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

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

Merge from eCos master repository on 2002-05-20-20:11:54-BST

author	jlarmour
date	Mon, 20 May 2002 22:19:26 +0000
parents	42f843b391aa
children	d2c90368aeef

rev	line source
115 6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1 //==========================================================================
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	2 //
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	3 // dlmalloc.cxx
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	4 //
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	5 // Port of Doug Lea's malloc implementation
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	6 //
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	7 //==========================================================================
208 e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	8 //####ECOSGPLCOPYRIGHTBEGIN####
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	9 // -------------------------------------------
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	10 // This file is part of eCos, the Embedded Configurable Operating System.
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	11 // Copyright (C) 1998, 1999, 2000, 2001, 2002 Red Hat, Inc.
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	12 //
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	13 // eCos is free software; you can redistribute it and/or modify it under
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	14 // the terms of the GNU General Public License as published by the Free
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	15 // Software Foundation; either version 2 or (at your option) any later version.
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	16 //
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	17 // eCos is distributed in the hope that it will be useful, but WITHOUT ANY
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	18 // WARRANTY; without even the implied warranty of MERCHANTABILITY or
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	19 // FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	20 // for more details.
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	21 //
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	22 // You should have received a copy of the GNU General Public License along
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	23 // with eCos; if not, write to the Free Software Foundation, Inc.,
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	24 // 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	25 //
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	26 // As a special exception, if other files instantiate templates or use macros
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	27 // or inline functions from this file, or you compile this file and link it
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	28 // with other works to produce a work based on this file, this file does not
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	29 // by itself cause the resulting work to be covered by the GNU General Public
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	30 // License. However the source code for this file must still be made available
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	31 // in accordance with section (3) of the GNU General Public License.
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	32 //
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	33 // This exception does not invalidate any other reasons why a work based on
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	34 // this file might be covered by the GNU General Public License.
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	35 //
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	36 // Alternative licenses for eCos may be arranged by contacting Red Hat, Inc.
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	37 // at http://sources.redhat.com/ecos/ecos-license
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	38 // -------------------------------------------
e0c0827131d1 Merge from eCos master repository on 2002-05-20-20:11:54-BST jlarmour parents: 171 diff changeset	39 //####ECOSGPLCOPYRIGHTEND####
115 6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	40 //==========================================================================
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	41 //#####DESCRIPTIONBEGIN####
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	42 //
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	43 // Author(s): Doug Lea (dl at g.oswego.edu), jlarmour
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	44 // Contributors:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	45 // Date: 2000-06-18
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	46 // Purpose: Doug Lea's malloc implementation
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	47 // Description: Doug Lea's malloc has been ported to eCos. This file
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	48 // provides the implementation in a way acceptable to eCos.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	49 // Substantial amounts of unnecessary bits (to eCos) of the
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	50 // original implementation have been removed to make the
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	51 // code more tractable. Note this may make a number of the
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	52 // comments appear to make little sense, or no longer apply!
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	53 // In particular, mmap support is removed entirely.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	54 // Also the memory is "sbrked" all at once at the
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	55 // beginning, covering the entire memory region given at
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	56 // construction, and there can be no more afterwards.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	57 // Usage: #include <cyg/memalloc/dlmalloc.hxx>
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	58 //
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	59 //
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	60 //####DESCRIPTIONEND####
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	61 //
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	62 //==========================================================================
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	63
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	64 // DOCUMENTATION FROM ORIGINAL FILE:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	65 // (some now irrelevant parts elided)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	66
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	67 //----------------------------------------------------------------------------
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	68
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	69 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	70 A version of malloc/free/realloc written by Doug Lea and released to the
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	71 public domain. Send questions/comments/complaints/performance data
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	72 to dl at cs.oswego.edu
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	73
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	74 * VERSION 2.6.6 Sun Mar 5 19:10:03 2000 Doug Lea (dl at gee)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	75
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	76 Note: There may be an updated version of this malloc obtainable at
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	77 ftp://g.oswego.edu/pub/misc/malloc.c
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	78 Check before installing!
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	79
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	80 * Why use this malloc?
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	81
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	82 This is not the fastest, most space-conserving, most portable, or
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	83 most tunable malloc ever written. However it is among the fastest
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	84 while also being among the most space-conserving, portable and tunable.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	85 Consistent balance across these factors results in a good general-purpose
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	86 allocator. For a high-level description, see
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	87 http://g.oswego.edu/dl/html/malloc.html
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	88
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	89 * Synopsis of public routines
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	90
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	91 (Much fuller descriptions are contained in the program documentation below.)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	92
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	93 [ these have of course been renamed in the eCos port ]a
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	94
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	95 malloc(size_t n);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	96 Return a pointer to a newly allocated chunk of at least n bytes, or null
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	97 if no space is available.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	98 free(Void_t* p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	99 Release the chunk of memory pointed to by p, or no effect if p is null.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	100 realloc(Void_t* p, size_t n);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	101 Return a pointer to a chunk of size n that contains the same data
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	102 as does chunk p up to the minimum of (n, p's size) bytes, or null
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	103 if no space is available. The returned pointer may or may not be
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	104 the same as p. If p is null, equivalent to malloc. realloc of
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	105 zero bytes calls free(p)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	106
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	107 * Vital statistics:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	108
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	109 Alignment: 8-byte
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	110 8 byte alignment is currently hardwired into the design. This
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	111 seems to suffice for all current machines and C compilers.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	112
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	113 Assumed pointer representation: 4 or 8 bytes
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	114 Code for 8-byte pointers is untested by me but has worked
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	115 reliably by Wolfram Gloger, who contributed most of the
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	116 changes supporting this.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	117
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	118 Assumed size_t representation: 4 or 8 bytes
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	119 Note that size_t is allowed to be 4 bytes even if pointers are 8.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	120
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	121 Minimum overhead per allocated chunk: 4 or 8 bytes
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	122 Each malloced chunk has a hidden overhead of 4 bytes holding size
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	123 and status information.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	124
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	125 Minimum allocated size: 4-byte ptrs: 16 bytes (including 4 overhead)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	126 8-byte ptrs: 24/32 bytes (including, 4/8 overhead)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	127
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	128 When a chunk is freed, 12 (for 4byte ptrs) or 20 (for 8 byte
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	129 ptrs but 4 byte size) or 24 (for 8/8) additional bytes are
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	130 needed; 4 (8) for a trailing size field
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	131 and 8 (16) bytes for free list pointers. Thus, the minimum
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	132 allocatable size is 16/24/32 bytes.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	133
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	134 Even a request for zero bytes (i.e., malloc(0)) returns a
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	135 pointer to something of the minimum allocatable size.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	136
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	137 Maximum allocated size: 4-byte size_t: 2^31 - 8 bytes
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	138 8-byte size_t: 2^63 - 16 bytes
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	139
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	140 It is assumed that (possibly signed) size_t bit values suffice to
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	141 represent chunk sizes. `Possibly signed' is due to the fact
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	142 that `size_t' may be defined on a system as either a signed or
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	143 an unsigned type. To be conservative, values that would appear
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	144 as negative numbers are avoided.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	145 Requests for sizes with a negative sign bit when the request
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	146 size is treaded as a long will return null.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	147
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	148 Maximum overhead wastage per allocated chunk: normally 15 bytes
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	149
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	150 Alignnment demands, plus the minimum allocatable size restriction
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	151 make the normal worst-case wastage 15 bytes (i.e., up to 15
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	152 more bytes will be allocated than were requested in malloc), with
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	153 one exception: because requests for zero bytes allocate non-zero space,
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	154 the worst case wastage for a request of zero bytes is 24 bytes.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	155
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	156 * Limitations
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	157
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	158 Here are some features that are NOT currently supported
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	159
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	160 * No user-definable hooks for callbacks and the like.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	161 * No automated mechanism for fully checking that all accesses
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	162 to malloced memory stay within their bounds.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	163 * No support for compaction.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	164
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	165 * Synopsis of compile-time options:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	166
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	167 People have reported using previous versions of this malloc on all
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	168 versions of Unix, sometimes by tweaking some of the defines
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	169 below. It has been tested most extensively on Solaris and
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	170 Linux. It is also reported to work on WIN32 platforms.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	171 People have also reported adapting this malloc for use in
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	172 stand-alone embedded systems.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	173
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	174 The implementation is in straight, hand-tuned ANSI C. Among other
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	175 consequences, it uses a lot of macros. Because of this, to be at
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	176 all usable, this code should be compiled using an optimizing compiler
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	177 (for example gcc -O2) that can simplify expressions and control
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	178 paths.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	179
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	180 CYGDBG_MEMALLOC_ALLOCATOR_DLMALLOC_DEBUG (default: NOT defined)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	181 Define to enable debugging. Adds fairly extensive assertion-based
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	182 checking to help track down memory errors, but noticeably slows down
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	183 execution.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	184 MALLOC_LOCK (default: NOT defined)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	185 MALLOC_UNLOCK (default: NOT defined)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	186 Define these to C expressions which are run to lock and unlock
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	187 the malloc data structures. Calls may be nested; that is,
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	188 MALLOC_LOCK may be called more than once before the corresponding
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	189 MALLOC_UNLOCK calls. MALLOC_LOCK must avoid waiting for a lock
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	190 that it already holds.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	191 MALLOC_ALIGNMENT (default: NOT defined)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	192 Define this to 16 if you need 16 byte alignment instead of 8 byte alignment
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	193 which is the normal default.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	194 SIZE_T_SMALLER_THAN_LONG (default: NOT defined)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	195 Define this when the platform you are compiling has
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	196 sizeof(long) > sizeof(size_t).
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	197 The option causes some extra code to be generated to handle operations
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	198 that use size_t operands and have long results.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	199 INTERNAL_SIZE_T (default: size_t)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	200 Define to a 32-bit type (probably `unsigned int') if you are on a
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	201 64-bit machine, yet do not want or need to allow malloc requests of
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	202 greater than 2^31 to be handled. This saves space, especially for
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	203 very small chunks.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	204
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	205 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	206
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	207 //----------------------------------------------------------------------------
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	208
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	209
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	210 /* Preliminaries */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	211
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	212 #include <pkgconf/memalloc.h> // configuration header
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	213 #include <pkgconf/infra.h> // CYGDBG_USE_ASSERTS
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	214 #include <cyg/infra/cyg_type.h> // types
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	215 #include <cyg/infra/cyg_ass.h> // assertions
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	216 #include <stddef.h> // for size_t
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	217 #include <cyg/memalloc/dlmalloc.hxx>
171 42f843b391aa Merge from eCos master repository on 2001-07-18-03:13:25-BST jlarmour parents: 163 diff changeset	218 //#include <cyg/infra/diag.h>
115 6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	219
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	220 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	221 Debugging:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	222
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	223 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	224 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	225 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	226 in helping track down dangling pointers.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	227
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	228 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	229 number of assertion checks are
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	230 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	231 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	232 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	233 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	234 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	235 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	236 course of computing the summmaries.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	237
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	238 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	239 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	240 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	241 the algorithms.
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	245 #ifdef CYGDBG_MEMALLOC_ALLOCATOR_DLMALLOC_DEBUG
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	246 # define ASSERT(x) CYG_ASSERTC( x )
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	247 #else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	248 # define ASSERT(x) ((void)0)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	249 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	250
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	251
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	252 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	253 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	254 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	255 called recursively.
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 #ifndef MALLOC_LOCK
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	259 #define MALLOC_LOCK
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	260 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	261
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	262 #ifndef MALLOC_UNLOCK
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	263 #define MALLOC_UNLOCK
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	264 #endif
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 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	267 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	268 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	269 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	270 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	271 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	272 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	273 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	274
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	275 #ifndef INTERNAL_SIZE_T
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	276 #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	277 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	278
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	279 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	280 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	281 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	282 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	283 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	284 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	285 (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	286 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	287 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	288 */
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 #ifdef SIZE_T_SMALLER_THAN_LONG
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	291 #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	292 #else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	293 #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	294 #endif
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	297 #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	298
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	299 #include <string.h> // memcpy, memset
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	300
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	301 /* 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	302 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	303 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	304
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	305 #define MALLOC_ZERO(charp, nbytes) \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	306 do { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	307 INTERNAL_SIZE_T mzsz = (nbytes); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	308 if(mzsz <= 9*sizeof(mzsz)) { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	309 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	310 if(mzsz >= 5sizeof(mzsz)) { mz++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	311 *mz++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	312 if(mzsz >= 7sizeof(mzsz)) { mz++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	313 *mz++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	314 if(mzsz >= 9sizeof(mzsz)) { mz++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	315 *mz++ = 0; }}} \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	316 *mz++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	317 *mz++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	318 *mz = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	319 } else memset((charp), 0, mzsz); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	320 } while(0)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	321
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	322 #define MALLOC_COPY(dest,src,nbytes) \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	323 do { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	324 INTERNAL_SIZE_T mcsz = (nbytes); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	325 if(mcsz <= 9*sizeof(mcsz)) { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	326 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	327 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	328 if(mcsz >= 5sizeof(mcsz)) { mcdst++ = *mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	329 mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	330 if(mcsz >= 7sizeof(mcsz)) { mcdst++ = *mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	331 mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	332 if(mcsz >= 9sizeof(mcsz)) { mcdst++ = *mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	333 mcdst++ = mcsrc++; }}} \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	334 mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	335 mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	336 mcdst = mcsrc ; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	337 } else memcpy(dest, src, mcsz); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	338 } while(0)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	339
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	340 #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	341
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	342 /* 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	343
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	344 #define MALLOC_ZERO(charp, nbytes) \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	345 do { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	346 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	347 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	348 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	349 switch (mctmp) { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	350 case 0: for(;;) { *mzp++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	351 case 7: *mzp++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	352 case 6: *mzp++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	353 case 5: *mzp++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	354 case 4: *mzp++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	355 case 3: *mzp++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	356 case 2: *mzp++ = 0; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	357 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	358 } \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	359 } while(0)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	360
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	361 #define MALLOC_COPY(dest,src,nbytes) \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	362 do { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	363 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	364 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	365 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	366 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	367 switch (mctmp) { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	368 case 0: for(;;) { mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	369 case 7: mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	370 case 6: mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	371 case 5: mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	372 case 4: mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	373 case 3: mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	374 case 2: mcdst++ = mcsrc++; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	375 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	376 } \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	377 } while(0)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	378
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	379 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	380
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	381
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	382 //----------------------------------------------------------------------------
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	383
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	384 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	385 malloc_chunk details:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	386
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	387 (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	388
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	389 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	390 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	391 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	392 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	393 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	394 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	395 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	396 in use.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	397
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	398 An allocated chunk looks like this:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	399
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	400
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	401 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	402 \| Size of previous chunk, if allocated \| \|
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 \| Size of chunk, in bytes \|P\|
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	405 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	406 \| User data starts here... .
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	407 . .
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	408 . (malloc_usable_space() bytes) .
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 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	411 \| Size of chunk \|
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	412 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	413
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	414
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	415 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	416 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	417 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	418
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	419 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	420 (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	421 thus double-word aligned.
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 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	424
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	425 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	426 \| Size of previous chunk \|
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 `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	429 mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	430 \| 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	431 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	432 \| 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	433 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	434 \| 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	435 . .
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	436 . \|
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	437 nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	438 `foot:' \| Size of chunk, in bytes \|
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	441 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	442 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	443 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	444 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	445 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	446 (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	447 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	448
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	449 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	450 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	451 deal with alignments etc).
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	452
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	453 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	454 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	455 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	456 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	457
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	458 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	459
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	460 * `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	461 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	462 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	463 (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	464 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	465 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	466 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	467 approximately least recently used chunk.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	468
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	469 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	470 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	471 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	472 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	473 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	474 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	475 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	476 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	477 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	478 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	479 chunks and less fragmentation.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	480
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	481 * `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	482 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	483 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	484 available.
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 * `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	487 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	488 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	489 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	490
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	491 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	492
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	493 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	494
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	495 /* sizes, alignments */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	496
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	497 #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	498 #ifndef MALLOC_ALIGNMENT
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	499 #define MALLOC_ALIGN 8
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	500 #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	501 #else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	502 #define MALLOC_ALIGN MALLOC_ALIGNMENT
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	503 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	504 #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	505 #define MINSIZE \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	506 (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	507
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	508 /* 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	509
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	510 #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	511 #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	512
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	513 /* 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	514
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	515 #define request2size(req) \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	516 (((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	517 (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	518 (((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	519
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	520 /* Check if m has acceptable alignment */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	521
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	522 #define 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	523
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 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	526 Physical chunk operations
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	527 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	528
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	529
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	530 /* 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	531
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	532 #define PREV_INUSE 0x1
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 /* 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	535
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	536 #define SIZE_BITS (PREV_INUSE)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	537
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	538
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	539 /* Ptr to next physical malloc_chunk. */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	540
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	541 #define 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	542
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	543 /* Ptr to previous physical malloc_chunk */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	544
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	545 #define prev_chunk(p)\
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	546 ((mchunkptr)( ((char*)(p)) - ((p)->prev_size) ))
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	549 /* 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	550
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	551 #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	552
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	553 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	554 Dealing with use bits
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	555 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	556
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	557 /* extract p's inuse bit */
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 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 /* extract inuse bit of previous chunk */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	563
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	564 #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	565
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	566 /* 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	567
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	568 #define set_inuse(p)\
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	569 ((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	570
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	571 #define clear_inuse(p)\
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	572 ((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	573
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	574 /* 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	575
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	576 #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	577 (((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	578
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	579 #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	580 (((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	581
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	582 #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	583 (((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	584
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	585
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	586 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	587 Dealing with size fields
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	588 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	589
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	590 /* Get size, ignoring use bits */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	591
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	592 #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	593
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	594 /* 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	595
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	596 #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	597
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	598 /* 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	599
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	600 #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	601
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	602 /* 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	603
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	604 #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	605
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	606
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	607 //----------------------------------------------------------------------------
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	608
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	609 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	610 Bins
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	611
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	612 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	613 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	614 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	615 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	616 and chunks are the same).
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	617
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	618 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	619 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	620 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	621 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	622
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	623 Bin layout:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	624
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	625 64 bins of size 8
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	626 32 bins of size 64
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	627 16 bins of size 512
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	628 8 bins of size 4096
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	629 4 bins of size 32768
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	630 2 bins of size 262144
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	631 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	632
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	633 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	634 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	635
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	636 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	637 (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	638 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	639 always handled specially.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	640
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	641 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	642
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	643 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	644
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	645 /* access macros */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	646
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	647 #define 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	648 #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	649 #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	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 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	653 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	654 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	655 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	656
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	657 #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	658 #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	659
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	660
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	661 /* Helper macro to initialize bins */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	662
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	663 #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	664
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	665 #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	666 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	667 0, 0,
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	668 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	669 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	670 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	671 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	672 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	673 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	674 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	675 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	676 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	677 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	678 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	679 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	680 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	681 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	682 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	683 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	684 };
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	685 #endif
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 /* field-extraction macros */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	688
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	689 #define first(b) ((b)->fd)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	690 #define last(b) ((b)->bk)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	691
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	692 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	693 Indexing into bins
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	694 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	695
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	696 #define bin_index(sz) \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	697 (((((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	698 ((((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	699 ((((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	700 ((((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	701 ((((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	702 ((((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	703 126)
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 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	706 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	707 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	708
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	709 #define MAX_SMALLBIN_SIZE 512
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	710 #define SMALLBIN_WIDTH 8
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	711 #define SMALLBIN_WIDTH_BITS 3
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	712 #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	713
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	714 #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	715
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	716 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	717 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	718 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	719
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	720 #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	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 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	724 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	725 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	726 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	727 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	728 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	729 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	730 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	731
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	732 #define BINBLOCKWIDTH 4 /* bins per block */
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 #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	735
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	736 /* bin<->block macros */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	737
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	738 #define 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	739 #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	740 #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	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 //----------------------------------------------------------------------------
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	744
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	745 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	746 Debugging support
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	747 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	748
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	749 #ifdef CYGDBG_MEMALLOC_ALLOCATOR_DLMALLOC_DEBUG
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	750
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	751 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	752 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	753 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	754 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	755 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	756 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	757 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	758
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	759 void
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	760 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	761 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	762 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	763
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	764 /* Check for legal address ... */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	765 ASSERT((cyg_uint8 *)p >= arenabase);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	766 if (p != top)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	767 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	768 else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	769 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	770
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	771 } // 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	772
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	773
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	774 void
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	775 Cyg_Mempool_dlmalloc_Implementation::do_check_free_chunk(mchunkptr p)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	776 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	777 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	778 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	779
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	780 do_check_chunk(p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	781
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	782 /* 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	783 ASSERT(!inuse(p));
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	784
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	785 /* 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	786 if ((long)sz >= (long)MINSIZE)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	787 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	788 ASSERT((sz & MALLOC_ALIGN_MASK) == 0);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	789 ASSERT(aligned_OK(chunk2mem(p)));
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	790 /* ... matching footer field */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	791 ASSERT(next->prev_size == sz);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	792 /* ... and is fully consolidated */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	793 ASSERT(prev_inuse(p));
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	794 ASSERT (next == top \|\| inuse(next));
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	795
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	796 /* ... and has minimally sane links */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	797 ASSERT(p->fd->bk == p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	798 ASSERT(p->bk->fd == p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	799 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	800 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	801 ASSERT(sz == SIZE_SZ);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	802 } // 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	803
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	804 void
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	805 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	806 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	807 mchunkptr next = next_chunk(p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	808 do_check_chunk(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 /* 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	811 ASSERT(inuse(p));
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	812
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	813 /* ... and is surrounded by OK chunks.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	814 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	815 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	816 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	817 if (!prev_inuse(p))
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 mchunkptr prv = prev_chunk(p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	820 ASSERT(next_chunk(prv) == p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	821 do_check_free_chunk(prv);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	822 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	823 if (next == top)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	824 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	825 ASSERT(prev_inuse(next));
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	826 ASSERT(chunksize(next) >= MINSIZE);
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 else if (!inuse(next))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	829 do_check_free_chunk(next);
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 } // 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	832
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	833 void
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	834 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	835 INTERNAL_SIZE_T s)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	836 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	837 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	838 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	839
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	840 do_check_inuse_chunk(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 /* Legal size ... */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	843 ASSERT((long)sz >= (long)MINSIZE);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	844 ASSERT((sz & MALLOC_ALIGN_MASK) == 0);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	845 ASSERT(room >= 0);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	846 ASSERT(room < (long)MINSIZE);
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 /* ... and alignment */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	849 ASSERT(aligned_OK(chunk2mem(p)));
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	850
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	851
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	852 /* ... and 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	853 ASSERT(prev_inuse(p));
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	854
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	855 } // 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	856
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	857
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	858 #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	859 #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	860 #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	861 #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	862 #else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	863 #define check_free_chunk(P)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	864 #define check_inuse_chunk(P)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	865 #define check_chunk(P)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	866 #define check_malloced_chunk(P,N)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	867 #endif
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	870 //----------------------------------------------------------------------------
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	871
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	872 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	873 Macro-based internal utilities
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	874 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	875
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	876
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	877 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	878 Linking chunks in bin lists.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	879 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	880 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	881
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	882 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	883 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	884 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	885 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	886
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	887
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	888 #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	889 { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	890 if (S < MAX_SMALLBIN_SIZE) \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	891 { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	892 IDX = smallbin_index(S); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	893 mark_binblock(IDX); \
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 P->bk = BK; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	897 P->fd = FD; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	898 FD->bk = BK->fd = P; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	899 } \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	900 else \
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 IDX = bin_index(S); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	903 BK = bin_at(IDX); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	904 FD = BK->fd; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	905 if (FD == BK) mark_binblock(IDX); \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	906 else \
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 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	909 BK = FD->bk; \
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 P->bk = BK; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	912 P->fd = FD; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	913 FD->bk = BK->fd = P; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	914 } \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	915 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	916
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	917
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	918 /* take a chunk off a list */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	919
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	920 #define unlink(P, BK, FD) \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	921 { \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	922 BK = P->bk; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	923 FD = P->fd; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	924 FD->bk = BK; \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	925 BK->fd = FD; \
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	928 /* Place p as the last remainder */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	929
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	930 #define link_last_remainder(P) \
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 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	933 P->fd = P->bk = last_remainder; \
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	936 /* Clear the last_remainder bin */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	937
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	938 #define clear_last_remainder \
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	939 (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	940
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 //----------------------------------------------------------------------------
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	943
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	944 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	945 cyg_uint8 *base, cyg_int32 size,
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	946 CYG_ADDRWORD /* argthru */ )
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	947 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	948 arenabase = base;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	949 arenasize = size;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	950
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	951 CYG_ADDRESS front_misalign;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	952 cyg_int32 correction;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	953
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	954 #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	955 cyg_ucount16 i;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	956 av_[0] = av_[1] = 0;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	957 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	958 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	959 } // for
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	960
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	961 #elif defined(CYGDBG_USE_ASSERTS)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	962 static int instances;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	963 if ( ++instances > 1 )
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	964 CYG_FAIL( "Multiple dlmalloc instances but "
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	965 "CYGIMP_MEMALLOC_ALLOCATOR_DLMALLOC_SAFE_MULTIPLE "
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	966 "not defined" );
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	967 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	968
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	969 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	970
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	971 if ( front_misalign > 0 ) {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	972 correction = (MALLOC_ALIGNMENT) - front_misalign;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	973 } else {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	974 correction = 0;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	975 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	976
159 511f4dc167f6 Merge from eCos master repository on 2001-05-18-01:30:05-BST jlarmour parents: 115 diff changeset	977 // too small to be useful?
511f4dc167f6 Merge from eCos master repository on 2001-05-18-01:30:05-BST jlarmour parents: 115 diff changeset	978 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	979 // 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	980 arenabase = NULL;
511f4dc167f6 Merge from eCos master repository on 2001-05-18-01:30:05-BST jlarmour parents: 115 diff changeset	981 else {
511f4dc167f6 Merge from eCos master repository on 2001-05-18-01:30:05-BST jlarmour parents: 115 diff changeset	982 top = (mchunkptr)(base + correction);
511f4dc167f6 Merge from eCos master repository on 2001-05-18-01:30:05-BST jlarmour parents: 115 diff changeset	983 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	984 }
115 6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	985 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	986
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	987 //----------------------------------------------------------------------------
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	988
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	989 /* Main public routines */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	990
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	991 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	992 Malloc Algorithm:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	993
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	994 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	995 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	996 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	997 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	998 (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	999
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1000 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	1001
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1002 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	1003 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	1004
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1005 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	1006 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	1007 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	1008 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	1009 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	1010 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	1011 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	1012 fragmentation in the long run.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1013
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1014 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	1015 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	1016 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	1017 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	1018 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	1019
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1020 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	1021 (`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	1022 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	1023 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	1024 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	1025 (up to system limitations).
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1026
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1027 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	1028 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	1029 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	1030 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	1031 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	1032
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1033 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1034
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1035 cyg_uint8 *
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1036 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	1037 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1038 mchunkptr victim; /* inspected/selected chunk */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1039 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	1040 int idx; /* index for bin traversal */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1041 mbinptr bin; /* associated bin */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1042 mchunkptr remainder; /* remainder from a split */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1043 long remainder_size; /* its size */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1044 int remainder_index; /* its bin index */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1045 unsigned long block; /* block traverser bit */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1046 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	1047 mchunkptr fwd; /* misc temp for linking */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1048 mchunkptr bck; /* misc temp for linking */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1049 mbinptr q; /* misc temp */
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 INTERNAL_SIZE_T nb;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1052
159 511f4dc167f6 Merge from eCos master repository on 2001-05-18-01:30:05-BST jlarmour parents: 115 diff changeset	1053 /* 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	1054 * 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	1055 * memory. */
511f4dc167f6 Merge from eCos master repository on 2001-05-18-01:30:05-BST jlarmour parents: 115 diff changeset	1056 if (NULL==arenabase) return NULL;
511f4dc167f6 Merge from eCos master repository on 2001-05-18-01:30:05-BST jlarmour parents: 115 diff changeset	1057
115 6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1058 if ((long)bytes < 0) return 0;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1059
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1060 nb = request2size(bytes); /* padded request size; */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1061
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1062 MALLOC_LOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1063
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1064 /* 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	1065
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1066 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	1067 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1068 idx = smallbin_index(nb);
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 /* 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	1071
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1072 q = bin_at(idx);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1073 victim = last(q);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1074
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1075 #if MALLOC_ALIGN != 16
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1076 /* 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	1077 if (victim == q)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1078 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1079 q = next_bin(q);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1080 victim = last(q);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1081 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1082 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1083 if (victim != q)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1084 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1085 victim_size = chunksize(victim);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1086 unlink(victim, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1087 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	1088 check_malloced_chunk(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1089 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1090 return chunk2mem(victim);
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1093 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	1094
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1095 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1096 else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1097 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1098 idx = bin_index(nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1099 bin = bin_at(idx);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1100
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1101 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	1102 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1103 victim_size = chunksize(victim);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1104 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	1105
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1106 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	1107 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1108 --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	1109 break;
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 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	1113 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1114 unlink(victim, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1115 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	1116 check_malloced_chunk(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1117 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1118 return chunk2mem(victim);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1119 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1120 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1121
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1122 ++idx;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1123
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1124 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1125
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1126 /* 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	1127
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1128 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	1129 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1130 victim_size = chunksize(victim);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1131 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	1132
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1133 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	1134 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1135 remainder = chunk_at_offset(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1136 set_head(victim, nb \| PREV_INUSE);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1137 link_last_remainder(remainder);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1138 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	1139 set_foot(remainder, remainder_size);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1140 check_malloced_chunk(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1141 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1142 return chunk2mem(victim);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1143 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1144
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1145 clear_last_remainder;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1146
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1147 if (remainder_size >= 0) /* exhaust */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1148 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1149 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	1150 check_malloced_chunk(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1151 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1152 return chunk2mem(victim);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1153 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1154
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1155 /* Else place in bin */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1156
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1157 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	1158 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1159
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1160 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1161 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	1162 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	1163 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1164
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1165 if ( (block = idx2binblock(idx)) <= binblocks)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1166 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1167
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1168 /* Get to the first marked block */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1169
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1170 if ( (block & binblocks) == 0)
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 /* force to an even block boundary */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1173 idx = (idx & ~(BINBLOCKWIDTH - 1)) + BINBLOCKWIDTH;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1174 block <<= 1;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1175 while ((block & binblocks) == 0)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1176 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1177 idx += BINBLOCKWIDTH;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1178 block <<= 1;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1179 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1180 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1181
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1182 /* For each possibly nonempty block ... */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1183 for (;;)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1184 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1185 startidx = idx; /* (track incomplete blocks) */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1186 q = bin = bin_at(idx);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1187
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1188 /* For each bin in this block ... */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1189 do
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 /* 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	1192
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1193 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	1194 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1195 victim_size = chunksize(victim);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1196 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	1197
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1198 if (remainder_size >= (long)MINSIZE) /* split */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1199 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1200 remainder = chunk_at_offset(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1201 set_head(victim, nb \| PREV_INUSE);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1202 unlink(victim, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1203 link_last_remainder(remainder);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1204 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	1205 set_foot(remainder, remainder_size);
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 else if (remainder_size >= 0) /* take */
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 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	1214 unlink(victim, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1215 check_malloced_chunk(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1216 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1217 return chunk2mem(victim);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1218 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1219
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1220 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1221
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1222 bin = next_bin(bin);
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 #if MALLOC_ALIGN == 16
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1225 if (idx < MAX_SMALLBIN)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1226 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1227 bin = next_bin(bin);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1228 ++idx;
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 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1231 } while ((++idx & (BINBLOCKWIDTH - 1)) != 0);
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 /* Clear out the block bit. */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1234
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1235 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	1236 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1237 if ((startidx & (BINBLOCKWIDTH - 1)) == 0)
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 binblocks &= ~block;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1240 break;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1241 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1242 --startidx;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1243 q = prev_bin(q);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1244 } while (first(q) == q);
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 /* 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	1247
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1248 if ( (block <<= 1) <= binblocks && (block != 0) )
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 while ((block & binblocks) == 0)
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 idx += BINBLOCKWIDTH;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1253 block <<= 1;
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 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1256 else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1257 break;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1258 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1259 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1260
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1261
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1262 /* Try to use top chunk */
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 /* 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	1265 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	1266 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	1267 {
171 42f843b391aa Merge from eCos master repository on 2001-07-18-03:13:25-BST jlarmour parents: 163 diff changeset	1268 //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	1269 // nb, remainder_size);
115 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 NULL; /* propagate failure */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1272 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1273
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1274 victim = top;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1275 set_head(victim, nb \| PREV_INUSE);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1276 top = chunk_at_offset(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1277 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	1278 check_malloced_chunk(victim, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1279 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1280 return chunk2mem(victim);
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 } // Cyg_Mempool_dlmalloc_Implementation::try_alloc()
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 //----------------------------------------------------------------------------
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1285
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1286 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1287 free() algorithm :
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 cases:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1290
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1291 1. free(NULL) has no effect.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1292
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1293 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	1294 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	1295 consolidating with the current `last_remainder').
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1296 */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1297
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1298 cyg_bool
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1299 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	1300 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1301 mchunkptr p; /* chunk corresponding to mem */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1302 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	1303 INTERNAL_SIZE_T sz; /* its size */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1304 int idx; /* its bin index */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1305 mchunkptr next; /* next contiguous chunk */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1306 INTERNAL_SIZE_T nextsz; /* its size */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1307 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	1308 mchunkptr bck; /* misc temp for linking */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1309 mchunkptr fwd; /* misc temp for linking */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1310 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	1311
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1312 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	1313 return false;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1314
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1315 MALLOC_LOCK;
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 p = mem2chunk(mem);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1318 hd = p->size;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1319
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1320 check_inuse_chunk(p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1321
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1322 sz = hd & ~PREV_INUSE;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1323 next = chunk_at_offset(p, sz);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1324 nextsz = chunksize(next);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1325
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1326 if (next == top) /* merge with top */
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 sz += nextsz;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1329
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1330 if (!(hd & PREV_INUSE)) /* consolidate backward */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1331 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1332 prevsz = p->prev_size;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1333 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	1334 sz += prevsz;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1335 unlink(p, bck, fwd);
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1338 set_head(p, sz \| PREV_INUSE);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1339 top = p;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1340 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1341 return true;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1342 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1343
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1344 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	1345
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1346 islr = 0;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1347
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1348 if (!(hd & PREV_INUSE)) /* consolidate backward */
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 prevsz = p->prev_size;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1351 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	1352 sz += prevsz;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1353
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1354 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	1355 islr = 1;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1356 else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1357 unlink(p, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1358 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1359
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1360 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	1361 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1362 sz += nextsz;
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 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	1365 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1366 islr = 1;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1367 link_last_remainder(p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1368 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1369 else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1370 unlink(next, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1371 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1372
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1373
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1374 set_head(p, sz \| PREV_INUSE);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1375 set_foot(p, sz);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1376 if (!islr)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1377 frontlink(p, sz, idx, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1378
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1379 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1380
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1381 return true;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1382 } // Cyg_Mempool_dlmalloc_Implementation::free()
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1383
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1384 //----------------------------------------------------------------------------
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1385
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1386 // 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	1387 // 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	1388 // 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	1389 // 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	1390 // 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	1391 // 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	1392 // 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	1393 // 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	1394 // 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	1395 // 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	1396
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1397
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1398 // DOCUMENTATION FROM ORIGINAL FILE:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1399 // (some now irrelevant parts elided)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1400 /*
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1401 Realloc algorithm:
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 additional space, and the
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1404 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	1405 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	1406 extended. All are tried:
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1407
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1408 * 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	1409 * Shifting backwards, joining preceding adjacent space
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1410 * Both shifting backwards and extending forward.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1411
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1412 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	1413 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	1414 off and freed.
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1415
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1416 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	1417 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	1418 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	1419 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	1420 usages of realloc to be sensible.
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1423 cyg_uint8 *
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1424 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	1425 cyg_int32 bytes,
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1426 cyg_int32 *poldsize )
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1427 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1428
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1429 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	1430
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1431 mchunkptr oldp; /* chunk corresponding to oldmem */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1432 INTERNAL_SIZE_T oldsize; /* its size */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1433
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1434 mchunkptr newp; /* chunk to return */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1435 INTERNAL_SIZE_T newsize; /* its size */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1436 cyg_uint8* newmem; /* corresponding user mem */
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 next; /* next contiguous chunk after oldp */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1439 INTERNAL_SIZE_T nextsize; /* its size */
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 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	1442 INTERNAL_SIZE_T prevsize; /* its size */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1443
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1444 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	1445 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	1446
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1447 mchunkptr bck; /* misc temp for linking */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1448 mchunkptr fwd; /* misc temp for linking */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1449
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1450 MALLOC_LOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1451
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1452 newp = oldp = mem2chunk(oldmem);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1453 newsize = oldsize = chunksize(oldp);
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 if (NULL != poldsize)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1456 *poldsize = oldsize - SIZE_SZ;
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 nb = request2size(bytes);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1459
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1460 check_inuse_chunk(oldp);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1461
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1462 if ((long)(oldsize) < (long)(nb))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1463 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1464
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1465 /* Try expanding forward */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1466
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1467 next = chunk_at_offset(oldp, oldsize);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1468 if (next == top \|\| !inuse(next))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1469 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1470 nextsize = chunksize(next);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1471
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1472 /* 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	1473 if (next == top)
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 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	1476 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1477 newsize += nextsize;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1478 top = chunk_at_offset(oldp, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1479 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	1480 set_head_size(oldp, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1481 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1482 return chunk2mem(oldp);
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1486 /* Forward into next chunk */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1487 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	1488 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1489 unlink(next, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1490 newsize += nextsize;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1491 goto split;
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 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1494 else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1495 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1496 next = 0;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1497 nextsize = 0;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1498 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1499
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1500 /* Try shifting backwards. */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1501
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1502 if (!prev_inuse(oldp))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1503 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1504 prev = prev_chunk(oldp);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1505 prevsize = chunksize(prev);
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 /* 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	1508
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1509 if (next != 0)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1510 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1511 /* into top */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1512 if (next == top)
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1513 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1514 if ((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	1515 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1516 unlink(prev, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1517 newp = prev;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1518 newsize += prevsize + nextsize;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1519 newmem = chunk2mem(newp);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1520 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	1521 top = chunk_at_offset(newp, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1522 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	1523 set_head_size(newp, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1524 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1525 return newmem;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1526 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1527 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1528
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1529 /* into next chunk */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1530 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	1531 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1532 unlink(next, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1533 unlink(prev, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1534 newp = prev;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1535 newsize += nextsize + prevsize;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1536 newmem = chunk2mem(newp);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1537 MALLOC_COPY(newmem, oldmem, oldsize - SIZE_SZ);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1538 goto split;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1539 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1540 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1541
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1542 /* backward only */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1543 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	1544 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1545 unlink(prev, bck, fwd);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1546 newp = prev;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1547 newsize += prevsize;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1548 newmem = chunk2mem(newp);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1549 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	1550 goto split;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1551 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1552 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1553
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1554 // 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	1555 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1556 return NULL;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1557 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1558
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1559
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1560 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	1561
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1562 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	1563
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1564 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	1565 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1566 remainder = chunk_at_offset(newp, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1567 set_head_size(newp, nb);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1568 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	1569 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	1570 /* let free() deal with it */
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1571 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	1572 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1573 else
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1574 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1575 set_head_size(newp, newsize);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1576 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	1577 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1578
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1579 check_inuse_chunk(newp);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1580 MALLOC_UNLOCK;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1581 return chunk2mem(newp);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1582
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1583 } // Cyg_Mempool_dlmalloc_Implementation::resize_alloc()
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1584
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
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1587 // Get memory pool status
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1588 // 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	1589 // defined in common.hxx
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1590 void
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1591 Cyg_Mempool_dlmalloc_Implementation::get_status(
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1592 cyg_mempool_status_flag_t flags,
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1593 Cyg_Mempool_Status &status )
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1594 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1595 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	1596 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	1597 {
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1598 int i;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1599 mbinptr b;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1600 mchunkptr p;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1601 cyg_int32 chunksizep;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1602 cyg_int32 maxfree;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1603 #ifdef CYGDBG_MEMALLOC_ALLOCATOR_DLMALLOC_DEBUG
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1604 mchunkptr q;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1605 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1606
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1607 INTERNAL_SIZE_T avail = chunksize(top);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1608 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	1609 maxfree = avail;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1610
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1611 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	1612 b = bin_at(i);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1613 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	1614 #ifdef CYGDBG_MEMALLOC_ALLOCATOR_DLMALLOC_DEBUG
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1615 check_free_chunk(p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1616 for (q = next_chunk(p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1617 (q < top) && inuse(q) &&
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1618 (long)(chunksize(q)) >= (long)MINSIZE;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1619 q = next_chunk(q))
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1620 check_inuse_chunk(q);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1621 #endif
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1622 chunksizep = chunksize(p);
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1623 avail += chunksizep;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1624 if ( chunksizep > maxfree )
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1625 maxfree = chunksizep;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1626 navail++;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1627 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1628 }
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1629
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1630 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	1631 status.totalallocated = arenasize - avail;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1632 // 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	1633 // test flag first
171 42f843b391aa Merge from eCos master repository on 2001-07-18-03:13:25-BST jlarmour parents: 163 diff changeset	1634 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	1635 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	1636 >= MINSIZE, "free mem negative!" );
115 6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1637 status.freeblocks = navail;
171 42f843b391aa Merge from eCos master repository on 2001-07-18-03:13:25-BST jlarmour parents: 163 diff changeset	1638 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	1639 //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	1640 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	1641 ~MALLOC_ALIGN_MASK) >= MINSIZE,
42f843b391aa Merge from eCos master repository on 2001-07-18-03:13:25-BST jlarmour parents: 163 diff changeset	1642 "max free block size negative!" );
115 6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1643 } // if
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 // 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	1646 // test flag first
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1647 status.arenabase = status.origbase = arenabase;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1648 status.arenasize = status.origsize = arenasize;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1649 status.maxoverhead = MINSIZE + MALLOC_ALIGNMENT;
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1650
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1651 } // Cyg_Mempool_dlmalloc_Implementation::get_status()
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1652
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1653
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1654 //----------------------------------------------------------------------------
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1655
6ed91473a1cd Merge from eCos master repository on 2000-08-21-22:40:54-BST jlarmour parents: diff changeset	1656 // EOF dlmalloc.cxx

Mercurial > ecos

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