source: trunk/src/dnmalloc.c @ 481

Last change on this file since 481 was 481, checked in by katerina, 6 years ago

Enhancements and fixes for tickets #374, #375, #376, #377, #378, and #379.

File size: 164.9 KB
Line 
1/* DistriNet malloc (dnmalloc): a more secure memory allocator.
2   Copyright (C) 2005, Yves Younan, Wouter Joosen, Frank Piessens
3   and Rainer Wichmann
4
5   The authors can be contacted by:
6      Email: dnmalloc@fort-knox.org
7      Address:
8#if defined(WITH_TPT)
9             Yves Younan
10             Celestijnenlaan 200A
11             B-3001 Heverlee
12             Belgium
13   
14   This library is free software; you can redistribute it and/or
15   modify it under the terms of the GNU Lesser General Public
16   License as published by the Free Software Foundation; either
17   version 2.1 of the License, or (at your option) any later version.
18
19   This library is distributed in the hope that it will be useful,
20   but WITHOUT ANY WARRANTY; without even the implied warranty of
21   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
22   Lesser General Public License for more details.
23
24   You should have received a copy of the GNU Lesser General Public
25   License along with this library; if not, write to the Free Software
26   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
27   
28*/
29
30/* Current version: dnmalloc 1.0 */
31/* Includes arc4random from OpenBSD, which is under the BDS license     */
32
33/* Versions:
34   0.1-0.5:
35   Proof of concept implementation by Hans Van den Eynden and Yves Younan
36   0.6-0.7:
37   Bug fixes by Yves Younan
38   0.8-1.0.beta4:
39   Reimplementation from scratch by Yves Younan
40   1.0.beta4:
41   Public release
42   1.0.beta5:
43   Prev_chunkinfo speeded up, was really slow because of the way we did lookups
44   A freechunkinfo region is now freed when it is completely empty and
45   not the current one
46
47   1.0 (Rainer Wichmann [support at la dash samhna dot org]):
48   ---------------------
49
50   Compiler warnings fixed
51   Define REALLOC_ZERO_BYTES_FREES because it's what GNU libc does
52       (and what the standard says)
53   Removed unused code
54   Fix       assert(aligned_OK(chunk(newp)));
55         ->  assert(aligned_OK(chunk(oldp)));
56   Fix statistics in sYSMALLOc
57   Fix overwrite of av->top in sYSMALLOc
58   Provide own assert(), glibc assert() doesn't work (calls malloc)
59   Fix bug in mEMALIGn(), put remainder in hashtable before calling fREe
60   Remove cfree, independent_cmalloc, independent_comalloc (untested
61       public functions not covered by any standard)
62   Provide posix_memalign (that one is in the standard)
63   Move the malloc_state struct to mmapped memory protected by guard pages
64   Add arc4random function to initialize random canary on startup
65   Implement random canary at end of (re|m)alloced/memaligned buffer,
66       check at free/realloc
67   Remove code conditional on !HAVE_MMAP, since mmap is required anyway.
68   Use standard HAVE_foo macros (as generated by autoconf) instead of LACKS_foo
69
70   Profiling: Reorder branches in hashtable_add, next_chunkinfo,
71                  prev_chunkinfo, hashtable_insert, mALLOc, fREe, request2size,
72                  checked_request2size (gcc predicts if{} branch to be taken).
73              Use UNLIKELY macro (gcc __builtin_expect()) where branch
74                  reordering would make the code awkward.
75
76   Portability: Hashtable always covers full 32bit address space to
77                avoid assumptions about memory layout.
78   Portability: Try hard to enforce mapping of mmapped memory into
79                32bit address space, even on 64bit systems.
80   Portability: Provide a dnmalloc_pthread_init() function, since
81                pthread locking on HP-UX only works if initialized
82                after the application has entered main().
83   Portability: On *BSD, pthread_mutex_lock is unusable since it
84                calls malloc, use spinlocks instead.
85   Portability: Dynamically detect whether the heap is within
86                32bit address range (e.g. on Linux x86_64, it isn't).
87                Don't use sbrk() if the heap is mapped to an address
88                outside the 32bit range, since this doesn't work with
89                the hashtable. New macro morecore32bit.
90               
91   Success on: HP-UX 11.11/pthread, Linux/pthread (32/64 bit),
92               FreeBSD/pthread, and Solaris 10 i386/pthread.
93   Fail    on: OpenBSD/pthread (in  _thread_machdep_save_float_state),
94               might be related to OpenBSD pthread internals (??).
95               Non-treaded version (#undef USE_MALLOC_LOCK)
96               works on OpenBSD.
97   
98   further to 1.0:
99   Valgrind client requests inserted (#define USE_VALGRIND)
100   Fix: malloc_consolidate (nextchunk->fd, nextchunk->bck may be NULL)
101   Portability: minsize = 32 bit on 64bit architecture
102   Minor cleanups
103   Fix: eliminate prototypes for memset, memcpy (they're in string.h)
104   Fix: one more malloc_consolidate segfault
105
106   There may be some bugs left in this version. please use with caution.
107*/
108
109
110
111/* Please read the following papers for documentation:
112
113   Yves Younan, Wouter Joosen, and Frank Piessens, A Methodology for Designing
114   Countermeasures against Current and Future Code Injection Attacks,
115   Proceedings of the Third IEEE International Information Assurance
116   Workshop 2005 (IWIA2005), College Park, Maryland, U.S.A., March 2005,
117   IEEE, IEEE Press.
118   http://www.fort-knox.org/younany_countermeasures.pdf
119   
120   Yves Younan, Wouter Joosen and Frank Piessens and Hans Van den
121   Eynden. Security of Memory Allocators for C and C++. Technical Report
122   CW419, Departement Computerwetenschappen, Katholieke Universiteit
123   Leuven, July 2005. http://www.fort-knox.org/CW419.pdf
124 
125 */
126
127/* Compile:
128   gcc -fPIC -rdynamic -c -Wall dnmalloc-portable.c
129   "Link":
130   Dynamic:
131   gcc -shared -Wl,-soname,libdnmalloc.so.0 -o libdnmalloc.so.0.0 dnmalloc-portable.o -lc
132   Static:
133   ar -rv libdnmalloc.a dnmalloc-portable.o
134   
135*/
136
137/*
138   dnmalloc is based on dlmalloc 2.7.2 (by Doug Lea (dl@cs.oswego.edu))
139   dlmalloc was released as public domain and contained the following license:
140   
141   "This is a version (aka dlmalloc) of malloc/free/realloc written by
142   Doug Lea and released to the public domain.  Use, modify, and
143   redistribute this code without permission or acknowledgement in any
144   way you wish.  Send questions, comments, complaints, performance
145   data, etc to dl@cs.oswego.edu
146   
147   * VERSION 2.7.2 Sat Aug 17 09:07:30 2002  Doug Lea  (dl at gee)
148   
149   Note: There may be an updated version of this malloc obtainable at
150   ftp://gee.cs.oswego.edu/pub/misc/malloc.c
151   Check before installing!"
152   
153*/
154
155/* The following preprocessor macros are tested,
156 *   and hence should have #define directives:
157 *
158 *   HAVE_CONFIG_H    Define to #include "config.h" (autoconf-generated)
159 *
160 *   HAVE_UNISTD_H    Define to #include <unistd.h>
161 *
162 *   HAVE_SYS_UIO_H   Define to #include <sys/uio.h> (for writev)
163 *   HAVE_WRITEV      Define if the 'writev' function is available
164 *
165 *   HAVE_SYS_PARAM_H Define to #include <sys/param.h> (for pagesize)
166 *
167 *   HAVE_MALLOC_H    Define to #include <malloc.h> (for struct mallinfo)
168 *
169 *   HAVE_FCNTL_H     Define to #include <fcntl.h>
170 *
171 *   HAVE_SYS_MMAN_H  Define to #include <sys/mman.h>
172 *   HAVE_MMAP        Define if the 'mmap' function is available.
173 *
174 *   HAVE_SCHED_H     Define to #include <sched.h>
175 *   HAVE_SCHED_YIELD Define id the 'sched_yield' function is available
176 */
177
178
179/*
180  __STD_C should be nonzero if using ANSI-standard C compiler, a C++
181  compiler, or a C compiler sufficiently close to ANSI to get away
182  with it.
183*/
184
185#ifdef HAVE_CONFIG_H
186#include "config.h"
187#endif
188
189#ifdef USE_VALGRIND
190#include <valgrind/memcheck.h>
191#else
192#define VALGRIND_FREELIKE_BLOCK(a,b)       ((void)0)
193#define VALGRIND_MALLOCLIKE_BLOCK(a,b,c,d) ((void)0)
194#define VALGRIND_CREATE_MEMPOOL(a,b,c)     ((void)0)
195#define VALGRIND_MEMPOOL_ALLOC(a,b,c)      ((void)0)
196#define VALGRIND_MEMPOOL_FREE(a,b)         ((void)0)
197#define VALGRIND_DESTROY_MEMPOOL(a)        ((void)0)
198#define VALGRIND_MAKE_MEM_DEFINED(a,b)     ((void)0)
199#define VALGRIND_MAKE_MEM_UNDEFINED(a,b)   ((void)0)
200#define VALGRIND_MAKE_MEM_NOACCESS(a,b)    ((void)0)
201#endif
202
203#if defined (__GNUC__) && __GNUC__ > 2
204# define LIKELY(expression) (__builtin_expect(!!(expression), 1))
205# define UNLIKELY(expression) (__builtin_expect(!!(expression), 0))
206# define __attribute_malloc__ __attribute__ ((__malloc__))
207#else
208# define LIKELY(x)       (x)
209# define UNLIKELY(x)     (x)
210# define __attribute_malloc__ /* Ignore */
211#endif
212
213/*
214  Define HAVE_MREMAP to make realloc() use mremap() to re-allocate
215  large blocks.  This is currently only possible on Linux with
216  kernel versions newer than 1.3.77.
217*/
218
219#ifndef HAVE_MREMAP
220#ifdef linux
221#define HAVE_MREMAP 1
222#define _GNU_SOURCE 1
223#else
224#define HAVE_MREMAP 0
225#endif
226#endif /* HAVE_MREMAP */
227
228
229
230#ifndef __STD_C
231#if defined(__STDC__) || defined(_cplusplus)
232#define __STD_C     1
233#else
234#define __STD_C     0
235#endif
236#endif /*__STD_C*/
237
238
239/*
240  Void_t* is the pointer type that malloc should say it returns
241*/
242
243#ifndef Void_t
244#if (__STD_C || defined(WIN32))
245#define Void_t      void
246#else
247#define Void_t      char
248#endif
249#endif /*Void_t*/
250
251#if __STD_C
252#include <stddef.h>   /* for size_t */
253#else
254#include <sys/types.h>
255#endif
256
257#if !defined(USE_SYSTEM_MALLOC)
258
259#ifdef __cplusplus
260extern "C" {
261#endif
262
263/* define HAVE_UNISTD_H if your system has a <unistd.h>. */
264
265#ifdef HAVE_UNISTD_H
266#include <unistd.h>
267#endif
268
269#ifdef HAVE_SYS_UIO_H
270#include <sys/uio.h>
271#endif
272
273#include <stdio.h>    /* needed for malloc_stats */
274#include <errno.h>    /* needed for optional MALLOC_FAILURE_ACTION */
275
276#include <string.h>
277#include <stdlib.h>
278
279#include <sys/resource.h>
280
281extern int errno;
282
283  /* 0: lazy,
284   * 1: medium (assertions compiled in),
285   * 2: high (guard pages at end of hash table and ciregions)
286   * 3: paranoid (guards at end of each allocated chunk, check at free)
287   */
288#ifndef PARANOIA
289#define PARANOIA 9
290#endif
291
292  /* Using assert() with multithreading will cause the code
293   * to deadlock since glibc __assert_fail will call malloc().
294   * We need our very own assert().
295   */
296typedef void assert_handler_tp(const char * error, const char *file, int line);
297
298#if  PARANOIA > 0
299
300#ifdef NDEBUG
301#undef NDEBUG
302#endif
303
304static void default_assert_handler(const char *error, 
305                                   const char *file, int line)
306{
307#ifdef HAVE_WRITEV
308  struct iovec iov[5];
309  char * i1 = "assertion failed (";
310  char * i3 = "): ";
311  char * i5 = "\n";
312  int    res = 0;
313  char   ifile[128];
314  char   ierr[128];
315
316  strncpy(ifile, file, sizeof(ifile)); ifile[sizeof(ifile)-1] = '\0';
317  strncpy(ierr, error, sizeof(ierr));  ierr[sizeof(ierr)-1]   = '\0';
318
319  iov[0].iov_base = i1;     iov[0].iov_len = strlen(i1); 
320  iov[1].iov_base = ifile;  iov[1].iov_len = strlen(ifile); 
321  iov[2].iov_base = i3;     iov[2].iov_len = strlen(i3); 
322  iov[3].iov_base = ierr;   iov[3].iov_len = strlen(ierr); 
323  iov[4].iov_base = i5;     iov[4].iov_len = strlen(i5);
324  do {
325    res = writev(STDERR_FILENO, iov, 5);
326  } while (res < 0 && errno == EINTR); 
327#else
328  fputs("assertion failed (", stderr);
329  fputs(file, stderr);
330  fputs("): ", stderr);
331  fputs(error, stderr);
332  fputc('\n', stderr);
333#endif
334  (void) line;
335  abort();
336}
337static assert_handler_tp *assert_handler = default_assert_handler;
338
339
340#define assert(x)                               \
341  do {                                          \
342    if (UNLIKELY(!(x))) {                       \
343      assert_handler(#x, __FILE__, __LINE__);   \
344    }                                           \
345  } while (0)
346
347#else
348
349static assert_handler_tp *assert_handler = NULL;
350#ifndef NDEBUG
351#define NDEBUG
352#endif
353#define assert(x) ((void)0)
354
355#endif
356
357assert_handler_tp *dnmalloc_set_handler(assert_handler_tp *new)
358{
359  assert_handler_tp *old = assert_handler;
360  assert_handler = new;
361  return old;
362}
363
364
365#include <stdarg.h>
366
367  /* define for debugging */
368  /* #define DNMALLOC_DEBUG */ 
369
370  /* Do some extra checks? if not, covered by assrt()s */
371  /* #define DNMALLOC_CHECKS */
372
373  /*
374    The unsigned integer type used for comparing any two chunk sizes.
375    This should be at least as wide as size_t, but should not be signed.
376  */
377
378#ifndef CHUNK_SIZE_T
379#define CHUNK_SIZE_T unsigned long
380#endif
381
382/*
383  The unsigned integer type used to hold addresses when they are are
384  manipulated as integers. Except that it is not defined on all
385  systems, intptr_t would suffice.
386*/
387#ifndef PTR_UINT
388#define PTR_UINT unsigned long
389#endif
390
391
392/*
393  INTERNAL_SIZE_T is the word-size used for internal bookkeeping
394  of chunk sizes.
395
396  The default version is the same as size_t.
397
398  While not strictly necessary, it is best to define this as an
399  unsigned type, even if size_t is a signed type. This may avoid some
400  artificial size limitations on some systems.
401
402  On a 64-bit machine, you may be able to reduce malloc overhead by
403  defining INTERNAL_SIZE_T to be a 32 bit `unsigned int' at the
404  expense of not being able to handle more than 2^32 of malloced
405  space. If this limitation is acceptable, you are encouraged to set
406  this unless you are on a platform requiring 16byte alignments. In
407  this case the alignment requirements turn out to negate any
408  potential advantages of decreasing size_t word size.
409
410  Implementors: Beware of the possible combinations of:
411     - INTERNAL_SIZE_T might be signed or unsigned, might be 32 or 64 bits,
412       and might be the same width as int or as long
413     - size_t might have different width and signedness as INTERNAL_SIZE_T
414     - int and long might be 32 or 64 bits, and might be the same width
415  To deal with this, most comparisons and difference computations
416  among INTERNAL_SIZE_Ts should cast them to CHUNK_SIZE_T, being
417  aware of the fact that casting an unsigned int to a wider long does
418  not sign-extend. (This also makes checking for negative numbers
419  awkward.) Some of these casts result in harmless compiler warnings
420  on some systems.
421*/
422
423#ifndef INTERNAL_SIZE_T
424#define INTERNAL_SIZE_T size_t
425#endif
426
427/* The corresponding word size */
428#define SIZE_SZ                (sizeof(INTERNAL_SIZE_T))
429
430
431
432/*
433  MALLOC_ALIGNMENT is the minimum alignment for malloc'ed chunks.
434  It must be a power of two at least 2 * SIZE_SZ, even on machines
435  for which smaller alignments would suffice. It may be defined as
436  larger than this though. Note however that code and data structures
437  are optimized for the case of 8-byte alignment.
438*/
439
440
441#ifndef MALLOC_ALIGNMENT
442#define MALLOC_ALIGNMENT       (2 * SIZE_SZ)
443#endif
444
445/* The corresponding bit mask value */
446#define MALLOC_ALIGN_MASK      (MALLOC_ALIGNMENT - 1)
447
448
449
450/*
451  REALLOC_ZERO_BYTES_FREES should be set if a call to
452  realloc with zero bytes should be the same as a call to free.
453  Some people think it should. Otherwise, since this malloc
454  returns a unique pointer for malloc(0), so does realloc(p, 0).
455*/
456
457#define REALLOC_ZERO_BYTES_FREES
458
459/*
460  TRIM_FASTBINS controls whether free() of a very small chunk can
461  immediately lead to trimming. Setting to true (1) can reduce memory
462  footprint, but will almost always slow down programs that use a lot
463  of small chunks.
464
465  Define this only if you are willing to give up some speed to more
466  aggressively reduce system-level memory footprint when releasing
467  memory in programs that use many small chunks.  You can get
468  essentially the same effect by setting MXFAST to 0, but this can
469  lead to even greater slowdowns in programs using many small chunks.
470  TRIM_FASTBINS is an in-between compile-time option, that disables
471  only those chunks bordering topmost memory from being placed in
472  fastbins.
473*/
474
475#ifndef TRIM_FASTBINS
476#define TRIM_FASTBINS  0
477#endif
478
479
480/*
481  USE_DL_PREFIX will prefix all public routines with the string 'dl'.
482  This is necessary when you only want to use this malloc in one part
483  of a program, using your regular system malloc elsewhere.
484*/
485
486/* #define USE_DL_PREFIX */
487
488
489/*
490  USE_MALLOC_LOCK causes wrapper functions to surround each
491  callable routine with pthread mutex lock/unlock.
492
493  USE_MALLOC_LOCK forces USE_PUBLIC_MALLOC_WRAPPERS to be defined
494*/
495
496/* #define USE_MALLOC_LOCK */
497
498
499/*
500  If USE_PUBLIC_MALLOC_WRAPPERS is defined, every public routine is
501  actually a wrapper function that first calls MALLOC_PREACTION, then
502  calls the internal routine, and follows it with
503  MALLOC_POSTACTION. This is needed for locking, but you can also use
504  this, without USE_MALLOC_LOCK, for purposes of interception,
505  instrumentation, etc. It is a sad fact that using wrappers often
506  noticeably degrades performance of malloc-intensive programs.
507*/
508
509
510#ifdef USE_MALLOC_LOCK
511#define USE_PUBLIC_MALLOC_WRAPPERS
512#else
513/* #define USE_PUBLIC_MALLOC_WRAPPERS */
514#endif
515
516
517/*
518   Two-phase name translation.
519   All of the actual routines are given mangled names.
520   When wrappers are used, they become the public callable versions.
521   When DL_PREFIX is used, the callable names are prefixed.
522*/
523
524#ifndef USE_PUBLIC_MALLOC_WRAPPERS
525#define cALLOc      public_cALLOc
526#define fREe        public_fREe
527#define mALLOc      public_mALLOc
528#define mEMALIGn    public_mEMALIGn
529#define posix_mEMALIGn    public_posix_mEMALIGn
530#define rEALLOc     public_rEALLOc
531#define vALLOc      public_vALLOc
532#define pVALLOc     public_pVALLOc
533#define mALLINFo    public_mALLINFo
534#define mALLOPt     public_mALLOPt
535#define mTRIm       public_mTRIm
536#define mSTATs      public_mSTATs
537#define mUSABLe     public_mUSABLe
538#endif
539
540#ifdef USE_DL_PREFIX
541#define public_cALLOc    dlcalloc
542#define public_fREe      dlfree
543#define public_mALLOc    dlmalloc
544#define public_mEMALIGn  dlmemalign
545#define public_posix_mEMALIGn  dlposix_memalign
546#define public_rEALLOc   dlrealloc
547#define public_vALLOc    dlvalloc
548#define public_pVALLOc   dlpvalloc
549#define public_mALLINFo  dlmallinfo
550#define public_mALLOPt   dlmallopt
551#define public_mTRIm     dlmalloc_trim
552#define public_mSTATs    dlmalloc_stats
553#define public_mUSABLe   dlmalloc_usable_size
554#else /* USE_DL_PREFIX */
555#define public_cALLOc    calloc
556#define public_fREe      free
557#define public_mALLOc    malloc
558#define public_mEMALIGn  memalign
559#define public_posix_mEMALIGn  posix_memalign
560#define public_rEALLOc   realloc
561#define public_vALLOc    valloc
562#define public_pVALLOc   pvalloc
563#define public_mALLINFo  mallinfo
564#define public_mALLOPt   mallopt
565#define public_mTRIm     malloc_trim
566#define public_mSTATs    malloc_stats
567#define public_mUSABLe   malloc_usable_size
568#endif /* USE_DL_PREFIX */
569
570
571/*
572  HAVE_MEMCPY should be defined if you are not otherwise using
573  ANSI STD C, but still have memcpy and memset in your C library
574  and want to use them in calloc and realloc. Otherwise simple
575  macro versions are defined below.
576
577  USE_MEMCPY should be defined as 1 if you actually want to
578  have memset and memcpy called. People report that the macro
579  versions are faster than libc versions on some systems.
580 
581  Even if USE_MEMCPY is set to 1, loops to copy/clear small chunks
582  (of <= 36 bytes) are manually unrolled in realloc and calloc.
583*/
584
585#ifndef HAVE_MEMCPY
586#define HAVE_MEMCPY
587#endif
588
589#ifndef USE_MEMCPY
590#ifdef HAVE_MEMCPY
591#define USE_MEMCPY 1
592#else
593#define USE_MEMCPY 0
594#endif
595#endif
596
597
598#if (__STD_C || defined(HAVE_MEMCPY))
599
600#ifdef WIN32
601  /* On Win32 memset and memcpy are already declared in windows.h */
602#else
603#if __STD_C
604  /* Defined in string.h */
605#else
606Void_t* memset();
607Void_t* memcpy();
608#endif
609#endif
610#endif
611
612/*
613  MALLOC_FAILURE_ACTION is the action to take before "return 0" when
614  malloc fails to be able to return memory, either because memory is
615  exhausted or because of illegal arguments.
616 
617  By default, sets errno if running on STD_C platform, else does nothing. 
618*/
619
620#ifndef MALLOC_FAILURE_ACTION
621#if __STD_C
622#define MALLOC_FAILURE_ACTION \
623   errno = ENOMEM;
624
625#else
626#define MALLOC_FAILURE_ACTION
627#endif
628#endif
629
630/*
631  MORECORE-related declarations. By default, rely on sbrk
632*/
633
634
635#if !defined(HAVE_UNISTD_H)
636#if !defined(__FreeBSD__) && !defined(__OpenBSD__) && !defined(__NetBSD__)
637#if __STD_C
638extern Void_t*     sbrk(ptrdiff_t);
639#else
640extern Void_t*     sbrk();
641#endif
642#endif
643#endif
644
645/*
646  MORECORE_FAILURE is the value returned upon failure of MORECORE
647  as well as mmap. Since it cannot be an otherwise valid memory address,
648  and must reflect values of standard sys calls, you probably ought not
649  try to redefine it.
650*/
651
652#ifndef MORECORE_FAILURE
653#define MORECORE_FAILURE ((void*)(-1UL))
654#endif
655
656/*
657  MORECORE is the name of the routine to call to obtain more memory
658  from the system.  See below for general guidance on writing
659  alternative MORECORE functions, as well as a version for WIN32 and a
660  sample version for pre-OSX macos.
661*/
662
663#ifndef MORECORE
664#define MORECORE sbrk
665#endif
666
667
668/*
669  If MORECORE_CONTIGUOUS is true, take advantage of fact that
670  consecutive calls to MORECORE with positive arguments always return
671  contiguous increasing addresses.  This is true of unix sbrk.  Even
672  if not defined, when regions happen to be contiguous, malloc will
673  permit allocations spanning regions obtained from different
674  calls. But defining this when applicable enables some stronger
675  consistency checks and space efficiencies.
676*/
677
678#ifndef MORECORE_CONTIGUOUS
679#define MORECORE_CONTIGUOUS 1
680#endif
681
682/*
683  Define MORECORE_CANNOT_TRIM if your version of MORECORE
684  cannot release space back to the system when given negative
685  arguments. This is generally necessary only if you are using
686  a hand-crafted MORECORE function that cannot handle negative arguments.
687*/
688
689/* #define MORECORE_CANNOT_TRIM */
690
691
692/*
693  This malloc requires mmap for heap management data. It is an error
694  if mmap is not available.
695
696  Additionally, mmap will be used to satisfy large requests.
697*/
698
699#ifndef HAVE_MMAP
700#  error HAVE_MMAP not defined, has your operating system mmap?
701#endif
702
703/*
704   Standard unix mmap using /dev/zero clears memory so calloc doesn't
705   need to.
706*/
707
708#ifndef MMAP_CLEARS
709#define MMAP_CLEARS 1
710#endif
711
712
713/*
714   MMAP_AS_MORECORE_SIZE is the minimum mmap size argument to use if
715   sbrk fails, and mmap is used as a backup (which is done only if
716   HAVE_MMAP).  The value must be a multiple of page size.  This
717   backup strategy generally applies only when systems have "holes" in
718   address space, so sbrk cannot perform contiguous expansion, but
719   there is still space available on system.  On systems for which
720   this is known to be useful (i.e. most linux kernels), this occurs
721   only when programs allocate huge amounts of memory.  Between this,
722   and the fact that mmap regions tend to be limited, the size should
723   be large, to avoid too many mmap calls and thus avoid running out
724   of kernel resources.
725*/
726
727#ifndef MMAP_AS_MORECORE_SIZE
728#define MMAP_AS_MORECORE_SIZE (1024 * 1024)
729#endif
730
731
732/*
733  The system page size. To the extent possible, this malloc manages
734  memory from the system in page-size units.  Note that this value is
735  cached during initialization into a field of malloc_state. So even
736  if malloc_getpagesize is a function, it is only called once.
737
738  The following mechanics for getpagesize were adapted from bsd/gnu
739  getpagesize.h. If none of the system-probes here apply, a value of
740  4096 is used, which should be OK: If they don't apply, then using
741  the actual value probably doesn't impact performance.
742*/
743
744
745#ifndef malloc_getpagesize
746
747#  ifdef _SC_PAGESIZE         /* some SVR4 systems omit an underscore */
748#    ifndef _SC_PAGE_SIZE
749#      define _SC_PAGE_SIZE _SC_PAGESIZE
750#    endif
751#  endif
752
753#  ifdef _SC_PAGE_SIZE
754#    define malloc_getpagesize sysconf(_SC_PAGE_SIZE)
755#  else
756#    if defined(BSD) || defined(DGUX) || defined(HAVE_GETPAGESIZE)
757       extern size_t getpagesize();
758#      define malloc_getpagesize getpagesize()
759#    else
760#      ifdef WIN32 /* use supplied emulation of getpagesize */
761#        define malloc_getpagesize getpagesize()
762#      else
763#        if defined(HAVE_SYS_PARAM_H)
764#          include <sys/param.h>
765#        endif
766#        ifdef EXEC_PAGESIZE
767#          define malloc_getpagesize EXEC_PAGESIZE
768#        else
769#          ifdef NBPG
770#            ifndef CLSIZE
771#              define malloc_getpagesize NBPG
772#            else
773#              define malloc_getpagesize (NBPG * CLSIZE)
774#            endif
775#          else
776#            ifdef NBPC
777#              define malloc_getpagesize NBPC
778#            else
779#              ifdef PAGESIZE
780#                define malloc_getpagesize PAGESIZE
781#              else /* just guess */
782#                define malloc_getpagesize (4096)
783#              endif
784#            endif
785#          endif
786#        endif
787#      endif
788#    endif
789#  endif
790#endif
791
792/*
793  This version of malloc supports the standard SVID/XPG mallinfo
794  routine that returns a struct containing usage properties and
795  statistics. It should work on any SVID/XPG compliant system that has
796  a /usr/include/malloc.h defining struct mallinfo. (If you'd like to
797  install such a thing yourself, cut out the preliminary declarations
798  as described above and below and save them in a malloc.h file. But
799  there's no compelling reason to bother to do this.)
800
801  The main declaration needed is the mallinfo struct that is returned
802  (by-copy) by mallinfo().  The SVID/XPG malloinfo struct contains a
803  bunch of fields that are not even meaningful in this version of
804  malloc.  These fields are are instead filled by mallinfo() with
805  other numbers that might be of interest.
806
807  HAVE_MALLOC_H should be set if you have a
808  /usr/include/malloc.h file that includes a declaration of struct
809  mallinfo.  If so, it is included; else an SVID2/XPG2 compliant
810  version is declared below.  These must be precisely the same for
811  mallinfo() to work.  The original SVID version of this struct,
812  defined on most systems with mallinfo, declares all fields as
813  ints. But some others define as unsigned long. If your system
814  defines the fields using a type of different width than listed here,
815  you must #include your system version and #define
816  HAVE_MALLOC_H.
817*/
818
819/* #define HAVE_MALLOC_H */
820
821/* On *BSD, malloc.h is deprecated, and on some *BSD including
822 * it may actually raise an error.
823 */
824#if defined(HAVE_MALLOC_H) && !defined(__OpenBSD__) && !defined(__FreeBSD__) && !defined(__NetBSD__)
825#include <malloc.h>
826#else
827
828/* SVID2/XPG mallinfo structure */
829
830struct mallinfo {
831  int arena;    /* non-mmapped space allocated from system */
832  int ordblks;  /* number of free chunks */
833  int smblks;   /* number of fastbin blocks */
834  int hblks;    /* number of mmapped regions */
835  int hblkhd;   /* space in mmapped regions */
836  int usmblks;  /* maximum total allocated space */
837  int fsmblks;  /* space available in freed fastbin blocks */
838  int uordblks; /* total allocated space */
839  int fordblks; /* total free space */
840  int keepcost; /* top-most, releasable (via malloc_trim) space */
841};
842
843/*
844  SVID/XPG defines four standard parameter numbers for mallopt,
845  normally defined in malloc.h.  Only one of these (M_MXFAST) is used
846  in this malloc. The others (M_NLBLKS, M_GRAIN, M_KEEP) don't apply,
847  so setting them has no effect. But this malloc also supports other
848  options in mallopt described below.
849*/
850#endif
851
852
853/* ---------- description of public routines ------------ */
854
855/*
856  malloc(size_t n)
857  Returns a pointer to a newly allocated chunk of at least n bytes, or null
858  if no space is available. Additionally, on failure, errno is
859  set to ENOMEM on ANSI C systems.
860
861  If n is zero, malloc returns a minumum-sized chunk. (The minimum
862  size is 16 bytes on most 32bit systems, and 24 or 32 bytes on 64bit
863  systems.)  On most systems, size_t is an unsigned type, so calls
864  with negative arguments are interpreted as requests for huge amounts
865  of space, which will often fail. The maximum supported value of n
866  differs across systems, but is in all cases less than the maximum
867  representable value of a size_t.
868*/
869#if __STD_C
870Void_t*  public_mALLOc(size_t) __attribute_malloc__;
871#else
872Void_t*  public_mALLOc();
873#endif
874
875/*
876  free(Void_t* p)
877  Releases the chunk of memory pointed to by p, that had been previously
878  allocated using malloc or a related routine such as realloc.
879  It has no effect if p is null. It can have arbitrary (i.e., bad!)
880  effects if p has already been freed.
881
882  Unless disabled (using mallopt), freeing very large spaces will
883  when possible, automatically trigger operations that give
884  back unused memory to the system, thus reducing program footprint.
885*/
886#if __STD_C
887void     public_fREe(Void_t*);
888#else
889void     public_fREe();
890#endif
891
892/*
893  calloc(size_t n_elements, size_t element_size);
894  Returns a pointer to n_elements * element_size bytes, with all locations
895  set to zero.
896*/
897#if __STD_C
898Void_t*  public_cALLOc(size_t, size_t) __attribute_malloc__;
899#else
900Void_t*  public_cALLOc();
901#endif
902
903/*
904  realloc(Void_t* p, size_t n)
905  Returns a pointer to a chunk of size n that contains the same data
906  as does chunk p up to the minimum of (n, p's size) bytes, or null
907  if no space is available.
908
909  The returned pointer may or may not be the same as p. The algorithm
910  prefers extending p when possible, otherwise it employs the
911  equivalent of a malloc-copy-free sequence.
912
913  If p is null, realloc is equivalent to malloc. 
914
915  If space is not available, realloc returns null, errno is set (if on
916  ANSI) and p is NOT freed.
917
918  if n is for fewer bytes than already held by p, the newly unused
919  space is lopped off and freed if possible.  Unless the #define
920  REALLOC_ZERO_BYTES_FREES is set, realloc with a size argument of
921  zero (re)allocates a minimum-sized chunk.
922
923  Large chunks that were internally obtained via mmap will always
924  be reallocated using malloc-copy-free sequences unless
925  the system supports MREMAP (currently only linux).
926
927  The old unix realloc convention of allowing the last-free'd chunk
928  to be used as an argument to realloc is not supported.
929*/
930#if __STD_C
931Void_t*  public_rEALLOc(Void_t*, size_t) __attribute_malloc__;
932#else
933Void_t*  public_rEALLOc();
934#endif
935
936/*
937  memalign(size_t alignment, size_t n);
938  Returns a pointer to a newly allocated chunk of n bytes, aligned
939  in accord with the alignment argument.
940
941  The alignment argument should be a power of two. If the argument is
942  not a power of two, the nearest greater power is used.
943  8-byte alignment is guaranteed by normal malloc calls, so don't
944  bother calling memalign with an argument of 8 or less.
945
946  Overreliance on memalign is a sure way to fragment space.
947*/
948#if __STD_C
949Void_t*  public_mEMALIGn(size_t, size_t) __attribute_malloc__;
950#else
951Void_t*  public_mEMALIGn();
952#endif
953
954/*
955  posix_memalign(void** memptr, size_t alignment, size_t n);
956  Sets *memptr to the address of a newly allocated chunk of n bytes, aligned
957  in accord with the alignment argument. Returns 0 on success, otherwise
958  an error (EINVAL for incorrect alignment, ENOMEM for out of memory).
959
960  The alignment must be a power of two, and a multiple of sizeof(void *).
961*/
962#if __STD_C
963int public_posix_mEMALIGn(Void_t**, size_t, size_t);
964#else
965int public_posix_mEMALIGn();
966#endif
967
968/*
969  valloc(size_t n);
970  Equivalent to memalign(pagesize, n), where pagesize is the page
971  size of the system. If the pagesize is unknown, 4096 is used.
972*/
973#if __STD_C
974Void_t*  public_vALLOc(size_t) __attribute_malloc__;
975#else
976Void_t*  public_vALLOc();
977#endif
978
979
980
981/*
982  mallopt(int parameter_number, int parameter_value)
983  Sets tunable parameters The format is to provide a
984  (parameter-number, parameter-value) pair.  mallopt then sets the
985  corresponding parameter to the argument value if it can (i.e., so
986  long as the value is meaningful), and returns 1 if successful else
987  0.  SVID/XPG/ANSI defines four standard param numbers for mallopt,
988  normally defined in malloc.h.  Only one of these (M_MXFAST) is used
989  in this malloc. The others (M_NLBLKS, M_GRAIN, M_KEEP) don't apply,
990  so setting them has no effect. But this malloc also supports four
991  other options in mallopt. See below for details.  Briefly, supported
992  parameters are as follows (listed defaults are for "typical"
993  configurations).
994
995  Symbol            param #   default    allowed param values
996  M_MXFAST          1         64         0-80  (0 disables fastbins)
997  M_TRIM_THRESHOLD -1         256*1024   any   (-1U disables trimming)
998  M_TOP_PAD        -2         0          any 
999  M_MMAP_THRESHOLD -3         256*1024   any   (or 0 if no MMAP support)
1000  M_MMAP_MAX       -4         65536      any   (0 disables use of mmap)
1001*/
1002#if __STD_C
1003int      public_mALLOPt(int, int);
1004#else
1005int      public_mALLOPt();
1006#endif
1007
1008
1009/*
1010  mallinfo()
1011  Returns (by copy) a struct containing various summary statistics:
1012
1013  arena:     current total non-mmapped bytes allocated from system
1014  ordblks:   the number of free chunks
1015  smblks:    the number of fastbin blocks (i.e., small chunks that
1016               have been freed but not use resused or consolidated)
1017  hblks:     current number of mmapped regions
1018  hblkhd:    total bytes held in mmapped regions
1019  usmblks:   the maximum total allocated space. This will be greater
1020                than current total if trimming has occurred.
1021  fsmblks:   total bytes held in fastbin blocks
1022  uordblks:  current total allocated space (normal or mmapped)
1023  fordblks:  total free space
1024  keepcost:  the maximum number of bytes that could ideally be released
1025               back to system via malloc_trim. ("ideally" means that
1026               it ignores page restrictions etc.)
1027
1028  Because these fields are ints, but internal bookkeeping may
1029  be kept as longs, the reported values may wrap around zero and
1030  thus be inaccurate.
1031*/
1032#if __STD_C
1033struct mallinfo public_mALLINFo(void);
1034#else
1035struct mallinfo public_mALLINFo();
1036#endif
1037
1038/*
1039  pvalloc(size_t n);
1040  Equivalent to valloc(minimum-page-that-holds(n)), that is,
1041  round up n to nearest pagesize.
1042 */
1043#if __STD_C
1044Void_t*  public_pVALLOc(size_t) __attribute_malloc__;
1045#else
1046Void_t*  public_pVALLOc();
1047#endif
1048
1049/*
1050  malloc_trim(size_t pad);
1051
1052  If possible, gives memory back to the system (via negative
1053  arguments to sbrk) if there is unused memory at the `high' end of
1054  the malloc pool. You can call this after freeing large blocks of
1055  memory to potentially reduce the system-level memory requirements
1056  of a program. However, it cannot guarantee to reduce memory. Under
1057  some allocation patterns, some large free blocks of memory will be
1058  locked between two used chunks, so they cannot be given back to
1059  the system.
1060 
1061  The `pad' argument to malloc_trim represents the amount of free
1062  trailing space to leave untrimmed. If this argument is zero,
1063  only the minimum amount of memory to maintain internal data
1064  structures will be left (one page or less). Non-zero arguments
1065  can be supplied to maintain enough trailing space to service
1066  future expected allocations without having to re-obtain memory
1067  from the system.
1068 
1069  Malloc_trim returns 1 if it actually released any memory, else 0.
1070  On systems that do not support "negative sbrks", it will always
1071  rreturn 0.
1072*/
1073#if __STD_C
1074int      public_mTRIm(size_t);
1075#else
1076int      public_mTRIm();
1077#endif
1078
1079/*
1080  malloc_usable_size(Void_t* p);
1081
1082  Returns the number of bytes you can actually use in
1083  an allocated chunk, which may be more than you requested (although
1084  often not) due to alignment and minimum size constraints.
1085  You can use this many bytes without worrying about
1086  overwriting other allocated objects. This is not a particularly great
1087  programming practice. malloc_usable_size can be more useful in
1088  debugging and assertions, for example:
1089
1090  p = malloc(n);
1091  assert(malloc_usable_size(p) >= 256);
1092
1093*/
1094#if __STD_C
1095size_t   public_mUSABLe(Void_t*);
1096#else
1097size_t   public_mUSABLe();
1098#endif
1099
1100/*
1101  malloc_stats();
1102  Prints on stderr the amount of space obtained from the system (both
1103  via sbrk and mmap), the maximum amount (which may be more than
1104  current if malloc_trim and/or munmap got called), and the current
1105  number of bytes allocated via malloc (or realloc, etc) but not yet
1106  freed. Note that this is the number of bytes allocated, not the
1107  number requested. It will be larger than the number requested
1108  because of alignment and bookkeeping overhead. Because it includes
1109  alignment wastage as being in use, this figure may be greater than
1110  zero even when no user-level chunks are allocated.
1111
1112  The reported current and maximum system memory can be inaccurate if
1113  a program makes other calls to system memory allocation functions
1114  (normally sbrk) outside of malloc.
1115
1116  malloc_stats prints only the most commonly interesting statistics.
1117  More information can be obtained by calling mallinfo.
1118
1119*/
1120#if __STD_C
1121void     public_mSTATs();
1122#else
1123void     public_mSTATs();
1124#endif
1125
1126/* mallopt tuning options */
1127
1128/*
1129  M_MXFAST is the maximum request size used for "fastbins", special bins
1130  that hold returned chunks without consolidating their spaces. This
1131  enables future requests for chunks of the same size to be handled
1132  very quickly, but can increase fragmentation, and thus increase the
1133  overall memory footprint of a program.
1134
1135  This malloc manages fastbins very conservatively yet still
1136  efficiently, so fragmentation is rarely a problem for values less
1137  than or equal to the default.  The maximum supported value of MXFAST
1138  is 80. You wouldn't want it any higher than this anyway.  Fastbins
1139  are designed especially for use with many small structs, objects or
1140  strings -- the default handles structs/objects/arrays with sizes up
1141  to 16 4byte fields, or small strings representing words, tokens,
1142  etc. Using fastbins for larger objects normally worsens
1143  fragmentation without improving speed.
1144
1145  M_MXFAST is set in REQUEST size units. It is internally used in
1146  chunksize units, which adds padding and alignment.  You can reduce
1147  M_MXFAST to 0 to disable all use of fastbins.  This causes the malloc
1148  algorithm to be a closer approximation of fifo-best-fit in all cases,
1149  not just for larger requests, but will generally cause it to be
1150  slower.
1151*/
1152
1153
1154/* M_MXFAST is a standard SVID/XPG tuning option, usually listed in malloc.h */
1155#ifndef M_MXFAST
1156#define M_MXFAST            1   
1157#endif
1158
1159#ifndef DEFAULT_MXFAST
1160#define DEFAULT_MXFAST     64
1161#endif
1162
1163
1164/*
1165  M_TRIM_THRESHOLD is the maximum amount of unused top-most memory
1166  to keep before releasing via malloc_trim in free().
1167
1168  Automatic trimming is mainly useful in long-lived programs.
1169  Because trimming via sbrk can be slow on some systems, and can
1170  sometimes be wasteful (in cases where programs immediately
1171  afterward allocate more large chunks) the value should be high
1172  enough so that your overall system performance would improve by
1173  releasing this much memory.
1174
1175  The trim threshold and the mmap control parameters (see below)
1176  can be traded off with one another. Trimming and mmapping are
1177  two different ways of releasing unused memory back to the
1178  system. Between these two, it is often possible to keep
1179  system-level demands of a long-lived program down to a bare
1180  minimum. For example, in one test suite of sessions measuring
1181  the XF86 X server on Linux, using a trim threshold of 128K and a
1182  mmap threshold of 192K led to near-minimal long term resource
1183  consumption.
1184
1185  If you are using this malloc in a long-lived program, it should
1186  pay to experiment with these values.  As a rough guide, you
1187  might set to a value close to the average size of a process
1188  (program) running on your system.  Releasing this much memory
1189  would allow such a process to run in memory.  Generally, it's
1190  worth it to tune for trimming rather tham memory mapping when a
1191  program undergoes phases where several large chunks are
1192  allocated and released in ways that can reuse each other's
1193  storage, perhaps mixed with phases where there are no such
1194  chunks at all.  And in well-behaved long-lived programs,
1195  controlling release of large blocks via trimming versus mapping
1196  is usually faster.
1197
1198  However, in most programs, these parameters serve mainly as
1199  protection against the system-level effects of carrying around
1200  massive amounts of unneeded memory. Since frequent calls to
1201  sbrk, mmap, and munmap otherwise degrade performance, the default
1202  parameters are set to relatively high values that serve only as
1203  safeguards.
1204
1205  The trim value must be greater than page size to have any useful
1206  effect.  To disable trimming completely, you can set to
1207  (unsigned long)(-1)
1208
1209  Trim settings interact with fastbin (MXFAST) settings: Unless
1210  TRIM_FASTBINS is defined, automatic trimming never takes place upon
1211  freeing a chunk with size less than or equal to MXFAST. Trimming is
1212  instead delayed until subsequent freeing of larger chunks. However,
1213  you can still force an attempted trim by calling malloc_trim.
1214
1215  Also, trimming is not generally possible in cases where
1216  the main arena is obtained via mmap.
1217
1218  Note that the trick some people use of mallocing a huge space and
1219  then freeing it at program startup, in an attempt to reserve system
1220  memory, doesn't have the intended effect under automatic trimming,
1221  since that memory will immediately be returned to the system.
1222*/
1223
1224#define M_TRIM_THRESHOLD       -1
1225
1226#ifndef DEFAULT_TRIM_THRESHOLD
1227#define DEFAULT_TRIM_THRESHOLD (256 * 1024)
1228#endif
1229
1230/*
1231  M_TOP_PAD is the amount of extra `padding' space to allocate or
1232  retain whenever sbrk is called. It is used in two ways internally:
1233
1234  * When sbrk is called to extend the top of the arena to satisfy
1235  a new malloc request, this much padding is added to the sbrk
1236  request.
1237
1238  * When malloc_trim is called automatically from free(),
1239  it is used as the `pad' argument.
1240
1241  In both cases, the actual amount of padding is rounded
1242  so that the end of the arena is always a system page boundary.
1243
1244  The main reason for using padding is to avoid calling sbrk so
1245  often. Having even a small pad greatly reduces the likelihood
1246  that nearly every malloc request during program start-up (or
1247  after trimming) will invoke sbrk, which needlessly wastes
1248  time.
1249
1250  Automatic rounding-up to page-size units is normally sufficient
1251  to avoid measurable overhead, so the default is 0.  However, in
1252  systems where sbrk is relatively slow, it can pay to increase
1253  this value, at the expense of carrying around more memory than
1254  the program needs.
1255*/
1256
1257#define M_TOP_PAD              -2
1258
1259#ifndef DEFAULT_TOP_PAD
1260#define DEFAULT_TOP_PAD        (0)
1261#endif
1262
1263/*
1264  M_MMAP_THRESHOLD is the request size threshold for using mmap()
1265  to service a request. Requests of at least this size that cannot
1266  be allocated using already-existing space will be serviced via mmap.
1267  (If enough normal freed space already exists it is used instead.)
1268
1269  Using mmap segregates relatively large chunks of memory so that
1270  they can be individually obtained and released from the host
1271  system. A request serviced through mmap is never reused by any
1272  other request (at least not directly; the system may just so
1273  happen to remap successive requests to the same locations).
1274
1275  Segregating space in this way has the benefits that:
1276
1277   1. Mmapped space can ALWAYS be individually released back
1278      to the system, which helps keep the system level memory
1279      demands of a long-lived program low.
1280   2. Mapped memory can never become `locked' between
1281      other chunks, as can happen with normally allocated chunks, which
1282      means that even trimming via malloc_trim would not release them.
1283   3. On some systems with "holes" in address spaces, mmap can obtain
1284      memory that sbrk cannot.
1285
1286  However, it has the disadvantages that:
1287
1288   1. The space cannot be reclaimed, consolidated, and then
1289      used to service later requests, as happens with normal chunks.
1290   2. It can lead to more wastage because of mmap page alignment
1291      requirements
1292   3. It causes malloc performance to be more dependent on host
1293      system memory management support routines which may vary in
1294      implementation quality and may impose arbitrary
1295      limitations. Generally, servicing a request via normal
1296      malloc steps is faster than going through a system's mmap.
1297
1298  The advantages of mmap nearly always outweigh disadvantages for
1299  "large" chunks, but the value of "large" varies across systems.  The
1300  default is an empirically derived value that works well in most
1301  systems.
1302*/
1303
1304#define M_MMAP_THRESHOLD      -3
1305
1306#ifndef DEFAULT_MMAP_THRESHOLD
1307#define DEFAULT_MMAP_THRESHOLD (256 * 1024)
1308#endif
1309
1310/*
1311  M_MMAP_MAX is the maximum number of requests to simultaneously
1312  service using mmap. This parameter exists because
1313. Some systems have a limited number of internal tables for
1314  use by mmap, and using more than a few of them may degrade
1315  performance.
1316
1317  The default is set to a value that serves only as a safeguard.
1318  Setting to 0 disables use of mmap for servicing large requests.  If
1319  HAVE_MMAP is not set, the default value is 0, and attempts to set it
1320  to non-zero values in mallopt will fail.
1321*/
1322
1323#define M_MMAP_MAX             -4
1324
1325#ifndef DEFAULT_MMAP_MAX
1326#define DEFAULT_MMAP_MAX       (65536)
1327#endif
1328
1329#ifdef __cplusplus
1330};  /* end of extern "C" */
1331#endif
1332
1333/*
1334  ========================================================================
1335  To make a fully customizable malloc.h header file, cut everything
1336  above this line, put into file malloc.h, edit to suit, and #include it
1337  on the next line, as well as in programs that use this malloc.
1338  ========================================================================
1339*/
1340
1341/* #include "malloc.h" */
1342
1343/* --------------------- public wrappers ---------------------- */
1344
1345#ifdef USE_PUBLIC_MALLOC_WRAPPERS
1346
1347/* DL_STATIC used to make functions (deep down) consistent
1348 * with prototypes (otherwise the prototypes are static
1349 * with USE_PUBLIC_MALLOC_WRAPPERS, but the functions aren't).
1350 * The gcc compiler doesn't care, but the HP-UX compiler does.
1351 */
1352#define DL_STATIC static
1353
1354/* Declare all routines as internal */
1355#if __STD_C
1356static Void_t*  mALLOc(size_t) __attribute_malloc__;
1357static void     fREe(Void_t*);
1358static Void_t*  rEALLOc(Void_t*, size_t) __attribute_malloc__;
1359static Void_t*  mEMALIGn(size_t, size_t) __attribute_malloc__;
1360static int      posix_mEMALIGn(Void_t**, size_t, size_t);
1361static Void_t*  vALLOc(size_t) __attribute_malloc__;
1362static Void_t*  pVALLOc(size_t) __attribute_malloc__;
1363static Void_t*  cALLOc(size_t, size_t) __attribute_malloc__;
1364static int      mTRIm(size_t);
1365static size_t   mUSABLe(Void_t*);
1366static void     mSTATs();
1367static int      mALLOPt(int, int);
1368static struct mallinfo mALLINFo(void);
1369#else
1370static Void_t*  mALLOc();
1371static void     fREe();
1372static Void_t*  rEALLOc();
1373static Void_t*  mEMALIGn();
1374static int      posix_mEMALIGn();
1375static Void_t*  vALLOc();
1376static Void_t*  pVALLOc();
1377static Void_t*  cALLOc();
1378static int      mTRIm();
1379static size_t   mUSABLe();
1380static void     mSTATs();
1381static int      mALLOPt();
1382static struct mallinfo mALLINFo();
1383#endif
1384
1385/*
1386  MALLOC_PREACTION and MALLOC_POSTACTION should be
1387  defined to return 0 on success, and nonzero on failure.
1388  The return value of MALLOC_POSTACTION is currently ignored
1389  in wrapper functions since there is no reasonable default
1390  action to take on failure.
1391*/
1392
1393
1394#ifdef USE_MALLOC_LOCK
1395
1396# ifdef WIN32
1397
1398static int mALLOC_MUTEx;
1399#define MALLOC_PREACTION   slwait(&mALLOC_MUTEx)
1400#define MALLOC_POSTACTION  slrelease(&mALLOC_MUTEx)
1401int dnmalloc_pthread_init(void) { return 0; }
1402
1403# elif defined(__NetBSD__) || defined(__OpenBSD__) || defined(__FreeBSD__)
1404
1405#   if defined(__NetBSD__)
1406#include <reentrant.h>
1407extern int __isthreaded;
1408static mutex_t thread_lock = MUTEX_INITIALIZER;
1409#define _MALLOC_LOCK()   if (__isthreaded) mutex_lock(&thread_lock)
1410#define _MALLOC_UNLOCK() if (__isthreaded) mutex_unlock(&thread_lock)
1411void _malloc_prefork(void) {  _MALLOC_LOCK(); }
1412void _malloc_postfork(void) { _MALLOC_UNLOCK(); }
1413#   endif
1414
1415#   if defined(__OpenBSD__)
1416extern int  __isthreaded;
1417void   _thread_malloc_lock(void);
1418void   _thread_malloc_unlock(void);
1419#define _MALLOC_LOCK()           if (__isthreaded) _thread_malloc_lock()
1420#define _MALLOC_UNLOCK()         if (__isthreaded) _thread_malloc_unlock()
1421#   endif
1422
1423#   if defined(__FreeBSD__)
1424extern int      __isthreaded;
1425struct _spinlock {
1426        volatile long   access_lock;
1427        volatile long   lock_owner;
1428        volatile char   *fname;
1429        volatile int    lineno;
1430};
1431typedef struct _spinlock spinlock_t;
1432#define _SPINLOCK_INITIALIZER   { 0, 0, 0, 0 }
1433void    _spinlock(spinlock_t *);
1434void    _spinunlock(spinlock_t *);
1435/* # include "/usr/src/lib/libc/include/spinlock.h" */
1436static spinlock_t thread_lock   = _SPINLOCK_INITIALIZER;
1437spinlock_t *__malloc_lock       = &thread_lock;
1438#define _MALLOC_LOCK()           if (__isthreaded) _spinlock(&thread_lock)
1439#define _MALLOC_UNLOCK()         if (__isthreaded) _spinunlock(&thread_lock)
1440#   endif
1441
1442/* Common for all three *BSD
1443 */
1444static int malloc_active = 0;
1445static int dnmalloc_mutex_lock()
1446{
1447  _MALLOC_LOCK();
1448  if (!malloc_active)
1449    {
1450      ++malloc_active;
1451      return 0;
1452    }
1453  assert(malloc_active == 0);
1454  _MALLOC_UNLOCK();
1455  errno = EDEADLK;
1456  return 1;
1457}
1458static int dnmalloc_mutex_unlock()
1459{
1460  --malloc_active;
1461  _MALLOC_UNLOCK();
1462  return 0;
1463}
1464#define MALLOC_PREACTION   dnmalloc_mutex_lock()
1465#define MALLOC_POSTACTION  dnmalloc_mutex_unlock()
1466int dnmalloc_pthread_init(void) { return 0; }
1467
1468# else
1469
1470/* Wrapping malloc with pthread_mutex_lock/pthread_mutex_unlock
1471 *
1472 * Works fine on linux (no malloc in pthread_mutex_lock)
1473 * Works with on HP-UX if initialized after entering main()
1474 */ 
1475#include <pthread.h>
1476static int malloc_active      = 0;
1477void dnmalloc_fork_prepare(void);
1478void dnmalloc_fork_parent(void);
1479void dnmalloc_fork_child(void);
1480
1481#if !defined(__linux__)
1482
1483static pthread_mutex_t mALLOC_MUTEx;
1484pthread_once_t dnmalloc_once_control = PTHREAD_ONCE_INIT;
1485static int dnmalloc_use_mutex = 0;
1486static void dnmalloc_pthread_init_int(void)
1487{
1488  pthread_mutexattr_t   mta;
1489  pthread_mutexattr_init(&mta);
1490  pthread_mutexattr_settype(&mta, PTHREAD_MUTEX_RECURSIVE);
1491  pthread_mutex_init(&(mALLOC_MUTEx), &mta);
1492  pthread_mutexattr_destroy(&mta);       
1493  pthread_atfork(dnmalloc_fork_prepare, 
1494                 dnmalloc_fork_parent,
1495                 dnmalloc_fork_child);
1496  dnmalloc_use_mutex = 1;
1497}
1498int dnmalloc_pthread_init(void)
1499{
1500  return pthread_once(&dnmalloc_once_control, dnmalloc_pthread_init_int);
1501}
1502
1503#else
1504
1505static pthread_mutex_t mALLOC_MUTEx = PTHREAD_MUTEX_INITIALIZER;
1506static int dnmalloc_use_mutex = 1;
1507int dnmalloc_pthread_init(void) { 
1508  return pthread_atfork(dnmalloc_fork_prepare, 
1509                        dnmalloc_fork_parent,
1510                        dnmalloc_fork_child); 
1511}
1512#endif /* !defined(__linux__) */
1513
1514void dnmalloc_fork_prepare(void) { 
1515  if (dnmalloc_use_mutex) 
1516    pthread_mutex_lock(&mALLOC_MUTEx);
1517}
1518void dnmalloc_fork_parent(void) { 
1519  if (dnmalloc_use_mutex)
1520    pthread_mutex_unlock(&mALLOC_MUTEx); 
1521}
1522void dnmalloc_fork_child(void) {
1523  int rc = 0;
1524#ifdef __GLIBC__
1525  if (dnmalloc_use_mutex)
1526    {
1527      pthread_mutex_unlock (&mALLOC_MUTEx);
1528      pthread_mutex_destroy(&mALLOC_MUTEx);
1529      rc = pthread_mutex_init(&mALLOC_MUTEx, NULL);
1530    } 
1531#else
1532  if (dnmalloc_use_mutex)
1533    rc = pthread_mutex_unlock(&mALLOC_MUTEx); 
1534#endif
1535  if (rc != 0)
1536    {
1537      fputs("fork_child failed", stderr);
1538      _exit(EXIT_FAILURE);
1539    }
1540}
1541static int dnmalloc_mutex_lock(pthread_mutex_t *mutex)
1542{
1543  if (dnmalloc_use_mutex)
1544    {
1545      int rc = pthread_mutex_lock(mutex);
1546      if (rc == 0)
1547        {
1548          if (!malloc_active)
1549            {
1550              ++malloc_active;
1551              return 0;
1552            }
1553          assert(malloc_active == 0);
1554          (void) pthread_mutex_unlock(mutex);
1555          errno = EDEADLK;
1556          return 1;
1557        }
1558      return rc;
1559    }
1560  return 0;
1561}
1562static int dnmalloc_mutex_unlock(pthread_mutex_t *mutex)
1563{
1564  if (dnmalloc_use_mutex)
1565    {
1566      --malloc_active;
1567      return pthread_mutex_unlock(mutex);
1568    }
1569  return 0;
1570}
1571# define MALLOC_PREACTION   dnmalloc_mutex_lock(&mALLOC_MUTEx)
1572# define MALLOC_POSTACTION  dnmalloc_mutex_unlock(&mALLOC_MUTEx)
1573
1574# endif
1575
1576#else
1577
1578/* Substitute anything you like for these */
1579
1580# define MALLOC_PREACTION   (0)
1581# define MALLOC_POSTACTION  (0)
1582int dnmalloc_pthread_init(void) { return 0; }
1583
1584#endif /* USE_MALLOC_LOCK */
1585
1586Void_t* public_mALLOc(size_t bytes) {
1587  Void_t* m;
1588  if (MALLOC_PREACTION == 0) {
1589    m = mALLOc(bytes);
1590    (void) MALLOC_POSTACTION;
1591    return m;
1592  }
1593  return 0;
1594}
1595
1596void public_fREe(Void_t* m) {
1597  if (MALLOC_PREACTION == 0) {
1598    fREe(m);
1599    (void) MALLOC_POSTACTION;
1600  }
1601}
1602
1603Void_t* public_rEALLOc(Void_t* m, size_t bytes) {
1604  if (MALLOC_PREACTION == 0) {
1605    m = rEALLOc(m, bytes);
1606    (void) MALLOC_POSTACTION;
1607    return m;
1608  }
1609  return 0;
1610}
1611
1612Void_t* public_mEMALIGn(size_t alignment, size_t bytes) {
1613  Void_t* m;
1614  if (MALLOC_PREACTION == 0) {
1615    m = mEMALIGn(alignment, bytes);
1616    (void) MALLOC_POSTACTION;
1617    return m;
1618  }
1619  return 0;
1620}
1621
1622int public_posix_mEMALIGn(Void_t**memptr, size_t alignment, size_t bytes) {
1623  int m, ret;
1624  if ((ret = MALLOC_PREACTION) == 0) {
1625    m = posix_mEMALIGn(memptr, alignment, bytes);
1626    (void) MALLOC_POSTACTION;
1627    return m;
1628  }
1629  return ret;
1630}
1631
1632Void_t* public_vALLOc(size_t bytes) {
1633  Void_t* m;
1634  if (MALLOC_PREACTION == 0) {
1635    m = vALLOc(bytes);
1636    (void) MALLOC_POSTACTION;
1637    return m;
1638  }
1639  return 0;
1640}
1641
1642Void_t* public_pVALLOc(size_t bytes) {
1643  Void_t* m;
1644  if (MALLOC_PREACTION == 0) {
1645    m = pVALLOc(bytes);
1646    (void) MALLOC_POSTACTION;
1647    return m;
1648  }
1649  return 0;
1650}
1651
1652Void_t* public_cALLOc(size_t n, size_t elem_size) {
1653  Void_t* m;
1654  if (MALLOC_PREACTION == 0) {
1655    m = cALLOc(n, elem_size);
1656    (void) MALLOC_POSTACTION;
1657    return m;
1658  }
1659  return 0;
1660}
1661
1662int public_mTRIm(size_t s) {
1663  int result;
1664  if (MALLOC_PREACTION == 0) {
1665    result = mTRIm(s);
1666    (void) MALLOC_POSTACTION;
1667    return result;
1668  }
1669  return 0;
1670}
1671
1672size_t public_mUSABLe(Void_t* m) {
1673  size_t result;
1674  if (MALLOC_PREACTION == 0) {
1675    result = mUSABLe(m);
1676    (void) MALLOC_POSTACTION;
1677    return result;
1678  }
1679  return 0;
1680}
1681
1682void public_mSTATs() {
1683  if (MALLOC_PREACTION == 0) {
1684    mSTATs();
1685    (void) MALLOC_POSTACTION;
1686  }
1687}
1688
1689struct mallinfo public_mALLINFo() {
1690  struct mallinfo m;
1691  if (MALLOC_PREACTION == 0) {
1692    m = mALLINFo();
1693    (void) MALLOC_POSTACTION;
1694    return m;
1695  } else {
1696    struct mallinfo nm = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
1697    return nm;
1698  }
1699}
1700
1701int public_mALLOPt(int p, int v) {
1702  int result;
1703  if (MALLOC_PREACTION == 0) {
1704    result = mALLOPt(p, v);
1705    (void) MALLOC_POSTACTION;
1706    return result;
1707  }
1708  return 0;
1709}
1710
1711#else
1712
1713int dnmalloc_pthread_init(void) { return 0; }
1714#define DL_STATIC
1715
1716#endif /* USE_PUBLIC_MALLOC_WRAPPERS */
1717
1718
1719
1720/* ------------- Optional versions of memcopy ---------------- */
1721
1722
1723#if USE_MEMCPY
1724
1725/*
1726  Note: memcpy is ONLY invoked with non-overlapping regions,
1727  so the (usually slower) memmove is not needed.
1728*/
1729
1730#define MALLOC_COPY(dest, src, nbytes)  memcpy(dest, src, nbytes)
1731#define MALLOC_ZERO(dest, nbytes)       memset(dest, 0,   nbytes)
1732
1733#else /* !USE_MEMCPY */
1734
1735/* Use Duff's device for good zeroing/copying performance. */
1736
1737#define MALLOC_ZERO(charp, nbytes)                                            \
1738do {                                                                          \
1739  INTERNAL_SIZE_T* mzp = (INTERNAL_SIZE_T*)(charp);                           \
1740  CHUNK_SIZE_T  mctmp = (nbytes)/sizeof(INTERNAL_SIZE_T);                     \
1741  long mcn;                                                                   \
1742  if (mctmp < 8) mcn = 0; else { mcn = (mctmp-1)/8; mctmp %= 8; }             \
1743  switch (mctmp) {                                                            \
1744    case 0: for(;;) { *mzp++ = 0;                                             \
1745    case 7:           *mzp++ = 0;                                             \
1746    case 6:           *mzp++ = 0;                                             \
1747    case 5:           *mzp++ = 0;                                             \
1748    case 4:           *mzp++ = 0;                                             \
1749    case 3:           *mzp++ = 0;                                             \
1750    case 2:           *mzp++ = 0;                                             \
1751    case 1:           *mzp++ = 0; if(mcn <= 0) break; mcn--; }                \
1752  }                                                                           \
1753} while(0)
1754
1755#define MALLOC_COPY(dest,src,nbytes)                                          \
1756do {                                                                          \
1757  INTERNAL_SIZE_T* mcsrc = (INTERNAL_SIZE_T*) src;                            \
1758  INTERNAL_SIZE_T* mcdst = (INTERNAL_SIZE_T*) dest;                           \
1759  CHUNK_SIZE_T  mctmp = (nbytes)/sizeof(INTERNAL_SIZE_T);                     \
1760  long mcn;                                                                   \
1761  if (mctmp < 8) mcn = 0; else { mcn = (mctmp-1)/8; mctmp %= 8; }             \
1762  switch (mctmp) {                                                            \
1763    case 0: for(;;) { *mcdst++ = *mcsrc++;                                    \
1764    case 7:           *mcdst++ = *mcsrc++;                                    \
1765    case 6:           *mcdst++ = *mcsrc++;                                    \
1766    case 5:           *mcdst++ = *mcsrc++;                                    \
1767    case 4:           *mcdst++ = *mcsrc++;                                    \
1768    case 3:           *mcdst++ = *mcsrc++;                                    \
1769    case 2:           *mcdst++ = *mcsrc++;                                    \
1770    case 1:           *mcdst++ = *mcsrc++; if(mcn <= 0) break; mcn--; }       \
1771  }                                                                           \
1772} while(0)
1773
1774#endif
1775
1776/* ------------------ MMAP support ------------------  */
1777
1778
1779#if defined(HAVE_FCNTL_H)
1780#include <fcntl.h>
1781#endif
1782
1783#if defined(HAVE_SYS_MMAN_H)
1784#include <sys/mman.h>
1785#endif
1786
1787#if !defined(MAP_ANONYMOUS) && defined(MAP_ANON)
1788#define MAP_ANONYMOUS MAP_ANON
1789#endif
1790
1791/*
1792   Nearly all versions of mmap support MAP_ANONYMOUS,
1793   so the following is unlikely to be needed, but is
1794   supplied just in case.
1795*/
1796
1797#ifndef MAP_ANONYMOUS
1798
1799/* rw 19.05.2008 changed to avoid cached file descriptor, untested
1800 */
1801void * anon_mmap (void *addr, size_t length, int prot, int flags)
1802{
1803  void * retval   = NULL;
1804  int dev_zero_fd = -1; /* File descriptor for /dev/zero. */
1805
1806  dev_zero_fd = open("/dev/zero", O_RDWR);
1807  if (dev_zero_fd >= 0)
1808    {
1809      retval = mmap((addr), (size), (prot), (flags), dev_zero_fd, 0);
1810      /* closing the file descriptor does not unmap the region */
1811      close(dev_zero_fd); 
1812    }
1813  return retval;
1814}
1815 
1816#define MMAP(addr, size, prot, flags) \
1817  (anon_mmap((addr), (size), (prot), (flags)))
1818
1819
1820#else /* have MAP_ANONYMOUS */
1821
1822#if !defined(MAP_32BIT) && defined(MAP_ADDR32)
1823#define MAP_32BIT MAP_ADDR32
1824#endif
1825
1826#if defined(MAP_32BIT)
1827#define MMAP(addr, size, prot, flags) \
1828 (mmap((addr), (size), (prot), (flags)|MAP_ANONYMOUS|MAP_32BIT, -1, 0))
1829#elif defined(__sun)
1830/*
1831 * Hint an address within 32bit address space
1832 */
1833#define MMAP(addr, size, prot, flags) \
1834 (mmap((void*)0xC0000000, (size), (prot), (flags)|MAP_ANONYMOUS, -1, 0))
1835#else
1836/* *BSD */
1837#define MMAP(addr, size, prot, flags) \
1838 (mmap((void*)0x80000000, (size), (prot), (flags)|MAP_ANONYMOUS, -1, 0))
1839#endif
1840
1841#endif /* have MAP_ANONYMOUS */
1842
1843
1844/*
1845  -----------------------  Chunk representations -----------------------
1846*/
1847
1848typedef void * mchunkptr;
1849
1850struct chunkinfo {
1851   INTERNAL_SIZE_T      prev_size;  /* Size of previous in bytes          */
1852   INTERNAL_SIZE_T      size;       /* Size in bytes, including overhead. */
1853   INTERNAL_SIZE_T      req;        /* Original request size, for guard.  */
1854   struct chunkinfo* hash_next;     /* contains a pointer to the next chunk
1855                                       in the linked list if the hash
1856                                       value is the same as the chunk     */
1857   struct chunkinfo* fd;            /* double links -- used only if free. */
1858   struct chunkinfo* bk;
1859   mchunkptr chunk;
1860};
1861
1862typedef struct chunkinfo* chunkinfoptr;
1863
1864struct cireginfo {
1865        unsigned long position;
1866        unsigned long *freebitmap;
1867        struct cireginfo* next;
1868        struct chunkinfo *freelist;
1869        struct chunkinfo *begin; 
1870        unsigned long freecounter; 
1871};
1872
1873/*
1874  ---------- Size and alignment checks and conversions ----------
1875*/
1876
1877/* conversion from malloc headers to user pointers, and back */
1878#define chunk(p) (p->chunk)
1879
1880
1881#define chunk2mem(p)   (chunk(p))
1882#define mem2chunk(mem) (hashtable_lookup(mem))
1883
1884/* The smallest possible chunk      */
1885/* #define MIN_CHUNK_SIZE        16 */
1886#if (SIZEOF_UNSIGNED_LONG == 8) || defined(__arch64__) || defined(__ia64__) || defined(__x86_64__) || defined(__LP64__) || defined(__64BIT__) || defined(_LP64) || defined(_M_IA64) || (defined(_MIPS_SZLONG) && (_MIPS_SZLONG == 64))
1887#  define MIN_CHUNK_SIZE 32
1888#else
1889#  define MIN_CHUNK_SIZE 16
1890#endif
1891
1892/* The smallest size we can malloc is an aligned minimal chunk */
1893
1894#define MINSIZE  \
1895  (CHUNK_SIZE_T)(((MIN_CHUNK_SIZE+MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK))
1896
1897/* Check if m has acceptable alignment */
1898
1899#define aligned_OK(m)  (((PTR_UINT)((m)) & (MALLOC_ALIGN_MASK)) == 0)
1900
1901#define GUARD_SIZE 4
1902
1903/*
1904   Check if a request is so large that it would wrap around zero when
1905   padded and aligned. To simplify some other code, the bound is made
1906   low enough so that adding MINSIZE will also not wrap around zero.
1907
1908   Make it 4*MINSIZE.
1909*/
1910
1911#define REQUEST_OUT_OF_RANGE(req)                                 \
1912  ((CHUNK_SIZE_T)(req) >=                                         \
1913   (CHUNK_SIZE_T)(INTERNAL_SIZE_T)(-4 * MINSIZE))   
1914
1915/* pad request bytes into a usable size -- internal version */
1916
1917#define request2size(req)                                         \
1918  (((req) + GUARD_SIZE + MALLOC_ALIGN_MASK >= MINSIZE)  ?         \
1919   ((req) + GUARD_SIZE + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK :\
1920   MINSIZE)
1921
1922/*  Same, except also perform argument check */
1923
1924#define checked_request2size(req, sz)                             \
1925  if (!REQUEST_OUT_OF_RANGE(req)) {                               \
1926    (sz) = request2size(req);                                     \
1927    assert((sz-req) >= GUARD_SIZE);                               \
1928  } else {                                                        \
1929    MALLOC_FAILURE_ACTION;                                        \
1930    return 0;                                                     \
1931  }
1932
1933#if PARANOIA > 2
1934static char * guard_set_p;
1935static char * guard_set_q;
1936
1937#define guard_set(guard, P, request, sz)                          \
1938  assert((sz-request) >= GUARD_SIZE);                             \
1939  guard_set_p = (char*)(chunk(P));                                \
1940  guard_set_p += request;                                         \
1941  VALGRIND_MAKE_MEM_UNDEFINED(guard_set_p,GUARD_SIZE);            \
1942  guard_set_q = (char*)(guard);                                   \
1943  *guard_set_p = *guard_set_q; ++guard_set_p; ++guard_set_q;      \
1944  *guard_set_p = *guard_set_q; ++guard_set_p; ++guard_set_q;      \
1945  *guard_set_p = *guard_set_q; ++guard_set_p; ++guard_set_q;      \
1946  *guard_set_p = *guard_set_q;                                    \
1947  VALGRIND_MAKE_MEM_NOACCESS((((char*)chunk(P))+request),GUARD_SIZE);   \
1948  (P)->req = request
1949 
1950#define guard_check(guard, P)                                     \
1951  VALGRIND_MAKE_MEM_DEFINED((((char *)chunk(P))+(P)->req), GUARD_SIZE); \
1952  assert(0 == memcmp((((char *)chunk(P))+(P)->req),(void*)(guard),GUARD_SIZE));\
1953  VALGRIND_MAKE_MEM_NOACCESS((((char *)chunk(P))+(P)->req), GUARD_SIZE);
1954
1955#else
1956#define guard_set(guard, P, request, sz) ((void)0)
1957#define guard_check(guard, P) ((void)0)
1958#endif /* PARANOIA > 2 */
1959
1960/* dnmalloc forward declarations */
1961static char * dnmalloc_arc4random(void);
1962static void dnmalloc_init (void);
1963static void malloc_mmap_state(void);
1964static void cireg_extend (void);
1965static chunkinfoptr cireg_getfree (void);
1966static void hashtable_add (chunkinfoptr ci);
1967static void hashtable_insert (chunkinfoptr ci_orig, chunkinfoptr ci_insert);
1968static void hashtable_remove (mchunkptr p);             
1969static void hashtable_skiprm (chunkinfoptr ci_orig, chunkinfoptr ci_todelete);
1970static chunkinfoptr hashtable_lookup (mchunkptr p);
1971static chunkinfoptr next_chunkinfo (chunkinfoptr ci);         
1972static chunkinfoptr prev_chunkinfo (chunkinfoptr ci);
1973
1974
1975
1976/*
1977  --------------- Physical chunk operations ---------------
1978*/
1979
1980
1981/* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */
1982#define PREV_INUSE 0x1
1983
1984/* extract inuse bit of previous chunk */
1985#define prev_inuse(p)       ((p)->size & PREV_INUSE)
1986
1987/* size field is or'ed with IS_MMAPPED if the chunk was obtained with mmap() */
1988#define IS_MMAPPED 0x2
1989
1990/* check for mmap()'ed chunk */
1991#define chunk_is_mmapped(p) ((p)->size & IS_MMAPPED)
1992
1993
1994/* size field is or'ed when the chunk is in use */
1995#define INUSE 0x4
1996
1997/* extract inuse bit of chunk */
1998#define inuse(p)       ((p)->size & INUSE)
1999
2000/*
2001  Bits to mask off when extracting size
2002
2003  Note: IS_MMAPPED is intentionally not masked off from size field in
2004  macros for which mmapped chunks should never be seen. This should
2005  cause helpful core dumps to occur if it is tried by accident by
2006  people extending or adapting this malloc.
2007*/
2008#define SIZE_BITS (PREV_INUSE|IS_MMAPPED|INUSE)
2009
2010/* Bits to mask off when extracting size of chunks for macros which do not use mmap */
2011#define SIZE_NOMMAP (PREV_INUSE|INUSE)
2012
2013/* Get size, ignoring use bits */
2014#define chunksize(p)         ((p)->size & ~(SIZE_BITS))
2015
2016/* Ptr to chunkinfo of next physical malloc_chunk. */
2017#define next_chunk(p) ((mchunkptr)( ((char*)(p)) + ((p)->size & SIZE_NOMMAP) ))
2018
2019/* Treat space at ptr + offset as a chunk */
2020#define chunk_at_offset(p, s)  ((mchunkptr)(((char*)(p)) + (s)))
2021
2022/* set/clear chunk as being inuse without otherwise disturbing */
2023#define set_inuse(p) ((p)->size |= INUSE)
2024
2025#define clear_inuse(p) ((p)->size &= ~(INUSE))
2026
2027#define set_previnuse(p) ((p)->size |= PREV_INUSE)
2028
2029#define clear_previnuse(p) ((p)->size &= ~(PREV_INUSE))
2030
2031static void set_previnuse_next (chunkinfoptr p)
2032{
2033   chunkinfoptr q;
2034   q = next_chunkinfo (p);
2035   if (q)
2036      set_previnuse (q);
2037}
2038
2039#define set_all_inuse(p) \
2040set_inuse(p); \
2041set_previnuse_next(p);
2042
2043
2044/* Set size at head, without disturbing its use bit */
2045#define set_head_size(p, s)  ((p)->size = (((p)->size & SIZE_NOMMAP) | (s)))
2046
2047/* Set size/use field */
2048#define set_head(p, s)       ((p)->size = (s))
2049
2050/*
2051  Bins
2052
2053    An array of bin headers for free chunks. Each bin is doubly
2054    linked.  The bins are approximately proportionally (log) spaced.
2055    There are a lot of these bins (128). This may look excessive, but
2056    works very well in practice.  Most bins hold sizes that are
2057    unusual as malloc request sizes, but are more usual for fragments
2058    and consolidated sets of chunks, which is what these bins hold, so
2059    they can be found quickly.  All procedures maintain the invariant
2060    that no consolidated chunk physically borders another one, so each
2061    chunk in a list is known to be preceeded and followed by either
2062    inuse chunks or the ends of memory.
2063
2064    Chunks in bins are kept in size order, with ties going to the
2065    approximately least recently used chunk. Ordering isn't needed
2066    for the small bins, which all contain the same-sized chunks, but
2067    facilitates best-fit allocation for larger chunks. These lists
2068    are just sequential. Keeping them in order almost never requires
2069    enough traversal to warrant using fancier ordered data
2070    structures. 
2071
2072    Chunks of the same size are linked with the most
2073    recently freed at the front, and allocations are taken from the
2074    back.  This results in LRU (FIFO) allocation order, which tends
2075    to give each chunk an equal opportunity to be consolidated with
2076    adjacent freed chunks, resulting in larger free chunks and less
2077    fragmentation.
2078
2079    To simplify use in double-linked lists, each bin header acts
2080    as a malloc_chunk. This avoids special-casing for headers.
2081    But to conserve space and improve locality, we allocate
2082    only the fd/bk pointers of bins, and then use repositioning tricks
2083    to treat these as the fields of a malloc_chunk*. 
2084*/
2085
2086typedef struct chunkinfo* mbinptr;
2087
2088/* addressing -- note that bin_at(0) does not exist */
2089#define bin_at(m, i) (&(m)->bins[i])
2090
2091/* analog of ++bin */
2092#define next_bin(b)  (b+1)
2093
2094/* Reminders about list directionality within bins */
2095#define first(b)     ((b)->fd)
2096#define last(b)      ((b)->bk)
2097
2098/* Take a chunk off a bin list */
2099#define unlink(P, BK, FD) {                                            \
2100  FD = P->fd;                                                          \
2101  BK = P->bk;                                                          \
2102  FD->bk = BK;                                                         \
2103  BK->fd = FD;                                                         \
2104}
2105
2106/*
2107  Indexing
2108
2109    Bins for sizes < 512 bytes contain chunks of all the same size, spaced
2110    8 bytes apart. Larger bins are approximately logarithmically spaced:
2111
2112    64 bins of size       8
2113    32 bins of size      64
2114    16 bins of size     512
2115     8 bins of size    4096
2116     4 bins of size   32768
2117     2 bins of size  262144
2118     1 bin  of size what's left
2119
2120    The bins top out around 1MB because we expect to service large
2121    requests via mmap.
2122*/
2123
2124#define NBINS              96
2125#define NSMALLBINS         32
2126#define SMALLBIN_WIDTH      8
2127#define MIN_LARGE_SIZE    256
2128
2129#define in_smallbin_range(sz)  \
2130  ((CHUNK_SIZE_T)(sz) < (CHUNK_SIZE_T)MIN_LARGE_SIZE)
2131
2132#define smallbin_index(sz)     (((unsigned)(sz)) >> 3)
2133
2134/*
2135  Compute index for size. We expect this to be inlined when
2136  compiled with optimization, else not, which works out well.
2137*/
2138static int largebin_index(size_t sz) {
2139
2140  unsigned long  xx = sz >> SMALLBIN_WIDTH; 
2141
2142  if (xx < 0x10000) 
2143    {
2144      unsigned int  m;           /* bit position of highest set bit of m */
2145     
2146      /* On intel, use BSRL instruction to find highest bit */
2147#if defined(__GNUC__) && defined(i386) && !defined(USE_UNO)
2148
2149      unsigned int  x = (unsigned int) xx;
2150
2151      __asm__("bsrl %1,%0\n\t"
2152              : "=r" (m) 
2153              : "rm"  (x));
2154
2155#elif defined(__GNUC__) && defined(x86_64) && !defined(USE_UNO)
2156
2157      __asm__("bsrq %1,%0\n\t"
2158              : "=r" (m)
2159              : "rm"  (xx));
2160
2161#else
2162
2163      /* Taken from Bit Twiddling Hacks
2164       * http://graphics.stanford.edu/~seander/bithacks.html
2165       * public domain
2166       */
2167      unsigned int  v  = (unsigned int) xx;
2168      register unsigned int shift;
2169     
2170      m =     (v > 0xFFFF) << 4; v >>= m;
2171      shift = (v > 0xFF  ) << 3; v >>= shift; m |= shift;
2172      shift = (v > 0xF   ) << 2; v >>= shift; m |= shift;
2173      shift = (v > 0x3   ) << 1; v >>= shift; m |= shift;
2174      m |= (v >> 1);
2175     
2176#endif
2177     
2178      /* Use next 2 bits to create finer-granularity bins */
2179      return NSMALLBINS + (m << 2) + ((sz >> (m + 6)) & 3);
2180    }
2181  else
2182    {
2183      return NBINS-1;
2184    }
2185}
2186
2187#define bin_index(sz) \
2188 ((in_smallbin_range(sz)) ? smallbin_index(sz) : largebin_index(sz))
2189
2190/*
2191  FIRST_SORTED_BIN_SIZE is the chunk size corresponding to the
2192  first bin that is maintained in sorted order. This must
2193  be the smallest size corresponding to a given bin.
2194
2195  Normally, this should be MIN_LARGE_SIZE. But you can weaken
2196  best fit guarantees to sometimes speed up malloc by increasing value.
2197  Doing this means that malloc may choose a chunk that is
2198  non-best-fitting by up to the width of the bin.
2199
2200  Some useful cutoff values:
2201      512 - all bins sorted
2202     2560 - leaves bins <=     64 bytes wide unsorted 
2203    12288 - leaves bins <=    512 bytes wide unsorted
2204    65536 - leaves bins <=   4096 bytes wide unsorted
2205   262144 - leaves bins <=  32768 bytes wide unsorted
2206       -1 - no bins sorted (not recommended!)
2207*/
2208
2209/* #define FIRST_SORTED_BIN_SIZE 65536 */
2210
2211#define FIRST_SORTED_BIN_SIZE MIN_LARGE_SIZE
2212
2213
2214/*
2215  Unsorted chunks
2216
2217    All remainders from chunk splits, as well as all returned chunks,
2218    are first placed in the "unsorted" bin. They are then placed
2219    in regular bins after malloc gives them ONE chance to be used before
2220    binning. So, basically, the unsorted_chunks list acts as a queue,
2221    with chunks being placed on it in free (and malloc_consolidate),
2222    and taken off (to be either used or placed in bins) in malloc.
2223*/
2224
2225/* The otherwise unindexable 1-bin is used to hold unsorted chunks. */
2226#define unsorted_chunks(M)          (bin_at(M, 1))
2227
2228/*
2229  Top
2230
2231    The top-most available chunk (i.e., the one bordering the end of
2232    available memory) is treated specially. It is never included in
2233    any bin, is used only if no other chunk is available, and is
2234    released back to the system if it is very large (see
2235    M_TRIM_THRESHOLD).  Because top initially
2236    points to its own bin with initial zero size, thus forcing
2237    extension on the first malloc request, we avoid having any special
2238    code in malloc to check whether it even exists yet. But we still
2239    need to do so when getting memory from system, so we make
2240    initial_top treat the bin as a legal but unusable chunk during the
2241    interval between initialization and the first call to
2242    sYSMALLOc. (This is somewhat delicate, since it relies on
2243    the 2 preceding words to be zero during this interval as well.)
2244*/
2245
2246/* Conveniently, the unsorted bin can be used as dummy top on first call */
2247#define initial_top(M)              (unsorted_chunks(M))
2248
2249/*
2250  Binmap
2251
2252    To help compensate for the large number of bins, a one-level index
2253    structure is used for bin-by-bin searching.  `binmap' is a
2254    bitvector recording whether bins are definitely empty so they can
2255    be skipped over during during traversals.  The bits are NOT always
2256    cleared as soon as bins are empty, but instead only
2257    when they are noticed to be empty during traversal in malloc.
2258*/
2259
2260/* Conservatively use 32 bits per map word, even if on 64bit system */
2261#define BINMAPSHIFT      5
2262#define BITSPERMAP       (1U << BINMAPSHIFT)
2263#define BINMAPSIZE       (NBINS / BITSPERMAP)
2264
2265#define idx2block(i)     ((i) >> BINMAPSHIFT)
2266#define idx2bit(i)       ((1U << ((i) & ((1U << BINMAPSHIFT)-1))))
2267
2268#define mark_bin(m,i)    ((m)->binmap[idx2block(i)] |=  idx2bit(i))
2269#define unmark_bin(m,i)  ((m)->binmap[idx2block(i)] &= ~(idx2bit(i)))
2270#define get_binmap(m,i)  ((m)->binmap[idx2block(i)] &   idx2bit(i))
2271
2272/*
2273  Fastbins
2274
2275    An array of lists holding recently freed small chunks.  Fastbins
2276    are not doubly linked.  It is faster to single-link them, and
2277    since chunks are never removed from the middles of these lists,
2278    double linking is not necessary. Also, unlike regular bins, they
2279    are not even processed in FIFO order (they use faster LIFO) since
2280    ordering doesn't much matter in the transient contexts in which
2281    fastbins are normally used.
2282
2283    Chunks in fastbins keep their inuse bit set, so they cannot
2284    be consolidated with other free chunks. malloc_consolidate
2285    releases all chunks in fastbins and consolidates them with
2286    other free chunks.
2287*/
2288
2289typedef struct chunkinfo* mfastbinptr;
2290
2291/* offset 2 to use otherwise unindexable first 2 bins */
2292#define fastbin_index(sz)        ((((unsigned int)(sz)) >> 3) - 2)
2293
2294/* The maximum fastbin request size we support */
2295#define MAX_FAST_SIZE     80
2296
2297#define NFASTBINS  (fastbin_index(request2size(MAX_FAST_SIZE))+1)
2298
2299/*
2300  FASTBIN_CONSOLIDATION_THRESHOLD is the size of a chunk in free()
2301  that triggers automatic consolidation of possibly-surrounding
2302  fastbin chunks. This is a heuristic, so the exact value should not
2303  matter too much. It is defined at half the default trim threshold as a
2304  compromise heuristic to only attempt consolidation if it is likely
2305  to lead to trimming. However, it is not dynamically tunable, since
2306  consolidation reduces fragmentation surrounding loarge chunks even
2307  if trimming is not used.
2308*/
2309
2310#define FASTBIN_CONSOLIDATION_THRESHOLD  \
2311  ((unsigned long)(DEFAULT_TRIM_THRESHOLD) >> 1)
2312
2313/*
2314  Since the lowest 2 bits in max_fast don't matter in size comparisons,
2315  they are used as flags.
2316*/
2317
2318/*
2319  ANYCHUNKS_BIT held in max_fast indicates that there may be any
2320  freed chunks at all. It is set true when entering a chunk into any
2321  bin.
2322*/
2323
2324#define ANYCHUNKS_BIT        (1U)
2325
2326#define have_anychunks(M)     (((M)->max_fast &  ANYCHUNKS_BIT))
2327#define set_anychunks(M)      ((M)->max_fast |=  ANYCHUNKS_BIT)
2328#define clear_anychunks(M)    ((M)->max_fast &= ~ANYCHUNKS_BIT)
2329
2330/*
2331  FASTCHUNKS_BIT held in max_fast indicates that there are probably
2332  some fastbin chunks. It is set true on entering a chunk into any
2333  fastbin, and cleared only in malloc_consolidate.
2334*/
2335
2336#define FASTCHUNKS_BIT        (2U)
2337
2338#define have_fastchunks(M)   (((M)->max_fast &  FASTCHUNKS_BIT))
2339#define set_fastchunks(M)    ((M)->max_fast |=  (FASTCHUNKS_BIT|ANYCHUNKS_BIT))
2340#define clear_fastchunks(M)  ((M)->max_fast &= ~(FASTCHUNKS_BIT))
2341
2342/*
2343   Set value of max_fast.
2344   Use impossibly small value if 0.
2345*/
2346
2347#define set_max_fast(M, s) \
2348  (M)->max_fast = (((s) == 0)? SMALLBIN_WIDTH: request2size(s)) | \
2349  ((M)->max_fast &  (FASTCHUNKS_BIT|ANYCHUNKS_BIT))
2350
2351#define get_max_fast(M) \
2352  ((M)->max_fast & ~(FASTCHUNKS_BIT | ANYCHUNKS_BIT))
2353
2354
2355/*
2356  morecore_properties is a status word holding dynamically discovered
2357  or controlled properties of the morecore function
2358*/
2359
2360#define MORECORE_CONTIGUOUS_BIT  (1U)
2361
2362#define contiguous(M) \
2363        (((M)->morecore_properties &  MORECORE_CONTIGUOUS_BIT))
2364#define noncontiguous(M) \
2365        (((M)->morecore_properties &  MORECORE_CONTIGUOUS_BIT) == 0)
2366#define set_contiguous(M) \
2367        ((M)->morecore_properties |=  MORECORE_CONTIGUOUS_BIT)
2368#define set_noncontiguous(M) \
2369        ((M)->morecore_properties &= ~MORECORE_CONTIGUOUS_BIT)
2370
2371#define MORECORE_32BIT_BIT  (2U)
2372
2373#define morecore32bit(M) \
2374        (((M)->morecore_properties &  MORECORE_32BIT_BIT))
2375#define nonmorecore32bit(M) \
2376        (((M)->morecore_properties &  MORECORE_32BIT_BIT) == 0)
2377#define set_morecore32bit(M) \
2378        ((M)->morecore_properties |=  MORECORE_32BIT_BIT)
2379#define set_nonmorecore32bit(M) \
2380        ((M)->morecore_properties &= ~MORECORE_32BIT_BIT)
2381
2382
2383
2384/* ----------------- dnmalloc -------------------- */
2385
2386/* size of pages */
2387#define PGSIZE malloc_getpagesize
2388/* pointer size */
2389#define PTRSIZE sizeof(long)
2390
2391
2392
2393/* TODO: mmapped chunks are always multiples of pagesize -> we're wasting
2394   address space: the hashtable has granularity of 16*8, set it to something
2395   closer to pagesize for mmapped chunks (current waste: 32 positions/mmapped
2396   page)
2397*/
2398
2399/* The maximum heap size that dnmalloc can operate with
2400 * represented in hex to avoid annoying gcc warning
2401 *
2402 * Avoid integer overflow, cover complete 32bit address
2403 * space for portability. With deferred allocation, the
2404 * hashtable size is a non-issue.
2405 */
2406#define HEAPMAXSIZE_HALF 0x80000000UL
2407
2408/* How many elements are stored in the linked list */
2409#define LINKEDLSTELS 8
2410
2411/* Minimum size of a chunk */
2412
2413#if (SIZEOF_UNSIGNED_LONG == 8) || defined(__arch64__) || defined(__ia64__) || defined(__x86_64__) || defined(__LP64__) || defined(__64BIT__) || defined(_LP64) || defined(_M_IA64) || (defined(_MIPS_SZLONG) && (_MIPS_SZLONG == 64))
2414#  define MINCHUNKSIZE 32
2415#else
2416#  define MINCHUNKSIZE 16
2417#endif
2418
2419
2420/* The amount of hashtable entries for each page:
2421Pagesize divded by the numer of elements in the linkedlists
2422divided by the minimum chunk size
2423*/
2424#define CHUNKINFOPAGE (PGSIZE / LINKEDLSTELS / MINCHUNKSIZE)
2425
2426/* The amount of hashtable entries needed to manage the memory:
2427Maximum heap size divided by page size multiplied by the amount
2428of chunk info's per page
2429*/
2430#define AMOUNTHASH ((HEAPMAXSIZE_HALF / PGSIZE) * CHUNKINFOPAGE * 2)
2431
2432/* Initial size of the map for the hashtable
2433Amount of entries muliplied by pointer size
2434*/
2435#define  HASHTABLESIZE (AMOUNTHASH * PTRSIZE)
2436
2437/* Amount of free chunks that the system should allocate at the start */
2438#define NUMBER_FREE_CHUNKS 32768
2439
2440/* Initial size of the chunk info region,
2441also used when growing the region */
2442#define CIREGSIZE (NUMBER_FREE_CHUNKS * sizeof(struct chunkinfo))
2443
2444/* Start address of the heap */
2445char *startheap;
2446
2447/* pointer to the hashtable: struct chunkinfo **hashtable -> *hashtable[] */
2448chunkinfoptr *hashtable;
2449
2450/* Current chunkinfo region */
2451struct cireginfo *currciinfo = 0;
2452struct cireginfo *firstciinfo = 0;
2453
2454unsigned long totalcictr = 0;
2455
2456
2457/* Initialize the area for chunkinfos and the hashtable and protect
2458 * it with non-writable pages
2459 */
2460static void
2461dnmalloc_init ()
2462{
2463   void *hashtb;
2464   int mprot;
2465   int flags = MAP_PRIVATE;
2466
2467   /* Allocate the malloc_state struct */
2468   malloc_mmap_state();
2469
2470   /* Use MAP_NORESERVE if available (Solaris, HP-UX; most other
2471    * systems use defered allocation anyway.
2472    */
2473#ifdef MAP_NORESERVE
2474   flags |= MAP_NORESERVE;
2475#endif
2476
2477   /* Always start at 0, hashtable covers whole 32bit address space
2478    */
2479#define STARTHEAP_IS_ZERO
2480   startheap = 0;
2481
2482   /* Map space for the hashtable */
2483#if PARANOIA > 1
2484   hashtb = MMAP(0, HASHTABLESIZE+(2*PGSIZE), PROT_READ|PROT_WRITE, flags);
2485#else
2486   hashtb = MMAP(0, HASHTABLESIZE+PGSIZE, PROT_READ|PROT_WRITE, flags);
2487#endif
2488
2489#ifdef NDEBUG
2490   if (hashtb == MAP_FAILED) {
2491      fprintf (stderr, "Couldn't mmap hashtable: %s\n", strerror (errno));
2492      abort ();
2493   }
2494#else
2495   assert(hashtb != MAP_FAILED);
2496#endif
2497
2498   /* Protect the hashtable with non-writable pages */
2499   mprot = mprotect(hashtb, (size_t) PGSIZE, PROT_NONE);
2500#ifdef NDEBUG
2501   if (mprot == -1) {
2502     fprintf (stderr, "Couldn't mprotect first non-rw page for hashtable: %s\n",
2503              strerror (errno));
2504     abort ();
2505   }
2506#else
2507   assert(mprot != -1);
2508#endif
2509
2510   /* HP-UX: Cannot do arithmetic with pointers to objects of unknown size. */
2511   hashtable = (chunkinfoptr *) (((char*)hashtb) + PGSIZE);
2512
2513   /* Protect the hashtable with non-writable pages */
2514#if PARANOIA > 1
2515   mprot = mprotect((void*)((char*)hashtb+HASHTABLESIZE+PGSIZE), (size_t) PGSIZE, PROT_NONE);
2516#ifdef NDEBUG
2517   if (mprot == -1) {
2518     fprintf (stderr, "Couldn't mprotect last non-rw page for hashtable: %s\n",
2519              strerror (errno));
2520     abort ();
2521   }
2522#else
2523   assert(mprot != -1);
2524#endif
2525#endif
2526}
2527
2528
2529
2530/* Extend the region for chunk infos by mapping more memory before the region */
2531static void
2532cireg_extend ()
2533{
2534   void *newcireg;
2535   int mprot;
2536   struct cireginfo *tempciinfo = 0;
2537   
2538#if PARANOIA > 1
2539   newcireg = MMAP(0, CIREGSIZE+(2*PGSIZE), PROT_READ|PROT_WRITE, MAP_PRIVATE);
2540#else
2541   newcireg = MMAP(0, CIREGSIZE+PGSIZE, PROT_READ|PROT_WRITE, MAP_PRIVATE);
2542#endif
2543
2544#ifdef NDEBUG
2545   if (newcireg == MAP_FAILED)
2546   {
2547           fprintf (stderr, "Couldn't extend chunkinfo region: %s\n",
2548                    strerror (errno));
2549           abort ();
2550   }
2551#else
2552   assert(newcireg != MAP_FAILED);
2553#endif
2554   mprot = mprotect(newcireg, PGSIZE, PROT_NONE);
2555#ifdef NDEBUG
2556   if (mprot == -1) {
2557           fprintf (stderr, "Couldn't mprotect first non-rw page for extended region: %s\n",
2558                    strerror (errno));
2559           abort ();
2560   }
2561#else
2562   assert(mprot != -1);
2563#endif
2564   newcireg = ((char*)newcireg)+PGSIZE;
2565   
2566#if PARANOIA > 1
2567   mprot = mprotect((void*)((char*)newcireg+CIREGSIZE), (size_t) PGSIZE, PROT_NONE);
2568#ifdef NDEBUG
2569   if (mprot == -1) {
2570     fprintf (stderr, "Couldn't mprotect last non-rw page for extended region: %s\n",
2571              strerror (errno));
2572     abort ();
2573   }
2574#else
2575   assert(mprot != -1);
2576#endif
2577#endif
2578
2579   tempciinfo = currciinfo;
2580   currciinfo = (struct cireginfo *) newcireg;
2581   if (tempciinfo)
2582           tempciinfo->next = currciinfo;
2583   currciinfo->position = 1;
2584   currciinfo->freecounter = NUMBER_FREE_CHUNKS;
2585   if (!firstciinfo)
2586           firstciinfo = currciinfo;
2587   totalcictr++;
2588   VALGRIND_CREATE_MEMPOOL(newcireg, 0, 0);
2589}
2590
2591
2592/* Get a free chunkinfo */
2593static chunkinfoptr
2594cireg_getfree ()
2595{
2596   chunkinfoptr freeci;
2597   chunkinfoptr freelst = 0;
2598   struct cireginfo *newciinfo = firstciinfo;
2599   
2600   if (newciinfo) {
2601        freelst = newciinfo->freelist;
2602   
2603        if (!freelst && newciinfo->next) {
2604          do {
2605            newciinfo = newciinfo->next;
2606            freelst = newciinfo->freelist;
2607          } while (!freelst && newciinfo->next);
2608        }
2609   }
2610
2611   /* Check if there are any free chunkinfos on the list of free chunkinfos */
2612   if (freelst)
2613   {
2614     freeci = freelst;
2615     newciinfo->freecounter--;
2616     newciinfo->freelist = freelst->fd;
2617     
2618     VALGRIND_MEMPOOL_ALLOC((char*)currciinfo, (char*)freeci, 
2619                            sizeof(struct chunkinfo));
2620     
2621     freeci->prev_size = 0;
2622     freeci->size      = 0;
2623     freeci->req       = 0;
2624     freeci->hash_next = NULL;
2625     freeci->fd        = NULL;
2626     freeci->bk        = NULL;
2627     freeci->chunk     = NULL;
2628     return (freeci);
2629   }
2630   else
2631   {
2632     /* No free chunkinfos, check if chunkinfo region still has place
2633      * for a chunkinfo. If not, extend the region.
2634      */
2635     if (UNLIKELY(!currciinfo || currciinfo->position == NUMBER_FREE_CHUNKS))
2636       cireg_extend ();
2637     /* Get a chunkinfo from the chunkinfo region */
2638     freeci = (chunkinfoptr) currciinfo + currciinfo->position; 
2639     currciinfo->freecounter--;
2640     currciinfo->position++;
2641
2642     VALGRIND_MEMPOOL_ALLOC((char*)currciinfo, (char*)freeci, 
2643                            sizeof(struct chunkinfo));
2644
2645     return (freeci);
2646   }
2647}
2648
2649static void freeciregion(struct cireginfo *freeme) {
2650  /* free the chunkinfo region */
2651  struct cireginfo *newciinfo = firstciinfo;
2652  struct cireginfo *prevciinfo = firstciinfo;
2653  void *unmapme;
2654
2655  while (newciinfo && newciinfo != freeme) {
2656    prevciinfo = newciinfo;
2657    newciinfo = newciinfo->next;
2658  }
2659  assert(freeme == newciinfo); /* rw */
2660  assert(newciinfo != NULL);   /* rw */
2661  if (newciinfo)
2662    prevciinfo->next = newciinfo->next;
2663  unmapme = (void *) ((char*)freeme - PGSIZE);
2664  VALGRIND_DESTROY_MEMPOOL((char*)freeme);
2665#if PARANOIA > 1
2666  munmap(unmapme, CIREGSIZE+(2*PGSIZE));
2667#else
2668  munmap(unmapme, CIREGSIZE+PGSIZE);
2669#endif
2670}
2671
2672
2673static void freecilst_add(chunkinfoptr p) {
2674
2675  struct cireginfo *newciinfo;
2676
2677  newciinfo = currciinfo;
2678  if (((chunkinfoptr) newciinfo < p) && (<  (chunkinfoptr) (newciinfo+NUMBER_FREE_CHUNKS))) {
2679    p->fd = newciinfo->freelist;
2680    newciinfo->freelist = p;
2681    newciinfo->freecounter++;
2682    VALGRIND_MEMPOOL_FREE((char*)newciinfo, (char*)p);
2683    VALGRIND_MAKE_MEM_DEFINED(p,sizeof(struct chunkinfo));
2684    VALGRIND_MAKE_MEM_NOACCESS(p->size,     sizeof(INTERNAL_SIZE_T));
2685    VALGRIND_MAKE_MEM_NOACCESS(p->req,      sizeof(INTERNAL_SIZE_T));
2686    VALGRIND_MAKE_MEM_NOACCESS(p->bk,       sizeof(struct chunkinfo*));
2687    VALGRIND_MAKE_MEM_NOACCESS(p->chunk,    sizeof(mchunkptr));
2688  } else {
2689    newciinfo = firstciinfo;
2690    if (newciinfo) {
2691      do {
2692        if (((chunkinfoptr) newciinfo < p) && (<  (chunkinfoptr) (newciinfo+NUMBER_FREE_CHUNKS))) {
2693          p->fd = newciinfo->freelist;
2694          newciinfo->freelist = p;
2695          newciinfo->freecounter++;
2696          VALGRIND_MEMPOOL_FREE((char*)newciinfo, (char*)p);
2697          VALGRIND_MAKE_MEM_DEFINED(p,sizeof(struct chunkinfo));
2698          VALGRIND_MAKE_MEM_NOACCESS(p->size,     sizeof(INTERNAL_SIZE_T));
2699          VALGRIND_MAKE_MEM_NOACCESS(p->req,      sizeof(INTERNAL_SIZE_T));
2700          VALGRIND_MAKE_MEM_NOACCESS(p->bk,       sizeof(struct chunkinfo*));
2701          VALGRIND_MAKE_MEM_NOACCESS(p->chunk,    sizeof(mchunkptr));
2702          if (UNLIKELY(newciinfo->freecounter == NUMBER_FREE_CHUNKS))
2703            freeciregion(newciinfo);
2704          break;
2705        }
2706        newciinfo = newciinfo->next;
2707      } while (newciinfo);
2708    }
2709  }
2710}
2711
2712/* Calculate the hash table entry for a chunk */
2713#ifdef STARTHEAP_IS_ZERO
2714#define hash(p)  (((unsigned long) p) >> 7)
2715#else
2716#define hash(p)  (((unsigned long) p - (unsigned long) startheap) >> 7)
2717#endif
2718
2719static void
2720hashtable_add (chunkinfoptr ci)
2721{
2722   chunkinfoptr temp, next;
2723   unsigned long hashval;
2724   mchunkptr cic = chunk (ci);
2725   
2726   hashval = hash (cic);
2727
2728   if (hashval < AMOUNTHASH) {
2729
2730     temp = hashtable[hashval];
2731
2732#ifdef DNMALLOC_DEBUG
2733     fprintf(stderr, "hashtable_add: %p, %lu\n", chunk(ci), hashval);
2734#endif
2735
2736     /* If no pointer to a chunk info list is stored at this location
2737      * in the hashtable or if the chunk's address is smaller than the
2738      * one present, add the chunk to the front of the linked list
2739      */
2740     if (temp == 0 || chunk (temp) > cic)
2741       {
2742         ci->hash_next = temp;
2743         hashtable[hashval] = ci;
2744         if (!temp) /* more likely case */
2745           goto out;
2746         temp->prev_size = chunksize(ci);
2747         return;
2748       }
2749     else
2750       {
2751         /* We must place the chunk in the linked list for this hashentry
2752          * Loop to end of list or to a position where temp's chunk's address
2753          * is larger than the new chunkinfo's chunk's address
2754          */
2755         if (!temp->hash_next || (chunk (temp->hash_next) > cic))
2756           {
2757             ci->hash_next = temp->hash_next;
2758             temp->hash_next = ci;
2759           }
2760         else
2761           {
2762             while ((temp->hash_next != 0) && (chunk (temp->hash_next) < cic))
2763               {
2764                 temp = temp->hash_next;
2765               }
2766             /* Place in linked list if not already there */
2767             if (!temp->hash_next || !(chunk (temp->hash_next) == cic))
2768               {
2769                 ci->hash_next = temp->hash_next;
2770                 temp->hash_next = ci;
2771               }
2772           }
2773       }
2774   }
2775   else {
2776#ifdef DNMALLOC_CHECKS
2777     if (hashval >= AMOUNTHASH) {
2778       fprintf(stderr, "Dnmalloc error: trying to write outside of the bounds of the hashtable, this is definitely a bug, please email dnmalloc@fort-knox.org (hashval: %lu, AMOUNTHASH: %lu, HEAPMAXSIZE_HALF %lu PGSIZE %ld CHUNKINFOPAGE %ld chunk: %p, chunkinfo: %p, startheap: %p).\n", hashval, AMOUNTHASH, HEAPMAXSIZE_HALF, PGSIZE, CHUNKINFOPAGE, chunk(ci), ci, startheap);
2779           abort();
2780     }
2781#else
2782     assert(hashval < AMOUNTHASH);
2783#endif
2784   }
2785
2786 out:
2787   next = next_chunkinfo(ci);
2788   if (!next)
2789     return;
2790   next->prev_size = chunksize(ci);
2791}
2792
2793static void
2794hashtable_insert (chunkinfoptr ci_orig, chunkinfoptr ci_insert)
2795{
2796   chunkinfoptr next;
2797
2798#ifdef DNMALLOC_DEBUG
2799   fprintf(stderr, "hashtable_ins: %p, %lu\n", chunk(ci_insert), 
2800           (unsigned long)hash(chunk(ci_insert));
2801#endif
2802
2803   if (hash(chunk(ci_orig)) != hash(chunk(ci_insert))) {
2804      hashtable_add(ci_insert); 
2805   }
2806   else {
2807
2808      ci_insert->hash_next = ci_orig->hash_next;
2809      ci_orig->hash_next = ci_insert;
2810
2811      /* added for prevsize */
2812      if (!(ci_insert->hash_next))
2813              next = next_chunkinfo(ci_insert);
2814      else
2815              next = ci_insert->hash_next;
2816
2817      if (!next)
2818        {
2819          ci_insert->prev_size = chunksize(ci_orig);
2820        }
2821      else
2822        {
2823          next->prev_size = chunksize(ci_insert);
2824          ci_insert->prev_size = chunksize(ci_orig);
2825        }
2826   }
2827}
2828
2829static void
2830hashtable_remove (mchunkptr p) 
2831{
2832  chunkinfoptr prevtemp, temp;
2833  unsigned long hashval;
2834 
2835  hashval = hash (p);
2836#ifdef DNMALLOC_DEBUG
2837  fprintf(stderr, "hashtable_rem: %p, %lu\n", p, hashval);
2838#endif
2839  assert(hashval < AMOUNTHASH); /* rw */
2840  prevtemp = temp = hashtable[hashval];
2841  if (chunk (temp) == p) {
2842    hashtable[hashval] = temp->hash_next;
2843  } 
2844  else
2845    {
2846      if (temp && chunk (temp) != p) {
2847        do
2848          {
2849            prevtemp = temp;
2850            temp = temp->hash_next;
2851          } while (temp && chunk (temp) != p);
2852      }
2853#ifdef DNMALLOC_CHECKS
2854      if (!temp) {
2855        fprintf (stderr,
2856                 "Dnmalloc error (hash_rm): could not find a chunkinfo for the chunk %p in the hashtable at entry %lu\n This is definitely a bug, please report it to dnmalloc@fort-knox.org.\n",
2857                 p, hashval);
2858        abort();
2859      }
2860#else
2861      assert(temp != NULL);
2862#endif
2863      if (temp) prevtemp->hash_next = temp->hash_next;
2864    }
2865}
2866
2867/* mmapped chunks are multiples of pagesize, no hash_nexts,
2868 * just remove from the hashtable
2869 */
2870#define hashtable_remove_mmapped(p) hashtable[hash(p)] = 0;
2871
2872static void
2873hashtable_skiprm (chunkinfoptr ci_orig, chunkinfoptr ci_todelete)
2874{
2875   unsigned long hashval;
2876   chunkinfoptr next;
2877   
2878#ifdef DNMALLOC_DEBUG
2879   fprintf(stderr, "hashtable_skiprm: %p, %lu\n", chunk(ci_todelete), hash(chunk(ci_todelete)));
2880#endif
2881
2882   if (ci_orig->hash_next != ci_todelete) {
2883     hashval = hash(chunk(ci_todelete));
2884     assert(hashval < AMOUNTHASH); /* rw */
2885#ifdef DNMALLOC_CHECKS
2886     if (hashtable[hashval] != ci_todelete ) {
2887           fprintf(stderr, "Dnmalloc error: trying to delete wrong value (hash: %lu): ci_todelete: %p (%p), hashtable[hashval]: %p (%p)\n This is definitely a bug, please report it to dnmalloc@fort-knox.org.\n", hashval, ci_todelete, chunk(ci_todelete), hashtable[hashval], chunk(hashtable[hashval]));
2888     }
2889#else
2890     assert(hashtable[hashval] == ci_todelete);
2891#endif
2892     hashtable[hashval] = ci_todelete->hash_next;
2893   }
2894
2895   else {
2896     ci_orig->hash_next = ci_todelete->hash_next;
2897     if (!ci_orig->hash_next) {
2898       next = next_chunkinfo(ci_orig);
2899     } else {
2900       next = ci_orig->hash_next;
2901     }
2902     if (next)
2903       next->prev_size = chunksize(ci_orig);
2904
2905   } 
2906}
2907
2908
2909static chunkinfoptr
2910hashtable_lookup (mchunkptr p)
2911{
2912   chunkinfoptr ci;
2913   unsigned long hashval;
2914   
2915   /* if we were called wrongly
2916    * if ((char *) p < startheap) return 0;
2917    */
2918   if ((char *) p >= startheap)
2919     {
2920       hashval = hash (p);
2921       assert(hashval < AMOUNTHASH); /* rw */
2922       ci = hashtable[hashval];
2923       if (ci && chunk (ci) == p)
2924         return ci;
2925
2926       if (ci) {
2927         do {
2928           ci = ci->hash_next;
2929         } while (ci && chunk (ci) != p);
2930       }
2931#ifdef DNMALLOC_CHECKS
2932       /* This should never occur but if it does, we'd like to know */
2933       if (!ci) {
2934         fprintf (stderr,
2935                  "Dnmalloc error: could not find a chunkinfo for the chunk %p in the hashtable at entry %lu\n This is definitely a bug, please report it to dnmalloc@fort-knox.org.\n",
2936                  p, hashval);
2937         abort();
2938       }
2939#else
2940       assert(ci != NULL);
2941#endif
2942       return ci;
2943     }
2944   return 0;
2945}
2946
2947
2948
2949/*
2950   ----------- Internal state representation and initialization -----------
2951*/
2952
2953struct malloc_state {
2954
2955  /* The maximum chunk size to be eligible for fastbin */
2956  INTERNAL_SIZE_T  max_fast;   /* low 2 bits used as flags */
2957
2958  /* Fastbins */
2959  mfastbinptr      fastbins[NFASTBINS];
2960
2961  /* Base of the topmost chunk -- not otherwise kept in a bin */
2962  chunkinfoptr        top;
2963
2964  /* The remainder from the most recent split of a small request */
2965  chunkinfoptr        last_remainder;
2966
2967  /* Normal bins */
2968  struct chunkinfo bins[NBINS];
2969
2970  /* Bitmap of bins. Trailing zero map handles cases of largest binned size */
2971  unsigned int     binmap[BINMAPSIZE+1];
2972
2973  /* Tunable parameters */
2974  CHUNK_SIZE_T     trim_threshold;
2975  INTERNAL_SIZE_T  top_pad;
2976  INTERNAL_SIZE_T  mmap_threshold;
2977
2978  /* Memory map support */
2979  int              n_mmaps;
2980  int              n_mmaps_max;
2981  int              max_n_mmaps;
2982
2983  /* Cache malloc_getpagesize */
2984  unsigned int     pagesize; 
2985
2986  /* Canary */
2987  char             guard_stored[GUARD_SIZE];
2988
2989  /* Track properties of MORECORE */
2990  unsigned int     morecore_properties;
2991
2992  /* Statistics */
2993  INTERNAL_SIZE_T  mmapped_mem;
2994  INTERNAL_SIZE_T  sbrked_mem;
2995  INTERNAL_SIZE_T  max_sbrked_mem;
2996  INTERNAL_SIZE_T  max_mmapped_mem;
2997  INTERNAL_SIZE_T  max_total_mem;
2998};
2999
3000typedef struct malloc_state *mstate;
3001
3002/*
3003   There is exactly one instance of this struct in this malloc.
3004   If you are adapting this malloc in a way that does NOT use a static
3005   malloc_state, you MUST explicitly zero-fill it before using. This
3006   malloc relies on the property that malloc_state is initialized to
3007   all zeroes (as is true of C statics).
3008*/
3009
3010static struct malloc_state * av_ = NULL;  /* never directly referenced */
3011
3012/*
3013   All uses of av_ are via get_malloc_state().
3014   At most one "call" to get_malloc_state is made per invocation of
3015   the public versions of malloc and free, but other routines
3016   that in turn invoke malloc and/or free may call more then once.
3017   Also, it is called in check* routines if DEBUG is set.
3018*/
3019
3020#define get_malloc_state() (av_)
3021
3022/*
3023  Initialize a malloc_state struct.
3024
3025  This is called only from within malloc_consolidate, which needs
3026  be called in the same contexts anyway.  It is never called directly
3027  outside of malloc_consolidate because some optimizing compilers try
3028  to inline it at all call points, which turns out not to be an
3029  optimization at all. (Inlining it in malloc_consolidate is fine though.)
3030*/
3031
3032#if __STD_C
3033static void malloc_mmap_state(void)
3034#else
3035static void malloc_mmap_state()
3036#endif
3037{
3038  int mprot;
3039  unsigned long pagesize = malloc_getpagesize;
3040  size_t size = (sizeof(struct malloc_state) + pagesize - 1) & ~(pagesize - 1);
3041
3042  void * foo = MMAP(0, size+(2*pagesize), PROT_READ|PROT_WRITE, MAP_PRIVATE);
3043
3044
3045#ifdef NDEBUG
3046   if (foo == MAP_FAILED) {
3047      fprintf (stderr, "Couldn't mmap struct malloc_state: %s\n", strerror (errno));
3048      abort ();
3049   }
3050#else
3051   assert(foo != MAP_FAILED);
3052#endif
3053
3054   mprot = mprotect(foo, pagesize, PROT_NONE);
3055#ifdef NDEBUG
3056   if (mprot == -1) {
3057     fprintf (stderr, "Couldn't mprotect first non-rw page for struct malloc_state: %s\n",
3058              strerror (errno));
3059     abort ();
3060   }
3061#else
3062   assert(mprot != -1);
3063#endif
3064
3065   av_ = (struct malloc_state *) ((char*)foo + pagesize);
3066
3067   MALLOC_ZERO(av_, sizeof(struct malloc_state));
3068
3069   mprot = mprotect((void*)((char*)foo + size + pagesize), (size_t) pagesize, PROT_NONE);
3070#ifdef NDEBUG
3071   if (mprot == -1) {
3072     fprintf (stderr, 
3073              "Couldn't mprotect last non-rw page for struct malloc_state: %s\n",
3074              strerror (errno));
3075     abort ();
3076   }
3077#else
3078   assert(mprot != -1);
3079#endif
3080}
3081
3082#if __STD_C
3083static void malloc_init_state(mstate av)
3084#else
3085static void malloc_init_state(av) mstate av;
3086#endif
3087{
3088  int     i;
3089  mbinptr bin;
3090
3091  void *  morecore_test = MORECORE(0);
3092  unsigned long hashval;
3093
3094  /* Test morecore function
3095   */
3096  set_morecore32bit(av);
3097
3098  if (morecore_test == MORECORE_FAILURE)
3099    {
3100      set_nonmorecore32bit(av);
3101    }
3102  else
3103    {
3104      /* On 64bit systems, the heap may be located above the
3105       * 32bit address space. Since mmap() probably still can be
3106       * convinced to map within 32bit, we don't use sbrk().
3107       */
3108      hashval = hash (morecore_test);
3109      if (hashval >= AMOUNTHASH) 
3110        {
3111          set_nonmorecore32bit(av);
3112        }
3113    }
3114
3115 
3116  /* Establish circular links for normal bins */
3117  for (i = 1; i < NBINS; ++i) { 
3118    bin = bin_at(av,i);
3119    bin->fd = bin->bk = bin;
3120  }
3121
3122  av->top_pad        = DEFAULT_TOP_PAD;
3123  av->n_mmaps_max    = DEFAULT_MMAP_MAX;
3124  av->mmap_threshold = DEFAULT_MMAP_THRESHOLD;
3125  av->trim_threshold = DEFAULT_TRIM_THRESHOLD;
3126
3127#if MORECORE_CONTIGUOUS
3128  set_contiguous(av);
3129#else
3130  set_noncontiguous(av);
3131#endif
3132
3133  set_max_fast(av, DEFAULT_MXFAST);
3134
3135  av->top = cireg_getfree ();
3136  av->top->chunk     = (mchunkptr) startheap;
3137  av->top->size      = 0;
3138  set_previnuse(av->top);
3139  clear_inuse(av->top);
3140  hashtable[0]       = av->top;
3141  av->pagesize       = malloc_getpagesize;
3142
3143  memcpy(av->guard_stored, dnmalloc_arc4random(), GUARD_SIZE);
3144
3145}
3146
3147/*
3148   Other internal utilities operating on mstates
3149*/
3150
3151#if __STD_C
3152static Void_t*  sYSMALLOc(INTERNAL_SIZE_T, mstate);
3153static int      sYSTRIm(size_t, mstate);
3154static void     malloc_consolidate(mstate);
3155#else
3156static Void_t*  sYSMALLOc();
3157static int      sYSTRIm();
3158static void     malloc_consolidate();
3159#endif
3160
3161/* dnmalloc functions */
3162/* needs mstate so moved here */
3163
3164static chunkinfoptr
3165next_chunkinfo (chunkinfoptr ci)
3166{
3167   mchunkptr nextp;
3168   unsigned long hashval;
3169   chunkinfoptr cinfonextp;
3170   mstate av = get_malloc_state();
3171   
3172   /* ci is not the last element in the linked list, just
3173      return the next chunkinfo from the list
3174   */
3175   if (!ci->hash_next)
3176     {
3177       /* ci is the last element, find the next chunkinfo by
3178        * looking up the chunkinfo for the chunk that is after p's chunk
3179        */
3180       nextp = (mchunkptr) (((char *) (ci->chunk)) + chunksize (ci));
3181
3182       if (!(nextp == av->top->chunk)) 
3183         {
3184           hashval = hash (nextp);
3185           /* assert(hashval < AMOUNTHASH); *//* major bottleneck */
3186           cinfonextp = hashtable[hashval];
3187           if (cinfonextp && chunk (cinfonextp) == nextp)
3188             return cinfonextp; 
3189           
3190#ifdef DNMALLOC_CHECKS_EXTRA
3191           /* This seems bogus; a chunkinfo may legally have no nextp if
3192            * it's the last one allocated (?)
3193            */
3194           else {
3195             if (cinfonextp)
3196               fprintf (stderr,
3197                        "Dnmalloc error: could not find a next chunkinfo for the chunk %p in the hashtable at entry %lu, cinfonextp: %p, chunk(cinfonextp): %p, nextp: %p\n This is definitely a bug, please report it to dnmalloc@fort-knox.org.\n",
3198                        chunk(ci), hashval, cinfonextp, chunk(cinfonextp), nextp);
3199             else
3200               fprintf (stderr,
3201                        "Dnmalloc error: could not find a next chunkinfo for the chunk %p in the hashtable at entry %lu, cinfonextp: %s, chunk(cinfonextp): %s, nextp: %p\n This is definitely a bug, please report it to dnmalloc@fort-knox.org.\n",
3202                        chunk(ci), hashval, "null", "null", nextp);
3203           }
3204#endif
3205         
3206           return NULL;
3207         }
3208       else
3209         {
3210           return av->top;
3211         }
3212
3213     }
3214   else
3215     {
3216       return (ci->hash_next);
3217     }
3218}
3219
3220static int is_next_chunk(chunkinfoptr oldp, chunkinfoptr newp) {
3221        mchunkptr nextp;
3222        if (oldp->hash_next == newp)
3223                return 1;
3224        nextp = (mchunkptr) (((char *) (oldp->chunk)) + chunksize (oldp));
3225        if (nextp == chunk(newp))
3226                return 1;
3227        return 0;
3228}
3229
3230
3231
3232/* Get the chunkinfo of the physically previous chunk */
3233/* Since we disposed of prev_size, we need this function to find the previous */
3234
3235static chunkinfoptr
3236prev_chunkinfo (chunkinfoptr ci)
3237{
3238   unsigned int i;
3239   chunkinfoptr prev;
3240   mchunkptr prevchunk = 0;
3241   /* chunkinfoptr temp; */
3242   
3243   /* Get the hashtable location of the chunkinfo */
3244   i = hash (chunk (ci));
3245   assert(i < AMOUNTHASH); /* rw */
3246     
3247   /* Get the first element of the linked list of chunkinfo's that contains p */
3248   prev = hashtable[i];
3249   
3250   if (ci == prev) {
3251     prevchunk = (mchunkptr) (((char *) (ci->chunk)) - (ci->prev_size));
3252     i = hash(prevchunk);
3253     assert(i < AMOUNTHASH); /* rw */
3254     /* Loop over the linked list until we reach the last element */
3255     for (prev = hashtable[i]; prev->hash_next != 0; prev = prev->hash_next) ;
3256   } else {
3257     /* p is not the first element in the linked list, we can just
3258        loop over the list and return the previous
3259     */
3260     for (prev = hashtable[i]; prev->hash_next != ci; prev = prev->hash_next);
3261   }
3262
3263   return prev; 
3264}
3265
3266
3267/*
3268  Debugging support
3269  Dnmalloc broke dlmallocs debugging functions, should fix them some
3270  time in the future, for now leave them undefined.
3271*/
3272
3273#define check_chunk(P)
3274#define check_free_chunk(P)
3275#define check_inuse_chunk(P)
3276#define check_remalloced_chunk(P,N)
3277#define check_malloced_chunk(P,N)
3278#define check_malloc_state()
3279
3280
3281/* ----------- Routines dealing with system allocation -------------- */
3282
3283/*
3284  sysmalloc handles malloc cases requiring more memory from the system.
3285  On entry, it is assumed that av->top does not have enough
3286  space to service request for nb bytes, thus requiring that av->top
3287  be extended or replaced.
3288*/
3289
3290#if __STD_C
3291static Void_t* sYSMALLOc(INTERNAL_SIZE_T nb, mstate av)
3292#else
3293static Void_t* sYSMALLOc(nb, av) INTERNAL_SIZE_T nb; mstate av;
3294#endif
3295{
3296  chunkinfoptr    old_top;        /* incoming value of av->top */
3297  INTERNAL_SIZE_T old_size;       /* its size */
3298  char*           old_end;        /* its end address */
3299
3300  long            size;           /* arg to first MORECORE or mmap call */
3301  char*           brk;            /* return value from MORECORE */
3302
3303  long            correction;     /* arg to 2nd MORECORE call */
3304  char*           snd_brk;        /* 2nd return val */
3305
3306  INTERNAL_SIZE_T front_misalign; /* unusable bytes at front of new space */
3307  INTERNAL_SIZE_T end_misalign;   /* partial page left at end of new space */
3308  char*           aligned_brk;    /* aligned offset into brk */
3309
3310  chunkinfoptr    p;              /* the allocated/returned chunk */
3311  chunkinfoptr    remainder;      /* remainder from allocation */
3312  chunkinfoptr    fencepost;      /* fencepost */
3313  CHUNK_SIZE_T    remainder_size; /* its size */
3314
3315  CHUNK_SIZE_T    sum;            /* for updating stats */
3316
3317  size_t          pagemask  = av->pagesize - 1;
3318
3319#ifdef DNMALLOC_DEBUG
3320  fprintf(stderr, "Enter sysmalloc\n");
3321#endif
3322  /*
3323    If there is space available in fastbins, consolidate and retry
3324    malloc from scratch rather than getting memory from system.  This
3325    can occur only if nb is in smallbin range so we didn't consolidate
3326    upon entry to malloc. It is much easier to handle this case here
3327    than in malloc proper.
3328  */
3329
3330
3331  if (have_fastchunks(av)) {
3332    Void_t * retval;
3333    assert(in_smallbin_range(nb));
3334    malloc_consolidate(av);
3335#ifdef DNMALLOC_DEBUG
3336    fprintf(stderr, "Return sysmalloc have_fastchunks\n");
3337#endif
3338    retval = mALLOc(nb - MALLOC_ALIGN_MASK);
3339    VALGRIND_FREELIKE_BLOCK(retval, 0);
3340    return retval;
3341  }
3342
3343
3344  /*
3345    If have mmap, and the request size meets the mmap threshold, and
3346    the system supports mmap, and there are few enough currently
3347    allocated mmapped regions, try to directly map this request
3348    rather than expanding top.
3349  */
3350
3351  if (UNLIKELY((CHUNK_SIZE_T)(nb) >= (CHUNK_SIZE_T)(av->mmap_threshold) &&
3352               (av->n_mmaps < av->n_mmaps_max))) {
3353
3354    char* mm;             /* return value from mmap call*/
3355
3356    /*
3357      Round up size to nearest page.  For mmapped chunks, the overhead
3358      is one SIZE_SZ unit larger than for normal chunks, because there
3359      is no following chunk whose prev_size field could be used.
3360    */
3361    size = (nb + MALLOC_ALIGN_MASK + pagemask) & ~pagemask;
3362
3363    /* Don't try if size wraps around 0 */
3364    if ((CHUNK_SIZE_T)(size) > (CHUNK_SIZE_T)(nb)) {
3365           
3366
3367      mm = (char*)(MMAP(0, size, PROT_READ|PROT_WRITE, MAP_PRIVATE));
3368     
3369      if (mm != (char*)(MORECORE_FAILURE)) {
3370       
3371        VALGRIND_MAKE_MEM_NOACCESS(mm,size);
3372
3373        /*
3374          The offset to the start of the mmapped region is stored
3375          in the prev_size field of the chunk. This allows us to adjust
3376          returned start address to meet alignment requirements here
3377          and in memalign(), and still be able to compute proper
3378          address argument for later munmap in free() and realloc().
3379        */
3380       
3381        front_misalign = (INTERNAL_SIZE_T) mm & MALLOC_ALIGN_MASK;
3382        p = cireg_getfree();
3383       
3384        if (front_misalign > 0) {
3385          correction = MALLOC_ALIGNMENT - front_misalign;
3386          p->chunk = (mchunkptr)(mm + correction);
3387          p->hash_next = (chunkinfoptr) correction;
3388          set_head(p, (size - correction) |INUSE|IS_MMAPPED);
3389        }
3390        else {
3391          p->chunk = (mchunkptr)mm;
3392          p->hash_next = 0;
3393          set_head(p, size|INUSE|IS_MMAPPED);
3394        }
3395        hashtable_add(p);
3396        /* update statistics */
3397       
3398        if (++av->n_mmaps > av->max_n_mmaps) 
3399          av->max_n_mmaps = av->n_mmaps;
3400       
3401        sum = av->mmapped_mem += size;
3402        if (sum > (CHUNK_SIZE_T)(av->max_mmapped_mem)) 
3403          av->max_mmapped_mem = sum;
3404        sum += av->sbrked_mem;
3405        if (sum > (CHUNK_SIZE_T)(av->max_total_mem)) 
3406          av->max_total_mem = sum;
3407
3408        check_chunk(p);
3409       
3410#ifdef DNMALLOC_DEBUG
3411        fprintf(stderr, "Return mmapped (%lu, total %lu)\n", 
3412                size, (unsigned long)/* size_t */av->max_total_mem );
3413#endif
3414        return chunk(p);
3415      }
3416    }
3417  }
3418
3419  /* Record incoming configuration of top */
3420
3421  old_top  = av->top;
3422  old_size = chunksize(old_top);
3423  old_end  = (char*)(chunk_at_offset(chunk(old_top), old_size));
3424
3425  brk = snd_brk = (char*)(MORECORE_FAILURE); 
3426
3427  /*
3428     If not the first time through, we require old_size to be
3429     at least MINSIZE and to have prev_inuse set.
3430  */
3431
3432  /* assert((old_top == initial_top(av) && old_size == 0) ||
3433         ((CHUNK_SIZE_T) (old_size) >= MINSIZE &&
3434         prev_inuse(old_top))); */
3435
3436  /* Precondition: not enough current space to satisfy nb request */
3437  assert((CHUNK_SIZE_T)(old_size) < (CHUNK_SIZE_T)(nb + MINSIZE));
3438
3439  /* Precondition: all fastbins are consolidated */
3440  assert(!have_fastchunks(av));
3441
3442  /* Request enough space for nb + pad + overhead */
3443  size = nb + av->top_pad + MINSIZE;
3444
3445  /*
3446    If contiguous, we can subtract out existing space that we hope to
3447    combine with new space. We add it back later only if
3448    we don't actually get contiguous space.
3449  */
3450  if (contiguous(av))
3451    size -= old_size;
3452
3453  /*
3454    Round to a multiple of page size.
3455    If MORECORE is not contiguous, this ensures that we only call it
3456    with whole-page arguments.  And if MORECORE is contiguous and
3457    this is not first time through, this preserves page-alignment of
3458    previous calls. Otherwise, we correct to page-align below.
3459  */
3460
3461  size = (size + pagemask) & ~pagemask;
3462
3463  /*
3464    Don't try to call MORECORE if argument is so big as to appear
3465    negative. Note that since mmap takes size_t arg, it may succeed
3466    below even if we cannot call MORECORE.
3467  */
3468  if (size > 0 && morecore32bit(av)) 
3469    brk = (char*)(MORECORE(size));
3470
3471  /*
3472    If have mmap, try using it as a backup when MORECORE fails or
3473    cannot be used. This is worth doing on systems that have "holes" in
3474    address space, so sbrk cannot extend to give contiguous space, but
3475    space is available elsewhere.  Note that we ignore mmap max count
3476    and threshold limits, since the space will not be used as a
3477    segregated mmap region.
3478  */
3479  if (brk != (char*)(MORECORE_FAILURE)) {
3480    av->sbrked_mem += size;
3481    VALGRIND_MAKE_MEM_NOACCESS(brk,size);
3482  }
3483
3484  else {
3485
3486#ifdef DNMALLOC_DEBUG
3487    fprintf(stderr, "Morecore failure in sysmalloc\n");
3488#endif
3489
3490    /* Cannot merge with old top, so add its size back in */
3491    if (contiguous(av))
3492      size = (size + old_size + pagemask) & ~pagemask;
3493
3494    /* If we are relying on mmap as backup, then use larger units */
3495    if ((CHUNK_SIZE_T)(size) < (CHUNK_SIZE_T)(MMAP_AS_MORECORE_SIZE))
3496      size = MMAP_AS_MORECORE_SIZE;
3497
3498    /* Don't try if size wraps around 0 */
3499    if ((CHUNK_SIZE_T)(size) > (CHUNK_SIZE_T)(nb)) {
3500
3501#ifdef DNMALLOC_DEBUG
3502      fprintf(stderr, "Try mmap in sysmalloc\n");
3503#endif
3504      brk = (char*)(MMAP(0, size, PROT_READ|PROT_WRITE, MAP_PRIVATE));
3505     
3506      if (brk != (char*)(MORECORE_FAILURE)) {
3507       
3508        VALGRIND_MAKE_MEM_NOACCESS(brk,size);
3509
3510        av->mmapped_mem += size;
3511#ifdef DNMALLOC_DEBUG
3512        fprintf(stderr, "Mmapped successfully in sysmalloc %p\n", brk);
3513#endif
3514
3515        /* We do not need, and cannot use, another sbrk call to find end */
3516        snd_brk = brk + size;
3517       
3518        /*
3519           Record that we no longer have a contiguous sbrk region.
3520           After the first time mmap is used as backup, we do not
3521           ever rely on contiguous space since this could incorrectly
3522           bridge regions.
3523        */
3524        set_noncontiguous(av);
3525      }
3526    }
3527  }
3528
3529  if (brk != (char*)(MORECORE_FAILURE)) {
3530#ifdef DNMALLOC_DEBUG
3531    fprintf(stderr, "Success path %lu allocated, sbrked %lu\n", 
3532            size, (unsigned long)av->sbrked_mem);
3533#endif
3534    /* av->sbrked_mem += size; moved up */
3535
3536    /*
3537      If MORECORE extends previous space, we can likewise extend top size.
3538    */
3539   
3540    if (brk == old_end && snd_brk == (char*)(MORECORE_FAILURE)) {
3541      set_head(old_top, (size + old_size) | PREV_INUSE);
3542#ifdef DNMALLOC_DEBUG
3543      fprintf(stderr, "Previous space extended\n");
3544#endif
3545    }
3546
3547    /*
3548      Otherwise, make adjustments:
3549     
3550      * If the first time through or noncontiguous, we need to call sbrk
3551        just to find out where the end of memory lies.
3552
3553      * We need to ensure that all returned chunks from malloc will meet
3554        MALLOC_ALIGNMENT
3555
3556      * If there was an intervening foreign sbrk, we need to adjust sbrk
3557        request size to account for fact that we will not be able to
3558        combine new space with existing space in old_top.
3559
3560      * Almost all systems internally allocate whole pages at a time, in
3561        which case we might as well use the whole last page of request.
3562        So we allocate enough more memory to hit a page boundary now,
3563        which in turn causes future contiguous calls to page-align.
3564    */
3565   
3566    else {
3567      /* front_misalign = 0; *//*superfluous */
3568      /* end_misalign = 0; *//*superfluous */
3569      correction = 0;
3570      aligned_brk = brk;
3571
3572      /*
3573        If MORECORE returns an address lower than we have seen before,
3574        we know it isn't really contiguous.  This and some subsequent
3575        checks help cope with non-conforming MORECORE functions and
3576        the presence of "foreign" calls to MORECORE from outside of
3577        malloc or by other threads.  We cannot guarantee to detect
3578        these in all cases, but cope with the ones we do detect.
3579      */
3580      if (contiguous(av) && old_size != 0 && brk < old_end) {
3581        set_noncontiguous(av);
3582      }
3583     
3584      /* handle contiguous cases */
3585      if (contiguous(av)) { 
3586
3587#ifdef DNMALLOC_DEBUG
3588        fprintf(stderr, "Handle contiguous cases\n");
3589#endif
3590        /*
3591           We can tolerate forward non-contiguities here (usually due
3592           to foreign calls) but treat them as part of our space for
3593           stats reporting.
3594        */
3595        if (old_size != 0) 
3596          av->sbrked_mem += brk - old_end;
3597       
3598        /* Guarantee alignment of first new chunk made from this space */
3599
3600        front_misalign = (INTERNAL_SIZE_T) brk & MALLOC_ALIGN_MASK;
3601        if (front_misalign > 0) {
3602
3603          /*
3604            Skip over some bytes to arrive at an aligned position.
3605            We don't need to specially mark these wasted front bytes.
3606            They will never be accessed anyway because
3607            prev_inuse of av->top (and any chunk created from its start)
3608            is always true after initialization.
3609          */
3610
3611          correction = MALLOC_ALIGNMENT - front_misalign;
3612          aligned_brk += correction;
3613        }
3614       
3615        /*
3616          If this isn't adjacent to existing space, then we will not
3617          be able to merge with old_top space, so must add to 2nd request.
3618        */
3619       
3620        correction += old_size;
3621       
3622        /* Extend the end address to hit a page boundary */
3623        end_misalign = (INTERNAL_SIZE_T)(brk + size + correction);
3624        correction += ((end_misalign + pagemask) & ~pagemask) - end_misalign;
3625       
3626        assert(correction >= 0);
3627        snd_brk = (char*)(MORECORE(correction));
3628       
3629        if (snd_brk == (char*)(MORECORE_FAILURE)) {
3630          /*
3631            If can't allocate correction, try to at least find out current
3632            brk.  It might be enough to proceed without failing.
3633          */
3634          correction = 0;
3635          snd_brk = (char*)(MORECORE(0));
3636        }
3637        else if (snd_brk < brk) {
3638          /*
3639            If the second call gives noncontiguous space even though
3640            it says it won't, the only course of action is to ignore
3641            results of second call, and conservatively estimate where
3642            the first call left us. Also set noncontiguous, so this
3643            won't happen again, leaving at most one hole.
3644           
3645            Note that this check is intrinsically incomplete.  Because
3646            MORECORE is allowed to give more space than we ask for,
3647            there is no reliable way to detect a noncontiguity
3648            producing a forward gap for the second call.
3649          */
3650          snd_brk = brk + size;
3651          correction = 0;
3652          set_noncontiguous(av);
3653        }
3654        else {
3655          VALGRIND_MAKE_MEM_NOACCESS(snd_brk,correction);
3656        }
3657
3658      }
3659     
3660      /* handle non-contiguous cases */
3661      else { 
3662
3663#ifdef DNMALLOC_DEBUG
3664        fprintf(stderr, "Handle non-contiguous cases\n");
3665#endif
3666
3667        /* MORECORE/mmap must correctly align */
3668        assert(aligned_OK(brk));
3669       
3670        /* Find out current end of memory */
3671        if (snd_brk == (char*)(MORECORE_FAILURE)) {
3672          snd_brk = (char*)(MORECORE(0));
3673          av->sbrked_mem += snd_brk - brk - size;
3674        }
3675#ifdef DNMALLOC_DEBUG
3676        fprintf(stderr, "Sbrked now %lu\n", (unsigned long)av->sbrked_mem);
3677#endif
3678      }
3679     
3680      /* Adjust top based on results of second sbrk.
3681       *
3682       * If mmap() has been used as backup for failed morecore(),
3683       * we end up in this branch as well.
3684       */
3685      if (snd_brk != (char*)(MORECORE_FAILURE)) {
3686#ifdef DNMALLOC_DEBUG
3687        fprintf(stderr, "Adjust top, correction %lu\n", correction);
3688#endif
3689        /* hashtable_remove(chunk(av->top)); *//* rw 19.05.2008 removed */
3690        av->top =  cireg_getfree();
3691        av->top->chunk = (mchunkptr)aligned_brk;
3692        set_head(av->top, (snd_brk - aligned_brk + correction) | PREV_INUSE);
3693#ifdef DNMALLOC_DEBUG
3694        fprintf(stderr, "Adjust top, top %p size %lu\n", 
3695                av->top, (unsigned long)chunksize(av->top));
3696#endif
3697        hashtable_add(av->top);
3698        av->sbrked_mem += correction;
3699     
3700        /*
3701          If not the first time through, we either have a
3702          gap due to foreign sbrk or a non-contiguous region.  Insert a
3703          double fencepost at old_top to prevent consolidation with space
3704          we don't own. These fenceposts are artificial chunks that are
3705          marked as inuse. Original dlmalloc had two of these but too
3706          small to use. To ensure that the linked lists contain a maximum
3707          of 8 elements we only use 1. Inuse is determined by the
3708          current rather than the next chunk anyway.
3709        */
3710   
3711        if (old_size != 0) {
3712#ifdef DNMALLOC_DEBUG
3713          fprintf(stderr, "Shrink old_top to insert fenceposts\n");
3714#endif
3715          /*
3716             Shrink old_top to insert fenceposts, keeping size a
3717             multiple of MALLOC_ALIGNMENT. We know there is at least
3718             enough space in old_top to do this.
3719          */
3720#ifdef DNMALLOC_DEBUG
3721          fprintf(stderr, "Adjust top, old_top %p old_size before %lu\n", 
3722                  old_top, (unsigned long)old_size);
3723#endif
3724          old_size = (old_size - 4*SIZE_SZ) & ~MALLOC_ALIGN_MASK;
3725          set_head(old_top, old_size | PREV_INUSE);
3726#ifdef DNMALLOC_DEBUG
3727          fprintf(stderr, "Adjust top, old_size after %lu\n", 
3728                  (unsigned long)old_size);
3729#endif
3730         
3731          /*
3732            Note that the following assignments completely overwrite
3733            old_top when old_size was previously MINSIZE.  This is
3734            intentional. We need the fencepost, even if old_top otherwise gets
3735            lost.
3736          */
3737          /* dnmalloc, we need the fencepost to be 16 bytes, however since
3738             it's marked inuse it will never be coalesced
3739          */
3740          fencepost = cireg_getfree();
3741          fencepost->chunk = (mchunkptr) chunk_at_offset(chunk(old_top), 
3742                                                         old_size);
3743          fencepost->size = 16|INUSE|PREV_INUSE;
3744          hashtable_add(fencepost);
3745          /*
3746             If possible, release the rest, suppressing trimming.
3747          */
3748          if (old_size >= MINSIZE) {
3749            INTERNAL_SIZE_T tt = av->trim_threshold;
3750#ifdef DNMALLOC_DEBUG
3751            fprintf(stderr, "Release\n");
3752#endif
3753            av->trim_threshold = (INTERNAL_SIZE_T)(-1);
3754            set_head(old_top, old_size | PREV_INUSE | INUSE);
3755            guard_set(av->guard_stored, old_top, 0, old_size);
3756            VALGRIND_MALLOCLIKE_BLOCK(chunk(old_top), old_size, 0, 0);
3757            fREe(chunk(old_top));
3758            av->trim_threshold = tt;
3759#ifdef DNMALLOC_DEBUG
3760            fprintf(stderr, "Release done\n");
3761#endif
3762          }
3763
3764#ifdef DNMALLOC_DEBUG
3765          fprintf(stderr, "Adjust top, size %lu\n", 
3766                  (unsigned long)chunksize(av->top));
3767#endif
3768
3769        } /* fenceposts */
3770      } /* adjust top */
3771    } /* not extended previous region */
3772   
3773    /* Update statistics */
3774    sum = av->sbrked_mem;
3775    if (sum > (CHUNK_SIZE_T)(av->max_sbrked_mem))
3776      av->max_sbrked_mem = sum;
3777   
3778    sum += av->mmapped_mem;
3779    if (sum > (CHUNK_SIZE_T)(av->max_total_mem))
3780      av->max_total_mem = sum;
3781
3782    check_malloc_state();
3783   
3784    /* finally, do the allocation */
3785
3786    p = av->top;
3787    size = chunksize(p);
3788   
3789#ifdef DNMALLOC_DEBUG
3790    fprintf(stderr, "Size: %lu  nb+MINSIZE: %lu\n", 
3791            (CHUNK_SIZE_T)(size), (CHUNK_SIZE_T)(nb + MINSIZE));
3792#endif
3793
3794    /* check that one of the above allocation paths succeeded */
3795    if ((CHUNK_SIZE_T)(size) >= (CHUNK_SIZE_T)(nb + MINSIZE)) {
3796      remainder_size = size - nb;
3797      remainder = cireg_getfree();
3798      remainder->chunk = chunk_at_offset(chunk(p), nb);
3799      av->top = remainder;
3800      set_head(p, nb | PREV_INUSE | INUSE);
3801      set_head(remainder, remainder_size | PREV_INUSE);
3802      hashtable_insert (p, av->top);
3803      check_malloced_chunk(p, nb);
3804#ifdef DNMALLOC_DEBUG
3805      fprintf(stderr, "Return any (total %lu)\n", 
3806              (unsigned long)/* size_t */av->max_total_mem );
3807#endif
3808      return chunk(p);
3809    }
3810
3811  }
3812
3813#ifdef DNMALLOC_DEBUG
3814  fprintf(stderr, "Return failed (total %lu)\n", 
3815          (unsigned long)/* size_t */av->max_total_mem );
3816#endif
3817
3818  /* catch all failure paths */
3819  MALLOC_FAILURE_ACTION;
3820  return 0;
3821}
3822
3823
3824
3825
3826/*
3827  sYSTRIm is an inverse of sorts to sYSMALLOc.  It gives memory back
3828  to the system (via negative arguments to sbrk) if there is unused
3829  memory at the `high' end of the malloc pool. It is called
3830  automatically by free() when top space exceeds the trim
3831  threshold. It is also called by the public malloc_trim routine.  It
3832  returns 1 if it actually released any memory, else 0.
3833*/
3834
3835#if __STD_C
3836static int sYSTRIm(size_t pad, mstate av)
3837#else
3838static int sYSTRIm(pad, av) size_t pad; mstate av;
3839#endif
3840{
3841  long  top_size;        /* Amount of top-most memory */
3842  long  extra;           /* Amount to release */
3843  long  released;        /* Amount actually released */
3844  char* current_brk;     /* address returned by pre-check sbrk call */
3845  char* new_brk;         /* address returned by post-check sbrk call */
3846  size_t pagesz;
3847
3848  pagesz = av->pagesize;
3849  top_size = chunksize(av->top);
3850 
3851  /* Release in pagesize units, keeping at least one page */
3852  extra = ((top_size - pad - MINSIZE + (pagesz-1)) / pagesz - 1) * pagesz;
3853 
3854  if (extra > 0) {
3855   
3856    /*
3857      Only proceed if end of memory is where we last set it.
3858      This avoids problems if there were foreign sbrk calls.
3859    */
3860    current_brk = (char*)(MORECORE(0));
3861    if (current_brk == (char*)(av->top) + top_size) {
3862     
3863      /*
3864        Attempt to release memory. We ignore MORECORE return value,
3865        and instead call again to find out where new end of memory is.
3866        This avoids problems if first call releases less than we asked,
3867        of if failure somehow altered brk value. (We could still
3868        encounter problems if it altered brk in some very bad way,
3869        but the only thing we can do is adjust anyway, which will cause
3870        some downstream failure.)
3871      */
3872     
3873      MORECORE(-extra);
3874      new_brk = (char*)(MORECORE(0));
3875     
3876      if (new_brk != (char*)MORECORE_FAILURE) {
3877        released = (long)(current_brk - new_brk);
3878       
3879        if (released != 0) {
3880          /* Success. Adjust top. */
3881          av->sbrked_mem -= released;
3882          set_head(av->top, (top_size - released) | PREV_INUSE);
3883          check_malloc_state();
3884          return 1;
3885        }
3886      }
3887    }
3888  }
3889  return 0;
3890}
3891
3892/*
3893  ------------------------------ malloc ------------------------------
3894*/
3895
3896
3897#if __STD_C
3898DL_STATIC Void_t* mALLOc(size_t bytes)
3899#else
3900DL_STATIC   Void_t* mALLOc(bytes) size_t bytes;
3901#endif
3902{
3903  mstate av = get_malloc_state();
3904
3905  INTERNAL_SIZE_T nb;               /* normalized request size */
3906  unsigned int    idx;              /* associated bin index */
3907  mbinptr         bin;              /* associated bin */
3908  mfastbinptr*    fb;               /* associated fastbin */
3909
3910  chunkinfoptr       victim;           /* inspected/selected chunk */
3911  INTERNAL_SIZE_T size;             /* its size */
3912  int             victim_index;     /* its bin index */
3913
3914  chunkinfoptr       remainder;        /* remainder from a split */
3915  CHUNK_SIZE_T    remainder_size;   /* its size */
3916
3917  unsigned int    block;            /* bit map traverser */
3918  unsigned int    bit;              /* bit map traverser */
3919  unsigned int    map;              /* current word of binmap */
3920
3921  chunkinfoptr       fwd;              /* misc temp for linking */
3922  chunkinfoptr       bck;              /* misc temp for linking */
3923 
3924  Void_t*         retval;
3925
3926  /* chunkinfoptr         next; */
3927 
3928
3929  /*
3930    Convert request size to internal form by adding SIZE_SZ bytes
3931    overhead plus possibly more to obtain necessary alignment and/or
3932    to obtain a size of at least MINSIZE, the smallest allocatable
3933    size. Also, checked_request2size traps (returning 0) request sizes
3934    that are so large that they wrap around zero when padded and
3935    aligned.
3936  */
3937#if defined(SH_CUTEST)
3938  extern int malloc_count;
3939  ++malloc_count;
3940#endif
3941
3942  checked_request2size(bytes, nb);
3943
3944  /*
3945    Bypass search if no frees yet
3946   */
3947  if (av && have_anychunks(av)) {
3948    goto av_initialized;
3949  }
3950  else {
3951    if (!av || av->max_fast == 0) { /* initialization check */
3952      malloc_consolidate(av);
3953      av = get_malloc_state();
3954    }
3955    goto use_top;
3956  }
3957
3958 av_initialized:
3959
3960  /*
3961    If the size qualifies as a fastbin, first check corresponding bin.
3962  */
3963  if ((CHUNK_SIZE_T)(nb) <= (CHUNK_SIZE_T)(av->max_fast)) {
3964    fb = &(av->fastbins[(fastbin_index(nb))]);
3965    if ( (victim = *fb) != 0) {
3966      *fb = victim->fd;
3967      check_remalloced_chunk(victim, nb);
3968      guard_set(av->guard_stored, victim, bytes, nb);
3969      VALGRIND_MALLOCLIKE_BLOCK(chunk(victim), bytes, 0, 0);
3970      return chunk(victim);
3971    }
3972  }
3973
3974  /*
3975    If a small request, check regular bin.  Since these "smallbins"
3976    hold one size each, no searching within bins is necessary.
3977    (For a large request, we need to wait until unsorted chunks are
3978    processed to find best fit. But for small ones, fits are exact
3979    anyway, so we can check now, which is faster.)
3980  */
3981
3982  if (in_smallbin_range(nb)) {
3983    idx = smallbin_index(nb);
3984    bin = bin_at(av,idx);
3985
3986    if ((victim = last(bin)) != bin) {
3987      bck = victim->bk;
3988      bin->bk = bck;
3989      bck->fd = bin;
3990
3991      set_all_inuse(victim);
3992           
3993      check_malloced_chunk(victim, nb);
3994      guard_set(av->guard_stored, victim, bytes, nb);
3995      VALGRIND_MALLOCLIKE_BLOCK(chunk(victim), bytes, 0, 0);
3996      return chunk(victim);
3997    }
3998  }
3999
4000  /*
4001     If this is a large request, consolidate fastbins before continuing.
4002     While it might look excessive to kill all fastbins before
4003     even seeing if there is space available, this avoids
4004     fragmentation problems normally associated with fastbins.
4005     Also, in practice, programs tend to have runs of either small or
4006     large requests, but less often mixtures, so consolidation is not
4007     invoked all that often in most programs. And the programs that
4008     it is called frequently in otherwise tend to fragment.
4009  */
4010
4011  else {
4012    idx = largebin_index(nb);
4013    if (have_fastchunks(av)) 
4014      malloc_consolidate(av);
4015  }
4016
4017  /*
4018    Process recently freed or remaindered chunks, taking one only if
4019    it is exact fit, or, if this a small request, the chunk is remainder from
4020    the most recent non-exact fit.  Place other traversed chunks in
4021    bins.  Note that this step is the only place in any routine where
4022    chunks are placed in bins.
4023  */
4024   
4025  while ( (victim = unsorted_chunks(av)->bk) != unsorted_chunks(av)) {
4026    bck = victim->bk;
4027    size = chunksize(victim);
4028   
4029    /*
4030       If a small request, try to use last remainder if it is the
4031       only chunk in unsorted bin.  This helps promote locality for
4032       runs of consecutive small requests. This is the only
4033       exception to best-fit, and applies only when there is
4034       no exact fit for a small chunk.
4035    */
4036   
4037    if (UNLIKELY(in_smallbin_range(nb) && 
4038                 bck == unsorted_chunks(av) &&
4039                 victim == av->last_remainder &&
4040                 (CHUNK_SIZE_T)(size) > (CHUNK_SIZE_T)(nb + MINSIZE))) {
4041     
4042      /* split and reattach remainder */
4043      remainder_size = size - nb;
4044      remainder = cireg_getfree();
4045      remainder->chunk = chunk_at_offset(chunk(victim), nb);
4046      unsorted_chunks(av)->bk = unsorted_chunks(av)->fd = remainder;
4047      av->last_remainder = remainder; 
4048      remainder->bk = remainder->fd = unsorted_chunks(av);
4049     
4050      set_head(victim, nb | PREV_INUSE|INUSE);
4051      set_head(remainder, remainder_size | PREV_INUSE);     
4052      hashtable_insert(victim, remainder);
4053
4054      check_malloced_chunk(victim, nb);
4055      guard_set(av->guard_stored, victim, bytes, nb);
4056      VALGRIND_MALLOCLIKE_BLOCK(chunk(victim), bytes, 0, 0);
4057      return chunk(victim);
4058    }
4059   
4060    /* remove from unsorted list */
4061    unsorted_chunks(av)->bk = bck;
4062    bck->fd = unsorted_chunks(av);
4063   
4064    /* Take now instead of binning if exact fit */
4065   
4066    if (UNLIKELY(size == nb)) {
4067      set_all_inuse(victim)
4068      check_malloced_chunk(victim, nb);
4069      guard_set(av->guard_stored, victim, bytes, nb);
4070      VALGRIND_MALLOCLIKE_BLOCK(chunk(victim), bytes, 0, 0);
4071      return chunk(victim);
4072    }
4073   
4074    /* place chunk in bin */
4075   
4076    if (in_smallbin_range(size)) {
4077
4078      victim_index = smallbin_index(size);
4079      bck = bin_at(av, victim_index);
4080      fwd = bck->fd;
4081    }
4082    else {
4083      victim_index = largebin_index(size);
4084      bck = bin_at(av, victim_index);
4085      fwd = bck->fd;
4086     
4087      if (UNLIKELY(fwd != bck)) {
4088        /* if smaller than smallest, place first */
4089        if ((CHUNK_SIZE_T)(size) < (CHUNK_SIZE_T)(bck->bk->size)) {
4090          fwd = bck;
4091          bck = bck->bk;
4092        }
4093        else if ((CHUNK_SIZE_T)(size) >= 
4094                 (CHUNK_SIZE_T)(FIRST_SORTED_BIN_SIZE)) {
4095         
4096          /* maintain large bins in sorted order */
4097          size |= PREV_INUSE|INUSE; /* Or with inuse bits to speed comparisons */
4098          while ((CHUNK_SIZE_T)(size) < (CHUNK_SIZE_T)(fwd->size)) 
4099            fwd = fwd->fd;
4100          bck = fwd->bk;
4101        }
4102      }
4103    }
4104
4105    mark_bin(av, victim_index);
4106    victim->bk = bck;
4107    victim->fd = fwd;
4108    fwd->bk = victim;
4109    bck->fd = victim;
4110  }
4111 
4112  /*
4113    If a large request, scan through the chunks of current bin to
4114    find one that fits.  (This will be the smallest that fits unless
4115    FIRST_SORTED_BIN_SIZE has been changed from default.)  This is
4116    the only step where an unbounded number of chunks might be
4117    scanned without doing anything useful with them. However the
4118    lists tend to be short.
4119  */
4120
4121  if (!in_smallbin_range(nb)) {
4122    bin = bin_at(av, idx);
4123   
4124    victim = last(bin);
4125
4126    if (UNLIKELY(victim != bin)) {
4127
4128      do {
4129        size = chunksize(victim);
4130     
4131        if ((CHUNK_SIZE_T)(size) >= (CHUNK_SIZE_T)(nb)) {
4132          remainder_size = size - nb;
4133          unlink(victim, bck, fwd);
4134       
4135          /* Split */
4136          if (remainder_size >= MINSIZE) {
4137            remainder = cireg_getfree();
4138            remainder->chunk = chunk_at_offset(chunk(victim), nb);
4139            unsorted_chunks(av)->bk = unsorted_chunks(av)->fd = remainder;
4140            remainder->bk = remainder->fd = unsorted_chunks(av);
4141            set_head(victim, nb | PREV_INUSE | INUSE);
4142            set_head(remainder, remainder_size | PREV_INUSE);
4143            hashtable_insert(victim, remainder);
4144            check_malloced_chunk(victim, nb);
4145            guard_set(av->guard_stored, victim, bytes, nb);
4146            VALGRIND_MALLOCLIKE_BLOCK(chunk(victim), bytes, 0, 0);
4147            return chunk(victim);
4148          } 
4149          /* Exhaust */
4150          else  {
4151            set_all_inuse(victim);
4152            check_malloced_chunk(victim, nb);
4153            guard_set(av->guard_stored, victim, bytes, nb);
4154            VALGRIND_MALLOCLIKE_BLOCK(chunk(victim), bytes, 0, 0);
4155            return chunk(victim);
4156          }
4157        }
4158        victim = victim->bk;
4159      } while(victim != bin);
4160    }
4161  }
4162
4163  /*
4164    Search for a chunk by scanning bins, starting with next largest
4165    bin. This search is strictly by best-fit; i.e., the smallest
4166    (with ties going to approximately the least recently used) chunk
4167    that fits is selected.
4168   
4169    The bitmap avoids needing to check that most blocks are nonempty.
4170  */
4171   
4172
4173  ++idx;
4174  bin = bin_at(av,idx);
4175  block = idx2block(idx);
4176  map = av->binmap[block];
4177  bit = idx2bit(idx);
4178 
4179  for (;;) {
4180   
4181    /* Skip rest of block if there are no more set bits in this block.  */
4182    if (bit > map || bit == 0) {
4183      do {
4184        if (++block >= BINMAPSIZE)  /* out of bins */
4185          goto use_top;
4186      } while ( (map = av->binmap[block]) == 0);
4187     
4188      bin = bin_at(av, (block << BINMAPSHIFT));
4189      bit = 1;
4190    }
4191   
4192    /* Advance to bin with set bit. There must be one. */
4193    while ((bit & map) == 0) {
4194      bin = next_bin(bin);
4195      bit <<= 1;
4196      assert(bit != 0);
4197    }
4198   
4199    /* Inspect the bin. It is likely to be non-empty */
4200    victim = last(bin);
4201   
4202    /*  If a false alarm (empty bin), clear the bit. */
4203    if (victim == bin) {
4204      av->binmap[block] = map &= ~bit; /* Write through */
4205      bin = next_bin(bin);
4206      bit <<= 1;
4207    }
4208   
4209    else {
4210      size = chunksize(victim);
4211     
4212      /*  We know the first chunk in this bin is big enough to use. */
4213      assert((CHUNK_SIZE_T)(size) >= (CHUNK_SIZE_T)(nb));
4214     
4215      remainder_size = size - nb;
4216     
4217      /* unlink */
4218      bck = victim->bk;
4219      bin->bk = bck;
4220      bck->fd = bin;
4221     
4222      /* Split */
4223      if (remainder_size >= MINSIZE) {
4224        remainder = cireg_getfree();
4225        remainder->chunk = chunk_at_offset(chunk(victim), nb);
4226       
4227        unsorted_chunks(av)->bk = unsorted_chunks(av)->fd = remainder;
4228        remainder->bk = remainder->fd = unsorted_chunks(av);
4229        /* advertise as last remainder */
4230        if (in_smallbin_range(nb))
4231          av->last_remainder = remainder;
4232       
4233        set_head(victim, nb | PREV_INUSE | INUSE);
4234        set_head(remainder, remainder_size | PREV_INUSE);
4235        hashtable_insert(victim, remainder);
4236        check_malloced_chunk(victim, nb);
4237        guard_set(av->guard_stored, victim, bytes, nb);
4238        VALGRIND_MALLOCLIKE_BLOCK(chunk(victim), bytes, 0, 0);
4239        return chunk(victim);
4240      }
4241      /* Exhaust */
4242      else {
4243        set_all_inuse(victim);
4244        check_malloced_chunk(victim, nb);
4245        guard_set(av->guard_stored, victim, bytes, nb);
4246        VALGRIND_MALLOCLIKE_BLOCK(chunk(victim), bytes, 0, 0);
4247        return chunk(victim);
4248      }
4249     
4250    }
4251  }
4252
4253  use_top:
4254   
4255
4256  /*
4257    If large enough, split off the chunk bordering the end of memory
4258    (held in av->top). Note that this is in accord with the best-fit
4259    search rule.  In effect, av->top is treated as larger (and thus
4260    less well fitting) than any other available chunk since it can
4261    be extended to be as large as necessary (up to system
4262    limitations).
4263   
4264    We require that av->top always exists (i.e., has size >=
4265    MINSIZE) after initialization, so if it would otherwise be
4266    exhuasted by current request, it is replenished. (The main
4267    reason for ensuring it exists is that we may need MINSIZE space
4268    to put in fenceposts in sysmalloc.)
4269  */
4270 
4271  victim = av->top;
4272  size = chunksize(victim);
4273 
4274  if ((CHUNK_SIZE_T)(size) >= (CHUNK_SIZE_T)(nb + MINSIZE)) {
4275    remainder = cireg_getfree();
4276    remainder_size = size - nb;
4277    remainder->chunk = chunk_at_offset(chunk(victim), nb);
4278    av->top = remainder;
4279    set_head(victim, nb | PREV_INUSE | INUSE);
4280    set_head(remainder, remainder_size | PREV_INUSE);
4281    hashtable_insert(victim, remainder);
4282    check_malloced_chunk(victim, nb);
4283    guard_set(av->guard_stored, victim, bytes, nb);
4284    VALGRIND_MALLOCLIKE_BLOCK(chunk(victim), bytes, 0, 0);
4285    return chunk(victim);
4286  }
4287 
4288  /*
4289     If no space in top, relay to handle system-dependent cases
4290  */
4291  retval = sYSMALLOc(nb, av);
4292  if (retval) {
4293#if PARANOIA > 2
4294    victim = mem2chunk(retval); /* is used in guard_set macro */
4295#endif
4296    guard_set(av->guard_stored, victim, bytes, nb);
4297  }
4298  VALGRIND_MALLOCLIKE_BLOCK(retval, bytes, 0, 0);
4299  return retval;
4300}
4301
4302/*
4303  ------------------------------ free ------------------------------
4304*/
4305
4306#if __STD_C
4307DL_STATIC void fREe(Void_t* mem)
4308#else
4309DL_STATIC void fREe(mem) Void_t* mem;
4310#endif
4311{
4312  mstate av = get_malloc_state();
4313
4314  chunkinfoptr       p;           /* chunk corresponding to mem */
4315  INTERNAL_SIZE_T size;        /* its size */
4316  mfastbinptr*    fb;          /* associated fastbin */
4317  chunkinfoptr       prevchunk;   /* previous physical chunk */
4318  chunkinfoptr       nextchunk;   /* next contiguous chunk */
4319  INTERNAL_SIZE_T nextsize;    /* its size */
4320  INTERNAL_SIZE_T prevsize;    /* size of previous contiguous chunk */
4321  chunkinfoptr       bck;         /* misc temp for linking */
4322  chunkinfoptr       fwd;         /* misc temp for linking */
4323  chunkinfoptr       next;
4324#if defined(SH_CUTEST)
4325  extern int malloc_count;
4326  --malloc_count;
4327#endif
4328
4329  /* free(0) has no effect */
4330  if (mem != 0) {
4331    p = hashtable_lookup(mem);
4332    /* check that memory is managed by us
4333     * and is inuse
4334     */
4335    if (UNLIKELY(!p || !inuse(p))) 
4336      {
4337#ifdef DNMALLOC_CHECKS
4338        if (p) {
4339          fprintf(stderr, "Attempt to free memory not in use\n");
4340          abort();
4341        } else {
4342          fprintf(stderr, "Attempt to free memory not allocated\n");
4343          abort();
4344        }
4345#endif
4346        assert(p && inuse(p));
4347        return;
4348      }
4349
4350    VALGRIND_FREELIKE_BLOCK(mem, 0);
4351 
4352    guard_check(av->guard_stored, p);
4353   
4354    size = chunksize(p);
4355
4356    check_inuse_chunk(p);
4357
4358    /*
4359      If eligible, place chunk on a fastbin so it can be found
4360      and used quickly in malloc.
4361    */
4362
4363    if ((CHUNK_SIZE_T)(size) <= (CHUNK_SIZE_T)(av->max_fast)
4364
4365#if TRIM_FASTBINS
4366        /*
4367           If TRIM_FASTBINS set, don't place chunks
4368           bordering top into fastbins
4369        */
4370        && (chunk_at_offset(chunk(p), size) != av->top)
4371#endif
4372        ) {
4373
4374      set_fastchunks(av);
4375      fb = &(av->fastbins[fastbin_index(size)]);
4376      p->fd = *fb;
4377      *fb = p;
4378    }
4379
4380    /*
4381       Consolidate other non-mmapped chunks as they arrive.
4382    */
4383
4384    else if (!chunk_is_mmapped(p)) {
4385      set_anychunks(av);
4386
4387      nextchunk = next_chunkinfo(p);
4388      if (nextchunk)
4389        nextsize = chunksize(nextchunk);
4390      else
4391        nextsize = 0;/* gcc doesn't notice that it's only used if (nextchunk)*/
4392
4393      /* consolidate backward */
4394      if (UNLIKELY(!prev_inuse(p))) {
4395        prevchunk = prev_chunkinfo(p);
4396        prevsize = chunksize(prevchunk);
4397#ifdef DNMALLOC_CHECKS
4398        if (inuse(prevchunk)) {
4399                fprintf(stderr, "Dnmalloc error: trying to unlink an inuse chunk: %p (chunk: %p)\n This is definitely a bug, please report it to dnmalloc@fort-knox.org.\n", prevchunk, chunk(prevchunk));
4400                abort();
4401        }
4402#else
4403        assert(!inuse(prevchunk));
4404#endif
4405        size += prevsize;
4406        unlink(prevchunk, bck, fwd);
4407        set_head(p, size | PREV_INUSE);
4408        hashtable_skiprm(prevchunk,p);
4409        /* This chunk no longer exists in any form: release the chunkinfoptr
4410         */
4411        freecilst_add(p);
4412        p = prevchunk;
4413      }
4414
4415      if (nextchunk) {
4416        if (nextchunk != av->top) {
4417          /* get and clear inuse bit */
4418          clear_previnuse(nextchunk);
4419         
4420          /* consolidate forward */
4421          if (!inuse(nextchunk)) {
4422            /* if mmap is used instead of sbrk, we may have a
4423             * chunk with !nextchunk->fd && !nextchunk->bk
4424             */
4425            if (nextchunk->fd && nextchunk->fd)
4426              {
4427                unlink(nextchunk, bck, fwd);
4428                size += nextsize;
4429                set_head(p, size | PREV_INUSE);
4430                hashtable_skiprm(p, nextchunk);
4431                freecilst_add (nextchunk);
4432              }
4433          }
4434         
4435          set_head(p, size | PREV_INUSE);
4436          next = next_chunkinfo(p);
4437          if (next)
4438            next->prev_size = size;
4439         
4440          /*
4441            Place the chunk in unsorted chunk list. Chunks are
4442            not placed into regular bins until after they have
4443            been given one chance to be used in malloc.
4444          */
4445         
4446          bck = unsorted_chunks(av);
4447          fwd = bck->fd;
4448          p->bk = bck;
4449          p->fd = fwd;
4450          bck->fd = p;
4451          fwd->bk = p;
4452         
4453          nextchunk = next_chunkinfo(p);
4454          if (nextchunk)
4455            nextchunk->prev_size = chunksize(p);       
4456         
4457          check_free_chunk(p);
4458        }
4459       
4460        /*
4461          If the chunk borders the current high end of memory,
4462          consolidate into top
4463        */
4464       
4465        else {
4466          size += nextsize;
4467          set_head(p, size | PREV_INUSE);
4468          hashtable_remove(chunk(av->top));
4469          freecilst_add(av->top);
4470          av->top = p;
4471          check_chunk(p);
4472        }
4473      } /* if (nextchunk) */
4474
4475      /*
4476        If freeing a large space, consolidate possibly-surrounding
4477        chunks. Then, if the total unused topmost memory exceeds trim
4478        threshold, ask malloc_trim to reduce top.
4479
4480        Unless max_fast is 0, we don't know if there are fastbins
4481        bordering top, so we cannot tell for sure whether threshold
4482        has been reached unless fastbins are consolidated.  But we
4483        don't want to consolidate on each free.  As a compromise,
4484        consolidation is performed if FASTBIN_CONSOLIDATION_THRESHOLD
4485        is reached.
4486      */
4487
4488      if (UNLIKELY((CHUNK_SIZE_T)(size) >= FASTBIN_CONSOLIDATION_THRESHOLD)) { 
4489        if (have_fastchunks(av)) 
4490          malloc_consolidate(av);
4491
4492#ifndef MORECORE_CANNOT_TRIM       
4493        if ((CHUNK_SIZE_T)(chunksize(av->top)) >= 
4494            (CHUNK_SIZE_T)(av->trim_threshold))
4495          {
4496            if (morecore32bit(av))
4497              {
4498#ifdef DNMALLOC_DEBUG
4499                fprintf(stderr, "Calling systrim from free()\n");
4500#endif
4501                sYSTRIm(av->top_pad, av);
4502#ifdef DNMALLOC_DEBUG
4503                fprintf(stderr, "Systrim done\n");
4504#endif
4505              }
4506          }
4507#endif
4508      }
4509
4510    }
4511    /*
4512      If the chunk was allocated via mmap, release via munmap()
4513      Note that if HAVE_MMAP is false but chunk_is_mmapped is
4514      true, then user must have overwritten memory. There's nothing
4515      we can do to catch this error unless DEBUG is set, in which case
4516      check_inuse_chunk (above) will have triggered error.
4517    */
4518
4519    else {
4520#if  PARANOIA > 0
4521      int ret;
4522#endif
4523      INTERNAL_SIZE_T offset = (INTERNAL_SIZE_T) p->hash_next;
4524      av->n_mmaps--;
4525      av->mmapped_mem -= (size + offset);
4526#if  PARANOIA > 0
4527      ret = munmap((char*) chunk(p) - offset, size + offset);
4528#else
4529      munmap((char*) chunk(p) - offset, size + offset);
4530#endif
4531      hashtable_remove_mmapped(chunk(p));
4532      freecilst_add(p);
4533      /* munmap returns non-zero on failure */
4534      assert(ret == 0);
4535    }
4536  }
4537}
4538
4539/*
4540  ------------------------- malloc_consolidate -------------------------
4541
4542  malloc_consolidate is a specialized version of free() that tears
4543  down chunks held in fastbins.  Free itself cannot be used for this
4544  purpose since, among other things, it might place chunks back onto
4545  fastbins.  So, instead, we need to use a minor variant of the same
4546  code.
4547 
4548  Also, because this routine needs to be called the first time through
4549  malloc anyway, it turns out to be the perfect place to trigger
4550  initialization code.
4551*/
4552
4553#if __STD_C
4554static void malloc_consolidate(mstate av)
4555#else
4556static void malloc_consolidate(av) mstate av;
4557#endif
4558{
4559  mfastbinptr*    fb;                 /* current fastbin being consolidated */
4560  mfastbinptr*    maxfb;              /* last fastbin (for loop control) */
4561  chunkinfoptr       p;                  /* current chunk being consolidated */
4562  chunkinfoptr       nextp;              /* next chunk to consolidate */
4563  chunkinfoptr       prevp;
4564  chunkinfoptr       unsorted_bin;       /* bin header */
4565  chunkinfoptr       first_unsorted;     /* chunk to link to */
4566
4567  /* These have same use as in free() */
4568  chunkinfoptr       nextchunk;
4569  INTERNAL_SIZE_T size;
4570  INTERNAL_SIZE_T nextsize;
4571  INTERNAL_SIZE_T prevsize;
4572  chunkinfoptr       bck;
4573  chunkinfoptr       fwd;
4574  chunkinfoptr       next;
4575 
4576  /*
4577    If max_fast is 0, we know that av hasn't
4578    yet been initialized, in which case do so below
4579  */
4580  if (av && av->max_fast != 0) {
4581
4582    clear_fastchunks(av);
4583
4584    unsorted_bin = unsorted_chunks(av);
4585
4586    /*
4587      Remove each chunk from fast bin and consolidate it, placing it
4588      then in unsorted bin. Among other reasons for doing this,
4589      placing in unsorted bin avoids needing to calculate actual bins
4590      until malloc is sure that chunks aren't immediately going to be
4591      reused anyway.
4592    */
4593   
4594    maxfb = &(av->fastbins[fastbin_index(av->max_fast)]);
4595    fb = &(av->fastbins[0]);
4596    do {
4597      if ( UNLIKELY((p = *fb) != 0)) {
4598        *fb = 0;
4599        do {
4600          check_inuse_chunk(p);
4601          nextp = p->fd;
4602         
4603          /*
4604           * Slightly streamlined version of consolidation code in free()
4605           */
4606
4607          size = chunksize(p);
4608          nextchunk = next_chunkinfo(p);
4609
4610          /* gcc doesn't notice that it's only used if (nextchunk) */
4611          if (nextchunk)
4612            nextsize = chunksize(nextchunk);
4613          else
4614            nextsize = 0; 
4615         
4616          if (!prev_inuse(p)) {
4617             prevp = prev_chunkinfo(p);
4618             prevsize = chunksize(prevp);
4619             size += prevsize;
4620#ifdef DNMALLOC_CHECKS
4621             if (inuse(prevp)) {
4622                fprintf(stderr, "Dnmalloc error: trying to unlink an inuse chunk (2): %p (chunk: %p)\n This is definitely a bug, please report it to dnmalloc@fort-knox.org.\n", prevp, chunk(prevp));
4623                     abort();
4624             }
4625#else
4626             assert(!inuse(prevp));
4627#endif
4628             unlink(prevp, bck, fwd);
4629             set_head(p, size | PREV_INUSE);         
4630             hashtable_skiprm(prevp,p);
4631             freecilst_add(p);
4632             p=prevp;
4633          }
4634         
4635          if (nextchunk) {
4636            if (nextchunk != av->top) {
4637
4638              clear_previnuse(nextchunk);
4639           
4640              /* if mmap is used instead of sbrk, we may have a
4641               * chunk with !nextchunk->fd && !nextchunk->bk
4642               */
4643              if (!inuse(nextchunk)) {
4644                if( nextchunk->fd && nextchunk->bk) {
4645                  size += nextsize;
4646                  unlink(nextchunk, bck, fwd);
4647                  set_head(p, size | PREV_INUSE);
4648                  hashtable_skiprm(p,nextchunk);
4649                  freecilst_add(nextchunk);
4650                }
4651              }
4652             
4653              first_unsorted = unsorted_bin->fd;
4654              unsorted_bin->fd = p;
4655              first_unsorted->bk = p;
4656             
4657              set_head(p, size | PREV_INUSE);
4658              p->bk = unsorted_bin;
4659              p->fd = first_unsorted;
4660              next = next_chunkinfo(p);
4661              if (next)
4662                next->prev_size = size;
4663
4664           
4665            }
4666         
4667            else if (nextchunk == av->top) {
4668              size += nextsize;
4669              set_head(p, size | PREV_INUSE);
4670              hashtable_remove(chunk(av->top));
4671              freecilst_add(av->top);
4672              av->top = p;
4673            }
4674          } /* if (nextchunk) */
4675         
4676        } while ( (p = nextp) != 0);
4677       
4678      }
4679    } while (fb++ != maxfb);
4680  }
4681  else {
4682    /* Initialize dnmalloc */
4683    dnmalloc_init();
4684    malloc_init_state(get_malloc_state());
4685    check_malloc_state();
4686  }
4687}
4688
4689/*
4690  ------------------------------ realloc ------------------------------
4691*/
4692
4693
4694#if __STD_C
4695DL_STATIC Void_t* rEALLOc(Void_t* oldmem, size_t bytes)
4696#else
4697DL_STATIC Void_t* rEALLOc(oldmem, bytes) Void_t* oldmem; size_t bytes;
4698#endif
4699{
4700  mstate av = get_malloc_state();
4701
4702  INTERNAL_SIZE_T  nb;              /* padded request size */
4703
4704  chunkinfoptr        oldp;            /* chunk corresponding to oldmem */
4705  INTERNAL_SIZE_T  oldsize;         /* its size */
4706
4707  chunkinfoptr        newp;            /* chunk to return */
4708  INTERNAL_SIZE_T  newsize;         /* its size */
4709  Void_t*          newmem;          /* corresponding user mem */
4710
4711  chunkinfoptr        next;            /* next contiguous chunk after oldp */
4712
4713  chunkinfoptr        remainder;       /* extra space at end of newp */
4714  CHUNK_SIZE_T     remainder_size;  /* its size */
4715
4716  chunkinfoptr        bck;             /* misc temp for linking */
4717  chunkinfoptr        fwd;             /* misc temp for linking */
4718
4719  CHUNK_SIZE_T     copysize;        /* bytes to copy */
4720  unsigned int     ncopies;         /* INTERNAL_SIZE_T words to copy */
4721  INTERNAL_SIZE_T* s;               /* copy source */ 
4722  INTERNAL_SIZE_T* d;               /* copy destination */
4723
4724 
4725#ifdef REALLOC_ZERO_BYTES_FREES
4726  if (UNLIKELY(bytes == 0)) {
4727    fREe(oldmem);
4728    return 0;
4729  }
4730#endif
4731
4732  if (UNLIKELY(!av || av->max_fast == 0)) {
4733    malloc_consolidate(av);
4734    av = get_malloc_state();
4735  }
4736
4737  /* realloc of null is supposed to be same as malloc */
4738  if (UNLIKELY(oldmem == 0)) 
4739    return mALLOc(bytes);
4740
4741  checked_request2size(bytes, nb);
4742
4743  oldp    = hashtable_lookup(oldmem);
4744 
4745  if (UNLIKELY(!oldp || !inuse(oldp))){ 
4746     /* attempt to either realloc memory not managed by us
4747      * or memory that is not in use
4748      */
4749#ifdef DNMALLOC_CHECKS
4750    if (oldp) {
4751      fprintf(stderr, "Attempt to free memory not in use\n");
4752      abort();
4753    } else {
4754      fprintf(stderr, "Attempt to free memory not allocated\n");
4755      abort();
4756    }
4757#endif
4758    assert(oldp && inuse(oldp));
4759    return 0;     
4760  }
4761
4762  VALGRIND_FREELIKE_BLOCK(oldmem, 0);
4763  guard_check(av->guard_stored, oldp);
4764
4765  oldsize = chunksize(oldp);
4766
4767  check_inuse_chunk(oldp);
4768
4769  if (!chunk_is_mmapped(oldp)) {
4770
4771    if (UNLIKELY((CHUNK_SIZE_T)(oldsize) >= (CHUNK_SIZE_T)(nb))) {
4772      /* already big enough; split below */
4773      newp    = oldp;
4774      newsize = oldsize;
4775    }
4776
4777    else {
4778      next = next_chunkinfo(oldp);
4779      if (next)
4780        next->prev_size = oldsize;
4781      /* Try to expand forward into top */
4782      if (next && next == av->top &&
4783          (CHUNK_SIZE_T)(newsize = oldsize + chunksize(next)) >=
4784          (CHUNK_SIZE_T)(nb + MINSIZE)) {
4785         set_head_size(oldp, nb);
4786         hashtable_remove(chunk(av->top));
4787         av->top->chunk = chunk_at_offset(chunk(oldp), nb);
4788         set_head(av->top, (newsize - nb) | PREV_INUSE);
4789         /* av->top->chunk has been moved move in hashtable */
4790         hashtable_insert(oldp, av->top);
4791         guard_set(av->guard_stored, oldp, bytes, nb);
4792         VALGRIND_MALLOCLIKE_BLOCK(chunk(oldp), bytes, 0, 0); 
4793         return chunk(oldp);
4794      }
4795     
4796      /* Try to expand forward into next chunk;  split off remainder below */
4797      else if (next && next != av->top && 
4798               !inuse(next) &&
4799               (CHUNK_SIZE_T)(newsize = oldsize + chunksize(next)) >=
4800               (CHUNK_SIZE_T)(nb)) {
4801        newp = oldp;
4802        unlink(next, bck, fwd);
4803        hashtable_remove(chunk(next));
4804        freecilst_add(next);
4805        next = next_chunkinfo(oldp);
4806        if (next)
4807          next->prev_size = newsize;
4808      }
4809
4810      /* allocate, copy, free */
4811      else {
4812
4813        newmem = mALLOc(nb - MALLOC_ALIGN_MASK);
4814         if (newmem == 0)
4815          return 0; /* propagate failure */
4816
4817        newp = hashtable_lookup(newmem);
4818        newsize = chunksize(newp);
4819       
4820 
4821        /* next = next_chunkinfo(oldp); *//* 'next' never used rw 19.05.2008 */
4822        /*
4823          Avoid copy if newp is next chunk after oldp.
4824        */
4825        if (UNLIKELY(is_next_chunk(oldp, newp))) {
4826          newsize += oldsize;
4827          set_head_size(oldp, newsize);
4828          hashtable_skiprm(oldp, newp);
4829          freecilst_add(newp);   
4830          newp = oldp;
4831        }
4832        else {
4833          /*
4834            Unroll copy of <= 40 bytes (80 if 8byte sizes)
4835            We know that contents have an even number of
4836            INTERNAL_SIZE_T-sized words; minimally 4 (2 on amd64).
4837          */
4838         
4839          VALGRIND_MALLOCLIKE_BLOCK(chunk(oldp), chunksize(oldp), 0, 0);
4840
4841          copysize = oldsize;
4842          s = (INTERNAL_SIZE_T*)(oldmem);
4843          d = (INTERNAL_SIZE_T*)(newmem);
4844          ncopies = copysize / sizeof(INTERNAL_SIZE_T);
4845          assert(ncopies >= 2);
4846         
4847          if (ncopies > 10)
4848            MALLOC_COPY(d, s, copysize);
4849         
4850          else {
4851            *(d+0) = *(s+0);
4852            *(d+1) = *(s+1);
4853            if (ncopies > 2) {
4854              *(d+2) = *(s+2);
4855              *(d+3) = *(s+3);
4856              if (ncopies > 4) {
4857                *(d+4) = *(s+4);
4858                *(d+5) = *(s+5);
4859                if (ncopies > 6) {
4860                  *(d+6) = *(s+6);
4861                  *(d+7) = *(s+7);
4862                  if (ncopies > 8) {
4863                    *(d+8) = *(s+8);
4864                    *(d+9) = *(s+9);
4865                  }
4866                }
4867              }
4868            }
4869          }
4870         
4871          fREe(oldmem);
4872          check_inuse_chunk(newp);
4873          guard_set(av->guard_stored, newp, bytes, nb);
4874          return chunk(newp);
4875        }
4876      }
4877    }
4878
4879    /* If possible, free extra space in old or extended chunk */
4880
4881    assert((CHUNK_SIZE_T)(newsize) >= (CHUNK_SIZE_T)(nb));
4882
4883    remainder_size = newsize - nb;
4884
4885    if (remainder_size >= MINSIZE) { /* split remainder */
4886      remainder = cireg_getfree();
4887      remainder->chunk = chunk_at_offset(chunk(newp), nb);
4888      set_head_size(newp, nb);
4889      set_head(remainder, remainder_size | PREV_INUSE | INUSE);
4890      remainder->prev_size = nb;
4891      hashtable_insert(newp, remainder);
4892      /* Mark remainder as inuse so free() won't complain */
4893      set_all_inuse(remainder);
4894      guard_set(av->guard_stored, remainder, 0, remainder_size);
4895      VALGRIND_MALLOCLIKE_BLOCK(chunk(remainder), remainder_size, 0, 0);
4896      fREe(chunk(remainder)); 
4897    }
4898    else { /* not enough extra to split off */
4899      set_head_size(newp, newsize);
4900      set_all_inuse(newp);
4901    }
4902
4903    check_inuse_chunk(newp);
4904    guard_set(av->guard_stored, newp, bytes, nb);
4905    VALGRIND_MALLOCLIKE_BLOCK(chunk(newp), bytes, 0, 0);
4906    return chunk(newp);
4907  }
4908
4909  /*
4910    Handle mmap cases
4911  */
4912
4913  else {
4914
4915#if HAVE_MREMAP
4916    INTERNAL_SIZE_T offset = (INTERNAL_SIZE_T) oldp->hash_next;
4917    size_t pagemask = av->pagesize - 1;
4918    char *cp;
4919    CHUNK_SIZE_T  sum;
4920   
4921
4922    /* Note the extra SIZE_SZ overhead */
4923    /* newsize = (nb + offset + SIZE_SZ + pagemask) & ~pagemask; */
4924    newsize = (nb + offset + pagemask) & ~pagemask;
4925
4926    /* don't need to remap if still within same page */
4927    if (oldsize == newsize - offset)
4928      {
4929        guard_set(av->guard_stored, oldp, bytes, nb);
4930        VALGRIND_FREELIKE_BLOCK(oldmem, 0);
4931        VALGRIND_MALLOCLIKE_BLOCK(oldmem, bytes, 0, 0);
4932        return oldmem;
4933      }
4934
4935    cp = (char*)mremap((char*)chunk(oldp) - offset, oldsize + offset, newsize, 1);
4936   
4937    if (cp != (char*)MORECORE_FAILURE) {
4938       
4939      hashtable_remove_mmapped(chunk(oldp));
4940       
4941      oldp->chunk = (mchunkptr)(cp + offset);
4942      set_head(oldp, (newsize - offset)|IS_MMAPPED|INUSE);
4943     
4944      hashtable_add(oldp);
4945     
4946      assert(aligned_OK(chunk(oldp))); /* rw fix: newp -> oldp */
4947      assert(( ((INTERNAL_SIZE_T) oldp->hash_next) == offset));
4948     
4949      /* update statistics */
4950      sum = av->mmapped_mem += newsize - oldsize;
4951      if (sum > (CHUNK_SIZE_T)(av->max_mmapped_mem)) 
4952        av->max_mmapped_mem = sum;
4953      sum += av->sbrked_mem;
4954      if (sum > (CHUNK_SIZE_T)(av->max_total_mem)) 
4955        av->max_total_mem = sum;
4956     
4957      guard_set(av->guard_stored, oldp, bytes, nb);
4958      VALGRIND_FREELIKE_BLOCK(oldmem, 0);
4959      VALGRIND_MALLOCLIKE_BLOCK(chunk(oldp), bytes, 0, 0);
4960      return chunk(oldp);
4961    }
4962#endif /* have MREMAP */
4963
4964    /* Note the extra SIZE_SZ overhead. */
4965    if ((CHUNK_SIZE_T)(oldsize) >= (CHUNK_SIZE_T)(nb + SIZE_SZ)) 
4966      newmem = oldmem; /* do nothing */
4967    else {
4968      /* Must alloc, copy, free. */
4969      newmem = mALLOc(nb - MALLOC_ALIGN_MASK);
4970      if (newmem != 0) {
4971        MALLOC_COPY(newmem, oldmem, oldsize);
4972        fREe(oldmem);
4973      }
4974    }
4975    VALGRIND_MALLOCLIKE_BLOCK(newmem, bytes, 0, 0);
4976    guard_set(av->guard_stored, mem2chunk(newmem), bytes, nb);
4977    return newmem;
4978  }
4979}
4980
4981/*
4982  ---------------------------posix_memalign ----------------------------
4983*/
4984
4985#if __STD_C
4986DL_STATIC int posix_mEMALIGn(Void_t** memptr, size_t alignment, size_t bytes)
4987#else
4988DL_STATIC int posix_mEMALIGn(memptr, alignment, bytes) Void_t** memptr; size_t alignment; size_t bytes;
4989#endif
4990{
4991  mstate av;
4992
4993  if (alignment % sizeof(void *) != 0)
4994    return EINVAL;
4995  if ((alignment & (alignment - 1)) != 0)
4996    return EINVAL;
4997
4998  av = get_malloc_state();
4999  if (!av || av->max_fast == 0) malloc_consolidate(av);
5000  *memptr =  mEMALIGn(alignment, bytes);
5001
5002  return (*memptr != NULL ? 0 : ENOMEM);
5003}
5004
5005/*
5006  ------------------------------ memalign ------------------------------
5007*/
5008
5009#if __STD_C
5010DL_STATIC Void_t* mEMALIGn(size_t alignment, size_t bytes)
5011#else
5012DL_STATIC Void_t* mEMALIGn(alignment, bytes) size_t alignment; size_t bytes;
5013#endif
5014{
5015  INTERNAL_SIZE_T nb;             /* padded  request size */
5016  char*           m;              /* memory returned by malloc call */
5017  chunkinfoptr       p;              /* corresponding chunk */
5018  char*           brk;            /* alignment point within p */
5019  chunkinfoptr       newp;           /* chunk to return */
5020  INTERNAL_SIZE_T newsize;        /* its size */
5021  INTERNAL_SIZE_T leadsize;       /* leading space before alignment point */
5022  chunkinfoptr       remainder;      /* spare room at end to split off */
5023  CHUNK_SIZE_T    remainder_size; /* its size */
5024  INTERNAL_SIZE_T size;
5025#if PARANOIA > 2
5026  mstate          av;
5027#endif
5028
5029  /* If need less alignment than we give anyway, just relay to malloc */
5030
5031  if (UNLIKELY(alignment <= MALLOC_ALIGNMENT)) return mALLOc(bytes);
5032
5033  /* Otherwise, ensure that it is at least a minimum chunk size */
5034
5035  if (alignment <  MINSIZE) alignment = MINSIZE;
5036
5037  /* Make sure alignment is power of 2 (in case MINSIZE is not).  */
5038  if (UNLIKELY((alignment & (alignment - 1)) != 0)) {
5039    size_t a = MALLOC_ALIGNMENT * 2;
5040    while ((CHUNK_SIZE_T)a < (CHUNK_SIZE_T)alignment) a <<= 1;
5041    alignment = a;
5042  }
5043
5044  checked_request2size(bytes, nb);
5045
5046  /*
5047    Strategy: find a spot within that chunk that meets the alignment
5048    request, and then possibly free the leading and trailing space.
5049  */
5050
5051
5052  /* Call malloc with worst case padding to hit alignment. */
5053
5054  m  = (char*)(mALLOc(nb + alignment + MINSIZE));
5055
5056  if (m == 0) return 0; /* propagate failure */
5057
5058#if PARANOIA > 2
5059  av = get_malloc_state();
5060#endif
5061
5062  p = hashtable_lookup((mchunkptr) m);
5063
5064  if ((((PTR_UINT)(m)) % alignment) != 0) { /* misaligned */
5065
5066    /*
5067      Find an aligned spot inside chunk.  Since we need to give back
5068      leading space in a chunk of at least MINSIZE, if the first
5069      calculation places us at a spot with less than MINSIZE leader,
5070      we can move to the next aligned spot -- we've allocated enough
5071      total room so that this is always possible.
5072    */
5073
5074    brk = (char*) ((PTR_UINT)(((PTR_UINT)(m + alignment - 1)) &
5075                           -((signed long) alignment)));
5076    if ((CHUNK_SIZE_T)(brk - (char*)(chunk(p))) < MINSIZE)
5077      brk += alignment;
5078
5079    newp = cireg_getfree();
5080    newp->chunk = (mchunkptr)brk;
5081    leadsize = brk - (char*)(chunk(p));
5082    newsize = chunksize(p) - leadsize;
5083
5084    /* For mmapped chunks, just adjust offset */
5085    if (UNLIKELY(chunk_is_mmapped(p))) {
5086      newp->hash_next = (chunkinfoptr) (((INTERNAL_SIZE_T) p->hash_next) + leadsize);
5087      set_head(newp, newsize|IS_MMAPPED|INUSE);
5088      hashtable_remove_mmapped(chunk(p));
5089      freecilst_add(p);
5090      hashtable_add(newp);
5091      guard_set(av->guard_stored, newp, bytes, nb);
5092      return chunk(newp);
5093    }
5094
5095    /* Otherwise, give back leader, use the rest */
5096    set_head(newp, newsize | PREV_INUSE | INUSE);
5097    set_head_size(p, leadsize);
5098    set_all_inuse(newp);
5099    hashtable_add(newp); /* 20.05.2008 rw */
5100    guard_set(av->guard_stored, p, 0, leadsize);
5101    fREe(chunk(p));
5102    p = newp;
5103
5104    assert (newsize >= nb &&
5105            (((PTR_UINT)(chunk(p))) % alignment) == 0);
5106  }
5107
5108  /* Also give back spare room at the end */
5109  if (!chunk_is_mmapped(p)) {
5110    size = chunksize(p);
5111    if ((CHUNK_SIZE_T)(size) > (CHUNK_SIZE_T)(nb + MINSIZE)) {
5112       remainder = cireg_getfree();
5113       remainder_size = size - nb;
5114       remainder->chunk = chunk_at_offset(chunk(p), nb);
5115       set_head(remainder, remainder_size | PREV_INUSE | INUSE);
5116       set_head_size(p, nb);
5117       hashtable_add(remainder); /* 20.05.2008 rw */
5118       guard_set(av->guard_stored, remainder, 0, remainder_size);
5119       fREe(chunk(remainder));
5120    }
5121  }
5122
5123  check_inuse_chunk(p);
5124  guard_set(av->guard_stored, p, bytes, nb);
5125  return chunk(p);
5126}
5127
5128/*
5129  ------------------------------ calloc ------------------------------
5130*/
5131
5132#if __STD_C
5133DL_STATIC Void_t* cALLOc(size_t n_elements, size_t elem_size)
5134#else
5135DL_STATIC Void_t* cALLOc(n_elements, elem_size) size_t n_elements; size_t elem_size;
5136#endif
5137{
5138  chunkinfoptr p;
5139  CHUNK_SIZE_T  clearsize;
5140  CHUNK_SIZE_T  nclears;
5141  INTERNAL_SIZE_T* d;
5142  Void_t* mem;
5143 
5144 
5145  mem = mALLOc(n_elements * elem_size);
5146
5147  if (mem != 0) {
5148    p = hashtable_lookup(mem);
5149
5150    if (!chunk_is_mmapped(p))
5151    { 
5152      /*
5153        Unroll clear of <= 40 bytes (80 if 8byte sizes)
5154        We know that contents have an even number of
5155        INTERNAL_SIZE_T-sized words; minimally 4 (2 on amd64).
5156      */
5157
5158      d = (INTERNAL_SIZE_T*)mem;
5159      clearsize = chunksize(p);
5160      nclears = clearsize / sizeof(INTERNAL_SIZE_T);
5161      assert(nclears >= 2);
5162
5163      if (nclears > 10) {
5164        MALLOC_ZERO(d, clearsize);
5165      }
5166
5167      else {
5168        *(d+0) = 0;
5169        *(d+1) = 0;
5170        if (nclears > 2) {
5171          *(d+2) = 0;
5172          *(d+3) = 0;
5173          if (nclears > 4) {
5174            *(d+4) = 0;
5175            *(d+5) = 0;
5176            if (nclears > 6) {
5177              *(d+6) = 0;
5178              *(d+7) = 0;
5179              if (nclears > 8) {
5180                *(d+8) = 0;
5181                *(d+9) = 0;
5182              }
5183            }
5184          }
5185        }
5186      }
5187    }
5188#if ! MMAP_CLEARS
5189    else
5190    {
5191      d = (INTERNAL_SIZE_T*)mem;
5192      clearsize = chunksize(p);
5193      MALLOC_ZERO(d, clearsize);
5194    }
5195#endif
5196    /* Set guard again, since we just cleared it
5197     */
5198    guard_set(get_malloc_state()->guard_stored, p, (n_elements * elem_size), p->size);
5199  }
5200
5201  return mem;
5202}
5203
5204/*
5205  ------------------------------ valloc ------------------------------
5206*/
5207
5208#if __STD_C
5209DL_STATIC Void_t* vALLOc(size_t bytes)
5210#else
5211DL_STATIC Void_t* vALLOc(bytes) size_t bytes;
5212#endif
5213{
5214  /* Ensure initialization */
5215  mstate av = get_malloc_state();
5216  if (!av || av->max_fast == 0) {
5217    malloc_consolidate(av);
5218    av = get_malloc_state();
5219  }
5220  return mEMALIGn(av->pagesize, bytes);
5221}
5222
5223/*
5224  ------------------------------ pvalloc ------------------------------
5225*/
5226
5227
5228#if __STD_C
5229DL_STATIC Void_t* pVALLOc(size_t bytes)
5230#else
5231DL_STATIC Void_t* pVALLOc(bytes) size_t bytes;
5232#endif
5233{
5234  mstate av = get_malloc_state();
5235  size_t pagesz;
5236
5237  /* Ensure initialization */
5238  if (!av || av->max_fast == 0) {
5239    malloc_consolidate(av);
5240    av = get_malloc_state();
5241  }
5242  pagesz = av->pagesize;
5243  return mEMALIGn(pagesz, (bytes + pagesz - 1) & ~(pagesz - 1));
5244}
5245   
5246
5247/*
5248  ------------------------------ malloc_trim ------------------------------
5249*/
5250
5251#if __STD_C
5252DL_STATIC int mTRIm(size_t pad)
5253#else
5254DL_STATIC int mTRIm(pad) size_t pad;
5255#endif
5256{
5257  mstate av = get_malloc_state();
5258  /* Ensure initialization/consolidation */
5259  malloc_consolidate(av);
5260  av = get_malloc_state();
5261#ifndef MORECORE_CANNOT_TRIM
5262  if (morecore32bit(av))
5263    return sYSTRIm(pad, av);
5264  else
5265    return 0;
5266#else
5267  return 0;
5268#endif
5269}
5270
5271
5272
5273/*
5274  ------------------------- malloc_usable_size -------------------------
5275*/
5276
5277#if __STD_C
5278DL_STATIC size_t mUSABLe(Void_t* mem)
5279#else
5280DL_STATIC size_t mUSABLe(mem) Void_t* mem;
5281#endif
5282{
5283  chunkinfoptr p;
5284  if (mem != 0) {
5285    p = hashtable_lookup(mem);
5286    if (p && inuse(p)) return chunksize(p);
5287  }
5288  return 0;
5289}
5290
5291/*
5292  ------------------------------ mallinfo ------------------------------
5293*/
5294
5295DL_STATIC struct mallinfo mALLINFo()
5296{
5297  mstate av = get_malloc_state();
5298  struct mallinfo mi;
5299  unsigned int i;
5300  mbinptr b;
5301  chunkinfoptr p;
5302  INTERNAL_SIZE_T avail;
5303  INTERNAL_SIZE_T fastavail;
5304  int nblocks;
5305  int nfastblocks;
5306
5307  /* Ensure initialization */
5308  if (!av || av->top == 0) {
5309    malloc_consolidate(av);
5310    av = get_malloc_state();
5311  }
5312  check_malloc_state();
5313
5314  /* Account for top */
5315  avail = chunksize(av->top);
5316  nblocks = 1;  /* top always exists */
5317
5318  /* traverse fastbins */
5319  nfastblocks = 0;
5320  fastavail = 0;
5321
5322  for (i = 0; i < NFASTBINS; ++i) {
5323    for (p = av->fastbins[i]; p != 0; p = p->fd) {
5324      ++nfastblocks;
5325      fastavail += chunksize(p);
5326    }
5327  }
5328
5329  avail += fastavail;
5330
5331  /* traverse regular bins */
5332  for (i = 1; i < NBINS; ++i) {
5333    b = bin_at(av, i);
5334    for (p = last(b); p != b; p = p->bk) {
5335      ++nblocks;
5336      avail += chunksize(p);
5337    }
5338  }
5339
5340  mi.smblks = nfastblocks;
5341  mi.ordblks = nblocks;
5342  mi.fordblks = avail;
5343  mi.uordblks = av->sbrked_mem - avail;
5344  mi.arena = av->sbrked_mem;
5345  mi.hblks = av->n_mmaps;
5346  mi.hblkhd = av->mmapped_mem;
5347  mi.fsmblks = fastavail;
5348  mi.keepcost = chunksize(av->top);
5349  mi.usmblks = av->max_total_mem;
5350  return mi;
5351}
5352
5353/*
5354  ------------------------------ malloc_stats ------------------------------
5355*/
5356
5357DL_STATIC void mSTATs()
5358{
5359  struct mallinfo mi = mALLINFo();
5360
5361  fprintf(stderr, "hashtable = %10lu MB\n", 
5362          (CHUNK_SIZE_T)(HASHTABLESIZE / (1024*1024)));
5363  fprintf(stderr, "max system bytes = %10lu\n",
5364          (CHUNK_SIZE_T)(mi.usmblks));
5365  fprintf(stderr, "system bytes     = %10lu  (%10lu sbrked, %10lu mmaped)\n",
5366          (CHUNK_SIZE_T)(mi.arena + mi.hblkhd),
5367          (CHUNK_SIZE_T)(mi.arena),
5368          (CHUNK_SIZE_T)(mi.hblkhd));
5369  fprintf(stderr, "in use bytes     = %10lu\n",
5370          (CHUNK_SIZE_T)(mi.uordblks + mi.hblkhd));
5371
5372}
5373
5374
5375/*
5376  ------------------------------ mallopt ------------------------------
5377*/
5378
5379#if __STD_C
5380DL_STATIC int mALLOPt(int param_number, int value)
5381#else
5382DL_STATIC int mALLOPt(param_number, value) int param_number; int value;
5383#endif
5384{
5385  mstate av = get_malloc_state();
5386  /* Ensure initialization/consolidation */
5387  malloc_consolidate(av);
5388  av = get_malloc_state();
5389
5390  switch(param_number) {
5391  case M_MXFAST:
5392    if (value >= 0 && value <= MAX_FAST_SIZE) {
5393      set_max_fast(av, value);
5394      return 1;
5395    }
5396    else
5397      return 0;
5398
5399  case M_TRIM_THRESHOLD:
5400    av->trim_threshold = value;
5401    return 1;
5402
5403  case M_TOP_PAD:
5404    av->top_pad = value;
5405    return 1;
5406
5407  case M_MMAP_THRESHOLD:
5408    av->mmap_threshold = value;
5409    return 1;
5410
5411  case M_MMAP_MAX:
5412    if (value != 0)
5413      return 0;
5414    av->n_mmaps_max = value;
5415    return 1;
5416
5417  default:
5418    return 0;
5419  }
5420}
5421
5422
5423/*      $OpenBSD: arc4random.c,v 1.19 2008/06/04 00:50:23 djm Exp $     */
5424
5425/*
5426 * Copyright (c) 1996, David Mazieres <dm@uun.org>
5427 * Copyright (c) 2008, Damien Miller <djm@openbsd.org>
5428 *
5429 * Permission to use, copy, modify, and distribute this software for any
5430 * purpose with or without fee is hereby granted, provided that the above
5431 * copyright notice and this permission notice appear in all copies.
5432 *
5433 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
5434 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
5435 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
5436 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
5437 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
5438 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
5439 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
5440 */
5441
5442/*
5443 * Arc4 random number generator for OpenBSD.
5444 *
5445 * This code is derived from section 17.1 of Applied Cryptography,
5446 * second edition, which describes a stream cipher allegedly
5447 * compatible with RSA Labs "RC4" cipher (the actual description of
5448 * which is a trade secret).  The same algorithm is used as a stream
5449 * cipher called "arcfour" in Tatu Ylonen's ssh package.
5450 *
5451 * Here the stream cipher has been modified always to include the time
5452 * when initializing the state.  That makes it impossible to
5453 * regenerate the same random sequence twice, so this can't be used
5454 * for encryption, but will generate good random numbers.
5455 *
5456 * RC4 is a registered trademark of RSA Laboratories.
5457 */
5458
5459/* Moved u_int8_t -> unsigned char (portability)
5460 * Eliminated unneeded functions, added read from /dev/urandom taken from:
5461 $MirOS: contrib/code/Snippets/arc4random.c,v 1.3 2008-03-04 22:53:14 tg Exp $
5462 * Modified by Robert Connolly from OpenBSD lib/libc/crypt/arc4random.c v1.11.
5463 * This is arc4random(3) using urandom.
5464 */
5465
5466#include <fcntl.h>
5467#include <limits.h>
5468#include <stdlib.h>
5469#include <sys/param.h>
5470#include <sys/time.h>
5471
5472struct arc4_stream {
5473        unsigned char i;
5474        unsigned char j;
5475        unsigned char s[256];
5476};
5477
5478static int rs_initialized;
5479static struct arc4_stream rs;
5480static pid_t arc4_stir_pid;
5481static int arc4_count;
5482
5483static unsigned char arc4_getbyte(void);
5484
5485static void
5486arc4_init(void)
5487{
5488        int     n;
5489
5490        for (n = 0; n < 256; n++)
5491                rs.s[n] = n;
5492        rs.i = 0;
5493        rs.j = 0;
5494}
5495
5496static inline void
5497arc4_addrandom(unsigned char *dat, int datlen)
5498{
5499        int     n;
5500        unsigned char si;
5501
5502        rs.i--;
5503        for (n = 0; n < 256; n++) {
5504                rs.i = (rs.i + 1);
5505                si = rs.s[rs.i];
5506                rs.j = (rs.j + si + dat[n % datlen]);
5507                rs.s[rs.i] = rs.s[rs.j];
5508                rs.s[rs.j] = si;
5509        }
5510        rs.j = rs.i;
5511}
5512
5513#ifdef HAVE_SCHED_H
5514#include <sched.h>
5515#endif
5516
5517static void
5518arc4_stir(void)
5519{
5520        int     i;
5521        struct {
5522                struct timeval tv1;
5523                struct timeval tv2;
5524                u_int rnd[(128 - 2*sizeof(struct timeval)) / sizeof(u_int)];
5525        } rdat;
5526#if !defined(__FreeBSD__) && !defined(__OpenBSD__) && !defined(__NetBSD__)
5527        ssize_t sz = 0;
5528        int    fd;
5529#endif
5530 
5531        gettimeofday(&rdat.tv1, NULL);
5532
5533
5534        if (!rs_initialized) {
5535                arc4_init();
5536                rs_initialized = 1;
5537        }
5538
5539#if !defined(__FreeBSD__) && !defined(__OpenBSD__) && !defined(__NetBSD__)
5540
5541#ifdef HAVE_SCHED_YIELD
5542        /* Yield the processor to introduce some random delay. */
5543        (void) sched_yield();
5544#endif
5545
5546        /*
5547         * Pthread problem in multithreaded code on *BSD.
5548         */
5549        fd = open("/dev/urandom", O_RDONLY);
5550        if (fd != -1) {
5551                sz = (size_t)read(fd, rdat.rnd, sizeof (rdat.rnd));
5552                /*
5553                 * gcc complains if we ignore the return value of read(), and
5554                 * the llvm/clang analyzer complains if we don't use it...
5555                 */
5556                if (sz > (-256)) /* always true */
5557                  close(fd);
5558        }
5559        /*
5560        if (sz > sizeof (rdat.rnd))
5561                sz = 0;
5562        */
5563 #endif
5564
5565        arc4_stir_pid = getpid();
5566        gettimeofday(&rdat.tv2, NULL);
5567
5568        arc4_addrandom((void *)&rdat, sizeof(rdat));
5569
5570        /*
5571         * Discard early keystream, as per recommendations in:
5572         * http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Rc4_ksa.ps
5573         */
5574        for (i = 0; i < 256; i++)
5575                (void)arc4_getbyte();
5576        arc4_count = 1600000;
5577}
5578
5579static unsigned char
5580arc4_getbyte(void)
5581{
5582        unsigned char si, sj;
5583
5584        rs.i = (rs.i + 1);
5585        si = rs.s[rs.i];
5586        rs.j = (rs.j + si);
5587        sj = rs.s[rs.j];
5588        rs.s[rs.i] = sj;
5589        rs.s[rs.j] = si;
5590        return (rs.s[(si + sj) & 0xff]);
5591}
5592
5593
5594 /* Changed to return char* */
5595static char *
5596dnmalloc_arc4random(void)
5597{
5598        static char val[4];
5599       
5600        /* We only call this once, hence no need for locking. */
5601
5602        /* _ARC4_LOCK(); */
5603        arc4_count -= 4;
5604        if (arc4_count <= 0 || !rs_initialized || arc4_stir_pid != getpid())
5605                arc4_stir();
5606
5607        val[0] = (char) arc4_getbyte();
5608        val[1] = (char) arc4_getbyte();
5609        val[2] = (char) arc4_getbyte();
5610        val[3] = (char) arc4_getbyte();
5611
5612        arc4_stir();
5613        /* _ARC4_UNLOCK(); */
5614        return val;
5615}
5616
5617#else
5618int dnmalloc_pthread_init() { return 0; }
5619#endif /* ! USE_SYSTEM_MALLOC */
Note: See TracBrowser for help on using the repository browser.