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