1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/nsprpub/pr/src/malloc/prmalloc.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,1142 @@
1.4 +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
1.5 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.6 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.7 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.8 +
1.9 +#include "primpl.h"
1.10 +
1.11 +/*
1.12 +** We override malloc etc. on any platform which has preemption +
1.13 +** nspr20 user level threads. When we're debugging, we can make our
1.14 +** version of malloc fail occasionally.
1.15 +*/
1.16 +#ifdef _PR_OVERRIDE_MALLOC
1.17 +
1.18 +/*
1.19 +** Thread safe version of malloc, calloc, realloc, free
1.20 +*/
1.21 +#include <stdarg.h>
1.22 +
1.23 +#ifdef DEBUG
1.24 +#define SANITY
1.25 +#define EXTRA_SANITY
1.26 +#else
1.27 +#undef SANITY
1.28 +#undef EXTRA_SANITY
1.29 +#endif
1.30 +
1.31 +/* Forward decls */
1.32 +void *_PR_UnlockedMalloc(size_t size);
1.33 +void _PR_UnlockedFree(void *ptr);
1.34 +void *_PR_UnlockedRealloc(void *ptr, size_t size);
1.35 +void *_PR_UnlockedCalloc(size_t n, size_t elsize);
1.36 +
1.37 +/************************************************************************/
1.38 +
1.39 +/*
1.40 + * ----------------------------------------------------------------------------
1.41 + * "THE BEER-WARE LICENSE" (Revision 42):
1.42 + * <phk@FreeBSD.ORG> wrote this file. As long as you retain this notice you
1.43 + * can do whatever you want with this stuff. If we meet some day, and you think
1.44 + * this stuff is worth it, you can buy me a beer in return. Poul-Henning Kamp
1.45 + * ----------------------------------------------------------------------------
1.46 + *
1.47 + */
1.48 +
1.49 +/*
1.50 + * Defining SANITY will enable some checks which will tell you if the users
1.51 + * program did botch something
1.52 + */
1.53 +
1.54 +/*
1.55 + * Defining EXTRA_SANITY will enable some checks which are mostly related
1.56 + * to internal conditions in malloc.c
1.57 + */
1.58 +
1.59 +/*
1.60 + * Very verbose progress on stdout...
1.61 + */
1.62 +#if 0
1.63 +# define TRACE(foo) printf foo
1.64 +static int malloc_event;
1.65 +#else
1.66 +# define TRACE(foo)
1.67 +#endif
1.68 +
1.69 +/* XXX Pick a number, any number */
1.70 +# define malloc_pagesize 4096UL
1.71 +# define malloc_pageshift 12UL
1.72 +
1.73 +#ifdef XP_UNIX
1.74 +#include <stdio.h>
1.75 +#include <stdlib.h>
1.76 +#include <unistd.h>
1.77 +#include <string.h>
1.78 +#include <errno.h>
1.79 +#include <sys/types.h>
1.80 +#include <sys/mman.h>
1.81 +#endif
1.82 +
1.83 +/*
1.84 + * This structure describes a page's worth of chunks.
1.85 + */
1.86 +
1.87 +struct pginfo {
1.88 + struct pginfo *next; /* next on the free list */
1.89 + char *page; /* Pointer to the page */
1.90 + u_short size; /* size of this page's chunks */
1.91 + u_short shift; /* How far to shift for this size chunks */
1.92 + u_short free; /* How many free chunks */
1.93 + u_short total; /* How many chunk */
1.94 + u_long bits[1]; /* Which chunks are free */
1.95 +};
1.96 +
1.97 +struct pgfree {
1.98 + struct pgfree *next; /* next run of free pages */
1.99 + struct pgfree *prev; /* prev run of free pages */
1.100 + char *page; /* pointer to free pages */
1.101 + char *end; /* pointer to end of free pages */
1.102 + u_long size; /* number of bytes free */
1.103 +};
1.104 +
1.105 +/*
1.106 + * How many bits per u_long in the bitmap.
1.107 + * Change only if not 8 bits/byte
1.108 + */
1.109 +#define MALLOC_BITS (8*sizeof(u_long))
1.110 +
1.111 +/*
1.112 + * Magic values to put in the page_directory
1.113 + */
1.114 +#define MALLOC_NOT_MINE ((struct pginfo*) 0)
1.115 +#define MALLOC_FREE ((struct pginfo*) 1)
1.116 +#define MALLOC_FIRST ((struct pginfo*) 2)
1.117 +#define MALLOC_FOLLOW ((struct pginfo*) 3)
1.118 +#define MALLOC_MAGIC ((struct pginfo*) 4)
1.119 +
1.120 +/*
1.121 + * Set to one when malloc_init has been called
1.122 + */
1.123 +static unsigned initialized;
1.124 +
1.125 +/*
1.126 + * The size of a page.
1.127 + * Must be a integral multiplum of the granularity of mmap(2).
1.128 + * Your toes will curl if it isn't a power of two
1.129 + */
1.130 +#define malloc_pagemask ((malloc_pagesize)-1)
1.131 +
1.132 +/*
1.133 + * The size of the largest chunk.
1.134 + * Half a page.
1.135 + */
1.136 +#define malloc_maxsize ((malloc_pagesize)>>1)
1.137 +
1.138 +/*
1.139 + * malloc_pagesize == 1 << malloc_pageshift
1.140 + */
1.141 +#ifndef malloc_pageshift
1.142 +static unsigned malloc_pageshift;
1.143 +#endif /* malloc_pageshift */
1.144 +
1.145 +/*
1.146 + * The smallest allocation we bother about.
1.147 + * Must be power of two
1.148 + */
1.149 +#ifndef malloc_minsize
1.150 +static unsigned malloc_minsize;
1.151 +#endif /* malloc_minsize */
1.152 +
1.153 +/*
1.154 + * The largest chunk we care about.
1.155 + * Must be smaller than pagesize
1.156 + * Must be power of two
1.157 + */
1.158 +#ifndef malloc_maxsize
1.159 +static unsigned malloc_maxsize;
1.160 +#endif /* malloc_maxsize */
1.161 +
1.162 +#ifndef malloc_cache
1.163 +static unsigned malloc_cache;
1.164 +#endif /* malloc_cache */
1.165 +
1.166 +/*
1.167 + * The offset from pagenumber to index into the page directory
1.168 + */
1.169 +static u_long malloc_origo;
1.170 +
1.171 +/*
1.172 + * The last index in the page directory we care about
1.173 + */
1.174 +static u_long last_index;
1.175 +
1.176 +/*
1.177 + * Pointer to page directory.
1.178 + * Allocated "as if with" malloc
1.179 + */
1.180 +static struct pginfo **page_dir;
1.181 +
1.182 +/*
1.183 + * How many slots in the page directory
1.184 + */
1.185 +static unsigned malloc_ninfo;
1.186 +
1.187 +/*
1.188 + * Free pages line up here
1.189 + */
1.190 +static struct pgfree free_list;
1.191 +
1.192 +/*
1.193 + * Abort() if we fail to get VM ?
1.194 + */
1.195 +static int malloc_abort;
1.196 +
1.197 +#ifdef SANITY
1.198 +/*
1.199 + * Are we trying to die ?
1.200 + */
1.201 +static int suicide;
1.202 +#endif
1.203 +
1.204 +/*
1.205 + * dump statistics
1.206 + */
1.207 +static int malloc_stats;
1.208 +
1.209 +/*
1.210 + * always realloc ?
1.211 + */
1.212 +static int malloc_realloc;
1.213 +
1.214 +/*
1.215 + * my last break.
1.216 + */
1.217 +static void *malloc_brk;
1.218 +
1.219 +/*
1.220 + * one location cache for free-list holders
1.221 + */
1.222 +static struct pgfree *px;
1.223 +
1.224 +static int set_pgdir(void *ptr, struct pginfo *info);
1.225 +static int extend_page_directory(u_long index);
1.226 +
1.227 +#ifdef SANITY
1.228 +void
1.229 +malloc_dump(FILE *fd)
1.230 +{
1.231 + struct pginfo **pd;
1.232 + struct pgfree *pf;
1.233 + int j;
1.234 +
1.235 + pd = page_dir;
1.236 +
1.237 + /* print out all the pages */
1.238 + for(j=0;j<=last_index;j++) {
1.239 + fprintf(fd,"%08lx %5d ",(j+malloc_origo) << malloc_pageshift,j);
1.240 + if (pd[j] == MALLOC_NOT_MINE) {
1.241 + for(j++;j<=last_index && pd[j] == MALLOC_NOT_MINE;j++)
1.242 + ;
1.243 + j--;
1.244 + fprintf(fd,".. %5d not mine\n", j);
1.245 + } else if (pd[j] == MALLOC_FREE) {
1.246 + for(j++;j<=last_index && pd[j] == MALLOC_FREE;j++)
1.247 + ;
1.248 + j--;
1.249 + fprintf(fd,".. %5d free\n", j);
1.250 + } else if (pd[j] == MALLOC_FIRST) {
1.251 + for(j++;j<=last_index && pd[j] == MALLOC_FOLLOW;j++)
1.252 + ;
1.253 + j--;
1.254 + fprintf(fd,".. %5d in use\n", j);
1.255 + } else if (pd[j] < MALLOC_MAGIC) {
1.256 + fprintf(fd,"(%p)\n", pd[j]);
1.257 + } else {
1.258 + fprintf(fd,"%p %d (of %d) x %d @ %p --> %p\n",
1.259 + pd[j],pd[j]->free, pd[j]->total,
1.260 + pd[j]->size, pd[j]->page, pd[j]->next);
1.261 + }
1.262 + }
1.263 +
1.264 + for(pf=free_list.next; pf; pf=pf->next) {
1.265 + fprintf(fd,"Free: @%p [%p...%p[ %ld ->%p <-%p\n",
1.266 + pf,pf->page,pf->end,pf->size,pf->prev,pf->next);
1.267 + if (pf == pf->next) {
1.268 + fprintf(fd,"Free_list loops.\n");
1.269 + break;
1.270 + }
1.271 + }
1.272 +
1.273 + /* print out various info */
1.274 + fprintf(fd,"Minsize\t%d\n",malloc_minsize);
1.275 + fprintf(fd,"Maxsize\t%ld\n",malloc_maxsize);
1.276 + fprintf(fd,"Pagesize\t%ld\n",malloc_pagesize);
1.277 + fprintf(fd,"Pageshift\t%ld\n",malloc_pageshift);
1.278 + fprintf(fd,"FirstPage\t%ld\n",malloc_origo);
1.279 + fprintf(fd,"LastPage\t%ld %lx\n",last_index+malloc_pageshift,
1.280 + (last_index + malloc_pageshift) << malloc_pageshift);
1.281 + fprintf(fd,"Break\t%ld\n",(u_long)sbrk(0) >> malloc_pageshift);
1.282 +}
1.283 +
1.284 +static void wrterror(char *fmt, ...)
1.285 +{
1.286 + char *q = "malloc() error: ";
1.287 + char buf[100];
1.288 + va_list ap;
1.289 +
1.290 + suicide = 1;
1.291 +
1.292 + va_start(ap, fmt);
1.293 + PR_vsnprintf(buf, sizeof(buf), fmt, ap);
1.294 + va_end(ap);
1.295 + fputs(q, stderr);
1.296 + fputs(buf, stderr);
1.297 +
1.298 + malloc_dump(stderr);
1.299 + PR_Abort();
1.300 +}
1.301 +
1.302 +static void wrtwarning(char *fmt, ...)
1.303 +{
1.304 + char *q = "malloc() warning: ";
1.305 + char buf[100];
1.306 + va_list ap;
1.307 +
1.308 + va_start(ap, fmt);
1.309 + PR_vsnprintf(buf, sizeof(buf), fmt, ap);
1.310 + va_end(ap);
1.311 + fputs(q, stderr);
1.312 + fputs(buf, stderr);
1.313 +}
1.314 +#endif /* SANITY */
1.315 +
1.316 +
1.317 +/*
1.318 + * Allocate a number of pages from the OS
1.319 + */
1.320 +static caddr_t
1.321 +map_pages(int pages, int update)
1.322 +{
1.323 + caddr_t result,tail;
1.324 +
1.325 + result = ((caddr_t)sbrk(0)) + malloc_pagemask - 1;
1.326 + result = (caddr_t) ((u_long)result & ~malloc_pagemask);
1.327 + tail = result + (pages << malloc_pageshift);
1.328 + if (!brk(tail)) {
1.329 + last_index = ((u_long)tail >> malloc_pageshift) - malloc_origo -1;
1.330 + malloc_brk = tail;
1.331 + TRACE(("%6d S %p .. %p\n",malloc_event++, result, tail));
1.332 + if (!update || last_index < malloc_ninfo ||
1.333 + extend_page_directory(last_index))
1.334 + return result;
1.335 + }
1.336 + TRACE(("%6d s %d %p %d\n",malloc_event++,pages,sbrk(0),errno));
1.337 +#ifdef EXTRA_SANITY
1.338 + wrterror("map_pages fails\n");
1.339 +#endif
1.340 + return 0;
1.341 +}
1.342 +
1.343 +#define set_bit(_pi,_bit) \
1.344 + (_pi)->bits[(_bit)/MALLOC_BITS] |= 1L<<((_bit)%MALLOC_BITS)
1.345 +
1.346 +#define clr_bit(_pi,_bit) \
1.347 + (_pi)->bits[(_bit)/MALLOC_BITS] &= ~(1L<<((_bit)%MALLOC_BITS));
1.348 +
1.349 +#define tst_bit(_pi,_bit) \
1.350 + ((_pi)->bits[(_bit)/MALLOC_BITS] & (1L<<((_bit)%MALLOC_BITS)))
1.351 +
1.352 +/*
1.353 + * Extend page directory
1.354 + */
1.355 +static int
1.356 +extend_page_directory(u_long index)
1.357 +{
1.358 + struct pginfo **young, **old;
1.359 + int i;
1.360 +
1.361 + TRACE(("%6d E %lu\n",malloc_event++,index));
1.362 +
1.363 + /* Make it this many pages */
1.364 + i = index * sizeof *page_dir;
1.365 + i /= malloc_pagesize;
1.366 + i += 2;
1.367 +
1.368 + /* Get new pages, if you used this much mem you don't care :-) */
1.369 + young = (struct pginfo**) map_pages(i,0);
1.370 + if (!young)
1.371 + return 0;
1.372 +
1.373 + /* Copy the old stuff */
1.374 + memset(young, 0, i * malloc_pagesize);
1.375 + memcpy(young, page_dir,
1.376 + malloc_ninfo * sizeof *page_dir);
1.377 +
1.378 + /* register the new size */
1.379 + malloc_ninfo = i * malloc_pagesize / sizeof *page_dir;
1.380 +
1.381 + /* swap the pointers */
1.382 + old = page_dir;
1.383 + page_dir = young;
1.384 +
1.385 + /* Mark the pages */
1.386 + index = ((u_long)young >> malloc_pageshift) - malloc_origo;
1.387 + page_dir[index] = MALLOC_FIRST;
1.388 + while (--i) {
1.389 + page_dir[++index] = MALLOC_FOLLOW;
1.390 + }
1.391 +
1.392 + /* Now free the old stuff */
1.393 + _PR_UnlockedFree(old);
1.394 + return 1;
1.395 +}
1.396 +
1.397 +/*
1.398 + * Set entry in page directory.
1.399 + * Extend page directory if need be.
1.400 + */
1.401 +static int
1.402 +set_pgdir(void *ptr, struct pginfo *info)
1.403 +{
1.404 + u_long index = ((u_long)ptr >> malloc_pageshift) - malloc_origo;
1.405 +
1.406 + if (index >= malloc_ninfo && !extend_page_directory(index))
1.407 + return 0;
1.408 + page_dir[index] = info;
1.409 + return 1;
1.410 +}
1.411 +
1.412 +/*
1.413 + * Initialize the world
1.414 + */
1.415 +static void
1.416 +malloc_init (void)
1.417 +{
1.418 + int i;
1.419 + char *p;
1.420 +
1.421 + TRACE(("%6d I\n",malloc_event++));
1.422 +#ifdef DEBUG
1.423 + for (p=getenv("MALLOC_OPTIONS"); p && *p; p++) {
1.424 + switch (*p) {
1.425 + case 'a': malloc_abort = 0; break;
1.426 + case 'A': malloc_abort = 1; break;
1.427 + case 'd': malloc_stats = 0; break;
1.428 + case 'D': malloc_stats = 1; break;
1.429 + case 'r': malloc_realloc = 0; break;
1.430 + case 'R': malloc_realloc = 1; break;
1.431 + default:
1.432 + wrtwarning("Unknown chars in MALLOC_OPTIONS\n");
1.433 + break;
1.434 + }
1.435 + }
1.436 +#endif
1.437 +
1.438 +#ifndef malloc_pagesize
1.439 + /* determine our pagesize */
1.440 + malloc_pagesize = getpagesize();
1.441 +#endif /* malloc_pagesize */
1.442 +
1.443 +#ifndef malloc_pageshift
1.444 + /* determine how much we shift by to get there */
1.445 + for (i = malloc_pagesize; i > 1; i >>= 1)
1.446 + malloc_pageshift++;
1.447 +#endif /* malloc_pageshift */
1.448 +
1.449 +#ifndef malloc_cache
1.450 + malloc_cache = 50 << malloc_pageshift;
1.451 +#endif /* malloc_cache */
1.452 +
1.453 +#ifndef malloc_minsize
1.454 + /*
1.455 + * find the smallest size allocation we will bother about.
1.456 + * this is determined as the smallest allocation that can hold
1.457 + * it's own pginfo;
1.458 + */
1.459 + i = 2;
1.460 + for(;;) {
1.461 + int j;
1.462 +
1.463 + /* Figure out the size of the bits */
1.464 + j = malloc_pagesize/i;
1.465 + j /= 8;
1.466 + if (j < sizeof(u_long))
1.467 + j = sizeof (u_long);
1.468 + if (sizeof(struct pginfo) + j - sizeof (u_long) <= i)
1.469 + break;
1.470 + i += i;
1.471 + }
1.472 + malloc_minsize = i;
1.473 +#endif /* malloc_minsize */
1.474 +
1.475 +
1.476 + /* Allocate one page for the page directory */
1.477 + page_dir = (struct pginfo **) map_pages(1,0);
1.478 +#ifdef SANITY
1.479 + if (!page_dir)
1.480 + wrterror("fatal: my first mmap failed. (check limits ?)\n");
1.481 +#endif
1.482 +
1.483 + /*
1.484 + * We need a maximum of malloc_pageshift buckets, steal these from the
1.485 + * front of the page_directory;
1.486 + */
1.487 + malloc_origo = (u_long) page_dir >> malloc_pageshift;
1.488 + malloc_origo -= malloc_pageshift;
1.489 +
1.490 + /* Clear it */
1.491 + memset(page_dir,0,malloc_pagesize);
1.492 +
1.493 + /* Find out how much it tells us */
1.494 + malloc_ninfo = malloc_pagesize / sizeof *page_dir;
1.495 +
1.496 + /* Plug the page directory into itself */
1.497 + i = set_pgdir(page_dir,MALLOC_FIRST);
1.498 +#ifdef SANITY
1.499 + if (!i)
1.500 + wrterror("fatal: couldn't set myself in the page directory\n");
1.501 +#endif
1.502 +
1.503 + /* Been here, done that */
1.504 + initialized++;
1.505 +}
1.506 +
1.507 +/*
1.508 + * Allocate a number of complete pages
1.509 + */
1.510 +static void *malloc_pages(size_t size)
1.511 +{
1.512 + void *p,*delay_free = 0;
1.513 + int i;
1.514 + struct pgfree *pf;
1.515 + u_long index;
1.516 +
1.517 + /* How many pages ? */
1.518 + size += (malloc_pagesize-1);
1.519 + size &= ~malloc_pagemask;
1.520 +
1.521 + p = 0;
1.522 + /* Look for free pages before asking for more */
1.523 + for(pf = free_list.next; pf; pf = pf->next) {
1.524 +#ifdef EXTRA_SANITY
1.525 + if (pf->page == pf->end)
1.526 + wrterror("zero entry on free_list\n");
1.527 + if (pf->page > pf->end) {
1.528 + TRACE(("%6d !s %p %p %p <%d>\n",malloc_event++,
1.529 + pf,pf->page,pf->end,__LINE__));
1.530 + wrterror("sick entry on free_list\n");
1.531 + }
1.532 + if ((void*)pf->page >= (void*)sbrk(0))
1.533 + wrterror("entry on free_list past brk\n");
1.534 + if (page_dir[((u_long)pf->page >> malloc_pageshift) - malloc_origo]
1.535 + != MALLOC_FREE) {
1.536 + TRACE(("%6d !f %p %p %p <%d>\n",malloc_event++,
1.537 + pf,pf->page,pf->end,__LINE__));
1.538 + wrterror("non-free first page on free-list\n");
1.539 + }
1.540 + if (page_dir[((u_long)pf->end >> malloc_pageshift) - 1 - malloc_origo]
1.541 + != MALLOC_FREE)
1.542 + wrterror("non-free last page on free-list\n");
1.543 +#endif /* EXTRA_SANITY */
1.544 + if (pf->size < size)
1.545 + continue;
1.546 + else if (pf->size == size) {
1.547 + p = pf->page;
1.548 + if (pf->next)
1.549 + pf->next->prev = pf->prev;
1.550 + pf->prev->next = pf->next;
1.551 + delay_free = pf;
1.552 + break;
1.553 + } else {
1.554 + p = pf->page;
1.555 + pf->page += size;
1.556 + pf->size -= size;
1.557 + break;
1.558 + }
1.559 + }
1.560 +#ifdef EXTRA_SANITY
1.561 + if (p && page_dir[((u_long)p >> malloc_pageshift) - malloc_origo]
1.562 + != MALLOC_FREE) {
1.563 + wrterror("allocated non-free page on free-list\n");
1.564 + }
1.565 +#endif /* EXTRA_SANITY */
1.566 +
1.567 + size >>= malloc_pageshift;
1.568 +
1.569 + /* Map new pages */
1.570 + if (!p)
1.571 + p = map_pages(size,1);
1.572 +
1.573 + if (p) {
1.574 + /* Mark the pages in the directory */
1.575 + index = ((u_long)p >> malloc_pageshift) - malloc_origo;
1.576 + page_dir[index] = MALLOC_FIRST;
1.577 + for (i=1;i<size;i++)
1.578 + page_dir[index+i] = MALLOC_FOLLOW;
1.579 + }
1.580 + if (delay_free) {
1.581 + if (!px)
1.582 + px = (struct pgfree*)delay_free;
1.583 + else
1.584 + _PR_UnlockedFree(delay_free);
1.585 + }
1.586 + return p;
1.587 +}
1.588 +
1.589 +/*
1.590 + * Allocate a page of fragments
1.591 + */
1.592 +
1.593 +static int
1.594 +malloc_make_chunks(int bits)
1.595 +{
1.596 + struct pginfo *bp;
1.597 + void *pp;
1.598 + int i,k,l;
1.599 +
1.600 + /* Allocate a new bucket */
1.601 + pp = malloc_pages(malloc_pagesize);
1.602 + if (!pp)
1.603 + return 0;
1.604 + l = sizeof *bp - sizeof(u_long);
1.605 + l += sizeof(u_long) *
1.606 + (((malloc_pagesize >> bits)+MALLOC_BITS-1) / MALLOC_BITS);
1.607 + if ((1<<(bits)) <= l+l) {
1.608 + bp = (struct pginfo *)pp;
1.609 + } else {
1.610 + bp = (struct pginfo *)_PR_UnlockedMalloc(l);
1.611 + }
1.612 + if (!bp)
1.613 + return 0;
1.614 + bp->size = (1<<bits);
1.615 + bp->shift = bits;
1.616 + bp->total = bp->free = malloc_pagesize >> bits;
1.617 + bp->next = page_dir[bits];
1.618 + bp->page = (char*)pp;
1.619 + i = set_pgdir(pp,bp);
1.620 + if (!i)
1.621 + return 0;
1.622 +
1.623 + /* We can safely assume that there is nobody in this chain */
1.624 + page_dir[bits] = bp;
1.625 +
1.626 + /* set all valid bits in the bits */
1.627 + k = bp->total;
1.628 + i = 0;
1.629 +/*
1.630 + for(;k-i >= MALLOC_BITS; i += MALLOC_BITS)
1.631 + bp->bits[i / MALLOC_BITS] = ~0;
1.632 +*/
1.633 + for(; i < k; i++)
1.634 + set_bit(bp,i);
1.635 +
1.636 + if (bp != pp)
1.637 + return 1;
1.638 +
1.639 + /* We may have used the first ones already */
1.640 + for(i=0;l > 0;i++) {
1.641 + clr_bit(bp,i);
1.642 + bp->free--;
1.643 + bp->total--;
1.644 + l -= (1 << bits);
1.645 + }
1.646 + return 1;
1.647 +}
1.648 +
1.649 +/*
1.650 + * Allocate a fragment
1.651 + */
1.652 +static void *malloc_bytes(size_t size)
1.653 +{
1.654 + size_t s;
1.655 + int j;
1.656 + struct pginfo *bp;
1.657 + int k;
1.658 + u_long *lp, bf;
1.659 +
1.660 + /* Don't bother with anything less than this */
1.661 + if (size < malloc_minsize) {
1.662 + size = malloc_minsize;
1.663 + }
1.664 +
1.665 + /* Find the right bucket */
1.666 + j = 1;
1.667 + s = size - 1;
1.668 + while (s >>= 1) {
1.669 + j++;
1.670 + }
1.671 +
1.672 + /* If it's empty, make a page more of that size chunks */
1.673 + if (!page_dir[j] && !malloc_make_chunks(j))
1.674 + return 0;
1.675 +
1.676 + /* Find first word of bitmap which isn't empty */
1.677 + bp = page_dir[j];
1.678 + for (lp = bp->bits; !*lp; lp++)
1.679 + ;
1.680 +
1.681 + /* Find that bit */
1.682 + bf = *lp;
1.683 + k = 0;
1.684 + while ((bf & 1) == 0) {
1.685 + bf >>= 1;
1.686 + k++;
1.687 + }
1.688 +
1.689 + *lp ^= 1L<<k; /* clear it */
1.690 + bp->free--;
1.691 + if (!bp->free) {
1.692 + page_dir[j] = bp->next;
1.693 + bp->next = 0;
1.694 + }
1.695 + k += (lp - bp->bits)*MALLOC_BITS;
1.696 + return bp->page + (k << bp->shift);
1.697 +}
1.698 +
1.699 +void *_PR_UnlockedMalloc(size_t size)
1.700 +{
1.701 + void *result;
1.702 +
1.703 + /* Round up to a multiple of 8 bytes */
1.704 + if (size & 7) {
1.705 + size = size + 8 - (size & 7);
1.706 + }
1.707 +
1.708 + if (!initialized)
1.709 + malloc_init();
1.710 +
1.711 +#ifdef SANITY
1.712 + if (suicide)
1.713 + PR_Abort();
1.714 +#endif
1.715 +
1.716 + if (size <= malloc_maxsize)
1.717 + result = malloc_bytes(size);
1.718 + else
1.719 + result = malloc_pages(size);
1.720 +#ifdef SANITY
1.721 + if (malloc_abort && !result)
1.722 + wrterror("malloc() returns NULL\n");
1.723 +#endif
1.724 + TRACE(("%6d M %p %d\n",malloc_event++,result,size));
1.725 +
1.726 + return result;
1.727 +}
1.728 +
1.729 +void *_PR_UnlockedMemalign(size_t alignment, size_t size)
1.730 +{
1.731 + void *result;
1.732 +
1.733 + /*
1.734 + * alignment has to be a power of 2
1.735 + */
1.736 +
1.737 + if ((size <= alignment) && (alignment <= malloc_maxsize))
1.738 + size = alignment;
1.739 + else
1.740 + size += alignment - 1;
1.741 +
1.742 + /* Round up to a multiple of 8 bytes */
1.743 + if (size & 7) {
1.744 + size = size + 8 - (size & 7);
1.745 + }
1.746 +
1.747 + if (!initialized)
1.748 + malloc_init();
1.749 +
1.750 +#ifdef SANITY
1.751 + if (suicide)
1.752 + abort();
1.753 +#endif
1.754 +
1.755 + if (size <= malloc_maxsize)
1.756 + result = malloc_bytes(size);
1.757 + else
1.758 + result = malloc_pages(size);
1.759 +#ifdef SANITY
1.760 + if (malloc_abort && !result)
1.761 + wrterror("malloc() returns NULL\n");
1.762 +#endif
1.763 + TRACE(("%6d A %p %d\n",malloc_event++,result,size));
1.764 +
1.765 + if ((u_long)result & (alignment - 1))
1.766 + return ((void *)(((u_long)result + alignment) & ~(alignment - 1)));
1.767 + else
1.768 + return result;
1.769 +}
1.770 +
1.771 +void *_PR_UnlockedCalloc(size_t n, size_t nelem)
1.772 +{
1.773 + void *p;
1.774 +
1.775 + /* Compute total size and then round up to a double word amount */
1.776 + n *= nelem;
1.777 + if (n & 7) {
1.778 + n = n + 8 - (n & 7);
1.779 + }
1.780 +
1.781 + /* Get the memory */
1.782 + p = _PR_UnlockedMalloc(n);
1.783 + if (p) {
1.784 + /* Zero it */
1.785 + memset(p, 0, n);
1.786 + }
1.787 + return p;
1.788 +}
1.789 +
1.790 +/*
1.791 + * Change an allocation's size
1.792 + */
1.793 +void *_PR_UnlockedRealloc(void *ptr, size_t size)
1.794 +{
1.795 + void *p;
1.796 + u_long osize,page,index,tmp_index;
1.797 + struct pginfo **mp;
1.798 +
1.799 + if (!initialized)
1.800 + malloc_init();
1.801 +
1.802 +#ifdef SANITY
1.803 + if (suicide)
1.804 + PR_Abort();
1.805 +#endif
1.806 +
1.807 + /* used as free() */
1.808 + TRACE(("%6d R %p %d\n",malloc_event++, ptr, size));
1.809 + if (ptr && !size) {
1.810 + _PR_UnlockedFree(ptr);
1.811 + return _PR_UnlockedMalloc (1);
1.812 + }
1.813 +
1.814 + /* used as malloc() */
1.815 + if (!ptr) {
1.816 + p = _PR_UnlockedMalloc(size);
1.817 + return p;
1.818 + }
1.819 +
1.820 + /* Find the page directory entry for the page in question */
1.821 + page = (u_long)ptr >> malloc_pageshift;
1.822 + index = page - malloc_origo;
1.823 +
1.824 + /*
1.825 + * check if memory was allocated by memalign
1.826 + */
1.827 + tmp_index = index;
1.828 + while (page_dir[tmp_index] == MALLOC_FOLLOW)
1.829 + tmp_index--;
1.830 + if (tmp_index != index) {
1.831 + /*
1.832 + * memalign-allocated memory
1.833 + */
1.834 + index = tmp_index;
1.835 + page = index + malloc_origo;
1.836 + ptr = (void *) (page << malloc_pageshift);
1.837 + }
1.838 + TRACE(("%6d R2 %p %d\n",malloc_event++, ptr, size));
1.839 +
1.840 + /* make sure it makes sense in some fashion */
1.841 + if (index < malloc_pageshift || index > last_index) {
1.842 +#ifdef SANITY
1.843 + wrtwarning("junk pointer passed to realloc()\n");
1.844 +#endif
1.845 + return 0;
1.846 + }
1.847 +
1.848 + /* find the size of that allocation, and see if we need to relocate */
1.849 + mp = &page_dir[index];
1.850 + if (*mp == MALLOC_FIRST) {
1.851 + osize = malloc_pagesize;
1.852 + while (mp[1] == MALLOC_FOLLOW) {
1.853 + osize += malloc_pagesize;
1.854 + mp++;
1.855 + }
1.856 + if (!malloc_realloc &&
1.857 + size < osize &&
1.858 + size > malloc_maxsize &&
1.859 + size > (osize - malloc_pagesize)) {
1.860 + return ptr;
1.861 + }
1.862 + } else if (*mp >= MALLOC_MAGIC) {
1.863 + osize = (*mp)->size;
1.864 + if (!malloc_realloc &&
1.865 + size < osize &&
1.866 + (size > (*mp)->size/2 || (*mp)->size == malloc_minsize)) {
1.867 + return ptr;
1.868 + }
1.869 + } else {
1.870 +#ifdef SANITY
1.871 + wrterror("realloc() of wrong page.\n");
1.872 +#endif
1.873 + }
1.874 +
1.875 + /* try to reallocate */
1.876 + p = _PR_UnlockedMalloc(size);
1.877 +
1.878 + if (p) {
1.879 + /* copy the lesser of the two sizes */
1.880 + if (osize < size)
1.881 + memcpy(p,ptr,osize);
1.882 + else
1.883 + memcpy(p,ptr,size);
1.884 + _PR_UnlockedFree(ptr);
1.885 + }
1.886 +#ifdef DEBUG
1.887 + else if (malloc_abort)
1.888 + wrterror("realloc() returns NULL\n");
1.889 +#endif
1.890 +
1.891 + return p;
1.892 +}
1.893 +
1.894 +/*
1.895 + * Free a sequence of pages
1.896 + */
1.897 +
1.898 +static void
1.899 +free_pages(char *ptr, u_long page, int index, struct pginfo *info)
1.900 +{
1.901 + int i;
1.902 + struct pgfree *pf,*pt;
1.903 + u_long l;
1.904 + char *tail;
1.905 +
1.906 + TRACE(("%6d FP %p %d\n",malloc_event++, ptr, page));
1.907 + /* Is it free already ? */
1.908 + if (info == MALLOC_FREE) {
1.909 +#ifdef SANITY
1.910 + wrtwarning("freeing free page at %p.\n", ptr);
1.911 +#endif
1.912 + return;
1.913 + }
1.914 +
1.915 +#ifdef SANITY
1.916 + /* Is it not the right place to begin ? */
1.917 + if (info != MALLOC_FIRST)
1.918 + wrterror("freeing wrong page.\n");
1.919 +
1.920 + /* Is this really a pointer to a page ? */
1.921 + if ((u_long)ptr & malloc_pagemask)
1.922 + wrterror("freeing messed up page pointer.\n");
1.923 +#endif
1.924 +
1.925 + /* Count how many pages it is anyway */
1.926 + page_dir[index] = MALLOC_FREE;
1.927 + for (i = 1; page_dir[index+i] == MALLOC_FOLLOW; i++)
1.928 + page_dir[index + i] = MALLOC_FREE;
1.929 +
1.930 + l = i << malloc_pageshift;
1.931 +
1.932 + tail = ptr+l;
1.933 +
1.934 + /* add to free-list */
1.935 + if (!px)
1.936 + px = (struct pgfree*)_PR_UnlockedMalloc(sizeof *pt);
1.937 + /* XXX check success */
1.938 + px->page = ptr;
1.939 + px->end = tail;
1.940 + px->size = l;
1.941 + if (!free_list.next) {
1.942 + px->next = free_list.next;
1.943 + px->prev = &free_list;
1.944 + free_list.next = px;
1.945 + pf = px;
1.946 + px = 0;
1.947 + } else {
1.948 + tail = ptr+l;
1.949 + for(pf = free_list.next; pf->next && pf->end < ptr; pf = pf->next)
1.950 + ;
1.951 + for(; pf; pf = pf->next) {
1.952 + if (pf->end == ptr ) {
1.953 + /* append to entry */
1.954 + pf->end += l;
1.955 + pf->size += l;
1.956 + if (pf->next && pf->end == pf->next->page ) {
1.957 + pt = pf->next;
1.958 + pf->end = pt->end;
1.959 + pf->size += pt->size;
1.960 + pf->next = pt->next;
1.961 + if (pf->next)
1.962 + pf->next->prev = pf;
1.963 + _PR_UnlockedFree(pt);
1.964 + }
1.965 + } else if (pf->page == tail) {
1.966 + /* prepend to entry */
1.967 + pf->size += l;
1.968 + pf->page = ptr;
1.969 + } else if (pf->page > ptr) {
1.970 + px->next = pf;
1.971 + px->prev = pf->prev;
1.972 + pf->prev = px;
1.973 + px->prev->next = px;
1.974 + pf = px;
1.975 + px = 0;
1.976 + } else if (!pf->next) {
1.977 + px->next = 0;
1.978 + px->prev = pf;
1.979 + pf->next = px;
1.980 + pf = px;
1.981 + px = 0;
1.982 + } else {
1.983 + continue;
1.984 + }
1.985 + break;
1.986 + }
1.987 + }
1.988 + if (!pf->next &&
1.989 + pf->size > malloc_cache &&
1.990 + pf->end == malloc_brk &&
1.991 + malloc_brk == (void*)sbrk(0)) {
1.992 + pf->end = pf->page + malloc_cache;
1.993 + pf->size = malloc_cache;
1.994 + TRACE(("%6d U %p %d\n",malloc_event++,pf->end,pf->end - pf->page));
1.995 + brk(pf->end);
1.996 + malloc_brk = pf->end;
1.997 + /* Find the page directory entry for the page in question */
1.998 + page = (u_long)pf->end >> malloc_pageshift;
1.999 + index = page - malloc_origo;
1.1000 + /* Now update the directory */
1.1001 + for(i=index;i <= last_index;)
1.1002 + page_dir[i++] = MALLOC_NOT_MINE;
1.1003 + last_index = index - 1;
1.1004 + }
1.1005 +}
1.1006 +
1.1007 +/*
1.1008 + * Free a chunk, and possibly the page it's on, if the page becomes empty.
1.1009 + */
1.1010 +
1.1011 +static void
1.1012 +free_bytes(void *ptr, u_long page, int index, struct pginfo *info)
1.1013 +{
1.1014 + int i;
1.1015 + struct pginfo **mp;
1.1016 + void *vp;
1.1017 +
1.1018 + /* Make sure that pointer is multiplum of chunk-size */
1.1019 +#ifdef SANITY
1.1020 + if ((u_long)ptr & (info->size - 1))
1.1021 + wrterror("freeing messed up chunk pointer\n");
1.1022 +#endif
1.1023 +
1.1024 + /* Find the chunk number on the page */
1.1025 + i = ((u_long)ptr & malloc_pagemask) >> info->shift;
1.1026 +
1.1027 + /* See if it's free already */
1.1028 + if (tst_bit(info,i)) {
1.1029 +#ifdef SANITY
1.1030 + wrtwarning("freeing free chunk at %p\n", ptr);
1.1031 +#endif
1.1032 + return;
1.1033 + }
1.1034 +
1.1035 + /* Mark it free */
1.1036 + set_bit(info,i);
1.1037 + info->free++;
1.1038 +
1.1039 + /* If the page was full before, we need to put it on the queue now */
1.1040 + if (info->free == 1) {
1.1041 + mp = page_dir + info->shift;
1.1042 + while (*mp && (*mp)->next && (*mp)->next->page < info->page)
1.1043 + mp = &(*mp)->next;
1.1044 + info->next = *mp;
1.1045 + *mp = info;
1.1046 + return;
1.1047 + }
1.1048 +
1.1049 + /* If this page isn't empty, don't do anything. */
1.1050 + if (info->free != info->total)
1.1051 + return;
1.1052 +
1.1053 + /* We may want to keep at least one page of each size chunks around. */
1.1054 + mp = page_dir + info->shift;
1.1055 + if (0 && (*mp == info) && !info->next)
1.1056 + return;
1.1057 +
1.1058 + /* Find & remove this page in the queue */
1.1059 + while (*mp != info) {
1.1060 + mp = &((*mp)->next);
1.1061 +#ifdef EXTRA_SANITY
1.1062 + if (!*mp) {
1.1063 + TRACE(("%6d !q %p\n",malloc_event++,info));
1.1064 + wrterror("Not on queue\n");
1.1065 + }
1.1066 +#endif
1.1067 + }
1.1068 + *mp = info->next;
1.1069 +
1.1070 + /* Free the page & the info structure if need be */
1.1071 + set_pgdir(info->page,MALLOC_FIRST);
1.1072 + if((void*)info->page == (void*)info) {
1.1073 + _PR_UnlockedFree(info->page);
1.1074 + } else {
1.1075 + vp = info->page;
1.1076 + _PR_UnlockedFree(info);
1.1077 + _PR_UnlockedFree(vp);
1.1078 + }
1.1079 +}
1.1080 +
1.1081 +void _PR_UnlockedFree(void *ptr)
1.1082 +{
1.1083 + u_long page;
1.1084 + struct pginfo *info;
1.1085 + int index, tmp_index;
1.1086 +
1.1087 + TRACE(("%6d F %p\n",malloc_event++,ptr));
1.1088 + /* This is legal */
1.1089 + if (!ptr)
1.1090 + return;
1.1091 +
1.1092 +#ifdef SANITY
1.1093 + /* There wouldn't be anything to free */
1.1094 + if (!initialized) {
1.1095 + wrtwarning("free() called before malloc() ever got called\n");
1.1096 + return;
1.1097 + }
1.1098 +#endif
1.1099 +
1.1100 +#ifdef SANITY
1.1101 + if (suicide)
1.1102 + PR_Abort();
1.1103 +#endif
1.1104 +
1.1105 + /* Find the page directory entry for the page in question */
1.1106 + page = (u_long)ptr >> malloc_pageshift;
1.1107 + index = page - malloc_origo;
1.1108 +
1.1109 + /*
1.1110 + * check if memory was allocated by memalign
1.1111 + */
1.1112 + tmp_index = index;
1.1113 + while (page_dir[tmp_index] == MALLOC_FOLLOW)
1.1114 + tmp_index--;
1.1115 + if (tmp_index != index) {
1.1116 + /*
1.1117 + * memalign-allocated memory
1.1118 + */
1.1119 + index = tmp_index;
1.1120 + page = index + malloc_origo;
1.1121 + ptr = (void *) (page << malloc_pageshift);
1.1122 + }
1.1123 + /* make sure it makes sense in some fashion */
1.1124 + if (index < malloc_pageshift) {
1.1125 +#ifdef SANITY
1.1126 + wrtwarning("junk pointer %p (low) passed to free()\n", ptr);
1.1127 +#endif
1.1128 + return;
1.1129 + }
1.1130 + if (index > last_index) {
1.1131 +#ifdef SANITY
1.1132 + wrtwarning("junk pointer %p (high) passed to free()\n", ptr);
1.1133 +#endif
1.1134 + return;
1.1135 + }
1.1136 +
1.1137 + /* handle as page-allocation or chunk allocation */
1.1138 + info = page_dir[index];
1.1139 + if (info < MALLOC_MAGIC)
1.1140 + free_pages((char*)ptr, page, index, info);
1.1141 + else
1.1142 + free_bytes(ptr,page,index,info);
1.1143 + return;
1.1144 +}
1.1145 +#endif /* _PR_OVERRIDE_MALLOC */
