Memory fragmentations-any solution?

Dear all,
For one of our module in a A/V based consumer product,we encounter
memory fragmentation problem in the following manner:
We have static buffer of  405KB.With in this 405KB,we need to allocate
memory dynamically depending on the requirement.The situation under
which fragmentation happens is:
First module gets 44KB
Second Module needs 512Bytes
Third one needs 44KB
Fourth one needs whole of 405KB

The product is in use for long time and the requests for memory comes
from a thirdparty application.In the scenerio explained above,44KB is
freed from first req,512 bytes is always in use once requested,44KB
third request is also freed.Fourth request is not able to find enough
memory due to 512 bytes in between.From the way of implementation it
seems to me its using First Fit algorithm.Increasing the size may be a
solution to solve this problem,but its not possible due to memory
constraints.
Also the module using this 405KB demands continguous memory per module
for effective operation.Static allocation is not possible,as in a
given situation we dont know the demand from third party for number of
modules it can create.Incase we want to defragment,the 512 bytes
prevents clubbing memory above it.So even though 44K is free,we are
not able to use it.512 bytes cannot be shifted dynamically because its
in use and shifting dynamic can cause disturbing viewer exp.

Can anyone point me any change need to be done in the allocation
method to regroup it and get memory?I can provide 512 bytes extra
memory as a whole but the modules using it need 256 Byte aligned
address which makes it even more tougher.

Looking farward for all your inputs and advanced thanks for the same,
Regards,
s.subbarayan

ssubbarayan wrote:
> Dear all,
> For one of our module in a A/V based consumer product,we encounter
> memory fragmentation problem in the following manner:
> We have static buffer of  405KB.With in this 405KB,we need to allocate
> memory dynamically depending on the requirement.The situation under
> which fragmentation happens is:
> First module gets 44KB
> Second Module needs 512Bytes
> Third one needs 44KB
> Fourth one needs whole of 405KB
> 
> The product is in use for long time and the requests for memory comes
> from a thirdparty application.In the scenerio explained above,44KB is
> freed from first req,512 bytes is always in use once requested,44KB
> third request is also freed.Fourth request is not able to find enough
> memory due to 512 bytes in between.From the way of implementation it
> seems to me its using First Fit algorithm.Increasing the size may be a
> solution to solve this problem,but its not possible due to memory
> constraints.
> Also the module using this 405KB demands continguous memory per module
> for effective operation.Static allocation is not possible,as in a
> given situation we dont know the demand from third party for number of
> modules it can create.Incase we want to defragment,the 512 bytes
> prevents clubbing memory above it.So even though 44K is free,we are
> not able to use it.512 bytes cannot be shifted dynamically because its
> in use and shifting dynamic can cause disturbing viewer exp.
> 
> Can anyone point me any change need to be done in the allocation
> method to regroup it and get memory?I can provide 512 bytes extra
> memory as a whole but the modules using it need 256 Byte aligned
> address which makes it even more tougher.
> 
> Looking farward for all your inputs and advanced thanks for the same,
> Regards,
> s.subbarayan

If the 512 byte block is never freed, and it is normally used at some 
point, then why is it being dynamically allocated at all?  Allocate it 
statically, or at least with a dynamic allocation at startup, then you 
have no fragmentation problem.

On Jan 4, 6:35=A0am, ssubbarayan <ssu...@gmail.com> wrote:
> Dear all,
> For one of our module in a A/V based consumer product,we encounter
> memory fragmentation problem in the following manner:
> We have static buffer of =A0405KB.With in this 405KB,we need to allocate
> memory dynamically depending on the requirement.The situation under
> which fragmentation happens is:
> First module gets 44KB
> Second Module needs 512Bytes
> Third one needs 44KB
> Fourth one needs whole of 405KB
>
> The product is in use for long time and the requests for memory comes
> from a thirdparty application.In the scenerio explained above,44KB is
> freed from first req,512 bytes is always in use once requested,44KB
> third request is also freed.Fourth request is not able to find enough
> memory due to 512 bytes in between.From the way of implementation it
> seems to me its using First Fit algorithm.Increasing the size may be a
> solution to solve this problem,but its not possible due to memory
> constraints.
> Also the module using this 405KB demands continguous memory per module
> for effective operation.Static allocation is not possible,as in a
> given situation we dont know the demand from third party for number of
> modules it can create.Incase we want to defragment,the 512 bytes
> prevents clubbing memory above it.So even though 44K is free,we are
> not able to use it.512 bytes cannot be shifted dynamically because its
> in use and shifting dynamic can cause disturbing viewer exp.
>
> Can anyone point me any change need to be done in the allocation
> method to regroup it and get memory?I can provide 512 bytes extra
> memory as a whole but the modules using it need 256 Byte aligned
> address which makes it even more tougher.
>
> Looking farward for all your inputs and advanced thanks for the same,
> Regards,
> s.subbarayan

you start with 405K
some dynamic allocation happens
one application demands ALL 405K

Of course the last request is going to fail. That's not fragmentation
failure, that is over allocation failure. It is an unreasonable
request given the resources.

I would request more avalable RAM (might not be possible due to other
hardware constraints, but that is the reasonable first choice). For
this case, I would say a minimum 44.5K, but say 64K would be better.
(someday you are going to add other applications. so planning for it
now with a little more RAM than the bare minimum.)

Second choice is changing that last application. 405K is an unusual
size to request. Is the case that it really needs EXACTLY 405K? Or
does it really just need the largest possible contiguous block of RAM?
In the latter case, can the allocate interface be changed to include
an option for requesting the largest available block? (requires
changes to that last application to use the new interface)

=46rom your description, the only other solution I can think of is to
shutdown all other applications while that last one is running. bottom
line is you are trying to fit 405.5K data into a 405K bucket. bits are
bound to spill out (and they are so hard to clean up).

HTH,
  ed

"ssubbarayan" <ssubba@gmail.com> wrote in message
news:b2bba22f-685f-4063-91cb-46db00b66615@i3g2000hsf.googlegroups.com...
> Dear all,
> For one of our module in a A/V based consumer product,we encounter
> memory fragmentation problem in the following manner:
> We have static buffer of  405KB.With in this 405KB,we need to allocate
> memory dynamically depending on the requirement.The situation under
> which fragmentation happens is:
> First module gets 44KB
> Second Module needs 512Bytes
> Third one needs 44KB
> Fourth one needs whole of 405KB
>
> The product is in use for long time and the requests for memory comes
> from a thirdparty application.In the scenerio explained above,44KB is
> freed from first req,512 bytes is always in use once requested,44KB
> third request is also freed.Fourth request is not able to find enough
> memory due to 512 bytes in between.From the way of implementation it
> seems to me its using First Fit algorithm.Increasing the size may be a
> solution to solve this problem,but its not possible due to memory
> constraints.
> Also the module using this 405KB demands continguous memory per module
> for effective operation.Static allocation is not possible,as in a
> given situation we dont know the demand from third party for number of
> modules it can create.Incase we want to defragment,the 512 bytes
> prevents clubbing memory above it.So even though 44K is free,we are
> not able to use it.512 bytes cannot be shifted dynamically because its
> in use and shifting dynamic can cause disturbing viewer exp.
>
> Can anyone point me any change need to be done in the allocation
> method to regroup it and get memory?I can provide 512 bytes extra
> memory as a whole but the modules using it need 256 Byte aligned
> address which makes it even more tougher.
>
> Looking farward for all your inputs and advanced thanks for the same,
> Regards,
> s.subbarayan


1. Make two heaps: one for the small blocks, the other one for the big
blocks. Or allocate the memory for the small blocks and for the big blocks
starting from from the opposite sides of one heap.

2. If you manage the memory dynamically, the total allocation should never
exceed ~50% of heap.

Vladimir Vassilevsky
DSP and Mixed Signal Consultant
www.abvolt.com

On Jan 4, 5:35=A0am, ssubbarayan <ssu...@gmail.com> wrote:
> Dear all,
> For one of our module in a A/V based consumer product,we encounter
> memory fragmentation problem in the following manner:
> We have static buffer of =A0405KB.With in this 405KB,we need to allocate
> memory dynamically depending on the requirement.The situation under
> which fragmentation happens is:
> First module gets 44KB
> Second Module needs 512Bytes
> Third one needs 44KB
> Fourth one needs whole of 405KB
>
> The product is in use for long time and the requests for memory comes
> from a thirdparty application.In the scenerio explained above,44KB is
> freed from first req,512 bytes is always in use once requested,44KB
> third request is also freed.Fourth request is not able to find enough
> memory due to 512 bytes in between.From the way of implementation it
> seems to me its using First Fit algorithm.Increasing the size may be a
> solution to solve this problem,but its not possible due to memory
> constraints.
> Also the module using this 405KB demands continguous memory per module
> for effective operation.Static allocation is not possible,as in a
> given situation we dont know the demand from third party for number of
> modules it can create.Incase we want to defragment,the 512 bytes
> prevents clubbing memory above it.So even though 44K is free,we are
> not able to use it.512 bytes cannot be shifted dynamically because its
> in use and shifting dynamic can cause disturbing viewer exp.
>
> Can anyone point me any change need to be done in the allocation
> method to regroup it and get memory?I can provide 512 bytes extra
> memory as a whole but the modules using it need 256 Byte aligned
> address which makes it even more tougher.
>
> Looking farward for all your inputs and advanced thanks for the same,
> Regards,
> s.subbarayan

First, I'll assume that your original problem statement was in error.
You said that:

> We have static buffer of 405KB.  Within this 405KB, we need to allocate me=
mory dynamically depending on the requirement.  The situation under which fr=
agmentation happens is:
> First module gets 44KB
> Second Module needs 512Bytes
> Third one needs 44KB
> Fourth one needs whole of 405KB

If the total memory available is 405 KB, and you allocate 44 KB, 0.5
KB, 44 KB, then free 44 KB and 44 KB, you only have 404.5 KB left,
which is obviously never going to provide the needed 405 KB for the
fourth module.  So, for any solution to be possible, the original
static buffer needs to be 405.5 KB in size, or the fourth module
request needs to be only 404.5 KB.  In either case, the following
discussion applies.

In a non-real-time system, the classic solution to a dynamic memory
allocation failure, when the unused parts of the heap would
collectively satisfy the request,  is known as "garbage collection".
(See http://tinyurl.com/ad7yc for more details.)  That process
interrupts memory accesses to the heap while the unused parts of the
heap are coalesced into larger areas.  In your case, it would also
require the reallocation of the 512-byte area to a new address, and
your code would have to expect that the pointer to that 512-byte area
(maintained in a static area of RAM that contains an array of pointers
to all allocated heap elements) could change when the garbage
collection takes place.

Garbage collection usually isn't done in real-time systems because for
an arbitrarily complex heap, the garbage collection process puts all
heap accesses on hold for an unreasonably long time.  But in a simple
case like yours, it might be acceptable.

As said earlier, other solutions are:

1.  Allocate small blocks from one end of the heap, and large blocks
from the other end of the heap, or use separate heaps.

2.  Allocate the 512-byte area before, or after, all of the large
areas.

3.  Make the 512-byte area static.

If that last solution is acceptable, it's by far the easiest.

ssubbarayan wrote:

> We have static buffer of  405KB.With in this 405KB,we need to allocate
> memory dynamically depending on the requirement.The situation under
> which fragmentation happens is:
[...]
> Fourth one needs whole of 405KB

That's practically guaranteed to fail, no matter what algorithm you use.
You can't seriously expect any heap management algorithm to be able to 
allocate you the entire heap whenever you feel like it.

> Can anyone point me any change need to be done in the allocation
> method to regroup it and get memory?

> I can provide 512 bytes extra
> memory as a whole but the modules using it need 256 Byte aligned
> address which makes it even more tougher.

Allocate those 256 bytes statically, then.  Why did you put them on the 
heap in the first place?

Summing it up: you don't "solve" memory fragmentation --- you avoid it.