]>
Commit | Line | Data |
---|---|---|
217c9dad WD |
1 | #if 0 /* Moved to malloc.h */ |
2 | /* ---------- To make a malloc.h, start cutting here ------------ */ | |
3 | ||
4 | /* | |
5 | A version of malloc/free/realloc written by Doug Lea and released to the | |
6 | public domain. Send questions/comments/complaints/performance data | |
7 | to dl@cs.oswego.edu | |
8 | ||
9 | * VERSION 2.6.6 Sun Mar 5 19:10:03 2000 Doug Lea (dl at gee) | |
10 | ||
11 | Note: There may be an updated version of this malloc obtainable at | |
8bde7f77 WD |
12 | ftp://g.oswego.edu/pub/misc/malloc.c |
13 | Check before installing! | |
217c9dad WD |
14 | |
15 | * Why use this malloc? | |
16 | ||
17 | This is not the fastest, most space-conserving, most portable, or | |
18 | most tunable malloc ever written. However it is among the fastest | |
19 | while also being among the most space-conserving, portable and tunable. | |
20 | Consistent balance across these factors results in a good general-purpose | |
21 | allocator. For a high-level description, see | |
22 | http://g.oswego.edu/dl/html/malloc.html | |
23 | ||
24 | * Synopsis of public routines | |
25 | ||
26 | (Much fuller descriptions are contained in the program documentation below.) | |
27 | ||
28 | malloc(size_t n); | |
29 | Return a pointer to a newly allocated chunk of at least n bytes, or null | |
30 | if no space is available. | |
31 | free(Void_t* p); | |
32 | Release the chunk of memory pointed to by p, or no effect if p is null. | |
33 | realloc(Void_t* p, size_t n); | |
34 | Return a pointer to a chunk of size n that contains the same data | |
35 | as does chunk p up to the minimum of (n, p's size) bytes, or null | |
36 | if no space is available. The returned pointer may or may not be | |
37 | the same as p. If p is null, equivalent to malloc. Unless the | |
38 | #define REALLOC_ZERO_BYTES_FREES below is set, realloc with a | |
39 | size argument of zero (re)allocates a minimum-sized chunk. | |
40 | memalign(size_t alignment, size_t n); | |
41 | Return a pointer to a newly allocated chunk of n bytes, aligned | |
42 | in accord with the alignment argument, which must be a power of | |
43 | two. | |
44 | valloc(size_t n); | |
45 | Equivalent to memalign(pagesize, n), where pagesize is the page | |
46 | size of the system (or as near to this as can be figured out from | |
47 | all the includes/defines below.) | |
48 | pvalloc(size_t n); | |
49 | Equivalent to valloc(minimum-page-that-holds(n)), that is, | |
50 | round up n to nearest pagesize. | |
51 | calloc(size_t unit, size_t quantity); | |
52 | Returns a pointer to quantity * unit bytes, with all locations | |
53 | set to zero. | |
54 | cfree(Void_t* p); | |
55 | Equivalent to free(p). | |
56 | malloc_trim(size_t pad); | |
57 | Release all but pad bytes of freed top-most memory back | |
58 | to the system. Return 1 if successful, else 0. | |
59 | malloc_usable_size(Void_t* p); | |
60 | Report the number usable allocated bytes associated with allocated | |
61 | chunk p. This may or may not report more bytes than were requested, | |
62 | due to alignment and minimum size constraints. | |
63 | malloc_stats(); | |
64 | Prints brief summary statistics. | |
65 | mallinfo() | |
66 | Returns (by copy) a struct containing various summary statistics. | |
67 | mallopt(int parameter_number, int parameter_value) | |
68 | Changes one of the tunable parameters described below. Returns | |
69 | 1 if successful in changing the parameter, else 0. | |
70 | ||
71 | * Vital statistics: | |
72 | ||
73 | Alignment: 8-byte | |
74 | 8 byte alignment is currently hardwired into the design. This | |
75 | seems to suffice for all current machines and C compilers. | |
76 | ||
77 | Assumed pointer representation: 4 or 8 bytes | |
78 | Code for 8-byte pointers is untested by me but has worked | |
79 | reliably by Wolfram Gloger, who contributed most of the | |
80 | changes supporting this. | |
81 | ||
82 | Assumed size_t representation: 4 or 8 bytes | |
83 | Note that size_t is allowed to be 4 bytes even if pointers are 8. | |
84 | ||
85 | Minimum overhead per allocated chunk: 4 or 8 bytes | |
86 | Each malloced chunk has a hidden overhead of 4 bytes holding size | |
87 | and status information. | |
88 | ||
89 | Minimum allocated size: 4-byte ptrs: 16 bytes (including 4 overhead) | |
8bde7f77 | 90 | 8-byte ptrs: 24/32 bytes (including, 4/8 overhead) |
217c9dad WD |
91 | |
92 | When a chunk is freed, 12 (for 4byte ptrs) or 20 (for 8 byte | |
93 | ptrs but 4 byte size) or 24 (for 8/8) additional bytes are | |
94 | needed; 4 (8) for a trailing size field | |
95 | and 8 (16) bytes for free list pointers. Thus, the minimum | |
96 | allocatable size is 16/24/32 bytes. | |
97 | ||
98 | Even a request for zero bytes (i.e., malloc(0)) returns a | |
99 | pointer to something of the minimum allocatable size. | |
100 | ||
101 | Maximum allocated size: 4-byte size_t: 2^31 - 8 bytes | |
8bde7f77 | 102 | 8-byte size_t: 2^63 - 16 bytes |
217c9dad WD |
103 | |
104 | It is assumed that (possibly signed) size_t bit values suffice to | |
105 | represent chunk sizes. `Possibly signed' is due to the fact | |
106 | that `size_t' may be defined on a system as either a signed or | |
107 | an unsigned type. To be conservative, values that would appear | |
108 | as negative numbers are avoided. | |
109 | Requests for sizes with a negative sign bit when the request | |
110 | size is treaded as a long will return null. | |
111 | ||
112 | Maximum overhead wastage per allocated chunk: normally 15 bytes | |
113 | ||
114 | Alignnment demands, plus the minimum allocatable size restriction | |
115 | make the normal worst-case wastage 15 bytes (i.e., up to 15 | |
116 | more bytes will be allocated than were requested in malloc), with | |
117 | two exceptions: | |
8bde7f77 WD |
118 | 1. Because requests for zero bytes allocate non-zero space, |
119 | the worst case wastage for a request of zero bytes is 24 bytes. | |
120 | 2. For requests >= mmap_threshold that are serviced via | |
121 | mmap(), the worst case wastage is 8 bytes plus the remainder | |
122 | from a system page (the minimal mmap unit); typically 4096 bytes. | |
217c9dad WD |
123 | |
124 | * Limitations | |
125 | ||
126 | Here are some features that are NOT currently supported | |
127 | ||
128 | * No user-definable hooks for callbacks and the like. | |
129 | * No automated mechanism for fully checking that all accesses | |
130 | to malloced memory stay within their bounds. | |
131 | * No support for compaction. | |
132 | ||
133 | * Synopsis of compile-time options: | |
134 | ||
135 | People have reported using previous versions of this malloc on all | |
136 | versions of Unix, sometimes by tweaking some of the defines | |
137 | below. It has been tested most extensively on Solaris and | |
138 | Linux. It is also reported to work on WIN32 platforms. | |
139 | People have also reported adapting this malloc for use in | |
140 | stand-alone embedded systems. | |
141 | ||
142 | The implementation is in straight, hand-tuned ANSI C. Among other | |
143 | consequences, it uses a lot of macros. Because of this, to be at | |
144 | all usable, this code should be compiled using an optimizing compiler | |
145 | (for example gcc -O2) that can simplify expressions and control | |
146 | paths. | |
147 | ||
148 | __STD_C (default: derived from C compiler defines) | |
149 | Nonzero if using ANSI-standard C compiler, a C++ compiler, or | |
150 | a C compiler sufficiently close to ANSI to get away with it. | |
151 | DEBUG (default: NOT defined) | |
152 | Define to enable debugging. Adds fairly extensive assertion-based | |
153 | checking to help track down memory errors, but noticeably slows down | |
154 | execution. | |
155 | REALLOC_ZERO_BYTES_FREES (default: NOT defined) | |
156 | Define this if you think that realloc(p, 0) should be equivalent | |
157 | to free(p). Otherwise, since malloc returns a unique pointer for | |
158 | malloc(0), so does realloc(p, 0). | |
159 | HAVE_MEMCPY (default: defined) | |
160 | Define if you are not otherwise using ANSI STD C, but still | |
161 | have memcpy and memset in your C library and want to use them. | |
162 | Otherwise, simple internal versions are supplied. | |
163 | USE_MEMCPY (default: 1 if HAVE_MEMCPY is defined, 0 otherwise) | |
164 | Define as 1 if you want the C library versions of memset and | |
165 | memcpy called in realloc and calloc (otherwise macro versions are used). | |
166 | At least on some platforms, the simple macro versions usually | |
167 | outperform libc versions. | |
168 | HAVE_MMAP (default: defined as 1) | |
169 | Define to non-zero to optionally make malloc() use mmap() to | |
170 | allocate very large blocks. | |
171 | HAVE_MREMAP (default: defined as 0 unless Linux libc set) | |
172 | Define to non-zero to optionally make realloc() use mremap() to | |
173 | reallocate very large blocks. | |
174 | malloc_getpagesize (default: derived from system #includes) | |
175 | Either a constant or routine call returning the system page size. | |
176 | HAVE_USR_INCLUDE_MALLOC_H (default: NOT defined) | |
177 | Optionally define if you are on a system with a /usr/include/malloc.h | |
178 | that declares struct mallinfo. It is not at all necessary to | |
179 | define this even if you do, but will ensure consistency. | |
180 | INTERNAL_SIZE_T (default: size_t) | |
181 | Define to a 32-bit type (probably `unsigned int') if you are on a | |
182 | 64-bit machine, yet do not want or need to allow malloc requests of | |
183 | greater than 2^31 to be handled. This saves space, especially for | |
184 | very small chunks. | |
185 | INTERNAL_LINUX_C_LIB (default: NOT defined) | |
186 | Defined only when compiled as part of Linux libc. | |
187 | Also note that there is some odd internal name-mangling via defines | |
188 | (for example, internally, `malloc' is named `mALLOc') needed | |
189 | when compiling in this case. These look funny but don't otherwise | |
190 | affect anything. | |
191 | WIN32 (default: undefined) | |
192 | Define this on MS win (95, nt) platforms to compile in sbrk emulation. | |
193 | LACKS_UNISTD_H (default: undefined if not WIN32) | |
194 | Define this if your system does not have a <unistd.h>. | |
195 | LACKS_SYS_PARAM_H (default: undefined if not WIN32) | |
196 | Define this if your system does not have a <sys/param.h>. | |
197 | MORECORE (default: sbrk) | |
198 | The name of the routine to call to obtain more memory from the system. | |
199 | MORECORE_FAILURE (default: -1) | |
200 | The value returned upon failure of MORECORE. | |
201 | MORECORE_CLEARS (default 1) | |
202 | True (1) if the routine mapped to MORECORE zeroes out memory (which | |
203 | holds for sbrk). | |
204 | DEFAULT_TRIM_THRESHOLD | |
205 | DEFAULT_TOP_PAD | |
206 | DEFAULT_MMAP_THRESHOLD | |
207 | DEFAULT_MMAP_MAX | |
208 | Default values of tunable parameters (described in detail below) | |
209 | controlling interaction with host system routines (sbrk, mmap, etc). | |
210 | These values may also be changed dynamically via mallopt(). The | |
211 | preset defaults are those that give best performance for typical | |
212 | programs/systems. | |
213 | USE_DL_PREFIX (default: undefined) | |
214 | Prefix all public routines with the string 'dl'. Useful to | |
215 | quickly avoid procedure declaration conflicts and linker symbol | |
216 | conflicts with existing memory allocation routines. | |
217 | ||
218 | ||
219 | */ | |
220 | ||
221 | \f | |
222 | ||
223 | ||
224 | /* Preliminaries */ | |
225 | ||
226 | #ifndef __STD_C | |
227 | #ifdef __STDC__ | |
228 | #define __STD_C 1 | |
229 | #else | |
230 | #if __cplusplus | |
231 | #define __STD_C 1 | |
232 | #else | |
233 | #define __STD_C 0 | |
234 | #endif /*__cplusplus*/ | |
235 | #endif /*__STDC__*/ | |
236 | #endif /*__STD_C*/ | |
237 | ||
238 | #ifndef Void_t | |
239 | #if (__STD_C || defined(WIN32)) | |
240 | #define Void_t void | |
241 | #else | |
242 | #define Void_t char | |
243 | #endif | |
244 | #endif /*Void_t*/ | |
245 | ||
246 | #if __STD_C | |
247 | #include <stddef.h> /* for size_t */ | |
248 | #else | |
249 | #include <sys/types.h> | |
250 | #endif | |
251 | ||
252 | #ifdef __cplusplus | |
253 | extern "C" { | |
254 | #endif | |
255 | ||
256 | #include <stdio.h> /* needed for malloc_stats */ | |
257 | ||
258 | ||
259 | /* | |
260 | Compile-time options | |
261 | */ | |
262 | ||
263 | ||
264 | /* | |
265 | Debugging: | |
266 | ||
267 | Because freed chunks may be overwritten with link fields, this | |
268 | malloc will often die when freed memory is overwritten by user | |
269 | programs. This can be very effective (albeit in an annoying way) | |
270 | in helping track down dangling pointers. | |
271 | ||
272 | If you compile with -DDEBUG, a number of assertion checks are | |
273 | enabled that will catch more memory errors. You probably won't be | |
274 | able to make much sense of the actual assertion errors, but they | |
275 | should help you locate incorrectly overwritten memory. The | |
276 | checking is fairly extensive, and will slow down execution | |
277 | noticeably. Calling malloc_stats or mallinfo with DEBUG set will | |
278 | attempt to check every non-mmapped allocated and free chunk in the | |
279 | course of computing the summmaries. (By nature, mmapped regions | |
280 | cannot be checked very much automatically.) | |
281 | ||
282 | Setting DEBUG may also be helpful if you are trying to modify | |
283 | this code. The assertions in the check routines spell out in more | |
284 | detail the assumptions and invariants underlying the algorithms. | |
285 | ||
286 | */ | |
287 | ||
288 | #ifdef DEBUG | |
289 | #include <assert.h> | |
290 | #else | |
291 | #define assert(x) ((void)0) | |
292 | #endif | |
293 | ||
294 | ||
295 | /* | |
296 | INTERNAL_SIZE_T is the word-size used for internal bookkeeping | |
297 | of chunk sizes. On a 64-bit machine, you can reduce malloc | |
298 | overhead by defining INTERNAL_SIZE_T to be a 32 bit `unsigned int' | |
299 | at the expense of not being able to handle requests greater than | |
300 | 2^31. This limitation is hardly ever a concern; you are encouraged | |
301 | to set this. However, the default version is the same as size_t. | |
302 | */ | |
303 | ||
304 | #ifndef INTERNAL_SIZE_T | |
305 | #define INTERNAL_SIZE_T size_t | |
306 | #endif | |
307 | ||
308 | /* | |
309 | REALLOC_ZERO_BYTES_FREES should be set if a call to | |
310 | realloc with zero bytes should be the same as a call to free. | |
311 | Some people think it should. Otherwise, since this malloc | |
312 | returns a unique pointer for malloc(0), so does realloc(p, 0). | |
313 | */ | |
314 | ||
315 | ||
316 | /* #define REALLOC_ZERO_BYTES_FREES */ | |
317 | ||
318 | ||
319 | /* | |
320 | WIN32 causes an emulation of sbrk to be compiled in | |
321 | mmap-based options are not currently supported in WIN32. | |
322 | */ | |
323 | ||
324 | /* #define WIN32 */ | |
325 | #ifdef WIN32 | |
326 | #define MORECORE wsbrk | |
327 | #define HAVE_MMAP 0 | |
328 | ||
329 | #define LACKS_UNISTD_H | |
330 | #define LACKS_SYS_PARAM_H | |
331 | ||
332 | /* | |
333 | Include 'windows.h' to get the necessary declarations for the | |
334 | Microsoft Visual C++ data structures and routines used in the 'sbrk' | |
335 | emulation. | |
336 | ||
337 | Define WIN32_LEAN_AND_MEAN so that only the essential Microsoft | |
338 | Visual C++ header files are included. | |
339 | */ | |
340 | #define WIN32_LEAN_AND_MEAN | |
341 | #include <windows.h> | |
342 | #endif | |
343 | ||
344 | ||
345 | /* | |
346 | HAVE_MEMCPY should be defined if you are not otherwise using | |
347 | ANSI STD C, but still have memcpy and memset in your C library | |
348 | and want to use them in calloc and realloc. Otherwise simple | |
349 | macro versions are defined here. | |
350 | ||
351 | USE_MEMCPY should be defined as 1 if you actually want to | |
352 | have memset and memcpy called. People report that the macro | |
353 | versions are often enough faster than libc versions on many | |
354 | systems that it is better to use them. | |
355 | ||
356 | */ | |
357 | ||
358 | #define HAVE_MEMCPY | |
359 | ||
360 | #ifndef USE_MEMCPY | |
361 | #ifdef HAVE_MEMCPY | |
362 | #define USE_MEMCPY 1 | |
363 | #else | |
364 | #define USE_MEMCPY 0 | |
365 | #endif | |
366 | #endif | |
367 | ||
368 | #if (__STD_C || defined(HAVE_MEMCPY)) | |
369 | ||
370 | #if __STD_C | |
371 | void* memset(void*, int, size_t); | |
372 | void* memcpy(void*, const void*, size_t); | |
373 | #else | |
374 | #ifdef WIN32 | |
8bde7f77 WD |
375 | /* On Win32 platforms, 'memset()' and 'memcpy()' are already declared in */ |
376 | /* 'windows.h' */ | |
217c9dad WD |
377 | #else |
378 | Void_t* memset(); | |
379 | Void_t* memcpy(); | |
380 | #endif | |
381 | #endif | |
382 | #endif | |
383 | ||
384 | #if USE_MEMCPY | |
385 | ||
386 | /* The following macros are only invoked with (2n+1)-multiples of | |
387 | INTERNAL_SIZE_T units, with a positive integer n. This is exploited | |
388 | for fast inline execution when n is small. */ | |
389 | ||
390 | #define MALLOC_ZERO(charp, nbytes) \ | |
391 | do { \ | |
392 | INTERNAL_SIZE_T mzsz = (nbytes); \ | |
393 | if(mzsz <= 9*sizeof(mzsz)) { \ | |
394 | INTERNAL_SIZE_T* mz = (INTERNAL_SIZE_T*) (charp); \ | |
395 | if(mzsz >= 5*sizeof(mzsz)) { *mz++ = 0; \ | |
8bde7f77 | 396 | *mz++ = 0; \ |
217c9dad | 397 | if(mzsz >= 7*sizeof(mzsz)) { *mz++ = 0; \ |
8bde7f77 WD |
398 | *mz++ = 0; \ |
399 | if(mzsz >= 9*sizeof(mzsz)) { *mz++ = 0; \ | |
400 | *mz++ = 0; }}} \ | |
401 | *mz++ = 0; \ | |
402 | *mz++ = 0; \ | |
403 | *mz = 0; \ | |
217c9dad WD |
404 | } else memset((charp), 0, mzsz); \ |
405 | } while(0) | |
406 | ||
407 | #define MALLOC_COPY(dest,src,nbytes) \ | |
408 | do { \ | |
409 | INTERNAL_SIZE_T mcsz = (nbytes); \ | |
410 | if(mcsz <= 9*sizeof(mcsz)) { \ | |
411 | INTERNAL_SIZE_T* mcsrc = (INTERNAL_SIZE_T*) (src); \ | |
412 | INTERNAL_SIZE_T* mcdst = (INTERNAL_SIZE_T*) (dest); \ | |
413 | if(mcsz >= 5*sizeof(mcsz)) { *mcdst++ = *mcsrc++; \ | |
8bde7f77 | 414 | *mcdst++ = *mcsrc++; \ |
217c9dad | 415 | if(mcsz >= 7*sizeof(mcsz)) { *mcdst++ = *mcsrc++; \ |
8bde7f77 WD |
416 | *mcdst++ = *mcsrc++; \ |
417 | if(mcsz >= 9*sizeof(mcsz)) { *mcdst++ = *mcsrc++; \ | |
418 | *mcdst++ = *mcsrc++; }}} \ | |
419 | *mcdst++ = *mcsrc++; \ | |
420 | *mcdst++ = *mcsrc++; \ | |
421 | *mcdst = *mcsrc ; \ | |
217c9dad WD |
422 | } else memcpy(dest, src, mcsz); \ |
423 | } while(0) | |
424 | ||
425 | #else /* !USE_MEMCPY */ | |
426 | ||
427 | /* Use Duff's device for good zeroing/copying performance. */ | |
428 | ||
429 | #define MALLOC_ZERO(charp, nbytes) \ | |
430 | do { \ | |
431 | INTERNAL_SIZE_T* mzp = (INTERNAL_SIZE_T*)(charp); \ | |
432 | long mctmp = (nbytes)/sizeof(INTERNAL_SIZE_T), mcn; \ | |
433 | if (mctmp < 8) mcn = 0; else { mcn = (mctmp-1)/8; mctmp %= 8; } \ | |
434 | switch (mctmp) { \ | |
435 | case 0: for(;;) { *mzp++ = 0; \ | |
436 | case 7: *mzp++ = 0; \ | |
437 | case 6: *mzp++ = 0; \ | |
438 | case 5: *mzp++ = 0; \ | |
439 | case 4: *mzp++ = 0; \ | |
440 | case 3: *mzp++ = 0; \ | |
441 | case 2: *mzp++ = 0; \ | |
442 | case 1: *mzp++ = 0; if(mcn <= 0) break; mcn--; } \ | |
443 | } \ | |
444 | } while(0) | |
445 | ||
446 | #define MALLOC_COPY(dest,src,nbytes) \ | |
447 | do { \ | |
448 | INTERNAL_SIZE_T* mcsrc = (INTERNAL_SIZE_T*) src; \ | |
449 | INTERNAL_SIZE_T* mcdst = (INTERNAL_SIZE_T*) dest; \ | |
450 | long mctmp = (nbytes)/sizeof(INTERNAL_SIZE_T), mcn; \ | |
451 | if (mctmp < 8) mcn = 0; else { mcn = (mctmp-1)/8; mctmp %= 8; } \ | |
452 | switch (mctmp) { \ | |
453 | case 0: for(;;) { *mcdst++ = *mcsrc++; \ | |
454 | case 7: *mcdst++ = *mcsrc++; \ | |
455 | case 6: *mcdst++ = *mcsrc++; \ | |
456 | case 5: *mcdst++ = *mcsrc++; \ | |
457 | case 4: *mcdst++ = *mcsrc++; \ | |
458 | case 3: *mcdst++ = *mcsrc++; \ | |
459 | case 2: *mcdst++ = *mcsrc++; \ | |
460 | case 1: *mcdst++ = *mcsrc++; if(mcn <= 0) break; mcn--; } \ | |
461 | } \ | |
462 | } while(0) | |
463 | ||
464 | #endif | |
465 | ||
466 | ||
467 | /* | |
468 | Define HAVE_MMAP to optionally make malloc() use mmap() to | |
469 | allocate very large blocks. These will be returned to the | |
470 | operating system immediately after a free(). | |
471 | */ | |
472 | ||
473 | #ifndef HAVE_MMAP | |
474 | #define HAVE_MMAP 1 | |
475 | #endif | |
476 | ||
477 | /* | |
478 | Define HAVE_MREMAP to make realloc() use mremap() to re-allocate | |
479 | large blocks. This is currently only possible on Linux with | |
480 | kernel versions newer than 1.3.77. | |
481 | */ | |
482 | ||
483 | #ifndef HAVE_MREMAP | |
484 | #ifdef INTERNAL_LINUX_C_LIB | |
485 | #define HAVE_MREMAP 1 | |
486 | #else | |
487 | #define HAVE_MREMAP 0 | |
488 | #endif | |
489 | #endif | |
490 | ||
491 | #if HAVE_MMAP | |
492 | ||
493 | #include <unistd.h> | |
494 | #include <fcntl.h> | |
495 | #include <sys/mman.h> | |
496 | ||
497 | #if !defined(MAP_ANONYMOUS) && defined(MAP_ANON) | |
498 | #define MAP_ANONYMOUS MAP_ANON | |
499 | #endif | |
500 | ||
501 | #endif /* HAVE_MMAP */ | |
502 | ||
503 | /* | |
504 | Access to system page size. To the extent possible, this malloc | |
505 | manages memory from the system in page-size units. | |
506 | ||
507 | The following mechanics for getpagesize were adapted from | |
508 | bsd/gnu getpagesize.h | |
509 | */ | |
510 | ||
511 | #ifndef LACKS_UNISTD_H | |
512 | # include <unistd.h> | |
513 | #endif | |
514 | ||
515 | #ifndef malloc_getpagesize | |
516 | # ifdef _SC_PAGESIZE /* some SVR4 systems omit an underscore */ | |
517 | # ifndef _SC_PAGE_SIZE | |
518 | # define _SC_PAGE_SIZE _SC_PAGESIZE | |
519 | # endif | |
520 | # endif | |
521 | # ifdef _SC_PAGE_SIZE | |
522 | # define malloc_getpagesize sysconf(_SC_PAGE_SIZE) | |
523 | # else | |
524 | # if defined(BSD) || defined(DGUX) || defined(HAVE_GETPAGESIZE) | |
525 | extern size_t getpagesize(); | |
526 | # define malloc_getpagesize getpagesize() | |
527 | # else | |
528 | # ifdef WIN32 | |
529 | # define malloc_getpagesize (4096) /* TBD: Use 'GetSystemInfo' instead */ | |
530 | # else | |
531 | # ifndef LACKS_SYS_PARAM_H | |
532 | # include <sys/param.h> | |
533 | # endif | |
534 | # ifdef EXEC_PAGESIZE | |
535 | # define malloc_getpagesize EXEC_PAGESIZE | |
536 | # else | |
537 | # ifdef NBPG | |
538 | # ifndef CLSIZE | |
539 | # define malloc_getpagesize NBPG | |
540 | # else | |
541 | # define malloc_getpagesize (NBPG * CLSIZE) | |
542 | # endif | |
543 | # else | |
544 | # ifdef NBPC | |
545 | # define malloc_getpagesize NBPC | |
546 | # else | |
547 | # ifdef PAGESIZE | |
548 | # define malloc_getpagesize PAGESIZE | |
549 | # else | |
550 | # define malloc_getpagesize (4096) /* just guess */ | |
551 | # endif | |
552 | # endif | |
553 | # endif | |
554 | # endif | |
555 | # endif | |
556 | # endif | |
557 | # endif | |
558 | #endif | |
559 | ||
560 | ||
217c9dad WD |
561 | /* |
562 | ||
563 | This version of malloc supports the standard SVID/XPG mallinfo | |
564 | routine that returns a struct containing the same kind of | |
565 | information you can get from malloc_stats. It should work on | |
566 | any SVID/XPG compliant system that has a /usr/include/malloc.h | |
567 | defining struct mallinfo. (If you'd like to install such a thing | |
568 | yourself, cut out the preliminary declarations as described above | |
569 | and below and save them in a malloc.h file. But there's no | |
570 | compelling reason to bother to do this.) | |
571 | ||
572 | The main declaration needed is the mallinfo struct that is returned | |
573 | (by-copy) by mallinfo(). The SVID/XPG malloinfo struct contains a | |
574 | bunch of fields, most of which are not even meaningful in this | |
575 | version of malloc. Some of these fields are are instead filled by | |
576 | mallinfo() with other numbers that might possibly be of interest. | |
577 | ||
578 | HAVE_USR_INCLUDE_MALLOC_H should be set if you have a | |
579 | /usr/include/malloc.h file that includes a declaration of struct | |
580 | mallinfo. If so, it is included; else an SVID2/XPG2 compliant | |
581 | version is declared below. These must be precisely the same for | |
582 | mallinfo() to work. | |
583 | ||
584 | */ | |
585 | ||
586 | /* #define HAVE_USR_INCLUDE_MALLOC_H */ | |
587 | ||
588 | #if HAVE_USR_INCLUDE_MALLOC_H | |
589 | #include "/usr/include/malloc.h" | |
590 | #else | |
591 | ||
592 | /* SVID2/XPG mallinfo structure */ | |
593 | ||
594 | struct mallinfo { | |
595 | int arena; /* total space allocated from system */ | |
596 | int ordblks; /* number of non-inuse chunks */ | |
597 | int smblks; /* unused -- always zero */ | |
598 | int hblks; /* number of mmapped regions */ | |
599 | int hblkhd; /* total space in mmapped regions */ | |
600 | int usmblks; /* unused -- always zero */ | |
601 | int fsmblks; /* unused -- always zero */ | |
602 | int uordblks; /* total allocated space */ | |
603 | int fordblks; /* total non-inuse space */ | |
604 | int keepcost; /* top-most, releasable (via malloc_trim) space */ | |
605 | }; | |
606 | ||
607 | /* SVID2/XPG mallopt options */ | |
608 | ||
609 | #define M_MXFAST 1 /* UNUSED in this malloc */ | |
610 | #define M_NLBLKS 2 /* UNUSED in this malloc */ | |
611 | #define M_GRAIN 3 /* UNUSED in this malloc */ | |
612 | #define M_KEEP 4 /* UNUSED in this malloc */ | |
613 | ||
614 | #endif | |
615 | ||
616 | /* mallopt options that actually do something */ | |
617 | ||
618 | #define M_TRIM_THRESHOLD -1 | |
619 | #define M_TOP_PAD -2 | |
620 | #define M_MMAP_THRESHOLD -3 | |
621 | #define M_MMAP_MAX -4 | |
622 | ||
623 | ||
217c9dad WD |
624 | #ifndef DEFAULT_TRIM_THRESHOLD |
625 | #define DEFAULT_TRIM_THRESHOLD (128 * 1024) | |
626 | #endif | |
627 | ||
628 | /* | |
629 | M_TRIM_THRESHOLD is the maximum amount of unused top-most memory | |
630 | to keep before releasing via malloc_trim in free(). | |
631 | ||
632 | Automatic trimming is mainly useful in long-lived programs. | |
633 | Because trimming via sbrk can be slow on some systems, and can | |
634 | sometimes be wasteful (in cases where programs immediately | |
635 | afterward allocate more large chunks) the value should be high | |
636 | enough so that your overall system performance would improve by | |
637 | releasing. | |
638 | ||
639 | The trim threshold and the mmap control parameters (see below) | |
640 | can be traded off with one another. Trimming and mmapping are | |
641 | two different ways of releasing unused memory back to the | |
642 | system. Between these two, it is often possible to keep | |
643 | system-level demands of a long-lived program down to a bare | |
644 | minimum. For example, in one test suite of sessions measuring | |
645 | the XF86 X server on Linux, using a trim threshold of 128K and a | |
646 | mmap threshold of 192K led to near-minimal long term resource | |
647 | consumption. | |
648 | ||
649 | If you are using this malloc in a long-lived program, it should | |
650 | pay to experiment with these values. As a rough guide, you | |
651 | might set to a value close to the average size of a process | |
652 | (program) running on your system. Releasing this much memory | |
653 | would allow such a process to run in memory. Generally, it's | |
654 | worth it to tune for trimming rather tham memory mapping when a | |
655 | program undergoes phases where several large chunks are | |
656 | allocated and released in ways that can reuse each other's | |
657 | storage, perhaps mixed with phases where there are no such | |
658 | chunks at all. And in well-behaved long-lived programs, | |
659 | controlling release of large blocks via trimming versus mapping | |
660 | is usually faster. | |
661 | ||
662 | However, in most programs, these parameters serve mainly as | |
663 | protection against the system-level effects of carrying around | |
664 | massive amounts of unneeded memory. Since frequent calls to | |
665 | sbrk, mmap, and munmap otherwise degrade performance, the default | |
666 | parameters are set to relatively high values that serve only as | |
667 | safeguards. | |
668 | ||
669 | The default trim value is high enough to cause trimming only in | |
670 | fairly extreme (by current memory consumption standards) cases. | |
671 | It must be greater than page size to have any useful effect. To | |
672 | disable trimming completely, you can set to (unsigned long)(-1); | |
673 | ||
674 | ||
675 | */ | |
676 | ||
677 | ||
678 | #ifndef DEFAULT_TOP_PAD | |
679 | #define DEFAULT_TOP_PAD (0) | |
680 | #endif | |
681 | ||
682 | /* | |
683 | M_TOP_PAD is the amount of extra `padding' space to allocate or | |
684 | retain whenever sbrk is called. It is used in two ways internally: | |
685 | ||
686 | * When sbrk is called to extend the top of the arena to satisfy | |
8bde7f77 WD |
687 | a new malloc request, this much padding is added to the sbrk |
688 | request. | |
217c9dad WD |
689 | |
690 | * When malloc_trim is called automatically from free(), | |
8bde7f77 | 691 | it is used as the `pad' argument. |
217c9dad WD |
692 | |
693 | In both cases, the actual amount of padding is rounded | |
694 | so that the end of the arena is always a system page boundary. | |
695 | ||
696 | The main reason for using padding is to avoid calling sbrk so | |
697 | often. Having even a small pad greatly reduces the likelihood | |
698 | that nearly every malloc request during program start-up (or | |
699 | after trimming) will invoke sbrk, which needlessly wastes | |
700 | time. | |
701 | ||
702 | Automatic rounding-up to page-size units is normally sufficient | |
703 | to avoid measurable overhead, so the default is 0. However, in | |
704 | systems where sbrk is relatively slow, it can pay to increase | |
705 | this value, at the expense of carrying around more memory than | |
706 | the program needs. | |
707 | ||
708 | */ | |
709 | ||
710 | ||
711 | #ifndef DEFAULT_MMAP_THRESHOLD | |
712 | #define DEFAULT_MMAP_THRESHOLD (128 * 1024) | |
713 | #endif | |
714 | ||
715 | /* | |
716 | ||
717 | M_MMAP_THRESHOLD is the request size threshold for using mmap() | |
718 | to service a request. Requests of at least this size that cannot | |
719 | be allocated using already-existing space will be serviced via mmap. | |
720 | (If enough normal freed space already exists it is used instead.) | |
721 | ||
722 | Using mmap segregates relatively large chunks of memory so that | |
723 | they can be individually obtained and released from the host | |
724 | system. A request serviced through mmap is never reused by any | |
725 | other request (at least not directly; the system may just so | |
726 | happen to remap successive requests to the same locations). | |
727 | ||
728 | Segregating space in this way has the benefit that mmapped space | |
729 | can ALWAYS be individually released back to the system, which | |
730 | helps keep the system level memory demands of a long-lived | |
731 | program low. Mapped memory can never become `locked' between | |
732 | other chunks, as can happen with normally allocated chunks, which | |
733 | menas that even trimming via malloc_trim would not release them. | |
734 | ||
735 | However, it has the disadvantages that: | |
736 | ||
8bde7f77 WD |
737 | 1. The space cannot be reclaimed, consolidated, and then |
738 | used to service later requests, as happens with normal chunks. | |
739 | 2. It can lead to more wastage because of mmap page alignment | |
740 | requirements | |
741 | 3. It causes malloc performance to be more dependent on host | |
742 | system memory management support routines which may vary in | |
743 | implementation quality and may impose arbitrary | |
744 | limitations. Generally, servicing a request via normal | |
745 | malloc steps is faster than going through a system's mmap. | |
217c9dad WD |
746 | |
747 | All together, these considerations should lead you to use mmap | |
748 | only for relatively large requests. | |
749 | ||
750 | ||
751 | */ | |
752 | ||
753 | ||
217c9dad WD |
754 | #ifndef DEFAULT_MMAP_MAX |
755 | #if HAVE_MMAP | |
756 | #define DEFAULT_MMAP_MAX (64) | |
757 | #else | |
758 | #define DEFAULT_MMAP_MAX (0) | |
759 | #endif | |
760 | #endif | |
761 | ||
762 | /* | |
763 | M_MMAP_MAX is the maximum number of requests to simultaneously | |
764 | service using mmap. This parameter exists because: | |
765 | ||
8bde7f77 WD |
766 | 1. Some systems have a limited number of internal tables for |
767 | use by mmap. | |
768 | 2. In most systems, overreliance on mmap can degrade overall | |
769 | performance. | |
770 | 3. If a program allocates many large regions, it is probably | |
771 | better off using normal sbrk-based allocation routines that | |
772 | can reclaim and reallocate normal heap memory. Using a | |
773 | small value allows transition into this mode after the | |
774 | first few allocations. | |
217c9dad WD |
775 | |
776 | Setting to 0 disables all use of mmap. If HAVE_MMAP is not set, | |
777 | the default value is 0, and attempts to set it to non-zero values | |
778 | in mallopt will fail. | |
779 | */ | |
780 | ||
781 | ||
217c9dad WD |
782 | /* |
783 | USE_DL_PREFIX will prefix all public routines with the string 'dl'. | |
784 | Useful to quickly avoid procedure declaration conflicts and linker | |
785 | symbol conflicts with existing memory allocation routines. | |
786 | ||
787 | */ | |
788 | ||
789 | /* #define USE_DL_PREFIX */ | |
790 | ||
791 | ||
217c9dad WD |
792 | /* |
793 | ||
794 | Special defines for linux libc | |
795 | ||
796 | Except when compiled using these special defines for Linux libc | |
797 | using weak aliases, this malloc is NOT designed to work in | |
798 | multithreaded applications. No semaphores or other concurrency | |
799 | control are provided to ensure that multiple malloc or free calls | |
800 | don't run at the same time, which could be disasterous. A single | |
801 | semaphore could be used across malloc, realloc, and free (which is | |
802 | essentially the effect of the linux weak alias approach). It would | |
803 | be hard to obtain finer granularity. | |
804 | ||
805 | */ | |
806 | ||
807 | ||
808 | #ifdef INTERNAL_LINUX_C_LIB | |
809 | ||
810 | #if __STD_C | |
811 | ||
812 | Void_t * __default_morecore_init (ptrdiff_t); | |
813 | Void_t *(*__morecore)(ptrdiff_t) = __default_morecore_init; | |
814 | ||
815 | #else | |
816 | ||
817 | Void_t * __default_morecore_init (); | |
818 | Void_t *(*__morecore)() = __default_morecore_init; | |
819 | ||
820 | #endif | |
821 | ||
822 | #define MORECORE (*__morecore) | |
823 | #define MORECORE_FAILURE 0 | |
824 | #define MORECORE_CLEARS 1 | |
825 | ||
826 | #else /* INTERNAL_LINUX_C_LIB */ | |
827 | ||
828 | #if __STD_C | |
829 | extern Void_t* sbrk(ptrdiff_t); | |
830 | #else | |
831 | extern Void_t* sbrk(); | |
832 | #endif | |
833 | ||
834 | #ifndef MORECORE | |
835 | #define MORECORE sbrk | |
836 | #endif | |
837 | ||
838 | #ifndef MORECORE_FAILURE | |
839 | #define MORECORE_FAILURE -1 | |
840 | #endif | |
841 | ||
842 | #ifndef MORECORE_CLEARS | |
843 | #define MORECORE_CLEARS 1 | |
844 | #endif | |
845 | ||
846 | #endif /* INTERNAL_LINUX_C_LIB */ | |
847 | ||
848 | #if defined(INTERNAL_LINUX_C_LIB) && defined(__ELF__) | |
849 | ||
850 | #define cALLOc __libc_calloc | |
851 | #define fREe __libc_free | |
852 | #define mALLOc __libc_malloc | |
853 | #define mEMALIGn __libc_memalign | |
854 | #define rEALLOc __libc_realloc | |
855 | #define vALLOc __libc_valloc | |
856 | #define pvALLOc __libc_pvalloc | |
857 | #define mALLINFo __libc_mallinfo | |
858 | #define mALLOPt __libc_mallopt | |
859 | ||
860 | #pragma weak calloc = __libc_calloc | |
861 | #pragma weak free = __libc_free | |
862 | #pragma weak cfree = __libc_free | |
863 | #pragma weak malloc = __libc_malloc | |
864 | #pragma weak memalign = __libc_memalign | |
865 | #pragma weak realloc = __libc_realloc | |
866 | #pragma weak valloc = __libc_valloc | |
867 | #pragma weak pvalloc = __libc_pvalloc | |
868 | #pragma weak mallinfo = __libc_mallinfo | |
869 | #pragma weak mallopt = __libc_mallopt | |
870 | ||
871 | #else | |
872 | ||
873 | #ifdef USE_DL_PREFIX | |
874 | #define cALLOc dlcalloc | |
875 | #define fREe dlfree | |
876 | #define mALLOc dlmalloc | |
877 | #define mEMALIGn dlmemalign | |
878 | #define rEALLOc dlrealloc | |
879 | #define vALLOc dlvalloc | |
880 | #define pvALLOc dlpvalloc | |
881 | #define mALLINFo dlmallinfo | |
882 | #define mALLOPt dlmallopt | |
883 | #else /* USE_DL_PREFIX */ | |
884 | #define cALLOc calloc | |
885 | #define fREe free | |
886 | #define mALLOc malloc | |
887 | #define mEMALIGn memalign | |
888 | #define rEALLOc realloc | |
889 | #define vALLOc valloc | |
890 | #define pvALLOc pvalloc | |
891 | #define mALLINFo mallinfo | |
892 | #define mALLOPt mallopt | |
893 | #endif /* USE_DL_PREFIX */ | |
894 | ||
895 | #endif | |
896 | ||
897 | /* Public routines */ | |
898 | ||
899 | #if __STD_C | |
900 | ||
901 | Void_t* mALLOc(size_t); | |
902 | void fREe(Void_t*); | |
903 | Void_t* rEALLOc(Void_t*, size_t); | |
904 | Void_t* mEMALIGn(size_t, size_t); | |
905 | Void_t* vALLOc(size_t); | |
906 | Void_t* pvALLOc(size_t); | |
907 | Void_t* cALLOc(size_t, size_t); | |
908 | void cfree(Void_t*); | |
909 | int malloc_trim(size_t); | |
910 | size_t malloc_usable_size(Void_t*); | |
911 | void malloc_stats(); | |
912 | int mALLOPt(int, int); | |
913 | struct mallinfo mALLINFo(void); | |
914 | #else | |
915 | Void_t* mALLOc(); | |
916 | void fREe(); | |
917 | Void_t* rEALLOc(); | |
918 | Void_t* mEMALIGn(); | |
919 | Void_t* vALLOc(); | |
920 | Void_t* pvALLOc(); | |
921 | Void_t* cALLOc(); | |
922 | void cfree(); | |
923 | int malloc_trim(); | |
924 | size_t malloc_usable_size(); | |
925 | void malloc_stats(); | |
926 | int mALLOPt(); | |
927 | struct mallinfo mALLINFo(); | |
928 | #endif | |
929 | ||
930 | ||
931 | #ifdef __cplusplus | |
932 | }; /* end of extern "C" */ | |
933 | #endif | |
934 | ||
935 | /* ---------- To make a malloc.h, end cutting here ------------ */ | |
936 | #else /* Moved to malloc.h */ | |
937 | ||
938 | #include <malloc.h> | |
939 | #if 0 | |
940 | #if __STD_C | |
941 | static void malloc_update_mallinfo (void); | |
942 | void malloc_stats (void); | |
943 | #else | |
944 | static void malloc_update_mallinfo (); | |
945 | void malloc_stats(); | |
946 | #endif | |
947 | #endif /* 0 */ | |
948 | ||
949 | #endif /* 0 */ /* Moved to malloc.h */ | |
950 | #include <common.h> | |
951 | ||
d87080b7 WD |
952 | DECLARE_GLOBAL_DATA_PTR; |
953 | ||
217c9dad WD |
954 | /* |
955 | Emulation of sbrk for WIN32 | |
956 | All code within the ifdef WIN32 is untested by me. | |
957 | ||
958 | Thanks to Martin Fong and others for supplying this. | |
959 | */ | |
960 | ||
961 | ||
962 | #ifdef WIN32 | |
963 | ||
964 | #define AlignPage(add) (((add) + (malloc_getpagesize-1)) & \ | |
965 | ~(malloc_getpagesize-1)) | |
966 | #define AlignPage64K(add) (((add) + (0x10000 - 1)) & ~(0x10000 - 1)) | |
967 | ||
968 | /* resrve 64MB to insure large contiguous space */ | |
969 | #define RESERVED_SIZE (1024*1024*64) | |
970 | #define NEXT_SIZE (2048*1024) | |
971 | #define TOP_MEMORY ((unsigned long)2*1024*1024*1024) | |
972 | ||
973 | struct GmListElement; | |
974 | typedef struct GmListElement GmListElement; | |
975 | ||
976 | struct GmListElement | |
977 | { | |
978 | GmListElement* next; | |
979 | void* base; | |
980 | }; | |
981 | ||
982 | static GmListElement* head = 0; | |
983 | static unsigned int gNextAddress = 0; | |
984 | static unsigned int gAddressBase = 0; | |
985 | static unsigned int gAllocatedSize = 0; | |
986 | ||
987 | static | |
988 | GmListElement* makeGmListElement (void* bas) | |
989 | { | |
990 | GmListElement* this; | |
991 | this = (GmListElement*)(void*)LocalAlloc (0, sizeof (GmListElement)); | |
992 | assert (this); | |
993 | if (this) | |
994 | { | |
995 | this->base = bas; | |
996 | this->next = head; | |
997 | head = this; | |
998 | } | |
999 | return this; | |
1000 | } | |
1001 | ||
1002 | void gcleanup () | |
1003 | { | |
1004 | BOOL rval; | |
1005 | assert ( (head == NULL) || (head->base == (void*)gAddressBase)); | |
1006 | if (gAddressBase && (gNextAddress - gAddressBase)) | |
1007 | { | |
1008 | rval = VirtualFree ((void*)gAddressBase, | |
1009 | gNextAddress - gAddressBase, | |
1010 | MEM_DECOMMIT); | |
8bde7f77 | 1011 | assert (rval); |
217c9dad WD |
1012 | } |
1013 | while (head) | |
1014 | { | |
1015 | GmListElement* next = head->next; | |
1016 | rval = VirtualFree (head->base, 0, MEM_RELEASE); | |
1017 | assert (rval); | |
1018 | LocalFree (head); | |
1019 | head = next; | |
1020 | } | |
1021 | } | |
1022 | ||
1023 | static | |
1024 | void* findRegion (void* start_address, unsigned long size) | |
1025 | { | |
1026 | MEMORY_BASIC_INFORMATION info; | |
1027 | if (size >= TOP_MEMORY) return NULL; | |
1028 | ||
1029 | while ((unsigned long)start_address + size < TOP_MEMORY) | |
1030 | { | |
1031 | VirtualQuery (start_address, &info, sizeof (info)); | |
1032 | if ((info.State == MEM_FREE) && (info.RegionSize >= size)) | |
1033 | return start_address; | |
1034 | else | |
1035 | { | |
8bde7f77 WD |
1036 | /* Requested region is not available so see if the */ |
1037 | /* next region is available. Set 'start_address' */ | |
1038 | /* to the next region and call 'VirtualQuery()' */ | |
1039 | /* again. */ | |
217c9dad WD |
1040 | |
1041 | start_address = (char*)info.BaseAddress + info.RegionSize; | |
1042 | ||
8bde7f77 WD |
1043 | /* Make sure we start looking for the next region */ |
1044 | /* on the *next* 64K boundary. Otherwise, even if */ | |
1045 | /* the new region is free according to */ | |
1046 | /* 'VirtualQuery()', the subsequent call to */ | |
1047 | /* 'VirtualAlloc()' (which follows the call to */ | |
1048 | /* this routine in 'wsbrk()') will round *down* */ | |
1049 | /* the requested address to a 64K boundary which */ | |
1050 | /* we already know is an address in the */ | |
1051 | /* unavailable region. Thus, the subsequent call */ | |
1052 | /* to 'VirtualAlloc()' will fail and bring us back */ | |
1053 | /* here, causing us to go into an infinite loop. */ | |
217c9dad WD |
1054 | |
1055 | start_address = | |
1056 | (void *) AlignPage64K((unsigned long) start_address); | |
1057 | } | |
1058 | } | |
1059 | return NULL; | |
1060 | ||
1061 | } | |
1062 | ||
1063 | ||
1064 | void* wsbrk (long size) | |
1065 | { | |
1066 | void* tmp; | |
1067 | if (size > 0) | |
1068 | { | |
1069 | if (gAddressBase == 0) | |
1070 | { | |
1071 | gAllocatedSize = max (RESERVED_SIZE, AlignPage (size)); | |
1072 | gNextAddress = gAddressBase = | |
1073 | (unsigned int)VirtualAlloc (NULL, gAllocatedSize, | |
1074 | MEM_RESERVE, PAGE_NOACCESS); | |
1075 | } else if (AlignPage (gNextAddress + size) > (gAddressBase + | |
1076 | gAllocatedSize)) | |
1077 | { | |
1078 | long new_size = max (NEXT_SIZE, AlignPage (size)); | |
1079 | void* new_address = (void*)(gAddressBase+gAllocatedSize); | |
1080 | do | |
1081 | { | |
1082 | new_address = findRegion (new_address, new_size); | |
1083 | ||
1084 | if (new_address == 0) | |
1085 | return (void*)-1; | |
1086 | ||
1087 | gAddressBase = gNextAddress = | |
1088 | (unsigned int)VirtualAlloc (new_address, new_size, | |
1089 | MEM_RESERVE, PAGE_NOACCESS); | |
8bde7f77 WD |
1090 | /* repeat in case of race condition */ |
1091 | /* The region that we found has been snagged */ | |
1092 | /* by another thread */ | |
217c9dad WD |
1093 | } |
1094 | while (gAddressBase == 0); | |
1095 | ||
1096 | assert (new_address == (void*)gAddressBase); | |
1097 | ||
1098 | gAllocatedSize = new_size; | |
1099 | ||
1100 | if (!makeGmListElement ((void*)gAddressBase)) | |
1101 | return (void*)-1; | |
1102 | } | |
1103 | if ((size + gNextAddress) > AlignPage (gNextAddress)) | |
1104 | { | |
1105 | void* res; | |
1106 | res = VirtualAlloc ((void*)AlignPage (gNextAddress), | |
1107 | (size + gNextAddress - | |
1108 | AlignPage (gNextAddress)), | |
1109 | MEM_COMMIT, PAGE_READWRITE); | |
1110 | if (res == 0) | |
1111 | return (void*)-1; | |
1112 | } | |
1113 | tmp = (void*)gNextAddress; | |
1114 | gNextAddress = (unsigned int)tmp + size; | |
1115 | return tmp; | |
1116 | } | |
1117 | else if (size < 0) | |
1118 | { | |
1119 | unsigned int alignedGoal = AlignPage (gNextAddress + size); | |
1120 | /* Trim by releasing the virtual memory */ | |
1121 | if (alignedGoal >= gAddressBase) | |
1122 | { | |
1123 | VirtualFree ((void*)alignedGoal, gNextAddress - alignedGoal, | |
1124 | MEM_DECOMMIT); | |
1125 | gNextAddress = gNextAddress + size; | |
1126 | return (void*)gNextAddress; | |
1127 | } | |
1128 | else | |
1129 | { | |
1130 | VirtualFree ((void*)gAddressBase, gNextAddress - gAddressBase, | |
1131 | MEM_DECOMMIT); | |
1132 | gNextAddress = gAddressBase; | |
1133 | return (void*)-1; | |
1134 | } | |
1135 | } | |
1136 | else | |
1137 | { | |
1138 | return (void*)gNextAddress; | |
1139 | } | |
1140 | } | |
1141 | ||
1142 | #endif | |
1143 | ||
1144 | \f | |
1145 | ||
1146 | /* | |
1147 | Type declarations | |
1148 | */ | |
1149 | ||
1150 | ||
1151 | struct malloc_chunk | |
1152 | { | |
1153 | INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */ | |
1154 | INTERNAL_SIZE_T size; /* Size in bytes, including overhead. */ | |
1155 | struct malloc_chunk* fd; /* double links -- used only if free. */ | |
1156 | struct malloc_chunk* bk; | |
1157 | }; | |
1158 | ||
1159 | typedef struct malloc_chunk* mchunkptr; | |
1160 | ||
1161 | /* | |
1162 | ||
1163 | malloc_chunk details: | |
1164 | ||
1165 | (The following includes lightly edited explanations by Colin Plumb.) | |
1166 | ||
1167 | Chunks of memory are maintained using a `boundary tag' method as | |
1168 | described in e.g., Knuth or Standish. (See the paper by Paul | |
1169 | Wilson ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a | |
1170 | survey of such techniques.) Sizes of free chunks are stored both | |
1171 | in the front of each chunk and at the end. This makes | |
1172 | consolidating fragmented chunks into bigger chunks very fast. The | |
1173 | size fields also hold bits representing whether chunks are free or | |
1174 | in use. | |
1175 | ||
1176 | An allocated chunk looks like this: | |
1177 | ||
1178 | ||
1179 | chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |
8bde7f77 WD |
1180 | | Size of previous chunk, if allocated | | |
1181 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |
1182 | | Size of chunk, in bytes |P| | |
217c9dad | 1183 | mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
8bde7f77 WD |
1184 | | User data starts here... . |
1185 | . . | |
1186 | . (malloc_usable_space() bytes) . | |
1187 | . | | |
217c9dad | 1188 | nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
8bde7f77 WD |
1189 | | Size of chunk | |
1190 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |
217c9dad WD |
1191 | |
1192 | ||
1193 | Where "chunk" is the front of the chunk for the purpose of most of | |
1194 | the malloc code, but "mem" is the pointer that is returned to the | |
1195 | user. "Nextchunk" is the beginning of the next contiguous chunk. | |
1196 | ||
1197 | Chunks always begin on even word boundries, so the mem portion | |
1198 | (which is returned to the user) is also on an even word boundary, and | |
1199 | thus double-word aligned. | |
1200 | ||
1201 | Free chunks are stored in circular doubly-linked lists, and look like this: | |
1202 | ||
1203 | chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |
8bde7f77 WD |
1204 | | Size of previous chunk | |
1205 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |
217c9dad WD |
1206 | `head:' | Size of chunk, in bytes |P| |
1207 | mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |
8bde7f77 WD |
1208 | | Forward pointer to next chunk in list | |
1209 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |
1210 | | Back pointer to previous chunk in list | | |
1211 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |
1212 | | Unused space (may be 0 bytes long) . | |
1213 | . . | |
1214 | . | | |
217c9dad WD |
1215 | nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
1216 | `foot:' | Size of chunk, in bytes | | |
8bde7f77 | 1217 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
217c9dad WD |
1218 | |
1219 | The P (PREV_INUSE) bit, stored in the unused low-order bit of the | |
1220 | chunk size (which is always a multiple of two words), is an in-use | |
1221 | bit for the *previous* chunk. If that bit is *clear*, then the | |
1222 | word before the current chunk size contains the previous chunk | |
1223 | size, and can be used to find the front of the previous chunk. | |
1224 | (The very first chunk allocated always has this bit set, | |
1225 | preventing access to non-existent (or non-owned) memory.) | |
1226 | ||
1227 | Note that the `foot' of the current chunk is actually represented | |
1228 | as the prev_size of the NEXT chunk. (This makes it easier to | |
1229 | deal with alignments etc). | |
1230 | ||
1231 | The two exceptions to all this are | |
1232 | ||
1233 | 1. The special chunk `top', which doesn't bother using the | |
8bde7f77 WD |
1234 | trailing size field since there is no |
1235 | next contiguous chunk that would have to index off it. (After | |
1236 | initialization, `top' is forced to always exist. If it would | |
1237 | become less than MINSIZE bytes long, it is replenished via | |
1238 | malloc_extend_top.) | |
217c9dad WD |
1239 | |
1240 | 2. Chunks allocated via mmap, which have the second-lowest-order | |
8bde7f77 WD |
1241 | bit (IS_MMAPPED) set in their size fields. Because they are |
1242 | never merged or traversed from any other chunk, they have no | |
1243 | foot size or inuse information. | |
217c9dad WD |
1244 | |
1245 | Available chunks are kept in any of several places (all declared below): | |
1246 | ||
1247 | * `av': An array of chunks serving as bin headers for consolidated | |
1248 | chunks. Each bin is doubly linked. The bins are approximately | |
1249 | proportionally (log) spaced. There are a lot of these bins | |
1250 | (128). This may look excessive, but works very well in | |
1251 | practice. All procedures maintain the invariant that no | |
1252 | consolidated chunk physically borders another one. Chunks in | |
1253 | bins are kept in size order, with ties going to the | |
1254 | approximately least recently used chunk. | |
1255 | ||
1256 | The chunks in each bin are maintained in decreasing sorted order by | |
1257 | size. This is irrelevant for the small bins, which all contain | |
1258 | the same-sized chunks, but facilitates best-fit allocation for | |
1259 | larger chunks. (These lists are just sequential. Keeping them in | |
1260 | order almost never requires enough traversal to warrant using | |
1261 | fancier ordered data structures.) Chunks of the same size are | |
1262 | linked with the most recently freed at the front, and allocations | |
1263 | are taken from the back. This results in LRU or FIFO allocation | |
1264 | order, which tends to give each chunk an equal opportunity to be | |
1265 | consolidated with adjacent freed chunks, resulting in larger free | |
1266 | chunks and less fragmentation. | |
1267 | ||
1268 | * `top': The top-most available chunk (i.e., the one bordering the | |
1269 | end of available memory) is treated specially. It is never | |
1270 | included in any bin, is used only if no other chunk is | |
1271 | available, and is released back to the system if it is very | |
1272 | large (see M_TRIM_THRESHOLD). | |
1273 | ||
1274 | * `last_remainder': A bin holding only the remainder of the | |
1275 | most recently split (non-top) chunk. This bin is checked | |
1276 | before other non-fitting chunks, so as to provide better | |
1277 | locality for runs of sequentially allocated chunks. | |
1278 | ||
1279 | * Implicitly, through the host system's memory mapping tables. | |
1280 | If supported, requests greater than a threshold are usually | |
1281 | serviced via calls to mmap, and then later released via munmap. | |
1282 | ||
1283 | */ | |
217c9dad | 1284 | \f |
217c9dad WD |
1285 | /* sizes, alignments */ |
1286 | ||
1287 | #define SIZE_SZ (sizeof(INTERNAL_SIZE_T)) | |
1288 | #define MALLOC_ALIGNMENT (SIZE_SZ + SIZE_SZ) | |
1289 | #define MALLOC_ALIGN_MASK (MALLOC_ALIGNMENT - 1) | |
1290 | #define MINSIZE (sizeof(struct malloc_chunk)) | |
1291 | ||
1292 | /* conversion from malloc headers to user pointers, and back */ | |
1293 | ||
1294 | #define chunk2mem(p) ((Void_t*)((char*)(p) + 2*SIZE_SZ)) | |
1295 | #define mem2chunk(mem) ((mchunkptr)((char*)(mem) - 2*SIZE_SZ)) | |
1296 | ||
1297 | /* pad request bytes into a usable size */ | |
1298 | ||
1299 | #define request2size(req) \ | |
1300 | (((long)((req) + (SIZE_SZ + MALLOC_ALIGN_MASK)) < \ | |
1301 | (long)(MINSIZE + MALLOC_ALIGN_MASK)) ? MINSIZE : \ | |
1302 | (((req) + (SIZE_SZ + MALLOC_ALIGN_MASK)) & ~(MALLOC_ALIGN_MASK))) | |
1303 | ||
1304 | /* Check if m has acceptable alignment */ | |
1305 | ||
1306 | #define aligned_OK(m) (((unsigned long)((m)) & (MALLOC_ALIGN_MASK)) == 0) | |
1307 | ||
1308 | ||
1309 | \f | |
1310 | ||
1311 | /* | |
1312 | Physical chunk operations | |
1313 | */ | |
1314 | ||
1315 | ||
1316 | /* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */ | |
1317 | ||
1318 | #define PREV_INUSE 0x1 | |
1319 | ||
1320 | /* size field is or'ed with IS_MMAPPED if the chunk was obtained with mmap() */ | |
1321 | ||
1322 | #define IS_MMAPPED 0x2 | |
1323 | ||
1324 | /* Bits to mask off when extracting size */ | |
1325 | ||
1326 | #define SIZE_BITS (PREV_INUSE|IS_MMAPPED) | |
1327 | ||
1328 | ||
1329 | /* Ptr to next physical malloc_chunk. */ | |
1330 | ||
1331 | #define next_chunk(p) ((mchunkptr)( ((char*)(p)) + ((p)->size & ~PREV_INUSE) )) | |
1332 | ||
1333 | /* Ptr to previous physical malloc_chunk */ | |
1334 | ||
1335 | #define prev_chunk(p)\ | |
1336 | ((mchunkptr)( ((char*)(p)) - ((p)->prev_size) )) | |
1337 | ||
1338 | ||
1339 | /* Treat space at ptr + offset as a chunk */ | |
1340 | ||
1341 | #define chunk_at_offset(p, s) ((mchunkptr)(((char*)(p)) + (s))) | |
1342 | ||
1343 | ||
1344 | \f | |
1345 | ||
1346 | /* | |
1347 | Dealing with use bits | |
1348 | */ | |
1349 | ||
1350 | /* extract p's inuse bit */ | |
1351 | ||
1352 | #define inuse(p)\ | |
1353 | ((((mchunkptr)(((char*)(p))+((p)->size & ~PREV_INUSE)))->size) & PREV_INUSE) | |
1354 | ||
1355 | /* extract inuse bit of previous chunk */ | |
1356 | ||
1357 | #define prev_inuse(p) ((p)->size & PREV_INUSE) | |
1358 | ||
1359 | /* check for mmap()'ed chunk */ | |
1360 | ||
1361 | #define chunk_is_mmapped(p) ((p)->size & IS_MMAPPED) | |
1362 | ||
1363 | /* set/clear chunk as in use without otherwise disturbing */ | |
1364 | ||
1365 | #define set_inuse(p)\ | |
1366 | ((mchunkptr)(((char*)(p)) + ((p)->size & ~PREV_INUSE)))->size |= PREV_INUSE | |
1367 | ||
1368 | #define clear_inuse(p)\ | |
1369 | ((mchunkptr)(((char*)(p)) + ((p)->size & ~PREV_INUSE)))->size &= ~(PREV_INUSE) | |
1370 | ||
1371 | /* check/set/clear inuse bits in known places */ | |
1372 | ||
1373 | #define inuse_bit_at_offset(p, s)\ | |
1374 | (((mchunkptr)(((char*)(p)) + (s)))->size & PREV_INUSE) | |
1375 | ||
1376 | #define set_inuse_bit_at_offset(p, s)\ | |
1377 | (((mchunkptr)(((char*)(p)) + (s)))->size |= PREV_INUSE) | |
1378 | ||
1379 | #define clear_inuse_bit_at_offset(p, s)\ | |
1380 | (((mchunkptr)(((char*)(p)) + (s)))->size &= ~(PREV_INUSE)) | |
1381 | ||
1382 | ||
1383 | \f | |
1384 | ||
1385 | /* | |
1386 | Dealing with size fields | |
1387 | */ | |
1388 | ||
1389 | /* Get size, ignoring use bits */ | |
1390 | ||
1391 | #define chunksize(p) ((p)->size & ~(SIZE_BITS)) | |
1392 | ||
1393 | /* Set size at head, without disturbing its use bit */ | |
1394 | ||
1395 | #define set_head_size(p, s) ((p)->size = (((p)->size & PREV_INUSE) | (s))) | |
1396 | ||
1397 | /* Set size/use ignoring previous bits in header */ | |
1398 | ||
1399 | #define set_head(p, s) ((p)->size = (s)) | |
1400 | ||
1401 | /* Set size at footer (only when chunk is not in use) */ | |
1402 | ||
1403 | #define set_foot(p, s) (((mchunkptr)((char*)(p) + (s)))->prev_size = (s)) | |
1404 | ||
1405 | ||
1406 | \f | |
1407 | ||
1408 | ||
1409 | /* | |
1410 | Bins | |
1411 | ||
1412 | The bins, `av_' are an array of pairs of pointers serving as the | |
1413 | heads of (initially empty) doubly-linked lists of chunks, laid out | |
1414 | in a way so that each pair can be treated as if it were in a | |
1415 | malloc_chunk. (This way, the fd/bk offsets for linking bin heads | |
1416 | and chunks are the same). | |
1417 | ||
1418 | Bins for sizes < 512 bytes contain chunks of all the same size, spaced | |
1419 | 8 bytes apart. Larger bins are approximately logarithmically | |
1420 | spaced. (See the table below.) The `av_' array is never mentioned | |
1421 | directly in the code, but instead via bin access macros. | |
1422 | ||
1423 | Bin layout: | |
1424 | ||
1425 | 64 bins of size 8 | |
1426 | 32 bins of size 64 | |
1427 | 16 bins of size 512 | |
1428 | 8 bins of size 4096 | |
1429 | 4 bins of size 32768 | |
1430 | 2 bins of size 262144 | |
1431 | 1 bin of size what's left | |
1432 | ||
1433 | There is actually a little bit of slop in the numbers in bin_index | |
1434 | for the sake of speed. This makes no difference elsewhere. | |
1435 | ||
1436 | The special chunks `top' and `last_remainder' get their own bins, | |
1437 | (this is implemented via yet more trickery with the av_ array), | |
1438 | although `top' is never properly linked to its bin since it is | |
1439 | always handled specially. | |
1440 | ||
1441 | */ | |
1442 | ||
1443 | #define NAV 128 /* number of bins */ | |
1444 | ||
1445 | typedef struct malloc_chunk* mbinptr; | |
1446 | ||
1447 | /* access macros */ | |
1448 | ||
1449 | #define bin_at(i) ((mbinptr)((char*)&(av_[2*(i) + 2]) - 2*SIZE_SZ)) | |
1450 | #define next_bin(b) ((mbinptr)((char*)(b) + 2 * sizeof(mbinptr))) | |
1451 | #define prev_bin(b) ((mbinptr)((char*)(b) - 2 * sizeof(mbinptr))) | |
1452 | ||
1453 | /* | |
1454 | The first 2 bins are never indexed. The corresponding av_ cells are instead | |
1455 | used for bookkeeping. This is not to save space, but to simplify | |
1456 | indexing, maintain locality, and avoid some initialization tests. | |
1457 | */ | |
1458 | ||
1459 | #define top (bin_at(0)->fd) /* The topmost chunk */ | |
1460 | #define last_remainder (bin_at(1)) /* remainder from last split */ | |
1461 | ||
1462 | ||
1463 | /* | |
1464 | Because top initially points to its own bin with initial | |
1465 | zero size, thus forcing extension on the first malloc request, | |
1466 | we avoid having any special code in malloc to check whether | |
1467 | it even exists yet. But we still need to in malloc_extend_top. | |
1468 | */ | |
1469 | ||
1470 | #define initial_top ((mchunkptr)(bin_at(0))) | |
1471 | ||
1472 | /* Helper macro to initialize bins */ | |
1473 | ||
1474 | #define IAV(i) bin_at(i), bin_at(i) | |
1475 | ||
1476 | static mbinptr av_[NAV * 2 + 2] = { | |
1477 | 0, 0, | |
1478 | IAV(0), IAV(1), IAV(2), IAV(3), IAV(4), IAV(5), IAV(6), IAV(7), | |
1479 | IAV(8), IAV(9), IAV(10), IAV(11), IAV(12), IAV(13), IAV(14), IAV(15), | |
1480 | IAV(16), IAV(17), IAV(18), IAV(19), IAV(20), IAV(21), IAV(22), IAV(23), | |
1481 | IAV(24), IAV(25), IAV(26), IAV(27), IAV(28), IAV(29), IAV(30), IAV(31), | |
1482 | IAV(32), IAV(33), IAV(34), IAV(35), IAV(36), IAV(37), IAV(38), IAV(39), | |
1483 | IAV(40), IAV(41), IAV(42), IAV(43), IAV(44), IAV(45), IAV(46), IAV(47), | |
1484 | IAV(48), IAV(49), IAV(50), IAV(51), IAV(52), IAV(53), IAV(54), IAV(55), | |
1485 | IAV(56), IAV(57), IAV(58), IAV(59), IAV(60), IAV(61), IAV(62), IAV(63), | |
1486 | IAV(64), IAV(65), IAV(66), IAV(67), IAV(68), IAV(69), IAV(70), IAV(71), | |
1487 | IAV(72), IAV(73), IAV(74), IAV(75), IAV(76), IAV(77), IAV(78), IAV(79), | |
1488 | IAV(80), IAV(81), IAV(82), IAV(83), IAV(84), IAV(85), IAV(86), IAV(87), | |
1489 | IAV(88), IAV(89), IAV(90), IAV(91), IAV(92), IAV(93), IAV(94), IAV(95), | |
1490 | IAV(96), IAV(97), IAV(98), IAV(99), IAV(100), IAV(101), IAV(102), IAV(103), | |
1491 | IAV(104), IAV(105), IAV(106), IAV(107), IAV(108), IAV(109), IAV(110), IAV(111), | |
1492 | IAV(112), IAV(113), IAV(114), IAV(115), IAV(116), IAV(117), IAV(118), IAV(119), | |
1493 | IAV(120), IAV(121), IAV(122), IAV(123), IAV(124), IAV(125), IAV(126), IAV(127) | |
1494 | }; | |
1495 | ||
1496 | void malloc_bin_reloc (void) | |
1497 | { | |
217c9dad WD |
1498 | unsigned long *p = (unsigned long *)(&av_[2]); |
1499 | int i; | |
1500 | for (i=2; i<(sizeof(av_)/sizeof(mbinptr)); ++i) { | |
1501 | *p++ += gd->reloc_off; | |
1502 | } | |
1503 | } | |
1504 | \f | |
1505 | ||
1506 | /* field-extraction macros */ | |
1507 | ||
1508 | #define first(b) ((b)->fd) | |
1509 | #define last(b) ((b)->bk) | |
1510 | ||
1511 | /* | |
1512 | Indexing into bins | |
1513 | */ | |
1514 | ||
1515 | #define bin_index(sz) \ | |
1516 | (((((unsigned long)(sz)) >> 9) == 0) ? (((unsigned long)(sz)) >> 3): \ | |
1517 | ((((unsigned long)(sz)) >> 9) <= 4) ? 56 + (((unsigned long)(sz)) >> 6): \ | |
1518 | ((((unsigned long)(sz)) >> 9) <= 20) ? 91 + (((unsigned long)(sz)) >> 9): \ | |
1519 | ((((unsigned long)(sz)) >> 9) <= 84) ? 110 + (((unsigned long)(sz)) >> 12): \ | |
1520 | ((((unsigned long)(sz)) >> 9) <= 340) ? 119 + (((unsigned long)(sz)) >> 15): \ | |
1521 | ((((unsigned long)(sz)) >> 9) <= 1364) ? 124 + (((unsigned long)(sz)) >> 18): \ | |
8bde7f77 | 1522 | 126) |
217c9dad WD |
1523 | /* |
1524 | bins for chunks < 512 are all spaced 8 bytes apart, and hold | |
1525 | identically sized chunks. This is exploited in malloc. | |
1526 | */ | |
1527 | ||
1528 | #define MAX_SMALLBIN 63 | |
1529 | #define MAX_SMALLBIN_SIZE 512 | |
1530 | #define SMALLBIN_WIDTH 8 | |
1531 | ||
1532 | #define smallbin_index(sz) (((unsigned long)(sz)) >> 3) | |
1533 | ||
1534 | /* | |
1535 | Requests are `small' if both the corresponding and the next bin are small | |
1536 | */ | |
1537 | ||
1538 | #define is_small_request(nb) (nb < MAX_SMALLBIN_SIZE - SMALLBIN_WIDTH) | |
1539 | ||
1540 | \f | |
1541 | ||
1542 | /* | |
1543 | To help compensate for the large number of bins, a one-level index | |
1544 | structure is used for bin-by-bin searching. `binblocks' is a | |
1545 | one-word bitvector recording whether groups of BINBLOCKWIDTH bins | |
1546 | have any (possibly) non-empty bins, so they can be skipped over | |
1547 | all at once during during traversals. The bits are NOT always | |
1548 | cleared as soon as all bins in a block are empty, but instead only | |
1549 | when all are noticed to be empty during traversal in malloc. | |
1550 | */ | |
1551 | ||
1552 | #define BINBLOCKWIDTH 4 /* bins per block */ | |
1553 | ||
1554 | #define binblocks (bin_at(0)->size) /* bitvector of nonempty blocks */ | |
1555 | ||
1556 | /* bin<->block macros */ | |
1557 | ||
1558 | #define idx2binblock(ix) ((unsigned)1 << (ix / BINBLOCKWIDTH)) | |
1559 | #define mark_binblock(ii) (binblocks |= idx2binblock(ii)) | |
1560 | #define clear_binblock(ii) (binblocks &= ~(idx2binblock(ii))) | |
1561 | ||
1562 | ||
1563 | \f | |
1564 | ||
1565 | ||
1566 | /* Other static bookkeeping data */ | |
1567 | ||
1568 | /* variables holding tunable values */ | |
1569 | ||
1570 | static unsigned long trim_threshold = DEFAULT_TRIM_THRESHOLD; | |
1571 | static unsigned long top_pad = DEFAULT_TOP_PAD; | |
1572 | static unsigned int n_mmaps_max = DEFAULT_MMAP_MAX; | |
1573 | static unsigned long mmap_threshold = DEFAULT_MMAP_THRESHOLD; | |
1574 | ||
1575 | /* The first value returned from sbrk */ | |
1576 | static char* sbrk_base = (char*)(-1); | |
1577 | ||
1578 | /* The maximum memory obtained from system via sbrk */ | |
1579 | static unsigned long max_sbrked_mem = 0; | |
1580 | ||
1581 | /* The maximum via either sbrk or mmap */ | |
1582 | static unsigned long max_total_mem = 0; | |
1583 | ||
1584 | /* internal working copy of mallinfo */ | |
1585 | static struct mallinfo current_mallinfo = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; | |
1586 | ||
1587 | /* The total memory obtained from system via sbrk */ | |
1588 | #define sbrked_mem (current_mallinfo.arena) | |
1589 | ||
1590 | /* Tracking mmaps */ | |
1591 | ||
1592 | #if 0 | |
1593 | static unsigned int n_mmaps = 0; | |
1594 | #endif /* 0 */ | |
1595 | static unsigned long mmapped_mem = 0; | |
1596 | #if HAVE_MMAP | |
1597 | static unsigned int max_n_mmaps = 0; | |
1598 | static unsigned long max_mmapped_mem = 0; | |
1599 | #endif | |
1600 | ||
1601 | \f | |
1602 | ||
1603 | /* | |
1604 | Debugging support | |
1605 | */ | |
1606 | ||
1607 | #ifdef DEBUG | |
1608 | ||
1609 | ||
1610 | /* | |
1611 | These routines make a number of assertions about the states | |
1612 | of data structures that should be true at all times. If any | |
1613 | are not true, it's very likely that a user program has somehow | |
1614 | trashed memory. (It's also possible that there is a coding error | |
1615 | in malloc. In which case, please report it!) | |
1616 | */ | |
1617 | ||
1618 | #if __STD_C | |
1619 | static void do_check_chunk(mchunkptr p) | |
1620 | #else | |
1621 | static void do_check_chunk(p) mchunkptr p; | |
1622 | #endif | |
1623 | { | |
1624 | #if 0 /* causes warnings because assert() is off */ | |
1625 | INTERNAL_SIZE_T sz = p->size & ~PREV_INUSE; | |
1626 | #endif /* 0 */ | |
1627 | ||
1628 | /* No checkable chunk is mmapped */ | |
1629 | assert(!chunk_is_mmapped(p)); | |
1630 | ||
1631 | /* Check for legal address ... */ | |
1632 | assert((char*)p >= sbrk_base); | |
1633 | if (p != top) | |
1634 | assert((char*)p + sz <= (char*)top); | |
1635 | else | |
1636 | assert((char*)p + sz <= sbrk_base + sbrked_mem); | |
1637 | ||
1638 | } | |
1639 | ||
1640 | ||
1641 | #if __STD_C | |
1642 | static void do_check_free_chunk(mchunkptr p) | |
1643 | #else | |
1644 | static void do_check_free_chunk(p) mchunkptr p; | |
1645 | #endif | |
1646 | { | |
1647 | INTERNAL_SIZE_T sz = p->size & ~PREV_INUSE; | |
1648 | #if 0 /* causes warnings because assert() is off */ | |
1649 | mchunkptr next = chunk_at_offset(p, sz); | |
1650 | #endif /* 0 */ | |
1651 | ||
1652 | do_check_chunk(p); | |
1653 | ||
1654 | /* Check whether it claims to be free ... */ | |
1655 | assert(!inuse(p)); | |
1656 | ||
1657 | /* Unless a special marker, must have OK fields */ | |
1658 | if ((long)sz >= (long)MINSIZE) | |
1659 | { | |
1660 | assert((sz & MALLOC_ALIGN_MASK) == 0); | |
1661 | assert(aligned_OK(chunk2mem(p))); | |
1662 | /* ... matching footer field */ | |
1663 | assert(next->prev_size == sz); | |
1664 | /* ... and is fully consolidated */ | |
1665 | assert(prev_inuse(p)); | |
1666 | assert (next == top || inuse(next)); | |
1667 | ||
1668 | /* ... and has minimally sane links */ | |
1669 | assert(p->fd->bk == p); | |
1670 | assert(p->bk->fd == p); | |
1671 | } | |
1672 | else /* markers are always of size SIZE_SZ */ | |
1673 | assert(sz == SIZE_SZ); | |
1674 | } | |
1675 | ||
1676 | #if __STD_C | |
1677 | static void do_check_inuse_chunk(mchunkptr p) | |
1678 | #else | |
1679 | static void do_check_inuse_chunk(p) mchunkptr p; | |
1680 | #endif | |
1681 | { | |
1682 | mchunkptr next = next_chunk(p); | |
1683 | do_check_chunk(p); | |
1684 | ||
1685 | /* Check whether it claims to be in use ... */ | |
1686 | assert(inuse(p)); | |
1687 | ||
1688 | /* ... and is surrounded by OK chunks. | |
1689 | Since more things can be checked with free chunks than inuse ones, | |
1690 | if an inuse chunk borders them and debug is on, it's worth doing them. | |
1691 | */ | |
1692 | if (!prev_inuse(p)) | |
1693 | { | |
1694 | mchunkptr prv = prev_chunk(p); | |
1695 | assert(next_chunk(prv) == p); | |
1696 | do_check_free_chunk(prv); | |
1697 | } | |
1698 | if (next == top) | |
1699 | { | |
1700 | assert(prev_inuse(next)); | |
1701 | assert(chunksize(next) >= MINSIZE); | |
1702 | } | |
1703 | else if (!inuse(next)) | |
1704 | do_check_free_chunk(next); | |
1705 | ||
1706 | } | |
1707 | ||
1708 | #if __STD_C | |
1709 | static void do_check_malloced_chunk(mchunkptr p, INTERNAL_SIZE_T s) | |
1710 | #else | |
1711 | static void do_check_malloced_chunk(p, s) mchunkptr p; INTERNAL_SIZE_T s; | |
1712 | #endif | |
1713 | { | |
1714 | #if 0 /* causes warnings because assert() is off */ | |
1715 | INTERNAL_SIZE_T sz = p->size & ~PREV_INUSE; | |
1716 | long room = sz - s; | |
1717 | #endif /* 0 */ | |
1718 | ||
1719 | do_check_inuse_chunk(p); | |
1720 | ||
1721 | /* Legal size ... */ | |
1722 | assert((long)sz >= (long)MINSIZE); | |
1723 | assert((sz & MALLOC_ALIGN_MASK) == 0); | |
1724 | assert(room >= 0); | |
1725 | assert(room < (long)MINSIZE); | |
1726 | ||
1727 | /* ... and alignment */ | |
1728 | assert(aligned_OK(chunk2mem(p))); | |
1729 | ||
1730 | ||
1731 | /* ... and was allocated at front of an available chunk */ | |
1732 | assert(prev_inuse(p)); | |
1733 | ||
1734 | } | |
1735 | ||
1736 | ||
1737 | #define check_free_chunk(P) do_check_free_chunk(P) | |
1738 | #define check_inuse_chunk(P) do_check_inuse_chunk(P) | |
1739 | #define check_chunk(P) do_check_chunk(P) | |
1740 | #define check_malloced_chunk(P,N) do_check_malloced_chunk(P,N) | |
1741 | #else | |
1742 | #define check_free_chunk(P) | |
1743 | #define check_inuse_chunk(P) | |
1744 | #define check_chunk(P) | |
1745 | #define check_malloced_chunk(P,N) | |
1746 | #endif | |
1747 | ||
1748 | \f | |
1749 | ||
1750 | /* | |
1751 | Macro-based internal utilities | |
1752 | */ | |
1753 | ||
1754 | ||
1755 | /* | |
1756 | Linking chunks in bin lists. | |
1757 | Call these only with variables, not arbitrary expressions, as arguments. | |
1758 | */ | |
1759 | ||
1760 | /* | |
1761 | Place chunk p of size s in its bin, in size order, | |
1762 | putting it ahead of others of same size. | |
1763 | */ | |
1764 | ||
1765 | ||
1766 | #define frontlink(P, S, IDX, BK, FD) \ | |
1767 | { \ | |
1768 | if (S < MAX_SMALLBIN_SIZE) \ | |
1769 | { \ | |
1770 | IDX = smallbin_index(S); \ | |
1771 | mark_binblock(IDX); \ | |
1772 | BK = bin_at(IDX); \ | |
1773 | FD = BK->fd; \ | |
1774 | P->bk = BK; \ | |
1775 | P->fd = FD; \ | |
1776 | FD->bk = BK->fd = P; \ | |
1777 | } \ | |
1778 | else \ | |
1779 | { \ | |
1780 | IDX = bin_index(S); \ | |
1781 | BK = bin_at(IDX); \ | |
1782 | FD = BK->fd; \ | |
1783 | if (FD == BK) mark_binblock(IDX); \ | |
1784 | else \ | |
1785 | { \ | |
1786 | while (FD != BK && S < chunksize(FD)) FD = FD->fd; \ | |
1787 | BK = FD->bk; \ | |
1788 | } \ | |
1789 | P->bk = BK; \ | |
1790 | P->fd = FD; \ | |
1791 | FD->bk = BK->fd = P; \ | |
1792 | } \ | |
1793 | } | |
1794 | ||
1795 | ||
1796 | /* take a chunk off a list */ | |
1797 | ||
1798 | #define unlink(P, BK, FD) \ | |
1799 | { \ | |
1800 | BK = P->bk; \ | |
1801 | FD = P->fd; \ | |
1802 | FD->bk = BK; \ | |
1803 | BK->fd = FD; \ | |
1804 | } \ | |
1805 | ||
1806 | /* Place p as the last remainder */ | |
1807 | ||
1808 | #define link_last_remainder(P) \ | |
1809 | { \ | |
1810 | last_remainder->fd = last_remainder->bk = P; \ | |
1811 | P->fd = P->bk = last_remainder; \ | |
1812 | } | |
1813 | ||
1814 | /* Clear the last_remainder bin */ | |
1815 | ||
1816 | #define clear_last_remainder \ | |
1817 | (last_remainder->fd = last_remainder->bk = last_remainder) | |
1818 | ||
1819 | ||
217c9dad WD |
1820 | \f |
1821 | ||
1822 | ||
1823 | /* Routines dealing with mmap(). */ | |
1824 | ||
1825 | #if HAVE_MMAP | |
1826 | ||
1827 | #if __STD_C | |
1828 | static mchunkptr mmap_chunk(size_t size) | |
1829 | #else | |
1830 | static mchunkptr mmap_chunk(size) size_t size; | |
1831 | #endif | |
1832 | { | |
1833 | size_t page_mask = malloc_getpagesize - 1; | |
1834 | mchunkptr p; | |
1835 | ||
1836 | #ifndef MAP_ANONYMOUS | |
1837 | static int fd = -1; | |
1838 | #endif | |
1839 | ||
1840 | if(n_mmaps >= n_mmaps_max) return 0; /* too many regions */ | |
1841 | ||
1842 | /* For mmapped chunks, the overhead is one SIZE_SZ unit larger, because | |
1843 | * there is no following chunk whose prev_size field could be used. | |
1844 | */ | |
1845 | size = (size + SIZE_SZ + page_mask) & ~page_mask; | |
1846 | ||
1847 | #ifdef MAP_ANONYMOUS | |
1848 | p = (mchunkptr)mmap(0, size, PROT_READ|PROT_WRITE, | |
1849 | MAP_PRIVATE|MAP_ANONYMOUS, -1, 0); | |
1850 | #else /* !MAP_ANONYMOUS */ | |
1851 | if (fd < 0) | |
1852 | { | |
1853 | fd = open("/dev/zero", O_RDWR); | |
1854 | if(fd < 0) return 0; | |
1855 | } | |
1856 | p = (mchunkptr)mmap(0, size, PROT_READ|PROT_WRITE, MAP_PRIVATE, fd, 0); | |
1857 | #endif | |
1858 | ||
1859 | if(p == (mchunkptr)-1) return 0; | |
1860 | ||
1861 | n_mmaps++; | |
1862 | if (n_mmaps > max_n_mmaps) max_n_mmaps = n_mmaps; | |
1863 | ||
1864 | /* We demand that eight bytes into a page must be 8-byte aligned. */ | |
1865 | assert(aligned_OK(chunk2mem(p))); | |
1866 | ||
1867 | /* The offset to the start of the mmapped region is stored | |
1868 | * in the prev_size field of the chunk; normally it is zero, | |
1869 | * but that can be changed in memalign(). | |
1870 | */ | |
1871 | p->prev_size = 0; | |
1872 | set_head(p, size|IS_MMAPPED); | |
1873 | ||
1874 | mmapped_mem += size; | |
1875 | if ((unsigned long)mmapped_mem > (unsigned long)max_mmapped_mem) | |
1876 | max_mmapped_mem = mmapped_mem; | |
1877 | if ((unsigned long)(mmapped_mem + sbrked_mem) > (unsigned long)max_total_mem) | |
1878 | max_total_mem = mmapped_mem + sbrked_mem; | |
1879 | return p; | |
1880 | } | |
1881 | ||
1882 | #if __STD_C | |
1883 | static void munmap_chunk(mchunkptr p) | |
1884 | #else | |
1885 | static void munmap_chunk(p) mchunkptr p; | |
1886 | #endif | |
1887 | { | |
1888 | INTERNAL_SIZE_T size = chunksize(p); | |
1889 | int ret; | |
1890 | ||
1891 | assert (chunk_is_mmapped(p)); | |
1892 | assert(! ((char*)p >= sbrk_base && (char*)p < sbrk_base + sbrked_mem)); | |
1893 | assert((n_mmaps > 0)); | |
1894 | assert(((p->prev_size + size) & (malloc_getpagesize-1)) == 0); | |
1895 | ||
1896 | n_mmaps--; | |
1897 | mmapped_mem -= (size + p->prev_size); | |
1898 | ||
1899 | ret = munmap((char *)p - p->prev_size, size + p->prev_size); | |
1900 | ||
1901 | /* munmap returns non-zero on failure */ | |
1902 | assert(ret == 0); | |
1903 | } | |
1904 | ||
1905 | #if HAVE_MREMAP | |
1906 | ||
1907 | #if __STD_C | |
1908 | static mchunkptr mremap_chunk(mchunkptr p, size_t new_size) | |
1909 | #else | |
1910 | static mchunkptr mremap_chunk(p, new_size) mchunkptr p; size_t new_size; | |
1911 | #endif | |
1912 | { | |
1913 | size_t page_mask = malloc_getpagesize - 1; | |
1914 | INTERNAL_SIZE_T offset = p->prev_size; | |
1915 | INTERNAL_SIZE_T size = chunksize(p); | |
1916 | char *cp; | |
1917 | ||
1918 | assert (chunk_is_mmapped(p)); | |
1919 | assert(! ((char*)p >= sbrk_base && (char*)p < sbrk_base + sbrked_mem)); | |
1920 | assert((n_mmaps > 0)); | |
1921 | assert(((size + offset) & (malloc_getpagesize-1)) == 0); | |
1922 | ||
1923 | /* Note the extra SIZE_SZ overhead as in mmap_chunk(). */ | |
1924 | new_size = (new_size + offset + SIZE_SZ + page_mask) & ~page_mask; | |
1925 | ||
1926 | cp = (char *)mremap((char *)p - offset, size + offset, new_size, 1); | |
1927 | ||
1928 | if (cp == (char *)-1) return 0; | |
1929 | ||
1930 | p = (mchunkptr)(cp + offset); | |
1931 | ||
1932 | assert(aligned_OK(chunk2mem(p))); | |
1933 | ||
1934 | assert((p->prev_size == offset)); | |
1935 | set_head(p, (new_size - offset)|IS_MMAPPED); | |
1936 | ||
1937 | mmapped_mem -= size + offset; | |
1938 | mmapped_mem += new_size; | |
1939 | if ((unsigned long)mmapped_mem > (unsigned long)max_mmapped_mem) | |
1940 | max_mmapped_mem = mmapped_mem; | |
1941 | if ((unsigned long)(mmapped_mem + sbrked_mem) > (unsigned long)max_total_mem) | |
1942 | max_total_mem = mmapped_mem + sbrked_mem; | |
1943 | return p; | |
1944 | } | |
1945 | ||
1946 | #endif /* HAVE_MREMAP */ | |
1947 | ||
1948 | #endif /* HAVE_MMAP */ | |
1949 | ||
1950 | ||
1951 | \f | |
1952 | ||
1953 | /* | |
1954 | Extend the top-most chunk by obtaining memory from system. | |
1955 | Main interface to sbrk (but see also malloc_trim). | |
1956 | */ | |
1957 | ||
1958 | #if __STD_C | |
1959 | static void malloc_extend_top(INTERNAL_SIZE_T nb) | |
1960 | #else | |
1961 | static void malloc_extend_top(nb) INTERNAL_SIZE_T nb; | |
1962 | #endif | |
1963 | { | |
1964 | char* brk; /* return value from sbrk */ | |
1965 | INTERNAL_SIZE_T front_misalign; /* unusable bytes at front of sbrked space */ | |
1966 | INTERNAL_SIZE_T correction; /* bytes for 2nd sbrk call */ | |
1967 | char* new_brk; /* return of 2nd sbrk call */ | |
1968 | INTERNAL_SIZE_T top_size; /* new size of top chunk */ | |
1969 | ||
1970 | mchunkptr old_top = top; /* Record state of old top */ | |
1971 | INTERNAL_SIZE_T old_top_size = chunksize(old_top); | |
1972 | char* old_end = (char*)(chunk_at_offset(old_top, old_top_size)); | |
1973 | ||
1974 | /* Pad request with top_pad plus minimal overhead */ | |
1975 | ||
1976 | INTERNAL_SIZE_T sbrk_size = nb + top_pad + MINSIZE; | |
1977 | unsigned long pagesz = malloc_getpagesize; | |
1978 | ||
1979 | /* If not the first time through, round to preserve page boundary */ | |
1980 | /* Otherwise, we need to correct to a page size below anyway. */ | |
1981 | /* (We also correct below if an intervening foreign sbrk call.) */ | |
1982 | ||
1983 | if (sbrk_base != (char*)(-1)) | |
1984 | sbrk_size = (sbrk_size + (pagesz - 1)) & ~(pagesz - 1); | |
1985 | ||
1986 | brk = (char*)(MORECORE (sbrk_size)); | |
1987 | ||
1988 | /* Fail if sbrk failed or if a foreign sbrk call killed our space */ | |
1989 | if (brk == (char*)(MORECORE_FAILURE) || | |
1990 | (brk < old_end && old_top != initial_top)) | |
1991 | return; | |
1992 | ||
1993 | sbrked_mem += sbrk_size; | |
1994 | ||
1995 | if (brk == old_end) /* can just add bytes to current top */ | |
1996 | { | |
1997 | top_size = sbrk_size + old_top_size; | |
1998 | set_head(top, top_size | PREV_INUSE); | |
1999 | } | |
2000 | else | |
2001 | { | |
2002 | if (sbrk_base == (char*)(-1)) /* First time through. Record base */ | |
2003 | sbrk_base = brk; | |
2004 | else /* Someone else called sbrk(). Count those bytes as sbrked_mem. */ | |
2005 | sbrked_mem += brk - (char*)old_end; | |
2006 | ||
2007 | /* Guarantee alignment of first new chunk made from this space */ | |
2008 | front_misalign = (unsigned long)chunk2mem(brk) & MALLOC_ALIGN_MASK; | |
2009 | if (front_misalign > 0) | |
2010 | { | |
2011 | correction = (MALLOC_ALIGNMENT) - front_misalign; | |
2012 | brk += correction; | |
2013 | } | |
2014 | else | |
2015 | correction = 0; | |
2016 | ||
2017 | /* Guarantee the next brk will be at a page boundary */ | |
2018 | ||
2019 | correction += ((((unsigned long)(brk + sbrk_size))+(pagesz-1)) & | |
8bde7f77 | 2020 | ~(pagesz - 1)) - ((unsigned long)(brk + sbrk_size)); |
217c9dad WD |
2021 | |
2022 | /* Allocate correction */ | |
2023 | new_brk = (char*)(MORECORE (correction)); | |
2024 | if (new_brk == (char*)(MORECORE_FAILURE)) return; | |
2025 | ||
2026 | sbrked_mem += correction; | |
2027 | ||
2028 | top = (mchunkptr)brk; | |
2029 | top_size = new_brk - brk + correction; | |
2030 | set_head(top, top_size | PREV_INUSE); | |
2031 | ||
2032 | if (old_top != initial_top) | |
2033 | { | |
2034 | ||
2035 | /* There must have been an intervening foreign sbrk call. */ | |
2036 | /* A double fencepost is necessary to prevent consolidation */ | |
2037 | ||
2038 | /* If not enough space to do this, then user did something very wrong */ | |
2039 | if (old_top_size < MINSIZE) | |
2040 | { | |
8bde7f77 WD |
2041 | set_head(top, PREV_INUSE); /* will force null return from malloc */ |
2042 | return; | |
217c9dad WD |
2043 | } |
2044 | ||
2045 | /* Also keep size a multiple of MALLOC_ALIGNMENT */ | |
2046 | old_top_size = (old_top_size - 3*SIZE_SZ) & ~MALLOC_ALIGN_MASK; | |
2047 | set_head_size(old_top, old_top_size); | |
2048 | chunk_at_offset(old_top, old_top_size )->size = | |
8bde7f77 | 2049 | SIZE_SZ|PREV_INUSE; |
217c9dad | 2050 | chunk_at_offset(old_top, old_top_size + SIZE_SZ)->size = |
8bde7f77 | 2051 | SIZE_SZ|PREV_INUSE; |
217c9dad WD |
2052 | /* If possible, release the rest. */ |
2053 | if (old_top_size >= MINSIZE) | |
8bde7f77 | 2054 | fREe(chunk2mem(old_top)); |
217c9dad WD |
2055 | } |
2056 | } | |
2057 | ||
2058 | if ((unsigned long)sbrked_mem > (unsigned long)max_sbrked_mem) | |
2059 | max_sbrked_mem = sbrked_mem; | |
2060 | if ((unsigned long)(mmapped_mem + sbrked_mem) > (unsigned long)max_total_mem) | |
2061 | max_total_mem = mmapped_mem + sbrked_mem; | |
2062 | ||
2063 | /* We always land on a page boundary */ | |
2064 | assert(((unsigned long)((char*)top + top_size) & (pagesz - 1)) == 0); | |
2065 | } | |
2066 | ||
2067 | ||
2068 | \f | |
2069 | ||
2070 | /* Main public routines */ | |
2071 | ||
2072 | ||
2073 | /* | |
2074 | Malloc Algorthim: | |
2075 | ||
2076 | The requested size is first converted into a usable form, `nb'. | |
2077 | This currently means to add 4 bytes overhead plus possibly more to | |
2078 | obtain 8-byte alignment and/or to obtain a size of at least | |
2079 | MINSIZE (currently 16 bytes), the smallest allocatable size. | |
2080 | (All fits are considered `exact' if they are within MINSIZE bytes.) | |
2081 | ||
2082 | From there, the first successful of the following steps is taken: | |
2083 | ||
2084 | 1. The bin corresponding to the request size is scanned, and if | |
8bde7f77 | 2085 | a chunk of exactly the right size is found, it is taken. |
217c9dad WD |
2086 | |
2087 | 2. The most recently remaindered chunk is used if it is big | |
8bde7f77 WD |
2088 | enough. This is a form of (roving) first fit, used only in |
2089 | the absence of exact fits. Runs of consecutive requests use | |
2090 | the remainder of the chunk used for the previous such request | |
2091 | whenever possible. This limited use of a first-fit style | |
2092 | allocation strategy tends to give contiguous chunks | |
2093 | coextensive lifetimes, which improves locality and can reduce | |
2094 | fragmentation in the long run. | |
217c9dad WD |
2095 | |
2096 | 3. Other bins are scanned in increasing size order, using a | |
8bde7f77 WD |
2097 | chunk big enough to fulfill the request, and splitting off |
2098 | any remainder. This search is strictly by best-fit; i.e., | |
2099 | the smallest (with ties going to approximately the least | |
2100 | recently used) chunk that fits is selected. | |
217c9dad WD |
2101 | |
2102 | 4. If large enough, the chunk bordering the end of memory | |
8bde7f77 WD |
2103 | (`top') is split off. (This use of `top' is in accord with |
2104 | the best-fit search rule. In effect, `top' is treated as | |
2105 | larger (and thus less well fitting) than any other available | |
2106 | chunk since it can be extended to be as large as necessary | |
2107 | (up to system limitations). | |
217c9dad WD |
2108 | |
2109 | 5. If the request size meets the mmap threshold and the | |
8bde7f77 WD |
2110 | system supports mmap, and there are few enough currently |
2111 | allocated mmapped regions, and a call to mmap succeeds, | |
2112 | the request is allocated via direct memory mapping. | |
217c9dad WD |
2113 | |
2114 | 6. Otherwise, the top of memory is extended by | |
8bde7f77 WD |
2115 | obtaining more space from the system (normally using sbrk, |
2116 | but definable to anything else via the MORECORE macro). | |
2117 | Memory is gathered from the system (in system page-sized | |
2118 | units) in a way that allows chunks obtained across different | |
2119 | sbrk calls to be consolidated, but does not require | |
2120 | contiguous memory. Thus, it should be safe to intersperse | |
2121 | mallocs with other sbrk calls. | |
217c9dad WD |
2122 | |
2123 | ||
2124 | All allocations are made from the the `lowest' part of any found | |
2125 | chunk. (The implementation invariant is that prev_inuse is | |
2126 | always true of any allocated chunk; i.e., that each allocated | |
2127 | chunk borders either a previously allocated and still in-use chunk, | |
2128 | or the base of its memory arena.) | |
2129 | ||
2130 | */ | |
2131 | ||
2132 | #if __STD_C | |
2133 | Void_t* mALLOc(size_t bytes) | |
2134 | #else | |
2135 | Void_t* mALLOc(bytes) size_t bytes; | |
2136 | #endif | |
2137 | { | |
2138 | mchunkptr victim; /* inspected/selected chunk */ | |
2139 | INTERNAL_SIZE_T victim_size; /* its size */ | |
2140 | int idx; /* index for bin traversal */ | |
2141 | mbinptr bin; /* associated bin */ | |
2142 | mchunkptr remainder; /* remainder from a split */ | |
2143 | long remainder_size; /* its size */ | |
2144 | int remainder_index; /* its bin index */ | |
2145 | unsigned long block; /* block traverser bit */ | |
2146 | int startidx; /* first bin of a traversed block */ | |
2147 | mchunkptr fwd; /* misc temp for linking */ | |
2148 | mchunkptr bck; /* misc temp for linking */ | |
2149 | mbinptr q; /* misc temp */ | |
2150 | ||
2151 | INTERNAL_SIZE_T nb; | |
2152 | ||
2153 | if ((long)bytes < 0) return 0; | |
2154 | ||
2155 | nb = request2size(bytes); /* padded request size; */ | |
2156 | ||
2157 | /* Check for exact match in a bin */ | |
2158 | ||
2159 | if (is_small_request(nb)) /* Faster version for small requests */ | |
2160 | { | |
2161 | idx = smallbin_index(nb); | |
2162 | ||
2163 | /* No traversal or size check necessary for small bins. */ | |
2164 | ||
2165 | q = bin_at(idx); | |
2166 | victim = last(q); | |
2167 | ||
2168 | /* Also scan the next one, since it would have a remainder < MINSIZE */ | |
2169 | if (victim == q) | |
2170 | { | |
2171 | q = next_bin(q); | |
2172 | victim = last(q); | |
2173 | } | |
2174 | if (victim != q) | |
2175 | { | |
2176 | victim_size = chunksize(victim); | |
2177 | unlink(victim, bck, fwd); | |
2178 | set_inuse_bit_at_offset(victim, victim_size); | |
2179 | check_malloced_chunk(victim, nb); | |
2180 | return chunk2mem(victim); | |
2181 | } | |
2182 | ||
2183 | idx += 2; /* Set for bin scan below. We've already scanned 2 bins. */ | |
2184 | ||
2185 | } | |
2186 | else | |
2187 | { | |
2188 | idx = bin_index(nb); | |
2189 | bin = bin_at(idx); | |
2190 | ||
2191 | for (victim = last(bin); victim != bin; victim = victim->bk) | |
2192 | { | |
2193 | victim_size = chunksize(victim); | |
2194 | remainder_size = victim_size - nb; | |
2195 | ||
2196 | if (remainder_size >= (long)MINSIZE) /* too big */ | |
2197 | { | |
8bde7f77 WD |
2198 | --idx; /* adjust to rescan below after checking last remainder */ |
2199 | break; | |
217c9dad WD |
2200 | } |
2201 | ||
2202 | else if (remainder_size >= 0) /* exact fit */ | |
2203 | { | |
8bde7f77 WD |
2204 | unlink(victim, bck, fwd); |
2205 | set_inuse_bit_at_offset(victim, victim_size); | |
2206 | check_malloced_chunk(victim, nb); | |
2207 | return chunk2mem(victim); | |
217c9dad WD |
2208 | } |
2209 | } | |
2210 | ||
2211 | ++idx; | |
2212 | ||
2213 | } | |
2214 | ||
2215 | /* Try to use the last split-off remainder */ | |
2216 | ||
2217 | if ( (victim = last_remainder->fd) != last_remainder) | |
2218 | { | |
2219 | victim_size = chunksize(victim); | |
2220 | remainder_size = victim_size - nb; | |
2221 | ||
2222 | if (remainder_size >= (long)MINSIZE) /* re-split */ | |
2223 | { | |
2224 | remainder = chunk_at_offset(victim, nb); | |
2225 | set_head(victim, nb | PREV_INUSE); | |
2226 | link_last_remainder(remainder); | |
2227 | set_head(remainder, remainder_size | PREV_INUSE); | |
2228 | set_foot(remainder, remainder_size); | |
2229 | check_malloced_chunk(victim, nb); | |
2230 | return chunk2mem(victim); | |
2231 | } | |
2232 | ||
2233 | clear_last_remainder; | |
2234 | ||
2235 | if (remainder_size >= 0) /* exhaust */ | |
2236 | { | |
2237 | set_inuse_bit_at_offset(victim, victim_size); | |
2238 | check_malloced_chunk(victim, nb); | |
2239 | return chunk2mem(victim); | |
2240 | } | |
2241 | ||
2242 | /* Else place in bin */ | |
2243 | ||
2244 | frontlink(victim, victim_size, remainder_index, bck, fwd); | |
2245 | } | |
2246 | ||
2247 | /* | |
2248 | If there are any possibly nonempty big-enough blocks, | |
2249 | search for best fitting chunk by scanning bins in blockwidth units. | |
2250 | */ | |
2251 | ||
2252 | if ( (block = idx2binblock(idx)) <= binblocks) | |
2253 | { | |
2254 | ||
2255 | /* Get to the first marked block */ | |
2256 | ||
2257 | if ( (block & binblocks) == 0) | |
2258 | { | |
2259 | /* force to an even block boundary */ | |
2260 | idx = (idx & ~(BINBLOCKWIDTH - 1)) + BINBLOCKWIDTH; | |
2261 | block <<= 1; | |
2262 | while ((block & binblocks) == 0) | |
2263 | { | |
8bde7f77 WD |
2264 | idx += BINBLOCKWIDTH; |
2265 | block <<= 1; | |
217c9dad WD |
2266 | } |
2267 | } | |
2268 | ||
2269 | /* For each possibly nonempty block ... */ | |
2270 | for (;;) | |
2271 | { | |
2272 | startidx = idx; /* (track incomplete blocks) */ | |
2273 | q = bin = bin_at(idx); | |
2274 | ||
2275 | /* For each bin in this block ... */ | |
2276 | do | |
2277 | { | |
8bde7f77 WD |
2278 | /* Find and use first big enough chunk ... */ |
2279 | ||
2280 | for (victim = last(bin); victim != bin; victim = victim->bk) | |
2281 | { | |
2282 | victim_size = chunksize(victim); | |
2283 | remainder_size = victim_size - nb; | |
2284 | ||
2285 | if (remainder_size >= (long)MINSIZE) /* split */ | |
2286 | { | |
2287 | remainder = chunk_at_offset(victim, nb); | |
2288 | set_head(victim, nb | PREV_INUSE); | |
2289 | unlink(victim, bck, fwd); | |
2290 | link_last_remainder(remainder); | |
2291 | set_head(remainder, remainder_size | PREV_INUSE); | |
2292 | set_foot(remainder, remainder_size); | |
2293 | check_malloced_chunk(victim, nb); | |
2294 | return chunk2mem(victim); | |
2295 | } | |
2296 | ||
2297 | else if (remainder_size >= 0) /* take */ | |
2298 | { | |
2299 | set_inuse_bit_at_offset(victim, victim_size); | |
2300 | unlink(victim, bck, fwd); | |
2301 | check_malloced_chunk(victim, nb); | |
2302 | return chunk2mem(victim); | |
2303 | } | |
2304 | ||
2305 | } | |
217c9dad WD |
2306 | |
2307 | bin = next_bin(bin); | |
2308 | ||
2309 | } while ((++idx & (BINBLOCKWIDTH - 1)) != 0); | |
2310 | ||
2311 | /* Clear out the block bit. */ | |
2312 | ||
2313 | do /* Possibly backtrack to try to clear a partial block */ | |
2314 | { | |
8bde7f77 WD |
2315 | if ((startidx & (BINBLOCKWIDTH - 1)) == 0) |
2316 | { | |
2317 | binblocks &= ~block; | |
2318 | break; | |
2319 | } | |
2320 | --startidx; | |
217c9dad WD |
2321 | q = prev_bin(q); |
2322 | } while (first(q) == q); | |
2323 | ||
2324 | /* Get to the next possibly nonempty block */ | |
2325 | ||
2326 | if ( (block <<= 1) <= binblocks && (block != 0) ) | |
2327 | { | |
8bde7f77 WD |
2328 | while ((block & binblocks) == 0) |
2329 | { | |
2330 | idx += BINBLOCKWIDTH; | |
2331 | block <<= 1; | |
2332 | } | |
217c9dad WD |
2333 | } |
2334 | else | |
8bde7f77 | 2335 | break; |
217c9dad WD |
2336 | } |
2337 | } | |
2338 | ||
2339 | ||
2340 | /* Try to use top chunk */ | |
2341 | ||
2342 | /* Require that there be a remainder, ensuring top always exists */ | |
2343 | if ( (remainder_size = chunksize(top) - nb) < (long)MINSIZE) | |
2344 | { | |
2345 | ||
2346 | #if HAVE_MMAP | |
2347 | /* If big and would otherwise need to extend, try to use mmap instead */ | |
2348 | if ((unsigned long)nb >= (unsigned long)mmap_threshold && | |
8bde7f77 | 2349 | (victim = mmap_chunk(nb)) != 0) |
217c9dad WD |
2350 | return chunk2mem(victim); |
2351 | #endif | |
2352 | ||
2353 | /* Try to extend */ | |
2354 | malloc_extend_top(nb); | |
2355 | if ( (remainder_size = chunksize(top) - nb) < (long)MINSIZE) | |
2356 | return 0; /* propagate failure */ | |
2357 | } | |
2358 | ||
2359 | victim = top; | |
2360 | set_head(victim, nb | PREV_INUSE); | |
2361 | top = chunk_at_offset(victim, nb); | |
2362 | set_head(top, remainder_size | PREV_INUSE); | |
2363 | check_malloced_chunk(victim, nb); | |
2364 | return chunk2mem(victim); | |
2365 | ||
2366 | } | |
2367 | ||
2368 | ||
2369 | \f | |
2370 | ||
2371 | /* | |
2372 | ||
2373 | free() algorithm : | |
2374 | ||
2375 | cases: | |
2376 | ||
2377 | 1. free(0) has no effect. | |
2378 | ||
2379 | 2. If the chunk was allocated via mmap, it is release via munmap(). | |
2380 | ||
2381 | 3. If a returned chunk borders the current high end of memory, | |
8bde7f77 WD |
2382 | it is consolidated into the top, and if the total unused |
2383 | topmost memory exceeds the trim threshold, malloc_trim is | |
2384 | called. | |
217c9dad WD |
2385 | |
2386 | 4. Other chunks are consolidated as they arrive, and | |
8bde7f77 WD |
2387 | placed in corresponding bins. (This includes the case of |
2388 | consolidating with the current `last_remainder'). | |
217c9dad WD |
2389 | |
2390 | */ | |
2391 | ||
2392 | ||
2393 | #if __STD_C | |
2394 | void fREe(Void_t* mem) | |
2395 | #else | |
2396 | void fREe(mem) Void_t* mem; | |
2397 | #endif | |
2398 | { | |
2399 | mchunkptr p; /* chunk corresponding to mem */ | |
2400 | INTERNAL_SIZE_T hd; /* its head field */ | |
2401 | INTERNAL_SIZE_T sz; /* its size */ | |
2402 | int idx; /* its bin index */ | |
2403 | mchunkptr next; /* next contiguous chunk */ | |
2404 | INTERNAL_SIZE_T nextsz; /* its size */ | |
2405 | INTERNAL_SIZE_T prevsz; /* size of previous contiguous chunk */ | |
2406 | mchunkptr bck; /* misc temp for linking */ | |
2407 | mchunkptr fwd; /* misc temp for linking */ | |
2408 | int islr; /* track whether merging with last_remainder */ | |
2409 | ||
2410 | if (mem == 0) /* free(0) has no effect */ | |
2411 | return; | |
2412 | ||
2413 | p = mem2chunk(mem); | |
2414 | hd = p->size; | |
2415 | ||
2416 | #if HAVE_MMAP | |
2417 | if (hd & IS_MMAPPED) /* release mmapped memory. */ | |
2418 | { | |
2419 | munmap_chunk(p); | |
2420 | return; | |
2421 | } | |
2422 | #endif | |
2423 | ||
2424 | check_inuse_chunk(p); | |
2425 | ||
2426 | sz = hd & ~PREV_INUSE; | |
2427 | next = chunk_at_offset(p, sz); | |
2428 | nextsz = chunksize(next); | |
2429 | ||
2430 | if (next == top) /* merge with top */ | |
2431 | { | |
2432 | sz += nextsz; | |
2433 | ||
2434 | if (!(hd & PREV_INUSE)) /* consolidate backward */ | |
2435 | { | |
2436 | prevsz = p->prev_size; | |
2437 | p = chunk_at_offset(p, -((long) prevsz)); | |
2438 | sz += prevsz; | |
2439 | unlink(p, bck, fwd); | |
2440 | } | |
2441 | ||
2442 | set_head(p, sz | PREV_INUSE); | |
2443 | top = p; | |
2444 | if ((unsigned long)(sz) >= (unsigned long)trim_threshold) | |
2445 | malloc_trim(top_pad); | |
2446 | return; | |
2447 | } | |
2448 | ||
2449 | set_head(next, nextsz); /* clear inuse bit */ | |
2450 | ||
2451 | islr = 0; | |
2452 | ||
2453 | if (!(hd & PREV_INUSE)) /* consolidate backward */ | |
2454 | { | |
2455 | prevsz = p->prev_size; | |
2456 | p = chunk_at_offset(p, -((long) prevsz)); | |
2457 | sz += prevsz; | |
2458 | ||
2459 | if (p->fd == last_remainder) /* keep as last_remainder */ | |
2460 | islr = 1; | |
2461 | else | |
2462 | unlink(p, bck, fwd); | |
2463 | } | |
2464 | ||
2465 | if (!(inuse_bit_at_offset(next, nextsz))) /* consolidate forward */ | |
2466 | { | |
2467 | sz += nextsz; | |
2468 | ||
2469 | if (!islr && next->fd == last_remainder) /* re-insert last_remainder */ | |
2470 | { | |
2471 | islr = 1; | |
2472 | link_last_remainder(p); | |
2473 | } | |
2474 | else | |
2475 | unlink(next, bck, fwd); | |
2476 | } | |
2477 | ||
2478 | ||
2479 | set_head(p, sz | PREV_INUSE); | |
2480 | set_foot(p, sz); | |
2481 | if (!islr) | |
2482 | frontlink(p, sz, idx, bck, fwd); | |
2483 | } | |
2484 | ||
2485 | ||
2486 | \f | |
2487 | ||
2488 | ||
2489 | /* | |
2490 | ||
2491 | Realloc algorithm: | |
2492 | ||
2493 | Chunks that were obtained via mmap cannot be extended or shrunk | |
2494 | unless HAVE_MREMAP is defined, in which case mremap is used. | |
2495 | Otherwise, if their reallocation is for additional space, they are | |
2496 | copied. If for less, they are just left alone. | |
2497 | ||
2498 | Otherwise, if the reallocation is for additional space, and the | |
2499 | chunk can be extended, it is, else a malloc-copy-free sequence is | |
2500 | taken. There are several different ways that a chunk could be | |
2501 | extended. All are tried: | |
2502 | ||
2503 | * Extending forward into following adjacent free chunk. | |
2504 | * Shifting backwards, joining preceding adjacent space | |
2505 | * Both shifting backwards and extending forward. | |
2506 | * Extending into newly sbrked space | |
2507 | ||
2508 | Unless the #define REALLOC_ZERO_BYTES_FREES is set, realloc with a | |
2509 | size argument of zero (re)allocates a minimum-sized chunk. | |
2510 | ||
2511 | If the reallocation is for less space, and the new request is for | |
2512 | a `small' (<512 bytes) size, then the newly unused space is lopped | |
2513 | off and freed. | |
2514 | ||
2515 | The old unix realloc convention of allowing the last-free'd chunk | |
2516 | to be used as an argument to realloc is no longer supported. | |
2517 | I don't know of any programs still relying on this feature, | |
2518 | and allowing it would also allow too many other incorrect | |
2519 | usages of realloc to be sensible. | |
2520 | ||
2521 | ||
2522 | */ | |
2523 | ||
2524 | ||
2525 | #if __STD_C | |
2526 | Void_t* rEALLOc(Void_t* oldmem, size_t bytes) | |
2527 | #else | |
2528 | Void_t* rEALLOc(oldmem, bytes) Void_t* oldmem; size_t bytes; | |
2529 | #endif | |
2530 | { | |
2531 | INTERNAL_SIZE_T nb; /* padded request size */ | |
2532 | ||
2533 | mchunkptr oldp; /* chunk corresponding to oldmem */ | |
2534 | INTERNAL_SIZE_T oldsize; /* its size */ | |
2535 | ||
2536 | mchunkptr newp; /* chunk to return */ | |
2537 | INTERNAL_SIZE_T newsize; /* its size */ | |
2538 | Void_t* newmem; /* corresponding user mem */ | |
2539 | ||
2540 | mchunkptr next; /* next contiguous chunk after oldp */ | |
2541 | INTERNAL_SIZE_T nextsize; /* its size */ | |
2542 | ||
2543 | mchunkptr prev; /* previous contiguous chunk before oldp */ | |
2544 | INTERNAL_SIZE_T prevsize; /* its size */ | |
2545 | ||
2546 | mchunkptr remainder; /* holds split off extra space from newp */ | |
2547 | INTERNAL_SIZE_T remainder_size; /* its size */ | |
2548 | ||
2549 | mchunkptr bck; /* misc temp for linking */ | |
2550 | mchunkptr fwd; /* misc temp for linking */ | |
2551 | ||
2552 | #ifdef REALLOC_ZERO_BYTES_FREES | |
2553 | if (bytes == 0) { fREe(oldmem); return 0; } | |
2554 | #endif | |
2555 | ||
2556 | if ((long)bytes < 0) return 0; | |
2557 | ||
2558 | /* realloc of null is supposed to be same as malloc */ | |
2559 | if (oldmem == 0) return mALLOc(bytes); | |
2560 | ||
2561 | newp = oldp = mem2chunk(oldmem); | |
2562 | newsize = oldsize = chunksize(oldp); | |
2563 | ||
2564 | ||
2565 | nb = request2size(bytes); | |
2566 | ||
2567 | #if HAVE_MMAP | |
2568 | if (chunk_is_mmapped(oldp)) | |
2569 | { | |
2570 | #if HAVE_MREMAP | |
2571 | newp = mremap_chunk(oldp, nb); | |
2572 | if(newp) return chunk2mem(newp); | |
2573 | #endif | |
2574 | /* Note the extra SIZE_SZ overhead. */ | |
2575 | if(oldsize - SIZE_SZ >= nb) return oldmem; /* do nothing */ | |
2576 | /* Must alloc, copy, free. */ | |
2577 | newmem = mALLOc(bytes); | |
2578 | if (newmem == 0) return 0; /* propagate failure */ | |
2579 | MALLOC_COPY(newmem, oldmem, oldsize - 2*SIZE_SZ); | |
2580 | munmap_chunk(oldp); | |
2581 | return newmem; | |
2582 | } | |
2583 | #endif | |
2584 | ||
2585 | check_inuse_chunk(oldp); | |
2586 | ||
2587 | if ((long)(oldsize) < (long)(nb)) | |
2588 | { | |
2589 | ||
2590 | /* Try expanding forward */ | |
2591 | ||
2592 | next = chunk_at_offset(oldp, oldsize); | |
2593 | if (next == top || !inuse(next)) | |
2594 | { | |
2595 | nextsize = chunksize(next); | |
2596 | ||
2597 | /* Forward into top only if a remainder */ | |
2598 | if (next == top) | |
2599 | { | |
8bde7f77 WD |
2600 | if ((long)(nextsize + newsize) >= (long)(nb + MINSIZE)) |
2601 | { | |
2602 | newsize += nextsize; | |
2603 | top = chunk_at_offset(oldp, nb); | |
2604 | set_head(top, (newsize - nb) | PREV_INUSE); | |
2605 | set_head_size(oldp, nb); | |
2606 | return chunk2mem(oldp); | |
2607 | } | |
217c9dad WD |
2608 | } |
2609 | ||
2610 | /* Forward into next chunk */ | |
2611 | else if (((long)(nextsize + newsize) >= (long)(nb))) | |
2612 | { | |
8bde7f77 WD |
2613 | unlink(next, bck, fwd); |
2614 | newsize += nextsize; | |
2615 | goto split; | |
217c9dad WD |
2616 | } |
2617 | } | |
2618 | else | |
2619 | { | |
2620 | next = 0; | |
2621 | nextsize = 0; | |
2622 | } | |
2623 | ||
2624 | /* Try shifting backwards. */ | |
2625 | ||
2626 | if (!prev_inuse(oldp)) | |
2627 | { | |
2628 | prev = prev_chunk(oldp); | |
2629 | prevsize = chunksize(prev); | |
2630 | ||
2631 | /* try forward + backward first to save a later consolidation */ | |
2632 | ||
2633 | if (next != 0) | |
2634 | { | |
8bde7f77 WD |
2635 | /* into top */ |
2636 | if (next == top) | |
2637 | { | |
2638 | if ((long)(nextsize + prevsize + newsize) >= (long)(nb + MINSIZE)) | |
2639 | { | |
2640 | unlink(prev, bck, fwd); | |
2641 | newp = prev; | |
2642 | newsize += prevsize + nextsize; | |
2643 | newmem = chunk2mem(newp); | |
2644 | MALLOC_COPY(newmem, oldmem, oldsize - SIZE_SZ); | |
2645 | top = chunk_at_offset(newp, nb); | |
2646 | set_head(top, (newsize - nb) | PREV_INUSE); | |
2647 | set_head_size(newp, nb); | |
2648 | return newmem; | |
2649 | } | |
2650 | } | |
2651 | ||
2652 | /* into next chunk */ | |
2653 | else if (((long)(nextsize + prevsize + newsize) >= (long)(nb))) | |
2654 | { | |
2655 | unlink(next, bck, fwd); | |
2656 | unlink(prev, bck, fwd); | |
2657 | newp = prev; | |
2658 | newsize += nextsize + prevsize; | |
2659 | newmem = chunk2mem(newp); | |
2660 | MALLOC_COPY(newmem, oldmem, oldsize - SIZE_SZ); | |
2661 | goto split; | |
2662 | } | |
217c9dad WD |
2663 | } |
2664 | ||
2665 | /* backward only */ | |
2666 | if (prev != 0 && (long)(prevsize + newsize) >= (long)nb) | |
2667 | { | |
8bde7f77 WD |
2668 | unlink(prev, bck, fwd); |
2669 | newp = prev; | |
2670 | newsize += prevsize; | |
2671 | newmem = chunk2mem(newp); | |
2672 | MALLOC_COPY(newmem, oldmem, oldsize - SIZE_SZ); | |
2673 | goto split; | |
217c9dad WD |
2674 | } |
2675 | } | |
2676 | ||
2677 | /* Must allocate */ | |
2678 | ||
2679 | newmem = mALLOc (bytes); | |
2680 | ||
2681 | if (newmem == 0) /* propagate failure */ | |
2682 | return 0; | |
2683 | ||
2684 | /* Avoid copy if newp is next chunk after oldp. */ | |
2685 | /* (This can only happen when new chunk is sbrk'ed.) */ | |
2686 | ||
2687 | if ( (newp = mem2chunk(newmem)) == next_chunk(oldp)) | |
2688 | { | |
2689 | newsize += chunksize(newp); | |
2690 | newp = oldp; | |
2691 | goto split; | |
2692 | } | |
2693 | ||
2694 | /* Otherwise copy, free, and exit */ | |
2695 | MALLOC_COPY(newmem, oldmem, oldsize - SIZE_SZ); | |
2696 | fREe(oldmem); | |
2697 | return newmem; | |
2698 | } | |
2699 | ||
2700 | ||
2701 | split: /* split off extra room in old or expanded chunk */ | |
2702 | ||
2703 | if (newsize - nb >= MINSIZE) /* split off remainder */ | |
2704 | { | |
2705 | remainder = chunk_at_offset(newp, nb); | |
2706 | remainder_size = newsize - nb; | |
2707 | set_head_size(newp, nb); | |
2708 | set_head(remainder, remainder_size | PREV_INUSE); | |
2709 | set_inuse_bit_at_offset(remainder, remainder_size); | |
2710 | fREe(chunk2mem(remainder)); /* let free() deal with it */ | |
2711 | } | |
2712 | else | |
2713 | { | |
2714 | set_head_size(newp, newsize); | |
2715 | set_inuse_bit_at_offset(newp, newsize); | |
2716 | } | |
2717 | ||
2718 | check_inuse_chunk(newp); | |
2719 | return chunk2mem(newp); | |
2720 | } | |
2721 | ||
2722 | ||
2723 | \f | |
2724 | ||
2725 | /* | |
2726 | ||
2727 | memalign algorithm: | |
2728 | ||
2729 | memalign requests more than enough space from malloc, finds a spot | |
2730 | within that chunk that meets the alignment request, and then | |
2731 | possibly frees the leading and trailing space. | |
2732 | ||
2733 | The alignment argument must be a power of two. This property is not | |
2734 | checked by memalign, so misuse may result in random runtime errors. | |
2735 | ||
2736 | 8-byte alignment is guaranteed by normal malloc calls, so don't | |
2737 | bother calling memalign with an argument of 8 or less. | |
2738 | ||
2739 | Overreliance on memalign is a sure way to fragment space. | |
2740 | ||
2741 | */ | |
2742 | ||
2743 | ||
2744 | #if __STD_C | |
2745 | Void_t* mEMALIGn(size_t alignment, size_t bytes) | |
2746 | #else | |
2747 | Void_t* mEMALIGn(alignment, bytes) size_t alignment; size_t bytes; | |
2748 | #endif | |
2749 | { | |
2750 | INTERNAL_SIZE_T nb; /* padded request size */ | |
2751 | char* m; /* memory returned by malloc call */ | |
2752 | mchunkptr p; /* corresponding chunk */ | |
2753 | char* brk; /* alignment point within p */ | |
2754 | mchunkptr newp; /* chunk to return */ | |
2755 | INTERNAL_SIZE_T newsize; /* its size */ | |
2756 | INTERNAL_SIZE_T leadsize; /* leading space befor alignment point */ | |
2757 | mchunkptr remainder; /* spare room at end to split off */ | |
2758 | long remainder_size; /* its size */ | |
2759 | ||
2760 | if ((long)bytes < 0) return 0; | |
2761 | ||
2762 | /* If need less alignment than we give anyway, just relay to malloc */ | |
2763 | ||
2764 | if (alignment <= MALLOC_ALIGNMENT) return mALLOc(bytes); | |
2765 | ||
2766 | /* Otherwise, ensure that it is at least a minimum chunk size */ | |
2767 | ||
2768 | if (alignment < MINSIZE) alignment = MINSIZE; | |
2769 | ||
2770 | /* Call malloc with worst case padding to hit alignment. */ | |
2771 | ||
2772 | nb = request2size(bytes); | |
2773 | m = (char*)(mALLOc(nb + alignment + MINSIZE)); | |
2774 | ||
2775 | if (m == 0) return 0; /* propagate failure */ | |
2776 | ||
2777 | p = mem2chunk(m); | |
2778 | ||
2779 | if ((((unsigned long)(m)) % alignment) == 0) /* aligned */ | |
2780 | { | |
2781 | #if HAVE_MMAP | |
2782 | if(chunk_is_mmapped(p)) | |
2783 | return chunk2mem(p); /* nothing more to do */ | |
2784 | #endif | |
2785 | } | |
2786 | else /* misaligned */ | |
2787 | { | |
2788 | /* | |
2789 | Find an aligned spot inside chunk. | |
2790 | Since we need to give back leading space in a chunk of at | |
2791 | least MINSIZE, if the first calculation places us at | |
2792 | a spot with less than MINSIZE leader, we can move to the | |
2793 | next aligned spot -- we've allocated enough total room so that | |
2794 | this is always possible. | |
2795 | */ | |
2796 | ||
2797 | brk = (char*)mem2chunk(((unsigned long)(m + alignment - 1)) & -((signed) alignment)); | |
2798 | if ((long)(brk - (char*)(p)) < MINSIZE) brk = brk + alignment; | |
2799 | ||
2800 | newp = (mchunkptr)brk; | |
2801 | leadsize = brk - (char*)(p); | |
2802 | newsize = chunksize(p) - leadsize; | |
2803 | ||
2804 | #if HAVE_MMAP | |
2805 | if(chunk_is_mmapped(p)) | |
2806 | { | |
2807 | newp->prev_size = p->prev_size + leadsize; | |
2808 | set_head(newp, newsize|IS_MMAPPED); | |
2809 | return chunk2mem(newp); | |
2810 | } | |
2811 | #endif | |
2812 | ||
2813 | /* give back leader, use the rest */ | |
2814 | ||
2815 | set_head(newp, newsize | PREV_INUSE); | |
2816 | set_inuse_bit_at_offset(newp, newsize); | |
2817 | set_head_size(p, leadsize); | |
2818 | fREe(chunk2mem(p)); | |
2819 | p = newp; | |
2820 | ||
2821 | assert (newsize >= nb && (((unsigned long)(chunk2mem(p))) % alignment) == 0); | |
2822 | } | |
2823 | ||
2824 | /* Also give back spare room at the end */ | |
2825 | ||
2826 | remainder_size = chunksize(p) - nb; | |
2827 | ||
2828 | if (remainder_size >= (long)MINSIZE) | |
2829 | { | |
2830 | remainder = chunk_at_offset(p, nb); | |
2831 | set_head(remainder, remainder_size | PREV_INUSE); | |
2832 | set_head_size(p, nb); | |
2833 | fREe(chunk2mem(remainder)); | |
2834 | } | |
2835 | ||
2836 | check_inuse_chunk(p); | |
2837 | return chunk2mem(p); | |
2838 | ||
2839 | } | |
2840 | ||
2841 | \f | |
2842 | ||
2843 | ||
2844 | /* | |
2845 | valloc just invokes memalign with alignment argument equal | |
2846 | to the page size of the system (or as near to this as can | |
2847 | be figured out from all the includes/defines above.) | |
2848 | */ | |
2849 | ||
2850 | #if __STD_C | |
2851 | Void_t* vALLOc(size_t bytes) | |
2852 | #else | |
2853 | Void_t* vALLOc(bytes) size_t bytes; | |
2854 | #endif | |
2855 | { | |
2856 | return mEMALIGn (malloc_getpagesize, bytes); | |
2857 | } | |
2858 | ||
2859 | /* | |
2860 | pvalloc just invokes valloc for the nearest pagesize | |
2861 | that will accommodate request | |
2862 | */ | |
2863 | ||
2864 | ||
2865 | #if __STD_C | |
2866 | Void_t* pvALLOc(size_t bytes) | |
2867 | #else | |
2868 | Void_t* pvALLOc(bytes) size_t bytes; | |
2869 | #endif | |
2870 | { | |
2871 | size_t pagesize = malloc_getpagesize; | |
2872 | return mEMALIGn (pagesize, (bytes + pagesize - 1) & ~(pagesize - 1)); | |
2873 | } | |
2874 | ||
2875 | /* | |
2876 | ||
2877 | calloc calls malloc, then zeroes out the allocated chunk. | |
2878 | ||
2879 | */ | |
2880 | ||
2881 | #if __STD_C | |
2882 | Void_t* cALLOc(size_t n, size_t elem_size) | |
2883 | #else | |
2884 | Void_t* cALLOc(n, elem_size) size_t n; size_t elem_size; | |
2885 | #endif | |
2886 | { | |
2887 | mchunkptr p; | |
2888 | INTERNAL_SIZE_T csz; | |
2889 | ||
2890 | INTERNAL_SIZE_T sz = n * elem_size; | |
2891 | ||
2892 | ||
2893 | /* check if expand_top called, in which case don't need to clear */ | |
2894 | #if MORECORE_CLEARS | |
2895 | mchunkptr oldtop = top; | |
2896 | INTERNAL_SIZE_T oldtopsize = chunksize(top); | |
2897 | #endif | |
2898 | Void_t* mem = mALLOc (sz); | |
2899 | ||
2900 | if ((long)n < 0) return 0; | |
2901 | ||
2902 | if (mem == 0) | |
2903 | return 0; | |
2904 | else | |
2905 | { | |
2906 | p = mem2chunk(mem); | |
2907 | ||
2908 | /* Two optional cases in which clearing not necessary */ | |
2909 | ||
2910 | ||
2911 | #if HAVE_MMAP | |
2912 | if (chunk_is_mmapped(p)) return mem; | |
2913 | #endif | |
2914 | ||
2915 | csz = chunksize(p); | |
2916 | ||
2917 | #if MORECORE_CLEARS | |
2918 | if (p == oldtop && csz > oldtopsize) | |
2919 | { | |
2920 | /* clear only the bytes from non-freshly-sbrked memory */ | |
2921 | csz = oldtopsize; | |
2922 | } | |
2923 | #endif | |
2924 | ||
2925 | MALLOC_ZERO(mem, csz - SIZE_SZ); | |
2926 | return mem; | |
2927 | } | |
2928 | } | |
2929 | ||
2930 | /* | |
2931 | ||
2932 | cfree just calls free. It is needed/defined on some systems | |
2933 | that pair it with calloc, presumably for odd historical reasons. | |
2934 | ||
2935 | */ | |
2936 | ||
2937 | #if !defined(INTERNAL_LINUX_C_LIB) || !defined(__ELF__) | |
2938 | #if __STD_C | |
2939 | void cfree(Void_t *mem) | |
2940 | #else | |
2941 | void cfree(mem) Void_t *mem; | |
2942 | #endif | |
2943 | { | |
2944 | fREe(mem); | |
2945 | } | |
2946 | #endif | |
2947 | ||
2948 | \f | |
2949 | ||
2950 | /* | |
2951 | ||
2952 | Malloc_trim gives memory back to the system (via negative | |
2953 | arguments to sbrk) if there is unused memory at the `high' end of | |
2954 | the malloc pool. You can call this after freeing large blocks of | |
2955 | memory to potentially reduce the system-level memory requirements | |
2956 | of a program. However, it cannot guarantee to reduce memory. Under | |
2957 | some allocation patterns, some large free blocks of memory will be | |
2958 | locked between two used chunks, so they cannot be given back to | |
2959 | the system. | |
2960 | ||
2961 | The `pad' argument to malloc_trim represents the amount of free | |
2962 | trailing space to leave untrimmed. If this argument is zero, | |
2963 | only the minimum amount of memory to maintain internal data | |
2964 | structures will be left (one page or less). Non-zero arguments | |
2965 | can be supplied to maintain enough trailing space to service | |
2966 | future expected allocations without having to re-obtain memory | |
2967 | from the system. | |
2968 | ||
2969 | Malloc_trim returns 1 if it actually released any memory, else 0. | |
2970 | ||
2971 | */ | |
2972 | ||
2973 | #if __STD_C | |
2974 | int malloc_trim(size_t pad) | |
2975 | #else | |
2976 | int malloc_trim(pad) size_t pad; | |
2977 | #endif | |
2978 | { | |
2979 | long top_size; /* Amount of top-most memory */ | |
2980 | long extra; /* Amount to release */ | |
2981 | char* current_brk; /* address returned by pre-check sbrk call */ | |
2982 | char* new_brk; /* address returned by negative sbrk call */ | |
2983 | ||
2984 | unsigned long pagesz = malloc_getpagesize; | |
2985 | ||
2986 | top_size = chunksize(top); | |
2987 | extra = ((top_size - pad - MINSIZE + (pagesz-1)) / pagesz - 1) * pagesz; | |
2988 | ||
2989 | if (extra < (long)pagesz) /* Not enough memory to release */ | |
2990 | return 0; | |
2991 | ||
2992 | else | |
2993 | { | |
2994 | /* Test to make sure no one else called sbrk */ | |
2995 | current_brk = (char*)(MORECORE (0)); | |
2996 | if (current_brk != (char*)(top) + top_size) | |
2997 | return 0; /* Apparently we don't own memory; must fail */ | |
2998 | ||
2999 | else | |
3000 | { | |
3001 | new_brk = (char*)(MORECORE (-extra)); | |
3002 | ||
3003 | if (new_brk == (char*)(MORECORE_FAILURE)) /* sbrk failed? */ | |
3004 | { | |
8bde7f77 WD |
3005 | /* Try to figure out what we have */ |
3006 | current_brk = (char*)(MORECORE (0)); | |
3007 | top_size = current_brk - (char*)top; | |
3008 | if (top_size >= (long)MINSIZE) /* if not, we are very very dead! */ | |
3009 | { | |
3010 | sbrked_mem = current_brk - sbrk_base; | |
3011 | set_head(top, top_size | PREV_INUSE); | |
3012 | } | |
3013 | check_chunk(top); | |
3014 | return 0; | |
217c9dad WD |
3015 | } |
3016 | ||
3017 | else | |
3018 | { | |
8bde7f77 WD |
3019 | /* Success. Adjust top accordingly. */ |
3020 | set_head(top, (top_size - extra) | PREV_INUSE); | |
3021 | sbrked_mem -= extra; | |
3022 | check_chunk(top); | |
3023 | return 1; | |
217c9dad WD |
3024 | } |
3025 | } | |
3026 | } | |
3027 | } | |
3028 | ||
3029 | \f | |
3030 | ||
3031 | /* | |
3032 | malloc_usable_size: | |
3033 | ||
3034 | This routine tells you how many bytes you can actually use in an | |
3035 | allocated chunk, which may be more than you requested (although | |
3036 | often not). You can use this many bytes without worrying about | |
3037 | overwriting other allocated objects. Not a particularly great | |
3038 | programming practice, but still sometimes useful. | |
3039 | ||
3040 | */ | |
3041 | ||
3042 | #if __STD_C | |
3043 | size_t malloc_usable_size(Void_t* mem) | |
3044 | #else | |
3045 | size_t malloc_usable_size(mem) Void_t* mem; | |
3046 | #endif | |
3047 | { | |
3048 | mchunkptr p; | |
3049 | if (mem == 0) | |
3050 | return 0; | |
3051 | else | |
3052 | { | |
3053 | p = mem2chunk(mem); | |
3054 | if(!chunk_is_mmapped(p)) | |
3055 | { | |
3056 | if (!inuse(p)) return 0; | |
3057 | check_inuse_chunk(p); | |
3058 | return chunksize(p) - SIZE_SZ; | |
3059 | } | |
3060 | return chunksize(p) - 2*SIZE_SZ; | |
3061 | } | |
3062 | } | |
3063 | ||
3064 | ||
3065 | \f | |
3066 | ||
3067 | /* Utility to update current_mallinfo for malloc_stats and mallinfo() */ | |
3068 | ||
3069 | #if 0 | |
3070 | static void malloc_update_mallinfo() | |
3071 | { | |
3072 | int i; | |
3073 | mbinptr b; | |
3074 | mchunkptr p; | |
3075 | #ifdef DEBUG | |
3076 | mchunkptr q; | |
3077 | #endif | |
3078 | ||
3079 | INTERNAL_SIZE_T avail = chunksize(top); | |
3080 | int navail = ((long)(avail) >= (long)MINSIZE)? 1 : 0; | |
3081 | ||
3082 | for (i = 1; i < NAV; ++i) | |
3083 | { | |
3084 | b = bin_at(i); | |
3085 | for (p = last(b); p != b; p = p->bk) | |
3086 | { | |
3087 | #ifdef DEBUG | |
3088 | check_free_chunk(p); | |
3089 | for (q = next_chunk(p); | |
8bde7f77 WD |
3090 | q < top && inuse(q) && (long)(chunksize(q)) >= (long)MINSIZE; |
3091 | q = next_chunk(q)) | |
3092 | check_inuse_chunk(q); | |
217c9dad WD |
3093 | #endif |
3094 | avail += chunksize(p); | |
3095 | navail++; | |
3096 | } | |
3097 | } | |
3098 | ||
3099 | current_mallinfo.ordblks = navail; | |
3100 | current_mallinfo.uordblks = sbrked_mem - avail; | |
3101 | current_mallinfo.fordblks = avail; | |
3102 | current_mallinfo.hblks = n_mmaps; | |
3103 | current_mallinfo.hblkhd = mmapped_mem; | |
3104 | current_mallinfo.keepcost = chunksize(top); | |
3105 | ||
3106 | } | |
3107 | #endif /* 0 */ | |
3108 | ||
3109 | \f | |
3110 | ||
3111 | /* | |
3112 | ||
3113 | malloc_stats: | |
3114 | ||
3115 | Prints on the amount of space obtain from the system (both | |
3116 | via sbrk and mmap), the maximum amount (which may be more than | |
3117 | current if malloc_trim and/or munmap got called), the maximum | |
3118 | number of simultaneous mmap regions used, and the current number | |
3119 | of bytes allocated via malloc (or realloc, etc) but not yet | |
3120 | freed. (Note that this is the number of bytes allocated, not the | |
3121 | number requested. It will be larger than the number requested | |
3122 | because of alignment and bookkeeping overhead.) | |
3123 | ||
3124 | */ | |
3125 | ||
3126 | #if 0 | |
3127 | void malloc_stats() | |
3128 | { | |
3129 | malloc_update_mallinfo(); | |
3130 | printf("max system bytes = %10u\n", | |
8bde7f77 | 3131 | (unsigned int)(max_total_mem)); |
217c9dad | 3132 | printf("system bytes = %10u\n", |
8bde7f77 | 3133 | (unsigned int)(sbrked_mem + mmapped_mem)); |
217c9dad | 3134 | printf("in use bytes = %10u\n", |
8bde7f77 | 3135 | (unsigned int)(current_mallinfo.uordblks + mmapped_mem)); |
217c9dad WD |
3136 | #if HAVE_MMAP |
3137 | printf("max mmap regions = %10u\n", | |
8bde7f77 | 3138 | (unsigned int)max_n_mmaps); |
217c9dad WD |
3139 | #endif |
3140 | } | |
3141 | #endif /* 0 */ | |
3142 | ||
3143 | /* | |
3144 | mallinfo returns a copy of updated current mallinfo. | |
3145 | */ | |
3146 | ||
3147 | #if 0 | |
3148 | struct mallinfo mALLINFo() | |
3149 | { | |
3150 | malloc_update_mallinfo(); | |
3151 | return current_mallinfo; | |
3152 | } | |
3153 | #endif /* 0 */ | |
3154 | ||
3155 | ||
3156 | \f | |
3157 | ||
3158 | /* | |
3159 | mallopt: | |
3160 | ||
3161 | mallopt is the general SVID/XPG interface to tunable parameters. | |
3162 | The format is to provide a (parameter-number, parameter-value) pair. | |
3163 | mallopt then sets the corresponding parameter to the argument | |
3164 | value if it can (i.e., so long as the value is meaningful), | |
3165 | and returns 1 if successful else 0. | |
3166 | ||
3167 | See descriptions of tunable parameters above. | |
3168 | ||
3169 | */ | |
3170 | ||
3171 | #if __STD_C | |
3172 | int mALLOPt(int param_number, int value) | |
3173 | #else | |
3174 | int mALLOPt(param_number, value) int param_number; int value; | |
3175 | #endif | |
3176 | { | |
3177 | switch(param_number) | |
3178 | { | |
3179 | case M_TRIM_THRESHOLD: | |
3180 | trim_threshold = value; return 1; | |
3181 | case M_TOP_PAD: | |
3182 | top_pad = value; return 1; | |
3183 | case M_MMAP_THRESHOLD: | |
3184 | mmap_threshold = value; return 1; | |
3185 | case M_MMAP_MAX: | |
3186 | #if HAVE_MMAP | |
3187 | n_mmaps_max = value; return 1; | |
3188 | #else | |
3189 | if (value != 0) return 0; else n_mmaps_max = value; return 1; | |
3190 | #endif | |
3191 | ||
3192 | default: | |
3193 | return 0; | |
3194 | } | |
3195 | } | |
3196 | ||
3197 | /* | |
3198 | ||
3199 | History: | |
3200 | ||
3201 | V2.6.6 Sun Dec 5 07:42:19 1999 Doug Lea (dl at gee) | |
3202 | * return null for negative arguments | |
3203 | * Added Several WIN32 cleanups from Martin C. Fong <mcfong@yahoo.com> | |
8bde7f77 WD |
3204 | * Add 'LACKS_SYS_PARAM_H' for those systems without 'sys/param.h' |
3205 | (e.g. WIN32 platforms) | |
3206 | * Cleanup up header file inclusion for WIN32 platforms | |
3207 | * Cleanup code to avoid Microsoft Visual C++ compiler complaints | |
3208 | * Add 'USE_DL_PREFIX' to quickly allow co-existence with existing | |
3209 | memory allocation routines | |
3210 | * Set 'malloc_getpagesize' for WIN32 platforms (needs more work) | |
3211 | * Use 'assert' rather than 'ASSERT' in WIN32 code to conform to | |
217c9dad | 3212 | usage of 'assert' in non-WIN32 code |
8bde7f77 WD |
3213 | * Improve WIN32 'sbrk()' emulation's 'findRegion()' routine to |
3214 | avoid infinite loop | |
217c9dad WD |
3215 | * Always call 'fREe()' rather than 'free()' |
3216 | ||
3217 | V2.6.5 Wed Jun 17 15:57:31 1998 Doug Lea (dl at gee) | |
3218 | * Fixed ordering problem with boundary-stamping | |
3219 | ||
3220 | V2.6.3 Sun May 19 08:17:58 1996 Doug Lea (dl at gee) | |
3221 | * Added pvalloc, as recommended by H.J. Liu | |
3222 | * Added 64bit pointer support mainly from Wolfram Gloger | |
3223 | * Added anonymously donated WIN32 sbrk emulation | |
3224 | * Malloc, calloc, getpagesize: add optimizations from Raymond Nijssen | |
3225 | * malloc_extend_top: fix mask error that caused wastage after | |
8bde7f77 | 3226 | foreign sbrks |
217c9dad WD |
3227 | * Add linux mremap support code from HJ Liu |
3228 | ||
3229 | V2.6.2 Tue Dec 5 06:52:55 1995 Doug Lea (dl at gee) | |
3230 | * Integrated most documentation with the code. | |
3231 | * Add support for mmap, with help from | |
8bde7f77 | 3232 | Wolfram Gloger (Gloger@lrz.uni-muenchen.de). |
217c9dad WD |
3233 | * Use last_remainder in more cases. |
3234 | * Pack bins using idea from colin@nyx10.cs.du.edu | |
3235 | * Use ordered bins instead of best-fit threshhold | |
3236 | * Eliminate block-local decls to simplify tracing and debugging. | |
3237 | * Support another case of realloc via move into top | |
3238 | * Fix error occuring when initial sbrk_base not word-aligned. | |
3239 | * Rely on page size for units instead of SBRK_UNIT to | |
8bde7f77 | 3240 | avoid surprises about sbrk alignment conventions. |
217c9dad | 3241 | * Add mallinfo, mallopt. Thanks to Raymond Nijssen |
8bde7f77 | 3242 | (raymond@es.ele.tue.nl) for the suggestion. |
217c9dad WD |
3243 | * Add `pad' argument to malloc_trim and top_pad mallopt parameter. |
3244 | * More precautions for cases where other routines call sbrk, | |
8bde7f77 | 3245 | courtesy of Wolfram Gloger (Gloger@lrz.uni-muenchen.de). |
217c9dad | 3246 | * Added macros etc., allowing use in linux libc from |
8bde7f77 | 3247 | H.J. Lu (hjl@gnu.ai.mit.edu) |
217c9dad WD |
3248 | * Inverted this history list |
3249 | ||
3250 | V2.6.1 Sat Dec 2 14:10:57 1995 Doug Lea (dl at gee) | |
3251 | * Re-tuned and fixed to behave more nicely with V2.6.0 changes. | |
3252 | * Removed all preallocation code since under current scheme | |
8bde7f77 WD |
3253 | the work required to undo bad preallocations exceeds |
3254 | the work saved in good cases for most test programs. | |
217c9dad | 3255 | * No longer use return list or unconsolidated bins since |
8bde7f77 WD |
3256 | no scheme using them consistently outperforms those that don't |
3257 | given above changes. | |
217c9dad WD |
3258 | * Use best fit for very large chunks to prevent some worst-cases. |
3259 | * Added some support for debugging | |
3260 | ||
3261 | V2.6.0 Sat Nov 4 07:05:23 1995 Doug Lea (dl at gee) | |
3262 | * Removed footers when chunks are in use. Thanks to | |
8bde7f77 | 3263 | Paul Wilson (wilson@cs.texas.edu) for the suggestion. |
217c9dad WD |
3264 | |
3265 | V2.5.4 Wed Nov 1 07:54:51 1995 Doug Lea (dl at gee) | |
3266 | * Added malloc_trim, with help from Wolfram Gloger | |
8bde7f77 | 3267 | (wmglo@Dent.MED.Uni-Muenchen.DE). |
217c9dad WD |
3268 | |
3269 | V2.5.3 Tue Apr 26 10:16:01 1994 Doug Lea (dl at g) | |
3270 | ||
3271 | V2.5.2 Tue Apr 5 16:20:40 1994 Doug Lea (dl at g) | |
3272 | * realloc: try to expand in both directions | |
3273 | * malloc: swap order of clean-bin strategy; | |
3274 | * realloc: only conditionally expand backwards | |
3275 | * Try not to scavenge used bins | |
3276 | * Use bin counts as a guide to preallocation | |
3277 | * Occasionally bin return list chunks in first scan | |
3278 | * Add a few optimizations from colin@nyx10.cs.du.edu | |
3279 | ||
3280 | V2.5.1 Sat Aug 14 15:40:43 1993 Doug Lea (dl at g) | |
3281 | * faster bin computation & slightly different binning | |
3282 | * merged all consolidations to one part of malloc proper | |
8bde7f77 | 3283 | (eliminating old malloc_find_space & malloc_clean_bin) |
217c9dad WD |
3284 | * Scan 2 returns chunks (not just 1) |
3285 | * Propagate failure in realloc if malloc returns 0 | |
3286 | * Add stuff to allow compilation on non-ANSI compilers | |
8bde7f77 | 3287 | from kpv@research.att.com |
217c9dad WD |
3288 | |
3289 | V2.5 Sat Aug 7 07:41:59 1993 Doug Lea (dl at g.oswego.edu) | |
3290 | * removed potential for odd address access in prev_chunk | |
3291 | * removed dependency on getpagesize.h | |
3292 | * misc cosmetics and a bit more internal documentation | |
3293 | * anticosmetics: mangled names in macros to evade debugger strangeness | |
3294 | * tested on sparc, hp-700, dec-mips, rs6000 | |
8bde7f77 WD |
3295 | with gcc & native cc (hp, dec only) allowing |
3296 | Detlefs & Zorn comparison study (in SIGPLAN Notices.) | |
217c9dad WD |
3297 | |
3298 | Trial version Fri Aug 28 13:14:29 1992 Doug Lea (dl at g.oswego.edu) | |
3299 | * Based loosely on libg++-1.2X malloc. (It retains some of the overall | |
8bde7f77 | 3300 | structure of old version, but most details differ.) |
217c9dad WD |
3301 | |
3302 | */ |