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

annotate packages/services/memalloc/common/current/src/dlmalloc.cxx @ 171:42f843b391aa

Merge from eCos master repository on 2001-07-18-03:13:25-BST

author	jlarmour
date	Wed, 18 Jul 2001 11:38:39 +0000
parents	0d2b193a635f
children	e0c0827131d1

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>
171 42f843b391aa Merge from eCos master repository on 2001-07-18-03:13:25-BST jlarmour parents: 163 diff changeset	209 //#include <cyg/infra/diag.h>
115 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 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	212 Debugging:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	213
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	214 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	215 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	216 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	217 in helping track down dangling pointers.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	218
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	219 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	220 number of assertion checks are
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	221 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	222 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	223 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	224 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	225 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	226 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	227 course of computing the summmaries.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	228
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	229 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	230 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	231 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	232 the algorithms.
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	236 #ifdef CYGDBG_MEMALLOC_ALLOCATOR_DLMALLOC_DEBUG
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	237 # define ASSERT(x) CYG_ASSERTC( x )
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	238 #else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	239 # define ASSERT(x) ((void)0)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	240 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	241
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	242
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	243 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	244 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	245 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	246 called recursively.
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	249 #ifndef MALLOC_LOCK
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	250 #define MALLOC_LOCK
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	251 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	252
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	253 #ifndef MALLOC_UNLOCK
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	254 #define MALLOC_UNLOCK
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	255 #endif
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 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	258 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	259 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	260 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	261 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	262 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	263 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	264 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	265
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	266 #ifndef INTERNAL_SIZE_T
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	267 #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	268 #endif
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 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	271 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	272 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	273 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	274 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	275 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	276 (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	277 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	278 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	279 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	280
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	281 #ifdef SIZE_T_SMALLER_THAN_LONG
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	282 #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	283 #else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	284 #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	285 #endif
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	288 #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	289
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	290 #include <string.h> // memcpy, memset
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	291
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	292 /* 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	293 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	294 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	295
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	296 #define MALLOC_ZERO(charp, nbytes) \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	297 do { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	298 INTERNAL_SIZE_T mzsz = (nbytes); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	299 if(mzsz <= 9*sizeof(mzsz)) { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	300 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	301 if(mzsz >= 5sizeof(mzsz)) { mz++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	302 *mz++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	303 if(mzsz >= 7sizeof(mzsz)) { mz++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	304 *mz++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	305 if(mzsz >= 9sizeof(mzsz)) { 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 *mz = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	310 } else memset((charp), 0, mzsz); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	311 } while(0)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	312
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	313 #define MALLOC_COPY(dest,src,nbytes) \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	314 do { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	315 INTERNAL_SIZE_T mcsz = (nbytes); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	316 if(mcsz <= 9*sizeof(mcsz)) { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	317 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	318 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	319 if(mcsz >= 5sizeof(mcsz)) { mcdst++ = *mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	320 mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	321 if(mcsz >= 7sizeof(mcsz)) { mcdst++ = *mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	322 mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	323 if(mcsz >= 9sizeof(mcsz)) { 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 mcdst = mcsrc ; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	328 } else memcpy(dest, src, mcsz); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	329 } while(0)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	330
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	331 #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	332
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	333 /* 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	334
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	335 #define MALLOC_ZERO(charp, nbytes) \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	336 do { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	337 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	338 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	339 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	340 switch (mctmp) { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	341 case 0: for(;;) { *mzp++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	342 case 7: *mzp++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	343 case 6: *mzp++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	344 case 5: *mzp++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	345 case 4: *mzp++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	346 case 3: *mzp++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	347 case 2: *mzp++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	348 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	349 } \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	350 } while(0)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	351
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	352 #define MALLOC_COPY(dest,src,nbytes) \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	353 do { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	354 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	355 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	356 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	357 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	358 switch (mctmp) { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	359 case 0: for(;;) { mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	360 case 7: mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	361 case 6: mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	362 case 5: mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	363 case 4: mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	364 case 3: mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	365 case 2: mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	366 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	367 } \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	368 } while(0)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	369
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	370 #endif
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 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	376 malloc_chunk details:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	377
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	378 (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	379
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	380 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	381 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	382 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	383 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	384 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	385 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	386 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	387 in use.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	388
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	389 An allocated chunk looks like this:
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	392 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	393 \| Size of previous chunk, if allocated \| \|
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	394 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	395 \| Size of chunk, in bytes \|P\|
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	396 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	397 \| User data starts here... .
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	398 . .
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	399 . (malloc_usable_space() bytes) .
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	400 . \|
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	401 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	402 \| Size of chunk \|
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	406 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	407 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	408 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	409
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	410 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	411 (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	412 thus double-word aligned.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	413
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	414 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	415
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	416 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	417 \| Size of previous chunk \|
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	418 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	419 `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	420 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	421 \| 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	422 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	423 \| 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	424 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	425 \| 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	426 . .
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	427 . \|
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	428 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	429 `foot:' \| Size of chunk, in bytes \|
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	432 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	433 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	434 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	435 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	436 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	437 (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	438 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	439
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	440 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	441 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	442 deal with alignments etc).
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	443
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	444 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	445 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	446 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	447 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	448
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	449 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	450
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	451 * `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	452 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	453 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	454 (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	455 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	456 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	457 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	458 approximately least recently used chunk.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	459
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	460 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	461 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	462 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	463 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	464 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	465 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	466 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	467 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	468 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	469 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	470 chunks and less fragmentation.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	471
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	472 * `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	473 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	474 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	475 available.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	476
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	477 * `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	478 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	479 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	480 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	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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	484 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	485
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	486 /* sizes, alignments */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	487
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	488 #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	489 #ifndef MALLOC_ALIGNMENT
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	490 #define MALLOC_ALIGN 8
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	491 #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	492 #else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	493 #define MALLOC_ALIGN MALLOC_ALIGNMENT
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	494 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	495 #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	496 #define MINSIZE \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	497 (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	498
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	499 /* 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	500
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	501 #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	502 #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	503
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	504 /* 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	505
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	506 #define request2size(req) \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	507 (((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	508 (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	509 (((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	510
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	511 /* Check if m has acceptable alignment */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	512
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	513 #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	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 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	517 Physical chunk operations
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	521 /* 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	522
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	523 #define PREV_INUSE 0x1
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	524
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	525 /* 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	526
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	527 #define SIZE_BITS (PREV_INUSE)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	528
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	529
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	530 /* Ptr to next physical malloc_chunk. */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	531
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	532 #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	533
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	534 /* Ptr to previous physical malloc_chunk */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	535
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	536 #define prev_chunk(p)\
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	537 ((mchunkptr)( ((char*)(p)) - ((p)->prev_size) ))
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	540 /* 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	541
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	542 #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	543
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	544 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	545 Dealing with use bits
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	548 /* extract p's inuse bit */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	549
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	550 #define inuse(p)\
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	551 ((((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	552
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	553 /* extract inuse bit of previous chunk */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	554
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	555 #define 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	556
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	557 /* 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	558
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	559 #define set_inuse(p)\
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	560 ((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	561
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	562 #define clear_inuse(p)\
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	563 ((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	564
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	565 /* 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	566
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	567 #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	568 (((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	569
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	570 #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	571 (((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	572
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	573 #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	574 (((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	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 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	578 Dealing with size fields
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	581 /* Get size, ignoring use bits */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	582
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	583 #define chunksize(p) ((p)->size & ~(SIZE_BITS))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	584
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	585 /* 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	586
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	587 #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	588
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	589 /* 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	590
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	591 #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	592
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	593 /* 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	594
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	595 #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	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 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	601 Bins
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	602
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	603 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	604 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	605 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	606 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	607 and chunks are the same).
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	608
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	609 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	610 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	611 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	612 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	613
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	614 Bin layout:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	615
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	616 64 bins of size 8
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	617 32 bins of size 64
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	618 16 bins of size 512
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	619 8 bins of size 4096
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	620 4 bins of size 32768
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	621 2 bins of size 262144
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	622 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	623
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	624 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	625 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	626
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	627 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	628 (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	629 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	630 always handled specially.
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	634 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	635
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	636 /* access macros */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	637
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	638 #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	639 #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	640 #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	641
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	642 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	643 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	644 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	645 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	646 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	647
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	648 #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	649 #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	650
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	651
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	652 /* Helper macro to initialize bins */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	653
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	654 #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	655
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	656 #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	657 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	658 0, 0,
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	659 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	660 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	661 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	662 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	663 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	664 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	665 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	666 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	667 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	668 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	669 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	670 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	671 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	672 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	673 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	674 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	675 };
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	676 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	677
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	678 /* field-extraction macros */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	679
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	680 #define first(b) ((b)->fd)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	681 #define last(b) ((b)->bk)
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 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	684 Indexing into bins
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	687 #define bin_index(sz) \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	688 (((((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	689 ((((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	690 ((((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	691 ((((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	692 ((((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	693 ((((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	694 126)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	695 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	696 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	697 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	698 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	699
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	700 #define MAX_SMALLBIN_SIZE 512
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	701 #define SMALLBIN_WIDTH 8
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	702 #define SMALLBIN_WIDTH_BITS 3
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	703 #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	704
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	705 #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	706
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	707 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	708 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	709 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	710
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	711 #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	712
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	713 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	714 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	715 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	716 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	717 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	718 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	719 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	720 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	721 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	722
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	723 #define BINBLOCKWIDTH 4 /* bins per block */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	724
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	725 #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	726
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	727 /* bin<->block macros */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	728
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	729 #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	730 #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	731 #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	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 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	737 Debugging support
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	740 #ifdef CYGDBG_MEMALLOC_ALLOCATOR_DLMALLOC_DEBUG
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 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	743 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	744 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	745 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	746 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	747 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	748 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	749
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	750 void
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	751 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	752 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	753 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	754
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	755 /* Check for legal address ... */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	756 ASSERT((cyg_uint8 *)p >= arenabase);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	757 if (p != top)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	758 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	759 else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	760 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	761
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	762 } // 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	763
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	764
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	765 void
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	766 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	767 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	768 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	769 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	770
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	771 do_check_chunk(p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	772
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	773 /* 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	774 ASSERT(!inuse(p));
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	775
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	776 /* 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	777 if ((long)sz >= (long)MINSIZE)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	778 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	779 ASSERT((sz & MALLOC_ALIGN_MASK) == 0);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	780 ASSERT(aligned_OK(chunk2mem(p)));
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	781 /* ... matching footer field */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	782 ASSERT(next->prev_size == sz);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	783 /* ... and is fully consolidated */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	784 ASSERT(prev_inuse(p));
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	785 ASSERT (next == top \|\| inuse(next));
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	786
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	787 /* ... and has minimally sane links */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	788 ASSERT(p->fd->bk == p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	789 ASSERT(p->bk->fd == p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	790 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	791 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	792 ASSERT(sz == SIZE_SZ);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	793 } // 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	794
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	795 void
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	796 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	797 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	798 mchunkptr next = next_chunk(p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	799 do_check_chunk(p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	800
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	801 /* 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	802 ASSERT(inuse(p));
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	803
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	804 /* ... and is surrounded by OK chunks.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	805 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	806 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	807 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	808 if (!prev_inuse(p))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	809 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	810 mchunkptr prv = prev_chunk(p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	811 ASSERT(next_chunk(prv) == p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	812 do_check_free_chunk(prv);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	813 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	814 if (next == top)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	815 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	816 ASSERT(prev_inuse(next));
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	817 ASSERT(chunksize(next) >= MINSIZE);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	818 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	819 else if (!inuse(next))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	820 do_check_free_chunk(next);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	821
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	822 } // 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	823
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	824 void
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	825 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	826 INTERNAL_SIZE_T s)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	827 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	828 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	829 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	830
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	831 do_check_inuse_chunk(p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	832
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	833 /* Legal size ... */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	834 ASSERT((long)sz >= (long)MINSIZE);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	835 ASSERT((sz & MALLOC_ALIGN_MASK) == 0);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	836 ASSERT(room >= 0);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	837 ASSERT(room < (long)MINSIZE);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	838
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	839 /* ... and alignment */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	840 ASSERT(aligned_OK(chunk2mem(p)));
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	843 /* ... 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	844 ASSERT(prev_inuse(p));
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	845
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	846 } // 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	847
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	848
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	849 #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	850 #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	851 #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	852 #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	853 #else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	854 #define check_free_chunk(P)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	855 #define check_inuse_chunk(P)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	856 #define check_chunk(P)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	857 #define check_malloced_chunk(P,N)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	858 #endif
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 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	864 Macro-based internal utilities
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 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	869 Linking chunks in bin lists.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	870 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	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 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	874 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	875 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	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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	879 #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	880 { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	881 if (S < MAX_SMALLBIN_SIZE) \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	882 { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	883 IDX = smallbin_index(S); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	884 mark_binblock(IDX); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	885 BK = bin_at(IDX); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	886 FD = BK->fd; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	887 P->bk = BK; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	888 P->fd = FD; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	889 FD->bk = BK->fd = P; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	890 } \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	891 else \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	892 { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	893 IDX = bin_index(S); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	894 BK = bin_at(IDX); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	895 FD = BK->fd; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	896 if (FD == BK) mark_binblock(IDX); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	897 else \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	898 { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	899 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	900 BK = FD->bk; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	901 } \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	902 P->bk = BK; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	903 P->fd = FD; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	904 FD->bk = BK->fd = P; \
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	909 /* take a chunk off a list */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	910
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	911 #define unlink(P, BK, FD) \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	912 { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	913 BK = P->bk; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	914 FD = P->fd; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	915 FD->bk = BK; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	916 BK->fd = FD; \
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	919 /* Place p as the last remainder */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	920
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	921 #define link_last_remainder(P) \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	922 { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	923 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	924 P->fd = P->bk = last_remainder; \
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	927 /* Clear the last_remainder bin */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	928
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	929 #define clear_last_remainder \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	930 (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	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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	935 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	936 cyg_uint8 *base, cyg_int32 size,
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	937 CYG_ADDRWORD /* argthru */ )
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	938 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	939 arenabase = base;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	940 arenasize = size;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	941
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	942 CYG_ADDRESS front_misalign;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	943 cyg_int32 correction;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	944
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	945 #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	946 cyg_ucount16 i;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	947 av_[0] = av_[1] = 0;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	948 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	949 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	950 } // for
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	951
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	952 #elif defined(CYGDBG_USE_ASSERTS)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	953 static int instances;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	954 if ( ++instances > 1 )
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	955 CYG_FAIL( "Multiple dlmalloc instances but "
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	956 "CYGIMP_MEMALLOC_ALLOCATOR_DLMALLOC_SAFE_MULTIPLE "
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	957 "not defined" );
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	958 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	959
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	960 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	961
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	962 if ( front_misalign > 0 ) {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	963 correction = (MALLOC_ALIGNMENT) - front_misalign;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	964 } else {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	965 correction = 0;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	966 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	967
159 511f4dc167f6 Merge from eCos master repository on 2001-05-18-01:30:05-BST jlarmour parents: 115 diff changeset	968 // too small to be useful?
511f4dc167f6 Merge from eCos master repository on 2001-05-18-01:30:05-BST jlarmour parents: 115 diff changeset	969 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	970 // 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	971 arenabase = NULL;
511f4dc167f6 Merge from eCos master repository on 2001-05-18-01:30:05-BST jlarmour parents: 115 diff changeset	972 else {
511f4dc167f6 Merge from eCos master repository on 2001-05-18-01:30:05-BST jlarmour parents: 115 diff changeset	973 top = (mchunkptr)(base + correction);
511f4dc167f6 Merge from eCos master repository on 2001-05-18-01:30:05-BST jlarmour parents: 115 diff changeset	974 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	975 }
115 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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	980 /* Main public routines */
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 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	983 Malloc Algorithm:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	984
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	985 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	986 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	987 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	988 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	989 (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	990
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	991 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	992
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	993 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	994 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	995
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	996 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	997 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	998 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	999 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	1000 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	1001 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	1002 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	1003 fragmentation in the long run.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1004
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1005 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	1006 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	1007 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	1008 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	1009 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	1010
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1011 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	1012 (`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	1013 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	1014 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	1015 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	1016 (up to system limitations).
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1017
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1018 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	1019 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	1020 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	1021 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	1022 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	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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1026 cyg_uint8 *
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1027 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	1028 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1029 mchunkptr victim; /* inspected/selected chunk */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1030 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	1031 int idx; /* index for bin traversal */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1032 mbinptr bin; /* associated bin */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1033 mchunkptr remainder; /* remainder from a split */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1034 long remainder_size; /* its size */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1035 int remainder_index; /* its bin index */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1036 unsigned long block; /* block traverser bit */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1037 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	1038 mchunkptr fwd; /* misc temp for linking */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1039 mchunkptr bck; /* misc temp for linking */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1040 mbinptr q; /* misc temp */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1041
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1042 INTERNAL_SIZE_T nb;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1043
159 511f4dc167f6 Merge from eCos master repository on 2001-05-18-01:30:05-BST jlarmour parents: 115 diff changeset	1044 /* 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	1045 * 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	1046 * memory. */
511f4dc167f6 Merge from eCos master repository on 2001-05-18-01:30:05-BST jlarmour parents: 115 diff changeset	1047 if (NULL==arenabase) return NULL;
511f4dc167f6 Merge from eCos master repository on 2001-05-18-01:30:05-BST jlarmour parents: 115 diff changeset	1048
115 6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1049 if ((long)bytes < 0) return 0;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1050
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1051 nb = request2size(bytes); /* padded request size; */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1052
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1053 MALLOC_LOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1054
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1055 /* 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	1056
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1057 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	1058 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1059 idx = smallbin_index(nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1060
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1061 /* 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	1062
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1063 q = bin_at(idx);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1064 victim = last(q);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1065
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1066 #if MALLOC_ALIGN != 16
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1067 /* 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	1068 if (victim == q)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1069 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1070 q = next_bin(q);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1071 victim = last(q);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1072 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1073 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1074 if (victim != q)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1075 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1076 victim_size = chunksize(victim);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1077 unlink(victim, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1078 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	1079 check_malloced_chunk(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1080 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1081 return chunk2mem(victim);
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1084 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	1085
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1086 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1087 else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1088 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1089 idx = bin_index(nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1090 bin = bin_at(idx);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1091
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1092 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	1093 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1094 victim_size = chunksize(victim);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1095 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	1096
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1097 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	1098 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1099 --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	1100 break;
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1103 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	1104 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1105 unlink(victim, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1106 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	1107 check_malloced_chunk(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1108 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1109 return chunk2mem(victim);
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1113 ++idx;
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1117 /* 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	1118
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1119 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	1120 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1121 victim_size = chunksize(victim);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1122 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	1123
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1124 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	1125 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1126 remainder = chunk_at_offset(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1127 set_head(victim, nb \| PREV_INUSE);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1128 link_last_remainder(remainder);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1129 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	1130 set_foot(remainder, remainder_size);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1131 check_malloced_chunk(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1132 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1133 return chunk2mem(victim);
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1136 clear_last_remainder;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1137
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1138 if (remainder_size >= 0) /* exhaust */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1139 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1140 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	1141 check_malloced_chunk(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1142 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1143 return chunk2mem(victim);
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1146 /* Else place in bin */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1147
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1148 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	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 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1152 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	1153 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	1154 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1155
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1156 if ( (block = idx2binblock(idx)) <= binblocks)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1157 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1158
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1159 /* Get to the first marked block */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1160
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1161 if ( (block & binblocks) == 0)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1162 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1163 /* force to an even block boundary */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1164 idx = (idx & ~(BINBLOCKWIDTH - 1)) + BINBLOCKWIDTH;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1165 block <<= 1;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1166 while ((block & binblocks) == 0)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1167 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1168 idx += BINBLOCKWIDTH;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1169 block <<= 1;
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1173 /* For each possibly nonempty block ... */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1174 for (;;)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1175 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1176 startidx = idx; /* (track incomplete blocks) */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1177 q = bin = bin_at(idx);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1178
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1179 /* For each bin in this block ... */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1180 do
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1181 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1182 /* 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	1183
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1184 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	1185 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1186 victim_size = chunksize(victim);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1187 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	1188
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1189 if (remainder_size >= (long)MINSIZE) /* split */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1190 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1191 remainder = chunk_at_offset(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1192 set_head(victim, nb \| PREV_INUSE);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1193 unlink(victim, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1194 link_last_remainder(remainder);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1195 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	1196 set_foot(remainder, remainder_size);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1197 check_malloced_chunk(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1198 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1199 return chunk2mem(victim);
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1202 else if (remainder_size >= 0) /* take */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1203 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1204 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	1205 unlink(victim, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1206 check_malloced_chunk(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1207 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1208 return chunk2mem(victim);
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1213 bin = next_bin(bin);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1214
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1215 #if MALLOC_ALIGN == 16
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1216 if (idx < MAX_SMALLBIN)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1217 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1218 bin = next_bin(bin);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1219 ++idx;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1220 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1221 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1222 } while ((++idx & (BINBLOCKWIDTH - 1)) != 0);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1223
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1224 /* Clear out the block bit. */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1225
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1226 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	1227 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1228 if ((startidx & (BINBLOCKWIDTH - 1)) == 0)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1229 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1230 binblocks &= ~block;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1231 break;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1232 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1233 --startidx;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1234 q = prev_bin(q);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1235 } while (first(q) == q);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1236
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1237 /* 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	1238
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1239 if ( (block <<= 1) <= binblocks && (block != 0) )
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1240 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1241 while ((block & binblocks) == 0)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1242 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1243 idx += BINBLOCKWIDTH;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1244 block <<= 1;
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 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1247 else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1248 break;
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1253 /* Try to use top chunk */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1254
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1255 /* 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	1256 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	1257 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	1258 {
171 42f843b391aa Merge from eCos master repository on 2001-07-18-03:13:25-BST jlarmour parents: 163 diff changeset	1259 //diag_printf("chunksize(top)=%ld, nb=%d, remainder=%ld\n", chunksize(top),
42f843b391aa Merge from eCos master repository on 2001-07-18-03:13:25-BST jlarmour parents: 163 diff changeset	1260 // nb, remainder_size);
115 6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1261 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1262 return NULL; /* propagate failure */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1263 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1264
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1265 victim = top;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1266 set_head(victim, nb \| PREV_INUSE);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1267 top = chunk_at_offset(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1268 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	1269 check_malloced_chunk(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1270 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1271 return chunk2mem(victim);
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 } // Cyg_Mempool_dlmalloc_Implementation::try_alloc()
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 //----------------------------------------------------------------------------
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 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1278 free() algorithm :
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1279
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1280 cases:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1281
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1282 1. free(NULL) has no effect.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1283
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1284 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	1285 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	1286 consolidating with the current `last_remainder').
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1287 */
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 cyg_bool
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1290 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	1291 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1292 mchunkptr p; /* chunk corresponding to mem */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1293 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	1294 INTERNAL_SIZE_T sz; /* its size */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1295 int idx; /* its bin index */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1296 mchunkptr next; /* next contiguous chunk */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1297 INTERNAL_SIZE_T nextsz; /* its size */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1298 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	1299 mchunkptr bck; /* misc temp for linking */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1300 mchunkptr fwd; /* misc temp for linking */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1301 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	1302
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1303 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	1304 return false;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1305
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1306 MALLOC_LOCK;
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 p = mem2chunk(mem);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1309 hd = p->size;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1310
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1311 check_inuse_chunk(p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1312
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1313 sz = hd & ~PREV_INUSE;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1314 next = chunk_at_offset(p, sz);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1315 nextsz = chunksize(next);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1316
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1317 if (next == top) /* merge with top */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1318 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1319 sz += nextsz;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1320
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1321 if (!(hd & PREV_INUSE)) /* consolidate backward */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1322 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1323 prevsz = p->prev_size;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1324 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	1325 sz += prevsz;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1326 unlink(p, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1327 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1328
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1329 set_head(p, sz \| PREV_INUSE);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1330 top = p;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1331 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1332 return true;
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1335 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	1336
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1337 islr = 0;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1338
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1339 if (!(hd & PREV_INUSE)) /* consolidate backward */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1340 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1341 prevsz = p->prev_size;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1342 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	1343 sz += prevsz;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1344
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1345 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	1346 islr = 1;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1347 else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1348 unlink(p, bck, fwd);
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1351 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	1352 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1353 sz += nextsz;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1354
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1355 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	1356 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1357 islr = 1;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1358 link_last_remainder(p);
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 else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1361 unlink(next, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1362 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1363
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1364
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1365 set_head(p, sz \| PREV_INUSE);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1366 set_foot(p, sz);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1367 if (!islr)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1368 frontlink(p, sz, idx, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1369
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1370 MALLOC_UNLOCK;
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 return true;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1373 } // Cyg_Mempool_dlmalloc_Implementation::free()
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1374
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1375 //----------------------------------------------------------------------------
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1376
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1377 // 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	1378 // 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	1379 // 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	1380 // 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	1381 // 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	1382 // 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	1383 // 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	1384 // 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	1385 // 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	1386 // 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	1387
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 // DOCUMENTATION FROM ORIGINAL FILE:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1390 // (some now irrelevant parts elided)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1391 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1392 Realloc algorithm:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1393
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1394 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	1395 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	1396 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	1397 extended. All are tried:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1398
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1399 * 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	1400 * Shifting backwards, joining preceding adjacent space
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1401 * Both shifting backwards and extending forward.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1402
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1403 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	1404 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	1405 off and freed.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1406
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1407 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	1408 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	1409 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	1410 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	1411 usages of realloc to be sensible.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1412 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1413
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1414 cyg_uint8 *
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1415 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	1416 cyg_int32 bytes,
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1417 cyg_int32 *poldsize )
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1420 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	1421
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1422 mchunkptr oldp; /* chunk corresponding to oldmem */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1423 INTERNAL_SIZE_T oldsize; /* its size */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1424
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1425 mchunkptr newp; /* chunk to return */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1426 INTERNAL_SIZE_T newsize; /* its size */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1427 cyg_uint8* newmem; /* corresponding user mem */
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 next; /* next contiguous chunk after oldp */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1430 INTERNAL_SIZE_T nextsize; /* 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 prev; /* previous contiguous chunk before oldp */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1433 INTERNAL_SIZE_T prevsize; /* 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 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	1436 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	1437
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1438 mchunkptr bck; /* misc temp for linking */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1439 mchunkptr fwd; /* misc temp for linking */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1440
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1441 MALLOC_LOCK;
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 newp = oldp = mem2chunk(oldmem);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1444 newsize = oldsize = chunksize(oldp);
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 if (NULL != poldsize)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1447 *poldsize = oldsize - SIZE_SZ;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1448
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1449 nb = request2size(bytes);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1450
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1451 check_inuse_chunk(oldp);
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 if ((long)(oldsize) < (long)(nb))
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1456 /* Try expanding forward */
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 next = chunk_at_offset(oldp, oldsize);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1459 if (next == top \|\| !inuse(next))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1460 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1461 nextsize = chunksize(next);
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 /* 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	1464 if (next == top)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1465 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1466 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	1467 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1468 newsize += nextsize;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1469 top = chunk_at_offset(oldp, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1470 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	1471 set_head_size(oldp, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1472 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1473 return chunk2mem(oldp);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1474 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1475 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1476
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1477 /* Forward into next chunk */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1478 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	1479 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1480 unlink(next, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1481 newsize += nextsize;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1482 goto split;
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 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1485 else
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 next = 0;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1488 nextsize = 0;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1489 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1490
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1491 /* Try shifting backwards. */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1492
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1493 if (!prev_inuse(oldp))
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 prev = prev_chunk(oldp);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1496 prevsize = chunksize(prev);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1497
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1498 /* 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	1499
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1500 if (next != 0)
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 /* into top */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1503 if (next == top)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1504 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1505 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	1506 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1507 unlink(prev, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1508 newp = prev;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1509 newsize += prevsize + nextsize;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1510 newmem = chunk2mem(newp);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1511 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	1512 top = chunk_at_offset(newp, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1513 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	1514 set_head_size(newp, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1515 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1516 return newmem;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1517 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1518 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1519
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1520 /* into next chunk */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1521 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	1522 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1523 unlink(next, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1524 unlink(prev, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1525 newp = prev;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1526 newsize += nextsize + prevsize;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1527 newmem = chunk2mem(newp);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1528 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	1529 goto split;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1530 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1531 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1532
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1533 /* backward only */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1534 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	1535 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1536 unlink(prev, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1537 newp = prev;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1538 newsize += prevsize;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1539 newmem = chunk2mem(newp);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1540 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	1541 goto split;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1542 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1543 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1544
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1545 // 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	1546 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1547 return NULL;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1548 }
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1551 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	1552
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1553 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	1554
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1555 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	1556 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1557 remainder = chunk_at_offset(newp, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1558 set_head_size(newp, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1559 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	1560 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	1561 /* let free() deal with it */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1562 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	1563 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1564 else
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 set_head_size(newp, newsize);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1567 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	1568 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1569
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1570 check_inuse_chunk(newp);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1571 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1572 return chunk2mem(newp);
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 } // Cyg_Mempool_dlmalloc_Implementation::resize_alloc()
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1575
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1576 //----------------------------------------------------------------------------
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1577
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1578 // Get memory pool status
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1579 // 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	1580 // defined in common.hxx
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1581 void
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1582 Cyg_Mempool_dlmalloc_Implementation::get_status(
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1583 cyg_mempool_status_flag_t flags,
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1584 Cyg_Mempool_Status &status )
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 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	1587 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	1588 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1589 int i;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1590 mbinptr b;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1591 mchunkptr p;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1592 cyg_int32 chunksizep;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1593 cyg_int32 maxfree;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1594 #ifdef CYGDBG_MEMALLOC_ALLOCATOR_DLMALLOC_DEBUG
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1595 mchunkptr q;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1596 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1597
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1598 INTERNAL_SIZE_T avail = chunksize(top);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1599 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	1600 maxfree = avail;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1601
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1602 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	1603 b = bin_at(i);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1604 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	1605 #ifdef CYGDBG_MEMALLOC_ALLOCATOR_DLMALLOC_DEBUG
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1606 check_free_chunk(p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1607 for (q = next_chunk(p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1608 (q < top) && inuse(q) &&
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1609 (long)(chunksize(q)) >= (long)MINSIZE;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1610 q = next_chunk(q))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1611 check_inuse_chunk(q);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1612 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1613 chunksizep = chunksize(p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1614 avail += chunksizep;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1615 if ( chunksizep > maxfree )
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1616 maxfree = chunksizep;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1617 navail++;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1618 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1619 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1620
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1621 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	1622 status.totalallocated = arenasize - avail;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1623 // 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	1624 // test flag first
171 42f843b391aa Merge from eCos master repository on 2001-07-18-03:13:25-BST jlarmour parents: 163 diff changeset	1625 status.totalfree = (avail & ~(MALLOC_ALIGN_MASK)) - SIZE_SZ - MINSIZE;
42f843b391aa Merge from eCos master repository on 2001-07-18-03:13:25-BST jlarmour parents: 163 diff changeset	1626 CYG_ASSERT( ((avail + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)
42f843b391aa Merge from eCos master repository on 2001-07-18-03:13:25-BST jlarmour parents: 163 diff changeset	1627 >= MINSIZE, "free mem negative!" );
115 6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1628 status.freeblocks = navail;
171 42f843b391aa Merge from eCos master repository on 2001-07-18-03:13:25-BST jlarmour parents: 163 diff changeset	1629 status.maxfree = (maxfree & ~(MALLOC_ALIGN_MASK)) - SIZE_SZ - MINSIZE;
42f843b391aa Merge from eCos master repository on 2001-07-18-03:13:25-BST jlarmour parents: 163 diff changeset	1630 //diag_printf("raw mf: %d, ret mf: %d\n", maxfree, status.maxfree);
42f843b391aa Merge from eCos master repository on 2001-07-18-03:13:25-BST jlarmour parents: 163 diff changeset	1631 CYG_ASSERT( ((maxfree + SIZE_SZ + MALLOC_ALIGN_MASK) &
42f843b391aa Merge from eCos master repository on 2001-07-18-03:13:25-BST jlarmour parents: 163 diff changeset	1632 ~MALLOC_ALIGN_MASK) >= MINSIZE,
42f843b391aa Merge from eCos master repository on 2001-07-18-03:13:25-BST jlarmour parents: 163 diff changeset	1633 "max free block size negative!" );
115 6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1634 } // if
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 // 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	1637 // test flag first
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1638 status.arenabase = status.origbase = arenabase;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1639 status.arenasize = status.origsize = arenasize;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1640 status.maxoverhead = MINSIZE + MALLOC_ALIGNMENT;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1641
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1642 } // Cyg_Mempool_dlmalloc_Implementation::get_status()
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1643
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1644
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1645 //----------------------------------------------------------------------------
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1646
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1647 // EOF dlmalloc.cxx

Mercurial > ecos

annotate packages/services/memalloc/common/current/src/dlmalloc.cxx @ 171:42f843b391aa