petermeier wrote on Tuesday, December 21, 2010:
I have finished another heap implementation, due to the reason that iam working a lot with usb devices (where i have to allocate and free a lot of buffers at runtime). The main problem of heap2 is that its not re-using freed memory regions, it only appends new buffers. So if you run the following example, heap2 will stuck quite fast:
for(i=0;i<5000;i++) { p = alloc(i); free(p) }; It will stuck with 25k of heap at around 700 calls… This is sad…
So created my own heap manager.
Some examples: heap is ~400 bytes.
a1,a2,a3,a4 allocating each 100 bytes.
memoylayout:
000…099 = a1,
100…199 = a2,
200…299 = a3,
300…399 = a4
Heap is full…
a2 and a3 are being freed:
memoylayout:
000…099 = a1,
100…299 (free),
300…399 = a4
On heap are available 200 bytes…
a2 and a3 and a5, a6 are allocating each 50 bytes
memoylayout:
000…099 = a1,
100…149 = a2,
150…199 = a3,
200…249 = a5,
250…299 = a6,
300…399 = a4
Now heap is full…
a1 and a2 are freed now
memoylayout:
000…0149 (free),
150…199 = a3,
200…249 = a5,
250…299 = a6,
300…399 = a4
free space on heap now 149…
You can allocate and free stuff like that the whole night, there will be no fragmentation at all…
The heap will be cleaned up with every call of free() function. The malloc() function tires to find the best suitable gap to avoid memory waste.
In my system network buffers and application buffer are allocated at startup and will be never touched. The only changeable thing is the usb stack, and even there i have a sorted allocation/deallocation, so no need to think about fragmentation .
The only optimization i haven’t done yet, is to implement a XOR-linked list, so the free() function could take some time.
If someone is interested, tell me, and i can post the source here somewhere.
Kind regards,
Peter