Rev 6099 | Go to most recent revision | Only display areas with differences | Regard whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 6099 | Rev 6536 | ||
---|---|---|---|
1 | /* |
1 | /* |
2 | This is a version (aka dlmalloc) of malloc/free/realloc written by |
2 | This is a version (aka dlmalloc) of malloc/free/realloc written by |
3 | Doug Lea and released to the public domain, as explained at |
3 | Doug Lea and released to the public domain, as explained at |
4 | http://creativecommons.org/licenses/publicdomain. Send questions, |
4 | http://creativecommons.org/licenses/publicdomain. Send questions, |
5 | comments, complaints, performance data, etc to dl@cs.oswego.edu |
5 | comments, complaints, performance data, etc to dl@cs.oswego.edu |
6 | 6 | ||
7 | * Version 2.8.4 Wed May 27 09:56:23 2009 Doug Lea (dl at gee) |
7 | * Version 2.8.4 Wed May 27 09:56:23 2009 Doug Lea (dl at gee) |
8 | 8 | ||
9 | Note: There may be an updated version of this malloc obtainable at |
9 | Note: There may be an updated version of this malloc obtainable at |
10 | ftp://gee.cs.oswego.edu/pub/misc/malloc.c |
10 | ftp://gee.cs.oswego.edu/pub/misc/malloc.c |
11 | Check before installing! |
11 | Check before installing! |
12 | 12 | ||
13 | * Quickstart |
13 | * Quickstart |
14 | 14 | ||
15 | This library is all in one file to simplify the most common usage: |
15 | This library is all in one file to simplify the most common usage: |
16 | ftp it, compile it (-O3), and link it into another program. All of |
16 | ftp it, compile it (-O3), and link it into another program. All of |
17 | the compile-time options default to reasonable values for use on |
17 | the compile-time options default to reasonable values for use on |
18 | most platforms. You might later want to step through various |
18 | most platforms. You might later want to step through various |
19 | compile-time and dynamic tuning options. |
19 | compile-time and dynamic tuning options. |
20 | 20 | ||
21 | For convenience, an include file for code using this malloc is at: |
21 | For convenience, an include file for code using this malloc is at: |
22 | ftp://gee.cs.oswego.edu/pub/misc/malloc-2.8.4.h |
22 | ftp://gee.cs.oswego.edu/pub/misc/malloc-2.8.4.h |
23 | You don't really need this .h file unless you call functions not |
23 | You don't really need this .h file unless you call functions not |
24 | defined in your system include files. The .h file contains only the |
24 | defined in your system include files. The .h file contains only the |
25 | excerpts from this file needed for using this malloc on ANSI C/C++ |
25 | excerpts from this file needed for using this malloc on ANSI C/C++ |
26 | systems, so long as you haven't changed compile-time options about |
26 | systems, so long as you haven't changed compile-time options about |
27 | naming and tuning parameters. If you do, then you can create your |
27 | naming and tuning parameters. If you do, then you can create your |
28 | own malloc.h that does include all settings by cutting at the point |
28 | own malloc.h that does include all settings by cutting at the point |
29 | indicated below. Note that you may already by default be using a C |
29 | indicated below. Note that you may already by default be using a C |
30 | library containing a malloc that is based on some version of this |
30 | library containing a malloc that is based on some version of this |
31 | malloc (for example in linux). You might still want to use the one |
31 | malloc (for example in linux). You might still want to use the one |
32 | in this file to customize settings or to avoid overheads associated |
32 | in this file to customize settings or to avoid overheads associated |
33 | with library versions. |
33 | with library versions. |
34 | 34 | ||
35 | */ |
35 | */ |
36 | #include |
36 | #include |
37 | #include |
37 | #include |
38 | #include |
38 | #include |
39 | 39 | ||
40 | 40 | ||
41 | 41 | ||
42 | struct malloc_chunk { |
42 | struct malloc_chunk { |
43 | size_t prev_foot; /* Size of previous chunk (if free). */ |
43 | size_t prev_foot; /* Size of previous chunk (if free). */ |
44 | size_t head; /* Size and inuse bits. */ |
44 | size_t head; /* Size and inuse bits. */ |
45 | struct malloc_chunk* fd; /* double links -- used only if free. */ |
45 | struct malloc_chunk* fd; /* double links -- used only if free. */ |
46 | struct malloc_chunk* bk; |
46 | struct malloc_chunk* bk; |
47 | }; |
47 | }; |
48 | 48 | ||
49 | typedef struct malloc_chunk mchunk; |
49 | typedef struct malloc_chunk mchunk; |
50 | typedef struct malloc_chunk* mchunkptr; |
50 | typedef struct malloc_chunk* mchunkptr; |
51 | typedef struct malloc_chunk* sbinptr; /* The type of bins of chunks */ |
51 | typedef struct malloc_chunk* sbinptr; /* The type of bins of chunks */ |
52 | typedef unsigned int bindex_t; /* Described below */ |
52 | typedef unsigned int bindex_t; /* Described below */ |
53 | typedef unsigned int binmap_t; /* Described below */ |
53 | typedef unsigned int binmap_t; /* Described below */ |
54 | typedef unsigned int flag_t; /* The type of various bit flag sets */ |
54 | typedef unsigned int flag_t; /* The type of various bit flag sets */ |
55 | 55 | ||
56 | 56 | ||
57 | 57 | ||
58 | /* ------------------- size_t and alignment properties -------------------- */ |
58 | /* ------------------- size_t and alignment properties -------------------- */ |
59 | 59 | ||
60 | /* The maximum possible size_t value has all bits set */ |
60 | /* The maximum possible size_t value has all bits set */ |
61 | #define MAX_SIZE_T (~(size_t)0) |
61 | #define MAX_SIZE_T (~(size_t)0) |
62 | 62 | ||
63 | void *user_alloc(size_t size) |
63 | void *user_alloc(size_t size) |
64 | { |
64 | { |
65 | void *val; |
65 | void *val; |
66 | 66 | ||
67 | // __asm__("int3"); |
67 | // __asm__("int3"); |
68 | 68 | ||
69 | __asm__ __volatile__( |
69 | __asm__ __volatile__( |
70 | "int $0x40" |
70 | "int $0x40" |
71 | :"=a"(val) |
71 | :"=a"(val) |
72 | :"a"(68),"b"(12),"c"(size)); |
72 | :"a"(68),"b"(12),"c"(size)); |
73 | return val; |
73 | return val; |
74 | } |
74 | } |
75 | 75 | ||
76 | static inline |
76 | static inline |
77 | int user_free(void *mem) |
77 | int user_free(void *mem) |
78 | { |
78 | { |
79 | int val; |
79 | int val; |
80 | 80 | ||
81 | // __asm__("int3"); |
81 | // __asm__("int3"); |
82 | 82 | ||
83 | __asm__ __volatile__( |
83 | __asm__ __volatile__( |
84 | "int $0x40" |
84 | "int $0x40" |
85 | :"=a"(val) |
85 | :"=a"(val) |
86 | :"a"(68),"b"(13),"c"(mem)); |
86 | :"a"(68),"b"(13),"c"(mem)); |
87 | return val; |
87 | return val; |
88 | } |
88 | } |
89 | 89 | ||
90 | 90 | ||
91 | /* ------------------- size_t and alignment properties -------------------- */ |
91 | /* ------------------- size_t and alignment properties -------------------- */ |
92 | 92 | ||
93 | /* The byte and bit size of a size_t */ |
93 | /* The byte and bit size of a size_t */ |
94 | #define SIZE_T_SIZE (sizeof(size_t)) |
94 | #define SIZE_T_SIZE (sizeof(size_t)) |
95 | #define SIZE_T_BITSIZE (sizeof(size_t) << 3) |
95 | #define SIZE_T_BITSIZE (sizeof(size_t) << 3) |
96 | 96 | ||
97 | /* Some constants coerced to size_t */ |
97 | /* Some constants coerced to size_t */ |
98 | /* Annoying but necessary to avoid errors on some platforms */ |
98 | /* Annoying but necessary to avoid errors on some platforms */ |
99 | #define SIZE_T_ZERO ((size_t)0) |
99 | #define SIZE_T_ZERO ((size_t)0) |
100 | #define SIZE_T_ONE ((size_t)1) |
100 | #define SIZE_T_ONE ((size_t)1) |
101 | #define SIZE_T_TWO ((size_t)2) |
101 | #define SIZE_T_TWO ((size_t)2) |
102 | #define SIZE_T_FOUR ((size_t)4) |
102 | #define SIZE_T_FOUR ((size_t)4) |
103 | #define TWO_SIZE_T_SIZES (SIZE_T_SIZE<<1) |
103 | #define TWO_SIZE_T_SIZES (SIZE_T_SIZE<<1) |
104 | #define FOUR_SIZE_T_SIZES (SIZE_T_SIZE<<2) |
104 | #define FOUR_SIZE_T_SIZES (SIZE_T_SIZE<<2) |
105 | #define SIX_SIZE_T_SIZES (FOUR_SIZE_T_SIZES+TWO_SIZE_T_SIZES) |
105 | #define SIX_SIZE_T_SIZES (FOUR_SIZE_T_SIZES+TWO_SIZE_T_SIZES) |
106 | #define HALF_MAX_SIZE_T (MAX_SIZE_T / 2U) |
106 | #define HALF_MAX_SIZE_T (MAX_SIZE_T / 2U) |
107 | 107 | ||
108 | #define USE_LOCK_BIT (2U) |
108 | #define USE_LOCK_BIT (2U) |
109 | #define USE_MMAP_BIT (SIZE_T_ONE) |
109 | #define USE_MMAP_BIT (SIZE_T_ONE) |
110 | #define USE_NONCONTIGUOUS_BIT (4U) |
110 | #define USE_NONCONTIGUOUS_BIT (4U) |
111 | 111 | ||
112 | /* segment bit set in create_mspace_with_base */ |
112 | /* segment bit set in create_mspace_with_base */ |
113 | #define EXTERN_BIT (8U) |
113 | #define EXTERN_BIT (8U) |
114 | 114 | ||
115 | #define HAVE_MMAP 1 |
115 | #define HAVE_MMAP 1 |
116 | #define CALL_MMAP(s) MMAP_DEFAULT(s) |
116 | #define CALL_MMAP(s) MMAP_DEFAULT(s) |
117 | #define CALL_MUNMAP(a, s) MUNMAP_DEFAULT((a), (s)) |
117 | #define CALL_MUNMAP(a, s) MUNMAP_DEFAULT((a), (s)) |
118 | #define CALL_MREMAP(addr, osz, nsz, mv) MFAIL |
118 | #define CALL_MREMAP(addr, osz, nsz, mv) MFAIL |
119 | 119 | ||
120 | #define calloc_must_clear(p) (!is_mmapped(p)) |
120 | #define calloc_must_clear(p) (!is_mmapped(p)) |
121 | 121 | ||
122 | #define MALLOC_FAILURE_ACTION |
122 | #define MALLOC_FAILURE_ACTION |
123 | 123 | ||
124 | #define MAX_RELEASE_CHECK_RATE 4095 |
124 | #define MAX_RELEASE_CHECK_RATE 4095 |
125 | #define NO_SEGMENT_TRAVERSAL 1 |
125 | #define NO_SEGMENT_TRAVERSAL 1 |
126 | #define MALLOC_ALIGNMENT ((size_t)8U) |
126 | #define MALLOC_ALIGNMENT ((size_t)8U) |
127 | #define CHUNK_OVERHEAD (SIZE_T_SIZE) |
127 | #define CHUNK_OVERHEAD (SIZE_T_SIZE) |
128 | #define DEFAULT_GRANULARITY ((size_t)512U * (size_t)1024U) |
128 | #define DEFAULT_GRANULARITY ((size_t)512U * (size_t)1024U) |
129 | #define DEFAULT_MMAP_THRESHOLD ((size_t)1024U * (size_t)1024U) |
129 | #define DEFAULT_MMAP_THRESHOLD ((size_t)1024U * (size_t)1024U) |
130 | #define DEFAULT_TRIM_THRESHOLD ((size_t)2048U * (size_t)1024U) |
130 | #define DEFAULT_TRIM_THRESHOLD ((size_t)2048U * (size_t)1024U) |
131 | 131 | ||
132 | /* The bit mask value corresponding to MALLOC_ALIGNMENT */ |
132 | /* The bit mask value corresponding to MALLOC_ALIGNMENT */ |
133 | #define CHUNK_ALIGN_MASK (MALLOC_ALIGNMENT - SIZE_T_ONE) |
133 | #define CHUNK_ALIGN_MASK (MALLOC_ALIGNMENT - SIZE_T_ONE) |
134 | 134 | ||
135 | /* True if address a has acceptable alignment */ |
135 | /* True if address a has acceptable alignment */ |
136 | #define is_aligned(A) (((size_t)((A)) & (CHUNK_ALIGN_MASK)) == 0) |
136 | #define is_aligned(A) (((size_t)((A)) & (CHUNK_ALIGN_MASK)) == 0) |
137 | 137 | ||
138 | /* the number of bytes to offset an address to align it */ |
138 | /* the number of bytes to offset an address to align it */ |
139 | #define align_offset(A)\ |
139 | #define align_offset(A)\ |
140 | ((((size_t)(A) & CHUNK_ALIGN_MASK) == 0)? 0 :\ |
140 | ((((size_t)(A) & CHUNK_ALIGN_MASK) == 0)? 0 :\ |
141 | ((MALLOC_ALIGNMENT - ((size_t)(A) & CHUNK_ALIGN_MASK)) & CHUNK_ALIGN_MASK)) |
141 | ((MALLOC_ALIGNMENT - ((size_t)(A) & CHUNK_ALIGN_MASK)) & CHUNK_ALIGN_MASK)) |
142 | 142 | ||
143 | 143 | ||
144 | #define MFAIL ((void*)(MAX_SIZE_T)) |
144 | #define MFAIL ((void*)(MAX_SIZE_T)) |
145 | #define CMFAIL ((char*)(MFAIL)) /* defined for convenience */ |
145 | #define CMFAIL ((char*)(MFAIL)) /* defined for convenience */ |
146 | 146 | ||
147 | /* For sys_alloc, enough padding to ensure can malloc request on success */ |
147 | /* For sys_alloc, enough padding to ensure can malloc request on success */ |
148 | #define SYS_ALLOC_PADDING (TOP_FOOT_SIZE + MALLOC_ALIGNMENT) |
148 | #define SYS_ALLOC_PADDING (TOP_FOOT_SIZE + MALLOC_ALIGNMENT) |
149 | 149 | ||
150 | /* |
150 | /* |
151 | TOP_FOOT_SIZE is padding at the end of a segment, including space |
151 | TOP_FOOT_SIZE is padding at the end of a segment, including space |
152 | that may be needed to place segment records and fenceposts when new |
152 | that may be needed to place segment records and fenceposts when new |
153 | noncontiguous segments are added. |
153 | noncontiguous segments are added. |
154 | */ |
154 | */ |
155 | #define TOP_FOOT_SIZE\ |
155 | #define TOP_FOOT_SIZE\ |
156 | (align_offset(chunk2mem(0))+pad_request(sizeof(struct malloc_segment))+MIN_CHUNK_SIZE) |
156 | (align_offset(chunk2mem(0))+pad_request(sizeof(struct malloc_segment))+MIN_CHUNK_SIZE) |
157 | 157 | ||
158 | /* ------------------- Chunks sizes and alignments ----------------------- */ |
158 | /* ------------------- Chunks sizes and alignments ----------------------- */ |
159 | 159 | ||
160 | #define MCHUNK_SIZE (sizeof(mchunk)) |
160 | #define MCHUNK_SIZE (sizeof(mchunk)) |
161 | 161 | ||
162 | /* MMapped chunks need a second word of overhead ... */ |
162 | /* MMapped chunks need a second word of overhead ... */ |
163 | #define MMAP_CHUNK_OVERHEAD (TWO_SIZE_T_SIZES) |
163 | #define MMAP_CHUNK_OVERHEAD (TWO_SIZE_T_SIZES) |
164 | /* ... and additional padding for fake next-chunk at foot */ |
164 | /* ... and additional padding for fake next-chunk at foot */ |
165 | #define MMAP_FOOT_PAD (FOUR_SIZE_T_SIZES) |
165 | #define MMAP_FOOT_PAD (FOUR_SIZE_T_SIZES) |
166 | 166 | ||
167 | /* The smallest size we can malloc is an aligned minimal chunk */ |
167 | /* The smallest size we can malloc is an aligned minimal chunk */ |
168 | #define MIN_CHUNK_SIZE\ |
168 | #define MIN_CHUNK_SIZE\ |
169 | ((MCHUNK_SIZE + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK) |
169 | ((MCHUNK_SIZE + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK) |
170 | 170 | ||
171 | /* conversion from malloc headers to user pointers, and back */ |
171 | /* conversion from malloc headers to user pointers, and back */ |
172 | #define chunk2mem(p) ((void*)((char*)(p) + TWO_SIZE_T_SIZES)) |
172 | #define chunk2mem(p) ((void*)((char*)(p) + TWO_SIZE_T_SIZES)) |
173 | #define mem2chunk(mem) ((mchunkptr)((char*)(mem) - TWO_SIZE_T_SIZES)) |
173 | #define mem2chunk(mem) ((mchunkptr)((char*)(mem) - TWO_SIZE_T_SIZES)) |
174 | /* chunk associated with aligned address A */ |
174 | /* chunk associated with aligned address A */ |
175 | #define align_as_chunk(A) (mchunkptr)((A) + align_offset(chunk2mem(A))) |
175 | #define align_as_chunk(A) (mchunkptr)((A) + align_offset(chunk2mem(A))) |
176 | 176 | ||
177 | /* Bounds on request (not chunk) sizes. */ |
177 | /* Bounds on request (not chunk) sizes. */ |
178 | #define MAX_REQUEST ((-MIN_CHUNK_SIZE) << 2) |
178 | #define MAX_REQUEST ((-MIN_CHUNK_SIZE) << 2) |
179 | #define MIN_REQUEST (MIN_CHUNK_SIZE - CHUNK_OVERHEAD - SIZE_T_ONE) |
179 | #define MIN_REQUEST (MIN_CHUNK_SIZE - CHUNK_OVERHEAD - SIZE_T_ONE) |
180 | 180 | ||
181 | /* pad request bytes into a usable size */ |
181 | /* pad request bytes into a usable size */ |
182 | #define pad_request(req) \ |
182 | #define pad_request(req) \ |
183 | (((req) + CHUNK_OVERHEAD + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK) |
183 | (((req) + CHUNK_OVERHEAD + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK) |
184 | 184 | ||
185 | /* pad request, checking for minimum (but not maximum) */ |
185 | /* pad request, checking for minimum (but not maximum) */ |
186 | #define request2size(req) \ |
186 | #define request2size(req) \ |
187 | (((req) < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(req)) |
187 | (((req) < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(req)) |
188 | 188 | ||
189 | /* ------------------ Operations on head and foot fields ----------------- */ |
189 | /* ------------------ Operations on head and foot fields ----------------- */ |
190 | 190 | ||
191 | /* |
191 | /* |
192 | The head field of a chunk is or'ed with PINUSE_BIT when previous |
192 | The head field of a chunk is or'ed with PINUSE_BIT when previous |
193 | adjacent chunk in use, and or'ed with CINUSE_BIT if this chunk is in |
193 | adjacent chunk in use, and or'ed with CINUSE_BIT if this chunk is in |
194 | use, unless mmapped, in which case both bits are cleared. |
194 | use, unless mmapped, in which case both bits are cleared. |
195 | 195 | ||
196 | FLAG4_BIT is not used by this malloc, but might be useful in extensions. |
196 | FLAG4_BIT is not used by this malloc, but might be useful in extensions. |
197 | */ |
197 | */ |
198 | 198 | ||
199 | #define PINUSE_BIT (SIZE_T_ONE) |
199 | #define PINUSE_BIT (SIZE_T_ONE) |
200 | #define CINUSE_BIT (SIZE_T_TWO) |
200 | #define CINUSE_BIT (SIZE_T_TWO) |
201 | #define FLAG4_BIT (SIZE_T_FOUR) |
201 | #define FLAG4_BIT (SIZE_T_FOUR) |
202 | #define INUSE_BITS (PINUSE_BIT|CINUSE_BIT) |
202 | #define INUSE_BITS (PINUSE_BIT|CINUSE_BIT) |
203 | #define FLAG_BITS (PINUSE_BIT|CINUSE_BIT|FLAG4_BIT) |
203 | #define FLAG_BITS (PINUSE_BIT|CINUSE_BIT|FLAG4_BIT) |
204 | 204 | ||
205 | /* Head value for fenceposts */ |
205 | /* Head value for fenceposts */ |
206 | #define FENCEPOST_HEAD (INUSE_BITS|SIZE_T_SIZE) |
206 | #define FENCEPOST_HEAD (INUSE_BITS|SIZE_T_SIZE) |
207 | 207 | ||
208 | /* extraction of fields from head words */ |
208 | /* extraction of fields from head words */ |
209 | #define cinuse(p) ((p)->head & CINUSE_BIT) |
209 | #define cinuse(p) ((p)->head & CINUSE_BIT) |
210 | #define pinuse(p) ((p)->head & PINUSE_BIT) |
210 | #define pinuse(p) ((p)->head & PINUSE_BIT) |
211 | #define is_inuse(p) (((p)->head & INUSE_BITS) != PINUSE_BIT) |
211 | #define is_inuse(p) (((p)->head & INUSE_BITS) != PINUSE_BIT) |
212 | #define is_mmapped(p) (((p)->head & INUSE_BITS) == 0) |
212 | #define is_mmapped(p) (((p)->head & INUSE_BITS) == 0) |
213 | 213 | ||
214 | #define chunksize(p) ((p)->head & ~(FLAG_BITS)) |
214 | #define chunksize(p) ((p)->head & ~(FLAG_BITS)) |
215 | 215 | ||
216 | #define clear_pinuse(p) ((p)->head &= ~PINUSE_BIT) |
216 | #define clear_pinuse(p) ((p)->head &= ~PINUSE_BIT) |
217 | 217 | ||
218 | /* Treat space at ptr +/- offset as a chunk */ |
218 | /* Treat space at ptr +/- offset as a chunk */ |
219 | #define chunk_plus_offset(p, s) ((mchunkptr)(((char*)(p)) + (s))) |
219 | #define chunk_plus_offset(p, s) ((mchunkptr)(((char*)(p)) + (s))) |
220 | #define chunk_minus_offset(p, s) ((mchunkptr)(((char*)(p)) - (s))) |
220 | #define chunk_minus_offset(p, s) ((mchunkptr)(((char*)(p)) - (s))) |
221 | 221 | ||
222 | /* Ptr to next or previous physical malloc_chunk. */ |
222 | /* Ptr to next or previous physical malloc_chunk. */ |
223 | #define next_chunk(p) ((mchunkptr)( ((char*)(p)) + ((p)->head & ~FLAG_BITS))) |
223 | #define next_chunk(p) ((mchunkptr)( ((char*)(p)) + ((p)->head & ~FLAG_BITS))) |
224 | #define prev_chunk(p) ((mchunkptr)( ((char*)(p)) - ((p)->prev_foot) )) |
224 | #define prev_chunk(p) ((mchunkptr)( ((char*)(p)) - ((p)->prev_foot) )) |
225 | 225 | ||
226 | /* extract next chunk's pinuse bit */ |
226 | /* extract next chunk's pinuse bit */ |
227 | #define next_pinuse(p) ((next_chunk(p)->head) & PINUSE_BIT) |
227 | #define next_pinuse(p) ((next_chunk(p)->head) & PINUSE_BIT) |
228 | 228 | ||
229 | /* Set size, pinuse bit, and foot */ |
229 | /* Set size, pinuse bit, and foot */ |
230 | #define set_size_and_pinuse_of_free_chunk(p, s)\ |
230 | #define set_size_and_pinuse_of_free_chunk(p, s)\ |
231 | ((p)->head = (s|PINUSE_BIT), set_foot(p, s)) |
231 | ((p)->head = (s|PINUSE_BIT), set_foot(p, s)) |
232 | 232 | ||
233 | /* Set size, pinuse bit, foot, and clear next pinuse */ |
233 | /* Set size, pinuse bit, foot, and clear next pinuse */ |
234 | #define set_free_with_pinuse(p, s, n)\ |
234 | #define set_free_with_pinuse(p, s, n)\ |
235 | (clear_pinuse(n), set_size_and_pinuse_of_free_chunk(p, s)) |
235 | (clear_pinuse(n), set_size_and_pinuse_of_free_chunk(p, s)) |
236 | 236 | ||
237 | /* Get the internal overhead associated with chunk p */ |
237 | /* Get the internal overhead associated with chunk p */ |
238 | #define overhead_for(p)\ |
238 | #define overhead_for(p)\ |
239 | (is_mmapped(p)? MMAP_CHUNK_OVERHEAD : CHUNK_OVERHEAD) |
239 | (is_mmapped(p)? MMAP_CHUNK_OVERHEAD : CHUNK_OVERHEAD) |
240 | 240 | ||
241 | 241 | ||
242 | struct malloc_tree_chunk { |
242 | struct malloc_tree_chunk { |
243 | /* The first four fields must be compatible with malloc_chunk */ |
243 | /* The first four fields must be compatible with malloc_chunk */ |
244 | size_t prev_foot; |
244 | size_t prev_foot; |
245 | size_t head; |
245 | size_t head; |
246 | struct malloc_tree_chunk* fd; |
246 | struct malloc_tree_chunk* fd; |
247 | struct malloc_tree_chunk* bk; |
247 | struct malloc_tree_chunk* bk; |
248 | 248 | ||
249 | struct malloc_tree_chunk* child[2]; |
249 | struct malloc_tree_chunk* child[2]; |
250 | struct malloc_tree_chunk* parent; |
250 | struct malloc_tree_chunk* parent; |
251 | bindex_t index; |
251 | bindex_t index; |
252 | }; |
252 | }; |
253 | 253 | ||
254 | typedef struct malloc_tree_chunk tchunk; |
254 | typedef struct malloc_tree_chunk tchunk; |
255 | typedef struct malloc_tree_chunk* tchunkptr; |
255 | typedef struct malloc_tree_chunk* tchunkptr; |
256 | typedef struct malloc_tree_chunk* tbinptr; /* The type of bins of trees */ |
256 | typedef struct malloc_tree_chunk* tbinptr; /* The type of bins of trees */ |
257 | 257 | ||
258 | /* A little helper macro for trees */ |
258 | /* A little helper macro for trees */ |
259 | #define leftmost_child(t) ((t)->child[0] != 0? (t)->child[0] : (t)->child[1]) |
259 | #define leftmost_child(t) ((t)->child[0] != 0? (t)->child[0] : (t)->child[1]) |
260 | 260 | ||
261 | 261 | ||
262 | struct malloc_segment { |
262 | struct malloc_segment { |
263 | char* base; /* base address */ |
263 | char* base; /* base address */ |
264 | size_t size; /* allocated size */ |
264 | size_t size; /* allocated size */ |
265 | struct malloc_segment* next; /* ptr to next segment */ |
265 | struct malloc_segment* next; /* ptr to next segment */ |
266 | flag_t sflags; /* mmap and extern flag */ |
266 | flag_t sflags; /* mmap and extern flag */ |
267 | }; |
267 | }; |
268 | 268 | ||
269 | #define is_mmapped_segment(S) ((S)->sflags & USE_MMAP_BIT) |
269 | #define is_mmapped_segment(S) ((S)->sflags & USE_MMAP_BIT) |
270 | #define is_extern_segment(S) ((S)->sflags & EXTERN_BIT) |
270 | #define is_extern_segment(S) ((S)->sflags & EXTERN_BIT) |
271 | 271 | ||
272 | typedef struct malloc_segment msegment; |
272 | typedef struct malloc_segment msegment; |
273 | typedef struct malloc_segment* msegmentptr; |
273 | typedef struct malloc_segment* msegmentptr; |
274 | 274 | ||
275 | /* ---------------------------- malloc_state ----------------------------- */ |
275 | /* ---------------------------- malloc_state ----------------------------- */ |
276 | 276 | ||
277 | /* |
277 | /* |
278 | A malloc_state holds all of the bookkeeping for a space. |
278 | A malloc_state holds all of the bookkeeping for a space. |
279 | The main fields are: |
279 | The main fields are: |
280 | 280 | ||
281 | Top |
281 | Top |
282 | The topmost chunk of the currently active segment. Its size is |
282 | The topmost chunk of the currently active segment. Its size is |
283 | cached in topsize. The actual size of topmost space is |
283 | cached in topsize. The actual size of topmost space is |
284 | topsize+TOP_FOOT_SIZE, which includes space reserved for adding |
284 | topsize+TOP_FOOT_SIZE, which includes space reserved for adding |
285 | fenceposts and segment records if necessary when getting more |
285 | fenceposts and segment records if necessary when getting more |
286 | space from the system. The size at which to autotrim top is |
286 | space from the system. The size at which to autotrim top is |
287 | cached from mparams in trim_check, except that it is disabled if |
287 | cached from mparams in trim_check, except that it is disabled if |
288 | an autotrim fails. |
288 | an autotrim fails. |
289 | 289 | ||
290 | Designated victim (dv) |
290 | Designated victim (dv) |
291 | This is the preferred chunk for servicing small requests that |
291 | This is the preferred chunk for servicing small requests that |
292 | don't have exact fits. It is normally the chunk split off most |
292 | don't have exact fits. It is normally the chunk split off most |
293 | recently to service another small request. Its size is cached in |
293 | recently to service another small request. Its size is cached in |
294 | dvsize. The link fields of this chunk are not maintained since it |
294 | dvsize. The link fields of this chunk are not maintained since it |
295 | is not kept in a bin. |
295 | is not kept in a bin. |
296 | 296 | ||
297 | SmallBins |
297 | SmallBins |
298 | An array of bin headers for free chunks. These bins hold chunks |
298 | An array of bin headers for free chunks. These bins hold chunks |
299 | with sizes less than MIN_LARGE_SIZE bytes. Each bin contains |
299 | with sizes less than MIN_LARGE_SIZE bytes. Each bin contains |
300 | chunks of all the same size, spaced 8 bytes apart. To simplify |
300 | chunks of all the same size, spaced 8 bytes apart. To simplify |
301 | use in double-linked lists, each bin header acts as a malloc_chunk |
301 | use in double-linked lists, each bin header acts as a malloc_chunk |
302 | pointing to the real first node, if it exists (else pointing to |
302 | pointing to the real first node, if it exists (else pointing to |
303 | itself). This avoids special-casing for headers. But to avoid |
303 | itself). This avoids special-casing for headers. But to avoid |
304 | waste, we allocate only the fd/bk pointers of bins, and then use |
304 | waste, we allocate only the fd/bk pointers of bins, and then use |
305 | repositioning tricks to treat these as the fields of a chunk. |
305 | repositioning tricks to treat these as the fields of a chunk. |
306 | 306 | ||
307 | TreeBins |
307 | TreeBins |
308 | Treebins are pointers to the roots of trees holding a range of |
308 | Treebins are pointers to the roots of trees holding a range of |
309 | sizes. There are 2 equally spaced treebins for each power of two |
309 | sizes. There are 2 equally spaced treebins for each power of two |
310 | from TREE_SHIFT to TREE_SHIFT+16. The last bin holds anything |
310 | from TREE_SHIFT to TREE_SHIFT+16. The last bin holds anything |
311 | larger. |
311 | larger. |
312 | 312 | ||
313 | Bin maps |
313 | Bin maps |
314 | There is one bit map for small bins ("smallmap") and one for |
314 | There is one bit map for small bins ("smallmap") and one for |
315 | treebins ("treemap). Each bin sets its bit when non-empty, and |
315 | treebins ("treemap). Each bin sets its bit when non-empty, and |
316 | clears the bit when empty. Bit operations are then used to avoid |
316 | clears the bit when empty. Bit operations are then used to avoid |
317 | bin-by-bin searching -- nearly all "search" is done without ever |
317 | bin-by-bin searching -- nearly all "search" is done without ever |
318 | looking at bins that won't be selected. The bit maps |
318 | looking at bins that won't be selected. The bit maps |
319 | conservatively use 32 bits per map word, even if on 64bit system. |
319 | conservatively use 32 bits per map word, even if on 64bit system. |
320 | For a good description of some of the bit-based techniques used |
320 | For a good description of some of the bit-based techniques used |
321 | here, see Henry S. Warren Jr's book "Hacker's Delight" (and |
321 | here, see Henry S. Warren Jr's book "Hacker's Delight" (and |
322 | supplement at http://hackersdelight.org/). Many of these are |
322 | supplement at http://hackersdelight.org/). Many of these are |
323 | intended to reduce the branchiness of paths through malloc etc, as |
323 | intended to reduce the branchiness of paths through malloc etc, as |
324 | well as to reduce the number of memory locations read or written. |
324 | well as to reduce the number of memory locations read or written. |
325 | 325 | ||
326 | Segments |
326 | Segments |
327 | A list of segments headed by an embedded malloc_segment record |
327 | A list of segments headed by an embedded malloc_segment record |
328 | representing the initial space. |
328 | representing the initial space. |
329 | 329 | ||
330 | Address check support |
330 | Address check support |
331 | The least_addr field is the least address ever obtained from |
331 | The least_addr field is the least address ever obtained from |
332 | MORECORE or MMAP. Attempted frees and reallocs of any address less |
332 | MORECORE or MMAP. Attempted frees and reallocs of any address less |
333 | than this are trapped (unless INSECURE is defined). |
333 | than this are trapped (unless INSECURE is defined). |
334 | 334 | ||
335 | Magic tag |
335 | Magic tag |
336 | A cross-check field that should always hold same value as mparams.magic. |
336 | A cross-check field that should always hold same value as mparams.magic. |
337 | 337 | ||
338 | Flags |
338 | Flags |
339 | Bits recording whether to use MMAP, locks, or contiguous MORECORE |
339 | Bits recording whether to use MMAP, locks, or contiguous MORECORE |
340 | 340 | ||
341 | Statistics |
341 | Statistics |
342 | Each space keeps track of current and maximum system memory |
342 | Each space keeps track of current and maximum system memory |
343 | obtained via MORECORE or MMAP. |
343 | obtained via MORECORE or MMAP. |
344 | 344 | ||
345 | Trim support |
345 | Trim support |
346 | Fields holding the amount of unused topmost memory that should trigger |
346 | Fields holding the amount of unused topmost memory that should trigger |
347 | timming, and a counter to force periodic scanning to release unused |
347 | timming, and a counter to force periodic scanning to release unused |
348 | non-topmost segments. |
348 | non-topmost segments. |
349 | 349 | ||
350 | Locking |
350 | Locking |
351 | If USE_LOCKS is defined, the "mutex" lock is acquired and released |
351 | If USE_LOCKS is defined, the "mutex" lock is acquired and released |
352 | around every public call using this mspace. |
352 | around every public call using this mspace. |
353 | 353 | ||
354 | Extension support |
354 | Extension support |
355 | A void* pointer and a size_t field that can be used to help implement |
355 | A void* pointer and a size_t field that can be used to help implement |
356 | extensions to this malloc. |
356 | extensions to this malloc. |
357 | */ |
357 | */ |
358 | 358 | ||
359 | /* Bin types, widths and sizes */ |
359 | /* Bin types, widths and sizes */ |
360 | #define NSMALLBINS (32U) |
360 | #define NSMALLBINS (32U) |
361 | #define NTREEBINS (32U) |
361 | #define NTREEBINS (32U) |
362 | #define SMALLBIN_SHIFT (3U) |
362 | #define SMALLBIN_SHIFT (3U) |
363 | #define SMALLBIN_WIDTH (SIZE_T_ONE << SMALLBIN_SHIFT) |
363 | #define SMALLBIN_WIDTH (SIZE_T_ONE << SMALLBIN_SHIFT) |
364 | #define TREEBIN_SHIFT (8U) |
364 | #define TREEBIN_SHIFT (8U) |
365 | #define MIN_LARGE_SIZE (SIZE_T_ONE << TREEBIN_SHIFT) |
365 | #define MIN_LARGE_SIZE (SIZE_T_ONE << TREEBIN_SHIFT) |
366 | #define MAX_SMALL_SIZE (MIN_LARGE_SIZE - SIZE_T_ONE) |
366 | #define MAX_SMALL_SIZE (MIN_LARGE_SIZE - SIZE_T_ONE) |
367 | #define MAX_SMALL_REQUEST (MAX_SMALL_SIZE - CHUNK_ALIGN_MASK - CHUNK_OVERHEAD) |
367 | #define MAX_SMALL_REQUEST (MAX_SMALL_SIZE - CHUNK_ALIGN_MASK - CHUNK_OVERHEAD) |
368 | 368 | ||
369 | struct malloc_state { |
369 | struct malloc_state { |
370 | binmap_t smallmap; |
370 | binmap_t smallmap; |
371 | binmap_t treemap; |
371 | binmap_t treemap; |
372 | size_t dvsize; |
372 | size_t dvsize; |
373 | size_t topsize; |
373 | size_t topsize; |
374 | char* least_addr; |
374 | char* least_addr; |
375 | mchunkptr dv; |
375 | mchunkptr dv; |
376 | mchunkptr top; |
376 | mchunkptr top; |
377 | size_t trim_check; |
377 | size_t trim_check; |
378 | size_t release_checks; |
378 | size_t release_checks; |
379 | size_t magic; |
379 | size_t magic; |
380 | mchunkptr smallbins[(NSMALLBINS+1)*2]; |
380 | mchunkptr smallbins[(NSMALLBINS+1)*2]; |
381 | tbinptr treebins[NTREEBINS]; |
381 | tbinptr treebins[NTREEBINS]; |
382 | size_t footprint; |
382 | size_t footprint; |
383 | size_t max_footprint; |
383 | size_t max_footprint; |
384 | flag_t mflags; |
384 | flag_t mflags; |
385 | __libc_lock_recursive_t lock; /* locate lock among fields that rarely change */ |
385 | _LOCK_RECURSIVE_T lock; /* locate lock among fields that rarely change */ |
386 | msegment seg; |
386 | msegment seg; |
387 | void* extp; /* Unused but available for extensions */ |
387 | void* extp; /* Unused but available for extensions */ |
388 | size_t exts; |
388 | size_t exts; |
389 | }; |
389 | }; |
390 | 390 | ||
391 | typedef struct malloc_state* mstate; |
391 | typedef struct malloc_state* mstate; |
392 | 392 | ||
393 | /* ------------- Global malloc_state and malloc_params ------------------- */ |
393 | /* ------------- Global malloc_state and malloc_params ------------------- */ |
394 | 394 | ||
395 | /* |
395 | /* |
396 | malloc_params holds global properties, including those that can be |
396 | malloc_params holds global properties, including those that can be |
397 | dynamically set using mallopt. There is a single instance, mparams, |
397 | dynamically set using mallopt. There is a single instance, mparams, |
398 | initialized in init_mparams. Note that the non-zeroness of "magic" |
398 | initialized in init_mparams. Note that the non-zeroness of "magic" |
399 | also serves as an initialization flag. |
399 | also serves as an initialization flag. |
400 | */ |
400 | */ |
401 | 401 | ||
402 | struct malloc_params |
402 | struct malloc_params |
403 | { |
403 | { |
404 | volatile size_t magic; |
404 | volatile size_t magic; |
405 | size_t page_size; |
405 | size_t page_size; |
406 | size_t granularity; |
406 | size_t granularity; |
407 | size_t mmap_threshold; |
407 | size_t mmap_threshold; |
408 | size_t trim_threshold; |
408 | size_t trim_threshold; |
409 | flag_t default_mflags; |
409 | flag_t default_mflags; |
410 | }; |
410 | }; |
411 | 411 | ||
412 | static struct malloc_params mparams; |
412 | static struct malloc_params mparams; |
413 | 413 | ||
414 | /* Ensure mparams initialized */ |
414 | /* Ensure mparams initialized */ |
415 | #define ensure_initialization() (void)(mparams.magic != 0 || init_mparams()) |
415 | #define ensure_initialization() (void)(mparams.magic != 0 || init_mparams()) |
416 | 416 | ||
417 | static struct malloc_state _gm_; |
417 | static struct malloc_state _gm_; |
418 | #define gm (&_gm_) |
418 | #define gm (&_gm_) |
419 | #define is_global(M) ((M) == &_gm_) |
419 | #define is_global(M) ((M) == &_gm_) |
420 | 420 | ||
421 | #define is_initialized(M) ((M)->top != 0) |
421 | #define is_initialized(M) ((M)->top != 0) |
422 | 422 | ||
423 | 423 | ||
424 | 424 | ||
425 | 425 | ||
426 | __LOCK_INIT_RECURSIVE(static, malloc_global_mutex); |
426 | __LOCK_INIT_RECURSIVE(static, malloc_global_mutex); |
427 | 427 | ||
428 | #define ACQUIRE_MALLOC_GLOBAL_LOCK() __libc_lock_lock_recursive(malloc_global_mutex); |
428 | #define ACQUIRE_MALLOC_GLOBAL_LOCK() __lock_acquire_recursive(malloc_global_mutex); |
429 | #define RELEASE_MALLOC_GLOBAL_LOCK() __libc_lock_unlock_recursive(malloc_global_mutex); |
429 | #define RELEASE_MALLOC_GLOBAL_LOCK() __lock_release_recursive(malloc_global_mutex); |
430 | 430 | ||
431 | #define PREACTION(M) ( __libc_lock_lock_recursive((M)->lock)) |
431 | #define PREACTION(M) ( __lock_acquire_recursive((M)->lock)) |
432 | #define POSTACTION(M) { __libc_lock_unlock_recursive((M)->lock); } |
432 | #define POSTACTION(M) { __lock_release_recursive((M)->lock); } |
433 | 433 | ||
434 | /* ---------------------------- Indexing Bins ---------------------------- */ |
434 | /* ---------------------------- Indexing Bins ---------------------------- */ |
435 | 435 | ||
436 | #define is_small(s) (((s) >> SMALLBIN_SHIFT) < NSMALLBINS) |
436 | #define is_small(s) (((s) >> SMALLBIN_SHIFT) < NSMALLBINS) |
437 | #define small_index(s) ((s) >> SMALLBIN_SHIFT) |
437 | #define small_index(s) ((s) >> SMALLBIN_SHIFT) |
438 | #define small_index2size(i) ((i) << SMALLBIN_SHIFT) |
438 | #define small_index2size(i) ((i) << SMALLBIN_SHIFT) |
439 | #define MIN_SMALL_INDEX (small_index(MIN_CHUNK_SIZE)) |
439 | #define MIN_SMALL_INDEX (small_index(MIN_CHUNK_SIZE)) |
440 | 440 | ||
441 | /* addressing by index. See above about smallbin repositioning */ |
441 | /* addressing by index. See above about smallbin repositioning */ |
442 | #define smallbin_at(M, i) ((sbinptr)((char*)&((M)->smallbins[(i)<<1]))) |
442 | #define smallbin_at(M, i) ((sbinptr)((char*)&((M)->smallbins[(i)<<1]))) |
443 | #define treebin_at(M,i) (&((M)->treebins[i])) |
443 | #define treebin_at(M,i) (&((M)->treebins[i])) |
444 | 444 | ||
445 | 445 | ||
446 | #define compute_tree_index(S, I)\ |
446 | #define compute_tree_index(S, I)\ |
447 | {\ |
447 | {\ |
448 | unsigned int X = S >> TREEBIN_SHIFT;\ |
448 | unsigned int X = S >> TREEBIN_SHIFT;\ |
449 | if (X == 0)\ |
449 | if (X == 0)\ |
450 | I = 0;\ |
450 | I = 0;\ |
451 | else if (X > 0xFFFF)\ |
451 | else if (X > 0xFFFF)\ |
452 | I = NTREEBINS-1;\ |
452 | I = NTREEBINS-1;\ |
453 | else {\ |
453 | else {\ |
454 | unsigned int K;\ |
454 | unsigned int K;\ |
455 | __asm__("bsrl\t%1, %0\n\t" : "=r" (K) : "g" (X));\ |
455 | __asm__("bsrl\t%1, %0\n\t" : "=r" (K) : "g" (X));\ |
456 | I = (bindex_t)((K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1)));\ |
456 | I = (bindex_t)((K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1)));\ |
457 | }\ |
457 | }\ |
458 | } |
458 | } |
459 | 459 | ||
460 | /* Bit representing maximum resolved size in a treebin at i */ |
460 | /* Bit representing maximum resolved size in a treebin at i */ |
461 | #define bit_for_tree_index(i) \ |
461 | #define bit_for_tree_index(i) \ |
462 | (i == NTREEBINS-1)? (SIZE_T_BITSIZE-1) : (((i) >> 1) + TREEBIN_SHIFT - 2) |
462 | (i == NTREEBINS-1)? (SIZE_T_BITSIZE-1) : (((i) >> 1) + TREEBIN_SHIFT - 2) |
463 | 463 | ||
464 | /* Shift placing maximum resolved bit in a treebin at i as sign bit */ |
464 | /* Shift placing maximum resolved bit in a treebin at i as sign bit */ |
465 | #define leftshift_for_tree_index(i) \ |
465 | #define leftshift_for_tree_index(i) \ |
466 | ((i == NTREEBINS-1)? 0 : \ |
466 | ((i == NTREEBINS-1)? 0 : \ |
467 | ((SIZE_T_BITSIZE-SIZE_T_ONE) - (((i) >> 1) + TREEBIN_SHIFT - 2))) |
467 | ((SIZE_T_BITSIZE-SIZE_T_ONE) - (((i) >> 1) + TREEBIN_SHIFT - 2))) |
468 | 468 | ||
469 | /* The size of the smallest chunk held in bin with index i */ |
469 | /* The size of the smallest chunk held in bin with index i */ |
470 | #define minsize_for_tree_index(i) \ |
470 | #define minsize_for_tree_index(i) \ |
471 | ((SIZE_T_ONE << (((i) >> 1) + TREEBIN_SHIFT)) | \ |
471 | ((SIZE_T_ONE << (((i) >> 1) + TREEBIN_SHIFT)) | \ |
472 | (((size_t)((i) & SIZE_T_ONE)) << (((i) >> 1) + TREEBIN_SHIFT - 1))) |
472 | (((size_t)((i) & SIZE_T_ONE)) << (((i) >> 1) + TREEBIN_SHIFT - 1))) |
473 | 473 | ||
474 | 474 | ||
475 | /* ------------------------ Operations on bin maps ----------------------- */ |
475 | /* ------------------------ Operations on bin maps ----------------------- */ |
476 | 476 | ||
477 | /* bit corresponding to given index */ |
477 | /* bit corresponding to given index */ |
478 | #define idx2bit(i) ((binmap_t)(1) << (i)) |
478 | #define idx2bit(i) ((binmap_t)(1) << (i)) |
479 | 479 | ||
480 | /* Mark/Clear bits with given index */ |
480 | /* Mark/Clear bits with given index */ |
481 | #define mark_smallmap(M,i) ((M)->smallmap |= idx2bit(i)) |
481 | #define mark_smallmap(M,i) ((M)->smallmap |= idx2bit(i)) |
482 | #define clear_smallmap(M,i) ((M)->smallmap &= ~idx2bit(i)) |
482 | #define clear_smallmap(M,i) ((M)->smallmap &= ~idx2bit(i)) |
483 | #define smallmap_is_marked(M,i) ((M)->smallmap & idx2bit(i)) |
483 | #define smallmap_is_marked(M,i) ((M)->smallmap & idx2bit(i)) |
484 | 484 | ||
485 | #define mark_treemap(M,i) ((M)->treemap |= idx2bit(i)) |
485 | #define mark_treemap(M,i) ((M)->treemap |= idx2bit(i)) |
486 | #define clear_treemap(M,i) ((M)->treemap &= ~idx2bit(i)) |
486 | #define clear_treemap(M,i) ((M)->treemap &= ~idx2bit(i)) |
487 | #define treemap_is_marked(M,i) ((M)->treemap & idx2bit(i)) |
487 | #define treemap_is_marked(M,i) ((M)->treemap & idx2bit(i)) |
488 | 488 | ||
489 | /* isolate the least set bit of a bitmap */ |
489 | /* isolate the least set bit of a bitmap */ |
490 | #define least_bit(x) ((x) & -(x)) |
490 | #define least_bit(x) ((x) & -(x)) |
491 | 491 | ||
492 | /* mask with all bits to left of least bit of x on */ |
492 | /* mask with all bits to left of least bit of x on */ |
493 | #define left_bits(x) ((x<<1) | -(x<<1)) |
493 | #define left_bits(x) ((x<<1) | -(x<<1)) |
494 | 494 | ||
495 | /* mask with all bits to left of or equal to least bit of x on */ |
495 | /* mask with all bits to left of or equal to least bit of x on */ |
496 | #define same_or_left_bits(x) ((x) | -(x)) |
496 | #define same_or_left_bits(x) ((x) | -(x)) |
497 | 497 | ||
498 | 498 | ||
499 | /* index corresponding to given bit. Use x86 asm if possible */ |
499 | /* index corresponding to given bit. Use x86 asm if possible */ |
500 | 500 | ||
501 | #define compute_bit2idx(X, I)\ |
501 | #define compute_bit2idx(X, I)\ |
502 | {\ |
502 | {\ |
503 | unsigned int J;\ |
503 | unsigned int J;\ |
504 | __asm__("bsfl\t%1, %0\n\t" : "=r" (J) : "g" (X));\ |
504 | __asm__("bsfl\t%1, %0\n\t" : "=r" (J) : "g" (X));\ |
505 | I = (bindex_t)J;\ |
505 | I = (bindex_t)J;\ |
506 | } |
506 | } |
507 | 507 | ||
508 | 508 | ||
509 | #define mark_inuse_foot(M,p,s) |
509 | #define mark_inuse_foot(M,p,s) |
510 | 510 | ||
511 | /* Get/set size at footer */ |
511 | /* Get/set size at footer */ |
512 | #define get_foot(p, s) (((mchunkptr)((char*)(p) + (s)))->prev_foot) |
512 | #define get_foot(p, s) (((mchunkptr)((char*)(p) + (s)))->prev_foot) |
513 | #define set_foot(p, s) (((mchunkptr)((char*)(p) + (s)))->prev_foot = (s)) |
513 | #define set_foot(p, s) (((mchunkptr)((char*)(p) + (s)))->prev_foot = (s)) |
514 | 514 | ||
515 | /* Macros for setting head/foot of non-mmapped chunks */ |
515 | /* Macros for setting head/foot of non-mmapped chunks */ |
516 | 516 | ||
517 | /* Set cinuse bit and pinuse bit of next chunk */ |
517 | /* Set cinuse bit and pinuse bit of next chunk */ |
518 | #define set_inuse(M,p,s)\ |
518 | #define set_inuse(M,p,s)\ |
519 | ((p)->head = (((p)->head & PINUSE_BIT)|s|CINUSE_BIT),\ |
519 | ((p)->head = (((p)->head & PINUSE_BIT)|s|CINUSE_BIT),\ |
520 | ((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT) |
520 | ((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT) |
521 | 521 | ||
522 | /* Set cinuse and pinuse of this chunk and pinuse of next chunk */ |
522 | /* Set cinuse and pinuse of this chunk and pinuse of next chunk */ |
523 | #define set_inuse_and_pinuse(M,p,s)\ |
523 | #define set_inuse_and_pinuse(M,p,s)\ |
524 | ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\ |
524 | ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\ |
525 | ((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT) |
525 | ((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT) |
526 | 526 | ||
527 | /* Set size, cinuse and pinuse bit of this chunk */ |
527 | /* Set size, cinuse and pinuse bit of this chunk */ |
528 | #define set_size_and_pinuse_of_inuse_chunk(M, p, s)\ |
528 | #define set_size_and_pinuse_of_inuse_chunk(M, p, s)\ |
529 | ((p)->head = (s|PINUSE_BIT|CINUSE_BIT)) |
529 | ((p)->head = (s|PINUSE_BIT|CINUSE_BIT)) |
530 | 530 | ||
531 | 531 | ||
532 | #define assert(x) |
532 | #define assert(x) |
533 | #define RTCHECK(e) __builtin_expect(e, 1) |
533 | #define RTCHECK(e) __builtin_expect(e, 1) |
534 | 534 | ||
535 | #define check_free_chunk(M,P) |
535 | #define check_free_chunk(M,P) |
536 | #define check_inuse_chunk(M,P) |
536 | #define check_inuse_chunk(M,P) |
537 | #define check_malloced_chunk(M,P,N) |
537 | #define check_malloced_chunk(M,P,N) |
538 | #define check_mmapped_chunk(M,P) |
538 | #define check_mmapped_chunk(M,P) |
539 | #define check_malloc_state(M) |
539 | #define check_malloc_state(M) |
540 | #define check_top_chunk(M,P) |
540 | #define check_top_chunk(M,P) |
541 | 541 | ||
542 | /* Check if address a is at least as high as any from MORECORE or MMAP */ |
542 | /* Check if address a is at least as high as any from MORECORE or MMAP */ |
543 | #define ok_address(M, a) ((char*)(a) >= (M)->least_addr) |
543 | #define ok_address(M, a) ((char*)(a) >= (M)->least_addr) |
544 | /* Check if address of next chunk n is higher than base chunk p */ |
544 | /* Check if address of next chunk n is higher than base chunk p */ |
545 | #define ok_next(p, n) ((char*)(p) < (char*)(n)) |
545 | #define ok_next(p, n) ((char*)(p) < (char*)(n)) |
546 | /* Check if p has inuse status */ |
546 | /* Check if p has inuse status */ |
547 | #define ok_inuse(p) is_inuse(p) |
547 | #define ok_inuse(p) is_inuse(p) |
548 | /* Check if p has its pinuse bit on */ |
548 | /* Check if p has its pinuse bit on */ |
549 | #define ok_pinuse(p) pinuse(p) |
549 | #define ok_pinuse(p) pinuse(p) |
550 | 550 | ||
551 | #define CORRUPTION_ERROR_ACTION(m) \ |
551 | #define CORRUPTION_ERROR_ACTION(m) \ |
552 | do { \ |
552 | do { \ |
553 | /*printf("%s malloc heap corrupted\n",__FUNCTION__); */\ |
553 | /*printf("%s malloc heap corrupted\n",__FUNCTION__); */\ |
554 | __asm__("int3"); \ |
554 | __asm__("int3"); \ |
555 | }while(0) \ |
555 | }while(0) \ |
556 | 556 | ||
557 | 557 | ||
558 | #define USAGE_ERROR_ACTION(m, p) \ |
558 | #define USAGE_ERROR_ACTION(m, p) \ |
559 | do { \ |
559 | do { \ |
560 | /*printf("%s malloc heap corrupted\n",__FUNCTION__); */\ |
560 | /*printf("%s malloc heap corrupted\n",__FUNCTION__); */\ |
561 | __asm__("int3"); \ |
561 | __asm__("int3"); \ |
562 | }while(0) \ |
562 | }while(0) \ |
563 | 563 | ||
564 | /* ----------------------- Operations on smallbins ----------------------- */ |
564 | /* ----------------------- Operations on smallbins ----------------------- */ |
565 | 565 | ||
566 | /* |
566 | /* |
567 | Various forms of linking and unlinking are defined as macros. Even |
567 | Various forms of linking and unlinking are defined as macros. Even |
568 | the ones for trees, which are very long but have very short typical |
568 | the ones for trees, which are very long but have very short typical |
569 | paths. This is ugly but reduces reliance on inlining support of |
569 | paths. This is ugly but reduces reliance on inlining support of |
570 | compilers. |
570 | compilers. |
571 | */ |
571 | */ |
572 | 572 | ||
573 | /* Link a free chunk into a smallbin */ |
573 | /* Link a free chunk into a smallbin */ |
574 | #define insert_small_chunk(M, P, S) {\ |
574 | #define insert_small_chunk(M, P, S) {\ |
575 | bindex_t I = small_index(S);\ |
575 | bindex_t I = small_index(S);\ |
576 | mchunkptr B = smallbin_at(M, I);\ |
576 | mchunkptr B = smallbin_at(M, I);\ |
577 | mchunkptr F = B;\ |
577 | mchunkptr F = B;\ |
578 | assert(S >= MIN_CHUNK_SIZE);\ |
578 | assert(S >= MIN_CHUNK_SIZE);\ |
579 | if (!smallmap_is_marked(M, I))\ |
579 | if (!smallmap_is_marked(M, I))\ |
580 | mark_smallmap(M, I);\ |
580 | mark_smallmap(M, I);\ |
581 | else if (RTCHECK(ok_address(M, B->fd)))\ |
581 | else if (RTCHECK(ok_address(M, B->fd)))\ |
582 | F = B->fd;\ |
582 | F = B->fd;\ |
583 | else {\ |
583 | else {\ |
584 | CORRUPTION_ERROR_ACTION(M);\ |
584 | CORRUPTION_ERROR_ACTION(M);\ |
585 | }\ |
585 | }\ |
586 | B->fd = P;\ |
586 | B->fd = P;\ |
587 | F->bk = P;\ |
587 | F->bk = P;\ |
588 | P->fd = F;\ |
588 | P->fd = F;\ |
589 | P->bk = B;\ |
589 | P->bk = B;\ |
590 | } |
590 | } |
591 | 591 | ||
592 | /* Unlink a chunk from a smallbin */ |
592 | /* Unlink a chunk from a smallbin */ |
593 | #define unlink_small_chunk(M, P, S) {\ |
593 | #define unlink_small_chunk(M, P, S) {\ |
594 | mchunkptr F = P->fd;\ |
594 | mchunkptr F = P->fd;\ |
595 | mchunkptr B = P->bk;\ |
595 | mchunkptr B = P->bk;\ |
596 | bindex_t I = small_index(S);\ |
596 | bindex_t I = small_index(S);\ |
597 | assert(P != B);\ |
597 | assert(P != B);\ |
598 | assert(P != F);\ |
598 | assert(P != F);\ |
599 | assert(chunksize(P) == small_index2size(I));\ |
599 | assert(chunksize(P) == small_index2size(I));\ |
600 | if (F == B)\ |
600 | if (F == B)\ |
601 | clear_smallmap(M, I);\ |
601 | clear_smallmap(M, I);\ |
602 | else if (RTCHECK((F == smallbin_at(M,I) || ok_address(M, F)) &&\ |
602 | else if (RTCHECK((F == smallbin_at(M,I) || ok_address(M, F)) &&\ |
603 | (B == smallbin_at(M,I) || ok_address(M, B)))) {\ |
603 | (B == smallbin_at(M,I) || ok_address(M, B)))) {\ |
604 | F->bk = B;\ |
604 | F->bk = B;\ |
605 | B->fd = F;\ |
605 | B->fd = F;\ |
606 | }\ |
606 | }\ |
607 | else {\ |
607 | else {\ |
608 | CORRUPTION_ERROR_ACTION(M);\ |
608 | CORRUPTION_ERROR_ACTION(M);\ |
609 | }\ |
609 | }\ |
610 | } |
610 | } |
611 | 611 | ||
612 | /* Unlink the first chunk from a smallbin */ |
612 | /* Unlink the first chunk from a smallbin */ |
613 | #define unlink_first_small_chunk(M, B, P, I) {\ |
613 | #define unlink_first_small_chunk(M, B, P, I) {\ |
614 | mchunkptr F = P->fd;\ |
614 | mchunkptr F = P->fd;\ |
615 | assert(P != B);\ |
615 | assert(P != B);\ |
616 | assert(P != F);\ |
616 | assert(P != F);\ |
617 | assert(chunksize(P) == small_index2size(I));\ |
617 | assert(chunksize(P) == small_index2size(I));\ |
618 | if (B == F)\ |
618 | if (B == F)\ |
619 | clear_smallmap(M, I);\ |
619 | clear_smallmap(M, I);\ |
620 | else if (RTCHECK(ok_address(M, F))) {\ |
620 | else if (RTCHECK(ok_address(M, F))) {\ |
621 | B->fd = F;\ |
621 | B->fd = F;\ |
622 | F->bk = B;\ |
622 | F->bk = B;\ |
623 | }\ |
623 | }\ |
624 | else {\ |
624 | else {\ |
625 | CORRUPTION_ERROR_ACTION(M);\ |
625 | CORRUPTION_ERROR_ACTION(M);\ |
626 | }\ |
626 | }\ |
627 | } |
627 | } |
628 | 628 | ||
629 | /* Replace dv node, binning the old one */ |
629 | /* Replace dv node, binning the old one */ |
630 | /* Used only when dvsize known to be small */ |
630 | /* Used only when dvsize known to be small */ |
631 | #define replace_dv(M, P, S) {\ |
631 | #define replace_dv(M, P, S) {\ |
632 | size_t DVS = M->dvsize;\ |
632 | size_t DVS = M->dvsize;\ |
633 | if (DVS != 0) {\ |
633 | if (DVS != 0) {\ |
634 | mchunkptr DV = M->dv;\ |
634 | mchunkptr DV = M->dv;\ |
635 | assert(is_small(DVS));\ |
635 | assert(is_small(DVS));\ |
636 | insert_small_chunk(M, DV, DVS);\ |
636 | insert_small_chunk(M, DV, DVS);\ |
637 | }\ |
637 | }\ |
638 | M->dvsize = S;\ |
638 | M->dvsize = S;\ |
639 | M->dv = P;\ |
639 | M->dv = P;\ |
640 | } |
640 | } |
641 | 641 | ||
642 | 642 | ||
643 | /* ------------------------- Operations on trees ------------------------- */ |
643 | /* ------------------------- Operations on trees ------------------------- */ |
644 | 644 | ||
645 | /* Insert chunk into tree */ |
645 | /* Insert chunk into tree */ |
646 | #define insert_large_chunk(M, X, S) {\ |
646 | #define insert_large_chunk(M, X, S) {\ |
647 | tbinptr* H;\ |
647 | tbinptr* H;\ |
648 | bindex_t I;\ |
648 | bindex_t I;\ |
649 | compute_tree_index(S, I);\ |
649 | compute_tree_index(S, I);\ |
650 | H = treebin_at(M, I);\ |
650 | H = treebin_at(M, I);\ |
651 | X->index = I;\ |
651 | X->index = I;\ |
652 | X->child[0] = X->child[1] = 0;\ |
652 | X->child[0] = X->child[1] = 0;\ |
653 | if (!treemap_is_marked(M, I)) {\ |
653 | if (!treemap_is_marked(M, I)) {\ |
654 | mark_treemap(M, I);\ |
654 | mark_treemap(M, I);\ |
655 | *H = X;\ |
655 | *H = X;\ |
656 | X->parent = (tchunkptr)H;\ |
656 | X->parent = (tchunkptr)H;\ |
657 | X->fd = X->bk = X;\ |
657 | X->fd = X->bk = X;\ |
658 | }\ |
658 | }\ |
659 | else {\ |
659 | else {\ |
660 | tchunkptr T = *H;\ |
660 | tchunkptr T = *H;\ |
661 | size_t K = S << leftshift_for_tree_index(I);\ |
661 | size_t K = S << leftshift_for_tree_index(I);\ |
662 | for (;;) {\ |
662 | for (;;) {\ |
663 | if (chunksize(T) != S) {\ |
663 | if (chunksize(T) != S) {\ |
664 | tchunkptr* C = &(T->child[(K >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1]);\ |
664 | tchunkptr* C = &(T->child[(K >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1]);\ |
665 | K <<= 1;\ |
665 | K <<= 1;\ |
666 | if (*C != 0)\ |
666 | if (*C != 0)\ |
667 | T = *C;\ |
667 | T = *C;\ |
668 | else if (RTCHECK(ok_address(M, C))) {\ |
668 | else if (RTCHECK(ok_address(M, C))) {\ |
669 | *C = X;\ |
669 | *C = X;\ |
670 | X->parent = T;\ |
670 | X->parent = T;\ |
671 | X->fd = X->bk = X;\ |
671 | X->fd = X->bk = X;\ |
672 | break;\ |
672 | break;\ |
673 | }\ |
673 | }\ |
674 | else {\ |
674 | else {\ |
675 | CORRUPTION_ERROR_ACTION(M);\ |
675 | CORRUPTION_ERROR_ACTION(M);\ |
676 | break;\ |
676 | break;\ |
677 | }\ |
677 | }\ |
678 | }\ |
678 | }\ |
679 | else {\ |
679 | else {\ |
680 | tchunkptr F = T->fd;\ |
680 | tchunkptr F = T->fd;\ |
681 | if (RTCHECK(ok_address(M, T) && ok_address(M, F))) {\ |
681 | if (RTCHECK(ok_address(M, T) && ok_address(M, F))) {\ |
682 | T->fd = F->bk = X;\ |
682 | T->fd = F->bk = X;\ |
683 | X->fd = F;\ |
683 | X->fd = F;\ |
684 | X->bk = T;\ |
684 | X->bk = T;\ |
685 | X->parent = 0;\ |
685 | X->parent = 0;\ |
686 | break;\ |
686 | break;\ |
687 | }\ |
687 | }\ |
688 | else {\ |
688 | else {\ |
689 | CORRUPTION_ERROR_ACTION(M);\ |
689 | CORRUPTION_ERROR_ACTION(M);\ |
690 | break;\ |
690 | break;\ |
691 | }\ |
691 | }\ |
692 | }\ |
692 | }\ |
693 | }\ |
693 | }\ |
694 | }\ |
694 | }\ |
695 | } |
695 | } |
696 | 696 | ||
697 | /* |
697 | /* |
698 | Unlink steps: |
698 | Unlink steps: |
699 | 699 | ||
700 | 1. If x is a chained node, unlink it from its same-sized fd/bk links |
700 | 1. If x is a chained node, unlink it from its same-sized fd/bk links |
701 | and choose its bk node as its replacement. |
701 | and choose its bk node as its replacement. |
702 | 2. If x was the last node of its size, but not a leaf node, it must |
702 | 2. If x was the last node of its size, but not a leaf node, it must |
703 | be replaced with a leaf node (not merely one with an open left or |
703 | be replaced with a leaf node (not merely one with an open left or |
704 | right), to make sure that lefts and rights of descendents |
704 | right), to make sure that lefts and rights of descendents |
705 | correspond properly to bit masks. We use the rightmost descendent |
705 | correspond properly to bit masks. We use the rightmost descendent |
706 | of x. We could use any other leaf, but this is easy to locate and |
706 | of x. We could use any other leaf, but this is easy to locate and |
707 | tends to counteract removal of leftmosts elsewhere, and so keeps |
707 | tends to counteract removal of leftmosts elsewhere, and so keeps |
708 | paths shorter than minimally guaranteed. This doesn't loop much |
708 | paths shorter than minimally guaranteed. This doesn't loop much |
709 | because on average a node in a tree is near the bottom. |
709 | because on average a node in a tree is near the bottom. |
710 | 3. If x is the base of a chain (i.e., has parent links) relink |
710 | 3. If x is the base of a chain (i.e., has parent links) relink |
711 | x's parent and children to x's replacement (or null if none). |
711 | x's parent and children to x's replacement (or null if none). |
712 | */ |
712 | */ |
713 | 713 | ||
714 | #define unlink_large_chunk(M, X) {\ |
714 | #define unlink_large_chunk(M, X) {\ |
715 | tchunkptr XP = X->parent;\ |
715 | tchunkptr XP = X->parent;\ |
716 | tchunkptr R;\ |
716 | tchunkptr R;\ |
717 | if (X->bk != X) {\ |
717 | if (X->bk != X) {\ |
718 | tchunkptr F = X->fd;\ |
718 | tchunkptr F = X->fd;\ |
719 | R = X->bk;\ |
719 | R = X->bk;\ |
720 | if (RTCHECK(ok_address(M, F))) {\ |
720 | if (RTCHECK(ok_address(M, F))) {\ |
721 | F->bk = R;\ |
721 | F->bk = R;\ |
722 | R->fd = F;\ |
722 | R->fd = F;\ |
723 | }\ |
723 | }\ |
724 | else {\ |
724 | else {\ |
725 | CORRUPTION_ERROR_ACTION(M);\ |
725 | CORRUPTION_ERROR_ACTION(M);\ |
726 | }\ |
726 | }\ |
727 | }\ |
727 | }\ |
728 | else {\ |
728 | else {\ |
729 | tchunkptr* RP;\ |
729 | tchunkptr* RP;\ |
730 | if (((R = *(RP = &(X->child[1]))) != 0) ||\ |
730 | if (((R = *(RP = &(X->child[1]))) != 0) ||\ |
731 | ((R = *(RP = &(X->child[0]))) != 0)) {\ |
731 | ((R = *(RP = &(X->child[0]))) != 0)) {\ |
732 | tchunkptr* CP;\ |
732 | tchunkptr* CP;\ |
733 | while ((*(CP = &(R->child[1])) != 0) ||\ |
733 | while ((*(CP = &(R->child[1])) != 0) ||\ |
734 | (*(CP = &(R->child[0])) != 0)) {\ |
734 | (*(CP = &(R->child[0])) != 0)) {\ |
735 | R = *(RP = CP);\ |
735 | R = *(RP = CP);\ |
736 | }\ |
736 | }\ |
737 | if (RTCHECK(ok_address(M, RP)))\ |
737 | if (RTCHECK(ok_address(M, RP)))\ |
738 | *RP = 0;\ |
738 | *RP = 0;\ |
739 | else {\ |
739 | else {\ |
740 | CORRUPTION_ERROR_ACTION(M);\ |
740 | CORRUPTION_ERROR_ACTION(M);\ |
741 | }\ |
741 | }\ |
742 | }\ |
742 | }\ |
743 | }\ |
743 | }\ |
744 | if (XP != 0) {\ |
744 | if (XP != 0) {\ |
745 | tbinptr* H = treebin_at(M, X->index);\ |
745 | tbinptr* H = treebin_at(M, X->index);\ |
746 | if (X == *H) {\ |
746 | if (X == *H) {\ |
747 | if ((*H = R) == 0) \ |
747 | if ((*H = R) == 0) \ |
748 | clear_treemap(M, X->index);\ |
748 | clear_treemap(M, X->index);\ |
749 | }\ |
749 | }\ |
750 | else if (RTCHECK(ok_address(M, XP))) {\ |
750 | else if (RTCHECK(ok_address(M, XP))) {\ |
751 | if (XP->child[0] == X) \ |
751 | if (XP->child[0] == X) \ |
752 | XP->child[0] = R;\ |
752 | XP->child[0] = R;\ |
753 | else \ |
753 | else \ |
754 | XP->child[1] = R;\ |
754 | XP->child[1] = R;\ |
755 | }\ |
755 | }\ |
756 | else\ |
756 | else\ |
757 | CORRUPTION_ERROR_ACTION(M);\ |
757 | CORRUPTION_ERROR_ACTION(M);\ |
758 | if (R != 0) {\ |
758 | if (R != 0) {\ |
759 | if (RTCHECK(ok_address(M, R))) {\ |
759 | if (RTCHECK(ok_address(M, R))) {\ |
760 | tchunkptr C0, C1;\ |
760 | tchunkptr C0, C1;\ |
761 | R->parent = XP;\ |
761 | R->parent = XP;\ |
762 | if ((C0 = X->child[0]) != 0) {\ |
762 | if ((C0 = X->child[0]) != 0) {\ |
763 | if (RTCHECK(ok_address(M, C0))) {\ |
763 | if (RTCHECK(ok_address(M, C0))) {\ |
764 | R->child[0] = C0;\ |
764 | R->child[0] = C0;\ |
765 | C0->parent = R;\ |
765 | C0->parent = R;\ |
766 | }\ |
766 | }\ |
767 | else\ |
767 | else\ |
768 | CORRUPTION_ERROR_ACTION(M);\ |
768 | CORRUPTION_ERROR_ACTION(M);\ |
769 | }\ |
769 | }\ |
770 | if ((C1 = X->child[1]) != 0) {\ |
770 | if ((C1 = X->child[1]) != 0) {\ |
771 | if (RTCHECK(ok_address(M, C1))) {\ |
771 | if (RTCHECK(ok_address(M, C1))) {\ |
772 | R->child[1] = C1;\ |
772 | R->child[1] = C1;\ |
773 | C1->parent = R;\ |
773 | C1->parent = R;\ |
774 | }\ |
774 | }\ |
775 | else\ |
775 | else\ |
776 | CORRUPTION_ERROR_ACTION(M);\ |
776 | CORRUPTION_ERROR_ACTION(M);\ |
777 | }\ |
777 | }\ |
778 | }\ |
778 | }\ |
779 | else\ |
779 | else\ |
780 | CORRUPTION_ERROR_ACTION(M);\ |
780 | CORRUPTION_ERROR_ACTION(M);\ |
781 | }\ |
781 | }\ |
782 | }\ |
782 | }\ |
783 | } |
783 | } |
784 | 784 | ||
785 | /* Relays to large vs small bin operations */ |
785 | /* Relays to large vs small bin operations */ |
786 | 786 | ||
787 | #define insert_chunk(M, P, S)\ |
787 | #define insert_chunk(M, P, S)\ |
788 | if (is_small(S)) insert_small_chunk(M, P, S)\ |
788 | if (is_small(S)) insert_small_chunk(M, P, S)\ |
789 | else { tchunkptr TP = (tchunkptr)(P); insert_large_chunk(M, TP, S); } |
789 | else { tchunkptr TP = (tchunkptr)(P); insert_large_chunk(M, TP, S); } |
790 | 790 | ||
791 | #define unlink_chunk(M, P, S)\ |
791 | #define unlink_chunk(M, P, S)\ |
792 | if (is_small(S)) unlink_small_chunk(M, P, S)\ |
792 | if (is_small(S)) unlink_small_chunk(M, P, S)\ |
793 | else { tchunkptr TP = (tchunkptr)(P); unlink_large_chunk(M, TP); } |
793 | else { tchunkptr TP = (tchunkptr)(P); unlink_large_chunk(M, TP); } |
794 | 794 | ||
795 | 795 | ||
796 | /* -------------------------- system alloc setup ------------------------- */ |
796 | /* -------------------------- system alloc setup ------------------------- */ |
797 | 797 | ||
798 | /* Operations on mflags */ |
798 | /* Operations on mflags */ |
799 | 799 | ||
800 | #define use_lock(M) ((M)->mflags & USE_LOCK_BIT) |
800 | #define use_lock(M) ((M)->mflags & USE_LOCK_BIT) |
801 | #define enable_lock(M) ((M)->mflags |= USE_LOCK_BIT) |
801 | #define enable_lock(M) ((M)->mflags |= USE_LOCK_BIT) |
802 | #define disable_lock(M) ((M)->mflags &= ~USE_LOCK_BIT) |
802 | #define disable_lock(M) ((M)->mflags &= ~USE_LOCK_BIT) |
803 | 803 | ||
804 | #define use_mmap(M) ((M)->mflags & USE_MMAP_BIT) |
804 | #define use_mmap(M) ((M)->mflags & USE_MMAP_BIT) |
805 | #define enable_mmap(M) ((M)->mflags |= USE_MMAP_BIT) |
805 | #define enable_mmap(M) ((M)->mflags |= USE_MMAP_BIT) |
806 | #define disable_mmap(M) ((M)->mflags &= ~USE_MMAP_BIT) |
806 | #define disable_mmap(M) ((M)->mflags &= ~USE_MMAP_BIT) |
807 | 807 | ||
808 | #define use_noncontiguous(M) ((M)->mflags & USE_NONCONTIGUOUS_BIT) |
808 | #define use_noncontiguous(M) ((M)->mflags & USE_NONCONTIGUOUS_BIT) |
809 | #define disable_contiguous(M) ((M)->mflags |= USE_NONCONTIGUOUS_BIT) |
809 | #define disable_contiguous(M) ((M)->mflags |= USE_NONCONTIGUOUS_BIT) |
810 | 810 | ||
811 | #define set_lock(M,L)\ |
811 | #define set_lock(M,L)\ |
812 | ((M)->mflags = (L)?\ |
812 | ((M)->mflags = (L)?\ |
813 | ((M)->mflags | USE_LOCK_BIT) :\ |
813 | ((M)->mflags | USE_LOCK_BIT) :\ |
814 | ((M)->mflags & ~USE_LOCK_BIT)) |
814 | ((M)->mflags & ~USE_LOCK_BIT)) |
815 | 815 | ||
816 | /* page-align a size */ |
816 | /* page-align a size */ |
817 | #define page_align(S)\ |
817 | #define page_align(S)\ |
818 | (((S) + (mparams.page_size - SIZE_T_ONE)) & ~(mparams.page_size - SIZE_T_ONE)) |
818 | (((S) + (mparams.page_size - SIZE_T_ONE)) & ~(mparams.page_size - SIZE_T_ONE)) |
819 | 819 | ||
820 | /* granularity-align a size */ |
820 | /* granularity-align a size */ |
821 | #define granularity_align(S)\ |
821 | #define granularity_align(S)\ |
822 | (((S) + (mparams.granularity - SIZE_T_ONE))\ |
822 | (((S) + (mparams.granularity - SIZE_T_ONE))\ |
823 | & ~(mparams.granularity - SIZE_T_ONE)) |
823 | & ~(mparams.granularity - SIZE_T_ONE)) |
824 | 824 | ||
825 | 825 | ||
826 | /* For mmap, use granularity alignment */ |
826 | /* For mmap, use granularity alignment */ |
827 | #define mmap_align(S) granularity_align(S) |
827 | #define mmap_align(S) granularity_align(S) |
828 | 828 | ||
829 | /* For sys_alloc, enough padding to ensure can malloc request on success */ |
829 | /* For sys_alloc, enough padding to ensure can malloc request on success */ |
830 | #define SYS_ALLOC_PADDING (TOP_FOOT_SIZE + MALLOC_ALIGNMENT) |
830 | #define SYS_ALLOC_PADDING (TOP_FOOT_SIZE + MALLOC_ALIGNMENT) |
831 | 831 | ||
832 | #define is_page_aligned(S)\ |
832 | #define is_page_aligned(S)\ |
833 | (((size_t)(S) & (mparams.page_size - SIZE_T_ONE)) == 0) |
833 | (((size_t)(S) & (mparams.page_size - SIZE_T_ONE)) == 0) |
834 | #define is_granularity_aligned(S)\ |
834 | #define is_granularity_aligned(S)\ |
835 | (((size_t)(S) & (mparams.granularity - SIZE_T_ONE)) == 0) |
835 | (((size_t)(S) & (mparams.granularity - SIZE_T_ONE)) == 0) |
836 | 836 | ||
837 | /* True if segment S holds address A */ |
837 | /* True if segment S holds address A */ |
838 | #define segment_holds(S, A)\ |
838 | #define segment_holds(S, A)\ |
839 | ((char*)(A) >= S->base && (char*)(A) < S->base + S->size) |
839 | ((char*)(A) >= S->base && (char*)(A) < S->base + S->size) |
840 | 840 | ||
841 | /* Return segment holding given address */ |
841 | /* Return segment holding given address */ |
842 | static msegmentptr segment_holding(mstate m, char* addr) |
842 | static msegmentptr segment_holding(mstate m, char* addr) |
843 | { |
843 | { |
844 | msegmentptr sp = &m->seg; |
844 | msegmentptr sp = &m->seg; |
845 | for (;;) { |
845 | for (;;) { |
846 | if (addr >= sp->base && addr < sp->base + sp->size) |
846 | if (addr >= sp->base && addr < sp->base + sp->size) |
847 | return sp; |
847 | return sp; |
848 | if ((sp = sp->next) == 0) |
848 | if ((sp = sp->next) == 0) |
849 | return 0; |
849 | return 0; |
850 | } |
850 | } |
851 | } |
851 | } |
852 | 852 | ||
853 | /* Return true if segment contains a segment link */ |
853 | /* Return true if segment contains a segment link */ |
854 | static int has_segment_link(mstate m, msegmentptr ss) |
854 | static int has_segment_link(mstate m, msegmentptr ss) |
855 | { |
855 | { |
856 | msegmentptr sp = &m->seg; |
856 | msegmentptr sp = &m->seg; |
857 | for (;;) { |
857 | for (;;) { |
858 | if ((char*)sp >= ss->base && (char*)sp < ss->base + ss->size) |
858 | if ((char*)sp >= ss->base && (char*)sp < ss->base + ss->size) |
859 | return 1; |
859 | return 1; |
860 | if ((sp = sp->next) == 0) |
860 | if ((sp = sp->next) == 0) |
861 | return 0; |
861 | return 0; |
862 | } |
862 | } |
863 | } |
863 | } |
864 | 864 | ||
865 | static inline void* os_mmap(size_t size) |
865 | static inline void* os_mmap(size_t size) |
866 | { |
866 | { |
867 | void* ptr = user_alloc(size); |
867 | void* ptr = user_alloc(size); |
868 | return (ptr != 0)? ptr: MFAIL; |
868 | return (ptr != 0)? ptr: MFAIL; |
869 | } |
869 | } |
870 | 870 | ||
871 | static inline int os_munmap(void* ptr, size_t size) |
871 | static inline int os_munmap(void* ptr, size_t size) |
872 | { |
872 | { |
873 | return (user_free(ptr) != 0) ? 0 : -1; |
873 | return (user_free(ptr) != 0) ? 0 : -1; |
874 | } |
874 | } |
875 | 875 | ||
876 | #define should_trim(M,s) ((s) > (M)->trim_check) |
876 | #define should_trim(M,s) ((s) > (M)->trim_check) |
877 | 877 | ||
878 | 878 | ||
879 | #define MMAP_DEFAULT(s) os_mmap(s) |
879 | #define MMAP_DEFAULT(s) os_mmap(s) |
880 | #define MUNMAP_DEFAULT(a, s) os_munmap((a), (s)) |
880 | #define MUNMAP_DEFAULT(a, s) os_munmap((a), (s)) |
881 | #define DIRECT_MMAP_DEFAULT(s) os_mmap(s) |
881 | #define DIRECT_MMAP_DEFAULT(s) os_mmap(s) |
882 | 882 | ||
883 | #define internal_malloc(m, b) malloc(b) |
883 | #define internal_malloc(m, b) malloc(b) |
884 | #define internal_free(m, mem) free(mem) |
884 | #define internal_free(m, mem) free(mem) |
885 | 885 | ||
886 | /* ----------------------- Direct-mmapping chunks ----------------------- */ |
886 | /* ----------------------- Direct-mmapping chunks ----------------------- */ |
887 | 887 | ||
888 | /* |
888 | /* |
889 | Directly mmapped chunks are set up with an offset to the start of |
889 | Directly mmapped chunks are set up with an offset to the start of |
890 | the mmapped region stored in the prev_foot field of the chunk. This |
890 | the mmapped region stored in the prev_foot field of the chunk. This |
891 | allows reconstruction of the required argument to MUNMAP when freed, |
891 | allows reconstruction of the required argument to MUNMAP when freed, |
892 | and also allows adjustment of the returned chunk to meet alignment |
892 | and also allows adjustment of the returned chunk to meet alignment |
893 | requirements (especially in memalign). |
893 | requirements (especially in memalign). |
894 | */ |
894 | */ |
895 | 895 | ||
896 | /* Malloc using mmap */ |
896 | /* Malloc using mmap */ |
897 | static void* mmap_alloc(mstate m, size_t nb) |
897 | static void* mmap_alloc(mstate m, size_t nb) |
898 | { |
898 | { |
899 | size_t mmsize = mmap_align(nb + SIX_SIZE_T_SIZES + CHUNK_ALIGN_MASK); |
899 | size_t mmsize = mmap_align(nb + SIX_SIZE_T_SIZES + CHUNK_ALIGN_MASK); |
900 | if (mmsize > nb) /* Check for wrap around 0 */ |
900 | if (mmsize > nb) /* Check for wrap around 0 */ |
901 | { |
901 | { |
902 | char* mm = (char*)(os_mmap(mmsize)); |
902 | char* mm = (char*)(os_mmap(mmsize)); |
903 | if (mm != CMFAIL) |
903 | if (mm != CMFAIL) |
904 | { |
904 | { |
905 | size_t offset = align_offset(chunk2mem(mm)); |
905 | size_t offset = align_offset(chunk2mem(mm)); |
906 | size_t psize = mmsize - offset - MMAP_FOOT_PAD; |
906 | size_t psize = mmsize - offset - MMAP_FOOT_PAD; |
907 | mchunkptr p = (mchunkptr)(mm + offset); |
907 | mchunkptr p = (mchunkptr)(mm + offset); |
908 | p->prev_foot = offset; |
908 | p->prev_foot = offset; |
909 | p->head = psize; |
909 | p->head = psize; |
910 | mark_inuse_foot(m, p, psize); |
910 | mark_inuse_foot(m, p, psize); |
911 | chunk_plus_offset(p, psize)->head = FENCEPOST_HEAD; |
911 | chunk_plus_offset(p, psize)->head = FENCEPOST_HEAD; |
912 | chunk_plus_offset(p, psize+SIZE_T_SIZE)->head = 0; |
912 | chunk_plus_offset(p, psize+SIZE_T_SIZE)->head = 0; |
913 | 913 | ||
914 | if (m->least_addr == 0 || mm < m->least_addr) |
914 | if (m->least_addr == 0 || mm < m->least_addr) |
915 | m->least_addr = mm; |
915 | m->least_addr = mm; |
916 | if ((m->footprint += mmsize) > m->max_footprint) |
916 | if ((m->footprint += mmsize) > m->max_footprint) |
917 | m->max_footprint = m->footprint; |
917 | m->max_footprint = m->footprint; |
918 | assert(is_aligned(chunk2mem(p))); |
918 | assert(is_aligned(chunk2mem(p))); |
919 | check_mmapped_chunk(m, p); |
919 | check_mmapped_chunk(m, p); |
920 | return chunk2mem(p); |
920 | return chunk2mem(p); |
921 | } |
921 | } |
922 | } |
922 | } |
923 | return 0; |
923 | return 0; |
924 | } |
924 | } |
925 | 925 | ||
926 | /* Realloc using mmap */ |
926 | /* Realloc using mmap */ |
927 | static mchunkptr mmap_resize(mstate m, mchunkptr oldp, size_t nb) |
927 | static mchunkptr mmap_resize(mstate m, mchunkptr oldp, size_t nb) |
928 | { |
928 | { |
929 | size_t oldsize = chunksize(oldp); |
929 | size_t oldsize = chunksize(oldp); |
930 | if (is_small(nb)) /* Can't shrink mmap regions below small size */ |
930 | if (is_small(nb)) /* Can't shrink mmap regions below small size */ |
931 | return 0; |
931 | return 0; |
932 | /* Keep old chunk if big enough but not too big */ |
932 | /* Keep old chunk if big enough but not too big */ |
933 | if (oldsize >= nb + SIZE_T_SIZE && |
933 | if (oldsize >= nb + SIZE_T_SIZE && |
934 | (oldsize - nb) <= (mparams.granularity << 1)) |
934 | (oldsize - nb) <= (mparams.granularity << 1)) |
935 | return oldp; |
935 | return oldp; |
936 | else |
936 | else |
937 | { |
937 | { |
938 | size_t offset = oldp->prev_foot; |
938 | size_t offset = oldp->prev_foot; |
939 | size_t oldmmsize = oldsize + offset + MMAP_FOOT_PAD; |
939 | size_t oldmmsize = oldsize + offset + MMAP_FOOT_PAD; |
940 | size_t newmmsize = mmap_align(nb + SIX_SIZE_T_SIZES + CHUNK_ALIGN_MASK); |
940 | size_t newmmsize = mmap_align(nb + SIX_SIZE_T_SIZES + CHUNK_ALIGN_MASK); |
941 | char* cp = (char*)CALL_MREMAP((char*)oldp - offset, |
941 | char* cp = (char*)CALL_MREMAP((char*)oldp - offset, |
942 | oldmmsize, newmmsize, 1); |
942 | oldmmsize, newmmsize, 1); |
943 | if (cp != CMFAIL) |
943 | if (cp != CMFAIL) |
944 | { |
944 | { |
945 | mchunkptr newp = (mchunkptr)(cp + offset); |
945 | mchunkptr newp = (mchunkptr)(cp + offset); |
946 | size_t psize = newmmsize - offset - MMAP_FOOT_PAD; |
946 | size_t psize = newmmsize - offset - MMAP_FOOT_PAD; |
947 | newp->head = psize; |
947 | newp->head = psize; |
948 | mark_inuse_foot(m, newp, psize); |
948 | mark_inuse_foot(m, newp, psize); |
949 | chunk_plus_offset(newp, psize)->head = FENCEPOST_HEAD; |
949 | chunk_plus_offset(newp, psize)->head = FENCEPOST_HEAD; |
950 | chunk_plus_offset(newp, psize+SIZE_T_SIZE)->head = 0; |
950 | chunk_plus_offset(newp, psize+SIZE_T_SIZE)->head = 0; |
951 | 951 | ||
952 | if (cp < m->least_addr) |
952 | if (cp < m->least_addr) |
953 | m->least_addr = cp; |
953 | m->least_addr = cp; |
954 | if ((m->footprint += newmmsize - oldmmsize) > m->max_footprint) |
954 | if ((m->footprint += newmmsize - oldmmsize) > m->max_footprint) |
955 | m->max_footprint = m->footprint; |
955 | m->max_footprint = m->footprint; |
956 | check_mmapped_chunk(m, newp); |
956 | check_mmapped_chunk(m, newp); |
957 | return newp; |
957 | return newp; |
958 | } |
958 | } |
959 | } |
959 | } |
960 | return 0; |
960 | return 0; |
961 | } |
961 | } |
962 | 962 | ||
963 | /* ---------------------------- setting mparams -------------------------- */ |
963 | /* ---------------------------- setting mparams -------------------------- */ |
964 | 964 | ||
965 | /* Initialize mparams */ |
965 | /* Initialize mparams */ |
966 | static int init_mparams(void) { |
966 | static int init_mparams(void) { |
967 | 967 | ||
968 | ACQUIRE_MALLOC_GLOBAL_LOCK(); |
968 | ACQUIRE_MALLOC_GLOBAL_LOCK(); |
969 | 969 | ||
970 | if (mparams.magic == 0) |
970 | if (mparams.magic == 0) |
971 | { |
971 | { |
972 | size_t magic; |
972 | size_t magic; |
973 | size_t psize; |
973 | size_t psize; |
974 | size_t gsize; |
974 | size_t gsize; |
975 | 975 | ||
976 | psize = 4096; |
976 | psize = 4096; |
977 | gsize = DEFAULT_GRANULARITY; |
977 | gsize = DEFAULT_GRANULARITY; |
978 | 978 | ||
979 | /* Sanity-check configuration: |
979 | /* Sanity-check configuration: |
980 | size_t must be unsigned and as wide as pointer type. |
980 | size_t must be unsigned and as wide as pointer type. |
981 | ints must be at least 4 bytes. |
981 | ints must be at least 4 bytes. |
982 | alignment must be at least 8. |
982 | alignment must be at least 8. |
983 | Alignment, min chunk size, and page size must all be powers of 2. |
983 | Alignment, min chunk size, and page size must all be powers of 2. |
984 | */ |
984 | */ |
985 | 985 | ||
986 | mparams.granularity = gsize; |
986 | mparams.granularity = gsize; |
987 | mparams.page_size = psize; |
987 | mparams.page_size = psize; |
988 | mparams.mmap_threshold = DEFAULT_MMAP_THRESHOLD; |
988 | mparams.mmap_threshold = DEFAULT_MMAP_THRESHOLD; |
989 | mparams.trim_threshold = DEFAULT_TRIM_THRESHOLD; |
989 | mparams.trim_threshold = DEFAULT_TRIM_THRESHOLD; |
990 | mparams.default_mflags = USE_LOCK_BIT|USE_MMAP_BIT|USE_NONCONTIGUOUS_BIT; |
990 | mparams.default_mflags = USE_LOCK_BIT|USE_MMAP_BIT|USE_NONCONTIGUOUS_BIT; |
991 | 991 | ||
992 | /* Set up lock for main malloc area */ |
992 | /* Set up lock for main malloc area */ |
993 | gm->mflags = mparams.default_mflags; |
993 | gm->mflags = mparams.default_mflags; |
994 | __libc_lock_init_recursive(gm->lock); |
994 | __lock_init_recursive(gm->lock); |
995 | 995 | ||
996 | magic = (size_t)(0x12345678 ^ (size_t)0x55555555U); |
996 | magic = (size_t)(0x12345678 ^ (size_t)0x55555555U); |
997 | magic |= (size_t)8U; /* ensure nonzero */ |
997 | magic |= (size_t)8U; /* ensure nonzero */ |
998 | magic &= ~(size_t)7U; /* improve chances of fault for bad values */ |
998 | magic &= ~(size_t)7U; /* improve chances of fault for bad values */ |
999 | mparams.magic = magic; |
999 | mparams.magic = magic; |
1000 | } |
1000 | } |
1001 | 1001 | ||
1002 | RELEASE_MALLOC_GLOBAL_LOCK(); |
1002 | RELEASE_MALLOC_GLOBAL_LOCK(); |
1003 | return 1; |
1003 | return 1; |
1004 | } |
1004 | } |
1005 | 1005 | ||
1006 | /* -------------------------- mspace management -------------------------- */ |
1006 | /* -------------------------- mspace management -------------------------- */ |
1007 | 1007 | ||
1008 | /* Initialize top chunk and its size */ |
1008 | /* Initialize top chunk and its size */ |
1009 | static void init_top(mstate m, mchunkptr p, size_t psize) |
1009 | static void init_top(mstate m, mchunkptr p, size_t psize) |
1010 | { |
1010 | { |
1011 | /* Ensure alignment */ |
1011 | /* Ensure alignment */ |
1012 | size_t offset = align_offset(chunk2mem(p)); |
1012 | size_t offset = align_offset(chunk2mem(p)); |
1013 | p = (mchunkptr)((char*)p + offset); |
1013 | p = (mchunkptr)((char*)p + offset); |
1014 | psize -= offset; |
1014 | psize -= offset; |
1015 | 1015 | ||
1016 | m->top = p; |
1016 | m->top = p; |
1017 | m->topsize = psize; |
1017 | m->topsize = psize; |
1018 | p->head = psize | PINUSE_BIT; |
1018 | p->head = psize | PINUSE_BIT; |
1019 | /* set size of fake trailing chunk holding overhead space only once */ |
1019 | /* set size of fake trailing chunk holding overhead space only once */ |
1020 | chunk_plus_offset(p, psize)->head = TOP_FOOT_SIZE; |
1020 | chunk_plus_offset(p, psize)->head = TOP_FOOT_SIZE; |
1021 | m->trim_check = mparams.trim_threshold; /* reset on each update */ |
1021 | m->trim_check = mparams.trim_threshold; /* reset on each update */ |
1022 | } |
1022 | } |
1023 | 1023 | ||
1024 | /* Initialize bins for a new mstate that is otherwise zeroed out */ |
1024 | /* Initialize bins for a new mstate that is otherwise zeroed out */ |
1025 | static void init_bins(mstate m) |
1025 | static void init_bins(mstate m) |
1026 | { |
1026 | { |
1027 | /* Establish circular links for smallbins */ |
1027 | /* Establish circular links for smallbins */ |
1028 | bindex_t i; |
1028 | bindex_t i; |
1029 | for (i = 0; i < NSMALLBINS; ++i) { |
1029 | for (i = 0; i < NSMALLBINS; ++i) { |
1030 | sbinptr bin = smallbin_at(m,i); |
1030 | sbinptr bin = smallbin_at(m,i); |
1031 | bin->fd = bin->bk = bin; |
1031 | bin->fd = bin->bk = bin; |
1032 | } |
1032 | } |
1033 | } |
1033 | } |
1034 | 1034 | ||
1035 | /* Allocate chunk and prepend remainder with chunk in successor base. */ |
1035 | /* Allocate chunk and prepend remainder with chunk in successor base. */ |
1036 | static void* prepend_alloc(mstate m, char* newbase, char* oldbase, |
1036 | static void* prepend_alloc(mstate m, char* newbase, char* oldbase, |
1037 | size_t nb) |
1037 | size_t nb) |
1038 | { |
1038 | { |
1039 | mchunkptr p = align_as_chunk(newbase); |
1039 | mchunkptr p = align_as_chunk(newbase); |
1040 | mchunkptr oldfirst = align_as_chunk(oldbase); |
1040 | mchunkptr oldfirst = align_as_chunk(oldbase); |
1041 | size_t psize = (char*)oldfirst - (char*)p; |
1041 | size_t psize = (char*)oldfirst - (char*)p; |
1042 | mchunkptr q = chunk_plus_offset(p, nb); |
1042 | mchunkptr q = chunk_plus_offset(p, nb); |
1043 | size_t qsize = psize - nb; |
1043 | size_t qsize = psize - nb; |
1044 | set_size_and_pinuse_of_inuse_chunk(m, p, nb); |
1044 | set_size_and_pinuse_of_inuse_chunk(m, p, nb); |
1045 | 1045 | ||
1046 | assert((char*)oldfirst > (char*)q); |
1046 | assert((char*)oldfirst > (char*)q); |
1047 | assert(pinuse(oldfirst)); |
1047 | assert(pinuse(oldfirst)); |
1048 | assert(qsize >= MIN_CHUNK_SIZE); |
1048 | assert(qsize >= MIN_CHUNK_SIZE); |
1049 | 1049 | ||
1050 | /* consolidate remainder with first chunk of old base */ |
1050 | /* consolidate remainder with first chunk of old base */ |
1051 | if (oldfirst == m->top) { |
1051 | if (oldfirst == m->top) { |
1052 | size_t tsize = m->topsize += qsize; |
1052 | size_t tsize = m->topsize += qsize; |
1053 | m->top = q; |
1053 | m->top = q; |
1054 | q->head = tsize | PINUSE_BIT; |
1054 | q->head = tsize | PINUSE_BIT; |
1055 | check_top_chunk(m, q); |
1055 | check_top_chunk(m, q); |
1056 | } |
1056 | } |
1057 | else if (oldfirst == m->dv) { |
1057 | else if (oldfirst == m->dv) { |
1058 | size_t dsize = m->dvsize += qsize; |
1058 | size_t dsize = m->dvsize += qsize; |
1059 | m->dv = q; |
1059 | m->dv = q; |
1060 | set_size_and_pinuse_of_free_chunk(q, dsize); |
1060 | set_size_and_pinuse_of_free_chunk(q, dsize); |
1061 | } |
1061 | } |
1062 | else { |
1062 | else { |
1063 | if (!is_inuse(oldfirst)) { |
1063 | if (!is_inuse(oldfirst)) { |
1064 | size_t nsize = chunksize(oldfirst); |
1064 | size_t nsize = chunksize(oldfirst); |
1065 | unlink_chunk(m, oldfirst, nsize); |
1065 | unlink_chunk(m, oldfirst, nsize); |
1066 | oldfirst = chunk_plus_offset(oldfirst, nsize); |
1066 | oldfirst = chunk_plus_offset(oldfirst, nsize); |
1067 | qsize += nsize; |
1067 | qsize += nsize; |
1068 | } |
1068 | } |
1069 | set_free_with_pinuse(q, qsize, oldfirst); |
1069 | set_free_with_pinuse(q, qsize, oldfirst); |
1070 | insert_chunk(m, q, qsize); |
1070 | insert_chunk(m, q, qsize); |
1071 | check_free_chunk(m, q); |
1071 | check_free_chunk(m, q); |
1072 | } |
1072 | } |
1073 | 1073 | ||
1074 | check_malloced_chunk(m, chunk2mem(p), nb); |
1074 | check_malloced_chunk(m, chunk2mem(p), nb); |
1075 | return chunk2mem(p); |
1075 | return chunk2mem(p); |
1076 | } |
1076 | } |
1077 | 1077 | ||
1078 | /* Add a segment to hold a new noncontiguous region */ |
1078 | /* Add a segment to hold a new noncontiguous region */ |
1079 | static void add_segment(mstate m, char* tbase, size_t tsize, flag_t mmapped) |
1079 | static void add_segment(mstate m, char* tbase, size_t tsize, flag_t mmapped) |
1080 | { |
1080 | { |
1081 | /* Determine locations and sizes of segment, fenceposts, old top */ |
1081 | /* Determine locations and sizes of segment, fenceposts, old top */ |
1082 | char* old_top = (char*)m->top; |
1082 | char* old_top = (char*)m->top; |
1083 | msegmentptr oldsp = segment_holding(m, old_top); |
1083 | msegmentptr oldsp = segment_holding(m, old_top); |
1084 | char* old_end = oldsp->base + oldsp->size; |
1084 | char* old_end = oldsp->base + oldsp->size; |
1085 | size_t ssize = pad_request(sizeof(struct malloc_segment)); |
1085 | size_t ssize = pad_request(sizeof(struct malloc_segment)); |
1086 | char* rawsp = old_end - (ssize + FOUR_SIZE_T_SIZES + CHUNK_ALIGN_MASK); |
1086 | char* rawsp = old_end - (ssize + FOUR_SIZE_T_SIZES + CHUNK_ALIGN_MASK); |
1087 | size_t offset = align_offset(chunk2mem(rawsp)); |
1087 | size_t offset = align_offset(chunk2mem(rawsp)); |
1088 | char* asp = rawsp + offset; |
1088 | char* asp = rawsp + offset; |
1089 | char* csp = (asp < (old_top + MIN_CHUNK_SIZE))? old_top : asp; |
1089 | char* csp = (asp < (old_top + MIN_CHUNK_SIZE))? old_top : asp; |
1090 | mchunkptr sp = (mchunkptr)csp; |
1090 | mchunkptr sp = (mchunkptr)csp; |
1091 | msegmentptr ss = (msegmentptr)(chunk2mem(sp)); |
1091 | msegmentptr ss = (msegmentptr)(chunk2mem(sp)); |
1092 | mchunkptr tnext = chunk_plus_offset(sp, ssize); |
1092 | mchunkptr tnext = chunk_plus_offset(sp, ssize); |
1093 | mchunkptr p = tnext; |
1093 | mchunkptr p = tnext; |
1094 | int nfences = 0; |
1094 | int nfences = 0; |
1095 | 1095 | ||
1096 | /* reset top to new space */ |
1096 | /* reset top to new space */ |
1097 | init_top(m, (mchunkptr)tbase, tsize - TOP_FOOT_SIZE); |
1097 | init_top(m, (mchunkptr)tbase, tsize - TOP_FOOT_SIZE); |
1098 | 1098 | ||
1099 | /* Set up segment record */ |
1099 | /* Set up segment record */ |
1100 | assert(is_aligned(ss)); |
1100 | assert(is_aligned(ss)); |
1101 | set_size_and_pinuse_of_inuse_chunk(m, sp, ssize); |
1101 | set_size_and_pinuse_of_inuse_chunk(m, sp, ssize); |
1102 | *ss = m->seg; /* Push current record */ |
1102 | *ss = m->seg; /* Push current record */ |
1103 | m->seg.base = tbase; |
1103 | m->seg.base = tbase; |
1104 | m->seg.size = tsize; |
1104 | m->seg.size = tsize; |
1105 | m->seg.sflags = mmapped; |
1105 | m->seg.sflags = mmapped; |
1106 | m->seg.next = ss; |
1106 | m->seg.next = ss; |
1107 | 1107 | ||
1108 | /* Insert trailing fenceposts */ |
1108 | /* Insert trailing fenceposts */ |
1109 | for (;;) { |
1109 | for (;;) { |
1110 | mchunkptr nextp = chunk_plus_offset(p, SIZE_T_SIZE); |
1110 | mchunkptr nextp = chunk_plus_offset(p, SIZE_T_SIZE); |
1111 | p->head = FENCEPOST_HEAD; |
1111 | p->head = FENCEPOST_HEAD; |
1112 | ++nfences; |
1112 | ++nfences; |
1113 | if ((char*)(&(nextp->head)) < old_end) |
1113 | if ((char*)(&(nextp->head)) < old_end) |
1114 | p = nextp; |
1114 | p = nextp; |
1115 | else |
1115 | else |
1116 | break; |
1116 | break; |
1117 | } |
1117 | } |
1118 | assert(nfences >= 2); |
1118 | assert(nfences >= 2); |
1119 | 1119 | ||
1120 | /* Insert the rest of old top into a bin as an ordinary free chunk */ |
1120 | /* Insert the rest of old top into a bin as an ordinary free chunk */ |
1121 | if (csp != old_top) { |
1121 | if (csp != old_top) { |
1122 | mchunkptr q = (mchunkptr)old_top; |
1122 | mchunkptr q = (mchunkptr)old_top; |
1123 | size_t psize = csp - old_top; |
1123 | size_t psize = csp - old_top; |
1124 | mchunkptr tn = chunk_plus_offset(q, psize); |
1124 | mchunkptr tn = chunk_plus_offset(q, psize); |
1125 | set_free_with_pinuse(q, psize, tn); |
1125 | set_free_with_pinuse(q, psize, tn); |
1126 | insert_chunk(m, q, psize); |
1126 | insert_chunk(m, q, psize); |
1127 | } |
1127 | } |
1128 | 1128 | ||
1129 | check_top_chunk(m, m->top); |
1129 | check_top_chunk(m, m->top); |
1130 | } |
1130 | } |
1131 | 1131 | ||
1132 | /* -------------------------- System allocation -------------------------- */ |
1132 | /* -------------------------- System allocation -------------------------- */ |
1133 | 1133 | ||
1134 | /* Get memory from system using MORECORE or MMAP */ |
1134 | /* Get memory from system using MORECORE or MMAP */ |
1135 | static void* sys_alloc(mstate m, size_t nb) |
1135 | static void* sys_alloc(mstate m, size_t nb) |
1136 | { |
1136 | { |
1137 | char* tbase = CMFAIL; |
1137 | char* tbase = CMFAIL; |
1138 | size_t tsize = 0; |
1138 | size_t tsize = 0; |
1139 | flag_t mmap_flag = 0; |
1139 | flag_t mmap_flag = 0; |
1140 | 1140 | ||
1141 | ensure_initialization(); |
1141 | ensure_initialization(); |
1142 | 1142 | ||
1143 | /* Directly map large chunks, but only if already initialized */ |
1143 | /* Directly map large chunks, but only if already initialized */ |
1144 | if (use_mmap(m) && nb >= mparams.mmap_threshold && m->topsize != 0) |
1144 | if (use_mmap(m) && nb >= mparams.mmap_threshold && m->topsize != 0) |
1145 | { |
1145 | { |
1146 | void* mem = mmap_alloc(m, nb); |
1146 | void* mem = mmap_alloc(m, nb); |
1147 | if (mem != 0) |
1147 | if (mem != 0) |
1148 | return mem; |
1148 | return mem; |
1149 | } |
1149 | } |
1150 | 1150 | ||
1151 | /* |
1151 | /* |
1152 | Try getting memory in any of three ways (in most-preferred to |
1152 | Try getting memory in any of three ways (in most-preferred to |
1153 | least-preferred order): |
1153 | least-preferred order): |
1154 | 1. A call to MORECORE that can normally contiguously extend memory. |
1154 | 1. A call to MORECORE that can normally contiguously extend memory. |
1155 | (disabled if not MORECORE_CONTIGUOUS or not HAVE_MORECORE or |
1155 | (disabled if not MORECORE_CONTIGUOUS or not HAVE_MORECORE or |
1156 | or main space is mmapped or a previous contiguous call failed) |
1156 | or main space is mmapped or a previous contiguous call failed) |
1157 | 2. A call to MMAP new space (disabled if not HAVE_MMAP). |
1157 | 2. A call to MMAP new space (disabled if not HAVE_MMAP). |
1158 | Note that under the default settings, if MORECORE is unable to |
1158 | Note that under the default settings, if MORECORE is unable to |
1159 | fulfill a request, and HAVE_MMAP is true, then mmap is |
1159 | fulfill a request, and HAVE_MMAP is true, then mmap is |
1160 | used as a noncontiguous system allocator. This is a useful backup |
1160 | used as a noncontiguous system allocator. This is a useful backup |
1161 | strategy for systems with holes in address spaces -- in this case |
1161 | strategy for systems with holes in address spaces -- in this case |
1162 | sbrk cannot contiguously expand the heap, but mmap may be able to |
1162 | sbrk cannot contiguously expand the heap, but mmap may be able to |
1163 | find space. |
1163 | find space. |
1164 | 3. A call to MORECORE that cannot usually contiguously extend memory. |
1164 | 3. A call to MORECORE that cannot usually contiguously extend memory. |
1165 | (disabled if not HAVE_MORECORE) |
1165 | (disabled if not HAVE_MORECORE) |
1166 | 1166 | ||
1167 | In all cases, we need to request enough bytes from system to ensure |
1167 | In all cases, we need to request enough bytes from system to ensure |
1168 | we can malloc nb bytes upon success, so pad with enough space for |
1168 | we can malloc nb bytes upon success, so pad with enough space for |
1169 | top_foot, plus alignment-pad to make sure we don't lose bytes if |
1169 | top_foot, plus alignment-pad to make sure we don't lose bytes if |
1170 | not on boundary, and round this up to a granularity unit. |
1170 | not on boundary, and round this up to a granularity unit. |
1171 | */ |
1171 | */ |
1172 | 1172 | ||
1173 | if (HAVE_MMAP && tbase == CMFAIL) /* Try MMAP */ |
1173 | if (HAVE_MMAP && tbase == CMFAIL) /* Try MMAP */ |
1174 | { |
1174 | { |
1175 | size_t rsize = granularity_align(nb + SYS_ALLOC_PADDING); |
1175 | size_t rsize = granularity_align(nb + SYS_ALLOC_PADDING); |
1176 | if (rsize > nb) /* Fail if wraps around zero */ |
1176 | if (rsize > nb) /* Fail if wraps around zero */ |
1177 | { |
1177 | { |
1178 | char* mp = (char*)(CALL_MMAP(rsize)); |
1178 | char* mp = (char*)(CALL_MMAP(rsize)); |
1179 | if (mp != CMFAIL) |
1179 | if (mp != CMFAIL) |
1180 | { |
1180 | { |
1181 | tbase = mp; |
1181 | tbase = mp; |
1182 | tsize = rsize; |
1182 | tsize = rsize; |
1183 | mmap_flag = USE_MMAP_BIT; |
1183 | mmap_flag = USE_MMAP_BIT; |
1184 | } |
1184 | } |
1185 | } |
1185 | } |
1186 | } |
1186 | } |
1187 | 1187 | ||
1188 | if (tbase != CMFAIL) |
1188 | if (tbase != CMFAIL) |
1189 | { |
1189 | { |
1190 | 1190 | ||
1191 | if ((m->footprint += tsize) > m->max_footprint) |
1191 | if ((m->footprint += tsize) > m->max_footprint) |
1192 | m->max_footprint = m->footprint; |
1192 | m->max_footprint = m->footprint; |
1193 | 1193 | ||
1194 | if (!is_initialized(m)) /* first-time initialization */ |
1194 | if (!is_initialized(m)) /* first-time initialization */ |
1195 | { |
1195 | { |
1196 | if (m->least_addr == 0 || tbase < m->least_addr) |
1196 | if (m->least_addr == 0 || tbase < m->least_addr) |
1197 | m->least_addr = tbase; |
1197 | m->least_addr = tbase; |
1198 | m->seg.base = tbase; |
1198 | m->seg.base = tbase; |
1199 | m->seg.size = tsize; |
1199 | m->seg.size = tsize; |
1200 | m->seg.sflags = mmap_flag; |
1200 | m->seg.sflags = mmap_flag; |
1201 | m->magic = mparams.magic; |
1201 | m->magic = mparams.magic; |
1202 | m->release_checks = MAX_RELEASE_CHECK_RATE; |
1202 | m->release_checks = MAX_RELEASE_CHECK_RATE; |
1203 | init_bins(m); |
1203 | init_bins(m); |
1204 | 1204 | ||
1205 | if (is_global(m)) |
1205 | if (is_global(m)) |
1206 | init_top(m, (mchunkptr)tbase, tsize - TOP_FOOT_SIZE); |
1206 | init_top(m, (mchunkptr)tbase, tsize - TOP_FOOT_SIZE); |
1207 | else |
1207 | else |
1208 | { |
1208 | { |
1209 | /* Offset top by embedded malloc_state */ |
1209 | /* Offset top by embedded malloc_state */ |
1210 | mchunkptr mn = next_chunk(mem2chunk(m)); |
1210 | mchunkptr mn = next_chunk(mem2chunk(m)); |
1211 | init_top(m, mn, (size_t)((tbase + tsize) - (char*)mn) -TOP_FOOT_SIZE); |
1211 | init_top(m, mn, (size_t)((tbase + tsize) - (char*)mn) -TOP_FOOT_SIZE); |
1212 | } |
1212 | } |
1213 | } |
1213 | } |
1214 | else |
1214 | else |
1215 | { |
1215 | { |
1216 | /* Try to merge with an existing segment */ |
1216 | /* Try to merge with an existing segment */ |
1217 | msegmentptr sp = &m->seg; |
1217 | msegmentptr sp = &m->seg; |
1218 | /* Only consider most recent segment if traversal suppressed */ |
1218 | /* Only consider most recent segment if traversal suppressed */ |
1219 | while (sp != 0 && tbase != sp->base + sp->size) |
1219 | while (sp != 0 && tbase != sp->base + sp->size) |
1220 | sp = (NO_SEGMENT_TRAVERSAL) ? 0 : sp->next; |
1220 | sp = (NO_SEGMENT_TRAVERSAL) ? 0 : sp->next; |
1221 | if (sp != 0 && !is_extern_segment(sp) && |
1221 | if (sp != 0 && !is_extern_segment(sp) && |
1222 | (sp->sflags & USE_MMAP_BIT) == mmap_flag && |
1222 | (sp->sflags & USE_MMAP_BIT) == mmap_flag && |
1223 | segment_holds(sp, m->top)) /* append */ |
1223 | segment_holds(sp, m->top)) /* append */ |
1224 | { |
1224 | { |
1225 | sp->size += tsize; |
1225 | sp->size += tsize; |
1226 | init_top(m, m->top, m->topsize + tsize); |
1226 | init_top(m, m->top, m->topsize + tsize); |
1227 | } |
1227 | } |
1228 | else |
1228 | else |
1229 | { |
1229 | { |
1230 | if (tbase < m->least_addr) |
1230 | if (tbase < m->least_addr) |
1231 | m->least_addr = tbase; |
1231 | m->least_addr = tbase; |
1232 | sp = &m->seg; |
1232 | sp = &m->seg; |
1233 | while (sp != 0 && sp->base != tbase + tsize) |
1233 | while (sp != 0 && sp->base != tbase + tsize) |
1234 | sp = (NO_SEGMENT_TRAVERSAL) ? 0 : sp->next; |
1234 | sp = (NO_SEGMENT_TRAVERSAL) ? 0 : sp->next; |
1235 | if (sp != 0 && !is_extern_segment(sp) && |
1235 | if (sp != 0 && !is_extern_segment(sp) && |
1236 | (sp->sflags & USE_MMAP_BIT) == mmap_flag) |
1236 | (sp->sflags & USE_MMAP_BIT) == mmap_flag) |
1237 | { |
1237 | { |
1238 | char* oldbase = sp->base; |
1238 | char* oldbase = sp->base; |
1239 | sp->base = tbase; |
1239 | sp->base = tbase; |
1240 | sp->size += tsize; |
1240 | sp->size += tsize; |
1241 | return prepend_alloc(m, tbase, oldbase, nb); |
1241 | return prepend_alloc(m, tbase, oldbase, nb); |
1242 | } |
1242 | } |
1243 | else |
1243 | else |
1244 | add_segment(m, tbase, tsize, mmap_flag); |
1244 | add_segment(m, tbase, tsize, mmap_flag); |
1245 | } |
1245 | } |
1246 | } |
1246 | } |
1247 | 1247 | ||
1248 | if (nb < m->topsize) /* Allocate from new or extended top space */ |
1248 | if (nb < m->topsize) /* Allocate from new or extended top space */ |
1249 | { |
1249 | { |
1250 | size_t rsize = m->topsize -= nb; |
1250 | size_t rsize = m->topsize -= nb; |
1251 | mchunkptr p = m->top; |
1251 | mchunkptr p = m->top; |
1252 | mchunkptr r = m->top = chunk_plus_offset(p, nb); |
1252 | mchunkptr r = m->top = chunk_plus_offset(p, nb); |
1253 | r->head = rsize | PINUSE_BIT; |
1253 | r->head = rsize | PINUSE_BIT; |
1254 | set_size_and_pinuse_of_inuse_chunk(m, p, nb); |
1254 | set_size_and_pinuse_of_inuse_chunk(m, p, nb); |
1255 | check_top_chunk(m, m->top); |
1255 | check_top_chunk(m, m->top); |
1256 | check_malloced_chunk(m, chunk2mem(p), nb); |
1256 | check_malloced_chunk(m, chunk2mem(p), nb); |
1257 | return chunk2mem(p); |
1257 | return chunk2mem(p); |
1258 | } |
1258 | } |
1259 | } |
1259 | } |
1260 | 1260 | ||
1261 | MALLOC_FAILURE_ACTION; |
1261 | MALLOC_FAILURE_ACTION; |
1262 | return 0; |
1262 | return 0; |
1263 | } |
1263 | } |
1264 | 1264 | ||
1265 | 1265 | ||
1266 | /* ----------------------- system deallocation -------------------------- */ |
1266 | /* ----------------------- system deallocation -------------------------- */ |
1267 | 1267 | ||
1268 | /* Unmap and unlink any mmapped segments that don't contain used chunks */ |
1268 | /* Unmap and unlink any mmapped segments that don't contain used chunks */ |
1269 | static size_t release_unused_segments(mstate m) |
1269 | static size_t release_unused_segments(mstate m) |
1270 | { |
1270 | { |
1271 | size_t released = 0; |
1271 | size_t released = 0; |
1272 | int nsegs = 0; |
1272 | int nsegs = 0; |
1273 | msegmentptr pred = &m->seg; |
1273 | msegmentptr pred = &m->seg; |
1274 | msegmentptr sp = pred->next; |
1274 | msegmentptr sp = pred->next; |
1275 | while (sp != 0) |
1275 | while (sp != 0) |
1276 | { |
1276 | { |
1277 | char* base = sp->base; |
1277 | char* base = sp->base; |
1278 | size_t size = sp->size; |
1278 | size_t size = sp->size; |
1279 | msegmentptr next = sp->next; |
1279 | msegmentptr next = sp->next; |
1280 | ++nsegs; |
1280 | ++nsegs; |
1281 | if (is_mmapped_segment(sp) && !is_extern_segment(sp)) |
1281 | if (is_mmapped_segment(sp) && !is_extern_segment(sp)) |
1282 | { |
1282 | { |
1283 | mchunkptr p = align_as_chunk(base); |
1283 | mchunkptr p = align_as_chunk(base); |
1284 | size_t psize = chunksize(p); |
1284 | size_t psize = chunksize(p); |
1285 | /* Can unmap if first chunk holds entire segment and not pinned */ |
1285 | /* Can unmap if first chunk holds entire segment and not pinned */ |
1286 | if (!is_inuse(p) && (char*)p + psize >= base + size - TOP_FOOT_SIZE) |
1286 | if (!is_inuse(p) && (char*)p + psize >= base + size - TOP_FOOT_SIZE) |
1287 | { |
1287 | { |
1288 | tchunkptr tp = (tchunkptr)p; |
1288 | tchunkptr tp = (tchunkptr)p; |
1289 | assert(segment_holds(sp, (char*)sp)); |
1289 | assert(segment_holds(sp, (char*)sp)); |
1290 | if (p == m->dv) { |
1290 | if (p == m->dv) { |
1291 | m->dv = 0; |
1291 | m->dv = 0; |
1292 | m->dvsize = 0; |
1292 | m->dvsize = 0; |
1293 | } |
1293 | } |
1294 | else { |
1294 | else { |
1295 | unlink_large_chunk(m, tp); |
1295 | unlink_large_chunk(m, tp); |
1296 | } |
1296 | } |
1297 | if (CALL_MUNMAP(base, size) == 0) |
1297 | if (CALL_MUNMAP(base, size) == 0) |
1298 | { |
1298 | { |
1299 | released += size; |
1299 | released += size; |
1300 | m->footprint -= size; |
1300 | m->footprint -= size; |
1301 | /* unlink obsoleted record */ |
1301 | /* unlink obsoleted record */ |
1302 | sp = pred; |
1302 | sp = pred; |
1303 | sp->next = next; |
1303 | sp->next = next; |
1304 | } |
1304 | } |
1305 | else { /* back out if cannot unmap */ |
1305 | else { /* back out if cannot unmap */ |
1306 | insert_large_chunk(m, tp, psize); |
1306 | insert_large_chunk(m, tp, psize); |
1307 | } |
1307 | } |
1308 | } |
1308 | } |
1309 | } |
1309 | } |
1310 | if (NO_SEGMENT_TRAVERSAL) /* scan only first segment */ |
1310 | if (NO_SEGMENT_TRAVERSAL) /* scan only first segment */ |
1311 | break; |
1311 | break; |
1312 | pred = sp; |
1312 | pred = sp; |
1313 | sp = next; |
1313 | sp = next; |
1314 | } |
1314 | } |
1315 | /* Reset check counter */ |
1315 | /* Reset check counter */ |
1316 | m->release_checks = ((nsegs > MAX_RELEASE_CHECK_RATE)? |
1316 | m->release_checks = ((nsegs > MAX_RELEASE_CHECK_RATE)? |
1317 | nsegs : MAX_RELEASE_CHECK_RATE); |
1317 | nsegs : MAX_RELEASE_CHECK_RATE); |
1318 | return released; |
1318 | return released; |
1319 | } |
1319 | } |
1320 | 1320 | ||
1321 | static int sys_trim(mstate m, size_t pad) |
1321 | static int sys_trim(mstate m, size_t pad) |
1322 | { |
1322 | { |
1323 | size_t released = 0; |
1323 | size_t released = 0; |
1324 | ensure_initialization(); |
1324 | ensure_initialization(); |
1325 | if (pad < MAX_REQUEST && is_initialized(m)) |
1325 | if (pad < MAX_REQUEST && is_initialized(m)) |
1326 | { |
1326 | { |
1327 | pad += TOP_FOOT_SIZE; /* ensure enough room for segment overhead */ |
1327 | pad += TOP_FOOT_SIZE; /* ensure enough room for segment overhead */ |
1328 | 1328 | ||
1329 | if (m->topsize > pad) |
1329 | if (m->topsize > pad) |
1330 | { |
1330 | { |
1331 | /* Shrink top space in granularity-size units, keeping at least one */ |
1331 | /* Shrink top space in granularity-size units, keeping at least one */ |
1332 | size_t unit = mparams.granularity; |
1332 | size_t unit = mparams.granularity; |
1333 | size_t extra = ((m->topsize - pad + (unit - SIZE_T_ONE)) / unit - |
1333 | size_t extra = ((m->topsize - pad + (unit - SIZE_T_ONE)) / unit - |
1334 | SIZE_T_ONE) * unit; |
1334 | SIZE_T_ONE) * unit; |
1335 | msegmentptr sp = segment_holding(m, (char*)m->top); |
1335 | msegmentptr sp = segment_holding(m, (char*)m->top); |
1336 | 1336 | ||
1337 | if (!is_extern_segment(sp)) |
1337 | if (!is_extern_segment(sp)) |
1338 | { |
1338 | { |
1339 | if (is_mmapped_segment(sp)) |
1339 | if (is_mmapped_segment(sp)) |
1340 | { |
1340 | { |
1341 | if (HAVE_MMAP && |
1341 | if (HAVE_MMAP && |
1342 | sp->size >= extra && |
1342 | sp->size >= extra && |
1343 | !has_segment_link(m, sp)) /* can't shrink if pinned */ |
1343 | !has_segment_link(m, sp)) /* can't shrink if pinned */ |
1344 | { |
1344 | { |
1345 | size_t newsize = sp->size - extra; |
1345 | size_t newsize = sp->size - extra; |
1346 | /* Prefer mremap, fall back to munmap */ |
1346 | /* Prefer mremap, fall back to munmap */ |
1347 | if ((CALL_MREMAP(sp->base, sp->size, newsize, 0) != MFAIL) || |
1347 | if ((CALL_MREMAP(sp->base, sp->size, newsize, 0) != MFAIL) || |
1348 | (CALL_MUNMAP(sp->base + newsize, extra) == 0)) |
1348 | (CALL_MUNMAP(sp->base + newsize, extra) == 0)) |
1349 | { |
1349 | { |
1350 | released = extra; |
1350 | released = extra; |
1351 | } |
1351 | } |
1352 | } |
1352 | } |
1353 | } |
1353 | } |
1354 | } |
1354 | } |
1355 | 1355 | ||
1356 | if (released != 0) |
1356 | if (released != 0) |
1357 | { |
1357 | { |
1358 | sp->size -= released; |
1358 | sp->size -= released; |
1359 | m->footprint -= released; |
1359 | m->footprint -= released; |
1360 | init_top(m, m->top, m->topsize - released); |
1360 | init_top(m, m->top, m->topsize - released); |
1361 | check_top_chunk(m, m->top); |
1361 | check_top_chunk(m, m->top); |
1362 | } |
1362 | } |
1363 | } |
1363 | } |
1364 | 1364 | ||
1365 | /* Unmap any unused mmapped segments */ |
1365 | /* Unmap any unused mmapped segments */ |
1366 | if (HAVE_MMAP) |
1366 | if (HAVE_MMAP) |
1367 | released += release_unused_segments(m); |
1367 | released += release_unused_segments(m); |
1368 | 1368 | ||
1369 | /* On failure, disable autotrim to avoid repeated failed future calls */ |
1369 | /* On failure, disable autotrim to avoid repeated failed future calls */ |
1370 | if (released == 0 && m->topsize > m->trim_check) |
1370 | if (released == 0 && m->topsize > m->trim_check) |
1371 | m->trim_check = MAX_SIZE_T; |
1371 | m->trim_check = MAX_SIZE_T; |
1372 | } |
1372 | } |
1373 | 1373 | ||
1374 | return (released != 0)? 1 : 0; |
1374 | return (released != 0)? 1 : 0; |
1375 | } |
1375 | } |
1376 | 1376 | ||
1377 | 1377 | ||
1378 | 1378 | ||
1379 | /* ---------------------------- malloc support --------------------------- */ |
1379 | /* ---------------------------- malloc support --------------------------- */ |
1380 | 1380 | ||
1381 | /* allocate a large request from the best fitting chunk in a treebin */ |
1381 | /* allocate a large request from the best fitting chunk in a treebin */ |
1382 | static void* tmalloc_large(mstate m, size_t nb) { |
1382 | static void* tmalloc_large(mstate m, size_t nb) { |
1383 | tchunkptr v = 0; |
1383 | tchunkptr v = 0; |
1384 | size_t rsize = -nb; /* Unsigned negation */ |
1384 | size_t rsize = -nb; /* Unsigned negation */ |
1385 | tchunkptr t; |
1385 | tchunkptr t; |
1386 | bindex_t idx; |
1386 | bindex_t idx; |
1387 | compute_tree_index(nb, idx); |
1387 | compute_tree_index(nb, idx); |
1388 | if ((t = *treebin_at(m, idx)) != 0) { |
1388 | if ((t = *treebin_at(m, idx)) != 0) { |
1389 | /* Traverse tree for this bin looking for node with size == nb */ |
1389 | /* Traverse tree for this bin looking for node with size == nb */ |
1390 | size_t sizebits = nb << leftshift_for_tree_index(idx); |
1390 | size_t sizebits = nb << leftshift_for_tree_index(idx); |
1391 | tchunkptr rst = 0; /* The deepest untaken right subtree */ |
1391 | tchunkptr rst = 0; /* The deepest untaken right subtree */ |
1392 | for (;;) { |
1392 | for (;;) { |
1393 | tchunkptr rt; |
1393 | tchunkptr rt; |
1394 | size_t trem = chunksize(t) - nb; |
1394 | size_t trem = chunksize(t) - nb; |
1395 | if (trem < rsize) { |
1395 | if (trem < rsize) { |
1396 | v = t; |
1396 | v = t; |
1397 | if ((rsize = trem) == 0) |
1397 | if ((rsize = trem) == 0) |
1398 | break; |
1398 | break; |
1399 | } |
1399 | } |
1400 | rt = t->child[1]; |
1400 | rt = t->child[1]; |
1401 | t = t->child[(sizebits >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1]; |
1401 | t = t->child[(sizebits >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1]; |
1402 | if (rt != 0 && rt != t) |
1402 | if (rt != 0 && rt != t) |
1403 | rst = rt; |
1403 | rst = rt; |
1404 | if (t == 0) { |
1404 | if (t == 0) { |
1405 | t = rst; /* set t to least subtree holding sizes > nb */ |
1405 | t = rst; /* set t to least subtree holding sizes > nb */ |
1406 | break; |
1406 | break; |
1407 | } |
1407 | } |
1408 | sizebits <<= 1; |
1408 | sizebits <<= 1; |
1409 | } |
1409 | } |
1410 | } |
1410 | } |
1411 | if (t == 0 && v == 0) { /* set t to root of next non-empty treebin */ |
1411 | if (t == 0 && v == 0) { /* set t to root of next non-empty treebin */ |
1412 | binmap_t leftbits = left_bits(idx2bit(idx)) & m->treemap; |
1412 | binmap_t leftbits = left_bits(idx2bit(idx)) & m->treemap; |
1413 | if (leftbits != 0) { |
1413 | if (leftbits != 0) { |
1414 | bindex_t i; |
1414 | bindex_t i; |
1415 | binmap_t leastbit = least_bit(leftbits); |
1415 | binmap_t leastbit = least_bit(leftbits); |
1416 | compute_bit2idx(leastbit, i); |
1416 | compute_bit2idx(leastbit, i); |
1417 | t = *treebin_at(m, i); |
1417 | t = *treebin_at(m, i); |
1418 | } |
1418 | } |
1419 | } |
1419 | } |
1420 | 1420 | ||
1421 | while (t != 0) { /* find smallest of tree or subtree */ |
1421 | while (t != 0) { /* find smallest of tree or subtree */ |
1422 | size_t trem = chunksize(t) - nb; |
1422 | size_t trem = chunksize(t) - nb; |
1423 | if (trem < rsize) { |
1423 | if (trem < rsize) { |
1424 | rsize = trem; |
1424 | rsize = trem; |
1425 | v = t; |
1425 | v = t; |
1426 | } |
1426 | } |
1427 | t = leftmost_child(t); |
1427 | t = leftmost_child(t); |
1428 | } |
1428 | } |
1429 | 1429 | ||
1430 | /* If dv is a better fit, return 0 so malloc will use it */ |
1430 | /* If dv is a better fit, return 0 so malloc will use it */ |
1431 | if (v != 0 && rsize < (size_t)(m->dvsize - nb)) { |
1431 | if (v != 0 && rsize < (size_t)(m->dvsize - nb)) { |
1432 | if (RTCHECK(ok_address(m, v))) { /* split */ |
1432 | if (RTCHECK(ok_address(m, v))) { /* split */ |
1433 | mchunkptr r = chunk_plus_offset(v, nb); |
1433 | mchunkptr r = chunk_plus_offset(v, nb); |
1434 | assert(chunksize(v) == rsize + nb); |
1434 | assert(chunksize(v) == rsize + nb); |
1435 | if (RTCHECK(ok_next(v, r))) { |
1435 | if (RTCHECK(ok_next(v, r))) { |
1436 | unlink_large_chunk(m, v); |
1436 | unlink_large_chunk(m, v); |
1437 | if (rsize < MIN_CHUNK_SIZE) |
1437 | if (rsize < MIN_CHUNK_SIZE) |
1438 | set_inuse_and_pinuse(m, v, (rsize + nb)); |
1438 | set_inuse_and_pinuse(m, v, (rsize + nb)); |
1439 | else { |
1439 | else { |
1440 | set_size_and_pinuse_of_inuse_chunk(m, v, nb); |
1440 | set_size_and_pinuse_of_inuse_chunk(m, v, nb); |
1441 | set_size_and_pinuse_of_free_chunk(r, rsize); |
1441 | set_size_and_pinuse_of_free_chunk(r, rsize); |
1442 | insert_chunk(m, r, rsize); |
1442 | insert_chunk(m, r, rsize); |
1443 | } |
1443 | } |
1444 | return chunk2mem(v); |
1444 | return chunk2mem(v); |
1445 | } |
1445 | } |
1446 | } |
1446 | } |
1447 | CORRUPTION_ERROR_ACTION(m); |
1447 | CORRUPTION_ERROR_ACTION(m); |
1448 | } |
1448 | } |
1449 | return 0; |
1449 | return 0; |
1450 | } |
1450 | } |
1451 | 1451 | ||
1452 | /* allocate a small request from the best fitting chunk in a treebin */ |
1452 | /* allocate a small request from the best fitting chunk in a treebin */ |
1453 | static void* tmalloc_small(mstate m, size_t nb) |
1453 | static void* tmalloc_small(mstate m, size_t nb) |
1454 | { |
1454 | { |
1455 | tchunkptr t, v; |
1455 | tchunkptr t, v; |
1456 | size_t rsize; |
1456 | size_t rsize; |
1457 | bindex_t i; |
1457 | bindex_t i; |
1458 | binmap_t leastbit = least_bit(m->treemap); |
1458 | binmap_t leastbit = least_bit(m->treemap); |
1459 | compute_bit2idx(leastbit, i); |
1459 | compute_bit2idx(leastbit, i); |
1460 | v = t = *treebin_at(m, i); |
1460 | v = t = *treebin_at(m, i); |
1461 | rsize = chunksize(t) - nb; |
1461 | rsize = chunksize(t) - nb; |
1462 | 1462 | ||
1463 | while ((t = leftmost_child(t)) != 0) { |
1463 | while ((t = leftmost_child(t)) != 0) { |
1464 | size_t trem = chunksize(t) - nb; |
1464 | size_t trem = chunksize(t) - nb; |
1465 | if (trem < rsize) { |
1465 | if (trem < rsize) { |
1466 | rsize = trem; |
1466 | rsize = trem; |
1467 | v = t; |
1467 | v = t; |
1468 | } |
1468 | } |
1469 | } |
1469 | } |
1470 | 1470 | ||
1471 | if (RTCHECK(ok_address(m, v))) { |
1471 | if (RTCHECK(ok_address(m, v))) { |
1472 | mchunkptr r = chunk_plus_offset(v, nb); |
1472 | mchunkptr r = chunk_plus_offset(v, nb); |
1473 | assert(chunksize(v) == rsize + nb); |
1473 | assert(chunksize(v) == rsize + nb); |
1474 | if (RTCHECK(ok_next(v, r))) { |
1474 | if (RTCHECK(ok_next(v, r))) { |
1475 | unlink_large_chunk(m, v); |
1475 | unlink_large_chunk(m, v); |
1476 | if (rsize < MIN_CHUNK_SIZE) |
1476 | if (rsize < MIN_CHUNK_SIZE) |
1477 | set_inuse_and_pinuse(m, v, (rsize + nb)); |
1477 | set_inuse_and_pinuse(m, v, (rsize + nb)); |
1478 | else { |
1478 | else { |
1479 | set_size_and_pinuse_of_inuse_chunk(m, v, nb); |
1479 | set_size_and_pinuse_of_inuse_chunk(m, v, nb); |
1480 | set_size_and_pinuse_of_free_chunk(r, rsize); |
1480 | set_size_and_pinuse_of_free_chunk(r, rsize); |
1481 | replace_dv(m, r, rsize); |
1481 | replace_dv(m, r, rsize); |
1482 | } |
1482 | } |
1483 | return chunk2mem(v); |
1483 | return chunk2mem(v); |
1484 | } |
1484 | } |
1485 | } |
1485 | } |
1486 | 1486 | ||
1487 | CORRUPTION_ERROR_ACTION(m); |
1487 | CORRUPTION_ERROR_ACTION(m); |
1488 | return 0; |
1488 | return 0; |
1489 | } |
1489 | } |
1490 | 1490 | ||
1491 | /* --------------------------- realloc support --------------------------- */ |
1491 | /* --------------------------- realloc support --------------------------- */ |
1492 | 1492 | ||
1493 | static void* internal_realloc(struct _reent *reent_ptr, mstate m, void* oldmem, size_t bytes) |
1493 | static void* internal_realloc(struct _reent *reent_ptr, mstate m, void* oldmem, size_t bytes) |
1494 | { |
1494 | { |
1495 | if (bytes >= MAX_REQUEST) |
1495 | if (bytes >= MAX_REQUEST) |
1496 | { |
1496 | { |
1497 | MALLOC_FAILURE_ACTION; |
1497 | MALLOC_FAILURE_ACTION; |
1498 | return 0; |
1498 | return 0; |
1499 | } |
1499 | } |
1500 | 1500 | ||
1501 | PREACTION(m); |
1501 | PREACTION(m); |
1502 | { |
1502 | { |
1503 | mchunkptr oldp = mem2chunk(oldmem); |
1503 | mchunkptr oldp = mem2chunk(oldmem); |
1504 | size_t oldsize = chunksize(oldp); |
1504 | size_t oldsize = chunksize(oldp); |
1505 | mchunkptr next = chunk_plus_offset(oldp, oldsize); |
1505 | mchunkptr next = chunk_plus_offset(oldp, oldsize); |
1506 | mchunkptr newp = 0; |
1506 | mchunkptr newp = 0; |
1507 | void* extra = 0; |
1507 | void* extra = 0; |
1508 | 1508 | ||
1509 | /* Try to either shrink or extend into top. Else malloc-copy-free */ |
1509 | /* Try to either shrink or extend into top. Else malloc-copy-free */ |
1510 | 1510 | ||
1511 | if (RTCHECK(ok_address(m, oldp) && ok_inuse(oldp) && |
1511 | if (RTCHECK(ok_address(m, oldp) && ok_inuse(oldp) && |
1512 | ok_next(oldp, next) && ok_pinuse(next))) |
1512 | ok_next(oldp, next) && ok_pinuse(next))) |
1513 | { |
1513 | { |
1514 | size_t nb = request2size(bytes); |
1514 | size_t nb = request2size(bytes); |
1515 | if (is_mmapped(oldp)) |
1515 | if (is_mmapped(oldp)) |
1516 | newp = mmap_resize(m, oldp, nb); |
1516 | newp = mmap_resize(m, oldp, nb); |
1517 | else if (oldsize >= nb) { /* already big enough */ |
1517 | else if (oldsize >= nb) { /* already big enough */ |
1518 | size_t rsize = oldsize - nb; |
1518 | size_t rsize = oldsize - nb; |
1519 | newp = oldp; |
1519 | newp = oldp; |
1520 | if (rsize >= MIN_CHUNK_SIZE) |
1520 | if (rsize >= MIN_CHUNK_SIZE) |
1521 | { |
1521 | { |
1522 | mchunkptr remainder = chunk_plus_offset(newp, nb); |
1522 | mchunkptr remainder = chunk_plus_offset(newp, nb); |
1523 | set_inuse(m, newp, nb); |
1523 | set_inuse(m, newp, nb); |
1524 | set_inuse_and_pinuse(m, remainder, rsize); |
1524 | set_inuse_and_pinuse(m, remainder, rsize); |
1525 | extra = chunk2mem(remainder); |
1525 | extra = chunk2mem(remainder); |
1526 | } |
1526 | } |
1527 | } |
1527 | } |
1528 | else if (next == m->top && oldsize + m->topsize > nb) |
1528 | else if (next == m->top && oldsize + m->topsize > nb) |
1529 | { |
1529 | { |
1530 | /* Expand into top */ |
1530 | /* Expand into top */ |
1531 | size_t newsize = oldsize + m->topsize; |
1531 | size_t newsize = oldsize + m->topsize; |
1532 | size_t newtopsize = newsize - nb; |
1532 | size_t newtopsize = newsize - nb; |
1533 | mchunkptr newtop = chunk_plus_offset(oldp, nb); |
1533 | mchunkptr newtop = chunk_plus_offset(oldp, nb); |
1534 | set_inuse(m, oldp, nb); |
1534 | set_inuse(m, oldp, nb); |
1535 | newtop->head = newtopsize |PINUSE_BIT; |
1535 | newtop->head = newtopsize |PINUSE_BIT; |
1536 | m->top = newtop; |
1536 | m->top = newtop; |
1537 | m->topsize = newtopsize; |
1537 | m->topsize = newtopsize; |
1538 | newp = oldp; |
1538 | newp = oldp; |
1539 | } |
1539 | } |
1540 | } |
1540 | } |
1541 | else { |
1541 | else { |
1542 | USAGE_ERROR_ACTION(m, oldmem); |
1542 | USAGE_ERROR_ACTION(m, oldmem); |
1543 | POSTACTION(m); |
1543 | POSTACTION(m); |
1544 | return 0; |
1544 | return 0; |
1545 | } |
1545 | } |
1546 | #if DEBUG |
1546 | #if DEBUG |
1547 | if (newp != 0) { |
1547 | if (newp != 0) { |
1548 | check_inuse_chunk(m, newp); /* Check requires lock */ |
1548 | check_inuse_chunk(m, newp); /* Check requires lock */ |
1549 | } |
1549 | } |
1550 | #endif |
1550 | #endif |
1551 | 1551 | ||
1552 | POSTACTION(m); |
1552 | POSTACTION(m); |
1553 | 1553 | ||
1554 | if (newp != 0) |
1554 | if (newp != 0) |
1555 | { |
1555 | { |
1556 | if (extra != 0) { |
1556 | if (extra != 0) { |
1557 | _free_r(reent_ptr, extra); |
1557 | _free_r(reent_ptr, extra); |
1558 | } |
1558 | } |
1559 | return chunk2mem(newp); |
1559 | return chunk2mem(newp); |
1560 | } |
1560 | } |
1561 | else |
1561 | else |
1562 | { |
1562 | { |
1563 | void* newmem = _malloc_r(reent_ptr, bytes); |
1563 | void* newmem = _malloc_r(reent_ptr, bytes); |
1564 | if (newmem != 0) { |
1564 | if (newmem != 0) { |
1565 | size_t oc = oldsize - overhead_for(oldp); |
1565 | size_t oc = oldsize - overhead_for(oldp); |
1566 | memcpy(newmem, oldmem, (oc < bytes)? oc : bytes); |
1566 | memcpy(newmem, oldmem, (oc < bytes)? oc : bytes); |
1567 | _free_r(reent_ptr, oldmem); |
1567 | _free_r(reent_ptr, oldmem); |
1568 | } |
1568 | } |
1569 | return newmem; |
1569 | return newmem; |
1570 | } |
1570 | } |
1571 | } |
1571 | } |
1572 | return 0; |
1572 | return 0; |
1573 | } |
1573 | } |
1574 | 1574 | ||
1575 | /* --------------------------- memalign support -------------------------- */ |
1575 | /* --------------------------- memalign support -------------------------- */ |
1576 | 1576 | ||
1577 | static void* internal_memalign(mstate m, size_t alignment, size_t bytes) |
1577 | static void* internal_memalign(mstate m, size_t alignment, size_t bytes) |
1578 | { |
1578 | { |
1579 | if (alignment <= MALLOC_ALIGNMENT) /* Can just use malloc */ |
1579 | if (alignment <= MALLOC_ALIGNMENT) /* Can just use malloc */ |
1580 | return internal_malloc(m, bytes); |
1580 | return internal_malloc(m, bytes); |
1581 | if (alignment < MIN_CHUNK_SIZE) /* must be at least a minimum chunk size */ |
1581 | if (alignment < MIN_CHUNK_SIZE) /* must be at least a minimum chunk size */ |
1582 | alignment = MIN_CHUNK_SIZE; |
1582 | alignment = MIN_CHUNK_SIZE; |
1583 | if ((alignment & (alignment-SIZE_T_ONE)) != 0) {/* Ensure a power of 2 */ |
1583 | if ((alignment & (alignment-SIZE_T_ONE)) != 0) {/* Ensure a power of 2 */ |
1584 | size_t a = MALLOC_ALIGNMENT << 1; |
1584 | size_t a = MALLOC_ALIGNMENT << 1; |
1585 | while (a < alignment) a <<= 1; |
1585 | while (a < alignment) a <<= 1; |
1586 | alignment = a; |
1586 | alignment = a; |
1587 | } |
1587 | } |
1588 | 1588 | ||
1589 | if (bytes >= MAX_REQUEST - alignment) { |
1589 | if (bytes >= MAX_REQUEST - alignment) { |
1590 | if (m != 0) { /* Test isn't needed but avoids compiler warning */ |
1590 | if (m != 0) { /* Test isn't needed but avoids compiler warning */ |
1591 | MALLOC_FAILURE_ACTION; |
1591 | MALLOC_FAILURE_ACTION; |
1592 | } |
1592 | } |
1593 | } |
1593 | } |
1594 | else |
1594 | else |
1595 | { |
1595 | { |
1596 | size_t nb = request2size(bytes); |
1596 | size_t nb = request2size(bytes); |
1597 | size_t req = nb + alignment + MIN_CHUNK_SIZE - CHUNK_OVERHEAD; |
1597 | size_t req = nb + alignment + MIN_CHUNK_SIZE - CHUNK_OVERHEAD; |
1598 | char* mem = (char*)internal_malloc(m, req); |
1598 | char* mem = (char*)internal_malloc(m, req); |
1599 | if (mem != 0) |
1599 | if (mem != 0) |
1600 | { |
1600 | { |
1601 | void* leader = 0; |
1601 | void* leader = 0; |
1602 | void* trailer = 0; |
1602 | void* trailer = 0; |
1603 | mchunkptr p = mem2chunk(mem); |
1603 | mchunkptr p = mem2chunk(mem); |
1604 | 1604 | ||
1605 | PREACTION(m); |
1605 | PREACTION(m); |
1606 | 1606 | ||
1607 | if ((((size_t)(mem)) % alignment) != 0) /* misaligned */ |
1607 | if ((((size_t)(mem)) % alignment) != 0) /* misaligned */ |
1608 | { |
1608 | { |
1609 | /* |
1609 | /* |
1610 | Find an aligned spot inside chunk. Since we need to give |
1610 | Find an aligned spot inside chunk. Since we need to give |
1611 | back leading space in a chunk of at least MIN_CHUNK_SIZE, if |
1611 | back leading space in a chunk of at least MIN_CHUNK_SIZE, if |
1612 | the first calculation places us at a spot with less than |
1612 | the first calculation places us at a spot with less than |
1613 | MIN_CHUNK_SIZE leader, we can move to the next aligned spot. |
1613 | MIN_CHUNK_SIZE leader, we can move to the next aligned spot. |
1614 | We've allocated enough total room so that this is always |
1614 | We've allocated enough total room so that this is always |
1615 | possible. |
1615 | possible. |
1616 | */ |
1616 | */ |
1617 | char* br = (char*)mem2chunk((size_t)(((size_t)(mem + |
1617 | char* br = (char*)mem2chunk((size_t)(((size_t)(mem + |
1618 | alignment - |
1618 | alignment - |
1619 | SIZE_T_ONE)) & |
1619 | SIZE_T_ONE)) & |
1620 | -alignment)); |
1620 | -alignment)); |
1621 | char* pos = ((size_t)(br - (char*)(p)) >= MIN_CHUNK_SIZE)? |
1621 | char* pos = ((size_t)(br - (char*)(p)) >= MIN_CHUNK_SIZE)? |
1622 | br : br+alignment; |
1622 | br : br+alignment; |
1623 | mchunkptr newp = (mchunkptr)pos; |
1623 | mchunkptr newp = (mchunkptr)pos; |
1624 | size_t leadsize = pos - (char*)(p); |
1624 | size_t leadsize = pos - (char*)(p); |
1625 | size_t newsize = chunksize(p) - leadsize; |
1625 | size_t newsize = chunksize(p) - leadsize; |
1626 | 1626 | ||
1627 | if (is_mmapped(p)) { /* For mmapped chunks, just adjust offset */ |
1627 | if (is_mmapped(p)) { /* For mmapped chunks, just adjust offset */ |
1628 | newp->prev_foot = p->prev_foot + leadsize; |
1628 | newp->prev_foot = p->prev_foot + leadsize; |
1629 | newp->head = newsize; |
1629 | newp->head = newsize; |
1630 | } |
1630 | } |
1631 | else { /* Otherwise, give back leader, use the rest */ |
1631 | else { /* Otherwise, give back leader, use the rest */ |
1632 | set_inuse(m, newp, newsize); |
1632 | set_inuse(m, newp, newsize); |
1633 | set_inuse(m, p, leadsize); |
1633 | set_inuse(m, p, leadsize); |
1634 | leader = chunk2mem(p); |
1634 | leader = chunk2mem(p); |
1635 | } |
1635 | } |
1636 | p = newp; |
1636 | p = newp; |
1637 | } |
1637 | } |
1638 | 1638 | ||
1639 | /* Give back spare room at the end */ |
1639 | /* Give back spare room at the end */ |
1640 | if (!is_mmapped(p)) |
1640 | if (!is_mmapped(p)) |
1641 | { |
1641 | { |
1642 | size_t size = chunksize(p); |
1642 | size_t size = chunksize(p); |
1643 | if (size > nb + MIN_CHUNK_SIZE) |
1643 | if (size > nb + MIN_CHUNK_SIZE) |
1644 | { |
1644 | { |
1645 | size_t remainder_size = size - nb; |
1645 | size_t remainder_size = size - nb; |
1646 | mchunkptr remainder = chunk_plus_offset(p, nb); |
1646 | mchunkptr remainder = chunk_plus_offset(p, nb); |
1647 | set_inuse(m, p, nb); |
1647 | set_inuse(m, p, nb); |
1648 | set_inuse(m, remainder, remainder_size); |
1648 | set_inuse(m, remainder, remainder_size); |
1649 | trailer = chunk2mem(remainder); |
1649 | trailer = chunk2mem(remainder); |
1650 | } |
1650 | } |
1651 | } |
1651 | } |
1652 | 1652 | ||
1653 | assert (chunksize(p) >= nb); |
1653 | assert (chunksize(p) >= nb); |
1654 | assert((((size_t)(chunk2mem(p))) % alignment) == 0); |
1654 | assert((((size_t)(chunk2mem(p))) % alignment) == 0); |
1655 | check_inuse_chunk(m, p); |
1655 | check_inuse_chunk(m, p); |
1656 | POSTACTION(m); |
1656 | POSTACTION(m); |
1657 | if (leader != 0) { |
1657 | if (leader != 0) { |
1658 | internal_free(m, leader); |
1658 | internal_free(m, leader); |
1659 | } |
1659 | } |
1660 | if (trailer != 0) { |
1660 | if (trailer != 0) { |
1661 | internal_free(m, trailer); |
1661 | internal_free(m, trailer); |
1662 | } |
1662 | } |
1663 | return chunk2mem(p); |
1663 | return chunk2mem(p); |
1664 | } |
1664 | } |
1665 | } |
1665 | } |
1666 | return 0; |
1666 | return 0; |
1667 | } |
1667 | } |
1668 | 1668 | ||
1669 | void* memalign(size_t alignment, size_t bytes) |
1669 | void* memalign(size_t alignment, size_t bytes) |
1670 | { |
1670 | { |
1671 | return internal_memalign(gm, alignment, bytes); |
1671 | return internal_memalign(gm, alignment, bytes); |
1672 | } |
1672 | } |
1673 | 1673 | ||
1674 | 1674 | ||
1675 | 1675 | ||
1676 | void* _malloc_r(struct _reent *reent_ptr, size_t bytes) { |
1676 | void* _malloc_r(struct _reent *reent_ptr, size_t bytes) { |
1677 | /* |
1677 | /* |
1678 | Basic algorithm: |
1678 | Basic algorithm: |
1679 | If a small request (< 256 bytes minus per-chunk overhead): |
1679 | If a small request (< 256 bytes minus per-chunk overhead): |
1680 | 1. If one exists, use a remainderless chunk in associated smallbin. |
1680 | 1. If one exists, use a remainderless chunk in associated smallbin. |
1681 | (Remainderless means that there are too few excess bytes to |
1681 | (Remainderless means that there are too few excess bytes to |
1682 | represent as a chunk.) |
1682 | represent as a chunk.) |
1683 | 2. If it is big enough, use the dv chunk, which is normally the |
1683 | 2. If it is big enough, use the dv chunk, which is normally the |
1684 | chunk adjacent to the one used for the most recent small request. |
1684 | chunk adjacent to the one used for the most recent small request. |
1685 | 3. If one exists, split the smallest available chunk in a bin, |
1685 | 3. If one exists, split the smallest available chunk in a bin, |
1686 | saving remainder in dv. |
1686 | saving remainder in dv. |
1687 | 4. If it is big enough, use the top chunk. |
1687 | 4. If it is big enough, use the top chunk. |
1688 | 5. If available, get memory from system and use it |
1688 | 5. If available, get memory from system and use it |
1689 | Otherwise, for a large request: |
1689 | Otherwise, for a large request: |
1690 | 1. Find the smallest available binned chunk that fits, and use it |
1690 | 1. Find the smallest available binned chunk that fits, and use it |
1691 | if it is better fitting than dv chunk, splitting if necessary. |
1691 | if it is better fitting than dv chunk, splitting if necessary. |
1692 | 2. If better fitting than any binned chunk, use the dv chunk. |
1692 | 2. If better fitting than any binned chunk, use the dv chunk. |
1693 | 3. If it is big enough, use the top chunk. |
1693 | 3. If it is big enough, use the top chunk. |
1694 | 4. If request size >= mmap threshold, try to directly mmap this chunk. |
1694 | 4. If request size >= mmap threshold, try to directly mmap this chunk. |
1695 | 5. If available, get memory from system and use it |
1695 | 5. If available, get memory from system and use it |
1696 | 1696 | ||
1697 | The ugly goto's here ensure that postaction occurs along all paths. |
1697 | The ugly goto's here ensure that postaction occurs along all paths. |
1698 | */ |
1698 | */ |
1699 | 1699 | ||
1700 | ensure_initialization(); /* initialize in sys_alloc if not using locks */ |
1700 | ensure_initialization(); /* initialize in sys_alloc if not using locks */ |
1701 | 1701 | ||
1702 | PREACTION(gm); |
1702 | PREACTION(gm); |
1703 | { |
1703 | { |
1704 | void* mem; |
1704 | void* mem; |
1705 | size_t nb; |
1705 | size_t nb; |
1706 | 1706 | ||
1707 | if (bytes <= MAX_SMALL_REQUEST) |
1707 | if (bytes <= MAX_SMALL_REQUEST) |
1708 | { |
1708 | { |
1709 | bindex_t idx; |
1709 | bindex_t idx; |
1710 | binmap_t smallbits; |
1710 | binmap_t smallbits; |
1711 | nb = (bytes < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(bytes); |
1711 | nb = (bytes < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(bytes); |
1712 | idx = small_index(nb); |
1712 | idx = small_index(nb); |
1713 | smallbits = gm->smallmap >> idx; |
1713 | smallbits = gm->smallmap >> idx; |
1714 | 1714 | ||
1715 | if ((smallbits & 0x3U) != 0) /* Remainderless fit to a smallbin. */ |
1715 | if ((smallbits & 0x3U) != 0) /* Remainderless fit to a smallbin. */ |
1716 | { |
1716 | { |
1717 | mchunkptr b, p; |
1717 | mchunkptr b, p; |
1718 | idx += ~smallbits & 1; /* Uses next bin if idx empty */ |
1718 | idx += ~smallbits & 1; /* Uses next bin if idx empty */ |
1719 | b = smallbin_at(gm, idx); |
1719 | b = smallbin_at(gm, idx); |
1720 | p = b->fd; |
1720 | p = b->fd; |
1721 | assert(chunksize(p) == small_index2size(idx)); |
1721 | assert(chunksize(p) == small_index2size(idx)); |
1722 | unlink_first_small_chunk(gm, b, p, idx); |
1722 | unlink_first_small_chunk(gm, b, p, idx); |
1723 | set_inuse_and_pinuse(gm, p, small_index2size(idx)); |
1723 | set_inuse_and_pinuse(gm, p, small_index2size(idx)); |
1724 | mem = chunk2mem(p); |
1724 | mem = chunk2mem(p); |
1725 | check_malloced_chunk(gm, mem, nb); |
1725 | check_malloced_chunk(gm, mem, nb); |
1726 | goto postaction; |
1726 | goto postaction; |
1727 | } |
1727 | } |
1728 | else if (nb > gm->dvsize) |
1728 | else if (nb > gm->dvsize) |
1729 | { |
1729 | { |
1730 | if (smallbits != 0) /* Use chunk in next nonempty smallbin */ |
1730 | if (smallbits != 0) /* Use chunk in next nonempty smallbin */ |
1731 | { |
1731 | { |
1732 | mchunkptr b, p, r; |
1732 | mchunkptr b, p, r; |
1733 | size_t rsize; |
1733 | size_t rsize; |
1734 | bindex_t i; |
1734 | bindex_t i; |
1735 | binmap_t leftbits = (smallbits << idx) & left_bits(idx2bit(idx)); |
1735 | binmap_t leftbits = (smallbits << idx) & left_bits(idx2bit(idx)); |
1736 | binmap_t leastbit = least_bit(leftbits); |
1736 | binmap_t leastbit = least_bit(leftbits); |
1737 | compute_bit2idx(leastbit, i); |
1737 | compute_bit2idx(leastbit, i); |
1738 | b = smallbin_at(gm, i); |
1738 | b = smallbin_at(gm, i); |
1739 | p = b->fd; |
1739 | p = b->fd; |
1740 | assert(chunksize(p) == small_index2size(i)); |
1740 | assert(chunksize(p) == small_index2size(i)); |
1741 | unlink_first_small_chunk(gm, b, p, i); |
1741 | unlink_first_small_chunk(gm, b, p, i); |
1742 | rsize = small_index2size(i) - nb; |
1742 | rsize = small_index2size(i) - nb; |
1743 | /* Fit here cannot be remainderless if 4byte sizes */ |
1743 | /* Fit here cannot be remainderless if 4byte sizes */ |
1744 | if (SIZE_T_SIZE != 4 && rsize < MIN_CHUNK_SIZE) |
1744 | if (SIZE_T_SIZE != 4 && rsize < MIN_CHUNK_SIZE) |
1745 | set_inuse_and_pinuse(gm, p, small_index2size(i)); |
1745 | set_inuse_and_pinuse(gm, p, small_index2size(i)); |
1746 | else |
1746 | else |
1747 | { |
1747 | { |
1748 | set_size_and_pinuse_of_inuse_chunk(gm, p, nb); |
1748 | set_size_and_pinuse_of_inuse_chunk(gm, p, nb); |
1749 | r = chunk_plus_offset(p, nb); |
1749 | r = chunk_plus_offset(p, nb); |
1750 | set_size_and_pinuse_of_free_chunk(r, rsize); |
1750 | set_size_and_pinuse_of_free_chunk(r, rsize); |
1751 | replace_dv(gm, r, rsize); |
1751 | replace_dv(gm, r, rsize); |
1752 | } |
1752 | } |
1753 | mem = chunk2mem(p); |
1753 | mem = chunk2mem(p); |
1754 | check_malloced_chunk(gm, mem, nb); |
1754 | check_malloced_chunk(gm, mem, nb); |
1755 | goto postaction; |
1755 | goto postaction; |
1756 | } |
1756 | } |
1757 | else if (gm->treemap != 0 && (mem = tmalloc_small(gm, nb)) != 0) |
1757 | else if (gm->treemap != 0 && (mem = tmalloc_small(gm, nb)) != 0) |
1758 | { |
1758 | { |
1759 | check_malloced_chunk(gm, mem, nb); |
1759 | check_malloced_chunk(gm, mem, nb); |
1760 | goto postaction; |
1760 | goto postaction; |
1761 | } |
1761 | } |
1762 | } |
1762 | } |
1763 | } |
1763 | } |
1764 | else if (bytes >= MAX_REQUEST) |
1764 | else if (bytes >= MAX_REQUEST) |
1765 | nb = MAX_SIZE_T; /* Too big to allocate. Force failure (in sys alloc) */ |
1765 | nb = MAX_SIZE_T; /* Too big to allocate. Force failure (in sys alloc) */ |
1766 | else |
1766 | else |
1767 | { |
1767 | { |
1768 | nb = pad_request(bytes); |
1768 | nb = pad_request(bytes); |
1769 | if (gm->treemap != 0 && (mem = tmalloc_large(gm, nb)) != 0) |
1769 | if (gm->treemap != 0 && (mem = tmalloc_large(gm, nb)) != 0) |
1770 | { |
1770 | { |
1771 | check_malloced_chunk(gm, mem, nb); |
1771 | check_malloced_chunk(gm, mem, nb); |
1772 | goto postaction; |
1772 | goto postaction; |
1773 | } |
1773 | } |
1774 | } |
1774 | } |
1775 | 1775 | ||
1776 | if (nb <= gm->dvsize) { |
1776 | if (nb <= gm->dvsize) { |
1777 | size_t rsize = gm->dvsize - nb; |
1777 | size_t rsize = gm->dvsize - nb; |
1778 | mchunkptr p = gm->dv; |
1778 | mchunkptr p = gm->dv; |
1779 | if (rsize >= MIN_CHUNK_SIZE) { /* split dv */ |
1779 | if (rsize >= MIN_CHUNK_SIZE) { /* split dv */ |
1780 | mchunkptr r = gm->dv = chunk_plus_offset(p, nb); |
1780 | mchunkptr r = gm->dv = chunk_plus_offset(p, nb); |
1781 | gm->dvsize = rsize; |
1781 | gm->dvsize = rsize; |
1782 | set_size_and_pinuse_of_free_chunk(r, rsize); |
1782 | set_size_and_pinuse_of_free_chunk(r, rsize); |
1783 | set_size_and_pinuse_of_inuse_chunk(gm, p, nb); |
1783 | set_size_and_pinuse_of_inuse_chunk(gm, p, nb); |
1784 | } |
1784 | } |
1785 | else { /* exhaust dv */ |
1785 | else { /* exhaust dv */ |
1786 | size_t dvs = gm->dvsize; |
1786 | size_t dvs = gm->dvsize; |
1787 | gm->dvsize = 0; |
1787 | gm->dvsize = 0; |
1788 | gm->dv = 0; |
1788 | gm->dv = 0; |
1789 | set_inuse_and_pinuse(gm, p, dvs); |
1789 | set_inuse_and_pinuse(gm, p, dvs); |
1790 | } |
1790 | } |
1791 | mem = chunk2mem(p); |
1791 | mem = chunk2mem(p); |
1792 | check_malloced_chunk(gm, mem, nb); |
1792 | check_malloced_chunk(gm, mem, nb); |
1793 | goto postaction; |
1793 | goto postaction; |
1794 | } |
1794 | } |
1795 | else if (nb < gm->topsize) { /* Split top */ |
1795 | else if (nb < gm->topsize) { /* Split top */ |
1796 | size_t rsize = gm->topsize -= nb; |
1796 | size_t rsize = gm->topsize -= nb; |
1797 | mchunkptr p = gm->top; |
1797 | mchunkptr p = gm->top; |
1798 | mchunkptr r = gm->top = chunk_plus_offset(p, nb); |
1798 | mchunkptr r = gm->top = chunk_plus_offset(p, nb); |
1799 | r->head = rsize | PINUSE_BIT; |
1799 | r->head = rsize | PINUSE_BIT; |
1800 | set_size_and_pinuse_of_inuse_chunk(gm, p, nb); |
1800 | set_size_and_pinuse_of_inuse_chunk(gm, p, nb); |
1801 | mem = chunk2mem(p); |
1801 | mem = chunk2mem(p); |
1802 | check_top_chunk(gm, gm->top); |
1802 | check_top_chunk(gm, gm->top); |
1803 | check_malloced_chunk(gm, mem, nb); |
1803 | check_malloced_chunk(gm, mem, nb); |
1804 | goto postaction; |
1804 | goto postaction; |
1805 | } |
1805 | } |
1806 | 1806 | ||
1807 | mem = sys_alloc(gm, nb); |
1807 | mem = sys_alloc(gm, nb); |
1808 | 1808 | ||
1809 | postaction: |
1809 | postaction: |
1810 | POSTACTION(gm); |
1810 | POSTACTION(gm); |
1811 | return mem; |
1811 | return mem; |
1812 | } |
1812 | } |
1813 | 1813 | ||
1814 | return 0; |
1814 | return 0; |
1815 | } |
1815 | } |
1816 | 1816 | ||
1817 | void _free_r(struct _reent *reent_ptr, void* mem) { |
1817 | void _free_r(struct _reent *reent_ptr, void* mem) { |
1818 | /* |
1818 | /* |
1819 | Consolidate freed chunks with preceeding or succeeding bordering |
1819 | Consolidate freed chunks with preceeding or succeeding bordering |
1820 | free chunks, if they exist, and then place in a bin. Intermixed |
1820 | free chunks, if they exist, and then place in a bin. Intermixed |
1821 | with special cases for top, dv, mmapped chunks, and usage errors. |
1821 | with special cases for top, dv, mmapped chunks, and usage errors. |
1822 | */ |
1822 | */ |
1823 | 1823 | ||
1824 | if (mem != 0) |
1824 | if (mem != 0) |
1825 | { |
1825 | { |
1826 | mchunkptr p = mem2chunk(mem); |
1826 | mchunkptr p = mem2chunk(mem); |
1827 | 1827 | ||
1828 | #define fm gm |
1828 | #define fm gm |
1829 | 1829 | ||
1830 | PREACTION(fm); |
1830 | PREACTION(fm); |
1831 | { |
1831 | { |
1832 | check_inuse_chunk(fm, p); |
1832 | check_inuse_chunk(fm, p); |
1833 | if (RTCHECK(ok_address(fm, p) && ok_inuse(p))) |
1833 | if (RTCHECK(ok_address(fm, p) && ok_inuse(p))) |
1834 | { |
1834 | { |
1835 | size_t psize = chunksize(p); |
1835 | size_t psize = chunksize(p); |
1836 | mchunkptr next = chunk_plus_offset(p, psize); |
1836 | mchunkptr next = chunk_plus_offset(p, psize); |
1837 | if (!pinuse(p)) |
1837 | if (!pinuse(p)) |
1838 | { |
1838 | { |
1839 | size_t prevsize = p->prev_foot; |
1839 | size_t prevsize = p->prev_foot; |
1840 | if (is_mmapped(p)) |
1840 | if (is_mmapped(p)) |
1841 | { |
1841 | { |
1842 | psize += prevsize + MMAP_FOOT_PAD; |
1842 | psize += prevsize + MMAP_FOOT_PAD; |
1843 | if (CALL_MUNMAP((char*)p - prevsize, psize) == 0) |
1843 | if (CALL_MUNMAP((char*)p - prevsize, psize) == 0) |
1844 | fm->footprint -= psize; |
1844 | fm->footprint -= psize; |
1845 | goto postaction; |
1845 | goto postaction; |
1846 | } |
1846 | } |
1847 | else |
1847 | else |
1848 | { |
1848 | { |
1849 | mchunkptr prev = chunk_minus_offset(p, prevsize); |
1849 | mchunkptr prev = chunk_minus_offset(p, prevsize); |
1850 | psize += prevsize; |
1850 | psize += prevsize; |
1851 | p = prev; |
1851 | p = prev; |
1852 | if (RTCHECK(ok_address(fm, prev))) /* consolidate backward */ |
1852 | if (RTCHECK(ok_address(fm, prev))) /* consolidate backward */ |
1853 | { |
1853 | { |
1854 | if (p != fm->dv) |
1854 | if (p != fm->dv) |
1855 | { |
1855 | { |
1856 | unlink_chunk(fm, p, prevsize); |
1856 | unlink_chunk(fm, p, prevsize); |
1857 | } |
1857 | } |
1858 | else if ((next->head & INUSE_BITS) == INUSE_BITS) |
1858 | else if ((next->head & INUSE_BITS) == INUSE_BITS) |
1859 | { |
1859 | { |
1860 | fm->dvsize = psize; |
1860 | fm->dvsize = psize; |
1861 | set_free_with_pinuse(p, psize, next); |
1861 | set_free_with_pinuse(p, psize, next); |
1862 | goto postaction; |
1862 | goto postaction; |
1863 | } |
1863 | } |
1864 | } |
1864 | } |
1865 | else |
1865 | else |
1866 | goto erroraction; |
1866 | goto erroraction; |
1867 | } |
1867 | } |
1868 | } |
1868 | } |
1869 | 1869 | ||
1870 | if (RTCHECK(ok_next(p, next) && ok_pinuse(next))) |
1870 | if (RTCHECK(ok_next(p, next) && ok_pinuse(next))) |
1871 | { |
1871 | { |
1872 | if (!cinuse(next)) /* consolidate forward */ |
1872 | if (!cinuse(next)) /* consolidate forward */ |
1873 | { |
1873 | { |
1874 | if (next == fm->top) |
1874 | if (next == fm->top) |
1875 | { |
1875 | { |
1876 | size_t tsize = fm->topsize += psize; |
1876 | size_t tsize = fm->topsize += psize; |
1877 | fm->top = p; |
1877 | fm->top = p; |
1878 | p->head = tsize | PINUSE_BIT; |
1878 | p->head = tsize | PINUSE_BIT; |
1879 | if (p == fm->dv) |
1879 | if (p == fm->dv) |
1880 | { |
1880 | { |
1881 | fm->dv = 0; |
1881 | fm->dv = 0; |
1882 | fm->dvsize = 0; |
1882 | fm->dvsize = 0; |
1883 | } |
1883 | } |
1884 | if (should_trim(fm, tsize)) |
1884 | if (should_trim(fm, tsize)) |
1885 | sys_trim(fm, 0); |
1885 | sys_trim(fm, 0); |
1886 | goto postaction; |
1886 | goto postaction; |
1887 | } |
1887 | } |
1888 | else if (next == fm->dv) |
1888 | else if (next == fm->dv) |
1889 | { |
1889 | { |
1890 | size_t dsize = fm->dvsize += psize; |
1890 | size_t dsize = fm->dvsize += psize; |
1891 | fm->dv = p; |
1891 | fm->dv = p; |
1892 | set_size_and_pinuse_of_free_chunk(p, dsize); |
1892 | set_size_and_pinuse_of_free_chunk(p, dsize); |
1893 | goto postaction; |
1893 | goto postaction; |
1894 | } |
1894 | } |
1895 | else |
1895 | else |
1896 | { |
1896 | { |
1897 | size_t nsize = chunksize(next); |
1897 | size_t nsize = chunksize(next); |
1898 | psize += nsize; |
1898 | psize += nsize; |
1899 | unlink_chunk(fm, next, nsize); |
1899 | unlink_chunk(fm, next, nsize); |
1900 | set_size_and_pinuse_of_free_chunk(p, psize); |
1900 | set_size_and_pinuse_of_free_chunk(p, psize); |
1901 | if (p == fm->dv) |
1901 | if (p == fm->dv) |
1902 | { |
1902 | { |
1903 | fm->dvsize = psize; |
1903 | fm->dvsize = psize; |
1904 | goto postaction; |
1904 | goto postaction; |
1905 | } |
1905 | } |
1906 | } |
1906 | } |
1907 | } |
1907 | } |
1908 | else |
1908 | else |
1909 | set_free_with_pinuse(p, psize, next); |
1909 | set_free_with_pinuse(p, psize, next); |
1910 | 1910 | ||
1911 | if (is_small(psize)) |
1911 | if (is_small(psize)) |
1912 | { |
1912 | { |
1913 | insert_small_chunk(fm, p, psize); |
1913 | insert_small_chunk(fm, p, psize); |
1914 | check_free_chunk(fm, p); |
1914 | check_free_chunk(fm, p); |
1915 | } |
1915 | } |
1916 | else |
1916 | else |
1917 | { |
1917 | { |
1918 | tchunkptr tp = (tchunkptr)p; |
1918 | tchunkptr tp = (tchunkptr)p; |
1919 | insert_large_chunk(fm, tp, psize); |
1919 | insert_large_chunk(fm, tp, psize); |
1920 | check_free_chunk(fm, p); |
1920 | check_free_chunk(fm, p); |
1921 | if (--fm->release_checks == 0) |
1921 | if (--fm->release_checks == 0) |
1922 | release_unused_segments(fm); |
1922 | release_unused_segments(fm); |
1923 | } |
1923 | } |
1924 | goto postaction; |
1924 | goto postaction; |
1925 | } |
1925 | } |
1926 | } |
1926 | } |
1927 | erroraction: |
1927 | erroraction: |
1928 | USAGE_ERROR_ACTION(fm, p); |
1928 | USAGE_ERROR_ACTION(fm, p); |
1929 | postaction: |
1929 | postaction: |
1930 | POSTACTION(fm); |
1930 | POSTACTION(fm); |
1931 | } |
1931 | } |
1932 | } |
1932 | } |
1933 | #undef fm |
1933 | #undef fm |
1934 | } |
1934 | } |
1935 | 1935 | ||
1936 | void* _calloc_r(struct _reent *reent_ptr, size_t n_elements, size_t elem_size) { |
1936 | void* _calloc_r(struct _reent *reent_ptr, size_t n_elements, size_t elem_size) { |
1937 | void* mem; |
1937 | void* mem; |
1938 | size_t req = 0; |
1938 | size_t req = 0; |
1939 | if (n_elements != 0) { |
1939 | if (n_elements != 0) { |
1940 | req = n_elements * elem_size; |
1940 | req = n_elements * elem_size; |
1941 | if (((n_elements | elem_size) & ~(size_t)0xffff) && |
1941 | if (((n_elements | elem_size) & ~(size_t)0xffff) && |
1942 | (req / n_elements != elem_size)) |
1942 | (req / n_elements != elem_size)) |
1943 | req = MAX_SIZE_T; /* force downstream failure on overflow */ |
1943 | req = MAX_SIZE_T; /* force downstream failure on overflow */ |
1944 | } |
1944 | } |
1945 | mem = _malloc_r(reent_ptr, req); |
1945 | mem = _malloc_r(reent_ptr, req); |
1946 | if (mem != 0 && calloc_must_clear(mem2chunk(mem))) |
1946 | if (mem != 0 && calloc_must_clear(mem2chunk(mem))) |
1947 | memset(mem, 0, req); |
1947 | memset(mem, 0, req); |
1948 | return mem; |
1948 | return mem; |
1949 | } |
1949 | } |
1950 | 1950 | ||
1951 | void* _realloc_r (struct _reent *reent_ptr, void* oldmem, size_t bytes){ |
1951 | void* _realloc_r (struct _reent *reent_ptr, void* oldmem, size_t bytes){ |
1952 | if (oldmem == 0) |
1952 | if (oldmem == 0) |
1953 | return _malloc_r(reent_ptr, bytes); |
1953 | return _malloc_r(reent_ptr, bytes); |
1954 | #ifdef REALLOC_ZERO_BYTES_FREES |
1954 | #ifdef REALLOC_ZERO_BYTES_FREES |
1955 | if (bytes == 0) { |
1955 | if (bytes == 0) { |
1956 | _free_r(ptr, oldmem); |
1956 | _free_r(ptr, oldmem); |
1957 | return 0; |
1957 | return 0; |
1958 | } |
1958 | } |
1959 | #endif /* REALLOC_ZERO_BYTES_FREES */ |
1959 | #endif /* REALLOC_ZERO_BYTES_FREES */ |
1960 | else { |
1960 | else { |
1961 | #if ! FOOTERS |
1961 | #if ! FOOTERS |
1962 | mstate m = gm; |
1962 | mstate m = gm; |
1963 | #else /* FOOTERS */ |
1963 | #else /* FOOTERS */ |
1964 | mstate m = get_mstate_for(mem2chunk(oldmem)); |
1964 | mstate m = get_mstate_for(mem2chunk(oldmem)); |
1965 | if (!ok_magic(m)) { |
1965 | if (!ok_magic(m)) { |
1966 | USAGE_ERROR_ACTION(m, oldmem); |
1966 | USAGE_ERROR_ACTION(m, oldmem); |
1967 | return 0; |
1967 | return 0; |
1968 | } |
1968 | } |
1969 | #endif /* FOOTERS */ |
1969 | #endif /* FOOTERS */ |
1970 | return internal_realloc(reent_ptr, m, oldmem, bytes); |
1970 | return internal_realloc(reent_ptr, m, oldmem, bytes); |
1971 | } |
1971 | } |
1972 | } |
1972 | } |
1973 | 1973 | ||
1974 | 1974 | ||
1975 | 1975 | ||
1976 | /* ----------------------------------------------------------------------- |
1976 | /* ----------------------------------------------------------------------- |
1977 | History: |
1977 | History: |
1978 | V2.8.4 Wed May 27 09:56:23 2009 Doug Lea (dl at gee) |
1978 | V2.8.4 Wed May 27 09:56:23 2009 Doug Lea (dl at gee) |
1979 | * Use zeros instead of prev foot for is_mmapped |
1979 | * Use zeros instead of prev foot for is_mmapped |
1980 | * Add mspace_track_large_chunks; thanks to Jean Brouwers |
1980 | * Add mspace_track_large_chunks; thanks to Jean Brouwers |
1981 | * Fix set_inuse in internal_realloc; thanks to Jean Brouwers |
1981 | * Fix set_inuse in internal_realloc; thanks to Jean Brouwers |
1982 | * Fix insufficient sys_alloc padding when using 16byte alignment |
1982 | * Fix insufficient sys_alloc padding when using 16byte alignment |
1983 | * Fix bad error check in mspace_footprint |
1983 | * Fix bad error check in mspace_footprint |
1984 | * Adaptations for ptmalloc; thanks to Wolfram Gloger. |
1984 | * Adaptations for ptmalloc; thanks to Wolfram Gloger. |
1985 | * Reentrant spin locks; thanks to Earl Chew and others |
1985 | * Reentrant spin locks; thanks to Earl Chew and others |
1986 | * Win32 improvements; thanks to Niall Douglas and Earl Chew |
1986 | * Win32 improvements; thanks to Niall Douglas and Earl Chew |
1987 | * Add NO_SEGMENT_TRAVERSAL and MAX_RELEASE_CHECK_RATE options |
1987 | * Add NO_SEGMENT_TRAVERSAL and MAX_RELEASE_CHECK_RATE options |
1988 | * Extension hook in malloc_state |
1988 | * Extension hook in malloc_state |
1989 | * Various small adjustments to reduce warnings on some compilers |
1989 | * Various small adjustments to reduce warnings on some compilers |
1990 | * Various configuration extensions/changes for more platforms. Thanks |
1990 | * Various configuration extensions/changes for more platforms. Thanks |
1991 | to all who contributed these. |
1991 | to all who contributed these. |
1992 | 1992 | ||
1993 | V2.8.3 Thu Sep 22 11:16:32 2005 Doug Lea (dl at gee) |
1993 | V2.8.3 Thu Sep 22 11:16:32 2005 Doug Lea (dl at gee) |
1994 | * Add max_footprint functions |
1994 | * Add max_footprint functions |
1995 | * Ensure all appropriate literals are size_t |
1995 | * Ensure all appropriate literals are size_t |
1996 | * Fix conditional compilation problem for some #define settings |
1996 | * Fix conditional compilation problem for some #define settings |
1997 | * Avoid concatenating segments with the one provided |
1997 | * Avoid concatenating segments with the one provided |
1998 | in create_mspace_with_base |
1998 | in create_mspace_with_base |
1999 | * Rename some variables to avoid compiler shadowing warnings |
1999 | * Rename some variables to avoid compiler shadowing warnings |
2000 | * Use explicit lock initialization. |
2000 | * Use explicit lock initialization. |
2001 | * Better handling of sbrk interference. |
2001 | * Better handling of sbrk interference. |
2002 | * Simplify and fix segment insertion, trimming and mspace_destroy |
2002 | * Simplify and fix segment insertion, trimming and mspace_destroy |
2003 | * Reinstate REALLOC_ZERO_BYTES_FREES option from 2.7.x |
2003 | * Reinstate REALLOC_ZERO_BYTES_FREES option from 2.7.x |
2004 | * Thanks especially to Dennis Flanagan for help on these. |
2004 | * Thanks especially to Dennis Flanagan for help on these. |
2005 | 2005 | ||
2006 | V2.8.2 Sun Jun 12 16:01:10 2005 Doug Lea (dl at gee) |
2006 | V2.8.2 Sun Jun 12 16:01:10 2005 Doug Lea (dl at gee) |
2007 | * Fix memalign brace error. |
2007 | * Fix memalign brace error. |
2008 | 2008 | ||
2009 | V2.8.1 Wed Jun 8 16:11:46 2005 Doug Lea (dl at gee) |
2009 | V2.8.1 Wed Jun 8 16:11:46 2005 Doug Lea (dl at gee) |
2010 | * Fix improper #endif nesting in C++ |
2010 | * Fix improper #endif nesting in C++ |
2011 | * Add explicit casts needed for C++ |
2011 | * Add explicit casts needed for C++ |
2012 | 2012 | ||
2013 | V2.8.0 Mon May 30 14:09:02 2005 Doug Lea (dl at gee) |
2013 | V2.8.0 Mon May 30 14:09:02 2005 Doug Lea (dl at gee) |
2014 | * Use trees for large bins |
2014 | * Use trees for large bins |
2015 | * Support mspaces |
2015 | * Support mspaces |
2016 | * Use segments to unify sbrk-based and mmap-based system allocation, |
2016 | * Use segments to unify sbrk-based and mmap-based system allocation, |
2017 | removing need for emulation on most platforms without sbrk. |
2017 | removing need for emulation on most platforms without sbrk. |
2018 | * Default safety checks |
2018 | * Default safety checks |
2019 | * Optional footer checks. Thanks to William Robertson for the idea. |
2019 | * Optional footer checks. Thanks to William Robertson for the idea. |
2020 | * Internal code refactoring |
2020 | * Internal code refactoring |
2021 | * Incorporate suggestions and platform-specific changes. |
2021 | * Incorporate suggestions and platform-specific changes. |
2022 | Thanks to Dennis Flanagan, Colin Plumb, Niall Douglas, |
2022 | Thanks to Dennis Flanagan, Colin Plumb, Niall Douglas, |
2023 | Aaron Bachmann, Emery Berger, and others. |
2023 | Aaron Bachmann, Emery Berger, and others. |
2024 | * Speed up non-fastbin processing enough to remove fastbins. |
2024 | * Speed up non-fastbin processing enough to remove fastbins. |
2025 | * Remove useless cfree() to avoid conflicts with other apps. |
2025 | * Remove useless cfree() to avoid conflicts with other apps. |
2026 | * Remove internal memcpy, memset. Compilers handle builtins better. |
2026 | * Remove internal memcpy, memset. Compilers handle builtins better. |
2027 | * Remove some options that no one ever used and rename others. |
2027 | * Remove some options that no one ever used and rename others. |
2028 | 2028 | ||
2029 | V2.7.2 Sat Aug 17 09:07:30 2002 Doug Lea (dl at gee) |
2029 | V2.7.2 Sat Aug 17 09:07:30 2002 Doug Lea (dl at gee) |
2030 | * Fix malloc_state bitmap array misdeclaration |
2030 | * Fix malloc_state bitmap array misdeclaration |
2031 | 2031 | ||
2032 | V2.7.1 Thu Jul 25 10:58:03 2002 Doug Lea (dl at gee) |
2032 | V2.7.1 Thu Jul 25 10:58:03 2002 Doug Lea (dl at gee) |
2033 | * Allow tuning of FIRST_SORTED_BIN_SIZE |
2033 | * Allow tuning of FIRST_SORTED_BIN_SIZE |
2034 | * Use PTR_UINT as type for all ptr->int casts. Thanks to John Belmonte. |
2034 | * Use PTR_UINT as type for all ptr->int casts. Thanks to John Belmonte. |
2035 | * Better detection and support for non-contiguousness of MORECORE. |
2035 | * Better detection and support for non-contiguousness of MORECORE. |
2036 | Thanks to Andreas Mueller, Conal Walsh, and Wolfram Gloger |
2036 | Thanks to Andreas Mueller, Conal Walsh, and Wolfram Gloger |
2037 | * Bypass most of malloc if no frees. Thanks To Emery Berger. |
2037 | * Bypass most of malloc if no frees. Thanks To Emery Berger. |
2038 | * Fix freeing of old top non-contiguous chunk im sysmalloc. |
2038 | * Fix freeing of old top non-contiguous chunk im sysmalloc. |
2039 | * Raised default trim and map thresholds to 256K. |
2039 | * Raised default trim and map thresholds to 256K. |
2040 | * Fix mmap-related #defines. Thanks to Lubos Lunak. |
2040 | * Fix mmap-related #defines. Thanks to Lubos Lunak. |
2041 | * Fix copy macros; added LACKS_FCNTL_H. Thanks to Neal Walfield. |
2041 | * Fix copy macros; added LACKS_FCNTL_H. Thanks to Neal Walfield. |
2042 | * Branch-free bin calculation |
2042 | * Branch-free bin calculation |
2043 | * Default trim and mmap thresholds now 256K. |
2043 | * Default trim and mmap thresholds now 256K. |
2044 | 2044 | ||
2045 | V2.7.0 Sun Mar 11 14:14:06 2001 Doug Lea (dl at gee) |
2045 | V2.7.0 Sun Mar 11 14:14:06 2001 Doug Lea (dl at gee) |
2046 | * Introduce independent_comalloc and independent_calloc. |
2046 | * Introduce independent_comalloc and independent_calloc. |
2047 | Thanks to Michael Pachos for motivation and help. |
2047 | Thanks to Michael Pachos for motivation and help. |
2048 | * Make optional .h file available |
2048 | * Make optional .h file available |
2049 | * Allow > 2GB requests on 32bit systems. |
2049 | * Allow > 2GB requests on 32bit systems. |
2050 | * new WIN32 sbrk, mmap, munmap, lock code from |
2050 | * new WIN32 sbrk, mmap, munmap, lock code from |
2051 | Thanks also to Andreas Mueller |
2051 | Thanks also to Andreas Mueller |
2052 | and Anonymous. |
2052 | and Anonymous. |
2053 | * Allow override of MALLOC_ALIGNMENT (Thanks to Ruud Waij for |
2053 | * Allow override of MALLOC_ALIGNMENT (Thanks to Ruud Waij for |
2054 | helping test this.) |
2054 | helping test this.) |
2055 | * memalign: check alignment arg |
2055 | * memalign: check alignment arg |
2056 | * realloc: don't try to shift chunks backwards, since this |
2056 | * realloc: don't try to shift chunks backwards, since this |
2057 | leads to more fragmentation in some programs and doesn't |
2057 | leads to more fragmentation in some programs and doesn't |
2058 | seem to help in any others. |
2058 | seem to help in any others. |
2059 | * Collect all cases in malloc requiring system memory into sysmalloc |
2059 | * Collect all cases in malloc requiring system memory into sysmalloc |
2060 | * Use mmap as backup to sbrk |
2060 | * Use mmap as backup to sbrk |
2061 | * Place all internal state in malloc_state |
2061 | * Place all internal state in malloc_state |
2062 | * Introduce fastbins (although similar to 2.5.1) |
2062 | * Introduce fastbins (although similar to 2.5.1) |
2063 | * Many minor tunings and cosmetic improvements |
2063 | * Many minor tunings and cosmetic improvements |
2064 | * Introduce USE_PUBLIC_MALLOC_WRAPPERS, USE_MALLOC_LOCK |
2064 | * Introduce USE_PUBLIC_MALLOC_WRAPPERS, USE_MALLOC_LOCK |
2065 | * Introduce MALLOC_FAILURE_ACTION, MORECORE_CONTIGUOUS |
2065 | * Introduce MALLOC_FAILURE_ACTION, MORECORE_CONTIGUOUS |
2066 | Thanks to Tony E. Bennett |
2066 | Thanks to Tony E. Bennett |
2067 | * Include errno.h to support default failure action. |
2067 | * Include errno.h to support default failure action. |
2068 | 2068 | ||
2069 | V2.6.6 Sun Dec 5 07:42:19 1999 Doug Lea (dl at gee) |
2069 | V2.6.6 Sun Dec 5 07:42:19 1999 Doug Lea (dl at gee) |
2070 | * return null for negative arguments |
2070 | * return null for negative arguments |
2071 | * Added Several WIN32 cleanups from Martin C. Fong |
2071 | * Added Several WIN32 cleanups from Martin C. Fong |
2072 | * Add 'LACKS_SYS_PARAM_H' for those systems without 'sys/param.h' |
2072 | * Add 'LACKS_SYS_PARAM_H' for those systems without 'sys/param.h' |
2073 | (e.g. WIN32 platforms) |
2073 | (e.g. WIN32 platforms) |
2074 | * Cleanup header file inclusion for WIN32 platforms |
2074 | * Cleanup header file inclusion for WIN32 platforms |
2075 | * Cleanup code to avoid Microsoft Visual C++ compiler complaints |
2075 | * Cleanup code to avoid Microsoft Visual C++ compiler complaints |
2076 | * Add 'USE_DL_PREFIX' to quickly allow co-existence with existing |
2076 | * Add 'USE_DL_PREFIX' to quickly allow co-existence with existing |
2077 | memory allocation routines |
2077 | memory allocation routines |
2078 | * Set 'malloc_getpagesize' for WIN32 platforms (needs more work) |
2078 | * Set 'malloc_getpagesize' for WIN32 platforms (needs more work) |
2079 | * Use 'assert' rather than 'ASSERT' in WIN32 code to conform to |
2079 | * Use 'assert' rather than 'ASSERT' in WIN32 code to conform to |
2080 | usage of 'assert' in non-WIN32 code |
2080 | usage of 'assert' in non-WIN32 code |
2081 | * Improve WIN32 'sbrk()' emulation's 'findRegion()' routine to |
2081 | * Improve WIN32 'sbrk()' emulation's 'findRegion()' routine to |
2082 | avoid infinite loop |
2082 | avoid infinite loop |
2083 | * Always call 'fREe()' rather than 'free()' |
2083 | * Always call 'fREe()' rather than 'free()' |
2084 | 2084 | ||
2085 | V2.6.5 Wed Jun 17 15:57:31 1998 Doug Lea (dl at gee) |
2085 | V2.6.5 Wed Jun 17 15:57:31 1998 Doug Lea (dl at gee) |
2086 | * Fixed ordering problem with boundary-stamping |
2086 | * Fixed ordering problem with boundary-stamping |
2087 | 2087 | ||
2088 | V2.6.3 Sun May 19 08:17:58 1996 Doug Lea (dl at gee) |
2088 | V2.6.3 Sun May 19 08:17:58 1996 Doug Lea (dl at gee) |
2089 | * Added pvalloc, as recommended by H.J. Liu |
2089 | * Added pvalloc, as recommended by H.J. Liu |
2090 | * Added 64bit pointer support mainly from Wolfram Gloger |
2090 | * Added 64bit pointer support mainly from Wolfram Gloger |
2091 | * Added anonymously donated WIN32 sbrk emulation |
2091 | * Added anonymously donated WIN32 sbrk emulation |
2092 | * Malloc, calloc, getpagesize: add optimizations from Raymond Nijssen |
2092 | * Malloc, calloc, getpagesize: add optimizations from Raymond Nijssen |
2093 | * malloc_extend_top: fix mask error that caused wastage after |
2093 | * malloc_extend_top: fix mask error that caused wastage after |
2094 | foreign sbrks |
2094 | foreign sbrks |
2095 | * Add linux mremap support code from HJ Liu |
2095 | * Add linux mremap support code from HJ Liu |
2096 | 2096 | ||
2097 | V2.6.2 Tue Dec 5 06:52:55 1995 Doug Lea (dl at gee) |
2097 | V2.6.2 Tue Dec 5 06:52:55 1995 Doug Lea (dl at gee) |
2098 | * Integrated most documentation with the code. |
2098 | * Integrated most documentation with the code. |
2099 | * Add support for mmap, with help from |
2099 | * Add support for mmap, with help from |
2100 | Wolfram Gloger (Gloger@lrz.uni-muenchen.de). |
2100 | Wolfram Gloger (Gloger@lrz.uni-muenchen.de). |
2101 | * Use last_remainder in more cases. |
2101 | * Use last_remainder in more cases. |
2102 | * Pack bins using idea from colin@nyx10.cs.du.edu |
2102 | * Pack bins using idea from colin@nyx10.cs.du.edu |
2103 | * Use ordered bins instead of best-fit threshhold |
2103 | * Use ordered bins instead of best-fit threshhold |
2104 | * Eliminate block-local decls to simplify tracing and debugging. |
2104 | * Eliminate block-local decls to simplify tracing and debugging. |
2105 | * Support another case of realloc via move into top |
2105 | * Support another case of realloc via move into top |
2106 | * Fix error occuring when initial sbrk_base not word-aligned. |
2106 | * Fix error occuring when initial sbrk_base not word-aligned. |
2107 | * Rely on page size for units instead of SBRK_UNIT to |
2107 | * Rely on page size for units instead of SBRK_UNIT to |
2108 | avoid surprises about sbrk alignment conventions. |
2108 | avoid surprises about sbrk alignment conventions. |
2109 | * Add mallinfo, mallopt. Thanks to Raymond Nijssen |
2109 | * Add mallinfo, mallopt. Thanks to Raymond Nijssen |
2110 | (raymond@es.ele.tue.nl) for the suggestion. |
2110 | (raymond@es.ele.tue.nl) for the suggestion. |
2111 | * Add `pad' argument to malloc_trim and top_pad mallopt parameter. |
2111 | * Add `pad' argument to malloc_trim and top_pad mallopt parameter. |
2112 | * More precautions for cases where other routines call sbrk, |
2112 | * More precautions for cases where other routines call sbrk, |
2113 | courtesy of Wolfram Gloger (Gloger@lrz.uni-muenchen.de). |
2113 | courtesy of Wolfram Gloger (Gloger@lrz.uni-muenchen.de). |
2114 | * Added macros etc., allowing use in linux libc from |
2114 | * Added macros etc., allowing use in linux libc from |
2115 | H.J. Lu (hjl@gnu.ai.mit.edu) |
2115 | H.J. Lu (hjl@gnu.ai.mit.edu) |
2116 | * Inverted this history list |
2116 | * Inverted this history list |
2117 | 2117 | ||
2118 | V2.6.1 Sat Dec 2 14:10:57 1995 Doug Lea (dl at gee) |
2118 | V2.6.1 Sat Dec 2 14:10:57 1995 Doug Lea (dl at gee) |
2119 | * Re-tuned and fixed to behave more nicely with V2.6.0 changes. |
2119 | * Re-tuned and fixed to behave more nicely with V2.6.0 changes. |
2120 | * Removed all preallocation code since under current scheme |
2120 | * Removed all preallocation code since under current scheme |
2121 | the work required to undo bad preallocations exceeds |
2121 | the work required to undo bad preallocations exceeds |
2122 | the work saved in good cases for most test programs. |
2122 | the work saved in good cases for most test programs. |
2123 | * No longer use return list or unconsolidated bins since |
2123 | * No longer use return list or unconsolidated bins since |
2124 | no scheme using them consistently outperforms those that don't |
2124 | no scheme using them consistently outperforms those that don't |
2125 | given above changes. |
2125 | given above changes. |
2126 | * Use best fit for very large chunks to prevent some worst-cases. |
2126 | * Use best fit for very large chunks to prevent some worst-cases. |
2127 | * Added some support for debugging |
2127 | * Added some support for debugging |
2128 | 2128 | ||
2129 | V2.6.0 Sat Nov 4 07:05:23 1995 Doug Lea (dl at gee) |
2129 | V2.6.0 Sat Nov 4 07:05:23 1995 Doug Lea (dl at gee) |
2130 | * Removed footers when chunks are in use. Thanks to |
2130 | * Removed footers when chunks are in use. Thanks to |
2131 | Paul Wilson (wilson@cs.texas.edu) for the suggestion. |
2131 | Paul Wilson (wilson@cs.texas.edu) for the suggestion. |
2132 | 2132 | ||
2133 | V2.5.4 Wed Nov 1 07:54:51 1995 Doug Lea (dl at gee) |
2133 | V2.5.4 Wed Nov 1 07:54:51 1995 Doug Lea (dl at gee) |
2134 | * Added malloc_trim, with help from Wolfram Gloger |
2134 | * Added malloc_trim, with help from Wolfram Gloger |
2135 | (wmglo@Dent.MED.Uni-Muenchen.DE). |
2135 | (wmglo@Dent.MED.Uni-Muenchen.DE). |
2136 | 2136 | ||
2137 | V2.5.3 Tue Apr 26 10:16:01 1994 Doug Lea (dl at g) |
2137 | V2.5.3 Tue Apr 26 10:16:01 1994 Doug Lea (dl at g) |
2138 | 2138 | ||
2139 | V2.5.2 Tue Apr 5 16:20:40 1994 Doug Lea (dl at g) |
2139 | V2.5.2 Tue Apr 5 16:20:40 1994 Doug Lea (dl at g) |
2140 | * realloc: try to expand in both directions |
2140 | * realloc: try to expand in both directions |
2141 | * malloc: swap order of clean-bin strategy; |
2141 | * malloc: swap order of clean-bin strategy; |
2142 | * realloc: only conditionally expand backwards |
2142 | * realloc: only conditionally expand backwards |
2143 | * Try not to scavenge used bins |
2143 | * Try not to scavenge used bins |
2144 | * Use bin counts as a guide to preallocation |
2144 | * Use bin counts as a guide to preallocation |
2145 | * Occasionally bin return list chunks in first scan |
2145 | * Occasionally bin return list chunks in first scan |
2146 | * Add a few optimizations from colin@nyx10.cs.du.edu |
2146 | * Add a few optimizations from colin@nyx10.cs.du.edu |
2147 | 2147 | ||
2148 | V2.5.1 Sat Aug 14 15:40:43 1993 Doug Lea (dl at g) |
2148 | V2.5.1 Sat Aug 14 15:40:43 1993 Doug Lea (dl at g) |
2149 | * faster bin computation & slightly different binning |
2149 | * faster bin computation & slightly different binning |
2150 | * merged all consolidations to one part of malloc proper |
2150 | * merged all consolidations to one part of malloc proper |
2151 | (eliminating old malloc_find_space & malloc_clean_bin) |
2151 | (eliminating old malloc_find_space & malloc_clean_bin) |
2152 | * Scan 2 returns chunks (not just 1) |
2152 | * Scan 2 returns chunks (not just 1) |
2153 | * Propagate failure in realloc if malloc returns 0 |
2153 | * Propagate failure in realloc if malloc returns 0 |
2154 | * Add stuff to allow compilation on non-ANSI compilers |
2154 | * Add stuff to allow compilation on non-ANSI compilers |
2155 | from kpv@research.att.com |
2155 | from kpv@research.att.com |
2156 | 2156 | ||
2157 | V2.5 Sat Aug 7 07:41:59 1993 Doug Lea (dl at g.oswego.edu) |
2157 | V2.5 Sat Aug 7 07:41:59 1993 Doug Lea (dl at g.oswego.edu) |
2158 | * removed potential for odd address access in prev_chunk |
2158 | * removed potential for odd address access in prev_chunk |
2159 | * removed dependency on getpagesize.h |
2159 | * removed dependency on getpagesize.h |
2160 | * misc cosmetics and a bit more internal documentation |
2160 | * misc cosmetics and a bit more internal documentation |
2161 | * anticosmetics: mangled names in macros to evade debugger strangeness |
2161 | * anticosmetics: mangled names in macros to evade debugger strangeness |
2162 | * tested on sparc, hp-700, dec-mips, rs6000 |
2162 | * tested on sparc, hp-700, dec-mips, rs6000 |
2163 | with gcc & native cc (hp, dec only) allowing |
2163 | with gcc & native cc (hp, dec only) allowing |
2164 | Detlefs & Zorn comparison study (in SIGPLAN Notices.) |
2164 | Detlefs & Zorn comparison study (in SIGPLAN Notices.) |
2165 | 2165 | ||
2166 | Trial version Fri Aug 28 13:14:29 1992 Doug Lea (dl at g.oswego.edu) |
2166 | Trial version Fri Aug 28 13:14:29 1992 Doug Lea (dl at g.oswego.edu) |
2167 | * Based loosely on libg++-1.2X malloc. (It retains some of the overall |
2167 | * Based loosely on libg++-1.2X malloc. (It retains some of the overall |
2168 | structure of old version, but most details differ.) |
2168 | structure of old version, but most details differ.) |
2169 | 2169 | ||
2170 | */>=>>><>>=>>=><=>>><>>=>>>>>>>=><=>>><>>>>>>>>>><>=>>>>>=><=>><>>1)) |
2170 | */>=>>><>>=>>=><=>>><>>=>>>>>>>=><=>>><>>>>>>>>>><>=>>>>>=><=>><>>1)) |
2171 | 2171 | ||
2172 | /*><1)) |
2172 | /*><1)) |
2173 | 2173 | ||
2174 | /*>1)><1)>><>><>><>><>1]))) |
2174 | /*>1)><1)>><>><>><>><>1]))) |
2175 | #define><1]))) |
2175 | #define><1]))) |
2176 | #define>><>>><>><>>><>2) |
2176 | #define>><>>><>><>>><>2) |
2177 | #define><2) |
2177 | #define><2) |
2178 | #define>1) |
2178 | #define>1) |
2179 | #define><1) |
2179 | #define><1) |
2180 | #define>><> |
2180 | #define>><> |