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

annotate packages/services/memalloc/common/current/src/dlmalloc.cxx @ 163:0d2b193a635f

Merge from eCos master repository on 2001-06-22-17:38:39-BST

author	jlarmour
date	Fri, 22 Jun 2001 18:18:44 +0000
parents	511f4dc167f6
children	42f843b391aa

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 //==========================================================================
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	8 //####COPYRIGHTBEGIN####
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	9 //
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	10 // -------------------------------------------
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	11 // The contents of this file are subject to the Red Hat eCos Public License
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	12 // Version 1.1 (the "License"); you may not use this file except in
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	13 // compliance with the License. You may obtain a copy of the License at
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	14 // http://www.redhat.com/
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	15 //
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	16 // Software distributed under the License is distributed on an "AS IS"
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	17 // basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	18 // License for the specific language governing rights and limitations under
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	19 // the License.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	20 //
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	21 // The Original Code is eCos - Embedded Configurable Operating System,
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	22 // released September 30, 1998.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	23 //
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	24 // The Initial Developer of the Original Code is Red Hat.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	25 // Portions created by Red Hat are
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	26 // Copyright (C) 1998, 1999, 2000 Red Hat, Inc.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	27 // All Rights Reserved.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	28 // -------------------------------------------
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	29 //
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	30 //####COPYRIGHTEND####
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	31 //==========================================================================
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	32 //#####DESCRIPTIONBEGIN####
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	33 //
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	34 // 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	35 // Contributors:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	36 // Date: 2000-06-18
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	37 // Purpose: Doug Lea's malloc implementation
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	38 // 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	39 // 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	40 // 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	41 // 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	42 // 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	43 // 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	44 // 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	45 // 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	46 // 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	47 // 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	48 // Usage: #include <cyg/memalloc/dlmalloc.hxx>
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	49 //
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	50 //
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	51 //####DESCRIPTIONEND####
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	52 //
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	53 //==========================================================================
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	54
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	55 // DOCUMENTATION FROM ORIGINAL FILE:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	56 // (some now irrelevant parts elided)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	57
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 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	61 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	62 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	63 to dl at cs.oswego.edu
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	64
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	65 * 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	66
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	67 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	68 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	69 Check before installing!
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	70
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	71 * Why use this malloc?
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	72
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	73 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	74 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	75 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	76 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	77 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	78 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	79
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	80 * Synopsis of public routines
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 (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	83
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	84 [ 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	85
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	86 malloc(size_t n);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	87 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	88 if no space is available.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	89 free(Void_t* p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	90 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	91 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	92 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	93 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	94 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	95 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	96 zero bytes calls free(p)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	97
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	98 * Vital statistics:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	99
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	100 Alignment: 8-byte
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	101 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	102 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	103
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	104 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	105 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	106 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	107 changes supporting this.
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 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	110 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	111
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	112 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	113 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	114 and status information.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	115
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	116 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	117 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	118
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	119 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	120 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	121 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	122 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	123 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	124
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	125 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	126 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	127
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	128 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	129 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	130
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	131 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	132 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	133 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	134 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	135 as negative numbers are avoided.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	136 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	137 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	138
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	139 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	140
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	141 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	142 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	143 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	144 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	145 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	146
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	147 * Limitations
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	148
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	149 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	150
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	151 * 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	152 * 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	153 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	154 * No support for compaction.
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 * Synopsis of compile-time options:
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 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	159 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	160 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	161 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	162 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	163 stand-alone embedded systems.
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 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	166 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	167 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	168 (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	169 paths.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	170
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	171 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	172 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	173 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	174 execution.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	175 MALLOC_LOCK (default: NOT defined)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	176 MALLOC_UNLOCK (default: NOT defined)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	177 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	178 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	179 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	180 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	181 that it already holds.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	182 MALLOC_ALIGNMENT (default: NOT defined)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	183 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	184 which is the normal default.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	185 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	186 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	187 sizeof(long) > sizeof(size_t).
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	188 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	189 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	190 INTERNAL_SIZE_T (default: size_t)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	191 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	192 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	193 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	194 very small chunks.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	195
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	196 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	197
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	198 //----------------------------------------------------------------------------
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	199
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	200
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	201 /* Preliminaries */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	202
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	203 #include <pkgconf/memalloc.h> // configuration header
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	204 #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	205 #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	206 #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	207 #include <stddef.h> // for size_t
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	208 #include <cyg/memalloc/dlmalloc.hxx>
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 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	211 Debugging:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	212
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	213 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	214 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	215 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	216 in helping track down dangling pointers.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	217
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	218 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	219 number of assertion checks are
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	220 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	221 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	222 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	223 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	224 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	225 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	226 course of computing the summmaries.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	227
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	228 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	229 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	230 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	231 the algorithms.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	232
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	233 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	234
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	235 #ifdef CYGDBG_MEMALLOC_ALLOCATOR_DLMALLOC_DEBUG
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	236 # define ASSERT(x) CYG_ASSERTC( x )
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	237 #else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	238 # define ASSERT(x) ((void)0)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	239 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	240
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 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	244 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	245 called recursively.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	246 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	247
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	248 #ifndef MALLOC_LOCK
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	249 #define MALLOC_LOCK
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	250 #endif
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 #ifndef MALLOC_UNLOCK
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	253 #define MALLOC_UNLOCK
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	254 #endif
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 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	258 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	259 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	260 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	261 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	262 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	263 */
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 #ifndef INTERNAL_SIZE_T
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	266 #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	267 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	268
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	269 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	270 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	271 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	272 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	273 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	274 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	275 (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	276 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	277 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	278 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	279
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	280 #ifdef SIZE_T_SMALLER_THAN_LONG
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	281 #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	282 #else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	283 #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	284 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	285
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	286
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	287 #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	288
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	289 #include <string.h> // memcpy, memset
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	290
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	291 /* 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	292 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	293 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	294
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	295 #define MALLOC_ZERO(charp, nbytes) \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	296 do { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	297 INTERNAL_SIZE_T mzsz = (nbytes); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	298 if(mzsz <= 9*sizeof(mzsz)) { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	299 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	300 if(mzsz >= 5sizeof(mzsz)) { mz++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	301 *mz++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	302 if(mzsz >= 7sizeof(mzsz)) { mz++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	303 *mz++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	304 if(mzsz >= 9sizeof(mzsz)) { mz++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	305 *mz++ = 0; }}} \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	306 *mz++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	307 *mz++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	308 *mz = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	309 } else memset((charp), 0, mzsz); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	310 } while(0)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	311
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	312 #define MALLOC_COPY(dest,src,nbytes) \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	313 do { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	314 INTERNAL_SIZE_T mcsz = (nbytes); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	315 if(mcsz <= 9*sizeof(mcsz)) { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	316 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	317 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	318 if(mcsz >= 5sizeof(mcsz)) { mcdst++ = *mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	319 mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	320 if(mcsz >= 7sizeof(mcsz)) { mcdst++ = *mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	321 mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	322 if(mcsz >= 9sizeof(mcsz)) { mcdst++ = *mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	323 mcdst++ = mcsrc++; }}} \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	324 mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	325 mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	326 mcdst = mcsrc ; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	327 } else memcpy(dest, src, mcsz); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	328 } while(0)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	329
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	330 #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	331
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	332 /* 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	333
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	334 #define MALLOC_ZERO(charp, nbytes) \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	335 do { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	336 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	337 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	338 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	339 switch (mctmp) { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	340 case 0: for(;;) { *mzp++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	341 case 7: *mzp++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	342 case 6: *mzp++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	343 case 5: *mzp++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	344 case 4: *mzp++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	345 case 3: *mzp++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	346 case 2: *mzp++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	347 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	348 } \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	349 } while(0)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	350
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	351 #define MALLOC_COPY(dest,src,nbytes) \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	352 do { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	353 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	354 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	355 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	356 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	357 switch (mctmp) { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	358 case 0: for(;;) { mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	359 case 7: mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	360 case 6: mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	361 case 5: mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	362 case 4: mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	363 case 3: mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	364 case 2: mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	365 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	366 } \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	367 } while(0)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	368
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	369 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	370
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	371
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	372 //----------------------------------------------------------------------------
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	373
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	374 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	375 malloc_chunk details:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	376
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	377 (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	378
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	379 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	380 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	381 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	382 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	383 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	384 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	385 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	386 in use.
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 An allocated chunk looks like this:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	389
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	390
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	391 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	392 \| Size of previous chunk, if allocated \| \|
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	393 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	394 \| Size of chunk, in bytes \|P\|
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	395 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	396 \| User data starts here... .
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	397 . .
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	398 . (malloc_usable_space() bytes) .
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 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	401 \| Size of chunk \|
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	404
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	405 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	406 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	407 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	408
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	409 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	410 (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	411 thus double-word aligned.
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 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	414
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	415 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	416 \| Size of previous 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 `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	419 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	420 \| 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	421 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	422 \| 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	423 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	424 \| 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	425 . .
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 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	428 `foot:' \| Size of chunk, in bytes \|
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	429 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
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 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	432 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	433 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	434 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	435 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	436 (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	437 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	438
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	439 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	440 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	441 deal with alignments etc).
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	442
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	443 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	444 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	445 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	446 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	447
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	448 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	449
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	450 * `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	451 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	452 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	453 (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	454 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	455 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	456 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	457 approximately least recently used chunk.
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 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	460 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	461 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	462 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	463 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	464 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	465 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	466 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	467 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	468 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	469 chunks and less fragmentation.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	470
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	471 * `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	472 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	473 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	474 available.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	475
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	476 * `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	477 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	478 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	479 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	480
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	481 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	482
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	483 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	484
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	485 /* sizes, alignments */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	486
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	487 #define SIZE_SZ (sizeof(INTERNAL_SIZE_T))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	488 #ifndef MALLOC_ALIGNMENT
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	489 #define MALLOC_ALIGN 8
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	490 #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	491 #else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	492 #define MALLOC_ALIGN MALLOC_ALIGNMENT
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	493 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	494 #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	495 #define MINSIZE \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	496 (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	497
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	498 /* 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	499
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	500 #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	501 #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	502
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	503 /* 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	504
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	505 #define request2size(req) \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	506 (((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	507 (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	508 (((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	509
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	510 /* Check if m has acceptable alignment */
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 #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	513
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	514
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	515 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	516 Physical chunk operations
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	517 */
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	520 /* 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	521
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	522 #define PREV_INUSE 0x1
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 /* 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	525
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	526 #define SIZE_BITS (PREV_INUSE)
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 /* Ptr to next physical malloc_chunk. */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	530
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	531 #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	532
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	533 /* Ptr to previous physical malloc_chunk */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	534
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	535 #define prev_chunk(p)\
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	536 ((mchunkptr)( ((char*)(p)) - ((p)->prev_size) ))
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	539 /* 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	540
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	541 #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	542
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	543 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	544 Dealing with use bits
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	545 */
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 /* extract p's inuse bit */
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 inuse(p)\
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	550 ((((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	551
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	552 /* extract inuse bit of previous chunk */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	553
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	554 #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	555
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	556 /* 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	557
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	558 #define set_inuse(p)\
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	559 ((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	560
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	561 #define clear_inuse(p)\
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	562 ((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	563
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	564 /* 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	565
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	566 #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	567 (((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	568
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	569 #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	570 (((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	571
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	572 #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	573 (((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	574
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	575
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	576 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	577 Dealing with size fields
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	578 */
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 /* Get size, ignoring use bits */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	581
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	582 #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	583
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	584 /* 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	585
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	586 #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	587
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	588 /* 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	589
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	590 #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	591
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	592 /* 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	593
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	594 #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	595
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	596
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
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 Bins
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 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	603 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	604 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	605 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	606 and chunks are the same).
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 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	609 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	610 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	611 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	612
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	613 Bin layout:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	614
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	615 64 bins of size 8
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	616 32 bins of size 64
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	617 16 bins of size 512
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	618 8 bins of size 4096
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	619 4 bins of size 32768
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	620 2 bins of size 262144
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	621 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	622
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	623 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	624 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	625
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	626 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	627 (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	628 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	629 always handled specially.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	630
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	631 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	632
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	633 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	634
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	635 /* access macros */
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 #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	638 #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	639 #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	640
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	641 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	642 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	643 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	644 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	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 #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	648 #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	649
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 /* Helper macro to initialize bins */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	652
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	653 #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	654
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	655 #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	656 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	657 0, 0,
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	658 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	659 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	660 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	661 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	662 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	663 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	664 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	665 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	666 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	667 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	668 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	669 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	670 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	671 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	672 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	673 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	674 };
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	675 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	676
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	677 /* field-extraction macros */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	678
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	679 #define first(b) ((b)->fd)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	680 #define last(b) ((b)->bk)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	681
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	682 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	683 Indexing into bins
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	684 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	685
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	686 #define bin_index(sz) \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	687 (((((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	688 ((((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	689 ((((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	690 ((((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	691 ((((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	692 ((((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	693 126)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	694 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	695 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	696 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	697 */
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 #define MAX_SMALLBIN_SIZE 512
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	700 #define SMALLBIN_WIDTH 8
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	701 #define SMALLBIN_WIDTH_BITS 3
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	702 #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	703
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	704 #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	705
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	706 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	707 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	708 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	709
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	710 #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	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 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	714 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	715 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	716 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	717 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	718 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	719 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	720 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	721
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	722 #define BINBLOCKWIDTH 4 /* bins per block */
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 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	725
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	726 /* bin<->block macros */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	727
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	728 #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	729 #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	730 #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	731
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	732
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	733 //----------------------------------------------------------------------------
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 Debugging support
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	739 #ifdef CYGDBG_MEMALLOC_ALLOCATOR_DLMALLOC_DEBUG
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	740
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 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	743 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	744 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	745 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	746 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	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 void
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	750 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	751 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	752 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	753
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	754 /* Check for legal address ... */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	755 ASSERT((cyg_uint8 *)p >= arenabase);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	756 if (p != top)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	757 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	758 else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	759 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	760
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	761 } // 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	762
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	763
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	764 void
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	765 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	766 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	767 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	768 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	769
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	770 do_check_chunk(p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	771
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	772 /* 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	773 ASSERT(!inuse(p));
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 /* 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	776 if ((long)sz >= (long)MINSIZE)
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 ASSERT((sz & MALLOC_ALIGN_MASK) == 0);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	779 ASSERT(aligned_OK(chunk2mem(p)));
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	780 /* ... matching footer field */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	781 ASSERT(next->prev_size == sz);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	782 /* ... and is fully consolidated */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	783 ASSERT(prev_inuse(p));
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	784 ASSERT (next == top \|\| inuse(next));
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 /* ... and has minimally sane links */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	787 ASSERT(p->fd->bk == p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	788 ASSERT(p->bk->fd == p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	789 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	790 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	791 ASSERT(sz == SIZE_SZ);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	792 } // 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	793
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	794 void
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	795 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	796 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	797 mchunkptr next = next_chunk(p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	798 do_check_chunk(p);
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 /* 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	801 ASSERT(inuse(p));
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	802
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	803 /* ... and is surrounded by OK chunks.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	804 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	805 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	806 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	807 if (!prev_inuse(p))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	808 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	809 mchunkptr prv = prev_chunk(p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	810 ASSERT(next_chunk(prv) == p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	811 do_check_free_chunk(prv);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	812 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	813 if (next == top)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	814 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	815 ASSERT(prev_inuse(next));
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	816 ASSERT(chunksize(next) >= MINSIZE);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	817 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	818 else if (!inuse(next))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	819 do_check_free_chunk(next);
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 } // 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	822
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	823 void
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	824 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	825 INTERNAL_SIZE_T s)
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 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	828 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	829
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	830 do_check_inuse_chunk(p);
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 /* Legal size ... */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	833 ASSERT((long)sz >= (long)MINSIZE);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	834 ASSERT((sz & MALLOC_ALIGN_MASK) == 0);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	835 ASSERT(room >= 0);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	836 ASSERT(room < (long)MINSIZE);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	837
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	838 /* ... and alignment */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	839 ASSERT(aligned_OK(chunk2mem(p)));
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	842 /* ... 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	843 ASSERT(prev_inuse(p));
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	844
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	845 } // 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	846
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	847
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	848 #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	849 #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	850 #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	851 #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	852 #else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	853 #define check_free_chunk(P)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	854 #define check_inuse_chunk(P)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	855 #define check_chunk(P)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	856 #define check_malloced_chunk(P,N)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	857 #endif
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
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 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	863 Macro-based internal utilities
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	864 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	865
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	866
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	867 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	868 Linking chunks in bin lists.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	869 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	870 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	871
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 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	874 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	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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	878 #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	879 { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	880 if (S < MAX_SMALLBIN_SIZE) \
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 IDX = smallbin_index(S); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	883 mark_binblock(IDX); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	884 BK = bin_at(IDX); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	885 FD = BK->fd; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	886 P->bk = BK; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	887 P->fd = FD; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	888 FD->bk = BK->fd = P; \
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 else \
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 IDX = bin_index(S); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	893 BK = bin_at(IDX); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	894 FD = BK->fd; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	895 if (FD == BK) mark_binblock(IDX); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	896 else \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	897 { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	898 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	899 BK = FD->bk; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	900 } \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	901 P->bk = BK; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	902 P->fd = FD; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	903 FD->bk = BK->fd = P; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	904 } \
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	907
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	908 /* take a chunk off a list */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	909
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	910 #define unlink(P, BK, FD) \
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 BK = P->bk; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	913 FD = P->fd; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	914 FD->bk = BK; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	915 BK->fd = FD; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	916 } \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	917
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	918 /* Place p as the last remainder */
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 #define link_last_remainder(P) \
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 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	923 P->fd = P->bk = last_remainder; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	924 }
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 /* Clear the last_remainder bin */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	927
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	928 #define clear_last_remainder \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	929 (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	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 //----------------------------------------------------------------------------
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 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	935 cyg_uint8 *base, cyg_int32 size,
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	936 CYG_ADDRWORD /* argthru */ )
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	937 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	938 arenabase = base;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	939 arenasize = size;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	940
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	941 CYG_ADDRESS front_misalign;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	942 cyg_int32 correction;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	943
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	944 #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	945 cyg_ucount16 i;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	946 av_[0] = av_[1] = 0;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	947 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	948 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	949 } // for
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	950
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	951 #elif defined(CYGDBG_USE_ASSERTS)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	952 static int instances;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	953 if ( ++instances > 1 )
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	954 CYG_FAIL( "Multiple dlmalloc instances but "
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	955 "CYGIMP_MEMALLOC_ALLOCATOR_DLMALLOC_SAFE_MULTIPLE "
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	956 "not defined" );
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	957 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	958
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	959 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	960
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	961 if ( front_misalign > 0 ) {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	962 correction = (MALLOC_ALIGNMENT) - front_misalign;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	963 } else {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	964 correction = 0;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	965 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	966
159 511f4dc167f6 Merge from eCos master repository on 2001-05-18-01:30:05-BST jlarmour parents: 115 diff changeset	967 // too small to be useful?
511f4dc167f6 Merge from eCos master repository on 2001-05-18-01:30:05-BST jlarmour parents: 115 diff changeset	968 if ( correction + 2*MALLOC_ALIGNMENT > (unsigned) size )
511f4dc167f6 Merge from eCos master repository on 2001-05-18-01:30:05-BST jlarmour parents: 115 diff changeset	969 // 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	970 arenabase = NULL;
511f4dc167f6 Merge from eCos master repository on 2001-05-18-01:30:05-BST jlarmour parents: 115 diff changeset	971 else {
511f4dc167f6 Merge from eCos master repository on 2001-05-18-01:30:05-BST jlarmour parents: 115 diff changeset	972 top = (mchunkptr)(base + correction);
511f4dc167f6 Merge from eCos master repository on 2001-05-18-01:30:05-BST jlarmour parents: 115 diff changeset	973 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	974 }
115 6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	975 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	976
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	977 //----------------------------------------------------------------------------
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	978
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	979 /* Main public routines */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	980
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	981 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	982 Malloc Algorithm:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	983
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	984 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	985 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	986 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	987 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	988 (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	989
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	990 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	991
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	992 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	993 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	994
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	995 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	996 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	997 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	998 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	999 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	1000 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	1001 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	1002 fragmentation in the long run.
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 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	1005 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	1006 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	1007 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	1008 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	1009
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1010 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	1011 (`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	1012 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	1013 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	1014 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	1015 (up to system limitations).
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1016
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1017 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	1018 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	1019 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	1020 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	1021 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	1022
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1025 cyg_uint8 *
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1026 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	1027 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1028 mchunkptr victim; /* inspected/selected chunk */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1029 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	1030 int idx; /* index for bin traversal */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1031 mbinptr bin; /* associated bin */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1032 mchunkptr remainder; /* remainder from a split */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1033 long remainder_size; /* its size */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1034 int remainder_index; /* its bin index */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1035 unsigned long block; /* block traverser bit */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1036 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	1037 mchunkptr fwd; /* misc temp for linking */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1038 mchunkptr bck; /* misc temp for linking */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1039 mbinptr q; /* misc temp */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1040
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1041 INTERNAL_SIZE_T nb;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1042
159 511f4dc167f6 Merge from eCos master repository on 2001-05-18-01:30:05-BST jlarmour parents: 115 diff changeset	1043 /* 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	1044 * 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	1045 * memory. */
511f4dc167f6 Merge from eCos master repository on 2001-05-18-01:30:05-BST jlarmour parents: 115 diff changeset	1046 if (NULL==arenabase) return NULL;
511f4dc167f6 Merge from eCos master repository on 2001-05-18-01:30:05-BST jlarmour parents: 115 diff changeset	1047
115 6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1048 if ((long)bytes < 0) return 0;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1049
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1050 nb = request2size(bytes); /* padded request size; */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1051
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1052 MALLOC_LOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1053
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1054 /* 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	1055
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1056 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	1057 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1058 idx = smallbin_index(nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1059
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1060 /* 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	1061
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1062 q = bin_at(idx);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1063 victim = last(q);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1064
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1065 #if MALLOC_ALIGN != 16
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1066 /* 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	1067 if (victim == q)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1068 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1069 q = next_bin(q);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1070 victim = last(q);
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 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1073 if (victim != q)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1074 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1075 victim_size = chunksize(victim);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1076 unlink(victim, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1077 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	1078 check_malloced_chunk(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1079 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1080 return chunk2mem(victim);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1081 }
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 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	1084
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 else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1087 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1088 idx = bin_index(nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1089 bin = bin_at(idx);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1090
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1091 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	1092 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1093 victim_size = chunksize(victim);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1094 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	1095
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1096 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	1097 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1098 --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	1099 break;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1100 }
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 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	1103 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1104 unlink(victim, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1105 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	1106 check_malloced_chunk(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1107 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1108 return chunk2mem(victim);
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 }
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;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1113
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 /* 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	1117
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1118 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	1119 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1120 victim_size = chunksize(victim);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1121 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	1122
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1123 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	1124 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1125 remainder = chunk_at_offset(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1126 set_head(victim, nb \| PREV_INUSE);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1127 link_last_remainder(remainder);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1128 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	1129 set_foot(remainder, remainder_size);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1130 check_malloced_chunk(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1131 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1132 return chunk2mem(victim);
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1135 clear_last_remainder;
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 >= 0) /* exhaust */
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 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	1140 check_malloced_chunk(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1141 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1142 return chunk2mem(victim);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1143 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1144
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1145 /* Else place in bin */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1146
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1147 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	1148 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1149
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 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	1152 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	1153 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1154
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1155 if ( (block = idx2binblock(idx)) <= binblocks)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1156 {
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 /* Get to the first marked block */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1159
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1160 if ( (block & binblocks) == 0)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1161 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1162 /* force to an even block boundary */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1163 idx = (idx & ~(BINBLOCKWIDTH - 1)) + BINBLOCKWIDTH;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1164 block <<= 1;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1165 while ((block & binblocks) == 0)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1166 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1167 idx += BINBLOCKWIDTH;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1168 block <<= 1;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1169 }
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 /* For each possibly nonempty block ... */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1173 for (;;)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1174 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1175 startidx = idx; /* (track incomplete blocks) */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1176 q = bin = bin_at(idx);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1177
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1178 /* For each bin in this block ... */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1179 do
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 /* 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	1182
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1183 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	1184 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1185 victim_size = chunksize(victim);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1186 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	1187
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1188 if (remainder_size >= (long)MINSIZE) /* split */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1189 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1190 remainder = chunk_at_offset(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1191 set_head(victim, nb \| PREV_INUSE);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1192 unlink(victim, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1193 link_last_remainder(remainder);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1194 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	1195 set_foot(remainder, remainder_size);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1196 check_malloced_chunk(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1197 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1198 return chunk2mem(victim);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1199 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1200
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1201 else if (remainder_size >= 0) /* take */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1202 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1203 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	1204 unlink(victim, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1205 check_malloced_chunk(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1206 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1207 return chunk2mem(victim);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1208 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1209
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1210 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1211
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1212 bin = next_bin(bin);
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 #if MALLOC_ALIGN == 16
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1215 if (idx < MAX_SMALLBIN)
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 bin = next_bin(bin);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1218 ++idx;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1219 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1220 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1221 } while ((++idx & (BINBLOCKWIDTH - 1)) != 0);
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 /* Clear out the block bit. */
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 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	1226 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1227 if ((startidx & (BINBLOCKWIDTH - 1)) == 0)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1228 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1229 binblocks &= ~block;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1230 break;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1231 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1232 --startidx;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1233 q = prev_bin(q);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1234 } while (first(q) == q);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1235
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1236 /* 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	1237
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1238 if ( (block <<= 1) <= binblocks && (block != 0) )
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1239 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1240 while ((block & binblocks) == 0)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1241 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1242 idx += BINBLOCKWIDTH;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1243 block <<= 1;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1244 }
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 else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1247 break;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1248 }
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
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 /* Try to use top chunk */
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 /* 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	1255 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	1256 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	1257 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1258 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1259 return NULL; /* propagate failure */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1260 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1261
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1262 victim = top;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1263 set_head(victim, nb \| PREV_INUSE);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1264 top = chunk_at_offset(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1265 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	1266 check_malloced_chunk(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1267 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1268 return chunk2mem(victim);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1269
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1270 } // Cyg_Mempool_dlmalloc_Implementation::try_alloc()
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1271
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1272 //----------------------------------------------------------------------------
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1273
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1274 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1275 free() algorithm :
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1276
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1277 cases:
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 1. free(NULL) has no effect.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1280
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1281 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	1282 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	1283 consolidating with the current `last_remainder').
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1284 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1285
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1286 cyg_bool
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1287 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	1288 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1289 mchunkptr p; /* chunk corresponding to mem */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1290 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	1291 INTERNAL_SIZE_T sz; /* its size */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1292 int idx; /* its bin index */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1293 mchunkptr next; /* next contiguous chunk */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1294 INTERNAL_SIZE_T nextsz; /* its size */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1295 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	1296 mchunkptr bck; /* misc temp for linking */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1297 mchunkptr fwd; /* misc temp for linking */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1298 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	1299
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1300 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	1301 return false;
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 MALLOC_LOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1304
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1305 p = mem2chunk(mem);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1306 hd = p->size;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1307
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1308 check_inuse_chunk(p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1309
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1310 sz = hd & ~PREV_INUSE;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1311 next = chunk_at_offset(p, sz);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1312 nextsz = chunksize(next);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1313
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1314 if (next == top) /* merge with top */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1315 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1316 sz += nextsz;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1317
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1318 if (!(hd & PREV_INUSE)) /* consolidate backward */
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 prevsz = p->prev_size;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1321 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	1322 sz += prevsz;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1323 unlink(p, bck, fwd);
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1326 set_head(p, sz \| PREV_INUSE);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1327 top = p;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1328 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1329 return true;
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1332 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	1333
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1334 islr = 0;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1335
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1336 if (!(hd & PREV_INUSE)) /* consolidate backward */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1337 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1338 prevsz = p->prev_size;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1339 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	1340 sz += prevsz;
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 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	1343 islr = 1;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1344 else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1345 unlink(p, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1346 }
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 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	1349 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1350 sz += nextsz;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1351
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1352 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	1353 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1354 islr = 1;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1355 link_last_remainder(p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1356 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1357 else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1358 unlink(next, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1359 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1360
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1361
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1362 set_head(p, sz \| PREV_INUSE);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1363 set_foot(p, sz);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1364 if (!islr)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1365 frontlink(p, sz, idx, bck, fwd);
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 MALLOC_UNLOCK;
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 return true;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1370 } // Cyg_Mempool_dlmalloc_Implementation::free()
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1371
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1372 //----------------------------------------------------------------------------
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 // 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	1375 // 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	1376 // 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	1377 // 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	1378 // 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	1379 // 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	1380 // 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	1381 // 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	1382 // 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	1383 // 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	1384
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 // DOCUMENTATION FROM ORIGINAL FILE:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1387 // (some now irrelevant parts elided)
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 Realloc algorithm:
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 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	1392 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	1393 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	1394 extended. All are tried:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1395
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1396 * 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	1397 * Shifting backwards, joining preceding adjacent space
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1398 * Both shifting backwards and extending forward.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1399
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1400 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	1401 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	1402 off and freed.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1403
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1404 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	1405 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	1406 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	1407 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	1408 usages of realloc to be sensible.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1409 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1410
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1411 cyg_uint8 *
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1412 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	1413 cyg_int32 bytes,
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1414 cyg_int32 *poldsize )
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1415 {
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 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	1418
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1419 mchunkptr oldp; /* chunk corresponding to oldmem */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1420 INTERNAL_SIZE_T oldsize; /* its size */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1421
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1422 mchunkptr newp; /* chunk to return */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1423 INTERNAL_SIZE_T newsize; /* its size */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1424 cyg_uint8* newmem; /* corresponding user mem */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1425
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1426 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	1427 INTERNAL_SIZE_T nextsize; /* its size */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1428
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1429 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	1430 INTERNAL_SIZE_T prevsize; /* its size */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1431
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1432 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	1433 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	1434
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1435 mchunkptr bck; /* misc temp for linking */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1436 mchunkptr fwd; /* misc temp for linking */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1437
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1438 MALLOC_LOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1439
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1440 newp = oldp = mem2chunk(oldmem);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1441 newsize = oldsize = chunksize(oldp);
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 if (NULL != poldsize)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1444 *poldsize = oldsize - SIZE_SZ;
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 nb = request2size(bytes);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1447
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1448 check_inuse_chunk(oldp);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1449
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1450 if ((long)(oldsize) < (long)(nb))
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1453 /* Try expanding forward */
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 next = chunk_at_offset(oldp, oldsize);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1456 if (next == top \|\| !inuse(next))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1457 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1458 nextsize = chunksize(next);
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 /* 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	1461 if (next == top)
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 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	1464 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1465 newsize += nextsize;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1466 top = chunk_at_offset(oldp, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1467 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	1468 set_head_size(oldp, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1469 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1470 return chunk2mem(oldp);
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 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1473
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1474 /* Forward into next chunk */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1475 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	1476 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1477 unlink(next, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1478 newsize += nextsize;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1479 goto split;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1480 }
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 else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1483 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1484 next = 0;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1485 nextsize = 0;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1486 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1487
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1488 /* Try shifting backwards. */
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 if (!prev_inuse(oldp))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1491 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1492 prev = prev_chunk(oldp);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1493 prevsize = chunksize(prev);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1494
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1495 /* 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	1496
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1497 if (next != 0)
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 /* into top */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1500 if (next == top)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1501 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1502 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	1503 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1504 unlink(prev, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1505 newp = prev;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1506 newsize += prevsize + nextsize;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1507 newmem = chunk2mem(newp);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1508 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	1509 top = chunk_at_offset(newp, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1510 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	1511 set_head_size(newp, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1512 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1513 return newmem;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1514 }
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1517 /* into next chunk */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1518 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	1519 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1520 unlink(next, bck, fwd);
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 += nextsize + prevsize;
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 goto split;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1527 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1528 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1529
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1530 /* backward only */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1531 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	1532 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1533 unlink(prev, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1534 newp = prev;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1535 newsize += prevsize;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1536 newmem = chunk2mem(newp);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1537 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	1538 goto split;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1539 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1540 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1541
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1542 // 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	1543 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1544 return NULL;
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1548 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	1549
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1550 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	1551
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1552 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	1553 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1554 remainder = chunk_at_offset(newp, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1555 set_head_size(newp, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1556 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	1557 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	1558 /* let free() deal with it */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1559 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	1560 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1561 else
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 set_head_size(newp, newsize);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1564 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	1565 }
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 check_inuse_chunk(newp);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1568 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1569 return chunk2mem(newp);
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 } // Cyg_Mempool_dlmalloc_Implementation::resize_alloc()
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1572
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1573 //----------------------------------------------------------------------------
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1574
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1575 // Get memory pool status
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1576 // 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	1577 // defined in common.hxx
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1578 void
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1579 Cyg_Mempool_dlmalloc_Implementation::get_status(
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1580 cyg_mempool_status_flag_t flags,
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1581 Cyg_Mempool_Status &status )
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 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	1584 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	1585 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1586 int i;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1587 mbinptr b;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1588 mchunkptr p;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1589 cyg_int32 chunksizep;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1590 cyg_int32 maxfree;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1591 #ifdef CYGDBG_MEMALLOC_ALLOCATOR_DLMALLOC_DEBUG
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1592 mchunkptr q;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1593 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1594
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1595 INTERNAL_SIZE_T avail = chunksize(top);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1596 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	1597 maxfree = avail;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1598
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1599 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	1600 b = bin_at(i);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1601 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	1602 #ifdef CYGDBG_MEMALLOC_ALLOCATOR_DLMALLOC_DEBUG
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1603 check_free_chunk(p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1604 for (q = next_chunk(p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1605 (q < top) && inuse(q) &&
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1606 (long)(chunksize(q)) >= (long)MINSIZE;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1607 q = next_chunk(q))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1608 check_inuse_chunk(q);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1609 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1610 chunksizep = chunksize(p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1611 avail += chunksizep;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1612 if ( chunksizep > maxfree )
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1613 maxfree = chunksizep;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1614 navail++;
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 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1617
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1618 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	1619 status.totalallocated = arenasize - avail;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1620 // 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	1621 // test flag first
163 0d2b193a635f Merge from eCos master repository on 2001-06-22-17:38:39-BST jlarmour parents: 159 diff changeset	1622 status.totalfree = avail - (2*SIZE_SZ) - MINSIZE;
115 6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1623 status.freeblocks = navail;
163 0d2b193a635f Merge from eCos master repository on 2001-06-22-17:38:39-BST jlarmour parents: 159 diff changeset	1624 status.maxfree = maxfree - (2*SIZE_SZ) - MINSIZE;
115 6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1625 } // if
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1626
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1627 // 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	1628 // test flag first
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1629 status.arenabase = status.origbase = arenabase;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1630 status.arenasize = status.origsize = arenasize;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1631 status.maxoverhead = MINSIZE + MALLOC_ALIGNMENT;
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 } // Cyg_Mempool_dlmalloc_Implementation::get_status()
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1636 //----------------------------------------------------------------------------
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1637
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1638 // EOF dlmalloc.cxx

Mercurial > ecos

annotate packages/services/memalloc/common/current/src/dlmalloc.cxx @ 163:0d2b193a635f