From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 14411 invoked by alias); 27 Jul 2012 08:19:20 -0000 Received: (qmail 14398 invoked by uid 22791); 27 Jul 2012 08:19:18 -0000 X-SWARE-Spam-Status: No, hits=-2.0 required=5.0 tests=AWL,BAYES_00,T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from hagrid.ecoscentric.com (HELO mail.ecoscentric.com) (212.13.207.197) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Fri, 27 Jul 2012 08:19:03 +0000 Received: by mail.ecoscentric.com (Postfix, from userid 48) id 2FF952F78007; Fri, 27 Jul 2012 09:19:01 +0100 (BST) From: bugzilla-daemon@bugs.ecos.sourceware.org To: unassigned@bugs.ecos.sourceware.org Subject: [Bug 1001634] New: A code review of dlmalloc.cxx revealed several weaknesses X-Bugzilla-Reason: AssignedTo X-Bugzilla-Type: new X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: eCos X-Bugzilla-Component: Memory allocators X-Bugzilla-Keywords: X-Bugzilla-Severity: enhancement X-Bugzilla-Who: bernd.edlinger@hotmail.de X-Bugzilla-Status: UNCONFIRMED X-Bugzilla-Priority: normal X-Bugzilla-Assigned-To: unassigned@bugs.ecos.sourceware.org X-Bugzilla-Target-Milestone: --- X-Bugzilla-Changed-Fields: Message-ID: X-Bugzilla-URL: http://bugs.ecos.sourceware.org/ Auto-Submitted: auto-generated Content-Type: text/plain; charset="UTF-8" MIME-Version: 1.0 Date: Fri, 27 Jul 2012 08:19:00 -0000 Mailing-List: contact ecos-bugs-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Post: List-Help: , Sender: ecos-bugs-owner@sourceware.org X-SW-Source: 2012/txt/msg01091.txt.bz2 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.