OpenCores
URL https://opencores.org/ocsvn/or1k/or1k/trunk

Subversion Repositories or1k

[/] [or1k/] [trunk/] [newlib/] [newlib/] [libc/] [stdlib/] [mallocr.c] - Blame information for rev 57

Go to most recent revision | Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.