lib/libc/stdlib/malloc.c

   1 /*
   2  * ----------------------------------------------------------------------------
   3  * "THE BEER-WARE LICENSE" (Revision 42):
   4  * <phk@FreeBSD.ORG> wrote this file.  As long as you retain this notice you
   5  * can do whatever you want with this stuff. If we meet some day, and you think
   6  * this stuff is worth it, you can buy me a beer in return.   Poul-Henning Kamp
   7  * ----------------------------------------------------------------------------
   8  *
   9  * $FreeBSD: src/lib/libc/stdlib/malloc.c,v 1.49.2.4 2001/12/29 08:10:14 knu Exp $
  10  * $DragonFly: src/lib/libc/stdlib/malloc.c,v 1.5 2004/02/03 07:34:10 dillon Exp $
  11  *
  12  */
  13
  14 /*
  15  * Defining EXTRA_SANITY will enable extra checks which are related
  16  * to internal conditions and consistency in malloc.c. This has a
  17  * noticeable runtime performance hit, and generally will not do you
  18  * any good unless you fiddle with the internals of malloc or want
  19  * to catch random pointer corruption as early as possible.
  20  */
  21 #ifndef MALLOC_EXTRA_SANITY
  22 #undef MALLOC_EXTRA_SANITY
  23 #endif
  24
  25 /*
  26  * What to use for Junk.  This is the byte value we use to fill with
  27  * when the 'J' option is enabled.
  28  */
  29 #define SOME_JUNK       0xd0            /* as in "Duh" :-) */
  30
  31 /*
  32  * The basic parameters you can tweak.
  33  *
  34  * malloc_pageshift     pagesize = 1 << malloc_pageshift
  35  *                      It's probably best if this is the native
  36  *                      page size, but it doesn't have to be.
  37  *
  38  * malloc_minsize       minimum size of an allocation in bytes.
  39  *                      If this is too small it's too much work
  40  *                      to manage them.  This is also the smallest
  41  *                      unit of alignment used for the storage
  42  *                      returned by malloc/realloc.
  43  *
  44  */
  45
  46 #if defined(__FreeBSD__) || defined(__DragonFly__)
  47 #   if defined(__i386__)
  48 #       define malloc_pageshift         12U
  49 #       define malloc_minsize           16U
  50 #   endif
  51 #   if defined(__alpha__)
  52 #       define malloc_pageshift         13U
  53 #       define malloc_minsize           16U
  54 #   endif
  55 #   if !defined(__NETBSD_SYSCALLS)
  56 #       define HAS_UTRACE
  57 #   endif
  58     /*
  59      * Make malloc/free/realloc thread-safe in libc for use with
  60      * kernel threads.
  61      */
  62 #   include "libc_private.h"
  63 #   include "spinlock.h"
  64     static spinlock_t thread_lock       = _SPINLOCK_INITIALIZER;
  65 #   define THREAD_LOCK()                if (__isthreaded) _SPINLOCK(&thread_lock);
  66 #   define THREAD_UNLOCK()              if (__isthreaded) _SPINUNLOCK(&thread_lock);
  67 #endif /* __FreeBSD__ || __DragonFly__ */
  68
  69 #if defined(__sparc__) && defined(sun)
  70 #   define malloc_pageshift             12U
  71 #   define malloc_minsize               16U
  72 #   define MAP_ANON                     (0)
  73     static int fdzero;
  74 #   define MMAP_FD      fdzero
  75 #   define INIT_MMAP() \
  76         { if ((fdzero = _open(_PATH_DEVZERO, O_RDWR, 0000)) == -1) \
  77             wrterror("open of /dev/zero"); }
  78 #   define MADV_FREE                    MADV_DONTNEED
  79 #endif /* __sparc__ */
  80
  81 /* Insert your combination here... */
  82 #if defined(__FOOCPU__) && defined(__BAROS__)
  83 #   define malloc_pageshift             12U
  84 #   define malloc_minsize               16U
  85 #endif /* __FOOCPU__ && __BAROS__ */
  86
  87
  88 /*
  89  * No user serviceable parts behind this point.
  90  */
  91 #include <sys/types.h>
  92 #include <sys/mman.h>
  93 #include <errno.h>
  94 #include <fcntl.h>
  95 #include <paths.h>
  96 #include <stddef.h>
  97 #include <stdio.h>
  98 #include <stdlib.h>
  99 #include <string.h>
 100 #include <unistd.h>
 101
 102 /*
 103  * This structure describes a page worth of chunks.
 104  */
 105
 106 struct pginfo {
 107     struct pginfo       *next;  /* next on the free list */
 108     void                *page;  /* Pointer to the page */
 109     u_short             size;   /* size of this page's chunks */
 110     u_short             shift;  /* How far to shift for this size chunks */
 111     u_short             free;   /* How many free chunks */
 112     u_short             total;  /* How many chunk */
 113     u_int               bits[1]; /* Which chunks are free */
 114 };
 115
 116 /*
 117  * This structure describes a number of free pages.
 118  */
 119
 120 struct pgfree {
 121     struct pgfree       *next;  /* next run of free pages */
 122     struct pgfree       *prev;  /* prev run of free pages */
 123     void                *page;  /* pointer to free pages */
 124     void                *end;   /* pointer to end of free pages */
 125     size_t              size;   /* number of bytes free */
 126 };
 127
 128 /*
 129  * How many bits per u_int in the bitmap.
 130  * Change only if not 8 bits/byte
 131  */
 132 #define MALLOC_BITS     (8*sizeof(u_int))
 133
 134 /*
 135  * Magic values to put in the page_directory
 136  */
 137 #define MALLOC_NOT_MINE ((struct pginfo*) 0)
 138 #define MALLOC_FREE     ((struct pginfo*) 1)
 139 #define MALLOC_FIRST    ((struct pginfo*) 2)
 140 #define MALLOC_FOLLOW   ((struct pginfo*) 3)
 141 #define MALLOC_MAGIC    ((struct pginfo*) 4)
 142
 143 #ifndef malloc_pageshift
 144 #define malloc_pageshift                12U
 145 #endif
 146
 147 #ifndef malloc_minsize
 148 #define malloc_minsize                  16U
 149 #endif
 150
 151 #if !defined(malloc_pagesize)
 152 #define malloc_pagesize                 (1UL<<malloc_pageshift)
 153 #endif
 154
 155 #if ((1<<malloc_pageshift) != malloc_pagesize)
 156 #error  "(1<<malloc_pageshift) != malloc_pagesize"
 157 #endif
 158
 159 #ifndef malloc_maxsize
 160 #define malloc_maxsize                  ((malloc_pagesize)>>1)
 161 #endif
 162
 163 /* A mask for the offset inside a page.  */
 164 #define malloc_pagemask ((malloc_pagesize)-1)
 165
 166 #define pageround(foo) (((foo) + (malloc_pagemask))&(~(malloc_pagemask)))
 167 #define ptr2index(foo) (((u_long)(foo) >> malloc_pageshift)-malloc_origo)
 168
 169 #ifndef THREAD_LOCK
 170 #define THREAD_LOCK()
 171 #endif
 172
 173 #ifndef THREAD_UNLOCK
 174 #define THREAD_UNLOCK()
 175 #endif
 176
 177 #ifndef MMAP_FD
 178 #define MMAP_FD (-1)
 179 #endif
 180
 181 #ifndef INIT_MMAP
 182 #define INIT_MMAP()
 183 #endif
 184
 185 /* Set when initialization has been done */
 186 static unsigned malloc_started;
 187
 188 /* Recusion flag for public interface. */
 189 static int malloc_active;
 190
 191 /* Number of free pages we cache */
 192 static unsigned malloc_cache = 16;
 193
 194 /* The offset from pagenumber to index into the page directory */
 195 static u_long malloc_origo;
 196
 197 /* The last index in the page directory we care about */
 198 static u_long last_index;
 199
 200 /* Pointer to page directory. Allocated "as if with" malloc */
 201 static struct   pginfo **page_dir;
 202
 203 /* How many slots in the page directory */
 204 static unsigned malloc_ninfo;
 205
 206 /* Free pages line up here */
 207 static struct pgfree free_list;
 208
 209 /* Abort(), user doesn't handle problems.  */
 210 static int malloc_abort;
 211
 212 /* Are we trying to die ?  */
 213 static int suicide;
 214
 215 /* always realloc ?  */
 216 static int malloc_realloc;
 217
 218 /* pass the kernel a hint on free pages ?  */
 219 static int malloc_hint = 0;
 220
 221 /* xmalloc behaviour ?  */
 222 static int malloc_xmalloc;
 223
 224 /* sysv behaviour for malloc(0) ?  */
 225 static int malloc_sysv;
 226
 227 /* zero fill ?  */
 228 static int malloc_zero;
 229
 230 /* junk fill ?  */
 231 static int malloc_junk;
 232
 233 #ifdef HAS_UTRACE
 234
 235 /* utrace ?  */
 236 static int malloc_utrace;
 237
 238 struct ut { void *p; size_t s; void *r; };
 239
 240 void utrace (struct ut *, int);
 241
 242 #define UTRACE(a, b, c) \
 243         if (malloc_utrace) \
 244                 {struct ut u; u.p=a; u.s = b; u.r=c; utrace(&u, sizeof u);}
 245 #else /* !HAS_UTRACE */
 246 #define UTRACE(a,b,c)
 247 #endif /* HAS_UTRACE */
 248
 249 /* my last break. */
 250 static void *malloc_brk;
 251
 252 /* one location cache for free-list holders */
 253 static struct pgfree *px;
 254
 255 /* compile-time options */
 256 char *malloc_options;
 257
 258 /* Name of the current public function */
 259 static char *malloc_func;
 260
 261 /* Macro for mmap */
 262 #define MMAP(size) \
 263         mmap(0, (size), PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, \
 264             MMAP_FD, 0);
 265
 266 /*
 267  * Necessary function declarations
 268  */
 269 static int extend_pgdir(u_long index);
 270 static void *imalloc(size_t size);
 271 static void ifree(void *ptr);
 272 static void *irealloc(void *ptr, size_t size);
 273
 274 extern char *__progname;
 275
 276 static void
 277 wrterror(char *p)
 278 {
 279     char *q = " error: ";
 280     _write(STDERR_FILENO, __progname, strlen(__progname));
 281     _write(STDERR_FILENO, malloc_func, strlen(malloc_func));
 282     _write(STDERR_FILENO, q, strlen(q));
 283     _write(STDERR_FILENO, p, strlen(p));
 284     suicide = 1;
 285     abort();
 286 }
 287
 288 static void
 289 wrtwarning(char *p)
 290 {
 291     char *q = " warning: ";
 292     if (malloc_abort)
 293         wrterror(p);
 294     _write(STDERR_FILENO, __progname, strlen(__progname));
 295     _write(STDERR_FILENO, malloc_func, strlen(malloc_func));
 296     _write(STDERR_FILENO, q, strlen(q));
 297     _write(STDERR_FILENO, p, strlen(p));
 298 }
 299
 300 /*
 301  * Allocate a number of pages from the OS
 302  */
 303 static void *
 304 map_pages(size_t pages)
 305 {
 306     caddr_t result, tail;
 307
 308     result = (caddr_t)pageround((u_long)sbrk(0));
 309     tail = result + (pages << malloc_pageshift);
 310
 311     if (brk(tail)) {
 312 #ifdef EXTRA_SANITY
 313         wrterror("(ES): map_pages fails\n");
 314 #endif /* EXTRA_SANITY */
 315         return 0;
 316     }
 317
 318     last_index = ptr2index(tail) - 1;
 319     malloc_brk = tail;
 320
 321     if ((last_index+1) >= malloc_ninfo && !extend_pgdir(last_index))
 322         return 0;;
 323
 324     return result;
 325 }
 326
 327 /*
 328  * Extend page directory
 329  */
 330 static int
 331 extend_pgdir(u_long index)
 332 {
 333     struct  pginfo **new, **old;
 334     u_long i, oldlen;
 335
 336     /* Make it this many pages */
 337     i = index * sizeof *page_dir;
 338     i /= malloc_pagesize;
 339     i += 2;
 340
 341     /* remember the old mapping size */
 342     oldlen = malloc_ninfo * sizeof *page_dir;
 343
 344     /*
 345      * NOTE: we allocate new pages and copy the directory rather than tempt
 346      * fate by trying to "grow" the region.. There is nothing to prevent
 347      * us from accidently re-mapping space that's been allocated by our caller
 348      * via dlopen() or other mmap().
 349      *
 350      * The copy problem is not too bad, as there is 4K of page index per
 351      * 4MB of malloc arena.
 352      *
 353      * We can totally avoid the copy if we open a file descriptor to associate
 354      * the anon mappings with.  Then, when we remap the pages at the new
 355      * address, the old pages will be "magically" remapped..  But this means
 356      * keeping open a "secret" file descriptor.....
 357      */
 358
 359     /* Get new pages */
 360     new = (struct pginfo**) MMAP(i * malloc_pagesize);
 361     if (new == (struct pginfo **)-1)
 362         return 0;
 363
 364     /* Copy the old stuff */
 365     memcpy(new, page_dir,
 366             malloc_ninfo * sizeof *page_dir);
 367
 368     /* register the new size */
 369     malloc_ninfo = i * malloc_pagesize / sizeof *page_dir;
 370
 371     /* swap the pointers */
 372     old = page_dir;
 373     page_dir = new;
 374
 375     /* Now free the old stuff */
 376     munmap(old, oldlen);
 377     return 1;
 378 }
 379
 380 /*
 381  * Initialize the world
 382  */
 383 static void
 384 malloc_init ()
 385 {
 386     char *p, b[64];
 387     int i, j;
 388     int errnosave;
 389
 390     INIT_MMAP();
 391
 392 #ifdef EXTRA_SANITY
 393     malloc_junk = 1;
 394 #endif /* EXTRA_SANITY */
 395
 396     for (i = 0; i < 3; i++) {
 397         if (i == 0) {
 398             errnosave = errno;
 399             j = readlink("/etc/malloc.conf", b, sizeof b - 1);
 400             errno = errnosave;
 401             if (j <= 0)
 402                 continue;
 403             b[j] = '\0';
 404             p = b;
 405         } else if (i == 1) {
 406             p = getenv("MALLOC_OPTIONS");
 407         } else {
 408             p = malloc_options;
 409         }
 410         for (; p && *p; p++) {
 411             switch (*p) {
 412                 case '>': malloc_cache   <<= 1; break;
 413                 case '<': malloc_cache   >>= 1; break;
 414                 case 'a': malloc_abort   = 0; break;
 415                 case 'A': malloc_abort   = 1; break;
 416                 case 'h': malloc_hint    = 0; break;
 417                 case 'H': malloc_hint    = 1; break;
 418                 case 'r': malloc_realloc = 0; break;
 419                 case 'R': malloc_realloc = 1; break;
 420                 case 'j': malloc_junk    = 0; break;
 421                 case 'J': malloc_junk    = 1; break;
 422 #ifdef HAS_UTRACE
 423                 case 'u': malloc_utrace  = 0; break;
 424                 case 'U': malloc_utrace  = 1; break;
 425 #endif
 426                 case 'v': malloc_sysv    = 0; break;
 427                 case 'V': malloc_sysv    = 1; break;
 428                 case 'x': malloc_xmalloc = 0; break;
 429                 case 'X': malloc_xmalloc = 1; break;
 430                 case 'z': malloc_zero    = 0; break;
 431                 case 'Z': malloc_zero    = 1; break;
 432                 default:
 433                     j = malloc_abort;
 434                     malloc_abort = 0;
 435                     wrtwarning("unknown char in MALLOC_OPTIONS\n");
 436                     malloc_abort = j;
 437                     break;
 438             }
 439         }
 440     }
 441
 442     UTRACE(0, 0, 0);
 443
 444     /*
 445      * We want junk in the entire allocation, and zero only in the part
 446      * the user asked for.
 447      */
 448     if (malloc_zero)
 449         malloc_junk=1;
 450
 451     /*
 452      * If we run with junk (or implicitly from above: zero), we want to
 453      * force realloc() to get new storage, so we can DTRT with it.
 454      */
 455     if (malloc_junk)
 456         malloc_realloc=1;
 457
 458     /* Allocate one page for the page directory */
 459     page_dir = (struct pginfo **) MMAP(malloc_pagesize);
 460
 461     if (page_dir == (struct pginfo **) -1)
 462         wrterror("mmap(2) failed, check limits\n");
 463
 464     /*
 465      * We need a maximum of malloc_pageshift buckets, steal these from the
 466      * front of the page_directory;
 467      */
 468     malloc_origo = ((u_long)pageround((u_long)sbrk(0))) >> malloc_pageshift;
 469     malloc_origo -= malloc_pageshift;
 470
 471     malloc_ninfo = malloc_pagesize / sizeof *page_dir;
 472
 473     /* Recalculate the cache size in bytes, and make sure it's nonzero */
 474
 475     if (!malloc_cache)
 476         malloc_cache++;
 477
 478     malloc_cache <<= malloc_pageshift;
 479
 480     /*
 481      * This is a nice hack from Kaleb Keithly (kaleb@x.org).
 482      * We can sbrk(2) further back when we keep this on a low address.
 483      */
 484     px = (struct pgfree *) imalloc (sizeof *px);
 485
 486     /* Been here, done that */
 487     malloc_started++;
 488 }
 489
 490 /*
 491  * Allocate a number of complete pages
 492  */
 493 static void *
 494 malloc_pages(size_t size)
 495 {
 496     void *p, *delay_free = 0;
 497     size_t i;
 498     struct pgfree *pf;
 499     u_long index;
 500
 501     size = pageround(size);
 502
 503     p = 0;
 504
 505     /* Look for free pages before asking for more */
 506     for(pf = free_list.next; pf; pf = pf->next) {
 507
 508 #ifdef EXTRA_SANITY
 509         if (pf->size & malloc_pagemask)
 510             wrterror("(ES): junk length entry on free_list\n");
 511         if (!pf->size)
 512             wrterror("(ES): zero length entry on free_list\n");
 513         if (pf->page == pf->end)
 514             wrterror("(ES): zero entry on free_list\n");
 515         if (pf->page > pf->end)
 516             wrterror("(ES): sick entry on free_list\n");
 517         if ((void*)pf->page >= (void*)sbrk(0))
 518             wrterror("(ES): entry on free_list past brk\n");
 519         if (page_dir[ptr2index(pf->page)] != MALLOC_FREE)
 520             wrterror("(ES): non-free first page on free-list\n");
 521         if (page_dir[ptr2index(pf->end)-1] != MALLOC_FREE)
 522             wrterror("(ES): non-free last page on free-list\n");
 523 #endif /* EXTRA_SANITY */
 524
 525         if (pf->size < size)
 526             continue;
 527
 528         if (pf->size == size) {
 529             p = pf->page;
 530             if (pf->next)
 531                     pf->next->prev = pf->prev;
 532             pf->prev->next = pf->next;
 533             delay_free = pf;
 534             break;
 535         }
 536
 537         p = pf->page;
 538         pf->page = (char *)pf->page + size;
 539         pf->size -= size;
 540         break;
 541     }
 542
 543 #ifdef EXTRA_SANITY
 544     if (p && page_dir[ptr2index(p)] != MALLOC_FREE)
 545         wrterror("(ES): allocated non-free page on free-list\n");
 546 #endif /* EXTRA_SANITY */
 547
 548     size >>= malloc_pageshift;
 549
 550     /* Map new pages */
 551     if (!p)
 552         p = map_pages(size);
 553
 554     if (p) {
 555
 556         index = ptr2index(p);
 557         page_dir[index] = MALLOC_FIRST;
 558         for (i=1;i<size;i++)
 559             page_dir[index+i] = MALLOC_FOLLOW;
 560
 561         if (malloc_junk)
 562             memset(p, SOME_JUNK, size << malloc_pageshift);
 563     }
 564
 565     if (delay_free) {
 566         if (!px)
 567             px = delay_free;
 568         else
 569             ifree(delay_free);
 570     }
 571
 572     return p;
 573 }
 574
 575 /*
 576  * Allocate a page of fragments
 577  */
 578
 579 static __inline__ int
 580 malloc_make_chunks(int bits)
 581 {
 582     struct  pginfo *bp;
 583     void *pp;
 584     int i, k, l;
 585
 586     /* Allocate a new bucket */
 587     pp = malloc_pages(malloc_pagesize);
 588     if (!pp)
 589         return 0;
 590
 591     /* Find length of admin structure */
 592     l = offsetof(struct pginfo, bits[0]);
 593     l += sizeof bp->bits[0] *
 594         (((malloc_pagesize >> bits)+MALLOC_BITS-1) / MALLOC_BITS);
 595
 596     /* Don't waste more than two chunks on this */
 597     if ((1<<(bits)) <= l+l) {
 598         bp = (struct  pginfo *)pp;
 599     } else {
 600         bp = (struct  pginfo *)imalloc(l);
 601         if (!bp) {
 602             ifree(pp);
 603             return 0;
 604         }
 605     }
 606
 607     bp->size = (1<<bits);
 608     bp->shift = bits;
 609     bp->total = bp->free = malloc_pagesize >> bits;
 610     bp->page = pp;
 611
 612     /* set all valid bits in the bitmap */
 613     k = bp->total;
 614     i = 0;
 615
 616     /* Do a bunch at a time */
 617     for(;k-i >= MALLOC_BITS; i += MALLOC_BITS)
 618         bp->bits[i / MALLOC_BITS] = ~0;
 619
 620     for(; i < k; i++)
 621         bp->bits[i/MALLOC_BITS] |= 1<<(i%MALLOC_BITS);
 622
 623     if (bp == bp->page) {
 624         /* Mark the ones we stole for ourselves */
 625         for(i=0;l > 0;i++) {
 626             bp->bits[i/MALLOC_BITS] &= ~(1<<(i%MALLOC_BITS));
 627             bp->free--;
 628             bp->total--;
 629             l -= (1 << bits);
 630         }
 631     }
 632
 633     /* MALLOC_LOCK */
 634
 635     page_dir[ptr2index(pp)] = bp;
 636
 637     bp->next = page_dir[bits];
 638     page_dir[bits] = bp;
 639
 640     /* MALLOC_UNLOCK */
 641
 642     return 1;
 643 }
 644
 645 /*
 646  * Allocate a fragment
 647  */
 648 static void *
 649 malloc_bytes(size_t size)
 650 {
 651     int i,j;
 652     u_int u;
 653     struct  pginfo *bp;
 654     int k;
 655     u_int *lp;
 656
 657     /* Don't bother with anything less than this */
 658     if (size < malloc_minsize)
 659         size = malloc_minsize;
 660
 661     /* Find the right bucket */
 662     j = 1;
 663     i = size-1;
 664     while (i >>= 1)
 665         j++;
 666
 667     /* If it's empty, make a page more of that size chunks */
 668     if (!page_dir[j] && !malloc_make_chunks(j))
 669         return 0;
 670
 671     bp = page_dir[j];
 672
 673     /* Find first word of bitmap which isn't empty */
 674     for (lp = bp->bits; !*lp; lp++)
 675         ;
 676
 677     /* Find that bit, and tweak it */
 678     u = 1;
 679     k = 0;
 680     while (!(*lp & u)) {
 681         u += u;
 682         k++;
 683     }
 684     *lp ^= u;
 685
 686     /* If there are no more free, remove from free-list */
 687     if (!--bp->free) {
 688         page_dir[j] = bp->next;
 689         bp->next = 0;
 690     }
 691
 692     /* Adjust to the real offset of that chunk */
 693     k += (lp-bp->bits)*MALLOC_BITS;
 694     k <<= bp->shift;
 695
 696     if (malloc_junk)
 697         memset((u_char*)bp->page + k, SOME_JUNK, bp->size);
 698
 699     return (u_char *)bp->page + k;
 700 }
 701
 702 /*
 703  * Allocate a piece of memory
 704  */
 705 static void *
 706 imalloc(size_t size)
 707 {
 708     void *result;
 709
 710     if (suicide)
 711         abort();
 712
 713     if ((size + malloc_pagesize) < size)        /* Check for overflow */
 714         result = 0;
 715     else if (size <= malloc_maxsize)
 716         result =  malloc_bytes(size);
 717     else
 718         result =  malloc_pages(size);
 719
 720     if (malloc_zero && result)
 721         memset(result, 0, size);
 722
 723     return result;
 724 }
 725
 726 /*
 727  * Change the size of an allocation.
 728  */
 729 static void *
 730 irealloc(void *ptr, size_t size)
 731 {
 732     void *p;
 733     u_long osize, index;
 734     struct pginfo **mp;
 735     int i;
 736
 737     if (suicide)
 738         abort();
 739
 740     index = ptr2index(ptr);
 741
 742     if (index < malloc_pageshift) {
 743         wrtwarning("junk pointer, too low to make sense\n");
 744         return 0;
 745     }
 746
 747     if (index > last_index) {
 748         wrtwarning("junk pointer, too high to make sense\n");
 749         return 0;
 750     }
 751
 752     mp = &page_dir[index];
 753
 754     if (*mp == MALLOC_FIRST) {                  /* Page allocation */
 755
 756         /* Check the pointer */
 757         if ((u_long)ptr & malloc_pagemask) {
 758             wrtwarning("modified (page-) pointer\n");
 759             return 0;
 760         }
 761
 762         /* Find the size in bytes */
 763         for (osize = malloc_pagesize; *++mp == MALLOC_FOLLOW;)
 764             osize += malloc_pagesize;
 765
 766         if (!malloc_realloc &&                  /* unless we have to, */
 767           size <= osize &&                      /* .. or are too small, */
 768           size > (osize - malloc_pagesize)) {   /* .. or can free a page, */
 769             return ptr;                         /* don't do anything. */
 770         }
 771
 772     } else if (*mp >= MALLOC_MAGIC) {           /* Chunk allocation */
 773
 774         /* Check the pointer for sane values */
 775         if (((u_long)ptr & ((*mp)->size-1))) {
 776             wrtwarning("modified (chunk-) pointer\n");
 777             return 0;
 778         }
 779
 780         /* Find the chunk index in the page */
 781         i = ((u_long)ptr & malloc_pagemask) >> (*mp)->shift;
 782
 783         /* Verify that it isn't a free chunk already */
 784         if ((*mp)->bits[i/MALLOC_BITS] & (1<<(i%MALLOC_BITS))) {
 785             wrtwarning("chunk is already free\n");
 786             return 0;
 787         }
 788
 789         osize = (*mp)->size;
 790
 791         if (!malloc_realloc &&          /* Unless we have to, */
 792           size < osize &&               /* ..or are too small, */
 793           (size > osize/2 ||            /* ..or could use a smaller size, */
 794           osize == malloc_minsize)) {   /* ..(if there is one) */
 795             return ptr;                 /* ..Don't do anything */
 796         }
 797
 798     } else {
 799         wrtwarning("pointer to wrong page\n");
 800         return 0;
 801     }
 802
 803     p = imalloc(size);
 804
 805     if (p) {
 806         /* copy the lesser of the two sizes, and free the old one */
 807         if (!size || !osize)
 808             ;
 809         else if (osize < size)
 810             memcpy(p, ptr, osize);
 811         else
 812             memcpy(p, ptr, size);
 813         ifree(ptr);
 814     }
 815     return p;
 816 }
 817
 818 /*
 819  * Free a sequence of pages
 820  */
 821
 822 static __inline__ void
 823 free_pages(void *ptr, u_long index, struct pginfo *info)
 824 {
 825     u_long i;
 826     struct pgfree *pf, *pt=0;
 827     u_long l;
 828     void *tail;
 829
 830     if (info == MALLOC_FREE) {
 831         wrtwarning("page is already free\n");
 832         return;
 833     }
 834
 835     if (info != MALLOC_FIRST) {
 836         wrtwarning("pointer to wrong page\n");
 837         return;
 838     }
 839
 840     if ((u_long)ptr & malloc_pagemask) {
 841         wrtwarning("modified (page-) pointer\n");
 842         return;
 843     }
 844
 845     /* Count how many pages and mark them free at the same time */
 846     page_dir[index] = MALLOC_FREE;
 847     for (i = 1; page_dir[index+i] == MALLOC_FOLLOW; i++)
 848         page_dir[index + i] = MALLOC_FREE;
 849
 850     l = i << malloc_pageshift;
 851
 852     if (malloc_junk)
 853         memset(ptr, SOME_JUNK, l);
 854
 855     if (malloc_hint)
 856         madvise(ptr, l, MADV_FREE);
 857
 858     tail = (char *)ptr+l;
 859
 860     /* add to free-list */
 861     if (!px)
 862         px = imalloc(sizeof *pt);       /* This cannot fail... */
 863     px->page = ptr;
 864     px->end =  tail;
 865     px->size = l;
 866     if (!free_list.next) {
 867
 868         /* Nothing on free list, put this at head */
 869         px->next = free_list.next;
 870         px->prev = &free_list;
 871         free_list.next = px;
 872         pf = px;
 873         px = 0;
 874
 875     } else {
 876
 877         /* Find the right spot, leave pf pointing to the modified entry. */
 878         tail = (char *)ptr+l;
 879
 880         for(pf = free_list.next; pf->end < ptr && pf->next; pf = pf->next)
 881             ; /* Race ahead here */
 882
 883         if (pf->page > tail) {
 884             /* Insert before entry */
 885             px->next = pf;
 886             px->prev = pf->prev;
 887             pf->prev = px;
 888             px->prev->next = px;
 889             pf = px;
 890             px = 0;
 891         } else if (pf->end == ptr ) {
 892             /* Append to the previous entry */
 893             pf->end = (char *)pf->end + l;
 894             pf->size += l;
 895             if (pf->next && pf->end == pf->next->page ) {
 896                 /* And collapse the next too. */
 897                 pt = pf->next;
 898                 pf->end = pt->end;
 899                 pf->size += pt->size;
 900                 pf->next = pt->next;
 901                 if (pf->next)
 902                     pf->next->prev = pf;
 903             }
 904         } else if (pf->page == tail) {
 905             /* Prepend to entry */
 906             pf->size += l;
 907             pf->page = ptr;
 908         } else if (!pf->next) {
 909             /* Append at tail of chain */
 910             px->next = 0;
 911             px->prev = pf;
 912             pf->next = px;
 913             pf = px;
 914             px = 0;
 915         } else {
 916             wrterror("freelist is destroyed\n");
 917         }
 918     }
 919
 920     /* Return something to OS ? */
 921     if (!pf->next &&                            /* If we're the last one, */
 922       pf->size > malloc_cache &&                /* ..and the cache is full, */
 923       pf->end == malloc_brk &&                  /* ..and none behind us, */
 924       malloc_brk == sbrk(0)) {                  /* ..and it's OK to do... */
 925
 926         /*
 927          * Keep the cache intact.  Notice that the '>' above guarantees that
 928          * the pf will always have at least one page afterwards.
 929          */
 930         pf->end = (char *)pf->page + malloc_cache;
 931         pf->size = malloc_cache;
 932
 933         brk(pf->end);
 934         malloc_brk = pf->end;
 935
 936         index = ptr2index(pf->end);
 937         last_index = index - 1;
 938
 939         for(i=index;i <= last_index;)
 940             page_dir[i++] = MALLOC_NOT_MINE;
 941
 942         /* XXX: We could realloc/shrink the pagedir here I guess. */
 943     }
 944     if (pt)
 945         ifree(pt);
 946 }
 947
 948 /*
 949  * Free a chunk, and possibly the page it's on, if the page becomes empty.
 950  */
 951
 952 static __inline__ void
 953 free_bytes(void *ptr, u_long index, struct pginfo *info)
 954 {
 955     int i;
 956     struct pginfo **mp;
 957     void *vp;
 958
 959     /* Find the chunk number on the page */
 960     i = ((u_long)ptr & malloc_pagemask) >> info->shift;
 961
 962     if (((u_long)ptr & (info->size-1))) {
 963         wrtwarning("modified (chunk-) pointer\n");
 964         return;
 965     }
 966
 967     if (info->bits[i/MALLOC_BITS] & (1<<(i%MALLOC_BITS))) {
 968         wrtwarning("chunk is already free\n");
 969         return;
 970     }
 971
 972     if (malloc_junk)
 973         memset(ptr, SOME_JUNK, info->size);
 974
 975     info->bits[i/MALLOC_BITS] |= 1<<(i%MALLOC_BITS);
 976     info->free++;
 977
 978     mp = page_dir + info->shift;
 979
 980     if (info->free == 1) {
 981
 982         /* Page became non-full */
 983
 984         mp = page_dir + info->shift;
 985         /* Insert in address order */
 986         while (*mp && (*mp)->next && (*mp)->next->page < info->page)
 987             mp = &(*mp)->next;
 988         info->next = *mp;
 989         *mp = info;
 990         return;
 991     }
 992
 993     if (info->free != info->total)
 994         return;
 995
 996     /* Find & remove this page in the queue */
 997     while (*mp != info) {
 998         mp = &((*mp)->next);
 999 #ifdef EXTRA_SANITY
1000         if (!*mp)
1001                 wrterror("(ES): Not on queue\n");
1002 #endif /* EXTRA_SANITY */
1003     }
1004     *mp = info->next;
1005
1006     /* Free the page & the info structure if need be */
1007     page_dir[ptr2index(info->page)] = MALLOC_FIRST;
1008     vp = info->page;            /* Order is important ! */
1009     if(vp != (void*)info)
1010         ifree(info);
1011     ifree(vp);
1012 }
1013
1014 static void
1015 ifree(void *ptr)
1016 {
1017     struct pginfo *info;
1018     u_long index;
1019
1020     /* This is legal */
1021     if (!ptr)
1022         return;
1023
1024     if (!malloc_started) {
1025         wrtwarning("malloc() has never been called\n");
1026         return;
1027     }
1028
1029     /* If we're already sinking, don't make matters any worse. */
1030     if (suicide)
1031         return;
1032
1033     index = ptr2index(ptr);
1034
1035     if (index < malloc_pageshift) {
1036         wrtwarning("junk pointer, too low to make sense\n");
1037         return;
1038     }
1039
1040     if (index > last_index) {
1041         wrtwarning("junk pointer, too high to make sense\n");
1042         return;
1043     }
1044
1045     info = page_dir[index];
1046
1047     if (info < MALLOC_MAGIC)
1048         free_pages(ptr, index, info);
1049     else
1050         free_bytes(ptr, index, info);
1051     return;
1052 }
1053
1054 /*
1055  * These are the public exported interface routines.
1056  */
1057
1058
1059 void *
1060 malloc(size_t size)
1061 {
1062     void *r;
1063
1064     THREAD_LOCK();
1065     malloc_func = " in malloc():";
1066     if (malloc_active++) {
1067         wrtwarning("recursive call\n");
1068         malloc_active--;
1069         THREAD_UNLOCK();
1070         return (0);
1071     }
1072     if (!malloc_started)
1073         malloc_init();
1074     if (malloc_sysv && !size)
1075         r = 0;
1076     else
1077         r = imalloc(size);
1078     UTRACE(0, size, r);
1079     malloc_active--;
1080     THREAD_UNLOCK();
1081     if (malloc_xmalloc && !r)
1082         wrterror("out of memory\n");
1083     return (r);
1084 }
1085
1086 void
1087 free(void *ptr)
1088 {
1089     THREAD_LOCK();
1090     malloc_func = " in free():";
1091     if (malloc_active++) {
1092         wrtwarning("recursive call\n");
1093         malloc_active--;
1094         THREAD_UNLOCK();
1095         return;
1096     } else {
1097         ifree(ptr);
1098         UTRACE(ptr, 0, 0);
1099     }
1100     malloc_active--;
1101     THREAD_UNLOCK();
1102     return;
1103 }
1104
1105 void *
1106 realloc(void *ptr, size_t size)
1107 {
1108     void *r;
1109     int err = 0;
1110
1111     THREAD_LOCK();
1112     malloc_func = " in realloc():";
1113     if (malloc_active++) {
1114         wrtwarning("recursive call\n");
1115         malloc_active--;
1116         THREAD_UNLOCK();
1117         return (0);
1118     }
1119     if (ptr && !malloc_started) {
1120         wrtwarning("malloc() has never been called\n");
1121         ptr = 0;
1122     }
1123     if (!malloc_started)
1124         malloc_init();
1125     if (malloc_sysv && !size) {
1126         ifree(ptr);
1127         r = 0;
1128     } else if (!ptr) {
1129         r = imalloc(size);
1130         err = (r == NULL);
1131     } else {
1132         r = irealloc(ptr, size);
1133         err = (r == NULL);
1134     }
1135     UTRACE(ptr, size, r);
1136     malloc_active--;
1137     THREAD_UNLOCK();
1138     if (malloc_xmalloc && err)
1139         wrterror("out of memory\n");
1140     return (r);
1141 }
1142