[Bug 1001634] New: A code review of dlmalloc.cxx revealed several weaknesses

[Bug 1001634] New: A code review of dlmalloc.cxx revealed several weaknesses

[bugzilla-daemon]

Please do not reply to this email. Use the web interface provided at:
http://bugs.ecos.sourceware.org/show_bug.cgi?id=1001634

           Summary: A code review of dlmalloc.cxx revealed several
                    weaknesses
           Product: eCos
           Version: CVS
          Platform: All
        OS/Version: All
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: normal
         Component: Memory allocators
        AssignedTo: unassigned@bugs.ecos.sourceware.org
        ReportedBy: bernd.edlinger@hotmail.de
                CC: ecos-bugs@ecos.sourceware.org
             Class: Advice Request


Created an attachment (id=1848)
 --> (http://bugs.ecos.sourceware.org/attachment.cgi?id=1848)
proposed patch to improve the dlmalloc performance

Summary of this patch:
1. added: significant performance improvements when many free blocks >512 bytes
exist in the same bin.
2. fixed: binblock flag may be accidentally reset by malloc; backtrack loop
assumes startidx must be empty bin, which is not true.
3. fixed: malloc(0x7FFFFFF5..0x7FFFFFFF) returns min size block.
4. fixed: realloc(x,0x7FFFFFF5..0xFFFFFFFF) shrinks x to min size block.
5. fixed: realloc(x,0x7FFFFFE5..0x7FFFFFF4) crashes if x is at top of memory.
6. removed: last_remainder/locality of sequentially allocated chunks; this is
only useful for demand paged memory architectures.

1. all free blocks in the large bins are in a sorted list.
For instance there is a single list for all objects in the range 512..568 bytes
All objects in the range 576..632 go into the next list.
The lists are sorted by object size.
However this sorted list may become excessively long, which makes malloc/free
execute in O(n) time.
In the case of eCos this also adds to the isr/dpc latencies, which is not
acceptable.

The patch adds another double linked list of same sized objects, while the
forward pointer always points to the next larger element.
Therefore the mediun sized lists can be sorted in constant time.

2. as an optimization there is a bitset where 4 of these lists are
grouped together in a bin.
For instance all objects in the range 512..760 are in a bin,
which is represented by one bit in the bitset "binblocks".
This means if there is no object in the range 512..760 this bit is cleared,
and malloc will not look for free space of that size at all.

Due to a bug in the malloc code, the following may happen.
Assume there are free objects of size 512 but none of size 520..760.
Now the application may request 520 bytes.
Then happens this: binblocks bit for 512..760 is silently cleared,
and the next larger block is split up and returned.
If the application now requests 512 bytes, the exactly fitting free blocks
are not found. Instead larger blocks are split up and returned.
Even if the 520 bytes block is returned the binblock bit is not set again.
This results in memory fragmentation and memory leaks.

3. - 5. are simple range checks.

6. removed because it increases memory fragmentation, but eCos does not
benefit from this kind of locality as the memory is not demand paged.

-- 
Configure bugmail: http://bugs.ecos.sourceware.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the assignee for the bug.

[Bug 1001634] A code review of dlmalloc.cxx revealed several weaknesses

[bugzilla-daemon]

Please do not reply to this email. Use the web interface provided at:
http://bugs.ecos.sourceware.org/show_bug.cgi?id=1001634

--- Comment #1 from Bernd Edlinger <bernd.edlinger@hotmail.de> 2012-07-27 10:12:03 BST ---
This is a test code to demonstrate the very slow performance
of the current implementation. The parameter k is the number
of kilobytes to use for the test.

The execution time of memtest(n) = O(n^2) without the patch.
When the patch is applied the execution time will be O(n).

#include <malloc.h>
void memtest(unsigned k)
{
    unsigned i;
    void **p,**q;
    p=q=malloc(504);
    for (i=0; i<k; i++)
    {
        q=*q=malloc(504+4*(i%16));
    }
    *q=0;
    q=p;
    for (i=0; i<k; i++)
    {
        void **n=*q;
        q=*q=*n;
        free(n);
        if (!q || !*q) q=p;
    }
    free(p);
}

-- 
Configure bugmail: http://bugs.ecos.sourceware.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the assignee for the bug.

[Bug 1001634] A code review of dlmalloc.cxx revealed several weaknesses

[bugzilla-daemon]

Please do not reply to this email. Use the web interface provided at:
http://bugs.ecos.sourceware.org/show_bug.cgi?id=1001634

--- Comment #1 from Bernd Edlinger <bernd.edlinger@hotmail.de> 2012-07-27 10:12:03 BST ---
This is a test code to demonstrate the very slow performance
of the current implementation. The parameter k is the number
of kilobytes to use for the test.

The execution time of memtest(n) = O(n^2) without the patch.
When the patch is applied the execution time will be O(n).

#include <malloc.h>
void memtest(unsigned k)
{
    unsigned i;
    void **p,**q;
    p=q=malloc(504);
    for (i=0; i<k; i++)
    {
        q=*q=malloc(504+4*(i%16));
    }
    *q=0;
    q=p;
    for (i=0; i<k; i++)
    {
        void **n=*q;
        q=*q=*n;
        free(n);
        if (!q || !*q) q=p;
    }
    free(p);
}

-- 
Configure bugmail: http://bugs.ecos.sourceware.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.