home *** CD-ROM | disk | FTP | other *** search
/ Tools / WinSN5.0Ver.iso / NETSCAP.50 / WIN1998.ZIP / ns / nsprpub / pr / src / malloc / prmalloc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-04-08  |  26.6 KB  |  1,157 lines
  1. /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
  2. /*
  3.  * The contents of this file are subject to the Netscape Public License
  4.  * Version 1.0 (the "NPL"); you may not use this file except in
  5.  * compliance with the NPL.  You may obtain a copy of the NPL at
  6.  * http://www.mozilla.org/NPL/
  7.  * 
  8.  * Software distributed under the NPL is distributed on an "AS IS" basis,
  9.  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the NPL
  10.  * for the specific language governing rights and limitations under the
  11.  * NPL.
  12.  * 
  13.  * The Initial Developer of this code under the NPL is Netscape
  14.  * Communications Corporation.  Portions created by Netscape are
  15.  * Copyright (C) 1998 Netscape Communications Corporation.  All Rights
  16.  * Reserved.
  17.  */
  18.  
  19. #include "primpl.h"
  20.  
  21. /*
  22. ** We override malloc etc. on any platform which has preemption +
  23. ** nspr20 user level threads.  When we're debugging, we can make our
  24. ** version of malloc fail occasionally.
  25. */
  26. #ifdef _PR_OVERRIDE_MALLOC
  27.  
  28. /*
  29. ** Thread safe version of malloc, calloc, realloc, free
  30. */
  31. #include <stdarg.h>
  32.  
  33. #ifdef DEBUG
  34. #define SANITY
  35. #define EXTRA_SANITY
  36. #else
  37. #undef SANITY
  38. #undef EXTRA_SANITY
  39. #endif
  40.  
  41. /* Forward decls */
  42. void *_PR_UnlockedMalloc(size_t size);
  43. void _PR_UnlockedFree(void *ptr);
  44. void *_PR_UnlockedRealloc(void *ptr, size_t size);
  45. void *_PR_UnlockedCalloc(size_t n, size_t elsize);
  46.  
  47. /************************************************************************/
  48.  
  49. /*
  50.  * ----------------------------------------------------------------------------
  51.  * "THE BEER-WARE LICENSE" (Revision 42):
  52.  * <phk@FreeBSD.ORG> wrote this file.  As long as you retain this notice you
  53.  * can do whatever you want with this stuff. If we meet some day, and you think
  54.  * this stuff is worth it, you can buy me a beer in return.   Poul-Henning Kamp
  55.  * ----------------------------------------------------------------------------
  56.  *
  57.  */
  58.  
  59. /*
  60.  * Defining SANITY will enable some checks which will tell you if the users
  61.  * program did botch something
  62.  */
  63.  
  64. /*
  65.  * Defining EXTRA_SANITY will enable some checks which are mostly related
  66.  * to internal conditions in malloc.c
  67.  */
  68.  
  69. /*
  70.  * Very verbose progress on stdout...
  71.  */
  72. #if 0
  73. #  define TRACE(foo)    printf  foo
  74. static int malloc_event;
  75. #else
  76. #  define TRACE(foo)    
  77. #endif
  78.  
  79. /* XXX Pick a number, any number */
  80. #   define malloc_pagesize        4096UL
  81. #   define malloc_pageshift        12UL
  82.  
  83. #ifdef XP_UNIX
  84. #include <stdio.h>
  85. #include <stdlib.h>
  86. #include <unistd.h>
  87. #include <memory.h>
  88. #include <string.h>
  89. #include <errno.h>
  90. #include <sys/types.h>
  91. #include <sys/mman.h>
  92. #endif
  93.  
  94. /*
  95.  * This structure describes a page's worth of chunks.
  96.  */
  97.  
  98. struct pginfo {
  99.     struct pginfo    *next;    /* next on the free list */
  100.     char        *page;    /* Pointer to the page */
  101.     u_short        size;    /* size of this page's chunks */
  102.     u_short        shift;    /* How far to shift for this size chunks */
  103.     u_short        free;    /* How many free chunks */
  104.     u_short        total;    /* How many chunk */
  105.     u_long        bits[1]; /* Which chunks are free */
  106. };
  107.  
  108. struct pgfree {
  109.     struct pgfree    *next;    /* next run of free pages */
  110.     struct pgfree    *prev;    /* prev run of free pages */
  111.     char        *page;    /* pointer to free pages */
  112.     char        *end;    /* pointer to end of free pages */
  113.     u_long        size;    /* number of bytes free */
  114. };
  115.  
  116. /*
  117.  * How many bits per u_long in the bitmap.
  118.  * Change only if not 8 bits/byte
  119.  */
  120. #define    MALLOC_BITS    (8*sizeof(u_long))
  121.  
  122. /*
  123.  * Magic values to put in the page_directory
  124.  */
  125. #define MALLOC_NOT_MINE    ((struct pginfo*) 0)
  126. #define MALLOC_FREE     ((struct pginfo*) 1)
  127. #define MALLOC_FIRST    ((struct pginfo*) 2)
  128. #define MALLOC_FOLLOW    ((struct pginfo*) 3)
  129. #define MALLOC_MAGIC    ((struct pginfo*) 4)
  130.  
  131. /*
  132.  * Set to one when malloc_init has been called
  133.  */
  134. static    unsigned    initialized;
  135.  
  136. /*
  137.  * The size of a page.
  138.  * Must be a integral multiplum of the granularity of mmap(2).
  139.  * Your toes will curl if it isn't a power of two
  140.  */
  141. #define malloc_pagemask    ((malloc_pagesize)-1)
  142.  
  143. /*
  144.  * The size of the largest chunk.
  145.  * Half a page.
  146.  */
  147. #define malloc_maxsize    ((malloc_pagesize)>>1)
  148.  
  149. /*
  150.  * malloc_pagesize == 1 << malloc_pageshift
  151.  */
  152. #ifndef malloc_pageshift
  153. static    unsigned    malloc_pageshift;
  154. #endif /* malloc_pageshift */
  155.  
  156. /*
  157.  * The smallest allocation we bother about.
  158.  * Must be power of two
  159.  */
  160. #ifndef malloc_minsize
  161. static    unsigned  malloc_minsize;
  162. #endif /* malloc_minsize */
  163.  
  164. /*
  165.  * The largest chunk we care about.
  166.  * Must be smaller than pagesize
  167.  * Must be power of two
  168.  */
  169. #ifndef malloc_maxsize
  170. static    unsigned  malloc_maxsize;
  171. #endif /* malloc_maxsize */
  172.  
  173. #ifndef malloc_cache
  174. static    unsigned  malloc_cache;
  175. #endif /* malloc_cache */
  176.  
  177. /*
  178.  * The offset from pagenumber to index into the page directory
  179.  */
  180. static    u_long  malloc_origo;
  181.  
  182. /*
  183.  * The last index in the page directory we care about
  184.  */
  185. static    u_long  last_index;
  186.  
  187. /*
  188.  * Pointer to page directory.
  189.  * Allocated "as if with" malloc
  190.  */
  191. static    struct    pginfo **page_dir;
  192.  
  193. /*
  194.  * How many slots in the page directory
  195.  */
  196. static    unsigned    malloc_ninfo;
  197.  
  198. /*
  199.  * Free pages line up here 
  200.  */
  201. static struct pgfree    free_list;
  202.  
  203. /*
  204.  * Abort() if we fail to get VM ?
  205.  */
  206. static int malloc_abort;
  207.  
  208. #ifdef SANITY
  209. /*
  210.  * Are we trying to die ?
  211.  */
  212. static int suicide;
  213. #endif
  214.  
  215. /*
  216.  * dump statistics
  217.  */
  218. static int malloc_stats;
  219.  
  220. /*
  221.  * always realloc ?
  222.  */
  223. static int malloc_realloc;
  224.  
  225. /*
  226.  * my last break.
  227.  */
  228. static void *malloc_brk;
  229.  
  230. /*
  231.  * one location cache for free-list holders
  232.  */
  233. static struct pgfree *px;
  234.  
  235. static int set_pgdir(void *ptr, struct  pginfo *info);
  236. static int extend_page_directory(u_long index);
  237.  
  238. #ifdef SANITY
  239. void
  240. malloc_dump(FILE *fd)
  241. {
  242.     struct pginfo **pd;
  243.     struct pgfree *pf;
  244.     int j;
  245.  
  246.     pd = page_dir;
  247.  
  248.     /* print out all the pages */
  249.     for(j=0;j<=last_index;j++) {
  250.     fprintf(fd,"%08lx %5d ",(j+malloc_origo) << malloc_pageshift,j);
  251.     if (pd[j] == MALLOC_NOT_MINE) {
  252.         for(j++;j<=last_index && pd[j] == MALLOC_NOT_MINE;j++)
  253.         ;
  254.         j--;
  255.         fprintf(fd,".. %5d not mine\n",    j);
  256.     } else if (pd[j] == MALLOC_FREE) {
  257.         for(j++;j<=last_index && pd[j] == MALLOC_FREE;j++)
  258.         ;
  259.         j--;
  260.         fprintf(fd,".. %5d free\n", j);
  261.     } else if (pd[j] == MALLOC_FIRST) {
  262.         for(j++;j<=last_index && pd[j] == MALLOC_FOLLOW;j++)
  263.         ;
  264.         j--;
  265.         fprintf(fd,".. %5d in use\n", j);
  266.     } else if (pd[j] < MALLOC_MAGIC) {
  267.         fprintf(fd,"(%p)\n", pd[j]);
  268.     } else {
  269.         fprintf(fd,"%p %d (of %d) x %d @ %p --> %p\n",
  270.         pd[j],pd[j]->free, pd[j]->total, 
  271.         pd[j]->size, pd[j]->page, pd[j]->next);
  272.     }
  273.     }
  274.  
  275.     for(pf=free_list.next; pf; pf=pf->next) {
  276.     fprintf(fd,"Free: @%p [%p...%p[ %ld ->%p <-%p\n",
  277.         pf,pf->page,pf->end,pf->size,pf->prev,pf->next);
  278.     if (pf == pf->next) {
  279.         fprintf(fd,"Free_list loops.\n");
  280.         break;
  281.     }
  282.     }
  283.  
  284.     /* print out various info */
  285.     fprintf(fd,"Minsize\t%d\n",malloc_minsize);
  286.     fprintf(fd,"Maxsize\t%d\n",malloc_maxsize);
  287.     fprintf(fd,"Pagesize\t%d\n",malloc_pagesize);
  288.     fprintf(fd,"Pageshift\t%d\n",malloc_pageshift);
  289.     fprintf(fd,"FirstPage\t%ld\n",malloc_origo);
  290.     fprintf(fd,"LastPage\t%ld %lx\n",last_index+malloc_pageshift,
  291.     (last_index + malloc_pageshift) << malloc_pageshift);
  292.     fprintf(fd,"Break\t%ld\n",(u_long)sbrk(0) >> malloc_pageshift);
  293. }
  294.  
  295. static void wrterror(char *fmt, ...)
  296. {
  297.     char *q = "malloc() error: ";
  298.     char buf[100];
  299.     va_list ap;
  300.  
  301.     suicide = 1;
  302.  
  303.     va_start(ap, fmt);
  304.     PR_vsnprintf(buf, sizeof(buf), fmt, ap);
  305.     va_end(ap);
  306.     fputs(q, stderr);
  307.     fputs(buf, stderr);
  308.  
  309.     malloc_dump(stderr);
  310.     PR_Abort();
  311. }
  312.  
  313. static void wrtwarning(char *fmt, ...)
  314. {
  315.     char *q = "malloc() warning: ";
  316.     char buf[100];
  317.     va_list ap;
  318.  
  319.     va_start(ap, fmt);
  320.     PR_vsnprintf(buf, sizeof(buf), fmt, ap);
  321.     va_end(ap);
  322.     fputs(q, stderr);
  323.     fputs(buf, stderr);
  324. }
  325. #endif /* SANITY */
  326.  
  327.  
  328. /*
  329.  * Allocate a number of pages from the OS
  330.  */
  331. static caddr_t
  332. map_pages(int pages, int update)
  333. {
  334.     caddr_t result,tail;
  335.  
  336.     result = ((caddr_t)sbrk(0)) + malloc_pagemask - 1;
  337.     result = (caddr_t) ((u_long)result & ~malloc_pagemask);
  338.     tail = result + (pages << malloc_pageshift);
  339.     if (!brk(tail)) {
  340.     last_index = ((u_long)tail >> malloc_pageshift) - malloc_origo -1;
  341.     malloc_brk = tail;
  342.     TRACE(("%6d S %p .. %p\n",malloc_event++, result, tail));
  343.     if (!update || last_index < malloc_ninfo ||
  344.       extend_page_directory(last_index))
  345.         return result;
  346.     }
  347.     TRACE(("%6d s %d %p %d\n",malloc_event++,pages,sbrk(0),errno));
  348. #ifdef EXTRA_SANITY
  349.     wrterror("map_pages fails\n");
  350. #endif
  351.     return 0;
  352. }
  353.  
  354. #define set_bit(_pi,_bit) \
  355.     (_pi)->bits[(_bit)/MALLOC_BITS] |= 1L<<((_bit)%MALLOC_BITS)
  356.  
  357. #define clr_bit(_pi,_bit) \
  358.     (_pi)->bits[(_bit)/MALLOC_BITS] &= ~(1L<<((_bit)%MALLOC_BITS));
  359.  
  360. #define tst_bit(_pi,_bit) \
  361.     ((_pi)->bits[(_bit)/MALLOC_BITS] & (1L<<((_bit)%MALLOC_BITS)))
  362.  
  363. /*
  364.  * Extend page directory
  365.  */
  366. static int
  367. extend_page_directory(u_long index)
  368. {
  369.     struct  pginfo **new,**old;
  370.     int i;
  371.  
  372.     TRACE(("%6d E %lu\n",malloc_event++,index));
  373.     
  374.     /* Make it this many pages */
  375.     i = index * sizeof *page_dir;
  376.     i /= malloc_pagesize;
  377.     i += 2;
  378.  
  379.     /* Get new pages, if you used this much mem you don't care :-) */
  380.     new = (struct pginfo**) map_pages(i,0);
  381.     if (!new)
  382.     return 0;
  383.  
  384.     /* Copy the old stuff */
  385.     memset(new, 0, i * malloc_pagesize);
  386.     memcpy(new, page_dir,
  387.         malloc_ninfo * sizeof *page_dir);
  388.  
  389.     /* register the new size */
  390.     malloc_ninfo = i * malloc_pagesize / sizeof *page_dir;
  391.  
  392.     /* swap the pointers */
  393.     old = page_dir;
  394.     page_dir = new;
  395.  
  396.     /* Mark the pages */
  397.     index = ((u_long)new >> malloc_pageshift) - malloc_origo;
  398.     page_dir[index] = MALLOC_FIRST;
  399.     while (--i) {
  400.     page_dir[++index] = MALLOC_FOLLOW;
  401.     }
  402.  
  403.     /* Now free the old stuff */
  404.     _PR_UnlockedFree(old);
  405.     return 1;
  406. }
  407.  
  408. /*
  409.  * Set entry in page directory.
  410.  * Extend page directory if need be.
  411.  */
  412. static int
  413. set_pgdir(void *ptr, struct  pginfo *info)
  414. {
  415.     u_long index = ((u_long)ptr >> malloc_pageshift) - malloc_origo;
  416.  
  417.     if (index >= malloc_ninfo && !extend_page_directory(index))
  418.     return 0;
  419.     page_dir[index] = info;
  420.     return 1;
  421. }
  422.  
  423. /*
  424.  * Initialize the world
  425.  */
  426. static void
  427. malloc_init (void)
  428. {
  429.     int i;
  430.     char *p;
  431.  
  432.     TRACE(("%6d I\n",malloc_event++));
  433. #ifdef DEBUG
  434.     for (p=getenv("MALLOC_OPTIONS"); p && *p; p++) {
  435.     switch (*p) {
  436.         case 'a': malloc_abort = 0; break;
  437.         case 'A': malloc_abort = 1; break;
  438.         case 'd': malloc_stats = 0; break;
  439.         case 'D': malloc_stats = 1; break;
  440.         case 'r': malloc_realloc = 0; break;
  441.         case 'R': malloc_realloc = 1; break;
  442.         default:
  443.         wrtwarning("Unknown chars in MALLOC_OPTIONS\n");
  444.         break;
  445.     }
  446.     }
  447. #endif
  448.  
  449. #ifndef malloc_pagesize
  450.     /* determine our pagesize */
  451.     malloc_pagesize = getpagesize();
  452. #endif /* malloc_pagesize */
  453.  
  454. #ifndef malloc_pageshift
  455.     /* determine how much we shift by to get there */
  456.     for (i = malloc_pagesize; i > 1; i >>= 1)
  457.     malloc_pageshift++;
  458. #endif /* malloc_pageshift */
  459.  
  460. #ifndef malloc_cache
  461.     malloc_cache = 50 << malloc_pageshift;    
  462. #endif /* malloc_cache */
  463.  
  464. #ifndef malloc_minsize
  465.     /*
  466.      * find the smallest size allocation we will bother about.
  467.      * this is determined as the smallest allocation that can hold
  468.      * it's own pginfo;
  469.      */
  470.     i = 2;
  471.     for(;;) {
  472.     int j;
  473.  
  474.     /* Figure out the size of the bits */
  475.     j = malloc_pagesize/i;
  476.     j /= 8;
  477.     if (j < sizeof(u_long))
  478.         j = sizeof (u_long);
  479.     if (sizeof(struct pginfo) + j - sizeof (u_long) <= i)
  480.         break;
  481.     i += i;
  482.     }
  483.     malloc_minsize = i;
  484. #endif /* malloc_minsize */
  485.  
  486.  
  487.     /* Allocate one page for the page directory */
  488.     page_dir = (struct pginfo **) map_pages(1,0);
  489. #ifdef SANITY
  490.     if (!page_dir)
  491.     wrterror("fatal: my first mmap failed.  (check limits ?)\n");
  492. #endif
  493.  
  494.     /*
  495.      * We need a maximum of malloc_pageshift buckets, steal these from the
  496.      * front of the page_directory;
  497.      */
  498.     malloc_origo = (u_long) page_dir >> malloc_pageshift;
  499.     malloc_origo -= malloc_pageshift;
  500.  
  501.     /* Clear it */
  502.     memset(page_dir,0,malloc_pagesize);
  503.  
  504.     /* Find out how much it tells us */
  505.     malloc_ninfo = malloc_pagesize / sizeof *page_dir;
  506.  
  507.     /* Plug the page directory into itself */
  508.     i = set_pgdir(page_dir,MALLOC_FIRST);
  509. #ifdef SANITY
  510.     if (!i)
  511.     wrterror("fatal: couldn't set myself in the page directory\n");
  512. #endif
  513.  
  514.     /* Been here, done that */
  515.     initialized++;
  516. }
  517.  
  518. /*
  519.  * Allocate a number of complete pages
  520.  */
  521. static void *malloc_pages(size_t size)
  522. {
  523.     void *p,*delay_free = 0;
  524.     int i;
  525.     struct pgfree *pf;
  526.     u_long index;
  527.  
  528.     /* How many pages ? */
  529.     size += (malloc_pagesize-1);
  530.     size &= ~malloc_pagemask;
  531.  
  532.     p = 0;
  533.     /* Look for free pages before asking for more */
  534.     for(pf = free_list.next; pf; pf = pf->next) {
  535. #ifdef EXTRA_SANITY
  536.     if (pf->page == pf->end)
  537.         wrterror("zero entry on free_list\n");
  538.     if (pf->page > pf->end) {
  539.         TRACE(("%6d !s %p %p %p <%d>\n",malloc_event++,
  540.         pf,pf->page,pf->end,__LINE__));
  541.         wrterror("sick entry on free_list\n");
  542.     }
  543.     if ((void*)pf->page >= (void*)sbrk(0))
  544.         wrterror("entry on free_list past brk\n");
  545.     if (page_dir[((u_long)pf->page >> malloc_pageshift) - malloc_origo] 
  546.       != MALLOC_FREE) {
  547.         TRACE(("%6d !f %p %p %p <%d>\n",malloc_event++,
  548.         pf,pf->page,pf->end,__LINE__));
  549.         wrterror("non-free first page on free-list\n");
  550.     }
  551.     if (page_dir[((u_long)pf->end >> malloc_pageshift) - 1 - malloc_origo] 
  552.       != MALLOC_FREE)
  553.         wrterror("non-free last page on free-list\n");
  554. #endif /* EXTRA_SANITY */
  555.     if (pf->size < size) 
  556.         continue;
  557.     else if (pf->size == size) {
  558.         p = pf->page;
  559.         if (pf->next)
  560.             pf->next->prev = pf->prev;
  561.         pf->prev->next = pf->next;
  562.         delay_free = pf;
  563.         break;
  564.     } else {
  565.         p = pf->page;
  566.         pf->page += size;
  567.         pf->size -= size;
  568.         break;
  569.         }
  570.     }
  571. #ifdef EXTRA_SANITY
  572.     if (p && page_dir[((u_long)p >> malloc_pageshift) - malloc_origo] 
  573.       != MALLOC_FREE) {
  574.     wrterror("allocated non-free page on free-list\n");
  575.     }
  576. #endif /* EXTRA_SANITY */
  577.  
  578.     size >>= malloc_pageshift;
  579.  
  580.     /* Map new pages */
  581.     if (!p)
  582.     p = map_pages(size,1);
  583.  
  584.     if (p) {
  585.     /* Mark the pages in the directory */
  586.     index = ((u_long)p >> malloc_pageshift) - malloc_origo;
  587.     page_dir[index] = MALLOC_FIRST;
  588.     for (i=1;i<size;i++)
  589.         page_dir[index+i] = MALLOC_FOLLOW;
  590.     }
  591.     if (delay_free) {
  592.     if (!px) 
  593.         px = delay_free;
  594.     else
  595.         _PR_UnlockedFree(delay_free);
  596.     }
  597.     return p;
  598. }
  599.  
  600. /*
  601.  * Allocate a page of fragments
  602.  */
  603.  
  604. static int
  605. malloc_make_chunks(int bits)
  606. {
  607.     struct  pginfo *bp;
  608.     void *pp;
  609.     int i,k,l;
  610.  
  611.     /* Allocate a new bucket */
  612.     pp = malloc_pages(malloc_pagesize);
  613.     if (!pp)
  614.     return 0;
  615.     l = sizeof *bp - sizeof(u_long);
  616.     l += sizeof(u_long) *
  617.     (((malloc_pagesize >> bits)+MALLOC_BITS-1) / MALLOC_BITS);
  618.     if ((1<<(bits)) <= l+l) {
  619.     bp = (struct  pginfo *)pp;
  620.     } else {
  621.     bp = (struct  pginfo *)_PR_UnlockedMalloc(l);
  622.     }
  623.     if (!bp)
  624.     return 0;
  625.     bp->size = (1<<bits);
  626.     bp->shift = bits;
  627.     bp->total = bp->free = malloc_pagesize >> bits;
  628.     bp->next = page_dir[bits];
  629.     bp->page = pp;
  630.     i = set_pgdir(pp,bp);
  631.     if (!i)
  632.     return 0;
  633.  
  634.     /* We can safely assume that there is nobody in this chain */
  635.     page_dir[bits] = bp;
  636.  
  637.     /* set all valid bits in the bits */
  638.     k = bp->total;
  639.     i = 0;
  640. /*
  641.     for(;k-i >= MALLOC_BITS; i += MALLOC_BITS)
  642.     bp->bits[i / MALLOC_BITS] = ~0;
  643. */
  644.     for(; i < k; i++)
  645.     set_bit(bp,i);
  646.  
  647.     if (bp != pp)
  648.     return 1;
  649.  
  650.     /* We may have used the first ones already */
  651.     for(i=0;l > 0;i++) {
  652.     clr_bit(bp,i);
  653.     bp->free--;
  654.     bp->total--;
  655.     l -= (1 << bits);
  656.     }
  657.     return 1;
  658. }
  659.  
  660. /*
  661.  * Allocate a fragment
  662.  */
  663. static void *malloc_bytes(size_t size)
  664. {
  665.     size_t s;
  666.     int j;
  667.     struct  pginfo *bp;
  668.     int k;
  669.     u_long *lp, bf;
  670.  
  671.     /* Don't bother with anything less than this */
  672.     if (size < malloc_minsize) {
  673.     size = malloc_minsize;
  674.     }
  675.  
  676.     /* Find the right bucket */
  677.     j = 1;
  678.     s = size - 1;
  679.     while (s >>= 1) {
  680.         j++;
  681.     }
  682.  
  683.     /* If it's empty, make a page more of that size chunks */
  684.     if (!page_dir[j] && !malloc_make_chunks(j))
  685.     return 0;
  686.  
  687.     /* Find first word of bitmap which isn't empty */
  688.     bp = page_dir[j];
  689.     for (lp = bp->bits; !*lp; lp++)
  690.     ;
  691.  
  692.     /* Find that bit */
  693.     bf = *lp;
  694.     k = 0;
  695.     while ((bf & 1) == 0) {
  696.     bf >>= 1;
  697.     k++;
  698.     }
  699.  
  700.     *lp ^= 1L<<k;                       /* clear it */
  701.     bp->free--;
  702.     if (!bp->free) {
  703.     page_dir[j] = bp->next;
  704.     bp->next = 0;
  705.     }
  706.     k += (lp - bp->bits)*MALLOC_BITS;
  707.     return bp->page + (k << bp->shift);
  708. }
  709.  
  710. void *_PR_UnlockedMalloc(size_t size)
  711. {
  712.     void *result;
  713.  
  714.     /* Round up to a multiple of 8 bytes */
  715.     if (size & 7) {
  716.     size = size + 8 - (size & 7);
  717.     }
  718.  
  719.     if (!initialized)
  720.     malloc_init();
  721.  
  722. #ifdef SANITY
  723.     if (suicide)
  724.     PR_Abort();
  725. #endif
  726.  
  727.     if (size <= malloc_maxsize)
  728.     result =  malloc_bytes(size);
  729.     else
  730.     result =  malloc_pages(size);
  731. #ifdef SANITY
  732.     if (malloc_abort && !result)
  733.     wrterror("malloc() returns NULL\n");
  734. #endif
  735.     TRACE(("%6d M %p %d\n",malloc_event++,result,size));
  736.  
  737.     return result;
  738. }
  739.  
  740. void *_PR_UnlockedMemalign(size_t alignment, size_t size)
  741. {
  742.     void *result;
  743.  
  744.     /*
  745.      * alignment has to be a power of 2
  746.      */
  747.  
  748.     if ((size <= alignment) && (alignment <= malloc_maxsize))
  749.         size = alignment;    
  750.     else
  751.                size += alignment - 1;    
  752.  
  753.     /* Round up to a multiple of 8 bytes */
  754.     if (size & 7) {
  755.     size = size + 8 - (size & 7);
  756.     }
  757.  
  758.     if (!initialized)
  759.     malloc_init();
  760.  
  761. #ifdef SANITY
  762.     if (suicide)
  763.     abort();
  764. #endif
  765.  
  766.     if (size <= malloc_maxsize)
  767.     result =  malloc_bytes(size);
  768.     else
  769.     result =  malloc_pages(size);
  770. #ifdef SANITY
  771.     if (malloc_abort && !result)
  772.     wrterror("malloc() returns NULL\n");
  773. #endif
  774.     TRACE(("%6d A %p %d\n",malloc_event++,result,size));
  775.  
  776.     if ((u_long)result & (alignment - 1))
  777.         return ((void *)(((u_long)result + alignment)  & ~(alignment - 1)));
  778.     else
  779.         return result;
  780. }
  781.  
  782. void *_PR_UnlockedCalloc(size_t n, size_t nelem)
  783. {
  784.     void *p;
  785.  
  786.     /* Compute total size and then round up to a double word amount */
  787.     n *= nelem;
  788.     if (n & 7) {
  789.     n = n + 8 - (n & 7);
  790.     }
  791.  
  792.     /* Get the memory */
  793.     p = _PR_UnlockedMalloc(n);
  794.     if (p) {
  795.     /* Zero it */
  796.     memset(p, 0, n);
  797.     }
  798.     return p;
  799. }
  800.  
  801. /*
  802.  * Change an allocation's size
  803.  */
  804. void *_PR_UnlockedRealloc(void *ptr, size_t size)
  805. {
  806.     void *p;
  807.     u_long osize,page,index,tmp_index;
  808.     struct pginfo **mp;
  809.  
  810.     if (!initialized)
  811.     malloc_init();
  812.  
  813. #ifdef SANITY
  814.     if (suicide)
  815.     PR_Abort();
  816. #endif
  817.  
  818.     /* used as free() */
  819.     TRACE(("%6d R %p %d\n",malloc_event++, ptr, size));
  820.     if (ptr && !size) {
  821.     _PR_UnlockedFree(ptr);
  822.     return _PR_UnlockedMalloc (1);
  823.     }
  824.  
  825.     /* used as malloc() */
  826.     if (!ptr) {
  827.     p = _PR_UnlockedMalloc(size);
  828.     return p;
  829.     }
  830.  
  831.     /* Find the page directory entry for the page in question */
  832.     page = (u_long)ptr >> malloc_pageshift;
  833.     index = page - malloc_origo;
  834.  
  835.     /*
  836.      * check if memory was allocated by memalign
  837.      */
  838.     tmp_index = index;
  839.     while (page_dir[tmp_index] == MALLOC_FOLLOW)
  840.     tmp_index--;
  841.     if (tmp_index != index) {
  842.     /*
  843.      * memalign-allocated memory
  844.      */
  845.     index = tmp_index;
  846.     page = index + malloc_origo;            
  847.     ptr = (void *) (page << malloc_pageshift);
  848.     }
  849.     TRACE(("%6d R2 %p %d\n",malloc_event++, ptr, size));
  850.  
  851.     /* make sure it makes sense in some fashion */
  852.     if (index < malloc_pageshift || index > last_index) {
  853. #ifdef SANITY
  854.     wrtwarning("junk pointer passed to realloc()\n");
  855. #endif
  856.     return 0;
  857.     }
  858.  
  859.     /* find the size of that allocation, and see if we need to relocate */
  860.     mp = &page_dir[index];
  861.     if (*mp == MALLOC_FIRST) {
  862.     osize = malloc_pagesize;
  863.     while (mp[1] == MALLOC_FOLLOW) {
  864.         osize += malloc_pagesize;
  865.         mp++;
  866.     }
  867.         if (!malloc_realloc && 
  868.         size < osize && 
  869.         size > malloc_maxsize &&
  870.         size > (osize - malloc_pagesize)) {
  871.         return ptr;
  872.     }
  873.     } else if (*mp >= MALLOC_MAGIC) {
  874.     osize = (*mp)->size;
  875.     if (!malloc_realloc &&
  876.         size < osize && 
  877.         (size > (*mp)->size/2 || (*mp)->size == malloc_minsize)) {
  878.         return ptr;
  879.     }
  880.     } else {
  881. #ifdef SANITY
  882.     wrterror("realloc() of wrong page.\n");
  883. #endif
  884.     }
  885.  
  886.     /* try to reallocate */
  887.     p = _PR_UnlockedMalloc(size);
  888.  
  889.     if (p) {
  890.     /* copy the lesser of the two sizes */
  891.     if (osize < size)
  892.         memcpy(p,ptr,osize);
  893.     else
  894.         memcpy(p,ptr,size);
  895.     _PR_UnlockedFree(ptr);
  896.     }
  897. #ifdef DEBUG
  898.     else if (malloc_abort)
  899.     wrterror("realloc() returns NULL\n");
  900. #endif
  901.  
  902.     return p;
  903. }
  904.  
  905. /*
  906.  * Free a sequence of pages
  907.  */
  908.  
  909. static void
  910. free_pages(char *ptr, u_long page, int index, struct pginfo *info)
  911. {
  912.     int i;
  913.     struct pgfree *pf,*pt;
  914.     u_long l;
  915.     char *tail;
  916.  
  917.     TRACE(("%6d FP %p %d\n",malloc_event++, ptr, page));
  918.     /* Is it free already ? */
  919.     if (info == MALLOC_FREE) {
  920. #ifdef SANITY
  921.     wrtwarning("freeing free page at %p.\n", ptr);
  922. #endif
  923.     return;
  924.     }
  925.  
  926. #ifdef SANITY
  927.     /* Is it not the right place to begin ? */
  928.     if (info != MALLOC_FIRST)
  929.     wrterror("freeing wrong page.\n");
  930.  
  931.     /* Is this really a pointer to a page ? */
  932.     if ((u_long)ptr & malloc_pagemask)
  933.     wrterror("freeing messed up page pointer.\n");
  934. #endif
  935.  
  936.     /* Count how many pages it is anyway */
  937.     page_dir[index] = MALLOC_FREE;
  938.     for (i = 1; page_dir[index+i] == MALLOC_FOLLOW; i++)
  939.     page_dir[index + i] = MALLOC_FREE;
  940.  
  941.     l = i << malloc_pageshift;
  942.  
  943.     tail = ptr+l;
  944.  
  945.     /* add to free-list */
  946.     if (!px)
  947.     px = _PR_UnlockedMalloc(sizeof *pt);
  948.     /* XXX check success */
  949.     px->page = ptr;
  950.     px->end =  tail;
  951.     px->size = l;
  952.     if (!free_list.next) {
  953.     px->next = free_list.next;
  954.     px->prev = &free_list;
  955.     free_list.next = px;
  956.     pf = px;
  957.     px = 0;
  958.     } else {
  959.     tail = ptr+l;
  960.     for(pf = free_list.next; pf->next && pf->end < ptr; pf = pf->next)
  961.         ;
  962.     for(; pf; pf = pf->next) {
  963.         if (pf->end == ptr ) {
  964.         /* append to entry */
  965.         pf->end += l;
  966.         pf->size += l;
  967.         if (pf->next && pf->end == pf->next->page ) {
  968.             pt = pf->next;
  969.             pf->end = pt->end;
  970.             pf->size += pt->size;
  971.             pf->next = pt->next;
  972.             if (pf->next)
  973.             pf->next->prev = pf;
  974.             _PR_UnlockedFree(pt);
  975.         }
  976.         } else if (pf->page == tail) {
  977.         /* prepend to entry */
  978.         pf->size += l;
  979.         pf->page = ptr;
  980.         } else if (pf->page > ptr) {
  981.         px->next = pf;
  982.         px->prev = pf->prev;
  983.         pf->prev = px;
  984.         px->prev->next = px;
  985.         pf = px;
  986.         px = 0;
  987.         } else if (!pf->next) {
  988.         px->next = 0;
  989.         px->prev = pf;
  990.         pf->next = px;
  991.         pf = px;
  992.         px = 0;
  993.         } else {
  994.         continue;
  995.         }
  996.         break;
  997.     }
  998.     }
  999.     if (!pf->next &&
  1000.       pf->size > malloc_cache &&
  1001.       pf->end == malloc_brk &&
  1002.       malloc_brk == (void*)sbrk(0)) {
  1003.     pf->end = pf->page + malloc_cache;
  1004.     pf->size = malloc_cache;
  1005.     TRACE(("%6d U %p %d\n",malloc_event++,pf->end,pf->end - pf->page));
  1006.     brk(pf->end);
  1007.     malloc_brk = pf->end;
  1008.     /* Find the page directory entry for the page in question */
  1009.     page = (u_long)pf->end >> malloc_pageshift;
  1010.     index = page - malloc_origo;
  1011.     /* Now update the directory */
  1012.     for(i=index;i <= last_index;)
  1013.         page_dir[i++] = MALLOC_NOT_MINE;
  1014.     last_index = index - 1;
  1015.     }
  1016. }
  1017.  
  1018. /*
  1019.  * Free a chunk, and possibly the page it's on, if the page becomes empty.
  1020.  */
  1021.  
  1022. static void
  1023. free_bytes(void *ptr, u_long page, int index, struct pginfo *info)
  1024. {
  1025.     int i;
  1026.     struct pginfo **mp;
  1027.     void *vp;
  1028.  
  1029.     /* Make sure that pointer is multiplum of chunk-size */
  1030. #ifdef SANITY
  1031.     if ((u_long)ptr & (info->size - 1))
  1032.     wrterror("freeing messed up chunk pointer\n");
  1033. #endif
  1034.  
  1035.     /* Find the chunk number on the page */
  1036.     i = ((u_long)ptr & malloc_pagemask) >> info->shift;
  1037.  
  1038.     /* See if it's free already */
  1039.     if (tst_bit(info,i)) {
  1040. #ifdef SANITY
  1041.     wrtwarning("freeing free chunk at %p\n", ptr);
  1042. #endif
  1043.     return;
  1044.     }
  1045.  
  1046.     /* Mark it free */
  1047.     set_bit(info,i);
  1048.     info->free++;
  1049.  
  1050.     /* If the page was full before, we need to put it on the queue now */
  1051.     if (info->free == 1) {
  1052.     mp = page_dir + info->shift;
  1053.     while (*mp && (*mp)->next && (*mp)->next->page < info->page)
  1054.         mp = &(*mp)->next;
  1055.     info->next = *mp;
  1056.     *mp = info;
  1057.     return;
  1058.     }
  1059.  
  1060.     /* If this page isn't empty, don't do anything. */
  1061.     if (info->free != info->total)
  1062.     return;
  1063.  
  1064.     /* We may want to keep at least one page of each size chunks around.  */
  1065.     mp = page_dir + info->shift;
  1066.     if (0 && (*mp == info) && !info->next)
  1067.     return;
  1068.  
  1069.     /* Find & remove this page in the queue */
  1070.     while (*mp != info) {
  1071.     mp = &((*mp)->next);
  1072. #ifdef EXTRA_SANITY
  1073.     if (!*mp) {
  1074.         TRACE(("%6d !q %p\n",malloc_event++,info));
  1075.         wrterror("Not on queue\n");
  1076.     }
  1077. #endif
  1078.     }
  1079.     *mp = info->next;
  1080.  
  1081.     /* Free the page & the info structure if need be */
  1082.     set_pgdir(info->page,MALLOC_FIRST);
  1083.     if((void*)info->page == (void*)info) {
  1084.     _PR_UnlockedFree(info->page);
  1085.     } else {
  1086.     vp = info->page;
  1087.     _PR_UnlockedFree(info);
  1088.     _PR_UnlockedFree(vp);
  1089.     }
  1090. }
  1091.  
  1092. void _PR_UnlockedFree(void *ptr)
  1093. {
  1094.     u_long page;
  1095.     struct pginfo *info;
  1096.     int index, tmp_index;
  1097.  
  1098.     TRACE(("%6d F %p\n",malloc_event++,ptr));
  1099.     /* This is legal */
  1100.     if (!ptr)
  1101.     return;
  1102.  
  1103. #ifdef SANITY
  1104.     /* There wouldn't be anything to free */
  1105.     if (!initialized) {
  1106.     wrtwarning("free() called before malloc() ever got called\n");
  1107.     return;
  1108.     }
  1109. #endif
  1110.  
  1111. #ifdef SANITY
  1112.     if (suicide)
  1113.     PR_Abort();
  1114. #endif
  1115.  
  1116.     /* Find the page directory entry for the page in question */
  1117.     page = (u_long)ptr >> malloc_pageshift;
  1118.     index = page - malloc_origo;
  1119.  
  1120.     /*
  1121.      * check if memory was allocated by memalign
  1122.      */
  1123.     tmp_index = index;
  1124.     while (page_dir[tmp_index] == MALLOC_FOLLOW)
  1125.     tmp_index--;
  1126.     if (tmp_index != index) {
  1127.     /*
  1128.      * memalign-allocated memory
  1129.      */
  1130.     index = tmp_index;
  1131.     page = index + malloc_origo;            
  1132.     ptr = (void *) (page << malloc_pageshift);
  1133.     }
  1134.     /* make sure it makes sense in some fashion */
  1135.     if (index < malloc_pageshift) {
  1136. #ifdef SANITY
  1137.     wrtwarning("junk pointer %p (low) passed to free()\n", ptr);
  1138. #endif
  1139.     return;
  1140.     }
  1141.     if (index > last_index) {
  1142. #ifdef SANITY
  1143.     wrtwarning("junk pointer %p (high) passed to free()\n", ptr);
  1144. #endif
  1145.     return;
  1146.     }
  1147.  
  1148.     /* handle as page-allocation or chunk allocation */
  1149.     info = page_dir[index];
  1150.     if (info < MALLOC_MAGIC)
  1151.         free_pages(ptr,page,index,info);
  1152.     else 
  1153.     free_bytes(ptr,page,index,info);
  1154.     return;
  1155. }
  1156. #endif /* _PR_OVERRIDE_MALLOC */
  1157.