Back to index

tor  0.2.3.18-rc
OpenBSD_malloc_Linux.c
Go to the documentation of this file.
00001 /* Version 1.83 for Linux.
00002  * Compilation: gcc -shared -fPIC -O2 OpenBSD_malloc_Linux.c -o malloc.so
00003  * Launching: LD_PRELOAD=/path/to/malloc.so firefox
00004  */
00005 
00006 /*     $OpenBSD: malloc.c,v 1.83 2006/05/14 19:53:40 otto Exp $       */
00007 
00008 /*
00009  * ----------------------------------------------------------------------------
00010  * "THE BEER-WARE LICENSE" (Revision 42):
00011  * <phk@FreeBSD.ORG> wrote this file.  As long as you retain this notice you
00012  * can do whatever you want with this stuff. If we meet some day, and you think
00013  * this stuff is worth it, you can buy me a beer in return.   Poul-Henning Kamp
00014  * ----------------------------------------------------------------------------
00015  */
00016 
00017 /*
00018  * Defining MALLOC_EXTRA_SANITY will enable extra checks which are
00019  * related to internal conditions and consistency in malloc.c. This has
00020  * a noticeable runtime performance hit, and generally will not do you
00021  * any good unless you fiddle with the internals of malloc or want
00022  * to catch random pointer corruption as early as possible.
00023  */
00024 #ifndef       MALLOC_EXTRA_SANITY
00025 #undef MALLOC_EXTRA_SANITY
00026 #endif
00027 
00028 /*
00029  * Defining MALLOC_STATS will enable you to call malloc_dump() and set
00030  * the [dD] options in the MALLOC_OPTIONS environment variable.
00031  * It has no run-time performance hit, but does pull in stdio...
00032  */
00033 #ifndef       MALLOC_STATS
00034 #undef MALLOC_STATS
00035 #endif
00036 
00037 /*
00038  * What to use for Junk.  This is the byte value we use to fill with
00039  * when the 'J' option is enabled.
00040  */
00041 #define SOME_JUNK    0xd0   /* as in "Duh" :-) */
00042 
00043 #include <sys/types.h>
00044 #include <sys/time.h>
00045 #include <sys/resource.h>
00046 #include <sys/param.h>
00047 #include <sys/mman.h>
00048 #include <sys/uio.h>
00049 #include <stdio.h>
00050 #include <stdlib.h>
00051 #include <string.h>
00052 #include <unistd.h>
00053 #include <fcntl.h>
00054 #include <limits.h>
00055 #include <errno.h>
00056 #include <err.h>
00057 /* For SIZE_T_MAX */
00058 #include "torint.h"
00059 
00060 //#include "thread_private.h"
00061 
00062 /*
00063  * The basic parameters you can tweak.
00064  *
00065  * malloc_pageshift  pagesize = 1 << malloc_pageshift
00066  *                   It's probably best if this is the native
00067  *                   page size, but it shouldn't have to be.
00068  *
00069  * malloc_minsize    minimum size of an allocation in bytes.
00070  *                   If this is too small it's too much work
00071  *                   to manage them.  This is also the smallest
00072  *                   unit of alignment used for the storage
00073  *                   returned by malloc/realloc.
00074  *
00075  */
00076 
00077 static int align = 0;
00078 static size_t g_alignment = 0;
00079 
00080 extern int __libc_enable_secure;
00081 
00082 static int issetugid(void)
00083 {
00084        if (__libc_enable_secure) return 1;
00085        if (getuid() != geteuid()) return 1;
00086        if (getgid() != getegid()) return 1;
00087        return 0;
00088 }
00089 
00090 #define PGSHIFT 12
00091 #define MADV_FREE MADV_DONTNEED
00092 #include <pthread.h>
00093 static pthread_mutex_t gen_mutex = PTHREAD_MUTEX_INITIALIZER;
00094 
00095 #define _MALLOC_LOCK_INIT() {;}
00096 #define _MALLOC_LOCK() {pthread_mutex_lock(&gen_mutex);}
00097 #define _MALLOC_UNLOCK() {pthread_mutex_unlock(&gen_mutex);}
00098 
00099 #if defined(__sparc__) || defined(__alpha__)
00100 #define       malloc_pageshift     13U
00101 #endif
00102 #if defined(__ia64__)
00103 #define       malloc_pageshift     14U
00104 #endif
00105 
00106 #ifndef malloc_pageshift
00107 #define malloc_pageshift    (PGSHIFT)
00108 #endif
00109 
00110 /*
00111  * No user serviceable parts behind this point.
00112  *
00113  * This structure describes a page worth of chunks.
00114  */
00115 struct pginfo {
00116        struct pginfo *next; /* next on the free list */
00117        void          *page; /* Pointer to the page */
00118        u_short              size;  /* size of this page's chunks */
00119        u_short              shift; /* How far to shift for this size chunks */
00120        u_short              free;  /* How many free chunks */
00121        u_short              total; /* How many chunk */
00122        u_long        bits[1];/* Which chunks are free */
00123 };
00124 
00125 /* How many bits per u_long in the bitmap */
00126 #define       MALLOC_BITS   (int)((NBBY * sizeof(u_long)))
00127 
00128 /*
00129  * This structure describes a number of free pages.
00130  */
00131 struct pgfree {
00132        struct pgfree *next; /* next run of free pages */
00133        struct pgfree *prev; /* prev run of free pages */
00134        void          *page; /* pointer to free pages */
00135        void          *pdir; /* pointer to the base page's dir */
00136        size_t        size;  /* number of bytes free */
00137 };
00138 
00139 /*
00140  * Magic values to put in the page_directory
00141  */
00142 #define MALLOC_NOT_MINE     ((struct pginfo*) 0)
00143 #define MALLOC_FREE  ((struct pginfo*) 1)
00144 #define MALLOC_FIRST ((struct pginfo*) 2)
00145 #define MALLOC_FOLLOW       ((struct pginfo*) 3)
00146 #define MALLOC_MAGIC ((struct pginfo*) 4)
00147 
00148 #ifndef malloc_minsize
00149 #define malloc_minsize                    16UL
00150 #endif
00151 
00152 #if !defined(malloc_pagesize)
00153 #define malloc_pagesize                   (1UL<<malloc_pageshift)
00154 #endif
00155 
00156 #if ((1UL<<malloc_pageshift) != malloc_pagesize)
00157 #error "(1UL<<malloc_pageshift) != malloc_pagesize"
00158 #endif
00159 
00160 #ifndef malloc_maxsize
00161 #define malloc_maxsize                    ((malloc_pagesize)>>1)
00162 #endif
00163 
00164 /* A mask for the offset inside a page. */
00165 #define malloc_pagemask     ((malloc_pagesize)-1)
00166 
00167 #define       pageround(foo)       (((foo) + (malloc_pagemask)) & ~malloc_pagemask)
00168 #define       ptr2index(foo)       (((u_long)(foo) >> malloc_pageshift)+malloc_pageshift)
00169 #define       index2ptr(idx)       ((void*)(((idx)-malloc_pageshift)<<malloc_pageshift))
00170 
00171 /* Set when initialization has been done */
00172 static unsigned int  malloc_started;
00173 
00174 /* Number of free pages we cache */
00175 static unsigned int  malloc_cache = 16;
00176 
00177 /* Structure used for linking discrete directory pages. */
00178 struct pdinfo {
00179        struct pginfo **base;
00180        struct pdinfo *prev;
00181        struct pdinfo *next;
00182        u_long        dirnum;
00183 };
00184 static struct pdinfo *last_dir;    /* Caches to the last and previous */
00185 static struct pdinfo *prev_dir;    /* referenced directory pages. */
00186 
00187 static size_t pdi_off;
00188 static u_long pdi_mod;
00189 #define       PD_IDX(num)   ((num) / (malloc_pagesize/sizeof(struct pginfo *)))
00190 #define       PD_OFF(num)   ((num) & ((malloc_pagesize/sizeof(struct pginfo *))-1))
00191 #define       PI_IDX(index) ((index) / pdi_mod)
00192 #define       PI_OFF(index) ((index) % pdi_mod)
00193 
00194 /* The last index in the page directory we care about */
00195 static u_long last_index;
00196 
00197 /* Pointer to page directory. Allocated "as if with" malloc */
00198 static struct pginfo **page_dir;
00199 
00200 /* Free pages line up here */
00201 static struct pgfree free_list;
00202 
00203 /* Abort(), user doesn't handle problems. */
00204 static int    malloc_abort = 2;
00205 
00206 /* Are we trying to die ? */
00207 static int    suicide;
00208 
00209 #ifdef MALLOC_STATS
00210 /* dump statistics */
00211 static int    malloc_stats;
00212 #endif
00213 
00214 /* avoid outputting warnings? */
00215 static int    malloc_silent;
00216 
00217 /* always realloc ? */
00218 static int    malloc_realloc;
00219 
00220 /* mprotect free pages PROT_NONE? */
00221 static int    malloc_freeprot;
00222 
00223 /* use guard pages after allocations? */
00224 static size_t malloc_guard = 0;
00225 static size_t malloc_guarded;
00226 /* align pointers to end of page? */
00227 static int    malloc_ptrguard;
00228 
00229 static int    malloc_hint = 1;
00230 
00231 /* xmalloc behaviour ? */
00232 static int    malloc_xmalloc;
00233 
00234 /* zero fill ? */
00235 static int    malloc_zero;
00236 
00237 /* junk fill ? */
00238 static int    malloc_junk;
00239 
00240 #ifdef __FreeBSD__
00241 /* utrace ? */
00242 static int    malloc_utrace;
00243 
00244 struct ut {
00245        void          *p;
00246        size_t        s;
00247        void          *r;
00248 };
00249 
00250 void          utrace(struct ut *, int);
00251 
00252 #define UTRACE(a, b, c) \
00253        if (malloc_utrace) \
00254               {struct ut u; u.p=a; u.s = b; u.r=c; utrace(&u, sizeof u);}
00255 #else                       /* !__FreeBSD__ */
00256 #define UTRACE(a,b,c)
00257 #endif
00258 
00259 /* Status of malloc. */
00260 static int    malloc_active;
00261 
00262 /* Allocated memory. */
00263 static size_t malloc_used;
00264 
00265 /* My last break. */
00266 static caddr_t       malloc_brk;
00267 
00268 /* One location cache for free-list holders. */
00269 static struct pgfree *px;
00270 
00271 /* Compile-time options. */
00272 char          *malloc_options;
00273 
00274 /* Name of the current public function. */
00275 static const char    *malloc_func;
00276 
00277 #define MMAP(size) \
00278        mmap((void *)0, (size), PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, \
00279            -1, (off_t)0)
00280 
00281 /*
00282  * Necessary function declarations.
00283  */
00284 static void   *imalloc(size_t size);
00285 static void   ifree(void *ptr);
00286 static void   *irealloc(void *ptr, size_t size);
00287 static void   *malloc_bytes(size_t size);
00288 void *memalign(size_t boundary, size_t size);
00289 size_t malloc_good_size(size_t size);
00290 
00291 /*
00292  * Function for page directory lookup.
00293  */
00294 static int
00295 pdir_lookup(u_long index, struct pdinfo ** pdi)
00296 {
00297        struct pdinfo *spi;
00298        u_long        pidx = PI_IDX(index);
00299 
00300        if (last_dir != NULL && PD_IDX(last_dir->dirnum) == pidx)
00301               *pdi = last_dir;
00302        else if (prev_dir != NULL && PD_IDX(prev_dir->dirnum) == pidx)
00303               *pdi = prev_dir;
00304        else if (last_dir != NULL && prev_dir != NULL) {
00305               if ((PD_IDX(last_dir->dirnum) > pidx) ?
00306                   (PD_IDX(last_dir->dirnum) - pidx) :
00307                   (pidx - PD_IDX(last_dir->dirnum))
00308                   < (PD_IDX(prev_dir->dirnum) > pidx) ?
00309                   (PD_IDX(prev_dir->dirnum) - pidx) :
00310                   (pidx - PD_IDX(prev_dir->dirnum)))
00311                      *pdi = last_dir;
00312               else
00313                      *pdi = prev_dir;
00314 
00315               if (PD_IDX((*pdi)->dirnum) > pidx) {
00316                      for (spi = (*pdi)->prev;
00317                          spi != NULL && PD_IDX(spi->dirnum) > pidx;
00318                          spi = spi->prev)
00319                             *pdi = spi;
00320                      if (spi != NULL)
00321                             *pdi = spi;
00322               } else
00323                      for (spi = (*pdi)->next;
00324                          spi != NULL && PD_IDX(spi->dirnum) <= pidx;
00325                          spi = spi->next)
00326                             *pdi = spi;
00327        } else {
00328               *pdi = (struct pdinfo *) ((caddr_t) page_dir + pdi_off);
00329               for (spi = *pdi;
00330                   spi != NULL && PD_IDX(spi->dirnum) <= pidx;
00331                   spi = spi->next)
00332                      *pdi = spi;
00333        }
00334 
00335        return ((PD_IDX((*pdi)->dirnum) == pidx) ? 0 :
00336            (PD_IDX((*pdi)->dirnum) > pidx) ? 1 : -1);
00337 }
00338 
00339 #ifdef MALLOC_STATS
00340 void
00341 malloc_dump(int fd)
00342 {
00343        char          buf[1024];
00344        struct pginfo **pd;
00345        struct pgfree *pf;
00346        struct pdinfo *pi;
00347        u_long        j;
00348 
00349        pd = page_dir;
00350        pi = (struct pdinfo *) ((caddr_t) pd + pdi_off);
00351 
00352        /* print out all the pages */
00353        for (j = 0; j <= last_index;) {
00354               snprintf(buf, sizeof buf, "%08lx %5lu ", j << malloc_pageshift, j);
00355               write(fd, buf, strlen(buf));
00356               if (pd[PI_OFF(j)] == MALLOC_NOT_MINE) {
00357                      for (j++; j <= last_index && pd[PI_OFF(j)] == MALLOC_NOT_MINE;) {
00358                             if (!PI_OFF(++j)) {
00359                                    if ((pi = pi->next) == NULL ||
00360                                        PD_IDX(pi->dirnum) != PI_IDX(j))
00361                                           break;
00362                                    pd = pi->base;
00363                                    j += pdi_mod;
00364                             }
00365                      }
00366                      j--;
00367                      snprintf(buf, sizeof buf, ".. %5lu not mine\n", j);
00368                      write(fd, buf, strlen(buf));
00369               } else if (pd[PI_OFF(j)] == MALLOC_FREE) {
00370                      for (j++; j <= last_index && pd[PI_OFF(j)] == MALLOC_FREE;) {
00371                             if (!PI_OFF(++j)) {
00372                                    if ((pi = pi->next) == NULL ||
00373                                        PD_IDX(pi->dirnum) != PI_IDX(j))
00374                                           break;
00375                                    pd = pi->base;
00376                                    j += pdi_mod;
00377                             }
00378                      }
00379                      j--;
00380                      snprintf(buf, sizeof buf, ".. %5lu free\n", j);
00381                      write(fd, buf, strlen(buf));
00382               } else if (pd[PI_OFF(j)] == MALLOC_FIRST) {
00383                      for (j++; j <= last_index && pd[PI_OFF(j)] == MALLOC_FOLLOW;) {
00384                             if (!PI_OFF(++j)) {
00385                                    if ((pi = pi->next) == NULL ||
00386                                        PD_IDX(pi->dirnum) != PI_IDX(j))
00387                                           break;
00388                                    pd = pi->base;
00389                                    j += pdi_mod;
00390                             }
00391                      }
00392                      j--;
00393                      snprintf(buf, sizeof buf, ".. %5lu in use\n", j);
00394                      write(fd, buf, strlen(buf));
00395               } else if (pd[PI_OFF(j)] < MALLOC_MAGIC) {
00396                      snprintf(buf, sizeof buf, "(%p)\n", pd[PI_OFF(j)]);
00397                      write(fd, buf, strlen(buf));
00398               } else {
00399                      snprintf(buf, sizeof buf, "%p %d (of %d) x %d @ %p --> %p\n",
00400                          pd[PI_OFF(j)], pd[PI_OFF(j)]->free,
00401                          pd[PI_OFF(j)]->total, pd[PI_OFF(j)]->size,
00402                          pd[PI_OFF(j)]->page, pd[PI_OFF(j)]->next);
00403                      write(fd, buf, strlen(buf));
00404               }
00405               if (!PI_OFF(++j)) {
00406                      if ((pi = pi->next) == NULL)
00407                             break;
00408                      pd = pi->base;
00409                      j += (1 + PD_IDX(pi->dirnum) - PI_IDX(j)) * pdi_mod;
00410               }
00411        }
00412 
00413        for (pf = free_list.next; pf; pf = pf->next) {
00414               snprintf(buf, sizeof buf, "Free: @%p [%p...%p[ %ld ->%p <-%p\n",
00415                   pf, pf->page, (char *)pf->page + pf->size,
00416                   pf->size, pf->prev, pf->next);
00417               write(fd, buf, strlen(buf));
00418               if (pf == pf->next) {
00419                      snprintf(buf, sizeof buf, "Free_list loops\n");
00420                      write(fd, buf, strlen(buf));
00421                      break;
00422               }
00423        }
00424 
00425        /* print out various info */
00426        snprintf(buf, sizeof buf, "Minsize\t%lu\n", malloc_minsize);
00427        write(fd, buf, strlen(buf));
00428        snprintf(buf, sizeof buf, "Maxsize\t%lu\n", malloc_maxsize);
00429        write(fd, buf, strlen(buf));
00430        snprintf(buf, sizeof buf, "Pagesize\t%lu\n", malloc_pagesize);
00431        write(fd, buf, strlen(buf));
00432        snprintf(buf, sizeof buf, "Pageshift\t%u\n", malloc_pageshift);
00433        write(fd, buf, strlen(buf));
00434        snprintf(buf, sizeof buf, "In use\t%lu\n", (u_long) malloc_used);
00435        write(fd, buf, strlen(buf));
00436        snprintf(buf, sizeof buf, "Guarded\t%lu\n", (u_long) malloc_guarded);
00437        write(fd, buf, strlen(buf));
00438 }
00439 #endif /* MALLOC_STATS */
00440 
00441 extern char   *__progname;
00442 
00443 static void
00444 wrterror(const char *p)
00445 {
00446        const char           *q = " error: ";
00447        struct iovec  iov[5];
00448 
00449        iov[0].iov_base = __progname;
00450        iov[0].iov_len = strlen(__progname);
00451        iov[1].iov_base = (char*)malloc_func;
00452        iov[1].iov_len = strlen(malloc_func);
00453        iov[2].iov_base = (char*)q;
00454        iov[2].iov_len = strlen(q);
00455        iov[3].iov_base = (char*)p;
00456        iov[3].iov_len = strlen(p);
00457        iov[4].iov_base = (char*)"\n";
00458        iov[4].iov_len = 1;
00459        writev(STDERR_FILENO, iov, 5);
00460 
00461        suicide = 1;
00462 #ifdef MALLOC_STATS
00463        if (malloc_stats)
00464               malloc_dump(STDERR_FILENO);
00465 #endif /* MALLOC_STATS */
00466        malloc_active--;
00467        if (malloc_abort)
00468               abort();
00469 }
00470 
00471 static void
00472 wrtwarning(const char *p)
00473 {
00474        const char           *q = " warning: ";
00475        struct iovec  iov[5];
00476 
00477        if (malloc_abort)
00478               wrterror(p);
00479        else if (malloc_silent)
00480               return;
00481 
00482        iov[0].iov_base = __progname;
00483        iov[0].iov_len = strlen(__progname);
00484        iov[1].iov_base = (char*)malloc_func;
00485        iov[1].iov_len = strlen(malloc_func);
00486        iov[2].iov_base = (char*)q;
00487        iov[2].iov_len = strlen(q);
00488        iov[3].iov_base = (char*)p;
00489        iov[3].iov_len = strlen(p);
00490        iov[4].iov_base = (char*)"\n";
00491        iov[4].iov_len = 1;
00492        
00493        writev(STDERR_FILENO, iov, 5);
00494 }
00495 
00496 #ifdef MALLOC_STATS
00497 static void
00498 malloc_exit(void)
00499 {
00500        char   *q = "malloc() warning: Couldn't dump stats\n";
00501        int    save_errno = errno, fd;
00502 
00503        fd = open("malloc.out", O_RDWR|O_APPEND);
00504        if (fd != -1) {
00505               malloc_dump(fd);
00506               close(fd);
00507        } else
00508               write(STDERR_FILENO, q, strlen(q));
00509        errno = save_errno;
00510 }
00511 #endif /* MALLOC_STATS */
00512 
00513 /*
00514  * Allocate aligned mmaped chunk
00515  */
00516 
00517 static void *MMAP_A(size_t pages, size_t alignment)
00518 {
00519        void *j, *p;
00520        size_t first_size, rest, begin, end;
00521        if (pages%malloc_pagesize != 0)
00522               pages = pages - pages%malloc_pagesize + malloc_pagesize;
00523        first_size = pages + alignment - malloc_pagesize;
00524        p = MMAP(first_size);
00525        rest = ((size_t)p) % alignment;
00526        j = (rest == 0) ? p : (void*) ((size_t)p + alignment - rest);
00527        begin = (size_t)j - (size_t)p;
00528        if (begin != 0) munmap(p, begin);
00529        end = (size_t)p + first_size - ((size_t)j + pages);
00530        if(end != 0) munmap( (void*) ((size_t)j + pages), end);
00531 
00532        return j;
00533 }
00534 
00535 
00536 /*
00537  * Allocate a number of pages from the OS
00538  */
00539 static void *
00540 map_pages(size_t pages)
00541 {
00542        struct pdinfo *pi, *spi;
00543        struct pginfo **pd;
00544        u_long        idx, pidx, lidx;
00545        caddr_t              result, tail;
00546        u_long        index, lindex;
00547        void          *pdregion = NULL;
00548        size_t        dirs, cnt;
00549 
00550        pages <<= malloc_pageshift;
00551        if (!align)
00552               result = MMAP(pages + malloc_guard);
00553        else {
00554               result = MMAP_A(pages + malloc_guard, g_alignment);
00555        }
00556        if (result == MAP_FAILED) {
00557 #ifdef MALLOC_EXTRA_SANITY
00558               wrtwarning("(ES): map_pages fails");
00559 #endif /* MALLOC_EXTRA_SANITY */
00560               errno = ENOMEM;
00561               return (NULL);
00562        }
00563        index = ptr2index(result);
00564        tail = result + pages + malloc_guard;
00565        lindex = ptr2index(tail) - 1;
00566        if (malloc_guard)
00567               mprotect(result + pages, malloc_guard, PROT_NONE);
00568 
00569        pidx = PI_IDX(index);
00570        lidx = PI_IDX(lindex);
00571 
00572        if (tail > malloc_brk) {
00573               malloc_brk = tail;
00574               last_index = lindex;
00575        }
00576 
00577        dirs = lidx - pidx;
00578 
00579        /* Insert directory pages, if needed. */
00580        if (pdir_lookup(index, &pi) != 0)
00581               dirs++;
00582 
00583        if (dirs > 0) {
00584               pdregion = MMAP(malloc_pagesize * dirs);
00585               if (pdregion == MAP_FAILED) {
00586                      munmap(result, tail - result);
00587 #ifdef MALLOC_EXTRA_SANITY
00588               wrtwarning("(ES): map_pages fails");
00589 #endif
00590                      errno = ENOMEM;
00591                      return (NULL);
00592               }
00593        }
00594 
00595        cnt = 0;
00596        for (idx = pidx, spi = pi; idx <= lidx; idx++) {
00597               if (pi == NULL || PD_IDX(pi->dirnum) != idx) {
00598                      pd = (struct pginfo **)((char *)pdregion +
00599                          cnt * malloc_pagesize);
00600                      cnt++;
00601                      memset(pd, 0, malloc_pagesize);
00602                      pi = (struct pdinfo *) ((caddr_t) pd + pdi_off);
00603                      pi->base = pd;
00604                      pi->prev = spi;
00605                      pi->next = spi->next;
00606                      pi->dirnum = idx * (malloc_pagesize /
00607                          sizeof(struct pginfo *));
00608 
00609                      if (spi->next != NULL)
00610                             spi->next->prev = pi;
00611                      spi->next = pi;
00612               }
00613               if (idx > pidx && idx < lidx) {
00614                      pi->dirnum += pdi_mod;
00615               } else if (idx == pidx) {
00616                      if (pidx == lidx) {
00617                             pi->dirnum += (u_long)(tail - result) >>
00618                                 malloc_pageshift;
00619                      } else {
00620                             pi->dirnum += pdi_mod - PI_OFF(index);
00621                      }
00622               } else {
00623                      pi->dirnum += PI_OFF(ptr2index(tail - 1)) + 1;
00624               }
00625 #ifdef MALLOC_EXTRA_SANITY
00626               if (PD_OFF(pi->dirnum) > pdi_mod || PD_IDX(pi->dirnum) > idx) {
00627                      wrterror("(ES): pages directory overflow");
00628                      errno = EFAULT;
00629                      return (NULL);
00630               }
00631 #endif /* MALLOC_EXTRA_SANITY */
00632               if (idx == pidx && pi != last_dir) {
00633                      prev_dir = last_dir;
00634                      last_dir = pi;
00635               }
00636               spi = pi;
00637               pi = spi->next;
00638        }
00639 #ifdef MALLOC_EXTRA_SANITY
00640        if (cnt > dirs)
00641               wrtwarning("(ES): cnt > dirs");
00642 #endif /* MALLOC_EXTRA_SANITY */
00643        if (cnt < dirs)
00644               munmap((char *)pdregion + cnt * malloc_pagesize,
00645                   (dirs - cnt) * malloc_pagesize);
00646 
00647        return (result);
00648 }
00649 
00650 /*
00651  * Initialize the world
00652  */
00653 static void
00654 malloc_init(void)
00655 {
00656        char          *p, b[64];
00657        int           i, j, save_errno = errno;
00658 
00659        _MALLOC_LOCK_INIT();
00660 
00661 #ifdef MALLOC_EXTRA_SANITY
00662        malloc_junk = 1;
00663 #endif /* MALLOC_EXTRA_SANITY */
00664 
00665        for (i = 0; i < 3; i++) {
00666               switch (i) {
00667               case 0:
00668                      j = readlink("/etc/malloc.conf", b, sizeof b - 1);
00669                      if (j <= 0)
00670                             continue;
00671                      b[j] = '\0';
00672                      p = b;
00673                      break;
00674               case 1:
00675                      if (issetugid() == 0)
00676                             p = getenv("MALLOC_OPTIONS");
00677                      else
00678                             continue;
00679                      break;
00680               case 2:
00681                      p = malloc_options;
00682                      break;
00683               default:
00684                      p = NULL;
00685               }
00686 
00687               for (; p != NULL && *p != '\0'; p++) {
00688                      switch (*p) {
00689                      case '>':
00690                             malloc_cache <<= 1;
00691                             break;
00692                      case '<':
00693                             malloc_cache >>= 1;
00694                             break;
00695                      case 'a':
00696                             malloc_abort = 0;
00697                             break;
00698                      case 'A':
00699                             malloc_abort = 1;
00700                             break;
00701 #ifdef MALLOC_STATS
00702                      case 'd':
00703                             malloc_stats = 0;
00704                             break;
00705                      case 'D':
00706                             malloc_stats = 1;
00707                             break;
00708 #endif /* MALLOC_STATS */
00709                      case 'f':
00710                             malloc_freeprot = 0;
00711                             break;
00712                      case 'F':
00713                             malloc_freeprot = 1;
00714                             break;
00715                      case 'g':
00716                             malloc_guard = 0;
00717                             break;
00718                      case 'G':
00719                             malloc_guard = malloc_pagesize;
00720                             break;
00721                      case 'h':
00722                             malloc_hint = 0;
00723                             break;
00724                      case 'H':
00725                             malloc_hint = 1;
00726                             break;
00727                      case 'j':
00728                             malloc_junk = 0;
00729                             break;
00730                      case 'J':
00731                             malloc_junk = 1;
00732                             break;
00733                      case 'n':
00734                             malloc_silent = 0;
00735                             break;
00736                      case 'N':
00737                             malloc_silent = 1;
00738                             break;
00739                      case 'p':
00740                             malloc_ptrguard = 0;
00741                             break;
00742                      case 'P':
00743                             malloc_ptrguard = 1;
00744                             break;
00745                      case 'r':
00746                             malloc_realloc = 0;
00747                             break;
00748                      case 'R':
00749                             malloc_realloc = 1;
00750                             break;
00751 #ifdef __FreeBSD__
00752                      case 'u':
00753                             malloc_utrace = 0;
00754                             break;
00755                      case 'U':
00756                             malloc_utrace = 1;
00757                             break;
00758 #endif /* __FreeBSD__ */
00759                      case 'x':
00760                             malloc_xmalloc = 0;
00761                             break;
00762                      case 'X':
00763                             malloc_xmalloc = 1;
00764                             break;
00765                      case 'z':
00766                             malloc_zero = 0;
00767                             break;
00768                      case 'Z':
00769                             malloc_zero = 1;
00770                             break;
00771                      default:
00772                             j = malloc_abort;
00773                             malloc_abort = 0;
00774                             wrtwarning("unknown char in MALLOC_OPTIONS");
00775                             malloc_abort = j;
00776                             break;
00777                      }
00778               }
00779        }
00780 
00781        UTRACE(0, 0, 0);
00782 
00783        /*
00784         * We want junk in the entire allocation, and zero only in the part
00785         * the user asked for.
00786         */
00787        if (malloc_zero)
00788               malloc_junk = 1;
00789 
00790 #ifdef MALLOC_STATS
00791        if (malloc_stats && (atexit(malloc_exit) == -1))
00792               wrtwarning("atexit(2) failed."
00793                   "  Will not be able to dump malloc stats on exit");
00794 #endif /* MALLOC_STATS */
00795 
00796        if (malloc_pagesize != getpagesize()) {
00797               wrterror("malloc() replacement compiled with a different "
00798                       "page size from what we're running with.  Failing.");
00799               errno = ENOMEM;
00800               return;
00801        }
00802 
00803        /* Allocate one page for the page directory. */
00804        page_dir = (struct pginfo **)MMAP(malloc_pagesize);
00805 
00806        if (page_dir == MAP_FAILED) {
00807               wrterror("mmap(2) failed, check limits");
00808               errno = ENOMEM;
00809               return;
00810        }
00811        pdi_off = (malloc_pagesize - sizeof(struct pdinfo)) & ~(malloc_minsize - 1);
00812        pdi_mod = pdi_off / sizeof(struct pginfo *);
00813 
00814        last_dir = (struct pdinfo *) ((caddr_t) page_dir + pdi_off);
00815        last_dir->base = page_dir;
00816        last_dir->prev = last_dir->next = NULL;
00817        last_dir->dirnum = malloc_pageshift;
00818 
00819        /* Been here, done that. */
00820        malloc_started++;
00821 
00822        /* Recalculate the cache size in bytes, and make sure it's nonzero. */
00823        if (!malloc_cache)
00824               malloc_cache++;
00825        malloc_cache <<= malloc_pageshift;
00826        errno = save_errno;
00827 }
00828 
00829 /*
00830  * Allocate a number of complete pages
00831  */
00832 static void *
00833 malloc_pages(size_t size)
00834 {
00835        void          *p, *delay_free = NULL, *tp;
00836        size_t        i;
00837        struct pginfo **pd;
00838        struct pdinfo *pi;
00839        u_long        pidx, index;
00840        struct pgfree *pf;
00841 
00842        size = pageround(size) + malloc_guard;
00843 
00844        p = NULL;
00845        /* Look for free pages before asking for more */
00846        if (!align)
00847        for (pf = free_list.next; pf; pf = pf->next) {
00848 
00849 #ifdef MALLOC_EXTRA_SANITY
00850               if (pf->size & malloc_pagemask) {
00851                      wrterror("(ES): junk length entry on free_list");
00852                      errno = EFAULT;
00853                      return (NULL);
00854               }
00855               if (!pf->size) {
00856                      wrterror("(ES): zero length entry on free_list");
00857                      errno = EFAULT;
00858                      return (NULL);
00859               }
00860               if (pf->page > (pf->page + pf->size)) {
00861                      wrterror("(ES): sick entry on free_list");
00862                      errno = EFAULT;
00863                      return (NULL);
00864               }
00865               if ((pi = pf->pdir) == NULL) {
00866                      wrterror("(ES): invalid page directory on free-list");
00867                      errno = EFAULT;
00868                      return (NULL);
00869               }
00870               if ((pidx = PI_IDX(ptr2index(pf->page))) != PD_IDX(pi->dirnum)) {
00871                      wrterror("(ES): directory index mismatch on free-list");
00872                      errno = EFAULT;
00873                      return (NULL);
00874               }
00875               pd = pi->base;
00876               if (pd[PI_OFF(ptr2index(pf->page))] != MALLOC_FREE) {
00877                      wrterror("(ES): non-free first page on free-list");
00878                      errno = EFAULT;
00879                      return (NULL);
00880               }
00881               pidx = PI_IDX(ptr2index((pf->page) + (pf->size)) - 1);
00882               for (pi = pf->pdir; pi != NULL && PD_IDX(pi->dirnum) < pidx;
00883                   pi = pi->next)
00884                      ;
00885               if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
00886                      wrterror("(ES): last page not referenced in page directory");
00887                      errno = EFAULT;
00888                      return (NULL);
00889               }
00890               pd = pi->base;
00891               if (pd[PI_OFF(ptr2index((pf->page) + (pf->size)) - 1)] != MALLOC_FREE) {
00892                      wrterror("(ES): non-free last page on free-list");
00893                      errno = EFAULT;
00894                      return (NULL);
00895               }
00896 #endif /* MALLOC_EXTRA_SANITY */
00897 
00898               if (pf->size < size)
00899                      continue;
00900 
00901               if (pf->size == size) {
00902                      p = pf->page;
00903                      pi = pf->pdir;
00904                      if (pf->next != NULL)
00905                             pf->next->prev = pf->prev;
00906                      pf->prev->next = pf->next;
00907                      delay_free = pf;
00908                      break;
00909               }
00910               p = pf->page;
00911               pf->page = (char *) pf->page + size;
00912               pf->size -= size;
00913               pidx = PI_IDX(ptr2index(pf->page));
00914               for (pi = pf->pdir; pi != NULL && PD_IDX(pi->dirnum) < pidx;
00915                   pi = pi->next)
00916                      ;
00917               if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
00918                      wrterror("(ES): hole in directories");
00919                      errno = EFAULT;
00920                      return (NULL);
00921               }
00922               tp = pf->pdir;
00923               pf->pdir = pi;
00924               pi = tp;
00925               break;
00926        }
00927 
00928        size -= malloc_guard;
00929 
00930 #ifdef MALLOC_EXTRA_SANITY
00931        if (p != NULL && pi != NULL) {
00932               pidx = PD_IDX(pi->dirnum);
00933               pd = pi->base;
00934        }
00935        if (p != NULL && pd[PI_OFF(ptr2index(p))] != MALLOC_FREE) {
00936               wrterror("(ES): allocated non-free page on free-list");
00937               errno = EFAULT;
00938               return (NULL);
00939        }
00940 #endif /* MALLOC_EXTRA_SANITY */
00941 
00942        if (p != NULL && (malloc_guard || malloc_freeprot))
00943               mprotect(p, size, PROT_READ | PROT_WRITE);
00944 
00945        size >>= malloc_pageshift;
00946 
00947        /* Map new pages */
00948        if (p == NULL)
00949               p = map_pages(size);
00950 
00951        if (p != NULL) {
00952               index = ptr2index(p);
00953               pidx = PI_IDX(index);
00954               pdir_lookup(index, &pi);
00955 #ifdef MALLOC_EXTRA_SANITY
00956               if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
00957                      wrterror("(ES): mapped pages not found in directory");
00958                      errno = EFAULT;
00959                      return (NULL);
00960               }
00961 #endif /* MALLOC_EXTRA_SANITY */
00962               if (pi != last_dir) {
00963                      prev_dir = last_dir;
00964                      last_dir = pi;
00965               }
00966               pd = pi->base;
00967               pd[PI_OFF(index)] = MALLOC_FIRST;
00968 
00969               for (i = 1; i < size; i++) {
00970                      if (!PI_OFF(index + i)) {
00971                             pidx++;
00972                             pi = pi->next;
00973 #ifdef MALLOC_EXTRA_SANITY
00974                             if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
00975                                    wrterror("(ES): hole in mapped pages directory");
00976                                    errno = EFAULT;
00977                                    return (NULL);
00978                             }
00979 #endif /* MALLOC_EXTRA_SANITY */
00980                             pd = pi->base;
00981                      }
00982                      pd[PI_OFF(index + i)] = MALLOC_FOLLOW;
00983               }
00984               if (malloc_guard) {
00985                      if (!PI_OFF(index + i)) {
00986                             pidx++;
00987                             pi = pi->next;
00988 #ifdef MALLOC_EXTRA_SANITY
00989                             if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
00990                                    wrterror("(ES): hole in mapped pages directory");
00991                                    errno = EFAULT;
00992                                    return (NULL);
00993                             }
00994 #endif /* MALLOC_EXTRA_SANITY */
00995                             pd = pi->base;
00996                      }
00997                      pd[PI_OFF(index + i)] = MALLOC_FIRST;
00998               }
00999 
01000               malloc_used += size << malloc_pageshift;
01001               malloc_guarded += malloc_guard;
01002 
01003               if (malloc_junk)
01004                      memset(p, SOME_JUNK, size << malloc_pageshift);
01005        }
01006        if (delay_free) {
01007               if (px == NULL)
01008                      px = delay_free;
01009               else
01010                      ifree(delay_free);
01011        }
01012        return (p);
01013 }
01014 
01015 /*
01016  * Allocate a page of fragments
01017  */
01018 
01019 static __inline__ int
01020 malloc_make_chunks(int bits)
01021 {
01022        struct pginfo *bp, **pd;
01023        struct pdinfo *pi;
01024 #ifdef MALLOC_EXTRA_SANITY
01025        u_long        pidx;
01026 #endif /* MALLOC_EXTRA_SANITY */
01027        void          *pp;
01028        long          i, k;
01029        size_t        l;
01030 
01031        /* Allocate a new bucket */
01032        pp = malloc_pages((size_t) malloc_pagesize);
01033        if (pp == NULL)
01034               return (0);
01035 
01036        /* Find length of admin structure */
01037        l = sizeof *bp - sizeof(u_long);
01038        l += sizeof(u_long) *
01039            (((malloc_pagesize >> bits) + MALLOC_BITS - 1) / MALLOC_BITS);
01040 
01041        /* Don't waste more than two chunks on this */
01042 
01043        /*
01044         * If we are to allocate a memory protected page for the malloc(0)
01045         * case (when bits=0), it must be from a different page than the
01046         * pginfo page.
01047         * --> Treat it like the big chunk alloc, get a second data page.
01048         */
01049        if (bits != 0 && (1UL << (bits)) <= l + l) {
01050               bp = (struct pginfo *) pp;
01051        } else {
01052               bp = (struct pginfo *) imalloc(l);
01053               if (bp == NULL) {
01054                      ifree(pp);
01055                      return (0);
01056               }
01057        }
01058 
01059        /* memory protect the page allocated in the malloc(0) case */
01060        if (bits == 0) {
01061               bp->size = 0;
01062               bp->shift = 1;
01063               i = malloc_minsize - 1;
01064               while (i >>= 1)
01065                      bp->shift++;
01066               bp->total = bp->free = malloc_pagesize >> bp->shift;
01067               bp->page = pp;
01068 
01069               k = mprotect(pp, malloc_pagesize, PROT_NONE);
01070               if (k < 0) {
01071                      ifree(pp);
01072                      ifree(bp);
01073                      return (0);
01074               }
01075        } else {
01076               bp->size = (1UL << bits);
01077               bp->shift = bits;
01078               bp->total = bp->free = malloc_pagesize >> bits;
01079               bp->page = pp;
01080        }
01081 
01082        /* set all valid bits in the bitmap */
01083        k = bp->total;
01084        i = 0;
01085 
01086        /* Do a bunch at a time */
01087        for (; (k - i) >= MALLOC_BITS; i += MALLOC_BITS)
01088               bp->bits[i / MALLOC_BITS] = ~0UL;
01089 
01090        for (; i < k; i++)
01091               bp->bits[i / MALLOC_BITS] |= 1UL << (i % MALLOC_BITS);
01092 
01093        k = (long)l;
01094        if (bp == bp->page) {
01095               /* Mark the ones we stole for ourselves */
01096               for (i = 0; k > 0; i++) {
01097                      bp->bits[i / MALLOC_BITS] &= ~(1UL << (i % MALLOC_BITS));
01098                      bp->free--;
01099                      bp->total--;
01100                      k -= (1 << bits);
01101               }
01102        }
01103        /* MALLOC_LOCK */
01104 
01105        pdir_lookup(ptr2index(pp), &pi);
01106 #ifdef MALLOC_EXTRA_SANITY
01107        pidx = PI_IDX(ptr2index(pp));
01108        if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
01109               wrterror("(ES): mapped pages not found in directory");
01110               errno = EFAULT;
01111               return (0);
01112        }
01113 #endif /* MALLOC_EXTRA_SANITY */
01114        if (pi != last_dir) {
01115               prev_dir = last_dir;
01116               last_dir = pi;
01117        }
01118        pd = pi->base;
01119        pd[PI_OFF(ptr2index(pp))] = bp;
01120 
01121        bp->next = page_dir[bits];
01122        page_dir[bits] = bp;
01123 
01124        /* MALLOC_UNLOCK */
01125        return (1);
01126 }
01127 
01128 /*
01129  * Allocate a fragment
01130  */
01131 static void *
01132 malloc_bytes(size_t size)
01133 {
01134        int           i, j;
01135        size_t        k;
01136        u_long        u, *lp;
01137        struct pginfo *bp;
01138 
01139        /* Don't bother with anything less than this */
01140        /* unless we have a malloc(0) requests */
01141        if (size != 0 && size < malloc_minsize)
01142               size = malloc_minsize;
01143 
01144        /* Find the right bucket */
01145        if (size == 0)
01146               j = 0;
01147        else {
01148               j = 1;
01149               i = size - 1;
01150               while (i >>= 1)
01151                      j++;
01152        }
01153 
01154        /* If it's empty, make a page more of that size chunks */
01155        if (page_dir[j] == NULL && !malloc_make_chunks(j))
01156               return (NULL);
01157 
01158        bp = page_dir[j];
01159 
01160        /* Find first word of bitmap which isn't empty */
01161        for (lp = bp->bits; !*lp; lp++);
01162 
01163        /* Find that bit, and tweak it */
01164        u = 1;
01165        k = 0;
01166        while (!(*lp & u)) {
01167               u += u;
01168               k++;
01169        }
01170 
01171        if (malloc_guard) {
01172               /* Walk to a random position. */
01173 //            i = arc4random() % bp->free;
01174               i = rand() % bp->free;
01175               while (i > 0) {
01176                      u += u;
01177                      k++;
01178                      if (k >= MALLOC_BITS) {
01179                             lp++;
01180                             u = 1;
01181                             k = 0;
01182                      }
01183 #ifdef MALLOC_EXTRA_SANITY
01184                      if (lp - bp->bits > (bp->total - 1) / MALLOC_BITS) {
01185                             wrterror("chunk overflow");
01186                             errno = EFAULT;
01187                             return (NULL);
01188                      }
01189 #endif /* MALLOC_EXTRA_SANITY */
01190                      if (*lp & u)
01191                             i--;
01192               }
01193        }
01194        *lp ^= u;
01195 
01196        /* If there are no more free, remove from free-list */
01197        if (!--bp->free) {
01198               page_dir[j] = bp->next;
01199               bp->next = NULL;
01200        }
01201        /* Adjust to the real offset of that chunk */
01202        k += (lp - bp->bits) * MALLOC_BITS;
01203        k <<= bp->shift;
01204 
01205        if (malloc_junk && bp->size != 0)
01206               memset((char *)bp->page + k, SOME_JUNK, (size_t)bp->size);
01207 
01208        return ((u_char *) bp->page + k);
01209 }
01210 
01211 /*
01212  * Magic so that malloc(sizeof(ptr)) is near the end of the page.
01213  */
01214 #define       PTR_GAP              (malloc_pagesize - sizeof(void *))
01215 #define       PTR_SIZE      (sizeof(void *))
01216 #define       PTR_ALIGNED(p)       (((unsigned long)p & malloc_pagemask) == PTR_GAP)
01217 
01218 /*
01219  * Allocate a piece of memory
01220  */
01221 static void *
01222 imalloc(size_t size)
01223 {
01224        void          *result;
01225        int           ptralloc = 0;
01226 
01227        if (!malloc_started)
01228               malloc_init();
01229 
01230        if (suicide)
01231               abort();
01232 
01233        /* does not matter if malloc_bytes fails */
01234        if (px == NULL)
01235               px = malloc_bytes(sizeof *px);
01236 
01237        if (malloc_ptrguard && size == PTR_SIZE) {
01238               ptralloc = 1;
01239               size = malloc_pagesize;
01240        }
01241        if (size > SIZE_MAX - malloc_pagesize) { /* Check for overflow */
01242               result = NULL;
01243               errno = ENOMEM;
01244        } else if (size <= malloc_maxsize)
01245               result = malloc_bytes(size);
01246        else
01247               result = malloc_pages(size);
01248 
01249        if (malloc_abort == 1 && result == NULL)
01250               wrterror("allocation failed");
01251 
01252        if (malloc_zero && result != NULL)
01253               memset(result, 0, size);
01254 
01255        if (result && ptralloc)
01256               return ((char *) result + PTR_GAP);
01257        return (result);
01258 }
01259 
01260 /*
01261  * Change the size of an allocation.
01262  */
01263 static void *
01264 irealloc(void *ptr, size_t size)
01265 {
01266        void          *p;
01267        size_t        osize;
01268        u_long        index, i;
01269        struct pginfo **mp;
01270        struct pginfo **pd;
01271        struct pdinfo *pi;
01272 #ifdef MALLOC_EXTRA_SANITY
01273        u_long        pidx;
01274 #endif /* MALLOC_EXTRA_SANITY */
01275 
01276        if (suicide)
01277               abort();
01278 
01279        if (!malloc_started) {
01280               wrtwarning("malloc() has never been called");
01281               return (NULL);
01282        }
01283        if (malloc_ptrguard && PTR_ALIGNED(ptr)) {
01284               if (size <= PTR_SIZE)
01285                      return (ptr);
01286 
01287               p = imalloc(size);
01288               if (p)
01289                      memcpy(p, ptr, PTR_SIZE);
01290               ifree(ptr);
01291               return (p);
01292        }
01293        index = ptr2index(ptr);
01294 
01295        if (index < malloc_pageshift) {
01296               wrtwarning("junk pointer, too low to make sense");
01297               return (NULL);
01298        }
01299        if (index > last_index) {
01300               wrtwarning("junk pointer, too high to make sense");
01301               return (NULL);
01302        }
01303        pdir_lookup(index, &pi);
01304 #ifdef MALLOC_EXTRA_SANITY
01305        pidx = PI_IDX(index);
01306        if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
01307               wrterror("(ES): mapped pages not found in directory");
01308               errno = EFAULT;
01309               return (NULL);
01310        }
01311 #endif /* MALLOC_EXTRA_SANITY */
01312        if (pi != last_dir) {
01313               prev_dir = last_dir;
01314               last_dir = pi;
01315        }
01316        pd = pi->base;
01317        mp = &pd[PI_OFF(index)];
01318 
01319        if (*mp == MALLOC_FIRST) {  /* Page allocation */
01320 
01321               /* Check the pointer */
01322               if ((u_long) ptr & malloc_pagemask) {
01323                      wrtwarning("modified (page-) pointer");
01324                      return (NULL);
01325               }
01326               /* Find the size in bytes */
01327               i = index;
01328               if (!PI_OFF(++i)) {
01329                      pi = pi->next;
01330                      if (pi != NULL && PD_IDX(pi->dirnum) != PI_IDX(i))
01331                             pi = NULL;
01332                      if (pi != NULL)
01333                             pd = pi->base;
01334               }
01335               for (osize = malloc_pagesize;
01336                   pi != NULL && pd[PI_OFF(i)] == MALLOC_FOLLOW;) {
01337                      osize += malloc_pagesize;
01338                      if (!PI_OFF(++i)) {
01339                             pi = pi->next;
01340                             if (pi != NULL && PD_IDX(pi->dirnum) != PI_IDX(i))
01341                                    pi = NULL;
01342                             if (pi != NULL)
01343                                    pd = pi->base;
01344                      }
01345               }
01346 
01347               if (!malloc_realloc && size <= osize &&
01348                   size > osize - malloc_pagesize) {
01349                      if (malloc_junk)
01350                             memset((char *)ptr + size, SOME_JUNK, osize - size);
01351                      return (ptr); /* ..don't do anything else. */
01352               }
01353        } else if (*mp >= MALLOC_MAGIC) {  /* Chunk allocation */
01354 
01355               /* Check the pointer for sane values */
01356               if ((u_long) ptr & ((1UL << ((*mp)->shift)) - 1)) {
01357                      wrtwarning("modified (chunk-) pointer");
01358                      return (NULL);
01359               }
01360               /* Find the chunk index in the page */
01361               i = ((u_long) ptr & malloc_pagemask) >> (*mp)->shift;
01362 
01363               /* Verify that it isn't a free chunk already */
01364               if ((*mp)->bits[i / MALLOC_BITS] & (1UL << (i % MALLOC_BITS))) {
01365                      wrtwarning("chunk is already free");
01366                      return (NULL);
01367               }
01368               osize = (*mp)->size;
01369 
01370               if (!malloc_realloc && size <= osize &&
01371                   (size > osize / 2 || osize == malloc_minsize)) {
01372                      if (malloc_junk)
01373                             memset((char *) ptr + size, SOME_JUNK, osize - size);
01374                      return (ptr); /* ..don't do anything else. */
01375               }
01376        } else {
01377               wrtwarning("irealloc: pointer to wrong page");
01378               return (NULL);
01379        }
01380 
01381        p = imalloc(size);
01382 
01383        if (p != NULL) {
01384               /* copy the lesser of the two sizes, and free the old one */
01385               /* Don't move from/to 0 sized region !!! */
01386               if (osize != 0 && size != 0) {
01387                      if (osize < size)
01388                             memcpy(p, ptr, osize);
01389                      else
01390                             memcpy(p, ptr, size);
01391               }
01392               ifree(ptr);
01393        }
01394        return (p);
01395 }
01396 
01397 /*
01398  * Free a sequence of pages
01399  */
01400 static __inline__ void
01401 free_pages(void *ptr, u_long index, struct pginfo * info)
01402 {
01403        u_long        i, pidx, lidx;
01404        size_t        l, cachesize = 0;
01405        struct pginfo **pd;
01406        struct pdinfo *pi, *spi;
01407        struct pgfree *pf, *pt = NULL;
01408        caddr_t              tail;
01409 
01410        if (info == MALLOC_FREE) {
01411               wrtwarning("page is already free");
01412               return;
01413        }
01414        if (info != MALLOC_FIRST) {
01415               wrtwarning("free_pages: pointer to wrong page");
01416               return;
01417        }
01418        if ((u_long) ptr & malloc_pagemask) {
01419               wrtwarning("modified (page-) pointer");
01420               return;
01421        }
01422        /* Count how many pages and mark them free at the same time */
01423        pidx = PI_IDX(index);
01424        pdir_lookup(index, &pi);
01425 #ifdef MALLOC_EXTRA_SANITY
01426        if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
01427               wrterror("(ES): mapped pages not found in directory");
01428               errno = EFAULT;
01429               return;
01430        }
01431 #endif /* MALLOC_EXTRA_SANITY */
01432 
01433        spi = pi;            /* Save page index for start of region. */
01434 
01435        pd = pi->base;
01436        pd[PI_OFF(index)] = MALLOC_FREE;
01437        i = 1;
01438        if (!PI_OFF(index + i)) {
01439               pi = pi->next;
01440               if (pi == NULL || PD_IDX(pi->dirnum) != PI_IDX(index + i))
01441                      pi = NULL;
01442               else
01443                      pd = pi->base;
01444        }
01445        while (pi != NULL && pd[PI_OFF(index + i)] == MALLOC_FOLLOW) {
01446               pd[PI_OFF(index + i)] = MALLOC_FREE;
01447               i++;
01448               if (!PI_OFF(index + i)) {
01449                      if ((pi = pi->next) == NULL ||
01450                          PD_IDX(pi->dirnum) != PI_IDX(index + i))
01451                             pi = NULL;
01452                      else
01453                             pd = pi->base;
01454               }
01455        }
01456 
01457        l = i << malloc_pageshift;
01458 
01459        if (malloc_junk)
01460               memset(ptr, SOME_JUNK, l);
01461 
01462        malloc_used -= l;
01463        malloc_guarded -= malloc_guard;
01464        if (malloc_guard) {
01465 #ifdef MALLOC_EXTRA_SANITY
01466               if (pi == NULL || PD_IDX(pi->dirnum) != PI_IDX(index + i)) {
01467                      wrterror("(ES): hole in mapped pages directory");
01468                      errno = EFAULT;
01469                      return;
01470               }
01471 #endif /* MALLOC_EXTRA_SANITY */
01472               pd[PI_OFF(index + i)] = MALLOC_FREE;
01473               l += malloc_guard;
01474        }
01475        tail = (caddr_t)ptr + l;
01476 
01477        if (malloc_hint)
01478               madvise(ptr, l, MADV_FREE);
01479 
01480        if (malloc_freeprot)
01481               mprotect(ptr, l, PROT_NONE);
01482 
01483        /* Add to free-list. */
01484        if (px == NULL && (px = malloc_bytes(sizeof *px)) == NULL)
01485                      goto not_return;
01486        px->page = ptr;
01487        px->pdir = spi;
01488        px->size = l;
01489 
01490        if (free_list.next == NULL) {
01491               /* Nothing on free list, put this at head. */
01492               px->next = NULL;
01493               px->prev = &free_list;
01494               free_list.next = px;
01495               pf = px;
01496               px = NULL;
01497        } else {
01498               /*
01499                * Find the right spot, leave pf pointing to the modified
01500                * entry.
01501                */
01502 
01503               /* Race ahead here, while calculating cache size. */
01504               for (pf = free_list.next;
01505                   (caddr_t)ptr > ((caddr_t)pf->page + pf->size)
01506                   && pf->next != NULL;
01507                   pf = pf->next)
01508                      cachesize += pf->size;
01509 
01510               /* Finish cache size calculation. */
01511               pt = pf;
01512               while (pt) {
01513                      cachesize += pt->size;
01514                      pt = pt->next;
01515               }
01516 
01517               if ((caddr_t)pf->page > tail) {
01518                      /* Insert before entry */
01519                      px->next = pf;
01520                      px->prev = pf->prev;
01521                      pf->prev = px;
01522                      px->prev->next = px;
01523                      pf = px;
01524                      px = NULL;
01525               } else if (((caddr_t)pf->page + pf->size) == ptr) {
01526                      /* Append to the previous entry. */
01527                      cachesize -= pf->size;
01528                      pf->size += l;
01529                      if (pf->next != NULL &&
01530                          pf->next->page == ((caddr_t)pf->page + pf->size)) {
01531                             /* And collapse the next too. */
01532                             pt = pf->next;
01533                             pf->size += pt->size;
01534                             pf->next = pt->next;
01535                             if (pf->next != NULL)
01536                                    pf->next->prev = pf;
01537                      }
01538               } else if (pf->page == tail) {
01539                      /* Prepend to entry. */
01540                      cachesize -= pf->size;
01541                      pf->size += l;
01542                      pf->page = ptr;
01543                      pf->pdir = spi;
01544               } else if (pf->next == NULL) {
01545                      /* Append at tail of chain. */
01546                      px->next = NULL;
01547                      px->prev = pf;
01548                      pf->next = px;
01549                      pf = px;
01550                      px = NULL;
01551               } else {
01552                      wrterror("freelist is destroyed");
01553                      errno = EFAULT;
01554                      return;
01555               }
01556        }
01557 
01558        if (pf->pdir != last_dir) {
01559               prev_dir = last_dir;
01560               last_dir = pf->pdir;
01561        }
01562 
01563        /* Return something to OS ? */
01564        if (pf->size > (malloc_cache - cachesize)) {
01565 
01566               /*
01567                * Keep the cache intact.  Notice that the '>' above guarantees that
01568                * the pf will always have at least one page afterwards.
01569                */
01570               if (munmap((char *) pf->page + (malloc_cache - cachesize),
01571                   pf->size - (malloc_cache - cachesize)) != 0)
01572                      goto not_return;
01573               tail = (caddr_t)pf->page + pf->size;
01574               lidx = ptr2index(tail) - 1;
01575               pf->size = malloc_cache - cachesize;
01576 
01577               index = ptr2index((caddr_t)pf->page + pf->size);
01578 
01579               pidx = PI_IDX(index);
01580               if (prev_dir != NULL && PD_IDX(prev_dir->dirnum) >= pidx)
01581                      prev_dir = NULL;     /* Will be wiped out below ! */
01582 
01583               for (pi = pf->pdir; pi != NULL && PD_IDX(pi->dirnum) < pidx;
01584                   pi = pi->next)
01585                      ;
01586 
01587               spi = pi;
01588               if (pi != NULL && PD_IDX(pi->dirnum) == pidx) {
01589                      pd = pi->base;
01590 
01591                      for (i = index; i <= lidx;) {
01592                             if (pd[PI_OFF(i)] != MALLOC_NOT_MINE) {
01593                                    pd[PI_OFF(i)] = MALLOC_NOT_MINE;
01594 #ifdef MALLOC_EXTRA_SANITY
01595                                    if (!PD_OFF(pi->dirnum)) {
01596                                           wrterror("(ES): pages directory underflow");
01597                                           errno = EFAULT;
01598                                           return;
01599                                    }
01600 #endif /* MALLOC_EXTRA_SANITY */
01601                                    pi->dirnum--;
01602                             }
01603 #ifdef MALLOC_EXTRA_SANITY
01604                             else
01605                                    wrtwarning("(ES): page already unmapped");
01606 #endif /* MALLOC_EXTRA_SANITY */
01607                             i++;
01608                             if (!PI_OFF(i)) {
01609                                    /*
01610                                     * If no page in that dir, free
01611                                     * directory page.
01612                                     */
01613                                    if (!PD_OFF(pi->dirnum)) {
01614                                           /* Remove from list. */
01615                                           if (spi == pi)
01616                                                  spi = pi->prev;
01617                                           if (pi->prev != NULL)
01618                                                  pi->prev->next = pi->next;
01619                                           if (pi->next != NULL)
01620                                                  pi->next->prev = pi->prev;
01621                                           pi = pi->next;
01622                                           munmap(pd, malloc_pagesize);
01623                                    } else
01624                                           pi = pi->next;
01625                                    if (pi == NULL ||
01626                                        PD_IDX(pi->dirnum) != PI_IDX(i))
01627                                           break;
01628                                    pd = pi->base;
01629                             }
01630                      }
01631                      if (pi && !PD_OFF(pi->dirnum)) {
01632                             /* Resulting page dir is now empty. */
01633                             /* Remove from list. */
01634                             if (spi == pi)       /* Update spi only if first. */
01635                                    spi = pi->prev;
01636                             if (pi->prev != NULL)
01637                                    pi->prev->next = pi->next;
01638                             if (pi->next != NULL)
01639                                    pi->next->prev = pi->prev;
01640                             pi = pi->next;
01641                             munmap(pd, malloc_pagesize);
01642                      }
01643               }
01644               if (pi == NULL && malloc_brk == tail) {
01645                      /* Resize down the malloc upper boundary. */
01646                      last_index = index - 1;
01647                      malloc_brk = index2ptr(index);
01648               }
01649 
01650               /* XXX: We could realloc/shrink the pagedir here I guess. */
01651               if (pf->size == 0) { /* Remove from free-list as well. */
01652                      if (px)
01653                             ifree(px);
01654                      if ((px = pf->prev) != &free_list) {
01655                             if (pi == NULL && last_index == (index - 1)) {
01656                                    if (spi == NULL) {
01657                                           malloc_brk = NULL;
01658                                           i = 11;
01659                                    } else {
01660                                           pd = spi->base;
01661                                           if (PD_IDX(spi->dirnum) < pidx)
01662                                                  index =
01663                                                      ((PD_IDX(spi->dirnum) + 1) *
01664                                                      pdi_mod) - 1;
01665                                           for (pi = spi, i = index;
01666                                               pd[PI_OFF(i)] == MALLOC_NOT_MINE;
01667                                               i--)
01668 #ifdef MALLOC_EXTRA_SANITY
01669                                                  if (!PI_OFF(i)) {
01670                                                         pi = pi->prev;
01671                                                         if (pi == NULL || i == 0)
01672                                                                break;
01673                                                         pd = pi->base;
01674                                                         i = (PD_IDX(pi->dirnum) + 1) * pdi_mod;
01675                                                  }
01676 #else /* !MALLOC_EXTRA_SANITY */
01677                                           {
01678                                           }
01679 #endif /* MALLOC_EXTRA_SANITY */
01680                                           malloc_brk = index2ptr(i + 1);
01681                                    }
01682                                    last_index = i;
01683                             }
01684                             if ((px->next = pf->next) != NULL)
01685                                    px->next->prev = px;
01686                      } else {
01687                             if ((free_list.next = pf->next) != NULL)
01688                                    free_list.next->prev = &free_list;
01689                      }
01690                      px = pf;
01691                      last_dir = prev_dir;
01692                      prev_dir = NULL;
01693               }
01694        }
01695 not_return:
01696        if (pt != NULL)
01697               ifree(pt);
01698 }
01699 
01700 /*
01701  * Free a chunk, and possibly the page it's on, if the page becomes empty.
01702  */
01703 
01704 /* ARGSUSED */
01705 static __inline__ void
01706 free_bytes(void *ptr, u_long index, struct pginfo * info)
01707 {
01708        struct pginfo **mp, **pd;
01709        struct pdinfo *pi;
01710 #ifdef MALLOC_EXTRA_SANITY
01711        u_long        pidx;
01712 #endif /* MALLOC_EXTRA_SANITY */
01713        void          *vp;
01714        long          i;
01715        (void) index;
01716 
01717        /* Find the chunk number on the page */
01718        i = ((u_long) ptr & malloc_pagemask) >> info->shift;
01719 
01720        if ((u_long) ptr & ((1UL << (info->shift)) - 1)) {
01721               wrtwarning("modified (chunk-) pointer");
01722               return;
01723        }
01724        if (info->bits[i / MALLOC_BITS] & (1UL << (i % MALLOC_BITS))) {
01725               wrtwarning("chunk is already free");
01726               return;
01727        }
01728        if (malloc_junk && info->size != 0)
01729               memset(ptr, SOME_JUNK, (size_t)info->size);
01730 
01731        info->bits[i / MALLOC_BITS] |= 1UL << (i % MALLOC_BITS);
01732        info->free++;
01733 
01734        if (info->size != 0)
01735               mp = page_dir + info->shift;
01736        else
01737               mp = page_dir;
01738 
01739        if (info->free == 1) {
01740               /* Page became non-full */
01741 
01742               /* Insert in address order */
01743               while (*mp != NULL && (*mp)->next != NULL &&
01744                   (*mp)->next->page < info->page)
01745                      mp = &(*mp)->next;
01746               info->next = *mp;
01747               *mp = info;
01748               return;
01749        }
01750        if (info->free != info->total)
01751               return;
01752 
01753        /* Find & remove this page in the queue */
01754        while (*mp != info) {
01755               mp = &((*mp)->next);
01756 #ifdef MALLOC_EXTRA_SANITY
01757               if (!*mp) {
01758                      wrterror("(ES): Not on queue");
01759                      errno = EFAULT;
01760                      return;
01761               }
01762 #endif /* MALLOC_EXTRA_SANITY */
01763        }
01764        *mp = info->next;
01765 
01766        /* Free the page & the info structure if need be */
01767        pdir_lookup(ptr2index(info->page), &pi);
01768 #ifdef MALLOC_EXTRA_SANITY
01769        pidx = PI_IDX(ptr2index(info->page));
01770        if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
01771               wrterror("(ES): mapped pages not found in directory");
01772               errno = EFAULT;
01773               return;
01774        }
01775 #endif /* MALLOC_EXTRA_SANITY */
01776        if (pi != last_dir) {
01777               prev_dir = last_dir;
01778               last_dir = pi;
01779        }
01780        pd = pi->base;
01781        pd[PI_OFF(ptr2index(info->page))] = MALLOC_FIRST;
01782 
01783        /* If the page was mprotected, unprotect it before releasing it */
01784        if (info->size == 0)
01785               mprotect(info->page, malloc_pagesize, PROT_READ | PROT_WRITE);
01786 
01787        vp = info->page;     /* Order is important ! */
01788        if (vp != (void *) info)
01789               ifree(info);
01790        ifree(vp);
01791 }
01792 
01793 static void
01794 ifree(void *ptr)
01795 {
01796        struct pginfo *info, **pd;
01797        u_long        index;
01798 #ifdef MALLOC_EXTRA_SANITY
01799        u_long        pidx;
01800 #endif /* MALLOC_EXTRA_SANITY */
01801        struct pdinfo *pi;
01802 
01803        if (!malloc_started) {
01804               wrtwarning("malloc() has never been called");
01805               return;
01806        }
01807        /* If we're already sinking, don't make matters any worse. */
01808        if (suicide)
01809               return;
01810 
01811        if (malloc_ptrguard && PTR_ALIGNED(ptr))
01812               ptr = (char *) ptr - PTR_GAP;
01813 
01814        index = ptr2index(ptr);
01815 
01816        if (index < malloc_pageshift) {
01817               warnx("(%p)", ptr);
01818               wrtwarning("ifree: junk pointer, too low to make sense");
01819               return;
01820        }
01821        if (index > last_index) {
01822               warnx("(%p)", ptr);
01823               wrtwarning("ifree: junk pointer, too high to make sense");
01824               return;
01825        }
01826        pdir_lookup(index, &pi);
01827 #ifdef MALLOC_EXTRA_SANITY
01828        pidx = PI_IDX(index);
01829        if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
01830               wrterror("(ES): mapped pages not found in directory");
01831               errno = EFAULT;
01832               return;
01833        }
01834 #endif /* MALLOC_EXTRA_SANITY */
01835        if (pi != last_dir) {
01836               prev_dir = last_dir;
01837               last_dir = pi;
01838        }
01839        pd = pi->base;
01840        info = pd[PI_OFF(index)];
01841 
01842        if (info < MALLOC_MAGIC)
01843               free_pages(ptr, index, info);
01844        else
01845               free_bytes(ptr, index, info);
01846 
01847        /* does not matter if malloc_bytes fails */
01848        if (px == NULL)
01849               px = malloc_bytes(sizeof *px);
01850 
01851        return;
01852 }
01853 
01854 /*
01855  * Common function for handling recursion.  Only
01856  * print the error message once, to avoid making the problem
01857  * potentially worse.
01858  */
01859 static void
01860 malloc_recurse(void)
01861 {
01862        static int    noprint;
01863 
01864        if (noprint == 0) {
01865               noprint = 1;
01866               wrtwarning("recursive call");
01867        }
01868        malloc_active--;
01869        _MALLOC_UNLOCK();
01870        errno = EDEADLK;
01871 }
01872 
01873 /*
01874  * These are the public exported interface routines.
01875  */
01876 void *
01877 malloc(size_t size)
01878 {
01879        void          *r;
01880 
01881        if (!align)
01882        _MALLOC_LOCK();
01883        malloc_func = " in malloc():";
01884        if (malloc_active++) {
01885               malloc_recurse();
01886               return (NULL);
01887        }
01888        r = imalloc(size);
01889        UTRACE(0, size, r);
01890        malloc_active--;
01891        if (!align)
01892        _MALLOC_UNLOCK();
01893        if (malloc_xmalloc && r == NULL) {
01894               wrterror("out of memory");
01895               errno = ENOMEM;
01896        }
01897        return (r);
01898 }
01899 
01900 void
01901 free(void *ptr)
01902 {
01903        /* This is legal. XXX quick path */
01904        if (ptr == NULL)
01905               return;
01906 
01907        _MALLOC_LOCK();
01908        malloc_func = " in free():";
01909        if (malloc_active++) {
01910               malloc_recurse();
01911               return;
01912        }
01913        ifree(ptr);
01914        UTRACE(ptr, 0, 0);
01915        malloc_active--;
01916        _MALLOC_UNLOCK();
01917        return;
01918 }
01919 
01920 void *
01921 realloc(void *ptr, size_t size)
01922 {
01923        void          *r;
01924 
01925        _MALLOC_LOCK();
01926        malloc_func = " in realloc():";
01927        if (malloc_active++) {
01928               malloc_recurse();
01929               return (NULL);
01930        }
01931 
01932        if (ptr == NULL)
01933               r = imalloc(size);
01934        else
01935               r = irealloc(ptr, size);
01936 
01937        UTRACE(ptr, size, r);
01938        malloc_active--;
01939        _MALLOC_UNLOCK();
01940        if (malloc_xmalloc && r == NULL) {
01941               wrterror("out of memory");
01942               errno = ENOMEM;
01943        }
01944        return (r);
01945 }
01946 
01947 #ifndef SIZE_MAX
01948 //#if defined(__i386__)||defined(__arm__)||defined(__powerpc__)
01949 //#define SIZE_MAX 0xffffffff
01950 //#endif
01951 //#if defined(__x86_64__)
01952 //#define SIZE_MAX 0xffffffffffffffff
01953 //#endif
01954 #define SIZE_MAX SIZE_T_MAX
01955 #endif
01956 
01957 void *
01958 calloc(size_t num, size_t size)
01959 {
01960        void *p;
01961        
01962        if (num && SIZE_MAX / num < size) {
01963               fprintf(stderr,"OOOOPS");
01964               errno = ENOMEM;
01965               return NULL;
01966        }
01967        size *= num;
01968        p = malloc(size);
01969        if (p)
01970               memset(p, 0, size);
01971        return(p);
01972 }
01973 
01974 static int ispowerof2 (size_t a) {
01975        size_t b;
01976        for (b = 1ULL << (sizeof(size_t)*NBBY - 1); b > 1; b >>= 1)
01977          if (b == a)
01978               return 1;
01979        return 0;
01980 }
01981 
01982 int posix_memalign(void **memptr, size_t alignment, size_t size)
01983 {
01984        void *r;
01985        size_t max;
01986        if ((alignment < PTR_SIZE) || (alignment%PTR_SIZE != 0)) return EINVAL;
01987        if (!ispowerof2(alignment)) return EINVAL;
01988        if (alignment < malloc_minsize) alignment = malloc_minsize;
01989        max = alignment > size ? alignment : size;
01990        if (alignment <= malloc_pagesize)
01991               r = malloc(max);
01992        else {
01993               _MALLOC_LOCK();
01994               align = 1;
01995               g_alignment = alignment;
01996               r = malloc(size);
01997               align=0;
01998               _MALLOC_UNLOCK();
01999        }
02000        *memptr = r;
02001        if (!r) return ENOMEM;
02002        return 0;
02003 }
02004 
02005 void *memalign(size_t boundary, size_t size)
02006 {
02007        void *r;
02008        posix_memalign(&r, boundary, size);
02009        return r;
02010 }
02011 
02012 void *valloc(size_t size)
02013 {
02014        void *r;
02015        posix_memalign(&r, malloc_pagesize, size);
02016        return r;
02017 }
02018 
02019 size_t malloc_good_size(size_t size)
02020 {
02021        if (size == 0) {
02022               return 1;
02023        } else if (size <= malloc_maxsize) {
02024               int i, j;
02025               /* round up to the nearest power of 2, with same approach
02026                * as malloc_bytes() uses. */
02027               j = 1;
02028               i = size - 1;
02029               while (i >>= 1)
02030                      j++;
02031               return ((size_t)1) << j;
02032        } else {
02033               return pageround(size);
02034        }
02035 }