ecos: packages/services/memalloc/common/current/src/dlmalloc.cxx annotate

annotate packages/services/memalloc/common/current/src/dlmalloc.cxx @ 2455:fcbc1384c4e3

* src/dlmalloc.cxx (MALLOC_COPY): * cdl/memalloc.cdl: Use memmove instead of memcpy which can go wrong in realloc() when the new and old block overlaps. CYGIMP_MEMALLOC_ALLOCATOR_DLMALLOC_USE_MEMCPY has been retained instead of being renamed to ..._MEMMOVE to help backward compatibility with older configurations. Thanks to Oyvind Harboe and Dave Lawrence.

author	asl
date	Sun, 06 Jan 2008 12:17:41 +0000
parents	5b91c0bea75a
children	07fc475e1c28

rev	line source
115 6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1 //==========================================================================
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	2 //
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	3 // dlmalloc.cxx
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	4 //
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	5 // Port of Doug Lea's malloc implementation
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	6 //
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	7 //==========================================================================
208 e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	8 //####ECOSGPLCOPYRIGHTBEGIN####
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	9 // -------------------------------------------
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	10 // This file is part of eCos, the Embedded Configurable Operating System.
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	11 // Copyright (C) 1998, 1999, 2000, 2001, 2002 Red Hat, Inc.
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	12 //
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	13 // eCos is free software; you can redistribute it and/or modify it under
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	14 // the terms of the GNU General Public License as published by the Free
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	15 // Software Foundation; either version 2 or (at your option) any later version.
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	16 //
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	17 // eCos is distributed in the hope that it will be useful, but WITHOUT ANY
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	18 // WARRANTY; without even the implied warranty of MERCHANTABILITY or
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	19 // FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	20 // for more details.
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	21 //
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	22 // You should have received a copy of the GNU General Public License along
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	23 // with eCos; if not, write to the Free Software Foundation, Inc.,
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	24 // 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	25 //
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	26 // As a special exception, if other files instantiate templates or use macros
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	27 // or inline functions from this file, or you compile this file and link it
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	28 // with other works to produce a work based on this file, this file does not
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	29 // by itself cause the resulting work to be covered by the GNU General Public
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	30 // License. However the source code for this file must still be made available
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	31 // in accordance with section (3) of the GNU General Public License.
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	32 //
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	33 // This exception does not invalidate any other reasons why a work based on
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	34 // this file might be covered by the GNU General Public License.
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	35 //
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	36 // Alternative licenses for eCos may be arranged by contacting Red Hat, Inc.
210 d2c90368aeef Merge from eCos master repository on 2002-05-23-21:39:14-BST jlarmour parents: 208 diff changeset	37 // at http://sources.redhat.com/ecos/ecos-license/
208 e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	38 // -------------------------------------------
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	39 //####ECOSGPLCOPYRIGHTEND####
115 6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	40 //==========================================================================
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	41 //#####DESCRIPTIONBEGIN####
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	42 //
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	43 // Author(s): Doug Lea (dl at g.oswego.edu), jlarmour
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	44 // Contributors:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	45 // Date: 2000-06-18
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	46 // Purpose: Doug Lea's malloc implementation
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	47 // Description: Doug Lea's malloc has been ported to eCos. This file
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	48 // provides the implementation in a way acceptable to eCos.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	49 // Substantial amounts of unnecessary bits (to eCos) of the
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	50 // original implementation have been removed to make the
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	51 // code more tractable. Note this may make a number of the
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	52 // comments appear to make little sense, or no longer apply!
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	53 // In particular, mmap support is removed entirely.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	54 // Also the memory is "sbrked" all at once at the
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	55 // beginning, covering the entire memory region given at
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	56 // construction, and there can be no more afterwards.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	57 // Usage: #include <cyg/memalloc/dlmalloc.hxx>
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	58 //
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	59 //
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	60 //####DESCRIPTIONEND####
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	61 //
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	62 //==========================================================================
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	63
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	64 // DOCUMENTATION FROM ORIGINAL FILE:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	65 // (some now irrelevant parts elided)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	66
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	67 //----------------------------------------------------------------------------
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	68
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	69 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	70 A version of malloc/free/realloc written by Doug Lea and released to the
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	71 public domain. Send questions/comments/complaints/performance data
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	72 to dl at cs.oswego.edu
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	73
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	74 * VERSION 2.6.6 Sun Mar 5 19:10:03 2000 Doug Lea (dl at gee)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	75
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	76 Note: There may be an updated version of this malloc obtainable at
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	77 ftp://g.oswego.edu/pub/misc/malloc.c
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	78 Check before installing!
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	79
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	80 * Why use this malloc?
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	81
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	82 This is not the fastest, most space-conserving, most portable, or
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	83 most tunable malloc ever written. However it is among the fastest
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	84 while also being among the most space-conserving, portable and tunable.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	85 Consistent balance across these factors results in a good general-purpose
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	86 allocator. For a high-level description, see
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	87 http://g.oswego.edu/dl/html/malloc.html
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	88
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	89 * Synopsis of public routines
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	90
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	91 (Much fuller descriptions are contained in the program documentation below.)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	92
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	93 [ these have of course been renamed in the eCos port ]a
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	94
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	95 malloc(size_t n);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	96 Return a pointer to a newly allocated chunk of at least n bytes, or null
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	97 if no space is available.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	98 free(Void_t* p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	99 Release the chunk of memory pointed to by p, or no effect if p is null.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	100 realloc(Void_t* p, size_t n);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	101 Return a pointer to a chunk of size n that contains the same data
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	102 as does chunk p up to the minimum of (n, p's size) bytes, or null
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	103 if no space is available. The returned pointer may or may not be
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	104 the same as p. If p is null, equivalent to malloc. realloc of
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	105 zero bytes calls free(p)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	106
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	107 * Vital statistics:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	108
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	109 Alignment: 8-byte
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	110 8 byte alignment is currently hardwired into the design. This
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	111 seems to suffice for all current machines and C compilers.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	112
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	113 Assumed pointer representation: 4 or 8 bytes
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	114 Code for 8-byte pointers is untested by me but has worked
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	115 reliably by Wolfram Gloger, who contributed most of the
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	116 changes supporting this.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	117
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	118 Assumed size_t representation: 4 or 8 bytes
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	119 Note that size_t is allowed to be 4 bytes even if pointers are 8.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	120
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	121 Minimum overhead per allocated chunk: 4 or 8 bytes
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	122 Each malloced chunk has a hidden overhead of 4 bytes holding size
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	123 and status information.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	124
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	125 Minimum allocated size: 4-byte ptrs: 16 bytes (including 4 overhead)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	126 8-byte ptrs: 24/32 bytes (including, 4/8 overhead)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	127
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	128 When a chunk is freed, 12 (for 4byte ptrs) or 20 (for 8 byte
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	129 ptrs but 4 byte size) or 24 (for 8/8) additional bytes are
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	130 needed; 4 (8) for a trailing size field
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	131 and 8 (16) bytes for free list pointers. Thus, the minimum
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	132 allocatable size is 16/24/32 bytes.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	133
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	134 Even a request for zero bytes (i.e., malloc(0)) returns a
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	135 pointer to something of the minimum allocatable size.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	136
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	137 Maximum allocated size: 4-byte size_t: 2^31 - 8 bytes
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	138 8-byte size_t: 2^63 - 16 bytes
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	139
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	140 It is assumed that (possibly signed) size_t bit values suffice to
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	141 represent chunk sizes. `Possibly signed' is due to the fact
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	142 that `size_t' may be defined on a system as either a signed or
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	143 an unsigned type. To be conservative, values that would appear
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	144 as negative numbers are avoided.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	145 Requests for sizes with a negative sign bit when the request
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	146 size is treaded as a long will return null.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	147
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	148 Maximum overhead wastage per allocated chunk: normally 15 bytes
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	149
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	150 Alignnment demands, plus the minimum allocatable size restriction
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	151 make the normal worst-case wastage 15 bytes (i.e., up to 15
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	152 more bytes will be allocated than were requested in malloc), with
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	153 one exception: because requests for zero bytes allocate non-zero space,
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	154 the worst case wastage for a request of zero bytes is 24 bytes.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	155
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	156 * Limitations
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	157
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	158 Here are some features that are NOT currently supported
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	159
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	160 * No user-definable hooks for callbacks and the like.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	161 * No automated mechanism for fully checking that all accesses
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	162 to malloced memory stay within their bounds.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	163 * No support for compaction.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	164
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	165 * Synopsis of compile-time options:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	166
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	167 People have reported using previous versions of this malloc on all
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	168 versions of Unix, sometimes by tweaking some of the defines
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	169 below. It has been tested most extensively on Solaris and
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	170 Linux. It is also reported to work on WIN32 platforms.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	171 People have also reported adapting this malloc for use in
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	172 stand-alone embedded systems.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	173
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	174 The implementation is in straight, hand-tuned ANSI C. Among other
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	175 consequences, it uses a lot of macros. Because of this, to be at
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	176 all usable, this code should be compiled using an optimizing compiler
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	177 (for example gcc -O2) that can simplify expressions and control
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	178 paths.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	179
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	180 CYGDBG_MEMALLOC_ALLOCATOR_DLMALLOC_DEBUG (default: NOT defined)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	181 Define to enable debugging. Adds fairly extensive assertion-based
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	182 checking to help track down memory errors, but noticeably slows down
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	183 execution.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	184 MALLOC_LOCK (default: NOT defined)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	185 MALLOC_UNLOCK (default: NOT defined)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	186 Define these to C expressions which are run to lock and unlock
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	187 the malloc data structures. Calls may be nested; that is,
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	188 MALLOC_LOCK may be called more than once before the corresponding
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	189 MALLOC_UNLOCK calls. MALLOC_LOCK must avoid waiting for a lock
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	190 that it already holds.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	191 MALLOC_ALIGNMENT (default: NOT defined)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	192 Define this to 16 if you need 16 byte alignment instead of 8 byte alignment
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	193 which is the normal default.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	194 SIZE_T_SMALLER_THAN_LONG (default: NOT defined)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	195 Define this when the platform you are compiling has
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	196 sizeof(long) > sizeof(size_t).
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	197 The option causes some extra code to be generated to handle operations
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	198 that use size_t operands and have long results.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	199 INTERNAL_SIZE_T (default: size_t)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	200 Define to a 32-bit type (probably `unsigned int') if you are on a
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	201 64-bit machine, yet do not want or need to allow malloc requests of
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	202 greater than 2^31 to be handled. This saves space, especially for
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	203 very small chunks.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	204
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	205 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	206
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	207 //----------------------------------------------------------------------------
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	208
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	209
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	210 /* Preliminaries */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	211
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	212 #include <pkgconf/memalloc.h> // configuration header
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	213 #include <pkgconf/infra.h> // CYGDBG_USE_ASSERTS
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	214 #include <cyg/infra/cyg_type.h> // types
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	215 #include <cyg/infra/cyg_ass.h> // assertions
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	216 #include <stddef.h> // for size_t
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	217 #include <cyg/memalloc/dlmalloc.hxx>
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	218
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	219 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	220 Debugging:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	221
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	222 Because freed chunks may be overwritten with link fields, this
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	223 malloc will often die when freed memory is overwritten by user
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	224 programs. This can be very effective (albeit in an annoying way)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	225 in helping track down dangling pointers.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	226
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	227 If you compile with CYGDBG_MEMALLOC_ALLOCATOR_DLMALLOC_DEBUG enabled, a
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	228 number of assertion checks are
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	229 enabled that will catch more memory errors. You probably won't be
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	230 able to make much sense of the actual assertion errors, but they
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	231 should help you locate incorrectly overwritten memory. The
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	232 checking is fairly extensive, and will slow down execution
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	233 noticeably. Calling get_status() with DEBUG set will
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	234 attempt to check every allocated and free chunk in the
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	235 course of computing the summmaries.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	236
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	237 Setting CYGDBG_MEMALLOC_ALLOCATOR_DLMALLOC_DEBUG may also be helpful if you
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	238 are trying to modify this code. The assertions in the check routines
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	239 spell out in more detail the assumptions and invariants underlying
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	240 the algorithms.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	241
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	242 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	243
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	244 #ifdef CYGDBG_MEMALLOC_ALLOCATOR_DLMALLOC_DEBUG
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	245 # define ASSERT(x) CYG_ASSERTC( x )
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	246 #else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	247 # define ASSERT(x) ((void)0)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	248 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	249
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	250
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	251 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	252 Define MALLOC_LOCK and MALLOC_UNLOCK to C expressions to run to
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	253 lock and unlock the malloc data structures. MALLOC_LOCK may be
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	254 called recursively.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	255 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	256
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	257 #ifndef MALLOC_LOCK
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	258 #define MALLOC_LOCK
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	259 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	260
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	261 #ifndef MALLOC_UNLOCK
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	262 #define MALLOC_UNLOCK
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	263 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	264
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	265 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	266 INTERNAL_SIZE_T is the word-size used for internal bookkeeping
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	267 of chunk sizes. On a 64-bit machine, you can reduce malloc
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	268 overhead by defining INTERNAL_SIZE_T to be a 32 bit `unsigned int'
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	269 at the expense of not being able to handle requests greater than
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	270 2^31. This limitation is hardly ever a concern; you are encouraged
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	271 to set this. However, the default version is the same as size_t.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	272 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	273
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	274 #ifndef INTERNAL_SIZE_T
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	275 #define INTERNAL_SIZE_T Cyg_Mempool_dlmalloc_Implementation::Cyg_dlmalloc_size_t
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	276 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	277
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	278 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	279 Following is needed on implementations whereby long > size_t.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	280 The problem is caused because the code performs subtractions of
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	281 size_t values and stores the result in long values. In the case
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	282 where long > size_t and the first value is actually less than
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	283 the second value, the resultant value is positive. For example,
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	284 (long)(x - y) where x = 0 and y is 1 ends up being 0x00000000FFFFFFFF
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	285 which is 2*31 - 1 instead of 0xFFFFFFFFFFFFFFFF. This is due to the
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	286 fact that assignment from unsigned to signed won't sign extend.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	287 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	288
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	289 #ifdef SIZE_T_SMALLER_THAN_LONG
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	290 #define long_sub_size_t(x, y) ( (x < y) ? -((long)(y - x)) : (x - y) );
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	291 #else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	292 #define long_sub_size_t(x, y) ( (long)(x - y) )
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	293 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	294
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	295
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	296 #ifdef CYGIMP_MEMALLOC_ALLOCATOR_DLMALLOC_USE_MEMCPY
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	297
2455 fcbc1384c4e3 * src/dlmalloc.cxx (MALLOC_COPY): asl parents: 1783 diff changeset	298 #include <string.h> // memmove, memset
115 6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	299
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	300 /* The following macros are only invoked with (2n+1)-multiples of
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	301 INTERNAL_SIZE_T units, with a positive integer n. This is exploited
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	302 for fast inline execution when n is small. */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	303
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	304 #define MALLOC_ZERO(charp, nbytes) \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	305 do { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	306 INTERNAL_SIZE_T mzsz = (nbytes); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	307 if(mzsz <= 9*sizeof(mzsz)) { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	308 INTERNAL_SIZE_T* mz = (INTERNAL_SIZE_T*) (charp); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	309 if(mzsz >= 5sizeof(mzsz)) { mz++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	310 *mz++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	311 if(mzsz >= 7sizeof(mzsz)) { mz++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	312 *mz++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	313 if(mzsz >= 9sizeof(mzsz)) { mz++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	314 *mz++ = 0; }}} \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	315 *mz++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	316 *mz++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	317 *mz = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	318 } else memset((charp), 0, mzsz); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	319 } while(0)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	320
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	321 #define MALLOC_COPY(dest,src,nbytes) \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	322 do { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	323 INTERNAL_SIZE_T mcsz = (nbytes); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	324 if(mcsz <= 9*sizeof(mcsz)) { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	325 INTERNAL_SIZE_T* mcsrc = (INTERNAL_SIZE_T*) (src); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	326 INTERNAL_SIZE_T* mcdst = (INTERNAL_SIZE_T*) (dest); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	327 if(mcsz >= 5sizeof(mcsz)) { mcdst++ = *mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	328 mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	329 if(mcsz >= 7sizeof(mcsz)) { mcdst++ = *mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	330 mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	331 if(mcsz >= 9sizeof(mcsz)) { mcdst++ = *mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	332 mcdst++ = mcsrc++; }}} \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	333 mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	334 mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	335 mcdst = mcsrc ; \
2455 fcbc1384c4e3 * src/dlmalloc.cxx (MALLOC_COPY): asl parents: 1783 diff changeset	336 } else memmove(dest, src, mcsz); \
115 6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	337 } while(0)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	338
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	339 #else /* !CYGIMP_MEMALLOC_ALLOCATOR_DLMALLOC_USE_MEMCPY */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	340
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	341 /* Use Duff's device for good zeroing/copying performance. */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	342
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	343 #define MALLOC_ZERO(charp, nbytes) \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	344 do { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	345 INTERNAL_SIZE_T* mzp = (INTERNAL_SIZE_T*)(charp); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	346 long mctmp = (nbytes)/sizeof(INTERNAL_SIZE_T), mcn; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	347 if (mctmp < 8) mcn = 0; else { mcn = (mctmp-1)/8; mctmp %= 8; } \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	348 switch (mctmp) { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	349 case 0: for(;;) { *mzp++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	350 case 7: *mzp++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	351 case 6: *mzp++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	352 case 5: *mzp++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	353 case 4: *mzp++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	354 case 3: *mzp++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	355 case 2: *mzp++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	356 case 1: *mzp++ = 0; if(mcn <= 0) break; mcn--; } \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	357 } \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	358 } while(0)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	359
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	360 #define MALLOC_COPY(dest,src,nbytes) \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	361 do { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	362 INTERNAL_SIZE_T* mcsrc = (INTERNAL_SIZE_T*) src; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	363 INTERNAL_SIZE_T* mcdst = (INTERNAL_SIZE_T*) dest; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	364 long mctmp = (nbytes)/sizeof(INTERNAL_SIZE_T), mcn; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	365 if (mctmp < 8) mcn = 0; else { mcn = (mctmp-1)/8; mctmp %= 8; } \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	366 switch (mctmp) { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	367 case 0: for(;;) { mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	368 case 7: mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	369 case 6: mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	370 case 5: mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	371 case 4: mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	372 case 3: mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	373 case 2: mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	374 case 1: mcdst++ = mcsrc++; if(mcn <= 0) break; mcn--; } \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	375 } \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	376 } while(0)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	377
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	378 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	379
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	380
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	381 //----------------------------------------------------------------------------
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	382
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	383 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	384 malloc_chunk details:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	385
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	386 (The following includes lightly edited explanations by Colin Plumb.)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	387
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	388 Chunks of memory are maintained using a `boundary tag' method as
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	389 described in e.g., Knuth or Standish. (See the paper by Paul
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	390 Wilson ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	391 survey of such techniques.) Sizes of free chunks are stored both
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	392 in the front of each chunk and at the end. This makes
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	393 consolidating fragmented chunks into bigger chunks very fast. The
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	394 size fields also hold bits representing whether chunks are free or
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	395 in use.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	396
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	397 An allocated chunk looks like this:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	398
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	399
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	400 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	401 \| Size of previous chunk, if allocated \| \|
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	402 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	403 \| Size of chunk, in bytes \|P\|
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	404 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	405 \| User data starts here... .
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	406 . .
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	407 . (malloc_usable_space() bytes) .
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	408 . \|
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	409 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	410 \| Size of chunk \|
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	411 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	412
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	413
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	414 Where "chunk" is the front of the chunk for the purpose of most of
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	415 the malloc code, but "mem" is the pointer that is returned to the
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	416 user. "Nextchunk" is the beginning of the next contiguous chunk.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	417
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	418 Chunks always begin on even word boundries, so the mem portion
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	419 (which is returned to the user) is also on an even word boundary, and
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	420 thus double-word aligned.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	421
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	422 Free chunks are stored in circular doubly-linked lists, and look like this:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	423
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	424 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	425 \| Size of previous chunk \|
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	426 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	427 `head:' \| Size of chunk, in bytes \|P\|
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	428 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	429 \| Forward pointer to next chunk in list \|
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	430 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	431 \| Back pointer to previous chunk in list \|
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	432 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	433 \| Unused space (may be 0 bytes long) .
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	434 . .
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	435 . \|
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	436 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	437 `foot:' \| Size of chunk, in bytes \|
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	438 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	439
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	440 The P (PREV_INUSE) bit, stored in the unused low-order bit of the
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	441 chunk size (which is always a multiple of two words), is an in-use
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	442 bit for the previous chunk. If that bit is clear, then the
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	443 word before the current chunk size contains the previous chunk
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	444 size, and can be used to find the front of the previous chunk.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	445 (The very first chunk allocated always has this bit set,
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	446 preventing access to non-existent (or non-owned) memory.)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	447
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	448 Note that the `foot' of the current chunk is actually represented
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	449 as the prev_size of the NEXT chunk. (This makes it easier to
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	450 deal with alignments etc).
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	451
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	452 The exception to all this is the special chunk `top', which doesn't
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	453 bother using the trailing size field since there is no next
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	454 contiguous chunk that would have to index off it. (After
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	455 initialization, `top' is forced to always exist. )
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	456
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	457 Available chunks are kept in any of several places (all declared below):
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	458
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	459 * `av': An array of chunks serving as bin headers for consolidated
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	460 chunks. Each bin is doubly linked. The bins are approximately
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	461 proportionally (log) spaced. There are a lot of these bins
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	462 (128). This may look excessive, but works very well in
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	463 practice. All procedures maintain the invariant that no
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	464 consolidated chunk physically borders another one. Chunks in
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	465 bins are kept in size order, with ties going to the
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	466 approximately least recently used chunk.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	467
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	468 The chunks in each bin are maintained in decreasing sorted order by
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	469 size. This is irrelevant for the small bins, which all contain
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	470 the same-sized chunks, but facilitates best-fit allocation for
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	471 larger chunks. (These lists are just sequential. Keeping them in
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	472 order almost never requires enough traversal to warrant using
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	473 fancier ordered data structures.) Chunks of the same size are
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	474 linked with the most recently freed at the front, and allocations
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	475 are taken from the back. This results in LRU or FIFO allocation
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	476 order, which tends to give each chunk an equal opportunity to be
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	477 consolidated with adjacent freed chunks, resulting in larger free
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	478 chunks and less fragmentation.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	479
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	480 * `top': The top-most available chunk (i.e., the one bordering the
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	481 end of available memory) is treated specially. It is never
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	482 included in any bin, is used only if no other chunk is
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	483 available.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	484
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	485 * `last_remainder': A bin holding only the remainder of the
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	486 most recently split (non-top) chunk. This bin is checked
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	487 before other non-fitting chunks, so as to provide better
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	488 locality for runs of sequentially allocated chunks.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	489
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	490 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	491
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	492 typedef struct Cyg_Mempool_dlmalloc_Implementation::malloc_chunk* mchunkptr;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	493
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	494 /* sizes, alignments */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	495
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	496 #define SIZE_SZ (sizeof(INTERNAL_SIZE_T))
1280 8d76b6216102 * cdl/memalloc.cdl, src/dlmalloc.cxx: Make the minimum memory asl parents: 210 diff changeset	497
8d76b6216102 * cdl/memalloc.cdl, src/dlmalloc.cxx: Make the minimum memory asl parents: 210 diff changeset	498 #ifdef CYGNUM_MEMALLOC_ALLOCATOR_DLMALLOC_ALIGNMENT
8d76b6216102 * cdl/memalloc.cdl, src/dlmalloc.cxx: Make the minimum memory asl parents: 210 diff changeset	499 #define MALLOC_ALIGNMENT (1<<(CYGNUM_MEMALLOC_ALLOCATOR_DLMALLOC_ALIGNMENT))
8d76b6216102 * cdl/memalloc.cdl, src/dlmalloc.cxx: Make the minimum memory asl parents: 210 diff changeset	500 #endif
8d76b6216102 * cdl/memalloc.cdl, src/dlmalloc.cxx: Make the minimum memory asl parents: 210 diff changeset	501
115 6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	502 #ifndef MALLOC_ALIGNMENT
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	503 #define MALLOC_ALIGN 8
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	504 #define MALLOC_ALIGNMENT (SIZE_SZ + SIZE_SZ)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	505 #else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	506 #define MALLOC_ALIGN MALLOC_ALIGNMENT
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	507 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	508 #define MALLOC_ALIGN_MASK (MALLOC_ALIGNMENT - 1)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	509 #define MINSIZE \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	510 (sizeof(struct Cyg_Mempool_dlmalloc_Implementation::malloc_chunk))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	511
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	512 /* conversion from malloc headers to user pointers, and back */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	513
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	514 #define chunk2mem(p) ((cyg_uint8)((char)(p) + 2*SIZE_SZ))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	515 #define mem2chunk(mem) ((mchunkptr)((char)(mem) - 2SIZE_SZ))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	516
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	517 /* pad request bytes into a usable size */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	518
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	519 #define request2size(req) \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	520 (((long)((req) + (SIZE_SZ + MALLOC_ALIGN_MASK)) < \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	521 (long)(MINSIZE + MALLOC_ALIGN_MASK)) ? ((MINSIZE + MALLOC_ALIGN_MASK) & ~(MALLOC_ALIGN_MASK)) : \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	522 (((req) + (SIZE_SZ + MALLOC_ALIGN_MASK)) & ~(MALLOC_ALIGN_MASK)))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	523
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	524 /* Check if m has acceptable alignment */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	525
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	526 #define aligned_OK(m) (((unsigned long)((m)) & (MALLOC_ALIGN_MASK)) == 0)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	527
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	528
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	529 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	530 Physical chunk operations
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	531 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	532
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	533
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	534 /* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	535
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	536 #define PREV_INUSE 0x1
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	537
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	538 /* Bits to mask off when extracting size */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	539
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	540 #define SIZE_BITS (PREV_INUSE)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	541
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	542
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	543 /* Ptr to next physical malloc_chunk. */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	544
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	545 #define next_chunk(p) ((mchunkptr)( ((char*)(p)) + ((p)->size & ~PREV_INUSE) ))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	546
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	547 /* Ptr to previous physical malloc_chunk */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	548
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	549 #define prev_chunk(p)\
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	550 ((mchunkptr)( ((char*)(p)) - ((p)->prev_size) ))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	551
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	552
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	553 /* Treat space at ptr + offset as a chunk */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	554
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	555 #define chunk_at_offset(p, s) ((mchunkptr)(((char*)(p)) + (s)))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	556
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	557 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	558 Dealing with use bits
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	559 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	560
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	561 /* extract p's inuse bit */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	562
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	563 #define inuse(p)\
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	564 ((((mchunkptr)(((char*)(p))+((p)->size & ~PREV_INUSE)))->size) & PREV_INUSE)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	565
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	566 /* extract inuse bit of previous chunk */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	567
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	568 #define prev_inuse(p) ((p)->size & PREV_INUSE)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	569
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	570 /* set/clear chunk as in use without otherwise disturbing */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	571
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	572 #define set_inuse(p)\
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	573 ((mchunkptr)(((char*)(p)) + ((p)->size & ~PREV_INUSE)))->size \|= PREV_INUSE
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	574
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	575 #define clear_inuse(p)\
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	576 ((mchunkptr)(((char*)(p)) + ((p)->size & ~PREV_INUSE)))->size &= ~(PREV_INUSE)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	577
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	578 /* check/set/clear inuse bits in known places */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	579
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	580 #define inuse_bit_at_offset(p, s)\
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	581 (((mchunkptr)(((char*)(p)) + (s)))->size & PREV_INUSE)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	582
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	583 #define set_inuse_bit_at_offset(p, s)\
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	584 (((mchunkptr)(((char*)(p)) + (s)))->size \|= PREV_INUSE)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	585
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	586 #define clear_inuse_bit_at_offset(p, s)\
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	587 (((mchunkptr)(((char*)(p)) + (s)))->size &= ~(PREV_INUSE))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	588
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	589
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	590 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	591 Dealing with size fields
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	592 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	593
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	594 /* Get size, ignoring use bits */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	595
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	596 #define chunksize(p) ((p)->size & ~(SIZE_BITS))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	597
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	598 /* Set size at head, without disturbing its use bit */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	599
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	600 #define set_head_size(p, s) ((p)->size = (((p)->size & PREV_INUSE) \| (s)))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	601
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	602 /* Set size/use ignoring previous bits in header */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	603
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	604 #define set_head(p, s) ((p)->size = (s))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	605
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	606 /* Set size at footer (only when chunk is not in use) */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	607
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	608 #define set_foot(p, s) (((mchunkptr)((char*)(p) + (s)))->prev_size = (s))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	609
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	610
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	611 //----------------------------------------------------------------------------
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	612
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	613 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	614 Bins
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	615
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	616 The bins, `av_' are an array of pairs of pointers serving as the
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	617 heads of (initially empty) doubly-linked lists of chunks, laid out
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	618 in a way so that each pair can be treated as if it were in a
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	619 malloc_chunk. (This way, the fd/bk offsets for linking bin heads
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	620 and chunks are the same).
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	621
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	622 Bins for sizes < 512 bytes contain chunks of all the same size, spaced
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	623 8 bytes apart. Larger bins are approximately logarithmically
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	624 spaced. (See the table below.) The `av_' array is never mentioned
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	625 directly in the code, but instead via bin access macros.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	626
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	627 Bin layout:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	628
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	629 64 bins of size 8
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	630 32 bins of size 64
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	631 16 bins of size 512
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	632 8 bins of size 4096
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	633 4 bins of size 32768
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	634 2 bins of size 262144
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	635 1 bin of size what's left
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	636
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	637 There is actually a little bit of slop in the numbers in bin_index
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	638 for the sake of speed. This makes no difference elsewhere.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	639
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	640 The special chunks `top' and `last_remainder' get their own bins,
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	641 (this is implemented via yet more trickery with the av_ array),
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	642 although `top' is never properly linked to its bin since it is
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	643 always handled specially.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	644
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	645 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	646
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	647 typedef struct Cyg_Mempool_dlmalloc_Implementation::malloc_chunk* mbinptr;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	648
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	649 /* access macros */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	650
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	651 #define bin_at(i) ((mbinptr)((char)&(av_[2(i) + 2]) - 2*SIZE_SZ))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	652 #define next_bin(b) ((mbinptr)((char)(b) + 2 sizeof(mbinptr)))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	653 #define prev_bin(b) ((mbinptr)((char)(b) - 2 sizeof(mbinptr)))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	654
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	655 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	656 The first 2 bins are never indexed. The corresponding av_ cells are instead
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	657 used for bookkeeping. This is not to save space, but to simplify
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	658 indexing, maintain locality, and avoid some initialization tests.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	659 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	660
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	661 #define top (bin_at(0)->fd) /* The topmost chunk */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	662 #define last_remainder (bin_at(1)) /* remainder from last split */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	663
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	664
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	665 /* Helper macro to initialize bins */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	666
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	667 #define IAV(i) bin_at(i), bin_at(i)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	668
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	669 #ifndef CYGIMP_MEMALLOC_ALLOCATOR_DLMALLOC_SAFE_MULTIPLE
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	670 static mbinptr av_[CYGPRI_MEMALLOC_ALLOCATOR_DLMALLOC_NAV * 2 + 2] = {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	671 0, 0,
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	672 IAV(0), IAV(1), IAV(2), IAV(3), IAV(4), IAV(5), IAV(6), IAV(7),
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	673 IAV(8), IAV(9), IAV(10), IAV(11), IAV(12), IAV(13), IAV(14), IAV(15),
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	674 IAV(16), IAV(17), IAV(18), IAV(19), IAV(20), IAV(21), IAV(22), IAV(23),
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	675 IAV(24), IAV(25), IAV(26), IAV(27), IAV(28), IAV(29), IAV(30), IAV(31),
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	676 IAV(32), IAV(33), IAV(34), IAV(35), IAV(36), IAV(37), IAV(38), IAV(39),
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	677 IAV(40), IAV(41), IAV(42), IAV(43), IAV(44), IAV(45), IAV(46), IAV(47),
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	678 IAV(48), IAV(49), IAV(50), IAV(51), IAV(52), IAV(53), IAV(54), IAV(55),
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	679 IAV(56), IAV(57), IAV(58), IAV(59), IAV(60), IAV(61), IAV(62), IAV(63),
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	680 IAV(64), IAV(65), IAV(66), IAV(67), IAV(68), IAV(69), IAV(70), IAV(71),
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	681 IAV(72), IAV(73), IAV(74), IAV(75), IAV(76), IAV(77), IAV(78), IAV(79),
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	682 IAV(80), IAV(81), IAV(82), IAV(83), IAV(84), IAV(85), IAV(86), IAV(87),
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	683 IAV(88), IAV(89), IAV(90), IAV(91), IAV(92), IAV(93), IAV(94), IAV(95),
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	684 IAV(96), IAV(97), IAV(98), IAV(99), IAV(100), IAV(101), IAV(102), IAV(103),
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	685 IAV(104), IAV(105), IAV(106), IAV(107), IAV(108), IAV(109), IAV(110), IAV(111),
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	686 IAV(112), IAV(113), IAV(114), IAV(115), IAV(116), IAV(117), IAV(118), IAV(119),
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	687 IAV(120), IAV(121), IAV(122), IAV(123), IAV(124), IAV(125), IAV(126), IAV(127)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	688 };
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	689 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	690
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	691 /* field-extraction macros */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	692
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	693 #define first(b) ((b)->fd)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	694 #define last(b) ((b)->bk)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	695
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	696 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	697 Indexing into bins
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	698 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	699
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	700 #define bin_index(sz) \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	701 (((((unsigned long)(sz)) >> 9) == 0) ? (((unsigned long)(sz)) >> 3): \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	702 ((((unsigned long)(sz)) >> 9) <= 4) ? 56 + (((unsigned long)(sz)) >> 6): \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	703 ((((unsigned long)(sz)) >> 9) <= 20) ? 91 + (((unsigned long)(sz)) >> 9): \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	704 ((((unsigned long)(sz)) >> 9) <= 84) ? 110 + (((unsigned long)(sz)) >> 12): \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	705 ((((unsigned long)(sz)) >> 9) <= 340) ? 119 + (((unsigned long)(sz)) >> 15): \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	706 ((((unsigned long)(sz)) >> 9) <= 1364) ? 124 + (((unsigned long)(sz)) >> 18): \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	707 126)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	708 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	709 bins for chunks < 512 are all spaced SMALLBIN_WIDTH bytes apart, and hold
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	710 identically sized chunks. This is exploited in malloc.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	711 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	712
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	713 #define MAX_SMALLBIN_SIZE 512
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	714 #define SMALLBIN_WIDTH 8
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	715 #define SMALLBIN_WIDTH_BITS 3
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	716 #define MAX_SMALLBIN (MAX_SMALLBIN_SIZE / SMALLBIN_WIDTH) - 1
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	717
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	718 #define smallbin_index(sz) (((unsigned long)(sz)) >> SMALLBIN_WIDTH_BITS)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	719
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	720 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	721 Requests are `small' if both the corresponding and the next bin are small
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	722 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	723
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	724 #define is_small_request(nb) (nb < MAX_SMALLBIN_SIZE - SMALLBIN_WIDTH)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	725
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	726 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	727 To help compensate for the large number of bins, a one-level index
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	728 structure is used for bin-by-bin searching. `binblocks' is a
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	729 one-word bitvector recording whether groups of BINBLOCKWIDTH bins
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	730 have any (possibly) non-empty bins, so they can be skipped over
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	731 all at once during during traversals. The bits are NOT always
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	732 cleared as soon as all bins in a block are empty, but instead only
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	733 when all are noticed to be empty during traversal in malloc.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	734 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	735
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	736 #define BINBLOCKWIDTH 4 /* bins per block */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	737
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	738 #define binblocks (bin_at(0)->size) /* bitvector of nonempty blocks */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	739
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	740 /* bin<->block macros */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	741
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	742 #define idx2binblock(ix) ((unsigned long)1 << (ix / BINBLOCKWIDTH))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	743 #define mark_binblock(ii) (binblocks \|= idx2binblock(ii))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	744 #define clear_binblock(ii) (binblocks &= ~(idx2binblock(ii)))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	745
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	746
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	747 //----------------------------------------------------------------------------
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	748
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	749 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	750 Debugging support
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	751 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	752
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	753 #ifdef CYGDBG_MEMALLOC_ALLOCATOR_DLMALLOC_DEBUG
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	754
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	755 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	756 These routines make a number of assertions about the states
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	757 of data structures that should be true at all times. If any
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	758 are not true, it's very likely that a user program has somehow
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	759 trashed memory. (It's also possible that there is a coding error
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	760 in malloc. In which case, please report it!)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	761 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	762
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	763 void
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	764 Cyg_Mempool_dlmalloc_Implementation::do_check_chunk( mchunkptr p )
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	765 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	766 INTERNAL_SIZE_T sz = p->size & ~PREV_INUSE;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	767
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	768 /* Check for legal address ... */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	769 ASSERT((cyg_uint8 *)p >= arenabase);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	770 if (p != top)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	771 ASSERT((cyg_uint8 )p + sz <= (cyg_uint8 )top);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	772 else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	773 ASSERT((cyg_uint8 *)p + sz <= arenabase + arenasize);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	774
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	775 } // Cyg_Mempool_dlmalloc_Implementation::do_check_chunk()
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	776
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	777
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	778 void
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	779 Cyg_Mempool_dlmalloc_Implementation::do_check_free_chunk(mchunkptr p)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	780 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	781 INTERNAL_SIZE_T sz = p->size & ~PREV_INUSE;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	782 mchunkptr next = chunk_at_offset(p, sz);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	783
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	784 do_check_chunk(p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	785
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	786 /* Check whether it claims to be free ... */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	787 ASSERT(!inuse(p));
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	788
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	789 /* Unless a special marker, must have OK fields */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	790 if ((long)sz >= (long)MINSIZE)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	791 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	792 ASSERT((sz & MALLOC_ALIGN_MASK) == 0);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	793 ASSERT(aligned_OK(chunk2mem(p)));
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	794 /* ... matching footer field */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	795 ASSERT(next->prev_size == sz);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	796 /* ... and is fully consolidated */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	797 ASSERT(prev_inuse(p));
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	798 ASSERT (next == top \|\| inuse(next));
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	799
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	800 /* ... and has minimally sane links */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	801 ASSERT(p->fd->bk == p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	802 ASSERT(p->bk->fd == p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	803 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	804 else /* markers are always of size SIZE_SZ */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	805 ASSERT(sz == SIZE_SZ);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	806 } // Cyg_Mempool_dlmalloc_Implementation::do_check_free_chunk()
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	807
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	808 void
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	809 Cyg_Mempool_dlmalloc_Implementation::do_check_inuse_chunk(mchunkptr p)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	810 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	811 mchunkptr next = next_chunk(p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	812 do_check_chunk(p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	813
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	814 /* Check whether it claims to be in use ... */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	815 ASSERT(inuse(p));
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	816
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	817 /* ... and is surrounded by OK chunks.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	818 Since more things can be checked with free chunks than inuse ones,
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	819 if an inuse chunk borders them and debug is on, it's worth doing them.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	820 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	821 if (!prev_inuse(p))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	822 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	823 mchunkptr prv = prev_chunk(p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	824 ASSERT(next_chunk(prv) == p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	825 do_check_free_chunk(prv);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	826 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	827 if (next == top)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	828 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	829 ASSERT(prev_inuse(next));
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	830 ASSERT(chunksize(next) >= MINSIZE);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	831 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	832 else if (!inuse(next))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	833 do_check_free_chunk(next);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	834
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	835 } // Cyg_Mempool_dlmalloc_Implementation::do_check_inuse_chunk(
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	836
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	837 void
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	838 Cyg_Mempool_dlmalloc_Implementation::do_check_malloced_chunk(mchunkptr p,
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	839 INTERNAL_SIZE_T s)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	840 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	841 INTERNAL_SIZE_T sz = p->size & ~PREV_INUSE;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	842 long room = long_sub_size_t(sz, s);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	843
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	844 do_check_inuse_chunk(p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	845
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	846 /* Legal size ... */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	847 ASSERT((long)sz >= (long)MINSIZE);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	848 ASSERT((sz & MALLOC_ALIGN_MASK) == 0);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	849 ASSERT(room >= 0);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	850 ASSERT(room < (long)MINSIZE);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	851
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	852 /* ... and alignment */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	853 ASSERT(aligned_OK(chunk2mem(p)));
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	854
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	855
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	856 /* ... and was allocated at front of an available chunk */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	857 ASSERT(prev_inuse(p));
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	858
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	859 } // Cyg_Mempool_dlmalloc_Implementation::do_check_malloced_chunk(
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	860
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	861
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	862 #define check_free_chunk(P) do_check_free_chunk(P)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	863 #define check_inuse_chunk(P) do_check_inuse_chunk(P)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	864 #define check_chunk(P) do_check_chunk(P)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	865 #define check_malloced_chunk(P,N) do_check_malloced_chunk(P,N)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	866 #else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	867 #define check_free_chunk(P)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	868 #define check_inuse_chunk(P)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	869 #define check_chunk(P)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	870 #define check_malloced_chunk(P,N)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	871 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	872
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	873
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	874 //----------------------------------------------------------------------------
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	875
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	876 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	877 Macro-based internal utilities
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	878 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	879
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	880
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	881 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	882 Linking chunks in bin lists.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	883 Call these only with variables, not arbitrary expressions, as arguments.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	884 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	885
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	886 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	887 Place chunk p of size s in its bin, in size order,
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	888 putting it ahead of others of same size.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	889 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	890
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	891
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	892 #define frontlink(P, S, IDX, BK, FD) \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	893 { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	894 if (S < MAX_SMALLBIN_SIZE) \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	895 { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	896 IDX = smallbin_index(S); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	897 mark_binblock(IDX); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	898 BK = bin_at(IDX); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	899 FD = BK->fd; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	900 P->bk = BK; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	901 P->fd = FD; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	902 FD->bk = BK->fd = P; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	903 } \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	904 else \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	905 { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	906 IDX = bin_index(S); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	907 BK = bin_at(IDX); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	908 FD = BK->fd; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	909 if (FD == BK) mark_binblock(IDX); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	910 else \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	911 { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	912 while (FD != BK && S < chunksize(FD)) FD = FD->fd; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	913 BK = FD->bk; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	914 } \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	915 P->bk = BK; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	916 P->fd = FD; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	917 FD->bk = BK->fd = P; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	918 } \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	919 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	920
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	921
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	922 /* take a chunk off a list */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	923
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	924 #define unlink(P, BK, FD) \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	925 { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	926 BK = P->bk; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	927 FD = P->fd; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	928 FD->bk = BK; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	929 BK->fd = FD; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	930 } \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	931
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	932 /* Place p as the last remainder */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	933
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	934 #define link_last_remainder(P) \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	935 { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	936 last_remainder->fd = last_remainder->bk = P; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	937 P->fd = P->bk = last_remainder; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	938 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	939
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	940 /* Clear the last_remainder bin */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	941
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	942 #define clear_last_remainder \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	943 (last_remainder->fd = last_remainder->bk = last_remainder)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	944
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	945
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	946 //----------------------------------------------------------------------------
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	947
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	948 Cyg_Mempool_dlmalloc_Implementation::Cyg_Mempool_dlmalloc_Implementation(
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	949 cyg_uint8 *base, cyg_int32 size,
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	950 CYG_ADDRWORD /* argthru */ )
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	951 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	952 arenabase = base;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	953 arenasize = size;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	954
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	955 CYG_ADDRESS front_misalign;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	956 cyg_int32 correction;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	957
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	958 #ifdef CYGIMP_MEMALLOC_ALLOCATOR_DLMALLOC_SAFE_MULTIPLE
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	959 cyg_ucount16 i;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	960 av_[0] = av_[1] = 0;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	961 for (i=0; i < CYGPRI_MEMALLOC_ALLOCATOR_DLMALLOC_NAV; i++) {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	962 av_[ i2+2 ] = av_[ i2+3 ] = bin_at(i);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	963 } // for
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	964
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	965 #elif defined(CYGDBG_USE_ASSERTS)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	966 static int instances;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	967 if ( ++instances > 1 )
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	968 CYG_FAIL( "Multiple dlmalloc instances but "
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	969 "CYGIMP_MEMALLOC_ALLOCATOR_DLMALLOC_SAFE_MULTIPLE "
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	970 "not defined" );
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	971 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	972
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	973 front_misalign = (CYG_ADDRESS)chunk2mem(base) & MALLOC_ALIGN_MASK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	974
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	975 if ( front_misalign > 0 ) {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	976 correction = (MALLOC_ALIGNMENT) - front_misalign;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	977 } else {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	978 correction = 0;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	979 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	980
159 511f4dc167f6 Merge from eCos master repository on 2001-05-18-01:30:05-BST jlarmour parents: 115 diff changeset	981 // too small to be useful?
1282 28c8c2fbb86e * src/dlmalloc.cxx (Cyg_Mempool_dlmalloc_Implementation): Fixed asl parents: 1280 diff changeset	982 if ( correction + 2*(unsigned)MALLOC_ALIGNMENT > (unsigned) size )
159 511f4dc167f6 Merge from eCos master repository on 2001-05-18-01:30:05-BST jlarmour parents: 115 diff changeset	983 // help catch errors. Don't fail now.
511f4dc167f6 Merge from eCos master repository on 2001-05-18-01:30:05-BST jlarmour parents: 115 diff changeset	984 arenabase = NULL;
511f4dc167f6 Merge from eCos master repository on 2001-05-18-01:30:05-BST jlarmour parents: 115 diff changeset	985 else {
511f4dc167f6 Merge from eCos master repository on 2001-05-18-01:30:05-BST jlarmour parents: 115 diff changeset	986 top = (mchunkptr)(base + correction);
511f4dc167f6 Merge from eCos master repository on 2001-05-18-01:30:05-BST jlarmour parents: 115 diff changeset	987 set_head(top, arenasize \| PREV_INUSE);
511f4dc167f6 Merge from eCos master repository on 2001-05-18-01:30:05-BST jlarmour parents: 115 diff changeset	988 }
115 6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	989 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	990
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	991 //----------------------------------------------------------------------------
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	992
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	993 /* Main public routines */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	994
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	995 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	996 Malloc Algorithm:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	997
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	998 The requested size is first converted into a usable form, `nb'.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	999 This currently means to add 4 bytes overhead plus possibly more to
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1000 obtain 8-byte alignment and/or to obtain a size of at least
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1001 MINSIZE (currently 16 bytes), the smallest allocatable size.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1002 (All fits are considered `exact' if they are within MINSIZE bytes.)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1003
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1004 From there, the first successful of the following steps is taken:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1005
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1006 1. The bin corresponding to the request size is scanned, and if
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1007 a chunk of exactly the right size is found, it is taken.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1008
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1009 2. The most recently remaindered chunk is used if it is big
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1010 enough. This is a form of (roving) first fit, used only in
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1011 the absence of exact fits. Runs of consecutive requests use
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1012 the remainder of the chunk used for the previous such request
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1013 whenever possible. This limited use of a first-fit style
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1014 allocation strategy tends to give contiguous chunks
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1015 coextensive lifetimes, which improves locality and can reduce
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1016 fragmentation in the long run.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1017
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1018 3. Other bins are scanned in increasing size order, using a
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1019 chunk big enough to fulfill the request, and splitting off
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1020 any remainder. This search is strictly by best-fit; i.e.,
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1021 the smallest (with ties going to approximately the least
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1022 recently used) chunk that fits is selected.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1023
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1024 4. If large enough, the chunk bordering the end of memory
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1025 (`top') is split off. (This use of `top' is in accord with
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1026 the best-fit search rule. In effect, `top' is treated as
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1027 larger (and thus less well fitting) than any other available
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1028 chunk since it can be extended to be as large as necessary
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1029 (up to system limitations).
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1030
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1031 All allocations are made from the the `lowest' part of any found
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1032 chunk. (The implementation invariant is that prev_inuse is
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1033 always true of any allocated chunk; i.e., that each allocated
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1034 chunk borders either a previously allocated and still in-use chunk,
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1035 or the base of its memory arena.)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1036
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1037 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1038
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1039 cyg_uint8 *
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1040 Cyg_Mempool_dlmalloc_Implementation::try_alloc( cyg_int32 bytes )
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1041 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1042 mchunkptr victim; /* inspected/selected chunk */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1043 INTERNAL_SIZE_T victim_size; /* its size */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1044 int idx; /* index for bin traversal */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1045 mbinptr bin; /* associated bin */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1046 mchunkptr remainder; /* remainder from a split */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1047 long remainder_size; /* its size */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1048 int remainder_index; /* its bin index */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1049 unsigned long block; /* block traverser bit */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1050 int startidx; /* first bin of a traversed block */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1051 mchunkptr fwd; /* misc temp for linking */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1052 mchunkptr bck; /* misc temp for linking */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1053 mbinptr q; /* misc temp */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1054
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1055 INTERNAL_SIZE_T nb;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1056
159 511f4dc167f6 Merge from eCos master repository on 2001-05-18-01:30:05-BST jlarmour parents: 115 diff changeset	1057 /* Allow uninitialised (zero sized) heaps because they could exist as a
511f4dc167f6 Merge from eCos master repository on 2001-05-18-01:30:05-BST jlarmour parents: 115 diff changeset	1058 * quirk of the MLT setup where a dynamically sized heap is at the top of
511f4dc167f6 Merge from eCos master repository on 2001-05-18-01:30:05-BST jlarmour parents: 115 diff changeset	1059 * memory. */
511f4dc167f6 Merge from eCos master repository on 2001-05-18-01:30:05-BST jlarmour parents: 115 diff changeset	1060 if (NULL==arenabase) return NULL;
511f4dc167f6 Merge from eCos master repository on 2001-05-18-01:30:05-BST jlarmour parents: 115 diff changeset	1061
115 6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1062 if ((long)bytes < 0) return 0;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1063
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1064 nb = request2size(bytes); /* padded request size; */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1065
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1066 MALLOC_LOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1067
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1068 /* Check for exact match in a bin */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1069
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1070 if (is_small_request(nb)) /* Faster version for small requests */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1071 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1072 idx = smallbin_index(nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1073
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1074 /* No traversal or size check necessary for small bins. */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1075
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1076 q = bin_at(idx);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1077 victim = last(q);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1078
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1079 #if MALLOC_ALIGN != 16
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1080 /* Also scan the next one, since it would have a remainder < MINSIZE */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1081 if (victim == q)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1082 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1083 q = next_bin(q);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1084 victim = last(q);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1085 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1086 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1087 if (victim != q)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1088 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1089 victim_size = chunksize(victim);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1090 unlink(victim, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1091 set_inuse_bit_at_offset(victim, victim_size);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1092 check_malloced_chunk(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1093 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1094 return chunk2mem(victim);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1095 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1096
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1097 idx += 2; /* Set for bin scan below. We've already scanned 2 bins. */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1098
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1099 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1100 else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1101 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1102 idx = bin_index(nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1103 bin = bin_at(idx);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1104
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1105 for (victim = last(bin); victim != bin; victim = victim->bk)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1106 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1107 victim_size = chunksize(victim);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1108 remainder_size = long_sub_size_t(victim_size, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1109
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1110 if (remainder_size >= (long)MINSIZE) /* too big */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1111 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1112 --idx; /* adjust to rescan below after checking last remainder */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1113 break;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1114 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1115
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1116 else if (remainder_size >= 0) /* exact fit */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1117 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1118 unlink(victim, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1119 set_inuse_bit_at_offset(victim, victim_size);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1120 check_malloced_chunk(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1121 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1122 return chunk2mem(victim);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1123 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1124 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1125
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1126 ++idx;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1127
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1128 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1129
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1130 /* Try to use the last split-off remainder */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1131
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1132 if ( (victim = last_remainder->fd) != last_remainder)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1133 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1134 victim_size = chunksize(victim);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1135 remainder_size = long_sub_size_t(victim_size, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1136
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1137 if (remainder_size >= (long)MINSIZE) /* re-split */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1138 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1139 remainder = chunk_at_offset(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1140 set_head(victim, nb \| PREV_INUSE);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1141 link_last_remainder(remainder);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1142 set_head(remainder, remainder_size \| PREV_INUSE);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1143 set_foot(remainder, remainder_size);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1144 check_malloced_chunk(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1145 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1146 return chunk2mem(victim);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1147 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1148
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1149 clear_last_remainder;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1150
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1151 if (remainder_size >= 0) /* exhaust */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1152 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1153 set_inuse_bit_at_offset(victim, victim_size);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1154 check_malloced_chunk(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1155 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1156 return chunk2mem(victim);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1157 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1158
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1159 /* Else place in bin */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1160
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1161 frontlink(victim, victim_size, remainder_index, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1162 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1163
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1164 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1165 If there are any possibly nonempty big-enough blocks,
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1166 search for best fitting chunk by scanning bins in blockwidth units.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1167 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1168
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1169 if ( (block = idx2binblock(idx)) <= binblocks)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1170 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1171
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1172 /* Get to the first marked block */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1173
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1174 if ( (block & binblocks) == 0)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1175 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1176 /* force to an even block boundary */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1177 idx = (idx & ~(BINBLOCKWIDTH - 1)) + BINBLOCKWIDTH;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1178 block <<= 1;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1179 while ((block & binblocks) == 0)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1180 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1181 idx += BINBLOCKWIDTH;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1182 block <<= 1;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1183 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1184 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1185
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1186 /* For each possibly nonempty block ... */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1187 for (;;)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1188 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1189 startidx = idx; /* (track incomplete blocks) */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1190 q = bin = bin_at(idx);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1191
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1192 /* For each bin in this block ... */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1193 do
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1194 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1195 /* Find and use first big enough chunk ... */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1196
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1197 for (victim = last(bin); victim != bin; victim = victim->bk)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1198 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1199 victim_size = chunksize(victim);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1200 remainder_size = long_sub_size_t(victim_size, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1201
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1202 if (remainder_size >= (long)MINSIZE) /* split */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1203 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1204 remainder = chunk_at_offset(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1205 set_head(victim, nb \| PREV_INUSE);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1206 unlink(victim, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1207 link_last_remainder(remainder);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1208 set_head(remainder, remainder_size \| PREV_INUSE);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1209 set_foot(remainder, remainder_size);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1210 check_malloced_chunk(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1211 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1212 return chunk2mem(victim);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1213 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1214
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1215 else if (remainder_size >= 0) /* take */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1216 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1217 set_inuse_bit_at_offset(victim, victim_size);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1218 unlink(victim, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1219 check_malloced_chunk(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1220 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1221 return chunk2mem(victim);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1222 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1223
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1224 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1225
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1226 bin = next_bin(bin);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1227
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1228 #if MALLOC_ALIGN == 16
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1229 if (idx < MAX_SMALLBIN)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1230 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1231 bin = next_bin(bin);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1232 ++idx;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1233 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1234 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1235 } while ((++idx & (BINBLOCKWIDTH - 1)) != 0);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1236
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1237 /* Clear out the block bit. */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1238
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1239 do /* Possibly backtrack to try to clear a partial block */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1240 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1241 if ((startidx & (BINBLOCKWIDTH - 1)) == 0)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1242 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1243 binblocks &= ~block;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1244 break;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1245 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1246 --startidx;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1247 q = prev_bin(q);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1248 } while (first(q) == q);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1249
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1250 /* Get to the next possibly nonempty block */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1251
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1252 if ( (block <<= 1) <= binblocks && (block != 0) )
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1253 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1254 while ((block & binblocks) == 0)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1255 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1256 idx += BINBLOCKWIDTH;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1257 block <<= 1;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1258 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1259 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1260 else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1261 break;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1262 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1263 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1264
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1265
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1266 /* Try to use top chunk */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1267
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1268 /* Require that there be a remainder, ensuring top always exists */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1269 remainder_size = long_sub_size_t(chunksize(top), nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1270 if (chunksize(top) < nb \|\| remainder_size < (long)MINSIZE)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1271 {
171 42f843b391aa Merge from eCos master repository on 2001-07-18-03:13:25-BST jlarmour parents: 163 diff changeset	1272 //diag_printf("chunksize(top)=%ld, nb=%d, remainder=%ld\n", chunksize(top),
42f843b391aa Merge from eCos master repository on 2001-07-18-03:13:25-BST jlarmour parents: 163 diff changeset	1273 // nb, remainder_size);
115 6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1274 MALLOC_UNLOCK;
1687 eb235374a7ae 2004-06-24 Oyvind Harboe <oyvind.harboe@zylin.com> asl parents: 1282 diff changeset	1275 CYG_MEMALLOC_FAIL(bytes);
115 6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1276 return NULL; /* propagate failure */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1277 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1278
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1279 victim = top;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1280 set_head(victim, nb \| PREV_INUSE);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1281 top = chunk_at_offset(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1282 set_head(top, remainder_size \| PREV_INUSE);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1283 check_malloced_chunk(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1284 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1285 return chunk2mem(victim);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1286
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1287 } // Cyg_Mempool_dlmalloc_Implementation::try_alloc()
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1288
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1289 //----------------------------------------------------------------------------
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1290
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1291 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1292 free() algorithm :
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1293
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1294 cases:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1295
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1296 1. free(NULL) has no effect.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1297
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1298 2. Chunks are consolidated as they arrive, and
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1299 placed in corresponding bins. (This includes the case of
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1300 consolidating with the current `last_remainder').
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1301 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1302
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1303 cyg_bool
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1304 Cyg_Mempool_dlmalloc_Implementation::free( cyg_uint8 *mem, cyg_int32 )
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1305 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1306 mchunkptr p; /* chunk corresponding to mem */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1307 INTERNAL_SIZE_T hd; /* its head field */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1308 INTERNAL_SIZE_T sz; /* its size */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1309 int idx; /* its bin index */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1310 mchunkptr next; /* next contiguous chunk */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1311 INTERNAL_SIZE_T nextsz; /* its size */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1312 INTERNAL_SIZE_T prevsz; /* size of previous contiguous chunk */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1313 mchunkptr bck; /* misc temp for linking */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1314 mchunkptr fwd; /* misc temp for linking */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1315 int islr; /* track whether merging with last_remainder */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1316
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1317 if (mem == NULL) /* free(NULL) has no effect */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1318 return false;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1319
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1320 MALLOC_LOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1321
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1322 p = mem2chunk(mem);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1323 hd = p->size;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1324
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1325 check_inuse_chunk(p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1326
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1327 sz = hd & ~PREV_INUSE;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1328 next = chunk_at_offset(p, sz);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1329 nextsz = chunksize(next);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1330
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1331 if (next == top) /* merge with top */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1332 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1333 sz += nextsz;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1334
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1335 if (!(hd & PREV_INUSE)) /* consolidate backward */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1336 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1337 prevsz = p->prev_size;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1338 p = chunk_at_offset(p, -((long) prevsz));
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1339 sz += prevsz;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1340 unlink(p, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1341 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1342
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1343 set_head(p, sz \| PREV_INUSE);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1344 top = p;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1345 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1346 return true;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1347 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1348
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1349 set_head(next, nextsz); /* clear inuse bit */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1350
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1351 islr = 0;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1352
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1353 if (!(hd & PREV_INUSE)) /* consolidate backward */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1354 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1355 prevsz = p->prev_size;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1356 p = chunk_at_offset(p, -((long) prevsz));
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1357 sz += prevsz;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1358
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1359 if (p->fd == last_remainder) /* keep as last_remainder */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1360 islr = 1;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1361 else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1362 unlink(p, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1363 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1364
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1365 if (!(inuse_bit_at_offset(next, nextsz))) /* consolidate forward */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1366 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1367 sz += nextsz;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1368
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1369 if (!islr && next->fd == last_remainder) /* re-insert last_remainder */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1370 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1371 islr = 1;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1372 link_last_remainder(p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1373 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1374 else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1375 unlink(next, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1376 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1377
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1378
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1379 set_head(p, sz \| PREV_INUSE);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1380 set_foot(p, sz);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1381 if (!islr)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1382 frontlink(p, sz, idx, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1383
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1384 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1385
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1386 return true;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1387 } // Cyg_Mempool_dlmalloc_Implementation::free()
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1388
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1389 //----------------------------------------------------------------------------
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1390
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1391 // resize existing allocation, if oldsize is non-NULL, previous
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1392 // allocation size is placed into it. If previous size not available,
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1393 // it is set to 0. NB previous allocation size may have been rounded up.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1394 // Occasionally the allocation can be adjusted backwards as well as,
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1395 // or instead of forwards, therefore the address of the resized
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1396 // allocation is returned, or NULL if no resizing was possible.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1397 // Note that this differs from ::realloc() in that no attempt is
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1398 // made to call malloc() if resizing is not possible - that is left
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1399 // to higher layers. The data is copied from old to new though.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1400 // The effects of alloc_ptr==NULL or newsize==0 are undefined
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1401
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1402
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1403 // DOCUMENTATION FROM ORIGINAL FILE:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1404 // (some now irrelevant parts elided)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1405 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1406 Realloc algorithm:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1407
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1408 If the reallocation is for additional space, and the
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1409 chunk can be extended, it is, else a malloc-copy-free sequence is
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1410 taken. There are several different ways that a chunk could be
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1411 extended. All are tried:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1412
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1413 * Extending forward into following adjacent free chunk.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1414 * Shifting backwards, joining preceding adjacent space
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1415 * Both shifting backwards and extending forward.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1416
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1417 If the reallocation is for less space, and the new request is for
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1418 a `small' (<512 bytes) size, then the newly unused space is lopped
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1419 off and freed.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1420
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1421 The old unix realloc convention of allowing the last-free'd chunk
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1422 to be used as an argument to realloc is no longer supported.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1423 I don't know of any programs still relying on this feature,
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1424 and allowing it would also allow too many other incorrect
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1425 usages of realloc to be sensible.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1426 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1427
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1428 cyg_uint8 *
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1429 Cyg_Mempool_dlmalloc_Implementation::resize_alloc( cyg_uint8 *oldmem,
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1430 cyg_int32 bytes,
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1431 cyg_int32 *poldsize )
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1432 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1433
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1434 INTERNAL_SIZE_T nb; /* padded request size */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1435
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1436 mchunkptr oldp; /* chunk corresponding to oldmem */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1437 INTERNAL_SIZE_T oldsize; /* its size */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1438
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1439 mchunkptr newp; /* chunk to return */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1440 INTERNAL_SIZE_T newsize; /* its size */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1441 cyg_uint8* newmem; /* corresponding user mem */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1442
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1443 mchunkptr next; /* next contiguous chunk after oldp */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1444 INTERNAL_SIZE_T nextsize; /* its size */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1445
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1446 mchunkptr prev; /* previous contiguous chunk before oldp */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1447 INTERNAL_SIZE_T prevsize; /* its size */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1448
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1449 mchunkptr remainder; /* holds split off extra space from newp */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1450 INTERNAL_SIZE_T remainder_size; /* its size */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1451
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1452 mchunkptr bck; /* misc temp for linking */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1453 mchunkptr fwd; /* misc temp for linking */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1454
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1455 MALLOC_LOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1456
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1457 newp = oldp = mem2chunk(oldmem);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1458 newsize = oldsize = chunksize(oldp);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1459
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1460 if (NULL != poldsize)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1461 *poldsize = oldsize - SIZE_SZ;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1462
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1463 nb = request2size(bytes);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1464
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1465 check_inuse_chunk(oldp);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1466
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1467 if ((long)(oldsize) < (long)(nb))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1468 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1469
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1470 /* Try expanding forward */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1471
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1472 next = chunk_at_offset(oldp, oldsize);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1473 if (next == top \|\| !inuse(next))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1474 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1475 nextsize = chunksize(next);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1476
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1477 /* Forward into top only if a remainder */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1478 if (next == top)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1479 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1480 if ((long)(nextsize + newsize) >= (long)(nb + MINSIZE))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1481 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1482 newsize += nextsize;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1483 top = chunk_at_offset(oldp, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1484 set_head(top, (newsize - nb) \| PREV_INUSE);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1485 set_head_size(oldp, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1486 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1487 return chunk2mem(oldp);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1488 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1489 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1490
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1491 /* Forward into next chunk */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1492 else if (((long)(nextsize + newsize) >= (long)(nb)))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1493 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1494 unlink(next, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1495 newsize += nextsize;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1496 goto split;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1497 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1498 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1499 else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1500 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1501 next = 0;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1502 nextsize = 0;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1503 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1504
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1505 /* Try shifting backwards. */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1506
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1507 if (!prev_inuse(oldp))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1508 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1509 prev = prev_chunk(oldp);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1510 prevsize = chunksize(prev);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1511
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1512 /* try forward + backward first to save a later consolidation */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1513
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1514 if (next != 0)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1515 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1516 /* into top */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1517 if (next == top)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1518 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1519 if ((long)(nextsize + prevsize + newsize) >= (long)(nb + MINSIZE))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1520 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1521 unlink(prev, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1522 newp = prev;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1523 newsize += prevsize + nextsize;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1524 newmem = chunk2mem(newp);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1525 MALLOC_COPY(newmem, oldmem, oldsize - SIZE_SZ);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1526 top = chunk_at_offset(newp, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1527 set_head(top, (newsize - nb) \| PREV_INUSE);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1528 set_head_size(newp, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1529 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1530 return newmem;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1531 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1532 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1533
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1534 /* into next chunk */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1535 else if (((long)(nextsize + prevsize + newsize) >= (long)(nb)))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1536 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1537 unlink(next, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1538 unlink(prev, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1539 newp = prev;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1540 newsize += nextsize + prevsize;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1541 newmem = chunk2mem(newp);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1542 MALLOC_COPY(newmem, oldmem, oldsize - SIZE_SZ);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1543 goto split;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1544 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1545 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1546
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1547 /* backward only */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1548 if (prev != 0 && (long)(prevsize + newsize) >= (long)nb)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1549 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1550 unlink(prev, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1551 newp = prev;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1552 newsize += prevsize;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1553 newmem = chunk2mem(newp);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1554 MALLOC_COPY(newmem, oldmem, oldsize - SIZE_SZ);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1555 goto split;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1556 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1557 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1558
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1559 // couldn't resize the allocation any direction, so return failure
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1560 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1561 return NULL;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1562 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1563
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1564
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1565 split: /* split off extra room in old or expanded chunk */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1566
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1567 remainder_size = long_sub_size_t(newsize, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1568
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1569 if (remainder_size >= (long)MINSIZE) /* split off remainder */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1570 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1571 remainder = chunk_at_offset(newp, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1572 set_head_size(newp, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1573 set_head(remainder, remainder_size \| PREV_INUSE);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1574 set_inuse_bit_at_offset(remainder, remainder_size);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1575 /* let free() deal with it */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1576 Cyg_Mempool_dlmalloc_Implementation::free( chunk2mem(remainder) );
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1577 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1578 else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1579 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1580 set_head_size(newp, newsize);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1581 set_inuse_bit_at_offset(newp, newsize);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1582 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1583
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1584 check_inuse_chunk(newp);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1585 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1586 return chunk2mem(newp);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1587
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1588 } // Cyg_Mempool_dlmalloc_Implementation::resize_alloc()
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1589
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1590 //----------------------------------------------------------------------------
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1591
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1592 // Get memory pool status
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1593 // flags is a bitmask of requested fields to fill in. The flags are
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1594 // defined in common.hxx
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1595 void
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1596 Cyg_Mempool_dlmalloc_Implementation::get_status(
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1597 cyg_mempool_status_flag_t flags,
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1598 Cyg_Mempool_Status &status )
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1599 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1600 if (0 != (flags&(CYG_MEMPOOL_STAT_FREEBLOCKS\|CYG_MEMPOOL_STAT_TOTALFREE\|
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1601 CYG_MEMPOOL_STAT_TOTALALLOCATED\|CYG_MEMPOOL_STAT_MAXFREE)))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1602 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1603 int i;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1604 mbinptr b;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1605 mchunkptr p;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1606 cyg_int32 chunksizep;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1607 cyg_int32 maxfree;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1608 #ifdef CYGDBG_MEMALLOC_ALLOCATOR_DLMALLOC_DEBUG
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1609 mchunkptr q;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1610 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1611
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1612 INTERNAL_SIZE_T avail = chunksize(top);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1613 int navail = ((long)(avail) >= (long)MINSIZE)? 1 : 0;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1614 maxfree = avail;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1615
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1616 for (i = 1; i < CYGPRI_MEMALLOC_ALLOCATOR_DLMALLOC_NAV; ++i) {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1617 b = bin_at(i);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1618 for (p = last(b); p != b; p = p->bk) {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1619 #ifdef CYGDBG_MEMALLOC_ALLOCATOR_DLMALLOC_DEBUG
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1620 check_free_chunk(p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1621 for (q = next_chunk(p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1622 (q < top) && inuse(q) &&
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1623 (long)(chunksize(q)) >= (long)MINSIZE;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1624 q = next_chunk(q))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1625 check_inuse_chunk(q);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1626 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1627 chunksizep = chunksize(p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1628 avail += chunksizep;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1629 if ( chunksizep > maxfree )
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1630 maxfree = chunksizep;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1631 navail++;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1632 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1633 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1634
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1635 if ( 0 != (flags & CYG_MEMPOOL_STAT_TOTALALLOCATED) )
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1636 status.totalallocated = arenasize - avail;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1637 // as quick or quicker to just set most of these, rather than
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1638 // test flag first
171 42f843b391aa Merge from eCos master repository on 2001-07-18-03:13:25-BST jlarmour parents: 163 diff changeset	1639 status.totalfree = (avail & ~(MALLOC_ALIGN_MASK)) - SIZE_SZ - MINSIZE;
42f843b391aa Merge from eCos master repository on 2001-07-18-03:13:25-BST jlarmour parents: 163 diff changeset	1640 CYG_ASSERT( ((avail + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)
42f843b391aa Merge from eCos master repository on 2001-07-18-03:13:25-BST jlarmour parents: 163 diff changeset	1641 >= MINSIZE, "free mem negative!" );
115 6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1642 status.freeblocks = navail;
171 42f843b391aa Merge from eCos master repository on 2001-07-18-03:13:25-BST jlarmour parents: 163 diff changeset	1643 status.maxfree = (maxfree & ~(MALLOC_ALIGN_MASK)) - SIZE_SZ - MINSIZE;
42f843b391aa Merge from eCos master repository on 2001-07-18-03:13:25-BST jlarmour parents: 163 diff changeset	1644 //diag_printf("raw mf: %d, ret mf: %d\n", maxfree, status.maxfree);
42f843b391aa Merge from eCos master repository on 2001-07-18-03:13:25-BST jlarmour parents: 163 diff changeset	1645 CYG_ASSERT( ((maxfree + SIZE_SZ + MALLOC_ALIGN_MASK) &
42f843b391aa Merge from eCos master repository on 2001-07-18-03:13:25-BST jlarmour parents: 163 diff changeset	1646 ~MALLOC_ALIGN_MASK) >= MINSIZE,
42f843b391aa Merge from eCos master repository on 2001-07-18-03:13:25-BST jlarmour parents: 163 diff changeset	1647 "max free block size negative!" );
115 6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1648 } // if
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1649
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1650 // as quick or quicker to just set most of these, rather than
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1651 // test flag first
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1652 status.arenabase = status.origbase = arenabase;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1653 status.arenasize = status.origsize = arenasize;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1654 status.maxoverhead = MINSIZE + MALLOC_ALIGNMENT;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1655
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1656 } // Cyg_Mempool_dlmalloc_Implementation::get_status()
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1657
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1658
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1659 //----------------------------------------------------------------------------
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1660
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1661 // EOF dlmalloc.cxx

Mercurial > ecos

annotate packages/services/memalloc/common/current/src/dlmalloc.cxx @ 2455:fcbc1384c4e3