1/*********************************************************************** 2* * 3* This software is part of the ast package * 4* Copyright (c) 1985-2011 AT&T Intellectual Property * 5* and is licensed under the * 6* Common Public License, Version 1.0 * 7* by AT&T Intellectual Property * 8* * 9* A copy of the License is available at * 10* http://www.opensource.org/licenses/cpl1.0.txt * 11* (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9) * 12* * 13* Information and Software Systems Research * 14* AT&T Research * 15* Florham Park NJ * 16* * 17* Glenn Fowler <gsf@research.att.com> * 18* David Korn <dgk@research.att.com> * 19* Phong Vo <kpv@research.att.com> * 20* * 21***********************************************************************/ 22#if defined(_UWIN) && defined(_BLD_ast) 23 24void _STUB_vmbest(){} 25 26#else 27 28#include "vmhdr.h" 29 30/* Best-fit allocation method. This is based on a best-fit strategy 31** using a splay tree for storage of lists of free blocks of the same 32** size. Recent free blocks may be cached for fast reuse. 33** 34** Written by Kiem-Phong Vo, kpv@research.att.com, 01/16/94. 35*/ 36 37#ifdef DEBUG 38static int N_free; /* # of free calls */ 39static int N_alloc; /* # of alloc calls */ 40static int N_resize; /* # of resize calls */ 41static int N_wild; /* # allocated from the wild block */ 42static int N_last; /* # allocated from last free block */ 43static int N_reclaim; /* # of bestreclaim calls */ 44 45#undef VM_TRUST /* always check for locking, etc.s */ 46#define VM_TRUST 0 47#endif /*DEBUG*/ 48 49#if _BLD_posix 50#define logmsg(d,a ...) logsrc(d,__FILE__,__LINE__,a) 51 52extern int logsrc(int, const char*, int, const char*, ...); 53#endif /*_BLD_posix*/ 54 55#define COMPACT 8 /* factor to decide when to compact */ 56 57/* Check to see if a block is in the free tree */ 58#if __STD_C 59static int vmintree(Block_t* node, Block_t* b) 60#else 61static int vmintree(node,b) 62Block_t* node; 63Block_t* b; 64#endif 65{ Block_t* t; 66 67 for(t = node; t; t = LINK(t)) 68 if(t == b) 69 return 1; 70 if(LEFT(node) && vmintree(LEFT(node),b)) 71 return 1; 72 if(RIGHT(node) && vmintree(RIGHT(node),b)) 73 return 1; 74 return 0; 75} 76 77#if __STD_C 78static int vmonlist(Block_t* list, Block_t* b) 79#else 80static int vmonlist(list,b) 81Block_t* list; 82Block_t* b; 83#endif 84{ 85 for(; list; list = LINK(list)) 86 if(list == b) 87 return 1; 88 return 0; 89} 90 91/* Check to see if a block is known to be free */ 92#if __STD_C 93static int vmisfree(Vmdata_t* vd, Block_t* b) 94#else 95static int vmisfree(vd,b) 96Vmdata_t* vd; 97Block_t* b; 98#endif 99{ 100 if(SIZE(b) & (BUSY|JUNK|PFREE)) 101 return 0; 102 103 if(b == vd->wild) 104 return 1; 105 106 if(SIZE(b) < MAXTINY) 107 return vmonlist(TINY(vd)[INDEX(SIZE(b))], b); 108 109 if(vd->root) 110 return vmintree(vd->root, b); 111 112 return 0; 113} 114 115/* Check to see if a block is known to be junked */ 116#if __STD_C 117static int vmisjunk(Vmdata_t* vd, Block_t* b) 118#else 119static int vmisjunk(vd,b) 120Vmdata_t* vd; 121Block_t* b; 122#endif 123{ 124 Block_t* t; 125 126 if((SIZE(b)&BUSY) == 0 || (SIZE(b)&JUNK) == 0) 127 return 0; 128 129 if(b == vd->free) /* recently freed */ 130 return 1; 131 132 /* check the list that b is supposed to be in */ 133 for(t = CACHE(vd)[C_INDEX(SIZE(b))]; t; t = LINK(t)) 134 if(t == b) 135 return 1; 136 137 /* on occasions, b may be put onto the catch-all list */ 138 if(C_INDEX(SIZE(b)) < S_CACHE) 139 for(t = CACHE(vd)[S_CACHE]; t; t = LINK(t)) 140 if(t == b) 141 return 1; 142 143 return 0; 144} 145 146/* check to see if the free tree is in good shape */ 147#if __STD_C 148static int vmchktree(Block_t* node) 149#else 150static int vmchktree(node) 151Block_t* node; 152#endif 153{ Block_t* t; 154 155 if(SIZE(node) & BITS) 156 { /**/ASSERT(0); return -1; } 157 158 for(t = LINK(node); t; t = LINK(t)) 159 if(SIZE(t) != SIZE(node)) 160 { /**/ASSERT(0); return -1; } 161 162 if((t = LEFT(node)) ) 163 { if(SIZE(t) >= SIZE(node) ) 164 { /**/ASSERT(0); return -1; } 165 else return vmchktree(t); 166 } 167 if((t = RIGHT(node)) ) 168 { if(SIZE(t) <= SIZE(node) ) 169 { /**/ASSERT(0); return -1; } 170 else return vmchktree(t); 171 } 172 173 return 0; 174} 175 176#if __STD_C 177int _vmbestcheck(Vmdata_t* vd, Block_t* freeb) 178#else 179int _vmbestcheck(vd, freeb) 180Vmdata_t* vd; 181Block_t* freeb; /* known to be free but not on any free list */ 182#endif 183{ 184 reg Seg_t *seg; 185 reg Block_t *b, *endb, *nextb; 186 int rv = 0; 187 188 if(!CHECK()) 189 return 0; 190 191 /* make sure the free tree is still in shape */ 192 if(vd->root && vmchktree(vd->root) < 0 ) 193 { rv = -1; /**/ASSERT(0); } 194 195 for(seg = vd->seg; seg && rv == 0; seg = seg->next) 196 { b = SEGBLOCK(seg); 197 endb = (Block_t*)(seg->baddr - sizeof(Head_t)); 198 for(; b < endb && rv == 0; b = nextb) 199 { nextb = (Block_t*)((Vmuchar_t*)DATA(b) + (SIZE(b)&~BITS) ); 200 201 if(!ISBUSY(SIZE(b)) ) /* a completely free block */ 202 { /* there should be no marked bits of any type */ 203 if(SIZE(b) & (BUSY|JUNK|PFREE) ) 204 { rv = -1; /**/ASSERT(0); } 205 206 /* next block must be busy and marked PFREE */ 207 if(!ISBUSY(SIZE(nextb)) || !ISPFREE(SIZE(nextb)) ) 208 { rv = -1; /**/ASSERT(0); } 209 210 /* must have a self-reference pointer */ 211 if(*SELF(b) != b) 212 { rv = -1; /**/ASSERT(0); } 213 214 /* segment pointer should be well-defined */ 215 if(!TINIEST(b) && SEG(b) != seg) 216 { rv = -1; /**/ASSERT(0); } 217 218 /* must be on a free list */ 219 if(b != freeb && !vmisfree(vd, b) ) 220 { rv = -1; /**/ASSERT(0); } 221 } 222 else 223 { /* segment pointer should be well-defined */ 224 if(SEG(b) != seg) 225 { rv = -1; /**/ASSERT(0); } 226 227 /* next block should not be marked PFREE */ 228 if(ISPFREE(SIZE(nextb)) ) 229 { rv = -1; /**/ASSERT(0); } 230 231 /* if PFREE, last block should be free */ 232 if(ISPFREE(SIZE(b)) && LAST(b) != freeb && 233 !vmisfree(vd, LAST(b)) ) 234 { rv = -1; /**/ASSERT(0); } 235 236 /* if free but unreclaimed, should be junk */ 237 if(ISJUNK(SIZE(b)) && !vmisjunk(vd, b)) 238 { rv = -1; /**/ASSERT(0); } 239 } 240 } 241 } 242 243 return rv; 244} 245 246/* Tree rotation functions */ 247#define RROTATE(x,y) (LEFT(x) = RIGHT(y), RIGHT(y) = (x), (x) = (y)) 248#define LROTATE(x,y) (RIGHT(x) = LEFT(y), LEFT(y) = (x), (x) = (y)) 249#define RLINK(s,x) ((s) = LEFT(s) = (x)) 250#define LLINK(s,x) ((s) = RIGHT(s) = (x)) 251 252/* Find and delete a suitable element in the free tree. */ 253#if __STD_C 254static Block_t* bestsearch(Vmdata_t* vd, reg size_t size, Block_t* wanted) 255#else 256static Block_t* bestsearch(vd, size, wanted) 257Vmdata_t* vd; 258reg size_t size; 259Block_t* wanted; 260#endif 261{ 262 reg size_t s; 263 reg Block_t *t, *root, *l, *r; 264 Block_t link; 265 266 /* extracting a tiniest block from its list */ 267 if((root = wanted) && size == TINYSIZE) 268 { reg Seg_t* seg; 269 270 l = TLEFT(root); 271 if((r = LINK(root)) ) 272 TLEFT(r) = l; 273 if(l) 274 LINK(l) = r; 275 else TINY(vd)[0] = r; 276 277 seg = vd->seg; 278 if(!seg->next) 279 SEG(root) = seg; 280 else for(;; seg = seg->next) 281 { if((Vmuchar_t*)root > (Vmuchar_t*)seg->addr && 282 (Vmuchar_t*)root < seg->baddr) 283 { SEG(root) = seg; 284 break; 285 } 286 } 287 288 return root; 289 } 290 291 /**/ASSERT(!vd->root || vmchktree(vd->root) == 0); 292 293 /* find the right one to delete */ 294 l = r = &link; 295 if((root = vd->root) ) do 296 { /**/ ASSERT(!ISBITS(size) && !ISBITS(SIZE(root))); 297 if(size == (s = SIZE(root)) ) 298 break; 299 if(size < s) 300 { if((t = LEFT(root)) ) 301 { if(size <= (s = SIZE(t)) ) 302 { RROTATE(root,t); 303 if(size == s) 304 break; 305 t = LEFT(root); 306 } 307 else 308 { LLINK(l,t); 309 t = RIGHT(t); 310 } 311 } 312 RLINK(r,root); 313 } 314 else 315 { if((t = RIGHT(root)) ) 316 { if(size >= (s = SIZE(t)) ) 317 { LROTATE(root,t); 318 if(size == s) 319 break; 320 t = RIGHT(root); 321 } 322 else 323 { RLINK(r,t); 324 t = LEFT(t); 325 } 326 } 327 LLINK(l,root); 328 } 329 /**/ ASSERT(root != t); 330 } while((root = t) ); 331 332 if(root) /* found it, now isolate it */ 333 { RIGHT(l) = LEFT(root); 334 LEFT(r) = RIGHT(root); 335 } 336 else /* nothing exactly fit */ 337 { LEFT(r) = NIL(Block_t*); 338 RIGHT(l) = NIL(Block_t*); 339 340 /* grab the least one from the right tree */ 341 if((root = LEFT(&link)) ) 342 { while((t = LEFT(root)) ) 343 RROTATE(root,t); 344 LEFT(&link) = RIGHT(root); 345 } 346 } 347 348 if(root && (r = LINK(root)) ) 349 { /* head of a link list, use next one for root */ 350 LEFT(r) = RIGHT(&link); 351 RIGHT(r) = LEFT(&link); 352 } 353 else if(!(r = LEFT(&link)) ) 354 r = RIGHT(&link); 355 else /* graft left tree to right tree */ 356 { while((t = LEFT(r)) ) 357 RROTATE(r,t); 358 LEFT(r) = RIGHT(&link); 359 } 360 vd->root = r; /**/ASSERT(!r || !ISBITS(SIZE(r))); 361 362 /**/ASSERT(!vd->root || vmchktree(vd->root) == 0); 363 /**/ASSERT(!wanted || wanted == root); 364 365 return root; 366} 367 368/* Reclaim all delayed free blocks into the free tree */ 369#if __STD_C 370static int bestreclaim(reg Vmdata_t* vd, Block_t* wanted, int c) 371#else 372static int bestreclaim(vd, wanted, c) 373reg Vmdata_t* vd; 374Block_t* wanted; 375int c; 376#endif 377{ 378 reg size_t size, s; 379 reg Block_t *fp, *np, *t, *list; 380 reg int n, saw_wanted; 381 reg Seg_t *seg; 382 383 /**/COUNT(N_reclaim); 384 /**/ASSERT(_vmbestcheck(vd, NIL(Block_t*)) == 0); 385 386 if((fp = vd->free) ) 387 { LINK(fp) = CACHE(vd)[S_CACHE]; CACHE(vd)[S_CACHE] = fp; 388 vd->free = NIL(Block_t*); 389 } 390 391 saw_wanted = wanted ? 0 : 1; 392 for(n = S_CACHE; n >= c; --n) 393 { list = CACHE(vd)[n]; CACHE(vd)[n] = NIL(Block_t*); 394 while((fp = list) ) 395 { /* Note that below here we allow ISJUNK blocks to be 396 ** forward-merged even though they are not removed from 397 ** the list immediately. In this way, the list is 398 ** scanned only once. It works because the LINK and SIZE 399 ** fields are not destroyed during the merging. This can 400 ** be seen by observing that a tiniest block has a 2-word 401 ** header and a 2-word body. Merging a tiniest block 402 ** (1seg) and the next block (2seg) looks like this: 403 ** 1seg size link left 2seg size link left .... 404 ** 1seg size link left rite xxxx xxxx .... self 405 ** After the merge, the 2seg word is replaced by the RIGHT 406 ** pointer of the new block and somewhere beyond the 407 ** two xxxx fields, the SELF pointer will replace some 408 ** other word. The important part is that the two xxxx 409 ** fields are kept intact. 410 */ 411 list = LINK(list); /**/ASSERT(!vmonlist(list,fp)); 412 413 size = SIZE(fp); 414 if(!ISJUNK(size)) /* already done */ 415 continue; 416 417 if(_Vmassert & VM_region) 418 { /* see if this address is from region */ 419 for(seg = vd->seg; seg; seg = seg->next) 420 if(fp >= SEGBLOCK(seg) && fp < (Block_t*)seg->baddr ) 421 break; 422 if(!seg) /* must be a bug in application code! */ 423 { /**/ ASSERT(seg != NIL(Seg_t*)); 424 continue; 425 } 426 } 427 428 if(ISPFREE(size)) /* backward merge */ 429 { fp = LAST(fp); 430#if _BLD_posix 431 if (fp < (Block_t*)0x00120000) 432 { 433 logmsg(0, "bestreclaim fp=%p", fp); 434 ASSERT(!fp); 435 } 436#endif 437 s = SIZE(fp); /**/ASSERT(!(s&BITS)); 438 REMOVE(vd,fp,INDEX(s),t,bestsearch); 439 size = (size&~BITS) + s + sizeof(Head_t); 440 } 441 else size &= ~BITS; 442 443 for(;;) /* forward merge */ 444 { np = (Block_t*)((Vmuchar_t*)fp+size+sizeof(Head_t)); 445#if _BLD_posix 446 if (np < (Block_t*)0x00120000) 447 { 448 logmsg(0, "bestreclaim np=%p", np); 449 ASSERT(!np); 450 } 451#endif 452 s = SIZE(np); /**/ASSERT(s > 0); 453 if(!ISBUSY(s)) 454 { /**/ASSERT((s&BITS) == 0); 455 if(np == vd->wild) 456 vd->wild = NIL(Block_t*); 457 else REMOVE(vd,np,INDEX(s),t,bestsearch); 458 } 459 else if(ISJUNK(s)) 460 { /* reclaim any touched junk list */ 461 if((int)C_INDEX(s) < c) 462 c = C_INDEX(s); 463 SIZE(np) = 0; 464 CLRBITS(s); 465 } 466 else break; 467 size += s + sizeof(Head_t); 468 } 469 SIZE(fp) = size; 470 471 /* tell next block that this one is free */ 472 np = NEXT(fp); /**/ASSERT(ISBUSY(SIZE(np))); 473 /**/ASSERT(!ISJUNK(SIZE(np))); 474 SETPFREE(SIZE(np)); 475 *(SELF(fp)) = fp; 476 477 if(fp == wanted) /* to be consumed soon */ 478 { /**/ASSERT(!saw_wanted); /* should be seen just once */ 479 saw_wanted = 1; 480 continue; 481 } 482 483 /* wilderness preservation */ 484 if(np->body.data >= vd->seg->baddr) 485 { vd->wild = fp; 486 continue; 487 } 488 489 /* tiny block goes to tiny list */ 490 if(size < MAXTINY) 491 { s = INDEX(size); 492 np = LINK(fp) = TINY(vd)[s]; 493 if(s == 0) /* TINIEST block */ 494 { if(np) 495 TLEFT(np) = fp; 496 TLEFT(fp) = NIL(Block_t*); 497 } 498 else 499 { if(np) 500 LEFT(np) = fp; 501 LEFT(fp) = NIL(Block_t*); 502 SETLINK(fp); 503 } 504 TINY(vd)[s] = fp; 505 continue; 506 } 507 508 LEFT(fp) = RIGHT(fp) = LINK(fp) = NIL(Block_t*); 509 if(!(np = vd->root) ) /* inserting into an empty tree */ 510 { vd->root = fp; 511 continue; 512 } 513 514 size = SIZE(fp); 515 while(1) /* leaf insertion */ 516 { /**/ASSERT(np != fp); 517 if((s = SIZE(np)) > size) 518 { if((t = LEFT(np)) ) 519 { /**/ ASSERT(np != t); 520 np = t; 521 } 522 else 523 { LEFT(np) = fp; 524 break; 525 } 526 } 527 else if(s < size) 528 { if((t = RIGHT(np)) ) 529 { /**/ ASSERT(np != t); 530 np = t; 531 } 532 else 533 { RIGHT(np) = fp; 534 break; 535 } 536 } 537 else /* s == size */ 538 { if((t = LINK(np)) ) 539 { LINK(fp) = t; 540 LEFT(t) = fp; 541 } 542 LINK(np) = fp; 543 LEFT(fp) = np; 544 SETLINK(fp); 545 break; 546 } 547 } 548 } 549 } 550 551 /**/ASSERT(!wanted || saw_wanted == 1); 552 /**/ASSERT(_vmbestcheck(vd, wanted) == 0); 553 return saw_wanted; 554} 555 556#if __STD_C 557static int bestcompact(Vmalloc_t* vm) 558#else 559static int bestcompact(vm) 560Vmalloc_t* vm; 561#endif 562{ 563 reg Seg_t *seg, *next; 564 reg Block_t *bp, *t; 565 reg size_t size, segsize, round; 566 reg int local, inuse; 567 reg Vmdata_t* vd = vm->data; 568 569 SETINUSE(vd, inuse); 570 571 if(!(local = vd->mode&VM_TRUST) ) 572 { GETLOCAL(vd,local); 573 if(ISLOCK(vd,local)) 574 { CLRINUSE(vd, inuse); 575 return -1; 576 } 577 SETLOCK(vd,local); 578 } 579 580 bestreclaim(vd,NIL(Block_t*),0); 581 582 for(seg = vd->seg; seg; seg = next) 583 { next = seg->next; 584 585 bp = BLOCK(seg->baddr); 586 if(!ISPFREE(SIZE(bp)) ) 587 continue; 588 589 bp = LAST(bp); /**/ASSERT(vmisfree(vd,bp)); 590 size = SIZE(bp); 591 if(bp == vd->wild) 592 { /* During large block allocations, _Vmextend might 593 ** have been enlarged the rounding factor. Reducing 594 ** it a bit help avoiding getting large raw memory. 595 */ 596 if((round = vm->disc->round) == 0) 597 round = _Vmpagesize; 598 if(size > COMPACT*vd->incr && vd->incr > round) 599 vd->incr /= 2; 600 601 /* for the bottom segment, we don't necessarily want 602 ** to return raw memory too early. vd->pool has an 603 ** approximation of the average size of recently freed 604 ** blocks. If this is large, the application is managing 605 ** large blocks so we throttle back memory chopping 606 ** to avoid thrashing the underlying memory system. 607 */ 608 if(size <= COMPACT*vd->incr || size <= COMPACT*vd->pool) 609 continue; 610 611 vd->wild = NIL(Block_t*); 612 vd->pool = 0; 613 } 614 else REMOVE(vd,bp,INDEX(size),t,bestsearch); 615 CLRPFREE(SIZE(NEXT(bp))); 616 617 if(size < (segsize = seg->size)) 618 size += sizeof(Head_t); 619 620 if((size = (*_Vmtruncate)(vm,seg,size,0)) > 0) 621 { if(size >= segsize) /* entire segment deleted */ 622 continue; 623 /**/ASSERT(SEG(BLOCK(seg->baddr)) == seg); 624 625 if((size = (seg->baddr - ((Vmuchar_t*)bp) - sizeof(Head_t))) > 0) 626 SIZE(bp) = size - sizeof(Head_t); 627 else bp = NIL(Block_t*); 628 } 629 630 if(bp) 631 { /**/ ASSERT(SIZE(bp) >= BODYSIZE); 632 /**/ ASSERT(SEGWILD(bp)); 633 /**/ ASSERT(!vd->root || !vmintree(vd->root,bp)); 634 SIZE(bp) |= BUSY|JUNK; 635 LINK(bp) = CACHE(vd)[C_INDEX(SIZE(bp))]; 636 CACHE(vd)[C_INDEX(SIZE(bp))] = bp; 637 } 638 } 639 640 if(!local && _Vmtrace && (vd->mode&VM_TRACE) && VMETHOD(vd) == VM_MTBEST) 641 (*_Vmtrace)(vm, (Vmuchar_t*)0, (Vmuchar_t*)0, 0, 0); 642 643 CLRLOCK(vd,local); /**/ASSERT(_vmbestcheck(vd, NIL(Block_t*)) == 0); 644 645 CLRINUSE(vd, inuse); 646 return 0; 647} 648 649#if __STD_C 650static Void_t* bestalloc(Vmalloc_t* vm, reg size_t size ) 651#else 652static Void_t* bestalloc(vm,size) 653Vmalloc_t* vm; /* region allocating from */ 654reg size_t size; /* desired block size */ 655#endif 656{ 657 reg Vmdata_t* vd = vm->data; 658 reg size_t s; 659 reg int n; 660 reg Block_t *tp, *np; 661 reg int local, inuse; 662 size_t orgsize = 0; 663 664 VMOPTIONS(); 665 666 /**/COUNT(N_alloc); 667 668 SETINUSE(vd, inuse); 669 670 if(!(local = vd->mode&VM_TRUST)) 671 { GETLOCAL(vd,local); /**/ASSERT(!ISLOCK(vd,local)); 672 if(ISLOCK(vd,local) ) 673 { CLRINUSE(vd, inuse); 674 return NIL(Void_t*); 675 } 676 SETLOCK(vd,local); 677 orgsize = size; 678 } 679 680 /**/ASSERT(_vmbestcheck(vd, NIL(Block_t*)) == 0); 681 /**/ ASSERT(HEADSIZE == sizeof(Head_t)); 682 /**/ ASSERT(BODYSIZE == sizeof(Body_t)); 683 /**/ ASSERT((ALIGN%(BITS+1)) == 0 ); 684 /**/ ASSERT((sizeof(Head_t)%ALIGN) == 0 ); 685 /**/ ASSERT((sizeof(Body_t)%ALIGN) == 0 ); 686 /**/ ASSERT((BODYSIZE%ALIGN) == 0 ); 687 /**/ ASSERT(sizeof(Block_t) == (sizeof(Body_t)+sizeof(Head_t)) ); 688 689 /* for ANSI requirement that malloc(0) returns non-NULL pointer */ 690 size = size <= BODYSIZE ? BODYSIZE : ROUND(size,ALIGN); 691 692 if((tp = vd->free) ) /* reuse last free piece if appropriate */ 693 { /**/ASSERT(ISBUSY(SIZE(tp)) ); 694 /**/ASSERT(ISJUNK(SIZE(tp)) ); 695 /**/COUNT(N_last); 696 697 vd->free = NIL(Block_t*); 698 if((s = SIZE(tp)) >= size && s < (size << 1) ) 699 { if(s >= size + (sizeof(Head_t)+BODYSIZE) ) 700 { SIZE(tp) = size; 701 np = NEXT(tp); 702 SEG(np) = SEG(tp); 703 SIZE(np) = ((s&~BITS) - (size+sizeof(Head_t)))|JUNK|BUSY; 704 vd->free = np; 705 SIZE(tp) |= s&BITS; 706 } 707 CLRJUNK(SIZE(tp)); 708 goto done; 709 } 710 711 LINK(tp) = CACHE(vd)[S_CACHE]; 712 CACHE(vd)[S_CACHE] = tp; 713 } 714 715 for(;;) 716 { for(n = S_CACHE; n >= 0; --n) /* best-fit except for coalescing */ 717 { bestreclaim(vd,NIL(Block_t*),n); 718 if(vd->root && (tp = bestsearch(vd,size,NIL(Block_t*))) ) 719 goto got_block; 720 } 721 722 /**/ASSERT(!vd->free); 723 if((tp = vd->wild) && SIZE(tp) >= size) 724 { /**/COUNT(N_wild); 725 vd->wild = NIL(Block_t*); 726 goto got_block; 727 } 728 729 KPVCOMPACT(vm,bestcompact); 730 if((tp = (*_Vmextend)(vm,size,bestsearch)) ) 731 goto got_block; 732 else if(vd->mode&VM_AGAIN) 733 vd->mode &= ~VM_AGAIN; 734 else 735 { CLRLOCK(vd,local); 736 CLRINUSE(vd, inuse); 737 return NIL(Void_t*); 738 } 739 } 740 741got_block: 742 /**/ ASSERT(!ISBITS(SIZE(tp))); 743 /**/ ASSERT(SIZE(tp) >= size); 744 /**/ ASSERT((SIZE(tp)%ALIGN) == 0); 745 /**/ ASSERT(!vd->free); 746 747 /* tell next block that we are no longer a free block */ 748 CLRPFREE(SIZE(NEXT(tp))); /**/ ASSERT(ISBUSY(SIZE(NEXT(tp)))); 749 750 if((s = SIZE(tp)-size) >= (sizeof(Head_t)+BODYSIZE) ) 751 { SIZE(tp) = size; 752 753 np = NEXT(tp); 754 SEG(np) = SEG(tp); 755 SIZE(np) = (s - sizeof(Head_t)) | BUSY|JUNK; 756 757 if(VMWILD(vd,np)) 758 { SIZE(np) &= ~BITS; 759 *SELF(np) = np; /**/ASSERT(ISBUSY(SIZE(NEXT(np)))); 760 SETPFREE(SIZE(NEXT(np))); 761 vd->wild = np; 762 } 763 else vd->free = np; 764 } 765 766 SETBUSY(SIZE(tp)); 767 768done: 769 if(!local && (vd->mode&VM_TRACE) && _Vmtrace && VMETHOD(vd) == VM_MTBEST) 770 (*_Vmtrace)(vm,NIL(Vmuchar_t*),(Vmuchar_t*)DATA(tp),orgsize,0); 771 772 /**/ASSERT(_vmbestcheck(vd, NIL(Block_t*)) == 0); 773 CLRLOCK(vd,local); 774 ANNOUNCE(local, vm, VM_ALLOC, DATA(tp), vm->disc); 775 776 CLRINUSE(vd, inuse); 777 return DATA(tp); 778} 779 780#if __STD_C 781static long bestaddr(Vmalloc_t* vm, Void_t* addr ) 782#else 783static long bestaddr(vm, addr) 784Vmalloc_t* vm; /* region allocating from */ 785Void_t* addr; /* address to check */ 786#endif 787{ 788 reg Seg_t* seg; 789 reg Block_t *b, *endb; 790 reg long offset; 791 reg Vmdata_t* vd = vm->data; 792 reg int local, inuse; 793 794 SETINUSE(vd, inuse); 795 796 if(!(local = vd->mode&VM_TRUST) ) 797 { GETLOCAL(vd,local); /**/ASSERT(!ISLOCK(vd,local)); 798 if(ISLOCK(vd,local)) 799 { CLRINUSE(vd, inuse); 800 return -1L; 801 } 802 SETLOCK(vd,local); 803 } 804 805 offset = -1L; b = endb = NIL(Block_t*); 806 for(seg = vd->seg; seg; seg = seg->next) 807 { b = SEGBLOCK(seg); 808 endb = (Block_t*)(seg->baddr - sizeof(Head_t)); 809 if((Vmuchar_t*)addr > (Vmuchar_t*)b && 810 (Vmuchar_t*)addr < (Vmuchar_t*)endb) 811 break; 812 } 813 814 if(local && !(vd->mode&VM_TRUST) ) /* from bestfree or bestresize */ 815 { b = BLOCK(addr); 816 if(seg && SEG(b) == seg && ISBUSY(SIZE(b)) && !ISJUNK(SIZE(b)) ) 817 offset = 0; 818 if(offset != 0 && vm->disc->exceptf) 819 (void)(*vm->disc->exceptf)(vm,VM_BADADDR,addr,vm->disc); 820 } 821 else if(seg) 822 { while(b < endb) 823 { reg Vmuchar_t* data = (Vmuchar_t*)DATA(b); 824 reg size_t size = SIZE(b)&~BITS; 825 826 if((Vmuchar_t*)addr >= data && (Vmuchar_t*)addr < data+size) 827 { if(ISJUNK(SIZE(b)) || !ISBUSY(SIZE(b))) 828 offset = -1L; 829 else offset = (Vmuchar_t*)addr - data; 830 goto done; 831 } 832 833 b = (Block_t*)((Vmuchar_t*)DATA(b) + size); 834 } 835 } 836 837done: 838 CLRLOCK(vd,local); 839 CLRINUSE(vd, inuse); 840 return offset; 841} 842 843#if __STD_C 844static int bestfree(Vmalloc_t* vm, Void_t* data ) 845#else 846static int bestfree(vm, data ) 847Vmalloc_t* vm; 848Void_t* data; 849#endif 850{ 851 reg Vmdata_t* vd = vm->data; 852 reg Block_t *bp; 853 reg size_t s; 854 reg int local, inuse; 855 856#ifdef DEBUG 857 if((local = (int)integralof(data)) >= 0 && local <= 0xf) 858 { int vmassert = _Vmassert; 859 _Vmassert = local ? local : vmassert ? vmassert : (VM_check|VM_abort); 860 _vmbestcheck(vd, NIL(Block_t*)); 861 _Vmassert = local ? local : vmassert; 862 return 0; 863 } 864#endif 865 866 if(!data) /* ANSI-ism */ 867 return 0; 868 869 /**/COUNT(N_free); 870 871 SETINUSE(vd, inuse); 872 873 if(!(local = vd->mode&VM_TRUST) ) 874 { GETLOCAL(vd,local); /**/ASSERT(!ISLOCK(vd,local)); 875 if(ISLOCK(vd,local) || KPVADDR(vm,data,bestaddr) != 0 ) 876 { CLRINUSE(vd, inuse); 877 return -1; 878 } 879 SETLOCK(vd,local); 880 } 881 882 /**/ASSERT(_vmbestcheck(vd, NIL(Block_t*)) == 0); 883 bp = BLOCK(data); s = SIZE(bp); 884 885 /* Keep an approximate average free block size. 886 ** This is used in bestcompact() to decide when to release 887 ** raw memory back to the underlying memory system. 888 */ 889 vd->pool = (vd->pool + (s&~BITS))/2; 890 891 if(ISBUSY(s) && !ISJUNK(s)) 892 { SETJUNK(SIZE(bp)); 893 if(s < MAXCACHE) 894 { /**/ASSERT(!vmonlist(CACHE(vd)[INDEX(s)], bp) ); 895 LINK(bp) = CACHE(vd)[INDEX(s)]; 896 CACHE(vd)[INDEX(s)] = bp; 897 } 898 else if(!vd->free) 899 vd->free = bp; 900 else 901 { /**/ASSERT(!vmonlist(CACHE(vd)[S_CACHE], bp) ); 902 LINK(bp) = CACHE(vd)[S_CACHE]; 903 CACHE(vd)[S_CACHE] = bp; 904 } 905 906 /* coalesce on freeing large blocks to avoid fragmentation */ 907 if(SIZE(bp) >= 2*vd->incr) 908 { bestreclaim(vd,NIL(Block_t*),0); 909 if(vd->wild && SIZE(vd->wild) >= COMPACT*vd->incr) 910 KPVCOMPACT(vm,bestcompact); 911 } 912 } 913 914 if(!local && _Vmtrace && (vd->mode&VM_TRACE) && VMETHOD(vd) == VM_MTBEST ) 915 (*_Vmtrace)(vm,(Vmuchar_t*)data,NIL(Vmuchar_t*), (s&~BITS), 0); 916 917 /**/ASSERT(_vmbestcheck(vd, NIL(Block_t*)) == 0); 918 CLRLOCK(vd,local); 919 ANNOUNCE(local, vm, VM_FREE, data, vm->disc); 920 921 CLRINUSE(vd, inuse); 922 return 0; 923} 924 925#if __STD_C 926static Void_t* bestresize(Vmalloc_t* vm, Void_t* data, reg size_t size, int type) 927#else 928static Void_t* bestresize(vm,data,size,type) 929Vmalloc_t* vm; /* region allocating from */ 930Void_t* data; /* old block of data */ 931reg size_t size; /* new size */ 932int type; /* !=0 to move, <0 for not copy */ 933#endif 934{ 935 reg Block_t *rp, *np, *t; 936 int local, inuse; 937 size_t s, bs, oldsize = 0, orgsize = 0; 938 Void_t *oldd, *orgdata = NIL(Void_t*); 939 Vmdata_t *vd = vm->data; 940 941 /**/COUNT(N_resize); 942 943 SETINUSE(vd, inuse); 944 945 if(!data) 946 { if((data = bestalloc(vm,size)) ) 947 { oldsize = 0; 948 size = size <= BODYSIZE ? BODYSIZE : ROUND(size,ALIGN); 949 } 950 goto done; 951 } 952 if(size == 0) 953 { (void)bestfree(vm,data); 954 CLRINUSE(vd, inuse); 955 return NIL(Void_t*); 956 } 957 958 if(!(local = vd->mode&VM_TRUST) ) 959 { GETLOCAL(vd,local); /**/ASSERT(!ISLOCK(vd,local)); 960 if(ISLOCK(vd,local) || (!local && KPVADDR(vm,data,bestaddr) != 0 ) ) 961 { CLRINUSE(vd, inuse); 962 return NIL(Void_t*); 963 } 964 SETLOCK(vd,local); 965 966 orgdata = data; /* for tracing */ 967 orgsize = size; 968 } 969 970 /**/ASSERT(_vmbestcheck(vd, NIL(Block_t*)) == 0); 971 size = size <= BODYSIZE ? BODYSIZE : ROUND(size,ALIGN); 972 rp = BLOCK(data); /**/ASSERT(ISBUSY(SIZE(rp)) && !ISJUNK(SIZE(rp))); 973 oldsize = SIZE(rp); CLRBITS(oldsize); 974 if(oldsize < size) 975 { np = (Block_t*)((Vmuchar_t*)rp + oldsize + sizeof(Head_t)); 976 do /* forward merge as much as possible */ 977 { s = SIZE(np); /**/ASSERT(!ISPFREE(s)); 978 if(np == vd->free) 979 { vd->free = NIL(Block_t*); 980 CLRBITS(s); 981 } 982 else if(ISJUNK(s) ) 983 { if(!bestreclaim(vd,np,C_INDEX(s)) ) 984 /**/ASSERT(0); /* oops: did not see np! */ 985 s = SIZE(np); /**/ASSERT(s%ALIGN == 0); 986 } 987 else if(!ISBUSY(s) ) 988 { if(np == vd->wild) 989 vd->wild = NIL(Block_t*); 990 else REMOVE(vd,np,INDEX(s),t,bestsearch); 991 } 992 else break; 993 994 SIZE(rp) += (s += sizeof(Head_t)); /**/ASSERT((s%ALIGN) == 0); 995 np = (Block_t*)((Vmuchar_t*)np + s); 996 CLRPFREE(SIZE(np)); 997 } while(SIZE(rp) < size); 998 999 if(SIZE(rp) < size && size > vd->incr && SEGWILD(rp) ) 1000 { reg Seg_t* seg; 1001 1002 s = (size - SIZE(rp)) + sizeof(Head_t); s = ROUND(s,vd->incr); 1003 seg = SEG(rp); 1004 if((*vm->disc->memoryf)(vm,seg->addr,seg->extent,seg->extent+s, 1005 vm->disc) == seg->addr ) 1006 { SIZE(rp) += s; 1007 seg->extent += s; 1008 seg->size += s; 1009 seg->baddr += s; 1010 s = (SIZE(rp)&~BITS) + sizeof(Head_t); 1011 np = (Block_t*)((Vmuchar_t*)rp + s); 1012 SEG(np) = seg; 1013 SIZE(np) = BUSY; 1014 } 1015 } 1016 } 1017 1018 if((s = SIZE(rp)) >= (size + (BODYSIZE+sizeof(Head_t))) ) 1019 { SIZE(rp) = size; 1020 np = NEXT(rp); 1021 SEG(np) = SEG(rp); 1022 SIZE(np) = (((s&~BITS)-size) - sizeof(Head_t))|BUSY|JUNK; 1023 CPYBITS(SIZE(rp),s); 1024 rp = np; 1025 goto do_free; 1026 } 1027 else if((bs = s&~BITS) < size) 1028 { if(!(type&(VM_RSMOVE|VM_RSCOPY)) ) 1029 data = NIL(Void_t*); /* old data is not moveable */ 1030 else 1031 { oldd = data; 1032 if((data = KPVALLOC(vm,size,bestalloc)) ) 1033 { if(type&VM_RSCOPY) 1034 memcpy(data, oldd, bs); 1035 1036 do_free: /* reclaim these right away */ 1037 SETJUNK(SIZE(rp)); 1038 LINK(rp) = CACHE(vd)[S_CACHE]; 1039 CACHE(vd)[S_CACHE] = rp; 1040 bestreclaim(vd, NIL(Block_t*), S_CACHE); 1041 } 1042 } 1043 } 1044 1045 if(!local && _Vmtrace && data && (vd->mode&VM_TRACE) && VMETHOD(vd) == VM_MTBEST) 1046 (*_Vmtrace)(vm, (Vmuchar_t*)orgdata, (Vmuchar_t*)data, orgsize, 0); 1047 1048 /**/ASSERT(_vmbestcheck(vd, NIL(Block_t*)) == 0); 1049 CLRLOCK(vd,local); 1050 ANNOUNCE(local, vm, VM_RESIZE, data, vm->disc); 1051 1052done: if(data && (type&VM_RSZERO) && (size = SIZE(BLOCK(data))&~BITS) > oldsize ) 1053 memset((Void_t*)((Vmuchar_t*)data + oldsize), 0, size-oldsize); 1054 1055 CLRINUSE(vd, inuse); 1056 return data; 1057} 1058 1059#if __STD_C 1060static long bestsize(Vmalloc_t* vm, Void_t* addr ) 1061#else 1062static long bestsize(vm, addr) 1063Vmalloc_t* vm; /* region allocating from */ 1064Void_t* addr; /* address to check */ 1065#endif 1066{ 1067 reg Seg_t* seg; 1068 reg Block_t *b, *endb; 1069 reg long size; 1070 reg Vmdata_t* vd = vm->data; 1071 reg int inuse; 1072 1073 SETINUSE(vd, inuse); 1074 1075 if(!(vd->mode&VM_TRUST) ) 1076 { if(ISLOCK(vd,0)) 1077 { CLRINUSE(vd, inuse); 1078 return -1L; 1079 } 1080 SETLOCK(vd,0); 1081 } 1082 1083 size = -1L; 1084 for(seg = vd->seg; seg; seg = seg->next) 1085 { b = SEGBLOCK(seg); 1086 endb = (Block_t*)(seg->baddr - sizeof(Head_t)); 1087 if((Vmuchar_t*)addr <= (Vmuchar_t*)b || 1088 (Vmuchar_t*)addr >= (Vmuchar_t*)endb) 1089 continue; 1090 while(b < endb) 1091 { if(addr == DATA(b)) 1092 { if(!ISBUSY(SIZE(b)) || ISJUNK(SIZE(b)) ) 1093 size = -1L; 1094 else size = (long)SIZE(b)&~BITS; 1095 goto done; 1096 } 1097 else if((Vmuchar_t*)addr <= (Vmuchar_t*)b) 1098 break; 1099 1100 b = (Block_t*)((Vmuchar_t*)DATA(b) + (SIZE(b)&~BITS) ); 1101 } 1102 } 1103 1104done: 1105 CLRLOCK(vd,0); 1106 CLRINUSE(vd, inuse); 1107 return size; 1108} 1109 1110#if __STD_C 1111static Void_t* bestalign(Vmalloc_t* vm, size_t size, size_t align) 1112#else 1113static Void_t* bestalign(vm, size, align) 1114Vmalloc_t* vm; 1115size_t size; 1116size_t align; 1117#endif 1118{ 1119 reg Vmuchar_t *data; 1120 reg Block_t *tp, *np; 1121 reg Seg_t* seg; 1122 reg int local, inuse; 1123 reg size_t s, extra, orgsize = 0, orgalign = 0; 1124 reg Vmdata_t* vd = vm->data; 1125 1126 if(size <= 0 || align <= 0) 1127 return NIL(Void_t*); 1128 1129 SETINUSE(vd, inuse); 1130 1131 if(!(local = vd->mode&VM_TRUST) ) 1132 { GETLOCAL(vd,local); /**/ASSERT(!ISLOCK(vd,local)); 1133 if(ISLOCK(vd,local) ) 1134 { CLRINUSE(vd, inuse); 1135 return NIL(Void_t*); 1136 } 1137 SETLOCK(vd,local); 1138 orgsize = size; 1139 orgalign = align; 1140 } 1141 1142 /**/ASSERT(_vmbestcheck(vd, NIL(Block_t*)) == 0); 1143 size = size <= BODYSIZE ? BODYSIZE : ROUND(size,ALIGN); 1144 align = MULTIPLE(align,ALIGN); 1145 1146 /* hack so that dbalign() can store header data */ 1147 if(VMETHOD(vd) != VM_MTDEBUG) 1148 extra = 0; 1149 else 1150 { extra = DB_HEAD; 1151 while(align < extra || (align - extra) < sizeof(Block_t)) 1152 align *= 2; 1153 } 1154 1155 /* reclaim all free blocks now to avoid fragmentation */ 1156 bestreclaim(vd,NIL(Block_t*),0); 1157 1158 s = size + 2*(align+sizeof(Head_t)+extra); 1159 if(!(data = (Vmuchar_t*)KPVALLOC(vm,s,bestalloc)) ) 1160 goto done; 1161 1162 tp = BLOCK(data); 1163 seg = SEG(tp); 1164 1165 /* get an aligned address that we can live with */ 1166 if((s = (size_t)((VLONG(data)+extra)%align)) != 0) 1167 data += align-s; /**/ASSERT(((VLONG(data)+extra)%align) == 0); 1168 1169 if((np = BLOCK(data)) != tp ) /* need to free left part */ 1170 { if(((Vmuchar_t*)np - (Vmuchar_t*)tp) < (ssize_t)(sizeof(Block_t)+extra) ) 1171 { data += align; 1172 np = BLOCK(data); 1173 } /**/ASSERT(((VLONG(data)+extra)%align) == 0); 1174 1175 s = (Vmuchar_t*)np - (Vmuchar_t*)tp; 1176 SIZE(np) = ((SIZE(tp)&~BITS) - s)|BUSY; 1177 SEG(np) = seg; 1178 1179 SIZE(tp) = (s - sizeof(Head_t)) | (SIZE(tp)&BITS) | JUNK; 1180 /**/ ASSERT(SIZE(tp) >= sizeof(Body_t) ); 1181 LINK(tp) = CACHE(vd)[C_INDEX(SIZE(tp))]; 1182 CACHE(vd)[C_INDEX(SIZE(tp))] = tp; 1183 } 1184 1185 /* free left-over if too big */ 1186 if((s = SIZE(np) - size) >= sizeof(Block_t)) 1187 { SIZE(np) = size; 1188 1189 tp = NEXT(np); 1190 SIZE(tp) = ((s & ~BITS) - sizeof(Head_t)) | BUSY | JUNK; 1191 SEG(tp) = seg; 1192 LINK(tp) = CACHE(vd)[C_INDEX(SIZE(tp))]; 1193 CACHE(vd)[C_INDEX(SIZE(tp))] = tp; 1194 1195 SIZE(np) |= s&BITS; 1196 } 1197 1198 bestreclaim(vd,NIL(Block_t*),0); /* coalesce all free blocks */ 1199 1200 if(!local && !(vd->mode&VM_TRUST) && _Vmtrace && (vd->mode&VM_TRACE) ) 1201 (*_Vmtrace)(vm,NIL(Vmuchar_t*),data,orgsize,orgalign); 1202 1203done: 1204 /**/ASSERT(_vmbestcheck(vd, NIL(Block_t*)) == 0); 1205 CLRLOCK(vd,local); 1206 ANNOUNCE(local, vm, VM_ALLOC, (Void_t*)data, vm->disc); 1207 1208 CLRINUSE(vd, inuse); 1209 return (Void_t*)data; 1210} 1211 1212 1213#if _mem_win32 1214#if _PACKAGE_ast 1215#include <ast_windows.h> 1216#else 1217#include <windows.h> 1218#endif 1219#endif /* _lib_win32 */ 1220 1221#if _mem_mmap_anon 1222#include <sys/mman.h> 1223#ifndef MAP_ANON 1224#define MAP_ANON MAP_ANONYMOUS 1225#endif 1226#endif /* _mem_mmap_anon */ 1227 1228#if _mem_mmap_zero 1229#include <sys/fcntl.h> 1230#include <sys/mman.h> 1231typedef struct _mmapdisc_s 1232{ Vmdisc_t disc; 1233 int fd; 1234 off_t offset; 1235} Mmapdisc_t; 1236 1237#ifndef OPEN_MAX 1238#define OPEN_MAX 64 1239#endif 1240#define OPEN_PRIVATE (3*OPEN_MAX/4) 1241#endif /* _mem_mmap_zero */ 1242 1243/* failure mode of mmap, sbrk and brk */ 1244#ifndef MAP_FAILED 1245#define MAP_FAILED ((Void_t*)(-1)) 1246#endif 1247#define BRK_FAILED ((Void_t*)(-1)) 1248 1249/* make sure that allocated memory are addressable */ 1250 1251#if _PACKAGE_ast 1252#include <sig.h> 1253#else 1254#include <signal.h> 1255typedef void (*Sig_handler_t)(int); 1256#endif 1257 1258static int Gotsegv = 0; 1259 1260#if __STD_C 1261static void sigsegv(int sig) 1262#else 1263static void sigsegv(sig) 1264int sig; 1265#endif 1266{ 1267 if(sig == SIGSEGV) 1268 Gotsegv = 1; 1269} 1270 1271/* 1272 * okaddr() is required for systems that overcommit brk()/mmap() allocations 1273 * by returning ok when even though the pages that cover the allocation 1274 * haven't been committed to the process yet -- linux does this and it 1275 * works most of the time, but when it fails its insidious because it 1276 * manifests as random core dumps under system load, although it can 1277 * also happen under normal load but during a spike of allocation requests 1278 * 1279 * overcommit is costly to iffe out, so we resort to cursed system specific 1280 * predefined macro guards to detect systems that we know 100% do not overcommit 1281 * 1282 * sunos only overcommits for mmap(MAP_NORESERVE) allocations (vmalloc doesn't use that) 1283 */ 1284 1285#if defined(__SunOS) 1286 1287#define okaddr(a,n) 0 1288 1289#else 1290 1291#if __STD_C 1292static int okaddr(Void_t* addr, size_t nsize) 1293#else 1294static int okaddr(addr, nsize) 1295Void_t* addr; 1296size_t nsize; 1297#endif 1298{ 1299 Sig_handler_t segv; 1300 int rv; 1301 1302 Gotsegv = 0; /* catch segment fault */ 1303 segv = signal(SIGSEGV, sigsegv); 1304 1305 if(Gotsegv == 0) 1306 rv = *((char*)addr); 1307 if(Gotsegv == 0) 1308 rv += *(((char*)addr)+nsize-1); 1309 if(Gotsegv == 0) 1310 rv = rv == 0 ? 0 : 1; 1311 else rv = -1; 1312 1313 signal(SIGSEGV, segv); /* restore signal catcher */ 1314 Gotsegv = 0; 1315 1316 return rv; 1317} 1318 1319#endif 1320 1321/* A discipline to get raw memory using sbrk/VirtualAlloc/mmap */ 1322#if __STD_C 1323static Void_t* sbrkmem(Vmalloc_t* vm, Void_t* caddr, 1324 size_t csize, size_t nsize, Vmdisc_t* disc) 1325#else 1326static Void_t* sbrkmem(vm, caddr, csize, nsize, disc) 1327Vmalloc_t* vm; /* region doing allocation from */ 1328Void_t* caddr; /* current address */ 1329size_t csize; /* current size */ 1330size_t nsize; /* new size */ 1331Vmdisc_t* disc; /* discipline structure */ 1332#endif 1333{ 1334#undef _done_sbrkmem 1335 1336#if !defined(_done_sbrkmem) && defined(_mem_win32) 1337#define _done_sbrkmem 1 1338 NOTUSED(vm); 1339 NOTUSED(disc); 1340 if(csize == 0) 1341 return (Void_t*)VirtualAlloc(0,nsize,MEM_COMMIT,PAGE_READWRITE); 1342 else if(nsize == 0) 1343 return VirtualFree((LPVOID)caddr,0,MEM_RELEASE) ? caddr : NIL(Void_t*); 1344 else return NIL(Void_t*); 1345#endif /* MUST_WIN32 */ 1346 1347#if !defined(_done_sbrkmem) && (_mem_sbrk || _mem_mmap_zero || _mem_mmap_anon) 1348#define _done_sbrkmem 1 1349 Vmuchar_t *addr; 1350#if _mem_mmap_zero 1351 Mmapdisc_t *mmdc = (Mmapdisc_t*)disc; 1352#else 1353 NOTUSED(disc); 1354#endif 1355 NOTUSED(vm); 1356 1357 if(csize == 0) /* allocating new memory */ 1358 { 1359 1360#if _mem_sbrk /* try using sbrk() and brk() */ 1361 if(!(_Vmassert & VM_mmap)) 1362 { 1363 addr = (Vmuchar_t*)sbrk(0); /* old break value */ 1364 if(addr && addr != (Vmuchar_t*)BRK_FAILED ) 1365 { 1366 if((addr+nsize) < addr) 1367 return NIL(Void_t*); 1368 if(brk(addr+nsize) == 0 ) 1369 { if(okaddr(addr,nsize) >= 0) 1370 return addr; 1371 (void)brk(addr); /* release reserved address */ 1372 } 1373 } 1374 } 1375#endif /* _mem_sbrk */ 1376 1377#if _mem_mmap_anon /* anonymous mmap */ 1378 addr = (Vmuchar_t*)mmap(0, nsize, PROT_READ|PROT_WRITE, 1379 MAP_ANON|MAP_PRIVATE, -1, 0); 1380 if(addr && addr != (Vmuchar_t*)MAP_FAILED) 1381 { if(okaddr(addr,nsize) >= 0) 1382 return addr; 1383 (void)munmap((char*)addr, nsize); /* release reserved address */ 1384 } 1385#endif /* _mem_mmap_anon */ 1386 1387#if _mem_mmap_zero /* mmap from /dev/zero */ 1388 if(mmdc->fd < 0) 1389 { int fd; 1390 if(mmdc->fd != -1) 1391 return NIL(Void_t*); 1392 if((fd = open("/dev/zero", O_RDONLY)) < 0 ) 1393 { mmdc->fd = -2; 1394 return NIL(Void_t*); 1395 } 1396 if(fd >= OPEN_PRIVATE || (mmdc->fd = dup2(fd,OPEN_PRIVATE)) < 0 ) 1397 mmdc->fd = fd; 1398 else close(fd); 1399#ifdef FD_CLOEXEC 1400 fcntl(mmdc->fd, F_SETFD, FD_CLOEXEC); 1401#endif 1402 } 1403 addr = (Vmuchar_t*)mmap(0, nsize, PROT_READ|PROT_WRITE, 1404 MAP_PRIVATE, mmdc->fd, mmdc->offset); 1405 if(addr && addr != (Vmuchar_t*)MAP_FAILED) 1406 { if(okaddr(addr, nsize) >= 0) 1407 { mmdc->offset += nsize; 1408 return addr; 1409 } 1410 (void)munmap((char*)addr, nsize); /* release reserved address */ 1411 } 1412#endif /* _mem_mmap_zero */ 1413 1414 return NIL(Void_t*); 1415 } 1416 else 1417 { 1418 1419#if _mem_sbrk 1420 addr = (Vmuchar_t*)sbrk(0); 1421 if(!addr || addr == (Vmuchar_t*)BRK_FAILED) 1422 addr = caddr; 1423 else if(((Vmuchar_t*)caddr+csize) == addr) /* in sbrk-space */ 1424 { if(nsize <= csize) 1425 addr -= csize-nsize; 1426 else if((addr += nsize-csize) < (Vmuchar_t*)caddr) 1427 return NIL(Void_t*); /* wrapped around address */ 1428 else return brk(addr) == 0 ? caddr : NIL(Void_t*); 1429 } 1430#else 1431 addr = caddr; 1432#endif /* _mem_sbrk */ 1433 1434#if _mem_mmap_zero || _mem_mmap_anon 1435 if(((Vmuchar_t*)caddr+csize) > addr) /* in mmap-space */ 1436 if(nsize == 0 && munmap(caddr,csize) == 0) 1437 return caddr; 1438#endif /* _mem_mmap_zero || _mem_mmap_anon */ 1439 1440 return NIL(Void_t*); 1441 } 1442#endif /*_done_sbrkmem*/ 1443 1444#if !_done_sbrkmem /* use native malloc/free as a last resort */ 1445 /**/ASSERT(_std_malloc); /* _std_malloc should be well-defined */ 1446 NOTUSED(vm); 1447 NOTUSED(disc); 1448 if(csize == 0) 1449 return (Void_t*)malloc(nsize); 1450 else if(nsize == 0) 1451 { free(caddr); 1452 return caddr; 1453 } 1454 else return NIL(Void_t*); 1455#endif /* _done_sbrkmem */ 1456} 1457 1458#if _mem_mmap_zero 1459static Mmapdisc_t _Vmdcsbrk = { { sbrkmem, NIL(Vmexcept_f), 64*1024 }, -1, 0 }; 1460#else 1461static Vmdisc_t _Vmdcsbrk = { sbrkmem, NIL(Vmexcept_f), 0 }; 1462#endif 1463 1464static Vmethod_t _Vmbest = 1465{ 1466 bestalloc, 1467 bestresize, 1468 bestfree, 1469 bestaddr, 1470 bestsize, 1471 bestcompact, 1472 bestalign, 1473 VM_MTBEST 1474}; 1475 1476/* The heap region */ 1477static Vmdata_t _Vmdata = 1478{ 1479 VM_MTBEST|VM_TRUST, /* mode */ 1480 0, /* incr */ 1481 0, /* pool */ 1482 NIL(Seg_t*), /* seg */ 1483 NIL(Block_t*), /* free */ 1484 NIL(Block_t*), /* wild */ 1485 NIL(Block_t*), /* root */ 1486}; 1487Vmalloc_t _Vmheap = 1488{ 1489 { bestalloc, 1490 bestresize, 1491 bestfree, 1492 bestaddr, 1493 bestsize, 1494 bestcompact, 1495 bestalign, 1496 VM_MTBEST 1497 }, 1498 NIL(char*), /* file */ 1499 0, /* line */ 1500 0, /* func */ 1501 (Vmdisc_t*)(&_Vmdcsbrk), /* disc */ 1502 &_Vmdata, /* data */ 1503 NIL(Vmalloc_t*) /* next */ 1504}; 1505 1506__DEFINE__(Vmalloc_t*, Vmheap, &_Vmheap); 1507__DEFINE__(Vmalloc_t*, Vmregion, &_Vmheap); 1508__DEFINE__(Vmethod_t*, Vmbest, &_Vmbest); 1509__DEFINE__(Vmdisc_t*, Vmdcsbrk, (Vmdisc_t*)(&_Vmdcsbrk) ); 1510 1511#ifdef NoF 1512NoF(vmbest) 1513#endif 1514 1515#endif 1516