Mercurial > projects > ldc
annotate tango/lib/gc/basic/gcx.d @ 268:23d0d9855cad trunk
[svn r289] Fixed: right shift >> was broken for unsigned types.
Fixed: debug info for classes now started.
| author | lindquist |
|---|---|
| date | Sun, 15 Jun 2008 18:52:27 +0200 |
| parents | ab43d1e1bf2a |
| children | 0baca2feb554 |
| rev | line source |
|---|---|
| 132 | 1 /** |
| 2 * This module contains the garbage collector implementation. | |
| 3 * | |
| 4 * Copyright: Copyright (C) 2001-2007 Digital Mars, www.digitalmars.com. | |
| 5 * All rights reserved. | |
| 6 * License: | |
| 7 * This software is provided 'as-is', without any express or implied | |
| 8 * warranty. In no event will the authors be held liable for any damages | |
| 9 * arising from the use of this software. | |
| 10 * | |
| 11 * Permission is granted to anyone to use this software for any purpose, | |
| 12 * including commercial applications, and to alter it and redistribute it | |
| 13 * freely, in both source and binary form, subject to the following | |
| 14 * restrictions: | |
| 15 * | |
| 16 * o The origin of this software must not be misrepresented; you must not | |
| 17 * claim that you wrote the original software. If you use this software | |
| 18 * in a product, an acknowledgment in the product documentation would be | |
| 19 * appreciated but is not required. | |
| 20 * o Altered source versions must be plainly marked as such, and must not | |
| 21 * be misrepresented as being the original software. | |
| 22 * o This notice may not be removed or altered from any source | |
| 23 * distribution. | |
| 24 * Authors: Walter Bright, David Friedman, Sean Kelly | |
| 25 */ | |
| 26 | |
| 27 // D Programming Language Garbage Collector implementation | |
| 28 | |
| 29 /************** Debugging ***************************/ | |
| 30 | |
| 31 //debug = PRINTF; // turn on printf's | |
| 32 //debug = COLLECT_PRINTF; // turn on printf's | |
| 33 //debug = THREADINVARIANT; // check thread integrity | |
| 34 //debug = LOGGING; // log allocations / frees | |
| 35 //debug = MEMSTOMP; // stomp on memory | |
| 36 //debug = SENTINEL; // add underrun/overrrun protection | |
| 37 //debug = PTRCHECK; // more pointer checking | |
| 38 //debug = PTRCHECK2; // thorough but slow pointer checking | |
| 39 | |
| 40 /*************** Configuration *********************/ | |
| 41 | |
| 42 version = STACKGROWSDOWN; // growing the stack means subtracting from the stack pointer | |
| 43 // (use for Intel X86 CPUs) | |
| 44 // else growing the stack means adding to the stack pointer | |
| 45 version = MULTI_THREADED; // produce multithreaded version | |
| 46 | |
| 47 /***************************************************/ | |
| 48 | |
| 49 private import gcbits; | |
| 50 private import gcstats; | |
| 51 private import gcalloc; | |
| 52 | |
| 53 private import cstdlib = tango.stdc.stdlib : calloc, free, malloc, realloc; | |
| 54 private import cstring = tango.stdc.string : memcpy, memmove, memset; | |
| 55 | |
|
268
23d0d9855cad
[svn r289] Fixed: right shift >> was broken for unsigned types.
lindquist
parents:
242
diff
changeset
|
56 private import tango.stdc.stdio; |
|
23d0d9855cad
[svn r289] Fixed: right shift >> was broken for unsigned types.
lindquist
parents:
242
diff
changeset
|
57 private import tango.stdc.posix.pthread; |
| 132 | 58 |
| 59 version (GNU) | |
| 60 { | |
| 61 // BUG: The following import will likely not work, since the gcc | |
| 62 // subdirectory is elsewhere. Instead, perhaps the functions | |
| 63 // could be declared directly or some other resolution could | |
| 64 // be found. | |
| 65 private import gcc.builtins; // for __builtin_unwind_init | |
| 66 } | |
| 67 | |
| 68 | |
| 69 private | |
| 70 { | |
| 71 enum BlkAttr : uint | |
| 72 { | |
| 73 FINALIZE = 0b0000_0001, | |
| 74 NO_SCAN = 0b0000_0010, | |
| 75 NO_MOVE = 0b0000_0100, | |
| 76 ALL_BITS = 0b1111_1111 | |
| 77 } | |
| 78 | |
| 79 struct BlkInfo | |
| 80 { | |
| 81 void* base; | |
| 82 size_t size; | |
| 83 uint attr; | |
| 84 } | |
| 85 | |
| 86 extern (C) void* rt_stackBottom(); | |
| 87 extern (C) void* rt_stackTop(); | |
| 88 | |
| 89 extern (C) void rt_finalize( void* p, bool det = true ); | |
| 90 | |
| 91 alias void delegate( void*, void* ) scanFn; | |
| 92 | |
| 93 extern (C) void rt_scanStaticData( scanFn scan ); | |
| 94 | |
| 95 version (MULTI_THREADED) | |
| 96 { | |
| 97 extern (C) bool thread_needLock(); | |
| 98 extern (C) void thread_suspendAll(); | |
| 99 extern (C) void thread_resumeAll(); | |
| 100 | |
| 101 extern (C) void thread_scanAll( scanFn fn, void* curStackTop = null ); | |
| 102 } | |
| 103 | |
| 104 extern (C) void onOutOfMemoryError(); | |
| 105 } | |
| 106 | |
| 107 | |
| 108 alias GC gc_t; | |
| 109 | |
| 110 | |
| 111 /* ======================= Leak Detector =========================== */ | |
| 112 | |
| 113 | |
| 114 debug (LOGGING) | |
| 115 { | |
| 116 struct Log | |
| 117 { | |
| 118 void* p; | |
| 119 size_t size; | |
| 120 uint line; | |
| 121 char* file; | |
| 122 void* parent; | |
| 123 | |
| 124 void print() | |
| 125 { | |
| 126 printf(" p = %x, size = %d, parent = %x ", p, size, parent); | |
| 127 if (file) | |
| 128 { | |
| 129 printf("%s(%u)", file, line); | |
| 130 } | |
| 131 printf("\n"); | |
| 132 } | |
| 133 } | |
| 134 | |
| 135 | |
| 136 struct LogArray | |
| 137 { | |
| 138 size_t dim; | |
| 139 size_t allocdim; | |
| 140 Log *data; | |
| 141 | |
| 142 void Dtor() | |
| 143 { | |
| 144 if (data) | |
| 145 cstdlib.free(data); | |
| 146 data = null; | |
| 147 } | |
| 148 | |
| 149 void reserve(size_t nentries) | |
| 150 { | |
| 151 assert(dim <= allocdim); | |
| 152 if (allocdim - dim < nentries) | |
| 153 { | |
| 154 allocdim = (dim + nentries) * 2; | |
| 155 assert(dim + nentries <= allocdim); | |
| 156 if (!data) | |
| 157 { | |
| 158 data = cast(Log *)cstdlib.malloc(allocdim * Log.sizeof); | |
| 159 if (!data && allocdim) | |
| 160 onOutOfMemoryError(); | |
| 161 } | |
| 162 else | |
| 163 { Log *newdata; | |
| 164 | |
| 165 newdata = cast(Log *)cstdlib.malloc(allocdim * Log.sizeof); | |
| 166 if (!newdata && allocdim) | |
| 167 onOutOfMemoryError(); | |
| 168 cstring.memcpy(newdata, data, dim * Log.sizeof); | |
| 169 cstdlib.free(data); | |
| 170 data = newdata; | |
| 171 } | |
| 172 } | |
| 173 } | |
| 174 | |
| 175 | |
| 176 void push(Log log) | |
| 177 { | |
| 178 reserve(1); | |
| 179 data[dim++] = log; | |
| 180 } | |
| 181 | |
| 182 void remove(size_t i) | |
| 183 { | |
| 184 cstring.memmove(data + i, data + i + 1, (dim - i) * Log.sizeof); | |
| 185 dim--; | |
| 186 } | |
| 187 | |
| 188 | |
| 189 size_t find(void *p) | |
| 190 { | |
| 191 for (size_t i = 0; i < dim; i++) | |
| 192 { | |
| 193 if (data[i].p == p) | |
| 194 return i; | |
| 195 } | |
| 196 return ~0u; // not found | |
| 197 } | |
| 198 | |
| 199 | |
| 200 void copy(LogArray *from) | |
| 201 { | |
| 202 reserve(from.dim - dim); | |
| 203 assert(from.dim <= allocdim); | |
| 204 cstring.memcpy(data, from.data, from.dim * Log.sizeof); | |
| 205 dim = from.dim; | |
| 206 } | |
| 207 } | |
| 208 } | |
| 209 | |
| 210 | |
| 211 /* ============================ GC =============================== */ | |
| 212 | |
| 213 | |
| 214 class GCLock { } // just a dummy so we can get a global lock | |
| 215 | |
| 216 | |
| 217 const uint GCVERSION = 1; // increment every time we change interface | |
| 218 // to GC. | |
| 219 | |
| 220 class GC | |
| 221 { | |
| 222 // For passing to debug code | |
| 223 static size_t line; | |
| 224 static char* file; | |
| 225 | |
| 226 uint gcversion = GCVERSION; | |
| 227 | |
| 228 Gcx *gcx; // implementation | |
| 229 static ClassInfo gcLock; // global lock | |
| 230 | |
| 231 | |
| 232 void initialize() | |
| 233 { | |
| 234 gcLock = GCLock.classinfo; | |
| 235 gcx = cast(Gcx *)cstdlib.calloc(1, Gcx.sizeof); | |
| 236 if (!gcx) | |
| 237 onOutOfMemoryError(); | |
| 238 gcx.initialize(); | |
| 239 setStackBottom(rt_stackBottom()); | |
| 240 } | |
| 241 | |
| 242 | |
| 243 void Dtor() | |
| 244 { | |
| 245 version (linux) | |
| 246 { | |
| 247 //debug(PRINTF) printf("Thread %x ", pthread_self()); | |
| 248 //debug(PRINTF) printf("GC.Dtor()\n"); | |
| 249 } | |
| 250 | |
| 251 if (gcx) | |
| 252 { | |
| 253 gcx.Dtor(); | |
| 254 cstdlib.free(gcx); | |
| 255 gcx = null; | |
| 256 } | |
| 257 } | |
| 258 | |
| 259 | |
| 260 invariant | |
| 261 { | |
| 262 if (gcx) | |
| 263 { | |
| 264 gcx.thread_Invariant(); | |
| 265 } | |
| 266 } | |
| 267 | |
| 268 | |
| 269 /** | |
| 270 * | |
| 271 */ | |
| 272 void enable() | |
| 273 { | |
| 274 if (!thread_needLock()) | |
| 275 { | |
| 276 assert(gcx.disabled > 0); | |
| 277 gcx.disabled--; | |
| 278 } | |
| 279 else synchronized (gcLock) | |
| 280 { | |
| 281 assert(gcx.disabled > 0); | |
| 282 gcx.disabled--; | |
| 283 } | |
| 284 } | |
| 285 | |
| 286 | |
| 287 /** | |
| 288 * | |
| 289 */ | |
| 290 void disable() | |
| 291 { | |
| 292 if (!thread_needLock()) | |
| 293 { | |
| 294 gcx.disabled++; | |
| 295 } | |
| 296 else synchronized (gcLock) | |
| 297 { | |
| 298 gcx.disabled++; | |
| 299 } | |
| 300 } | |
| 301 | |
| 302 | |
| 303 /** | |
| 304 * | |
| 305 */ | |
| 306 uint getAttr(void* p) | |
| 307 { | |
| 308 if (!p) | |
| 309 { | |
| 310 return 0; | |
| 311 } | |
| 312 | |
| 313 uint go() | |
| 314 { | |
| 315 Pool* pool = gcx.findPool(p); | |
| 316 uint oldb = 0; | |
| 317 | |
| 318 if (pool) | |
| 319 { | |
| 320 uint biti = (p - pool.baseAddr) / 16; | |
| 321 | |
| 322 oldb = gcx.getBits(pool, biti); | |
| 323 } | |
| 324 return oldb; | |
| 325 } | |
| 326 | |
| 327 if (!thread_needLock()) | |
| 328 { | |
| 329 return go(); | |
| 330 } | |
| 331 else synchronized (gcLock) | |
| 332 { | |
| 333 return go(); | |
| 334 } | |
| 335 } | |
| 336 | |
| 337 | |
| 338 /** | |
| 339 * | |
| 340 */ | |
| 341 uint setAttr(void* p, uint mask) | |
| 342 { | |
| 343 if (!p) | |
| 344 { | |
| 345 return 0; | |
| 346 } | |
| 347 | |
| 348 uint go() | |
| 349 { | |
| 350 Pool* pool = gcx.findPool(p); | |
| 351 uint oldb = 0; | |
| 352 | |
| 353 if (pool) | |
| 354 { | |
| 355 uint biti = (p - pool.baseAddr) / 16; | |
| 356 | |
| 357 oldb = gcx.getBits(pool, biti); | |
| 358 gcx.setBits(pool, biti, mask); | |
| 359 } | |
| 360 return oldb; | |
| 361 } | |
| 362 | |
| 363 if (!thread_needLock()) | |
| 364 { | |
| 365 return go(); | |
| 366 } | |
| 367 else synchronized (gcLock) | |
| 368 { | |
| 369 return go(); | |
| 370 } | |
| 371 } | |
| 372 | |
| 373 | |
| 374 /** | |
| 375 * | |
| 376 */ | |
| 377 uint clrAttr(void* p, uint mask) | |
| 378 { | |
| 379 if (!p) | |
| 380 { | |
| 381 return 0; | |
| 382 } | |
| 383 | |
| 384 uint go() | |
| 385 { | |
| 386 Pool* pool = gcx.findPool(p); | |
| 387 uint oldb = 0; | |
| 388 | |
| 389 if (pool) | |
| 390 { | |
| 391 uint biti = (p - pool.baseAddr) / 16; | |
| 392 | |
| 393 oldb = gcx.getBits(pool, biti); | |
| 394 gcx.clrBits(pool, biti, mask); | |
| 395 } | |
| 396 return oldb; | |
| 397 } | |
| 398 | |
| 399 if (!thread_needLock()) | |
| 400 { | |
| 401 return go(); | |
| 402 } | |
| 403 else synchronized (gcLock) | |
| 404 { | |
| 405 return go(); | |
| 406 } | |
| 407 } | |
| 408 | |
| 409 | |
| 410 /** | |
| 411 * | |
| 412 */ | |
| 413 void *malloc(size_t size, uint bits = 0) | |
| 414 { | |
| 415 if (!size) | |
| 416 { | |
| 417 return null; | |
| 418 } | |
| 419 | |
| 420 if (!thread_needLock()) | |
| 421 { | |
| 422 return mallocNoSync(size, bits); | |
| 423 } | |
| 424 else synchronized (gcLock) | |
| 425 { | |
| 426 return mallocNoSync(size, bits); | |
| 427 } | |
| 428 } | |
| 429 | |
| 430 | |
| 431 // | |
| 432 // | |
| 433 // | |
| 434 private void *mallocNoSync(size_t size, uint bits = 0) | |
| 435 { | |
| 436 assert(size != 0); | |
| 437 | |
| 438 void *p = null; | |
| 439 Bins bin; | |
| 440 | |
| 441 //debug(PRINTF) printf("GC::malloc(size = %d, gcx = %p)\n", size, gcx); | |
| 442 assert(gcx); | |
| 443 //debug(PRINTF) printf("gcx.self = %x, pthread_self() = %x\n", gcx.self, pthread_self()); | |
| 444 | |
| 445 size += SENTINEL_EXTRA; | |
| 446 | |
| 447 // Compute size bin | |
| 448 // Cache previous binsize lookup - Dave Fladebo. | |
| 449 static size_t lastsize = -1; | |
| 450 static Bins lastbin; | |
| 451 if (size == lastsize) | |
| 452 bin = lastbin; | |
| 453 else | |
| 454 { | |
| 455 bin = gcx.findBin(size); | |
| 456 lastsize = size; | |
| 457 lastbin = bin; | |
| 458 } | |
| 459 | |
| 460 if (bin < B_PAGE) | |
| 461 { | |
| 462 p = gcx.bucket[bin]; | |
| 463 if (p == null) | |
| 464 { | |
| 465 if (!gcx.allocPage(bin) && !gcx.disabled) // try to find a new page | |
| 466 { | |
| 467 if (!thread_needLock()) | |
| 468 { | |
| 469 /* Then we haven't locked it yet. Be sure | |
| 470 * and lock for a collection, since a finalizer | |
| 471 * may start a new thread. | |
| 472 */ | |
| 473 synchronized (gcLock) | |
| 474 { | |
| 475 gcx.fullcollectshell(); | |
| 476 } | |
| 477 } | |
| 478 else if (!gcx.fullcollectshell()) // collect to find a new page | |
| 479 { | |
| 480 //gcx.newPool(1); | |
| 481 } | |
| 482 } | |
| 483 if (!gcx.bucket[bin] && !gcx.allocPage(bin)) | |
| 484 { int result; | |
| 485 | |
| 486 gcx.newPool(1); // allocate new pool to find a new page | |
| 487 result = gcx.allocPage(bin); | |
| 488 if (!result) | |
| 489 onOutOfMemoryError(); | |
| 490 } | |
| 491 p = gcx.bucket[bin]; | |
| 492 } | |
| 493 | |
| 494 // Return next item from free list | |
| 495 gcx.bucket[bin] = (cast(List *)p).next; | |
| 496 if( !(bits & BlkAttr.NO_SCAN) ) | |
| 497 cstring.memset(p + size, 0, binsize[bin] - size); | |
| 498 //debug(PRINTF) printf("\tmalloc => %x\n", p); | |
| 499 debug (MEMSTOMP) cstring.memset(p, 0xF0, size); | |
| 500 } | |
| 501 else | |
| 502 { | |
| 503 p = gcx.bigAlloc(size); | |
| 504 if (!p) | |
| 505 onOutOfMemoryError(); | |
| 506 } | |
| 507 size -= SENTINEL_EXTRA; | |
| 508 p = sentinel_add(p); | |
| 509 sentinel_init(p, size); | |
| 510 gcx.log_malloc(p, size); | |
| 511 | |
| 512 if (bits) | |
| 513 { | |
| 514 Pool *pool = gcx.findPool(p); | |
| 515 assert(pool); | |
| 516 | |
| 517 gcx.setBits(pool, (p - pool.baseAddr) / 16, bits); | |
| 518 } | |
| 519 return p; | |
| 520 } | |
| 521 | |
| 522 | |
| 523 /** | |
| 524 * | |
| 525 */ | |
| 526 void *calloc(size_t size, uint bits = 0) | |
| 527 { | |
| 528 if (!size) | |
| 529 { | |
| 530 return null; | |
| 531 } | |
| 532 | |
| 533 if (!thread_needLock()) | |
| 534 { | |
| 535 return callocNoSync(size, bits); | |
| 536 } | |
| 537 else synchronized (gcLock) | |
| 538 { | |
| 539 return callocNoSync(size, bits); | |
| 540 } | |
| 541 } | |
| 542 | |
| 543 | |
| 544 // | |
| 545 // | |
| 546 // | |
| 547 private void *callocNoSync(size_t size, uint bits = 0) | |
| 548 { | |
| 549 assert(size != 0); | |
| 550 | |
| 551 //debug(PRINTF) printf("calloc: %x len %d\n", p, len); | |
| 552 void *p = mallocNoSync(size, bits); | |
| 553 cstring.memset(p, 0, size); | |
| 554 return p; | |
| 555 } | |
| 556 | |
| 557 | |
| 558 /** | |
| 559 * | |
| 560 */ | |
| 561 void *realloc(void *p, size_t size, uint bits = 0) | |
| 562 { | |
| 563 if (!thread_needLock()) | |
| 564 { | |
| 565 return reallocNoSync(p, size, bits); | |
| 566 } | |
| 567 else synchronized (gcLock) | |
| 568 { | |
| 569 return reallocNoSync(p, size, bits); | |
| 570 } | |
| 571 } | |
| 572 | |
| 573 | |
| 574 // | |
| 575 // | |
| 576 // | |
| 577 private void *reallocNoSync(void *p, size_t size, uint bits = 0) | |
| 578 { | |
| 579 if (!size) | |
| 580 { if (p) | |
| 581 { freeNoSync(p); | |
| 582 p = null; | |
| 583 } | |
| 584 } | |
| 585 else if (!p) | |
| 586 { | |
| 587 p = mallocNoSync(size, bits); | |
| 588 } | |
| 589 else | |
| 590 { void *p2; | |
| 591 size_t psize; | |
| 592 | |
| 593 //debug(PRINTF) printf("GC::realloc(p = %x, size = %u)\n", p, size); | |
| 594 version (SENTINEL) | |
| 595 { | |
| 596 sentinel_Invariant(p); | |
| 597 psize = *sentinel_size(p); | |
| 598 if (psize != size) | |
| 599 { | |
| 600 if (psize) | |
| 601 { | |
| 602 Pool *pool = gcx.findPool(p); | |
| 603 | |
| 604 if (pool) | |
| 605 { | |
| 606 uint biti = cast(uint)(p - pool.baseAddr) / 16; | |
| 607 | |
| 608 if (bits) | |
| 609 { | |
| 610 gcx.clrBits(pool, biti, BlkAttr.ALL_BITS); | |
| 611 gcx.setBits(pool, biti, bits); | |
| 612 } | |
| 613 else | |
| 614 { | |
| 615 bits = gcx.getBits(pool, biti); | |
| 616 } | |
| 617 } | |
| 618 } | |
| 619 p2 = mallocNoSync(size, bits); | |
| 620 if (psize < size) | |
| 621 size = psize; | |
| 622 //debug(PRINTF) printf("\tcopying %d bytes\n",size); | |
| 623 cstring.memcpy(p2, p, size); | |
| 624 p = p2; | |
| 625 } | |
| 626 } | |
| 627 else | |
| 628 { | |
| 629 psize = gcx.findSize(p); // find allocated size | |
| 630 if (psize >= PAGESIZE && size >= PAGESIZE) | |
| 631 { | |
| 632 auto psz = psize / PAGESIZE; | |
| 633 auto newsz = (size + PAGESIZE - 1) / PAGESIZE; | |
| 634 if (newsz == psz) | |
| 635 return p; | |
| 636 | |
| 637 auto pool = gcx.findPool(p); | |
| 638 auto pagenum = (p - pool.baseAddr) / PAGESIZE; | |
| 639 | |
| 640 if (newsz < psz) | |
| 641 { // Shrink in place | |
| 642 synchronized (gcLock) | |
| 643 { | |
| 644 debug (MEMSTOMP) cstring.memset(p + size, 0xF2, psize - size); | |
| 645 pool.freePages(pagenum + newsz, psz - newsz); | |
| 646 } | |
| 647 return p; | |
| 648 } | |
| 649 else if (pagenum + newsz <= pool.npages) | |
| 650 { | |
| 651 // Attempt to expand in place | |
| 652 synchronized (gcLock) | |
| 653 { | |
| 654 for (size_t i = pagenum + psz; 1;) | |
| 655 { | |
| 656 if (i == pagenum + newsz) | |
| 657 { | |
| 658 debug (MEMSTOMP) cstring.memset(p + psize, 0xF0, size - psize); | |
| 659 cstring.memset(&pool.pagetable[pagenum + psz], B_PAGEPLUS, newsz - psz); | |
| 660 return p; | |
| 661 } | |
| 662 if (i == pool.ncommitted) | |
| 663 { | |
| 664 auto u = pool.extendPages(pagenum + newsz - pool.ncommitted); | |
| 665 if (u == ~0u) | |
| 666 break; | |
| 667 i = pagenum + newsz; | |
| 668 continue; | |
| 669 } | |
| 670 if (pool.pagetable[i] != B_FREE) | |
| 671 break; | |
| 672 i++; | |
| 673 } | |
| 674 } | |
| 675 } | |
| 676 } | |
| 677 if (psize < size || // if new size is bigger | |
| 678 psize > size * 2) // or less than half | |
| 679 { | |
| 680 if (psize) | |
| 681 { | |
| 682 Pool *pool = gcx.findPool(p); | |
| 683 | |
| 684 if (pool) | |
| 685 { | |
| 686 uint biti = cast(uint)(p - pool.baseAddr) / 16; | |
| 687 | |
| 688 if (bits) | |
| 689 { | |
| 690 gcx.clrBits(pool, biti, BlkAttr.ALL_BITS); | |
| 691 gcx.setBits(pool, biti, bits); | |
| 692 } | |
| 693 else | |
| 694 { | |
| 695 bits = gcx.getBits(pool, biti); | |
| 696 } | |
| 697 } | |
| 698 } | |
| 699 p2 = mallocNoSync(size, bits); | |
| 700 if (psize < size) | |
| 701 size = psize; | |
| 702 //debug(PRINTF) printf("\tcopying %d bytes\n",size); | |
| 703 cstring.memcpy(p2, p, size); | |
| 704 p = p2; | |
| 705 } | |
| 706 } | |
| 707 } | |
| 708 return p; | |
| 709 } | |
| 710 | |
| 711 | |
| 712 /** | |
| 713 * Attempt to in-place enlarge the memory block pointed to by p by at least | |
| 714 * minbytes beyond its current capacity, up to a maximum of maxsize. This | |
| 715 * does not attempt to move the memory block (like realloc() does). | |
| 716 * | |
| 717 * Returns: | |
| 718 * 0 if could not extend p, | |
| 719 * total size of entire memory block if successful. | |
| 720 */ | |
| 721 size_t extend(void* p, size_t minsize, size_t maxsize) | |
| 722 { | |
| 723 if (!thread_needLock()) | |
| 724 { | |
| 725 return extendNoSync(p, minsize, maxsize); | |
| 726 } | |
| 727 else synchronized (gcLock) | |
| 728 { | |
| 729 return extendNoSync(p, minsize, maxsize); | |
| 730 } | |
| 731 } | |
| 732 | |
| 733 | |
| 734 // | |
| 735 // | |
| 736 // | |
| 737 private size_t extendNoSync(void* p, size_t minsize, size_t maxsize) | |
| 738 in | |
| 739 { | |
| 740 assert( minsize <= maxsize ); | |
| 741 } | |
| 742 body | |
| 743 { | |
| 744 //debug(PRINTF) printf("GC::extend(p = %x, minsize = %u, maxsize = %u)\n", p, minsize, maxsize); | |
| 745 version (SENTINEL) | |
| 746 { | |
| 747 return 0; | |
| 748 } | |
| 749 auto psize = gcx.findSize(p); // find allocated size | |
| 750 if (psize < PAGESIZE) | |
| 751 return 0; // cannot extend buckets | |
| 752 | |
| 753 auto psz = psize / PAGESIZE; | |
| 754 auto minsz = (minsize + PAGESIZE - 1) / PAGESIZE; | |
| 755 auto maxsz = (maxsize + PAGESIZE - 1) / PAGESIZE; | |
| 756 | |
| 757 auto pool = gcx.findPool(p); | |
| 758 auto pagenum = (p - pool.baseAddr) / PAGESIZE; | |
| 759 | |
| 760 size_t sz; | |
| 761 for (sz = 0; sz < maxsz; sz++) | |
| 762 { | |
| 763 auto i = pagenum + psz + sz; | |
| 764 if (i == pool.ncommitted) | |
| 765 break; | |
| 766 if (pool.pagetable[i] != B_FREE) | |
| 767 { if (sz < minsz) | |
| 768 return 0; | |
| 769 break; | |
| 770 } | |
| 771 } | |
| 772 if (sz >= minsz) | |
| 773 { | |
| 774 } | |
| 775 else if (pagenum + psz + sz == pool.ncommitted) | |
| 776 { | |
| 777 auto u = pool.extendPages(minsz - sz); | |
| 778 if (u == ~0u) | |
| 779 return 0; | |
| 780 sz = minsz; | |
| 781 } | |
| 782 else | |
| 783 return 0; | |
| 784 debug (MEMSTOMP) cstring.memset(p + psize, 0xF0, (psz + sz) * PAGESIZE - psize); | |
| 785 cstring.memset(pool.pagetable + pagenum + psz, B_PAGEPLUS, sz); | |
| 786 gcx.p_cache = null; | |
| 787 gcx.size_cache = 0; | |
| 788 return (psz + sz) * PAGESIZE; | |
| 789 } | |
| 790 | |
| 791 | |
| 792 /** | |
| 793 * | |
| 794 */ | |
| 795 void free(void *p) | |
| 796 { | |
| 797 if (!p) | |
| 798 { | |
| 799 return; | |
| 800 } | |
| 801 | |
| 802 if (!thread_needLock()) | |
| 803 { | |
| 804 return freeNoSync(p); | |
| 805 } | |
| 806 else synchronized (gcLock) | |
| 807 { | |
| 808 return freeNoSync(p); | |
| 809 } | |
| 810 } | |
| 811 | |
| 812 | |
| 813 // | |
| 814 // | |
| 815 // | |
| 816 private void freeNoSync(void *p) | |
| 817 { | |
| 818 assert (p); | |
| 819 | |
| 820 Pool *pool; | |
| 821 uint pagenum; | |
| 822 Bins bin; | |
| 823 uint biti; | |
| 824 | |
| 825 // Find which page it is in | |
| 826 pool = gcx.findPool(p); | |
| 827 if (!pool) // if not one of ours | |
| 828 return; // ignore | |
| 829 sentinel_Invariant(p); | |
| 830 p = sentinel_sub(p); | |
| 831 pagenum = (p - pool.baseAddr) / PAGESIZE; | |
| 832 biti = cast(uint)(p - pool.baseAddr) / 16; | |
| 833 gcx.clrBits(pool, biti, BlkAttr.ALL_BITS); | |
| 834 | |
| 835 bin = cast(Bins)pool.pagetable[pagenum]; | |
| 836 if (bin == B_PAGE) // if large alloc | |
| 837 { int npages; | |
| 838 uint n; | |
| 839 | |
| 840 // Free pages | |
| 841 npages = 1; | |
| 842 n = pagenum; | |
| 843 while (++n < pool.ncommitted && pool.pagetable[n] == B_PAGEPLUS) | |
| 844 npages++; | |
| 845 debug (MEMSTOMP) cstring.memset(p, 0xF2, npages * PAGESIZE); | |
| 846 pool.freePages(pagenum, npages); | |
| 847 } | |
| 848 else | |
| 849 { // Add to free list | |
| 850 List *list = cast(List *)p; | |
| 851 | |
| 852 debug (MEMSTOMP) cstring.memset(p, 0xF2, binsize[bin]); | |
| 853 | |
| 854 list.next = gcx.bucket[bin]; | |
| 855 gcx.bucket[bin] = list; | |
| 856 } | |
| 857 gcx.log_free(sentinel_add(p)); | |
| 858 } | |
| 859 | |
| 860 | |
| 861 /** | |
| 862 * Determine the base address of the block containing p. If p is not a gc | |
| 863 * allocated pointer, return null. | |
| 864 */ | |
| 865 void* addrOf(void *p) | |
| 866 { | |
| 867 if (!p) | |
| 868 { | |
| 869 return null; | |
| 870 } | |
| 871 | |
| 872 if (!thread_needLock()) | |
| 873 { | |
| 874 return addrOfNoSync(p); | |
| 875 } | |
| 876 else synchronized (gcLock) | |
| 877 { | |
| 878 return addrOfNoSync(p); | |
| 879 } | |
| 880 } | |
| 881 | |
| 882 | |
| 883 // | |
| 884 // | |
| 885 // | |
| 886 void* addrOfNoSync(void *p) | |
| 887 { | |
| 888 if (!p) | |
| 889 { | |
| 890 return null; | |
| 891 } | |
| 892 | |
| 893 return gcx.findBase(p); | |
| 894 } | |
| 895 | |
| 896 | |
| 897 /** | |
| 898 * Determine the allocated size of pointer p. If p is an interior pointer | |
| 899 * or not a gc allocated pointer, return 0. | |
| 900 */ | |
| 901 size_t sizeOf(void *p) | |
| 902 { | |
| 903 if (!p) | |
| 904 { | |
| 905 return 0; | |
| 906 } | |
| 907 | |
| 908 if (!thread_needLock()) | |
| 909 { | |
| 910 return sizeOfNoSync(p); | |
| 911 } | |
| 912 else synchronized (gcLock) | |
| 913 { | |
| 914 return sizeOfNoSync(p); | |
| 915 } | |
| 916 } | |
| 917 | |
| 918 | |
| 919 // | |
| 920 // | |
| 921 // | |
| 922 private size_t sizeOfNoSync(void *p) | |
| 923 { | |
| 924 assert (p); | |
| 925 | |
| 926 version (SENTINEL) | |
| 927 { | |
| 928 p = sentinel_sub(p); | |
| 929 size_t size = gcx.findSize(p); | |
| 930 | |
| 931 // Check for interior pointer | |
| 932 // This depends on: | |
| 933 // 1) size is a power of 2 for less than PAGESIZE values | |
| 934 // 2) base of memory pool is aligned on PAGESIZE boundary | |
| 935 if (cast(size_t)p & (size - 1) & (PAGESIZE - 1)) | |
| 936 size = 0; | |
| 937 return size ? size - SENTINAL_EXTRA : 0; | |
| 938 } | |
| 939 else | |
| 940 { | |
| 941 if (p == gcx.p_cache) | |
| 942 return gcx.size_cache; | |
| 943 | |
| 944 size_t size = gcx.findSize(p); | |
| 945 | |
| 946 // Check for interior pointer | |
| 947 // This depends on: | |
| 948 // 1) size is a power of 2 for less than PAGESIZE values | |
| 949 // 2) base of memory pool is aligned on PAGESIZE boundary | |
| 950 if (cast(size_t)p & (size - 1) & (PAGESIZE - 1)) | |
| 951 size = 0; | |
| 952 else | |
| 953 { | |
| 954 gcx.p_cache = p; | |
| 955 gcx.size_cache = size; | |
| 956 } | |
| 957 | |
| 958 return size; | |
| 959 } | |
| 960 } | |
| 961 | |
| 962 | |
| 963 /** | |
| 964 * Determine the base address of the block containing p. If p is not a gc | |
| 965 * allocated pointer, return null. | |
| 966 */ | |
| 967 BlkInfo query(void *p) | |
| 968 { | |
| 969 if (!p) | |
| 970 { | |
| 971 BlkInfo i; | |
| 972 return i; | |
| 973 } | |
| 974 | |
| 975 if (!thread_needLock()) | |
| 976 { | |
| 977 return queryNoSync(p); | |
| 978 } | |
| 979 else synchronized (gcLock) | |
| 980 { | |
| 981 return queryNoSync(p); | |
| 982 } | |
| 983 } | |
| 984 | |
| 985 | |
| 986 // | |
| 987 // | |
| 988 // | |
| 989 BlkInfo queryNoSync(void *p) | |
| 990 { | |
| 991 assert(p); | |
| 992 | |
| 993 return gcx.getInfo(p); | |
| 994 } | |
| 995 | |
| 996 | |
| 997 /** | |
| 998 * Verify that pointer p: | |
| 999 * 1) belongs to this memory pool | |
| 1000 * 2) points to the start of an allocated piece of memory | |
| 1001 * 3) is not on a free list | |
| 1002 */ | |
| 1003 void check(void *p) | |
| 1004 { | |
| 1005 if (!p) | |
| 1006 { | |
| 1007 return; | |
| 1008 } | |
| 1009 | |
| 1010 if (!thread_needLock()) | |
| 1011 { | |
| 1012 checkNoSync(p); | |
| 1013 } | |
| 1014 else synchronized (gcLock) | |
| 1015 { | |
| 1016 checkNoSync(p); | |
| 1017 } | |
| 1018 } | |
| 1019 | |
| 1020 | |
| 1021 // | |
| 1022 // | |
| 1023 // | |
| 1024 private void checkNoSync(void *p) | |
| 1025 { | |
| 1026 assert(p); | |
| 1027 | |
| 1028 sentinel_Invariant(p); | |
| 1029 debug (PTRCHECK) | |
| 1030 { | |
| 1031 Pool* pool; | |
| 1032 uint pagenum; | |
| 1033 Bins bin; | |
| 1034 size_t size; | |
| 1035 | |
| 1036 p = sentinel_sub(p); | |
| 1037 pool = gcx.findPool(p); | |
| 1038 assert(pool); | |
| 1039 pagenum = (p - pool.baseAddr) / PAGESIZE; | |
| 1040 bin = cast(Bins)pool.pagetable[pagenum]; | |
| 1041 assert(bin <= B_PAGE); | |
| 1042 size = binsize[bin]; | |
| 1043 assert((cast(size_t)p & (size - 1)) == 0); | |
| 1044 | |
| 1045 debug (PTRCHECK2) | |
| 1046 { | |
| 1047 if (bin < B_PAGE) | |
| 1048 { | |
| 1049 // Check that p is not on a free list | |
| 1050 List *list; | |
| 1051 | |
| 1052 for (list = gcx.bucket[bin]; list; list = list.next) | |
| 1053 { | |
| 1054 assert(cast(void *)list != p); | |
| 1055 } | |
| 1056 } | |
| 1057 } | |
| 1058 } | |
| 1059 } | |
| 1060 | |
| 1061 | |
| 1062 // | |
| 1063 // | |
| 1064 // | |
| 1065 private void setStackBottom(void *p) | |
| 1066 { | |
| 1067 version (STACKGROWSDOWN) | |
| 1068 { | |
| 1069 //p = (void *)((uint *)p + 4); | |
| 1070 if (p > gcx.stackBottom) | |
| 1071 { | |
| 1072 //debug(PRINTF) printf("setStackBottom(%x)\n", p); | |
| 1073 gcx.stackBottom = p; | |
| 1074 } | |
| 1075 } | |
| 1076 else | |
| 1077 { | |
| 1078 //p = (void *)((uint *)p - 4); | |
| 1079 if (p < gcx.stackBottom) | |
| 1080 { | |
| 1081 //debug(PRINTF) printf("setStackBottom(%x)\n", p); | |
| 1082 gcx.stackBottom = cast(char *)p; | |
| 1083 } | |
| 1084 } | |
| 1085 } | |
| 1086 | |
| 1087 | |
| 1088 /** | |
| 1089 * add p to list of roots | |
| 1090 */ | |
| 1091 void addRoot(void *p) | |
| 1092 { | |
| 1093 if (!p) | |
| 1094 { | |
| 1095 return; | |
| 1096 } | |
| 1097 | |
| 1098 if (!thread_needLock()) | |
| 1099 { | |
| 1100 gcx.addRoot(p); | |
| 1101 } | |
| 1102 else synchronized (gcLock) | |
| 1103 { | |
| 1104 gcx.addRoot(p); | |
| 1105 } | |
| 1106 } | |
| 1107 | |
| 1108 | |
| 1109 /** | |
| 1110 * remove p from list of roots | |
| 1111 */ | |
| 1112 void removeRoot(void *p) | |
| 1113 { | |
| 1114 if (!p) | |
| 1115 { | |
| 1116 return; | |
| 1117 } | |
| 1118 | |
| 1119 if (!thread_needLock()) | |
| 1120 { | |
| 1121 gcx.removeRoot(p); | |
| 1122 } | |
| 1123 else synchronized (gcLock) | |
| 1124 { | |
| 1125 gcx.removeRoot(p); | |
| 1126 } | |
| 1127 } | |
| 1128 | |
| 1129 | |
| 1130 /** | |
| 1131 * add range to scan for roots | |
| 1132 */ | |
| 1133 void addRange(void *p, size_t sz) | |
| 1134 { | |
| 1135 if (!p || !sz) | |
| 1136 { | |
| 1137 return; | |
| 1138 } | |
| 1139 | |
| 1140 //debug(PRINTF) printf("+GC.addRange(pbot = x%x, ptop = x%x)\n", pbot, ptop); | |
| 1141 if (!thread_needLock()) | |
| 1142 { | |
| 1143 gcx.addRange(p, p + sz); | |
| 1144 } | |
| 1145 else synchronized (gcLock) | |
| 1146 { | |
| 1147 gcx.addRange(p, p + sz); | |
| 1148 } | |
| 1149 //debug(PRINTF) printf("-GC.addRange()\n"); | |
| 1150 } | |
| 1151 | |
| 1152 | |
| 1153 /** | |
| 1154 * remove range | |
| 1155 */ | |
| 1156 void removeRange(void *p) | |
| 1157 { | |
| 1158 if (!p) | |
| 1159 { | |
| 1160 return; | |
| 1161 } | |
| 1162 | |
| 1163 if (!thread_needLock()) | |
| 1164 { | |
| 1165 gcx.removeRange(p); | |
| 1166 } | |
| 1167 else synchronized (gcLock) | |
| 1168 { | |
| 1169 gcx.removeRange(p); | |
| 1170 } | |
| 1171 } | |
| 1172 | |
| 1173 | |
| 1174 /** | |
| 1175 * do full garbage collection | |
| 1176 */ | |
| 1177 void fullCollect() | |
| 1178 { | |
| 1179 debug(PRINTF) printf("GC.fullCollect()\n"); | |
| 1180 | |
| 1181 if (!thread_needLock()) | |
| 1182 { | |
| 1183 gcx.fullcollectshell(); | |
| 1184 } | |
| 1185 else synchronized (gcLock) | |
| 1186 { | |
| 1187 gcx.fullcollectshell(); | |
| 1188 } | |
| 1189 | |
| 1190 version (none) | |
| 1191 { | |
| 1192 GCStats stats; | |
| 1193 | |
| 1194 getStats(stats); | |
| 1195 debug(PRINTF) printf("poolsize = %x, usedsize = %x, freelistsize = %x\n", | |
| 1196 stats.poolsize, stats.usedsize, stats.freelistsize); | |
| 1197 } | |
| 1198 | |
| 1199 gcx.log_collect(); | |
| 1200 } | |
| 1201 | |
| 1202 | |
| 1203 /** | |
| 1204 * do full garbage collection ignoring roots | |
| 1205 */ | |
| 1206 void fullCollectNoStack() | |
| 1207 { | |
| 1208 if (!thread_needLock()) | |
| 1209 { | |
| 1210 gcx.noStack++; | |
| 1211 gcx.fullcollectshell(); | |
| 1212 gcx.noStack--; | |
| 1213 } | |
| 1214 else synchronized (gcLock) | |
| 1215 { | |
| 1216 gcx.noStack++; | |
| 1217 gcx.fullcollectshell(); | |
| 1218 gcx.noStack--; | |
| 1219 } | |
| 1220 } | |
| 1221 | |
| 1222 | |
| 1223 /** | |
| 1224 * Retrieve statistics about garbage collection. | |
| 1225 * Useful for debugging and tuning. | |
| 1226 */ | |
| 1227 void getStats(out GCStats stats) | |
| 1228 { | |
| 1229 if (!thread_needLock()) | |
| 1230 { | |
| 1231 getStatsNoSync(stats); | |
| 1232 } | |
| 1233 else synchronized (gcLock) | |
| 1234 { | |
| 1235 getStatsNoSync(stats); | |
| 1236 } | |
| 1237 } | |
| 1238 | |
| 1239 | |
| 1240 // | |
| 1241 // | |
| 1242 // | |
| 1243 private void getStatsNoSync(out GCStats stats) | |
| 1244 { | |
| 1245 size_t psize = 0; | |
| 1246 size_t usize = 0; | |
| 1247 size_t flsize = 0; | |
| 1248 | |
| 1249 size_t n; | |
| 1250 size_t bsize = 0; | |
| 1251 | |
| 1252 //debug(PRINTF) printf("getStats()\n"); | |
| 1253 cstring.memset(&stats, 0, GCStats.sizeof); | |
| 1254 | |
| 1255 for (n = 0; n < gcx.npools; n++) | |
| 1256 { Pool *pool = gcx.pooltable[n]; | |
| 1257 | |
| 1258 psize += pool.ncommitted * PAGESIZE; | |
| 1259 for (uint j = 0; j < pool.ncommitted; j++) | |
| 1260 { | |
| 1261 Bins bin = cast(Bins)pool.pagetable[j]; | |
| 1262 if (bin == B_FREE) | |
| 1263 stats.freeblocks++; | |
| 1264 else if (bin == B_PAGE) | |
| 1265 stats.pageblocks++; | |
| 1266 else if (bin < B_PAGE) | |
| 1267 bsize += PAGESIZE; | |
| 1268 } | |
| 1269 } | |
| 1270 | |
| 1271 for (n = 0; n < B_PAGE; n++) | |
| 1272 { | |
| 1273 //debug(PRINTF) printf("bin %d\n", n); | |
| 1274 for (List *list = gcx.bucket[n]; list; list = list.next) | |
| 1275 { | |
| 1276 //debug(PRINTF) printf("\tlist %x\n", list); | |
| 1277 flsize += binsize[n]; | |
| 1278 } | |
| 1279 } | |
| 1280 | |
| 1281 usize = bsize - flsize; | |
| 1282 | |
| 1283 stats.poolsize = psize; | |
| 1284 stats.usedsize = bsize - flsize; | |
| 1285 stats.freelistsize = flsize; | |
| 1286 } | |
| 1287 } | |
| 1288 | |
| 1289 | |
| 1290 /* ============================ Gcx =============================== */ | |
| 1291 | |
| 1292 enum | |
| 1293 { PAGESIZE = 4096, | |
| 1294 COMMITSIZE = (4096*16), | |
| 1295 POOLSIZE = (4096*256), | |
| 1296 } | |
| 1297 | |
| 1298 | |
| 1299 enum | |
| 1300 { | |
| 1301 B_16, | |
| 1302 B_32, | |
| 1303 B_64, | |
| 1304 B_128, | |
| 1305 B_256, | |
| 1306 B_512, | |
| 1307 B_1024, | |
| 1308 B_2048, | |
| 1309 B_PAGE, // start of large alloc | |
| 1310 B_PAGEPLUS, // continuation of large alloc | |
| 1311 B_FREE, // free page | |
| 1312 B_UNCOMMITTED, // memory not committed for this page | |
| 1313 B_MAX | |
| 1314 } | |
| 1315 | |
| 1316 | |
| 1317 alias ubyte Bins; | |
| 1318 | |
| 1319 | |
| 1320 struct List | |
| 1321 { | |
| 1322 List *next; | |
| 1323 } | |
| 1324 | |
| 1325 | |
| 1326 struct Range | |
| 1327 { | |
| 1328 void *pbot; | |
| 1329 void *ptop; | |
| 1330 } | |
| 1331 | |
| 1332 | |
| 1333 const uint binsize[B_MAX] = [ 16,32,64,128,256,512,1024,2048,4096 ]; | |
| 1334 const uint notbinsize[B_MAX] = [ ~(16u-1),~(32u-1),~(64u-1),~(128u-1),~(256u-1), | |
| 1335 ~(512u-1),~(1024u-1),~(2048u-1),~(4096u-1) ]; | |
| 1336 | |
| 1337 /* ============================ Gcx =============================== */ | |
| 1338 | |
| 1339 | |
| 1340 struct Gcx | |
| 1341 { | |
| 1342 debug (THREADINVARIANT) | |
| 1343 { | |
| 1344 pthread_t self; | |
| 1345 void thread_Invariant() | |
| 1346 { | |
| 1347 if (self != pthread_self()) | |
| 1348 printf("thread_Invariant(): gcx = %x, self = %x, pthread_self() = %x\n", this, self, pthread_self()); | |
| 1349 assert(self == pthread_self()); | |
| 1350 } | |
| 1351 } | |
| 1352 else | |
| 1353 { | |
| 1354 void thread_Invariant() { } | |
| 1355 } | |
| 1356 | |
| 1357 void *p_cache; | |
| 1358 size_t size_cache; | |
| 1359 | |
| 1360 size_t nroots; | |
| 1361 size_t rootdim; | |
| 1362 void **roots; | |
| 1363 | |
| 1364 size_t nranges; | |
| 1365 size_t rangedim; | |
| 1366 Range *ranges; | |
| 1367 | |
| 1368 uint noStack; // !=0 means don't scan stack | |
| 1369 uint log; // turn on logging | |
| 1370 uint anychanges; | |
| 1371 void *stackBottom; | |
| 1372 uint inited; | |
| 1373 int disabled; // turn off collections if >0 | |
| 1374 | |
| 1375 byte *minAddr; // min(baseAddr) | |
| 1376 byte *maxAddr; // max(topAddr) | |
| 1377 | |
| 1378 uint npools; | |
| 1379 Pool **pooltable; | |
| 1380 | |
| 1381 List *bucket[B_MAX]; // free list for each size | |
| 1382 | |
| 1383 | |
| 1384 void initialize() | |
| 1385 { int dummy; | |
| 1386 | |
| 1387 (cast(byte *)this)[0 .. Gcx.sizeof] = 0; | |
| 1388 stackBottom = cast(char *)&dummy; | |
| 1389 log_init(); | |
| 1390 debug (THREADINVARIANT) | |
| 1391 self = pthread_self(); | |
| 1392 //printf("gcx = %p, self = %x\n", this, self); | |
| 1393 inited = 1; | |
| 1394 } | |
| 1395 | |
| 1396 | |
| 1397 void Dtor() | |
| 1398 { | |
| 1399 inited = 0; | |
| 1400 | |
| 1401 for (uint i = 0; i < npools; i++) | |
| 1402 { Pool *pool = pooltable[i]; | |
| 1403 | |
| 1404 pool.Dtor(); | |
| 1405 cstdlib.free(pool); | |
| 1406 } | |
| 1407 if (pooltable) | |
| 1408 cstdlib.free(pooltable); | |
| 1409 | |
| 1410 if (roots) | |
| 1411 cstdlib.free(roots); | |
| 1412 | |
| 1413 if (ranges) | |
| 1414 cstdlib.free(ranges); | |
| 1415 } | |
| 1416 | |
| 1417 | |
| 1418 void Invariant() { } | |
| 1419 | |
| 1420 | |
| 1421 invariant | |
| 1422 { | |
| 1423 if (inited) | |
| 1424 { | |
| 1425 //printf("Gcx.invariant(): this = %p\n", this); | |
| 1426 uint i; | |
| 1427 | |
| 1428 // Assure we're called on the right thread | |
| 1429 debug (THREADINVARIANT) assert(self == pthread_self()); | |
| 1430 | |
| 1431 for (i = 0; i < npools; i++) | |
| 1432 { Pool *pool = pooltable[i]; | |
| 1433 | |
| 1434 pool.Invariant(); | |
| 1435 if (i == 0) | |
| 1436 { | |
| 1437 assert(minAddr == pool.baseAddr); | |
| 1438 } | |
| 1439 if (i + 1 < npools) | |
| 1440 { | |
| 1441 assert(pool.opCmp(pooltable[i + 1]) < 0); | |
| 1442 } | |
| 1443 else if (i + 1 == npools) | |
| 1444 { | |
| 1445 assert(maxAddr == pool.topAddr); | |
| 1446 } | |
| 1447 } | |
| 1448 | |
| 1449 if (roots) | |
| 1450 { | |
| 1451 assert(rootdim != 0); | |
| 1452 assert(nroots <= rootdim); | |
| 1453 } | |
| 1454 | |
| 1455 if (ranges) | |
| 1456 { | |
| 1457 assert(rangedim != 0); | |
| 1458 assert(nranges <= rangedim); | |
| 1459 | |
| 1460 for (i = 0; i < nranges; i++) | |
| 1461 { | |
| 1462 assert(ranges[i].pbot); | |
| 1463 assert(ranges[i].ptop); | |
| 1464 assert(ranges[i].pbot <= ranges[i].ptop); | |
| 1465 } | |
| 1466 } | |
| 1467 | |
| 1468 for (i = 0; i < B_PAGE; i++) | |
| 1469 { | |
| 1470 for (List *list = bucket[i]; list; list = list.next) | |
| 1471 { | |
| 1472 } | |
| 1473 } | |
| 1474 } | |
| 1475 } | |
| 1476 | |
| 1477 | |
| 1478 /** | |
| 1479 * | |
| 1480 */ | |
| 1481 void addRoot(void *p) | |
| 1482 { | |
| 1483 if (nroots == rootdim) | |
| 1484 { | |
| 1485 size_t newdim = rootdim * 2 + 16; | |
| 1486 void** newroots; | |
| 1487 | |
| 1488 newroots = cast(void **)cstdlib.malloc(newdim * newroots[0].sizeof); | |
| 1489 if (!newroots) | |
| 1490 onOutOfMemoryError(); | |
| 1491 if (roots) | |
| 1492 { cstring.memcpy(newroots, roots, nroots * newroots[0].sizeof); | |
| 1493 cstdlib.free(roots); | |
| 1494 } | |
| 1495 roots = newroots; | |
| 1496 rootdim = newdim; | |
| 1497 } | |
| 1498 roots[nroots] = p; | |
| 1499 nroots++; | |
| 1500 } | |
| 1501 | |
| 1502 | |
| 1503 /** | |
| 1504 * | |
| 1505 */ | |
| 1506 void removeRoot(void *p) | |
| 1507 { | |
| 1508 for (size_t i = nroots; i--;) | |
| 1509 { | |
| 1510 if (roots[i] == p) | |
| 1511 { | |
| 1512 nroots--; | |
| 1513 cstring.memmove(roots + i, roots + i + 1, (nroots - i) * roots[0].sizeof); | |
| 1514 return; | |
| 1515 } | |
| 1516 } | |
| 1517 assert(0); | |
| 1518 } | |
| 1519 | |
| 1520 | |
| 1521 /** | |
| 1522 * | |
| 1523 */ | |
| 1524 void addRange(void *pbot, void *ptop) | |
| 1525 { | |
| 1526 debug(PRINTF) printf("Thread %x ", pthread_self()); | |
| 1527 debug(PRINTF) printf("%x.Gcx::addRange(%x, %x), nranges = %d\n", this, pbot, ptop, nranges); | |
| 1528 if (nranges == rangedim) | |
| 1529 { | |
| 1530 size_t newdim = rangedim * 2 + 16; | |
| 1531 Range *newranges; | |
| 1532 | |
| 1533 newranges = cast(Range *)cstdlib.malloc(newdim * newranges[0].sizeof); | |
| 1534 if (!newranges) | |
| 1535 onOutOfMemoryError(); | |
| 1536 if (ranges) | |
| 1537 { cstring.memcpy(newranges, ranges, nranges * newranges[0].sizeof); | |
| 1538 cstdlib.free(ranges); | |
| 1539 } | |
| 1540 ranges = newranges; | |
| 1541 rangedim = newdim; | |
| 1542 } | |
| 1543 ranges[nranges].pbot = pbot; | |
| 1544 ranges[nranges].ptop = ptop; | |
| 1545 nranges++; | |
| 1546 } | |
| 1547 | |
| 1548 | |
| 1549 /** | |
| 1550 * | |
| 1551 */ | |
| 1552 void removeRange(void *pbot) | |
| 1553 { | |
| 1554 debug(PRINTF) printf("Thread %x ", pthread_self()); | |
| 1555 debug(PRINTF) printf("%x.Gcx.removeRange(%x), nranges = %d\n", this, pbot, nranges); | |
| 1556 for (size_t i = nranges; i--;) | |
| 1557 { | |
| 1558 if (ranges[i].pbot == pbot) | |
| 1559 { | |
| 1560 nranges--; | |
| 1561 cstring.memmove(ranges + i, ranges + i + 1, (nranges - i) * ranges[0].sizeof); | |
| 1562 return; | |
| 1563 } | |
| 1564 } | |
| 1565 debug(PRINTF) printf("Wrong thread\n"); | |
| 1566 | |
| 1567 // This is a fatal error, but ignore it. | |
| 1568 // The problem is that we can get a Close() call on a thread | |
| 1569 // other than the one the range was allocated on. | |
| 1570 //assert(zero); | |
| 1571 } | |
| 1572 | |
| 1573 | |
| 1574 /** | |
| 1575 * Find Pool that pointer is in. | |
| 1576 * Return null if not in a Pool. | |
| 1577 * Assume pooltable[] is sorted. | |
| 1578 */ | |
| 1579 Pool *findPool(void *p) | |
| 1580 { | |
| 1581 if (p >= minAddr && p < maxAddr) | |
| 1582 { | |
| 1583 if (npools == 1) | |
| 1584 { | |
| 1585 return pooltable[0]; | |
| 1586 } | |
| 1587 | |
| 1588 for (uint i = 0; i < npools; i++) | |
| 1589 { Pool *pool; | |
| 1590 | |
| 1591 pool = pooltable[i]; | |
| 1592 if (p < pool.topAddr) | |
| 1593 { if (pool.baseAddr <= p) | |
| 1594 return pool; | |
| 1595 break; | |
| 1596 } | |
| 1597 } | |
| 1598 } | |
| 1599 return null; | |
| 1600 } | |
| 1601 | |
| 1602 | |
| 1603 /** | |
| 1604 * Find base address of block containing pointer p. | |
| 1605 * Returns null if not a gc'd pointer | |
| 1606 */ | |
| 1607 void* findBase(void *p) | |
| 1608 { | |
| 1609 Pool *pool; | |
| 1610 | |
| 1611 pool = findPool(p); | |
| 1612 if (pool) | |
| 1613 { | |
| 1614 size_t offset = cast(size_t)(p - pool.baseAddr); | |
| 1615 uint pn = offset / PAGESIZE; | |
| 1616 Bins bin = cast(Bins)pool.pagetable[pn]; | |
| 1617 | |
| 1618 // Adjust bit to be at start of allocated memory block | |
| 1619 if (bin <= B_PAGE) | |
| 1620 { | |
| 1621 return pool.baseAddr + (offset & notbinsize[bin]); | |
| 1622 } | |
| 1623 else if (bin == B_PAGEPLUS) | |
| 1624 { | |
| 1625 do | |
| 1626 { --pn, offset -= PAGESIZE; | |
| 1627 } while (cast(Bins)pool.pagetable[pn] == B_PAGEPLUS); | |
| 1628 | |
| 1629 return pool.baseAddr + (offset & (offset.max ^ (PAGESIZE-1))); | |
| 1630 } | |
| 1631 else | |
| 1632 { | |
| 1633 // we are in a B_FREE or B_UNCOMMITTED page | |
| 1634 return null; | |
| 1635 } | |
| 1636 } | |
| 1637 return null; | |
| 1638 } | |
| 1639 | |
| 1640 | |
| 1641 /** | |
| 1642 * Find size of pointer p. | |
| 1643 * Returns 0 if not a gc'd pointer | |
| 1644 */ | |
| 1645 size_t findSize(void *p) | |
| 1646 { | |
| 1647 Pool *pool; | |
| 1648 size_t size = 0; | |
| 1649 | |
| 1650 pool = findPool(p); | |
| 1651 if (pool) | |
| 1652 { | |
| 1653 uint pagenum; | |
| 1654 Bins bin; | |
| 1655 | |
| 1656 pagenum = (cast(uint)(p - pool.baseAddr)) / PAGESIZE; | |
| 1657 bin = cast(Bins)pool.pagetable[pagenum]; | |
| 1658 size = binsize[bin]; | |
| 1659 if (bin == B_PAGE) | |
| 1660 { uint npages = pool.ncommitted; | |
| 1661 ubyte* pt; | |
| 1662 uint i; | |
| 1663 | |
| 1664 pt = &pool.pagetable[0]; | |
| 1665 for (i = pagenum + 1; i < npages; i++) | |
| 1666 { | |
| 1667 if (pt[i] != B_PAGEPLUS) | |
| 1668 break; | |
| 1669 } | |
| 1670 size = (i - pagenum) * PAGESIZE; | |
| 1671 } | |
| 1672 } | |
| 1673 return size; | |
| 1674 } | |
| 1675 | |
| 1676 | |
| 1677 /** | |
| 1678 * | |
| 1679 */ | |
| 1680 BlkInfo getInfo(void* p) | |
| 1681 { | |
| 1682 Pool *pool; | |
| 1683 BlkInfo info; | |
| 1684 | |
| 1685 pool = findPool(p); | |
| 1686 if (pool) | |
| 1687 { | |
| 1688 size_t offset = cast(size_t)(p - pool.baseAddr); | |
| 1689 uint pn = offset / PAGESIZE; | |
| 1690 Bins bin = cast(Bins)pool.pagetable[pn]; | |
| 1691 | |
| 1692 //////////////////////////////////////////////////////////////////// | |
| 1693 // findAddr | |
| 1694 //////////////////////////////////////////////////////////////////// | |
| 1695 | |
| 1696 if (bin <= B_PAGE) | |
| 1697 { | |
| 1698 info.base = pool.baseAddr + (offset & notbinsize[bin]); | |
| 1699 } | |
| 1700 else if (bin == B_PAGEPLUS) | |
| 1701 { | |
| 1702 do | |
| 1703 { --pn, offset -= PAGESIZE; | |
| 1704 } while (cast(Bins)pool.pagetable[pn] == B_PAGEPLUS); | |
| 1705 | |
| 1706 info.base = pool.baseAddr + (offset & (offset.max ^ (PAGESIZE-1))); | |
| 1707 | |
| 1708 // fix bin for use by size calc below | |
| 1709 bin = cast(Bins)pool.pagetable[pn]; | |
| 1710 } | |
| 1711 | |
| 1712 //////////////////////////////////////////////////////////////////// | |
| 1713 // findSize | |
| 1714 //////////////////////////////////////////////////////////////////// | |
| 1715 | |
| 1716 info.size = binsize[bin]; | |
| 1717 if (bin == B_PAGE) | |
| 1718 { uint npages = pool.ncommitted; | |
| 1719 ubyte* pt; | |
| 1720 uint i; | |
| 1721 | |
| 1722 pt = &pool.pagetable[0]; | |
| 1723 for (i = pn + 1; i < npages; i++) | |
| 1724 { | |
| 1725 if (pt[i] != B_PAGEPLUS) | |
| 1726 break; | |
| 1727 } | |
| 1728 info.size = (i - pn) * PAGESIZE; | |
| 1729 } | |
| 1730 | |
| 1731 //////////////////////////////////////////////////////////////////// | |
| 1732 // getBits | |
| 1733 //////////////////////////////////////////////////////////////////// | |
| 1734 | |
| 1735 info.attr = getBits(pool, offset / 16); | |
| 1736 } | |
| 1737 return info; | |
| 1738 } | |
| 1739 | |
| 1740 | |
| 1741 /** | |
| 1742 * Compute bin for size. | |
| 1743 */ | |
| 1744 static Bins findBin(size_t size) | |
| 1745 { Bins bin; | |
| 1746 | |
| 1747 if (size <= 256) | |
| 1748 { | |
| 1749 if (size <= 64) | |
| 1750 { | |
| 1751 if (size <= 16) | |
| 1752 bin = B_16; | |
| 1753 else if (size <= 32) | |
| 1754 bin = B_32; | |
| 1755 else | |
| 1756 bin = B_64; | |
| 1757 } | |
| 1758 else | |
| 1759 { | |
| 1760 if (size <= 128) | |
| 1761 bin = B_128; | |
| 1762 else | |
| 1763 bin = B_256; | |
| 1764 } | |
| 1765 } | |
| 1766 else | |
| 1767 { | |
| 1768 if (size <= 1024) | |
| 1769 { | |
| 1770 if (size <= 512) | |
| 1771 bin = B_512; | |
| 1772 else | |
| 1773 bin = B_1024; | |
| 1774 } | |
| 1775 else | |
| 1776 { | |
| 1777 if (size <= 2048) | |
| 1778 bin = B_2048; | |
| 1779 else | |
| 1780 bin = B_PAGE; | |
| 1781 } | |
| 1782 } | |
| 1783 return bin; | |
| 1784 } | |
| 1785 | |
| 1786 | |
| 1787 /** | |
| 1788 * Allocate a chunk of memory that is larger than a page. | |
| 1789 * Return null if out of memory. | |
| 1790 */ | |
| 1791 void *bigAlloc(size_t size) | |
| 1792 { | |
| 1793 Pool *pool; | |
| 1794 uint npages; | |
| 1795 uint n; | |
| 1796 uint pn; | |
| 1797 uint freedpages; | |
| 1798 void *p; | |
| 1799 int state; | |
| 1800 | |
| 1801 npages = (size + PAGESIZE - 1) / PAGESIZE; | |
| 1802 | |
| 1803 for (state = 0; ; ) | |
| 1804 { | |
| 1805 // This code could use some refinement when repeatedly | |
| 1806 // allocating very large arrays. | |
| 1807 | |
| 1808 for (n = 0; n < npools; n++) | |
| 1809 { | |
| 1810 pool = pooltable[n]; | |
| 1811 pn = pool.allocPages(npages); | |
| 1812 if (pn != ~0u) | |
| 1813 goto L1; | |
| 1814 } | |
| 1815 | |
| 1816 // Failed | |
| 1817 switch (state) | |
| 1818 { | |
| 1819 case 0: | |
| 1820 if (disabled) | |
| 1821 { state = 1; | |
| 1822 continue; | |
| 1823 } | |
| 1824 // Try collecting | |
| 1825 freedpages = fullcollectshell(); | |
| 1826 if (freedpages >= npools * ((POOLSIZE / PAGESIZE) / 4)) | |
| 1827 { state = 1; | |
| 1828 continue; | |
| 1829 } | |
| 1830 // Allocate new pool | |
| 1831 pool = newPool(npages); | |
| 1832 if (!pool) | |
| 1833 { state = 2; | |
| 1834 continue; | |
| 1835 } | |
| 1836 pn = pool.allocPages(npages); | |
| 1837 assert(pn != ~0u); | |
| 1838 goto L1; | |
| 1839 case 1: | |
| 1840 // Allocate new pool | |
| 1841 pool = newPool(npages); | |
| 1842 if (!pool) | |
| 1843 goto Lnomemory; | |
| 1844 pn = pool.allocPages(npages); | |
| 1845 assert(pn != ~0u); | |
| 1846 goto L1; | |
| 1847 case 2: | |
| 1848 goto Lnomemory; | |
| 1849 default: | |
| 1850 assert(false); | |
| 1851 } | |
| 1852 } | |
| 1853 | |
| 1854 L1: | |
| 1855 pool.pagetable[pn] = B_PAGE; | |
| 1856 if (npages > 1) | |
| 1857 cstring.memset(&pool.pagetable[pn + 1], B_PAGEPLUS, npages - 1); | |
| 1858 p = pool.baseAddr + pn * PAGESIZE; | |
| 1859 cstring.memset(cast(char *)p + size, 0, npages * PAGESIZE - size); | |
| 1860 debug (MEMSTOMP) cstring.memset(p, 0xF1, size); | |
| 1861 //debug(PRINTF) printf("\tp = %x\n", p); | |
| 1862 return p; | |
| 1863 | |
| 1864 Lnomemory: | |
| 1865 return null; // let mallocNoSync handle the error | |
| 1866 } | |
| 1867 | |
| 1868 | |
| 1869 /** | |
| 1870 * Allocate a new pool with at least npages in it. | |
| 1871 * Sort it into pooltable[]. | |
| 1872 * Return null if failed. | |
| 1873 */ | |
| 1874 Pool *newPool(uint npages) | |
| 1875 { | |
| 1876 Pool *pool; | |
| 1877 Pool **newpooltable; | |
| 1878 uint newnpools; | |
| 1879 uint i; | |
| 1880 | |
| 1881 //debug(PRINTF) printf("************Gcx::newPool(npages = %d)****************\n", npages); | |
| 1882 | |
| 1883 // Round up to COMMITSIZE pages | |
| 1884 npages = (npages + (COMMITSIZE/PAGESIZE) - 1) & ~(COMMITSIZE/PAGESIZE - 1); | |
| 1885 | |
| 1886 // Minimum of POOLSIZE | |
| 1887 if (npages < POOLSIZE/PAGESIZE) | |
| 1888 npages = POOLSIZE/PAGESIZE; | |
| 1889 else if (npages > POOLSIZE/PAGESIZE) | |
| 1890 { // Give us 150% of requested size, so there's room to extend | |
| 1891 auto n = npages + (npages >> 1); | |
| 1892 if (n < size_t.max/PAGESIZE) | |
| 1893 npages = n; | |
| 1894 } | |
| 1895 | |
| 1896 // Allocate successively larger pools up to 8 megs | |
| 1897 if (npools) | |
| 1898 { uint n; | |
| 1899 | |
| 1900 n = npools; | |
| 1901 if (n > 8) | |
| 1902 n = 8; // cap pool size at 8 megs | |
| 1903 n *= (POOLSIZE / PAGESIZE); | |
| 1904 if (npages < n) | |
| 1905 npages = n; | |
| 1906 } | |
| 1907 | |
| 1908 pool = cast(Pool *)cstdlib.calloc(1, Pool.sizeof); | |
| 1909 if (pool) | |
| 1910 { | |
| 1911 pool.initialize(npages); | |
| 1912 if (!pool.baseAddr) | |
| 1913 goto Lerr; | |
| 1914 | |
| 1915 newnpools = npools + 1; | |
| 1916 newpooltable = cast(Pool **)cstdlib.realloc(pooltable, newnpools * (Pool *).sizeof); | |
| 1917 if (!newpooltable) | |
| 1918 goto Lerr; | |
| 1919 | |
| 1920 // Sort pool into newpooltable[] | |
| 1921 for (i = 0; i < npools; i++) | |
| 1922 { | |
| 1923 if (pool.opCmp(newpooltable[i]) < 0) | |
| 1924 break; | |
| 1925 } | |
| 1926 cstring.memmove(newpooltable + i + 1, newpooltable + i, (npools - i) * (Pool *).sizeof); | |
| 1927 newpooltable[i] = pool; | |
| 1928 | |
| 1929 pooltable = newpooltable; | |
| 1930 npools = newnpools; | |
| 1931 | |
| 1932 minAddr = pooltable[0].baseAddr; | |
| 1933 maxAddr = pooltable[npools - 1].topAddr; | |
| 1934 } | |
| 1935 return pool; | |
| 1936 | |
| 1937 Lerr: | |
| 1938 pool.Dtor(); | |
| 1939 cstdlib.free(pool); | |
| 1940 return null; | |
| 1941 } | |
| 1942 | |
| 1943 | |
| 1944 /** | |
| 1945 * Allocate a page of bin's. | |
| 1946 * Returns: | |
| 1947 * 0 failed | |
| 1948 */ | |
| 1949 int allocPage(Bins bin) | |
| 1950 { | |
| 1951 Pool *pool; | |
| 1952 uint n; | |
| 1953 uint pn; | |
| 1954 byte *p; | |
| 1955 byte *ptop; | |
| 1956 | |
| 1957 //debug(PRINTF) printf("Gcx::allocPage(bin = %d)\n", bin); | |
| 1958 for (n = 0; n < npools; n++) | |
| 1959 { | |
| 1960 pool = pooltable[n]; | |
| 1961 pn = pool.allocPages(1); | |
| 1962 if (pn != ~0u) | |
| 1963 goto L1; | |
| 1964 } | |
| 1965 return 0; // failed | |
| 1966 | |
| 1967 L1: | |
| 1968 pool.pagetable[pn] = cast(ubyte)bin; | |
| 1969 | |
| 1970 // Convert page to free list | |
| 1971 size_t size = binsize[bin]; | |
| 1972 List **b = &bucket[bin]; | |
| 1973 | |
| 1974 p = pool.baseAddr + pn * PAGESIZE; | |
| 1975 ptop = p + PAGESIZE; | |
| 1976 for (; p < ptop; p += size) | |
| 1977 { | |
| 1978 (cast(List *)p).next = *b; | |
| 1979 *b = cast(List *)p; | |
| 1980 } | |
| 1981 return 1; | |
| 1982 } | |
| 1983 | |
| 1984 | |
| 1985 /** | |
| 1986 * Search a range of memory values and mark any pointers into the GC pool. | |
| 1987 */ | |
| 1988 void mark(void *pbot, void *ptop) | |
| 1989 { | |
| 1990 void **p1 = cast(void **)pbot; | |
| 1991 void **p2 = cast(void **)ptop; | |
| 1992 uint changes = 0; | |
| 1993 | |
| 1994 //printf("marking range: %p -> %p\n", pbot, ptop); | |
| 1995 for (; p1 < p2; p1++) | |
| 1996 { | |
| 1997 Pool *pool; | |
| 1998 byte *p = cast(byte *)(*p1); | |
| 1999 | |
| 2000 //if (log) debug(PRINTF) printf("\tmark %x\n", p); | |
| 2001 if (p >= minAddr) | |
| 2002 { | |
| 2003 pool = findPool(p); | |
| 2004 if (pool) | |
| 2005 { | |
| 2006 size_t offset = cast(size_t)(p - pool.baseAddr); | |
| 2007 uint biti; | |
| 2008 uint pn = offset / PAGESIZE; | |
| 2009 Bins bin = cast(Bins)pool.pagetable[pn]; | |
| 2010 | |
| 2011 //debug(PRINTF) printf("\t\tfound pool %x, base=%x, pn = %d, bin = %d, biti = x%x\n", pool, pool.baseAddr, pn, bin, biti); | |
| 2012 | |
| 2013 // Adjust bit to be at start of allocated memory block | |
| 2014 if (bin <= B_PAGE) | |
| 2015 { | |
| 2016 biti = (offset & notbinsize[bin]) >> 4; | |
| 2017 //debug(PRINTF) printf("\t\tbiti = x%x\n", biti); | |
| 2018 } | |
| 2019 else if (bin == B_PAGEPLUS) | |
| 2020 { | |
| 2021 do | |
| 2022 { --pn; | |
| 2023 } while (cast(Bins)pool.pagetable[pn] == B_PAGEPLUS); | |
| 2024 biti = pn * (PAGESIZE / 16); | |
| 2025 } | |
| 2026 else | |
| 2027 { | |
| 2028 // Don't mark bits in B_FREE or B_UNCOMMITTED pages | |
| 2029 continue; | |
| 2030 } | |
| 2031 | |
| 2032 //debug(PRINTF) printf("\t\tmark(x%x) = %d\n", biti, pool.mark.test(biti)); | |
| 2033 if (!pool.mark.test(biti)) | |
| 2034 { | |
| 2035 //if (log) debug(PRINTF) printf("\t\tmarking %x\n", p); | |
| 2036 pool.mark.set(biti); | |
| 2037 if (!pool.noscan.test(biti)) | |
| 2038 { | |
| 2039 pool.scan.set(biti); | |
| 2040 changes = 1; | |
| 2041 } | |
| 2042 log_parent(sentinel_add(pool.baseAddr + biti * 16), sentinel_add(pbot)); | |
| 2043 } | |
| 2044 } | |
| 2045 } | |
| 2046 } | |
| 2047 anychanges |= changes; | |
| 2048 } | |
| 2049 | |
| 2050 | |
| 2051 /** | |
| 2052 * Return number of full pages free'd. | |
| 2053 */ | |
| 2054 size_t fullcollectshell() | |
| 2055 { | |
| 2056 // The purpose of the 'shell' is to ensure all the registers | |
| 2057 // get put on the stack so they'll be scanned | |
| 2058 void *sp; | |
| 2059 size_t result; | |
|
203
e881c9b1c738
[svn r219] Fixed: the tango/lib/gc/basic garbage collector now compiles and links into an executable (change in tango/lib/llvmdc-posix.mak), closes #5 .
lindquist
parents:
132
diff
changeset
|
2060 version(LLVMDC) |
|
e881c9b1c738
[svn r219] Fixed: the tango/lib/gc/basic garbage collector now compiles and links into an executable (change in tango/lib/llvmdc-posix.mak), closes #5 .
lindquist
parents:
132
diff
changeset
|
2061 { |
|
242
ab43d1e1bf2a
[svn r259] Enabled ASM for the GC, this closes #45 by saving the registers on the stack.
lindquist
parents:
203
diff
changeset
|
2062 // put registers on the stack |
|
ab43d1e1bf2a
[svn r259] Enabled ASM for the GC, this closes #45 by saving the registers on the stack.
lindquist
parents:
203
diff
changeset
|
2063 version(D_InlineAsm_X86) |
|
ab43d1e1bf2a
[svn r259] Enabled ASM for the GC, this closes #45 by saving the registers on the stack.
lindquist
parents:
203
diff
changeset
|
2064 { |
|
ab43d1e1bf2a
[svn r259] Enabled ASM for the GC, this closes #45 by saving the registers on the stack.
lindquist
parents:
203
diff
changeset
|
2065 uint _eax, _ecx, _edx, _ebx, _esp, _ebp, _esi, _edi; |
|
ab43d1e1bf2a
[svn r259] Enabled ASM for the GC, this closes #45 by saving the registers on the stack.
lindquist
parents:
203
diff
changeset
|
2066 asm |
|
ab43d1e1bf2a
[svn r259] Enabled ASM for the GC, this closes #45 by saving the registers on the stack.
lindquist
parents:
203
diff
changeset
|
2067 { |
|
ab43d1e1bf2a
[svn r259] Enabled ASM for the GC, this closes #45 by saving the registers on the stack.
lindquist
parents:
203
diff
changeset
|
2068 mov _eax, EAX; |
|
ab43d1e1bf2a
[svn r259] Enabled ASM for the GC, this closes #45 by saving the registers on the stack.
lindquist
parents:
203
diff
changeset
|
2069 mov _ecx, ECX; |
|
ab43d1e1bf2a
[svn r259] Enabled ASM for the GC, this closes #45 by saving the registers on the stack.
lindquist
parents:
203
diff
changeset
|
2070 mov _edx, EDX; |
|
ab43d1e1bf2a
[svn r259] Enabled ASM for the GC, this closes #45 by saving the registers on the stack.
lindquist
parents:
203
diff
changeset
|
2071 mov _ebx, EBX; |
|
ab43d1e1bf2a
[svn r259] Enabled ASM for the GC, this closes #45 by saving the registers on the stack.
lindquist
parents:
203
diff
changeset
|
2072 mov _esp, ESP; |
|
ab43d1e1bf2a
[svn r259] Enabled ASM for the GC, this closes #45 by saving the registers on the stack.
lindquist
parents:
203
diff
changeset
|
2073 mov _ebp, EBP; |
|
ab43d1e1bf2a
[svn r259] Enabled ASM for the GC, this closes #45 by saving the registers on the stack.
lindquist
parents:
203
diff
changeset
|
2074 mov _esi, ESI; |
|
ab43d1e1bf2a
[svn r259] Enabled ASM for the GC, this closes #45 by saving the registers on the stack.
lindquist
parents:
203
diff
changeset
|
2075 mov _edi, EDI; |
|
ab43d1e1bf2a
[svn r259] Enabled ASM for the GC, this closes #45 by saving the registers on the stack.
lindquist
parents:
203
diff
changeset
|
2076 mov sp, ESP; |
|
ab43d1e1bf2a
[svn r259] Enabled ASM for the GC, this closes #45 by saving the registers on the stack.
lindquist
parents:
203
diff
changeset
|
2077 } |
|
ab43d1e1bf2a
[svn r259] Enabled ASM for the GC, this closes #45 by saving the registers on the stack.
lindquist
parents:
203
diff
changeset
|
2078 } |
|
ab43d1e1bf2a
[svn r259] Enabled ASM for the GC, this closes #45 by saving the registers on the stack.
lindquist
parents:
203
diff
changeset
|
2079 else |
|
ab43d1e1bf2a
[svn r259] Enabled ASM for the GC, this closes #45 by saving the registers on the stack.
lindquist
parents:
203
diff
changeset
|
2080 { |
|
ab43d1e1bf2a
[svn r259] Enabled ASM for the GC, this closes #45 by saving the registers on the stack.
lindquist
parents:
203
diff
changeset
|
2081 // FIXME |
|
ab43d1e1bf2a
[svn r259] Enabled ASM for the GC, this closes #45 by saving the registers on the stack.
lindquist
parents:
203
diff
changeset
|
2082 } |
|
203
e881c9b1c738
[svn r219] Fixed: the tango/lib/gc/basic garbage collector now compiles and links into an executable (change in tango/lib/llvmdc-posix.mak), closes #5 .
lindquist
parents:
132
diff
changeset
|
2083 } |
|
e881c9b1c738
[svn r219] Fixed: the tango/lib/gc/basic garbage collector now compiles and links into an executable (change in tango/lib/llvmdc-posix.mak), closes #5 .
lindquist
parents:
132
diff
changeset
|
2084 else version (GNU) |
| 132 | 2085 { |
| 2086 __builtin_unwind_init(); | |
| 2087 sp = & sp; | |
| 2088 } | |
| 2089 else | |
| 2090 { | |
| 2091 asm | |
| 2092 { | |
| 2093 pushad ; | |
| 2094 mov sp[EBP],ESP ; | |
| 2095 } | |
| 2096 } | |
| 2097 result = fullcollect(sp); | |
|
203
e881c9b1c738
[svn r219] Fixed: the tango/lib/gc/basic garbage collector now compiles and links into an executable (change in tango/lib/llvmdc-posix.mak), closes #5 .
lindquist
parents:
132
diff
changeset
|
2098 version(LLVMDC) |
|
e881c9b1c738
[svn r219] Fixed: the tango/lib/gc/basic garbage collector now compiles and links into an executable (change in tango/lib/llvmdc-posix.mak), closes #5 .
lindquist
parents:
132
diff
changeset
|
2099 { |
|
e881c9b1c738
[svn r219] Fixed: the tango/lib/gc/basic garbage collector now compiles and links into an executable (change in tango/lib/llvmdc-posix.mak), closes #5 .
lindquist
parents:
132
diff
changeset
|
2100 // nothing to do |
|
e881c9b1c738
[svn r219] Fixed: the tango/lib/gc/basic garbage collector now compiles and links into an executable (change in tango/lib/llvmdc-posix.mak), closes #5 .
lindquist
parents:
132
diff
changeset
|
2101 } |
|
e881c9b1c738
[svn r219] Fixed: the tango/lib/gc/basic garbage collector now compiles and links into an executable (change in tango/lib/llvmdc-posix.mak), closes #5 .
lindquist
parents:
132
diff
changeset
|
2102 else version (GNU) |
| 132 | 2103 { |
| 2104 // nothing to do | |
| 2105 } | |
| 2106 else | |
| 2107 { | |
| 2108 asm | |
| 2109 { | |
| 2110 popad ; | |
| 2111 } | |
| 2112 } | |
| 2113 return result; | |
| 2114 } | |
| 2115 | |
| 2116 | |
| 2117 /** | |
| 2118 * | |
| 2119 */ | |
| 2120 size_t fullcollect(void *stackTop) | |
| 2121 { | |
| 2122 uint n; | |
| 2123 Pool *pool; | |
| 2124 | |
| 2125 debug(COLLECT_PRINTF) printf("Gcx.fullcollect()\n"); | |
| 2126 | |
| 2127 thread_suspendAll(); | |
| 2128 | |
| 2129 p_cache = null; | |
| 2130 size_cache = 0; | |
| 2131 | |
| 2132 anychanges = 0; | |
| 2133 for (n = 0; n < npools; n++) | |
| 2134 { | |
| 2135 pool = pooltable[n]; | |
| 2136 pool.mark.zero(); | |
| 2137 pool.scan.zero(); | |
| 2138 pool.freebits.zero(); | |
| 2139 } | |
| 2140 | |
| 2141 // Mark each free entry, so it doesn't get scanned | |
| 2142 for (n = 0; n < B_PAGE; n++) | |
| 2143 { | |
| 2144 for (List *list = bucket[n]; list; list = list.next) | |
| 2145 { | |
| 2146 pool = findPool(list); | |
| 2147 assert(pool); | |
| 2148 pool.freebits.set(cast(uint)(cast(byte *)list - pool.baseAddr) / 16); | |
| 2149 } | |
| 2150 } | |
| 2151 | |
| 2152 for (n = 0; n < npools; n++) | |
| 2153 { | |
| 2154 pool = pooltable[n]; | |
| 2155 pool.mark.copy(&pool.freebits); | |
| 2156 } | |
| 2157 | |
| 2158 rt_scanStaticData( &mark ); | |
| 2159 | |
| 2160 version (MULTI_THREADED) | |
| 2161 { | |
| 2162 if (!noStack) | |
| 2163 { | |
| 2164 // Scan stacks and registers for each paused thread | |
| 2165 thread_scanAll( &mark, stackTop ); | |
| 2166 } | |
| 2167 } | |
| 2168 else | |
| 2169 { | |
| 2170 if (!noStack) | |
| 2171 { | |
| 2172 // Scan stack for main thread | |
| 2173 debug(PRINTF) printf(" scan stack bot = %x, top = %x\n", stackTop, stackBottom); | |
| 2174 version (STACKGROWSDOWN) | |
| 2175 mark(stackTop, stackBottom); | |
| 2176 else | |
| 2177 mark(stackBottom, stackTop); | |
| 2178 } | |
| 2179 } | |
| 2180 | |
| 2181 // Scan roots[] | |
| 2182 debug(COLLECT_PRINTF) printf("scan roots[]\n"); | |
| 2183 mark(roots, roots + nroots); | |
| 2184 | |
| 2185 // Scan ranges[] | |
| 2186 debug(COLLECT_PRINTF) printf("scan ranges[]\n"); | |
| 2187 //log++; | |
| 2188 for (n = 0; n < nranges; n++) | |
| 2189 { | |
| 2190 debug(COLLECT_PRINTF) printf("\t%x .. %x\n", ranges[n].pbot, ranges[n].ptop); | |
| 2191 mark(ranges[n].pbot, ranges[n].ptop); | |
| 2192 } | |
| 2193 //log--; | |
| 2194 | |
| 2195 debug(COLLECT_PRINTF) printf("\tscan heap\n"); | |
| 2196 while (anychanges) | |
| 2197 { | |
| 2198 anychanges = 0; | |
| 2199 for (n = 0; n < npools; n++) | |
| 2200 { | |
| 2201 uint *bbase; | |
| 2202 uint *b; | |
| 2203 uint *btop; | |
| 2204 | |
| 2205 pool = pooltable[n]; | |
| 2206 | |
| 2207 bbase = pool.scan.base(); | |
| 2208 btop = bbase + pool.scan.nwords; | |
| 2209 for (b = bbase; b < btop;) | |
| 2210 { Bins bin; | |
| 2211 uint pn; | |
| 2212 uint u; | |
| 2213 uint bitm; | |
| 2214 byte *o; | |
| 2215 | |
| 2216 bitm = *b; | |
| 2217 if (!bitm) | |
| 2218 { b++; | |
| 2219 continue; | |
| 2220 } | |
| 2221 *b = 0; | |
| 2222 | |
| 2223 o = pool.baseAddr + (b - bbase) * 32 * 16; | |
| 2224 if (!(bitm & 0xFFFF)) | |
| 2225 { | |
| 2226 bitm >>= 16; | |
| 2227 o += 16 * 16; | |
| 2228 } | |
| 2229 for (; bitm; o += 16, bitm >>= 1) | |
| 2230 { | |
| 2231 if (!(bitm & 1)) | |
| 2232 continue; | |
| 2233 | |
| 2234 pn = (o - pool.baseAddr) / PAGESIZE; | |
| 2235 bin = cast(Bins)pool.pagetable[pn]; | |
| 2236 if (bin < B_PAGE) | |
| 2237 { | |
| 2238 mark(o, o + binsize[bin]); | |
| 2239 } | |
| 2240 else if (bin == B_PAGE || bin == B_PAGEPLUS) | |
| 2241 { | |
| 2242 if (bin == B_PAGEPLUS) | |
| 2243 { | |
| 2244 while (pool.pagetable[pn - 1] != B_PAGE) | |
| 2245 pn--; | |
| 2246 } | |
| 2247 u = 1; | |
| 2248 while (pn + u < pool.ncommitted && pool.pagetable[pn + u] == B_PAGEPLUS) | |
| 2249 u++; | |
| 2250 mark(o, o + u * PAGESIZE); | |
| 2251 } | |
| 2252 } | |
| 2253 } | |
| 2254 } | |
| 2255 } | |
| 2256 | |
| 2257 thread_resumeAll(); | |
| 2258 | |
| 2259 // Free up everything not marked | |
| 2260 debug(COLLECT_PRINTF) printf("\tfree'ing\n"); | |
| 2261 size_t freedpages = 0; | |
| 2262 size_t freed = 0; | |
| 2263 for (n = 0; n < npools; n++) | |
| 2264 { uint pn; | |
| 2265 uint ncommitted; | |
| 2266 uint *bbase; | |
| 2267 | |
| 2268 pool = pooltable[n]; | |
| 2269 bbase = pool.mark.base(); | |
| 2270 ncommitted = pool.ncommitted; | |
| 2271 for (pn = 0; pn < ncommitted; pn++, bbase += PAGESIZE / (32 * 16)) | |
| 2272 { | |
| 2273 Bins bin = cast(Bins)pool.pagetable[pn]; | |
| 2274 | |
| 2275 if (bin < B_PAGE) | |
| 2276 { byte *p; | |
| 2277 byte *ptop; | |
| 2278 uint biti; | |
| 2279 uint bitstride; | |
| 2280 uint size = binsize[bin]; | |
| 2281 | |
| 2282 p = pool.baseAddr + pn * PAGESIZE; | |
| 2283 ptop = p + PAGESIZE; | |
| 2284 biti = pn * (PAGESIZE/16); | |
| 2285 bitstride = size / 16; | |
| 2286 | |
| 2287 version(none) // BUG: doesn't work because freebits() must also be cleared | |
| 2288 { | |
| 2289 // If free'd entire page | |
| 2290 if (bbase[0] == 0 && bbase[1] == 0 && bbase[2] == 0 && bbase[3] == 0 && | |
| 2291 bbase[4] == 0 && bbase[5] == 0 && bbase[6] == 0 && bbase[7] == 0) | |
| 2292 { | |
| 2293 for (; p < ptop; p += size, biti += bitstride) | |
| 2294 { | |
| 2295 if (pool.finals.nbits && pool.finals.testClear(biti)) | |
| 2296 rt_finalize(cast(List *)sentinel_add(p), false/*noStack > 0*/); | |
| 2297 gcx.clrBits(pool, biti, BlkAttr.ALL_BITS); | |
| 2298 | |
| 2299 List *list = cast(List *)p; | |
| 2300 //debug(PRINTF) printf("\tcollecting %x\n", list); | |
| 2301 log_free(sentinel_add(list)); | |
| 2302 | |
| 2303 debug (MEMSTOMP) cstring.memset(p, 0xF3, size); | |
| 2304 } | |
| 2305 pool.pagetable[pn] = B_FREE; | |
| 2306 freed += PAGESIZE; | |
| 2307 //debug(PRINTF) printf("freeing entire page %d\n", pn); | |
| 2308 continue; | |
| 2309 } | |
| 2310 } | |
| 2311 for (; p < ptop; p += size, biti += bitstride) | |
| 2312 { | |
| 2313 if (!pool.mark.test(biti)) | |
| 2314 { | |
| 2315 sentinel_Invariant(sentinel_add(p)); | |
| 2316 | |
| 2317 pool.freebits.set(biti); | |
| 2318 if (pool.finals.nbits && pool.finals.testClear(biti)) | |
| 2319 rt_finalize(cast(List *)sentinel_add(p), false/*noStack > 0*/); | |
| 2320 clrBits(pool, biti, BlkAttr.ALL_BITS); | |
| 2321 | |
| 2322 List *list = cast(List *)p; | |
| 2323 debug(PRINTF) printf("\tcollecting %x\n", list); | |
| 2324 log_free(sentinel_add(list)); | |
| 2325 | |
| 2326 debug (MEMSTOMP) cstring.memset(p, 0xF3, size); | |
| 2327 | |
| 2328 freed += size; | |
| 2329 } | |
| 2330 } | |
| 2331 } | |
| 2332 else if (bin == B_PAGE) | |
| 2333 { uint biti = pn * (PAGESIZE / 16); | |
| 2334 | |
| 2335 if (!pool.mark.test(biti)) | |
| 2336 { byte *p = pool.baseAddr + pn * PAGESIZE; | |
| 2337 | |
| 2338 sentinel_Invariant(sentinel_add(p)); | |
| 2339 if (pool.finals.nbits && pool.finals.testClear(biti)) | |
| 2340 rt_finalize(sentinel_add(p), false/*noStack > 0*/); | |
| 2341 clrBits(pool, biti, BlkAttr.ALL_BITS); | |
| 2342 | |
| 2343 debug(COLLECT_PRINTF) printf("\tcollecting big %x\n", p); | |
| 2344 log_free(sentinel_add(p)); | |
| 2345 pool.pagetable[pn] = B_FREE; | |
| 2346 freedpages++; | |
| 2347 debug (MEMSTOMP) cstring.memset(p, 0xF3, PAGESIZE); | |
| 2348 while (pn + 1 < ncommitted && pool.pagetable[pn + 1] == B_PAGEPLUS) | |
| 2349 { | |
| 2350 pn++; | |
| 2351 pool.pagetable[pn] = B_FREE; | |
| 2352 freedpages++; | |
| 2353 | |
| 2354 debug (MEMSTOMP) | |
| 2355 { p += PAGESIZE; | |
| 2356 cstring.memset(p, 0xF3, PAGESIZE); | |
| 2357 } | |
| 2358 } | |
| 2359 } | |
| 2360 } | |
| 2361 } | |
| 2362 } | |
| 2363 | |
| 2364 // Zero buckets | |
| 2365 bucket[] = null; | |
| 2366 | |
| 2367 // Free complete pages, rebuild free list | |
| 2368 debug(COLLECT_PRINTF) printf("\tfree complete pages\n"); | |
| 2369 size_t recoveredpages = 0; | |
| 2370 for (n = 0; n < npools; n++) | |
| 2371 { uint pn; | |
| 2372 uint ncommitted; | |
| 2373 | |
| 2374 pool = pooltable[n]; | |
| 2375 ncommitted = pool.ncommitted; | |
| 2376 for (pn = 0; pn < ncommitted; pn++) | |
| 2377 { | |
| 2378 Bins bin = cast(Bins)pool.pagetable[pn]; | |
| 2379 uint biti; | |
| 2380 uint u; | |
| 2381 | |
| 2382 if (bin < B_PAGE) | |
| 2383 { | |
| 2384 uint size = binsize[bin]; | |
| 2385 uint bitstride = size / 16; | |
| 2386 uint bitbase = pn * (PAGESIZE / 16); | |
| 2387 uint bittop = bitbase + (PAGESIZE / 16); | |
| 2388 byte *p; | |
| 2389 | |
| 2390 biti = bitbase; | |
| 2391 for (biti = bitbase; biti < bittop; biti += bitstride) | |
| 2392 { if (!pool.freebits.test(biti)) | |
| 2393 goto Lnotfree; | |
| 2394 } | |
| 2395 pool.pagetable[pn] = B_FREE; | |
| 2396 recoveredpages++; | |
| 2397 continue; | |
| 2398 | |
| 2399 Lnotfree: | |
| 2400 p = pool.baseAddr + pn * PAGESIZE; | |
| 2401 for (u = 0; u < PAGESIZE; u += size) | |
| 2402 { biti = bitbase + u / 16; | |
| 2403 if (pool.freebits.test(biti)) | |
| 2404 { List *list; | |
| 2405 | |
| 2406 list = cast(List *)(p + u); | |
| 2407 if (list.next != bucket[bin]) // avoid unnecessary writes | |
| 2408 list.next = bucket[bin]; | |
| 2409 bucket[bin] = list; | |
| 2410 } | |
| 2411 } | |
| 2412 } | |
| 2413 } | |
| 2414 } | |
| 2415 | |
| 2416 debug(COLLECT_PRINTF) printf("recovered pages = %d\n", recoveredpages); | |
| 2417 debug(COLLECT_PRINTF) printf("\tfree'd %u bytes, %u pages from %u pools\n", freed, freedpages, npools); | |
| 2418 | |
| 2419 return freedpages + recoveredpages; | |
| 2420 } | |
| 2421 | |
| 2422 | |
| 2423 /** | |
| 2424 * | |
| 2425 */ | |
| 2426 uint getBits(Pool* pool, uint biti) | |
| 2427 in | |
| 2428 { | |
| 2429 assert( pool ); | |
| 2430 } | |
| 2431 body | |
| 2432 { | |
| 2433 uint bits; | |
| 2434 | |
| 2435 if (pool.finals.nbits && | |
| 2436 pool.finals.test(biti)) | |
| 2437 bits |= BlkAttr.FINALIZE; | |
| 2438 if (pool.noscan.test(biti)) | |
| 2439 bits |= BlkAttr.NO_SCAN; | |
| 2440 // if (pool.nomove.nbits && | |
| 2441 // pool.nomove.test(biti)) | |
| 2442 // bits |= BlkAttr.NO_MOVE; | |
| 2443 return bits; | |
| 2444 } | |
| 2445 | |
| 2446 | |
| 2447 /** | |
| 2448 * | |
| 2449 */ | |
| 2450 void setBits(Pool* pool, uint biti, uint mask) | |
| 2451 in | |
| 2452 { | |
| 2453 assert( pool ); | |
| 2454 } | |
| 2455 body | |
| 2456 { | |
| 2457 if (mask & BlkAttr.FINALIZE) | |
| 2458 { | |
| 2459 if (!pool.finals.nbits) | |
| 2460 pool.finals.alloc(pool.mark.nbits); | |
| 2461 pool.finals.set(biti); | |
| 2462 } | |
| 2463 if (mask & BlkAttr.NO_SCAN) | |
| 2464 { | |
| 2465 pool.noscan.set(biti); | |
| 2466 } | |
| 2467 // if (mask & BlkAttr.NO_MOVE) | |
| 2468 // { | |
| 2469 // if (!pool.nomove.nbits) | |
| 2470 // pool.nomove.alloc(pool.mark.nbits); | |
| 2471 // pool.nomove.set(biti); | |
| 2472 // } | |
| 2473 } | |
| 2474 | |
| 2475 | |
| 2476 /** | |
| 2477 * | |
| 2478 */ | |
| 2479 void clrBits(Pool* pool, uint biti, uint mask) | |
| 2480 in | |
| 2481 { | |
| 2482 assert( pool ); | |
| 2483 } | |
| 2484 body | |
| 2485 { | |
| 2486 if (mask & BlkAttr.FINALIZE && pool.finals.nbits) | |
| 2487 pool.finals.clear(biti); | |
| 2488 if (mask & BlkAttr.NO_SCAN) | |
| 2489 pool.noscan.clear(biti); | |
| 2490 // if (mask & BlkAttr.NO_MOVE && pool.nomove.nbits) | |
| 2491 // pool.nomove.clear(biti); | |
| 2492 } | |
| 2493 | |
| 2494 | |
| 2495 /***** Leak Detector ******/ | |
| 2496 | |
| 2497 | |
| 2498 debug (LOGGING) | |
| 2499 { | |
| 2500 LogArray current; | |
| 2501 LogArray prev; | |
| 2502 | |
| 2503 | |
| 2504 void log_init() | |
| 2505 { | |
| 2506 //debug(PRINTF) printf("+log_init()\n"); | |
| 2507 current.reserve(1000); | |
| 2508 prev.reserve(1000); | |
| 2509 //debug(PRINTF) printf("-log_init()\n"); | |
| 2510 } | |
| 2511 | |
| 2512 | |
| 2513 void log_malloc(void *p, size_t size) | |
| 2514 { | |
| 2515 //debug(PRINTF) printf("+log_malloc(p = %x, size = %d)\n", p, size); | |
| 2516 Log log; | |
| 2517 | |
| 2518 log.p = p; | |
| 2519 log.size = size; | |
| 2520 log.line = GC.line; | |
| 2521 log.file = GC.file; | |
| 2522 log.parent = null; | |
| 2523 | |
| 2524 GC.line = 0; | |
| 2525 GC.file = null; | |
| 2526 | |
| 2527 current.push(log); | |
| 2528 //debug(PRINTF) printf("-log_malloc()\n"); | |
| 2529 } | |
| 2530 | |
| 2531 | |
| 2532 void log_free(void *p) | |
| 2533 { | |
| 2534 //debug(PRINTF) printf("+log_free(%x)\n", p); | |
| 2535 size_t i; | |
| 2536 | |
| 2537 i = current.find(p); | |
| 2538 if (i == ~0u) | |
| 2539 { | |
| 2540 debug(PRINTF) printf("free'ing unallocated memory %x\n", p); | |
| 2541 } | |
| 2542 else | |
| 2543 current.remove(i); | |
| 2544 //debug(PRINTF) printf("-log_free()\n"); | |
| 2545 } | |
| 2546 | |
| 2547 | |
| 2548 void log_collect() | |
| 2549 { | |
| 2550 //debug(PRINTF) printf("+log_collect()\n"); | |
| 2551 // Print everything in current that is not in prev | |
| 2552 | |
| 2553 debug(PRINTF) printf("New pointers this cycle: --------------------------------\n"); | |
| 2554 size_t used = 0; | |
| 2555 for (size_t i = 0; i < current.dim; i++) | |
| 2556 { | |
| 2557 size_t j; | |
| 2558 | |
| 2559 j = prev.find(current.data[i].p); | |
| 2560 if (j == ~0u) | |
| 2561 current.data[i].print(); | |
| 2562 else | |
| 2563 used++; | |
| 2564 } | |
| 2565 | |
| 2566 debug(PRINTF) printf("All roots this cycle: --------------------------------\n"); | |
| 2567 for (size_t i = 0; i < current.dim; i++) | |
| 2568 { | |
| 2569 void *p; | |
| 2570 size_t j; | |
| 2571 | |
| 2572 p = current.data[i].p; | |
| 2573 if (!findPool(current.data[i].parent)) | |
| 2574 { | |
| 2575 j = prev.find(current.data[i].p); | |
| 2576 if (j == ~0u) | |
| 2577 debug(PRINTF) printf("N"); | |
| 2578 else | |
| 2579 debug(PRINTF) printf(" ");; | |
| 2580 current.data[i].print(); | |
| 2581 } | |
| 2582 } | |
| 2583 | |
| 2584 debug(PRINTF) printf("Used = %d-------------------------------------------------\n", used); | |
| 2585 prev.copy(¤t); | |
| 2586 | |
| 2587 debug(PRINTF) printf("-log_collect()\n"); | |
| 2588 } | |
| 2589 | |
| 2590 | |
| 2591 void log_parent(void *p, void *parent) | |
| 2592 { | |
| 2593 //debug(PRINTF) printf("+log_parent()\n"); | |
| 2594 size_t i; | |
| 2595 | |
| 2596 i = current.find(p); | |
| 2597 if (i == ~0u) | |
| 2598 { | |
| 2599 debug(PRINTF) printf("parent'ing unallocated memory %x, parent = %x\n", p, parent); | |
| 2600 Pool *pool; | |
| 2601 pool = findPool(p); | |
| 2602 assert(pool); | |
| 2603 size_t offset = cast(size_t)(p - pool.baseAddr); | |
| 2604 uint biti; | |
| 2605 uint pn = offset / PAGESIZE; | |
| 2606 Bins bin = cast(Bins)pool.pagetable[pn]; | |
| 2607 biti = (offset & notbinsize[bin]); | |
| 2608 debug(PRINTF) printf("\tbin = %d, offset = x%x, biti = x%x\n", bin, offset, biti); | |
| 2609 } | |
| 2610 else | |
| 2611 { | |
| 2612 current.data[i].parent = parent; | |
| 2613 } | |
| 2614 //debug(PRINTF) printf("-log_parent()\n"); | |
| 2615 } | |
| 2616 | |
| 2617 } | |
| 2618 else | |
| 2619 { | |
| 2620 void log_init() { } | |
| 2621 void log_malloc(void *p, size_t size) { } | |
| 2622 void log_free(void *p) { } | |
| 2623 void log_collect() { } | |
| 2624 void log_parent(void *p, void *parent) { } | |
| 2625 } | |
| 2626 } | |
| 2627 | |
| 2628 | |
| 2629 /* ============================ Pool =============================== */ | |
| 2630 | |
| 2631 | |
| 2632 struct Pool | |
| 2633 { | |
| 2634 byte* baseAddr; | |
| 2635 byte* topAddr; | |
| 2636 GCBits mark; // entries already scanned, or should not be scanned | |
| 2637 GCBits scan; // entries that need to be scanned | |
| 2638 GCBits freebits; // entries that are on the free list | |
| 2639 GCBits finals; // entries that need finalizer run on them | |
| 2640 GCBits noscan; // entries that should not be scanned | |
| 2641 | |
| 2642 uint npages; | |
| 2643 uint ncommitted; // ncommitted <= npages | |
| 2644 ubyte* pagetable; | |
| 2645 | |
| 2646 | |
| 2647 void initialize(uint npages) | |
| 2648 { | |
| 2649 size_t poolsize; | |
| 2650 | |
| 2651 //debug(PRINTF) printf("Pool::Pool(%u)\n", npages); | |
| 2652 poolsize = npages * PAGESIZE; | |
| 2653 assert(poolsize >= POOLSIZE); | |
| 2654 baseAddr = cast(byte *)os_mem_map(poolsize); | |
| 2655 | |
| 2656 // Some of the code depends on page alignment of memory pools | |
| 2657 assert((cast(uint)baseAddr & (PAGESIZE - 1)) == 0); | |
| 2658 | |
| 2659 if (!baseAddr) | |
| 2660 { | |
| 2661 //debug(PRINTF) printf("GC fail: poolsize = x%x, errno = %d\n", poolsize, errno); | |
| 2662 //debug(PRINTF) printf("message = '%s'\n", sys_errlist[errno]); | |
| 2663 | |
| 2664 npages = 0; | |
| 2665 poolsize = 0; | |
| 2666 } | |
| 2667 //assert(baseAddr); | |
| 2668 topAddr = baseAddr + poolsize; | |
| 2669 | |
| 2670 mark.alloc(poolsize / 16); | |
| 2671 scan.alloc(poolsize / 16); | |
| 2672 freebits.alloc(poolsize / 16); | |
| 2673 noscan.alloc(poolsize / 16); | |
| 2674 | |
| 2675 pagetable = cast(ubyte*)cstdlib.malloc(npages); | |
| 2676 if (!pagetable) | |
| 2677 onOutOfMemoryError(); | |
| 2678 cstring.memset(pagetable, B_UNCOMMITTED, npages); | |
| 2679 | |
| 2680 this.npages = npages; | |
| 2681 ncommitted = 0; | |
| 2682 } | |
| 2683 | |
| 2684 | |
| 2685 void Dtor() | |
| 2686 { | |
| 2687 if (baseAddr) | |
| 2688 { | |
| 2689 int result; | |
| 2690 | |
| 2691 if (ncommitted) | |
| 2692 { | |
| 2693 result = os_mem_decommit(baseAddr, 0, ncommitted * PAGESIZE); | |
| 2694 assert(result == 0); | |
| 2695 ncommitted = 0; | |
| 2696 } | |
| 2697 | |
| 2698 if (npages) | |
| 2699 { | |
| 2700 result = os_mem_unmap(baseAddr, npages * PAGESIZE); | |
| 2701 assert(result == 0); | |
| 2702 npages = 0; | |
| 2703 } | |
| 2704 | |
| 2705 baseAddr = null; | |
| 2706 topAddr = null; | |
| 2707 } | |
| 2708 if (pagetable) | |
| 2709 cstdlib.free(pagetable); | |
| 2710 | |
| 2711 mark.Dtor(); | |
| 2712 scan.Dtor(); | |
| 2713 freebits.Dtor(); | |
| 2714 finals.Dtor(); | |
| 2715 noscan.Dtor(); | |
| 2716 } | |
| 2717 | |
| 2718 | |
| 2719 void Invariant() { } | |
| 2720 | |
| 2721 | |
| 2722 invariant | |
| 2723 { | |
| 2724 //mark.Invariant(); | |
| 2725 //scan.Invariant(); | |
| 2726 //freebits.Invariant(); | |
| 2727 //finals.Invariant(); | |
| 2728 //noscan.Invariant(); | |
| 2729 | |
| 2730 if (baseAddr) | |
| 2731 { | |
| 2732 //if (baseAddr + npages * PAGESIZE != topAddr) | |
| 2733 //printf("baseAddr = %p, npages = %d, topAddr = %p\n", baseAddr, npages, topAddr); | |
| 2734 assert(baseAddr + npages * PAGESIZE == topAddr); | |
| 2735 assert(ncommitted <= npages); | |
| 2736 } | |
| 2737 | |
| 2738 for (uint i = 0; i < npages; i++) | |
| 2739 { Bins bin = cast(Bins)pagetable[i]; | |
| 2740 | |
| 2741 assert(bin < B_MAX); | |
| 2742 } | |
| 2743 } | |
| 2744 | |
| 2745 | |
| 2746 /** | |
| 2747 * Allocate n pages from Pool. | |
| 2748 * Returns ~0u on failure. | |
| 2749 */ | |
| 2750 uint allocPages(uint n) | |
| 2751 { | |
| 2752 uint i; | |
| 2753 uint n2; | |
| 2754 | |
| 2755 //debug(PRINTF) printf("Pool::allocPages(n = %d)\n", n); | |
| 2756 n2 = n; | |
| 2757 for (i = 0; i < ncommitted; i++) | |
| 2758 { | |
| 2759 if (pagetable[i] == B_FREE) | |
| 2760 { | |
| 2761 if (--n2 == 0) | |
| 2762 { //debug(PRINTF) printf("\texisting pn = %d\n", i - n + 1); | |
| 2763 return i - n + 1; | |
| 2764 } | |
| 2765 } | |
| 2766 else | |
| 2767 n2 = n; | |
| 2768 } | |
| 2769 return extendPages(n); | |
| 2770 } | |
| 2771 | |
| 2772 /** | |
| 2773 * Extend Pool by n pages. | |
| 2774 * Returns ~0u on failure. | |
| 2775 */ | |
| 2776 uint extendPages(uint n) | |
| 2777 { | |
| 2778 //debug(PRINTF) printf("Pool::extendPages(n = %d)\n", n); | |
| 2779 if (ncommitted + n <= npages) | |
| 2780 { | |
| 2781 uint tocommit; | |
| 2782 | |
| 2783 tocommit = (n + (COMMITSIZE/PAGESIZE) - 1) & ~(COMMITSIZE/PAGESIZE - 1); | |
| 2784 if (ncommitted + tocommit > npages) | |
| 2785 tocommit = npages - ncommitted; | |
| 2786 //debug(PRINTF) printf("\tlooking to commit %d more pages\n", tocommit); | |
| 2787 //fflush(stdout); | |
| 2788 if (os_mem_commit(baseAddr, ncommitted * PAGESIZE, tocommit * PAGESIZE) == 0) | |
| 2789 { | |
| 2790 cstring.memset(pagetable + ncommitted, B_FREE, tocommit); | |
| 2791 auto i = ncommitted; | |
| 2792 ncommitted += tocommit; | |
| 2793 | |
| 2794 while (i && pagetable[i - 1] == B_FREE) | |
| 2795 i--; | |
| 2796 | |
| 2797 return i; | |
| 2798 } | |
| 2799 //debug(PRINTF) printf("\tfailed to commit %d pages\n", tocommit); | |
| 2800 } | |
| 2801 | |
| 2802 return ~0u; | |
| 2803 } | |
| 2804 | |
| 2805 | |
| 2806 /** | |
| 2807 * Free npages pages starting with pagenum. | |
| 2808 */ | |
| 2809 void freePages(uint pagenum, uint npages) | |
| 2810 { | |
| 2811 cstring.memset(&pagetable[pagenum], B_FREE, npages); | |
| 2812 } | |
| 2813 | |
| 2814 | |
| 2815 /** | |
| 2816 * Used for sorting pooltable[] | |
| 2817 */ | |
| 2818 int opCmp(Pool *p2) | |
| 2819 { | |
| 2820 if (baseAddr < p2.baseAddr) | |
| 2821 return -1; | |
| 2822 else | |
| 2823 return cast(int)(baseAddr > p2.baseAddr); | |
| 2824 } | |
| 2825 } | |
| 2826 | |
| 2827 | |
| 2828 /* ============================ SENTINEL =============================== */ | |
| 2829 | |
| 2830 | |
| 2831 version (SENTINEL) | |
| 2832 { | |
| 2833 const size_t SENTINEL_PRE = cast(size_t) 0xF4F4F4F4F4F4F4F4UL; // 32 or 64 bits | |
| 2834 const ubyte SENTINEL_POST = 0xF5; // 8 bits | |
| 2835 const uint SENTINEL_EXTRA = 2 * size_t.sizeof + 1; | |
| 2836 | |
| 2837 | |
| 2838 size_t* sentinel_size(void *p) { return &(cast(size_t *)p)[-2]; } | |
| 2839 size_t* sentinel_pre(void *p) { return &(cast(size_t *)p)[-1]; } | |
| 2840 ubyte* sentinel_post(void *p) { return &(cast(ubyte *)p)[sentinel_size(p)]; } | |
| 2841 | |
| 2842 | |
| 2843 void sentinel_init(void *p, size_t size) | |
| 2844 { | |
| 2845 *sentinel_size(p) = size; | |
| 2846 *sentinel_pre(p) = SENTINEL_PRE; | |
| 2847 *sentinel_post(p) = SENTINEL_POST; | |
| 2848 } | |
| 2849 | |
| 2850 | |
| 2851 void sentinel_Invariant(void *p) | |
| 2852 { | |
| 2853 assert(*sentinel_pre(p) == SENTINEL_PRE); | |
| 2854 assert(*sentinel_post(p) == SENTINEL_POST); | |
| 2855 } | |
| 2856 | |
| 2857 | |
| 2858 void *sentinel_add(void *p) | |
| 2859 { | |
| 2860 return p + 2 * size_t.sizeof; | |
| 2861 } | |
| 2862 | |
| 2863 | |
| 2864 void *sentinel_sub(void *p) | |
| 2865 { | |
| 2866 return p - 2 * size_t.sizeof; | |
| 2867 } | |
| 2868 } | |
| 2869 else | |
| 2870 { | |
| 2871 const uint SENTINEL_EXTRA = 0; | |
| 2872 | |
| 2873 | |
| 2874 void sentinel_init(void *p, size_t size) | |
| 2875 { | |
| 2876 } | |
| 2877 | |
| 2878 | |
| 2879 void sentinel_Invariant(void *p) | |
| 2880 { | |
| 2881 } | |
| 2882 | |
| 2883 | |
| 2884 void *sentinel_add(void *p) | |
| 2885 { | |
| 2886 return p; | |
| 2887 } | |
| 2888 | |
| 2889 | |
| 2890 void *sentinel_sub(void *p) | |
| 2891 { | |
| 2892 return p; | |
| 2893 } | |
| 2894 } | |
| 2895 |