1/* 2Copyright (C) 1996-1997 Id Software, Inc. 3 4This program is free software; you can redistribute it and/or 5modify it under the terms of the GNU General Public License 6as published by the Free Software Foundation; either version 2 7of the License, or (at your option) any later version. 8 9This program is distributed in the hope that it will be useful, 10but WITHOUT ANY WARRANTY; without even the implied warranty of 11MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 12 13See the GNU General Public License for more details. 14 15You should have received a copy of the GNU General Public License 16along with this program; if not, write to the Free Software 17Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. 18 19*/ 20// Z_zone.c 21 22#include "quakedef.h" 23 24#define DYNAMIC_SIZE 0xc000 25 26#define ZONEID 0x1d4a11 27#define MINFRAGMENT 64 28 29typedef struct memblock_s 30{ 31 int size; // including the header and possibly tiny fragments 32 int tag; // a tag of 0 is a free block 33 int id; // should be ZONEID 34 struct memblock_s *next, *prev; 35 int pad; // pad to 64 bit boundary 36} memblock_t; 37 38typedef struct 39{ 40 int size; // total bytes malloced, including header 41 memblock_t blocklist; // start / end cap for linked list 42 memblock_t *rover; 43} memzone_t; 44 45void Cache_FreeLow (int new_low_hunk); 46void Cache_FreeHigh (int new_high_hunk); 47 48 49/* 50============================================================================== 51 52 ZONE MEMORY ALLOCATION 53 54There is never any space between memblocks, and there will never be two 55contiguous free memblocks. 56 57The rover can be left pointing at a non-empty block 58 59The zone calls are pretty much only used for small strings and structures, 60all big things are allocated on the hunk. 61============================================================================== 62*/ 63 64memzone_t *mainzone; 65 66void Z_ClearZone (memzone_t *zone, int size); 67 68 69/* 70======================== 71Z_ClearZone 72======================== 73*/ 74void Z_ClearZone (memzone_t *zone, int size) 75{ 76 memblock_t *block; 77 78// set the entire zone to one free block 79 80 zone->blocklist.next = zone->blocklist.prev = block = 81 (memblock_t *)( (byte *)zone + sizeof(memzone_t) ); 82 zone->blocklist.tag = 1; // in use block 83 zone->blocklist.id = 0; 84 zone->blocklist.size = 0; 85 zone->rover = block; 86 87 block->prev = block->next = &zone->blocklist; 88 block->tag = 0; // free block 89 block->id = ZONEID; 90 block->size = size - sizeof(memzone_t); 91} 92 93 94/* 95======================== 96Z_Free 97======================== 98*/ 99void Z_Free (void *ptr) 100{ 101 memblock_t *block, *other; 102 103 if (!ptr) 104 Sys_Error ("Z_Free: NULL pointer"); 105 106 block = (memblock_t *) ( (byte *)ptr - sizeof(memblock_t)); 107 if (block->id != ZONEID) 108 Sys_Error ("Z_Free: freed a pointer without ZONEID"); 109 if (block->tag == 0) 110 Sys_Error ("Z_Free: freed a freed pointer"); 111 112 block->tag = 0; // mark as free 113 114 other = block->prev; 115 if (!other->tag) 116 { // merge with previous free block 117 other->size += block->size; 118 other->next = block->next; 119 other->next->prev = other; 120 if (block == mainzone->rover) 121 mainzone->rover = other; 122 block = other; 123 } 124 125 other = block->next; 126 if (!other->tag) 127 { // merge the next free block onto the end 128 block->size += other->size; 129 block->next = other->next; 130 block->next->prev = block; 131 if (other == mainzone->rover) 132 mainzone->rover = block; 133 } 134} 135 136 137/* 138======================== 139Z_Malloc 140======================== 141*/ 142void *Z_Malloc (int size) 143{ 144 void *buf; 145 146Z_CheckHeap (); // DEBUG 147 buf = Z_TagMalloc (size, 1); 148 if (!buf) 149 Sys_Error ("Z_Malloc: failed on allocation of %i bytes",size); 150 Q_memset (buf, 0, size); 151 152 return buf; 153} 154 155void *Z_TagMalloc (int size, int tag) 156{ 157 int extra; 158 memblock_t *start, *rover, *newm, *base; 159 160 if (!tag) 161 Sys_Error ("Z_TagMalloc: tried to use a 0 tag"); 162 163// 164// scan through the block list looking for the first free block 165// of sufficient size 166// 167 size += sizeof(memblock_t); // account for size of block header 168 size += 4; // space for memory trash tester 169 size = (size + 7) & ~7; // align to 8-byte boundary 170 171 base = rover = mainzone->rover; 172 start = base->prev; 173 174 do 175 { 176 if (rover == start) // scaned all the way around the list 177 return NULL; 178 if (rover->tag) 179 base = rover = rover->next; 180 else 181 rover = rover->next; 182 } while (base->tag || base->size < size); 183 184// 185// found a block big enough 186// 187 extra = base->size - size; 188 if (extra > MINFRAGMENT) 189 { // there will be a free fragment after the allocated block 190 newm = (memblock_t *) ((byte *)base + size ); 191 newm->size = extra; 192 newm->tag = 0; // free block 193 newm->prev = base; 194 newm->id = ZONEID; 195 newm->next = base->next; 196 newm->next->prev = newm; 197 base->next = newm; 198 base->size = size; 199 } 200 201 base->tag = tag; // no longer a free block 202 203 mainzone->rover = base->next; // next allocation will start looking here 204 205 base->id = ZONEID; 206 207// marker for memory trash testing 208 *(int *)((byte *)base + base->size - 4) = ZONEID; 209 210 return (void *) ((byte *)base + sizeof(memblock_t)); 211} 212 213 214/* 215======================== 216Z_Print 217======================== 218*/ 219void Z_Print (memzone_t *zone) 220{ 221 memblock_t *block; 222 223 Con_Printf ("zone size: %i location: %p\n",mainzone->size,mainzone); 224 225 for (block = zone->blocklist.next ; ; block = block->next) 226 { 227 Con_Printf ("block:%p size:%7i tag:%3i\n", 228 block, block->size, block->tag); 229 230 if (block->next == &zone->blocklist) 231 break; // all blocks have been hit 232 if ( (byte *)block + block->size != (byte *)block->next) 233 Con_Printf ("ERROR: block size does not touch the next block\n"); 234 if ( block->next->prev != block) 235 Con_Printf ("ERROR: next block doesn't have proper back link\n"); 236 if (!block->tag && !block->next->tag) 237 Con_Printf ("ERROR: two consecutive free blocks\n"); 238 } 239} 240 241 242/* 243======================== 244Z_CheckHeap 245======================== 246*/ 247void Z_CheckHeap (void) 248{ 249 memblock_t *block; 250 251 for (block = mainzone->blocklist.next ; ; block = block->next) 252 { 253 if (block->next == &mainzone->blocklist) 254 break; // all blocks have been hit 255 if ( (byte *)block + block->size != (byte *)block->next) 256 Sys_Error ("Z_CheckHeap: block size does not touch the next block\n"); 257 if ( block->next->prev != block) 258 Sys_Error ("Z_CheckHeap: next block doesn't have proper back link\n"); 259 if (!block->tag && !block->next->tag) 260 Sys_Error ("Z_CheckHeap: two consecutive free blocks\n"); 261 } 262} 263 264//============================================================================ 265 266#define HUNK_SENTINAL 0x1df001ed 267 268typedef struct 269{ 270 int sentinal; 271 int size; // including sizeof(hunk_t), -1 = not allocated 272 char name[8]; 273} hunk_t; 274 275byte *hunk_base; 276int hunk_size; 277 278int hunk_low_used; 279int hunk_high_used; 280 281qboolean hunk_tempactive; 282int hunk_tempmark; 283 284void R_FreeTextures (void); 285 286/* 287============== 288Hunk_Check 289 290Run consistancy and sentinal trahing checks 291============== 292*/ 293void Hunk_Check (void) 294{ 295 hunk_t *h; 296 297 for (h = (hunk_t *)hunk_base ; (byte *)h != hunk_base + hunk_low_used ; ) 298 { 299 if (h->sentinal != HUNK_SENTINAL) 300 Sys_Error ("Hunk_Check: trahsed sentinal"); 301 if (h->size < 16 || h->size + (byte *)h - hunk_base > hunk_size) 302 Sys_Error ("Hunk_Check: bad size"); 303 h = (hunk_t *)((byte *)h+h->size); 304 } 305} 306 307/* 308============== 309Hunk_Print 310 311If "all" is specified, every single allocation is printed. 312Otherwise, allocations with the same name will be totaled up before printing. 313============== 314*/ 315void Hunk_Print (qboolean all) 316{ 317 hunk_t *h, *next, *endlow, *starthigh, *endhigh; 318 int count, sum; 319 int totalblocks; 320 char name[9]; 321 322 name[8] = 0; 323 count = 0; 324 sum = 0; 325 totalblocks = 0; 326 327 h = (hunk_t *)hunk_base; 328 endlow = (hunk_t *)(hunk_base + hunk_low_used); 329 starthigh = (hunk_t *)(hunk_base + hunk_size - hunk_high_used); 330 endhigh = (hunk_t *)(hunk_base + hunk_size); 331 332 Con_Printf (" :%8i total hunk size\n", hunk_size); 333 Con_Printf ("-------------------------\n"); 334 335 while (1) 336 { 337 // 338 // skip to the high hunk if done with low hunk 339 // 340 if ( h == endlow ) 341 { 342 Con_Printf ("-------------------------\n"); 343 Con_Printf (" :%8i REMAINING\n", hunk_size - hunk_low_used - hunk_high_used); 344 Con_Printf ("-------------------------\n"); 345 h = starthigh; 346 } 347 348 // 349 // if totally done, break 350 // 351 if ( h == endhigh ) 352 break; 353 354 // 355 // run consistancy checks 356 // 357 if (h->sentinal != HUNK_SENTINAL) 358 Sys_Error ("Hunk_Check: trahsed sentinal"); 359 if (h->size < 16 || h->size + (byte *)h - hunk_base > hunk_size) 360 Sys_Error ("Hunk_Check: bad size"); 361 362 next = (hunk_t *)((byte *)h+h->size); 363 count++; 364 totalblocks++; 365 sum += h->size; 366 367 // 368 // print the single block 369 // 370 memcpy (name, h->name, 8); 371 if (all) 372 Con_Printf ("%8p :%8i %8s\n",h, h->size, name); 373 374 // 375 // print the total 376 // 377 if (next == endlow || next == endhigh || 378 strncmp (h->name, next->name, 8) ) 379 { 380 if (!all) 381 Con_Printf (" :%8i %8s (TOTAL)\n",sum, name); 382 count = 0; 383 sum = 0; 384 } 385 386 h = next; 387 } 388 389 Con_Printf ("-------------------------\n"); 390 Con_Printf ("%8i total blocks\n", totalblocks); 391 392} 393 394/* 395=================== 396Hunk_AllocName 397=================== 398*/ 399void *Hunk_AllocName (int size, const char *name) 400{ 401 hunk_t *h; 402 403#ifdef PARANOID 404 Hunk_Check (); 405#endif 406 407 if (size < 0) 408 Sys_Error ("Hunk_Alloc: bad size: %i", size); 409 410 size = sizeof(hunk_t) + ((size+15)&~15); 411 412 if (hunk_size - hunk_low_used - hunk_high_used < size) 413 Sys_Error ("Hunk_Alloc: failed on %i bytes",size); 414 415 h = (hunk_t *)(hunk_base + hunk_low_used); 416 hunk_low_used += size; 417 418 Cache_FreeLow (hunk_low_used); 419 420 memset (h, 0, size); 421 422 h->size = size; 423 h->sentinal = HUNK_SENTINAL; 424 Q_strncpy (h->name, name, 8); 425 426 return (void *)(h+1); 427} 428 429/* 430=================== 431Hunk_Alloc 432=================== 433*/ 434void *Hunk_Alloc (int size) 435{ 436 return Hunk_AllocName (size, "unknown"); 437} 438 439int Hunk_LowMark (void) 440{ 441 return hunk_low_used; 442} 443 444void Hunk_FreeToLowMark (int mark) 445{ 446 if (mark < 0 || mark > hunk_low_used) 447 Sys_Error ("Hunk_FreeToLowMark: bad mark %i", mark); 448 memset (hunk_base + mark, 0, hunk_low_used - mark); 449 hunk_low_used = mark; 450} 451 452int Hunk_HighMark (void) 453{ 454 if (hunk_tempactive) 455 { 456 hunk_tempactive = false; 457 Hunk_FreeToHighMark (hunk_tempmark); 458 } 459 460 return hunk_high_used; 461} 462 463void Hunk_FreeToHighMark (int mark) 464{ 465 if (hunk_tempactive) 466 { 467 hunk_tempactive = false; 468 Hunk_FreeToHighMark (hunk_tempmark); 469 } 470 if (mark < 0 || mark > hunk_high_used) 471 Sys_Error ("Hunk_FreeToHighMark: bad mark %i", mark); 472 memset (hunk_base + hunk_size - hunk_high_used, 0, hunk_high_used - mark); 473 hunk_high_used = mark; 474} 475 476 477/* 478=================== 479Hunk_HighAllocName 480=================== 481*/ 482void *Hunk_HighAllocName (int size, const char *name) 483{ 484 hunk_t *h; 485 486 if (size < 0) 487 Sys_Error ("Hunk_HighAllocName: bad size: %i", size); 488 489 if (hunk_tempactive) 490 { 491 Hunk_FreeToHighMark (hunk_tempmark); 492 hunk_tempactive = false; 493 } 494 495#ifdef PARANOID 496 Hunk_Check (); 497#endif 498 499 size = sizeof(hunk_t) + ((size+15)&~15); 500 501 if (hunk_size - hunk_low_used - hunk_high_used < size) 502 { 503 Con_Printf ("Hunk_HighAlloc: failed on %i bytes\n",size); 504 return NULL; 505 } 506 507 hunk_high_used += size; 508 Cache_FreeHigh (hunk_high_used); 509 510 h = (hunk_t *)(hunk_base + hunk_size - hunk_high_used); 511 512 memset (h, 0, size); 513 h->size = size; 514 h->sentinal = HUNK_SENTINAL; 515 Q_strncpy (h->name, name, 8); 516 517 return (void *)(h+1); 518} 519 520 521/* 522================= 523Hunk_TempAlloc 524 525Return space from the top of the hunk 526================= 527*/ 528void *Hunk_TempAlloc (int size) 529{ 530 void *buf; 531 532 size = (size+15)&~15; 533 534 if (hunk_tempactive) 535 { 536 Hunk_FreeToHighMark (hunk_tempmark); 537 hunk_tempactive = false; 538 } 539 540 hunk_tempmark = Hunk_HighMark (); 541 542 buf = Hunk_HighAllocName (size, "temp"); 543 544 hunk_tempactive = true; 545 546 return buf; 547} 548 549/* 550=============================================================================== 551 552CACHE MEMORY 553 554=============================================================================== 555*/ 556 557typedef struct cache_system_s 558{ 559 int size; // including this header 560 cache_user_t *user; 561 char name[16]; 562 struct cache_system_s *prev, *next; 563 struct cache_system_s *lru_prev, *lru_next; // for LRU flushing 564} cache_system_t; 565 566cache_system_t *Cache_TryAlloc (int size, qboolean nobottom); 567 568cache_system_t cache_head; 569 570/* 571=========== 572Cache_Move 573=========== 574*/ 575void Cache_Move ( cache_system_t *c) 576{ 577 cache_system_t *newc; 578 579// we are clearing up space at the bottom, so only allocate it late 580 newc = Cache_TryAlloc (c->size, true); 581 if (newc) 582 { 583// Con_Printf ("cache_move ok\n"); 584 585 Q_memcpy ( newc+1, c+1, c->size - sizeof(cache_system_t) ); 586 newc->user = c->user; 587 Q_memcpy (newc->name, c->name, sizeof(newc->name)); 588 Cache_Free (c->user); 589 newc->user->data = (void *)(newc+1); 590 } 591 else 592 { 593// Con_Printf ("cache_move failed\n"); 594 595 Cache_Free (c->user); // tough luck... 596 } 597} 598 599/* 600============ 601Cache_FreeLow 602 603Throw things out until the hunk can be expanded to the given point 604============ 605*/ 606void Cache_FreeLow (int new_low_hunk) 607{ 608 cache_system_t *c; 609 610 while (1) 611 { 612 c = cache_head.next; 613 if (c == &cache_head) 614 return; // nothing in cache at all 615 if ((byte *)c >= hunk_base + new_low_hunk) 616 return; // there is space to grow the hunk 617 Cache_Move ( c ); // reclaim the space 618 } 619} 620 621/* 622============ 623Cache_FreeHigh 624 625Throw things out until the hunk can be expanded to the given point 626============ 627*/ 628void Cache_FreeHigh (int new_high_hunk) 629{ 630 cache_system_t *c, *prev; 631 632 prev = NULL; 633 while (1) 634 { 635 c = cache_head.prev; 636 if (c == &cache_head) 637 return; // nothing in cache at all 638 if ( (byte *)c + c->size <= hunk_base + hunk_size - new_high_hunk) 639 return; // there is space to grow the hunk 640 if (c == prev) 641 Cache_Free (c->user); // didn't move out of the way 642 else 643 { 644 Cache_Move (c); // try to move it 645 prev = c; 646 } 647 } 648} 649 650void Cache_UnlinkLRU (cache_system_t *cs) 651{ 652 if (!cs->lru_next || !cs->lru_prev) 653 Sys_Error ("Cache_UnlinkLRU: NULL link"); 654 655 cs->lru_next->lru_prev = cs->lru_prev; 656 cs->lru_prev->lru_next = cs->lru_next; 657 658 cs->lru_prev = cs->lru_next = NULL; 659} 660 661void Cache_MakeLRU (cache_system_t *cs) 662{ 663 if (cs->lru_next || cs->lru_prev) 664 Sys_Error ("Cache_MakeLRU: active link"); 665 666 cache_head.lru_next->lru_prev = cs; 667 cs->lru_next = cache_head.lru_next; 668 cs->lru_prev = &cache_head; 669 cache_head.lru_next = cs; 670} 671 672/* 673============ 674Cache_TryAlloc 675 676Looks for a free block of memory between the high and low hunk marks 677Size should already include the header and padding 678============ 679*/ 680cache_system_t *Cache_TryAlloc (int size, qboolean nobottom) 681{ 682 cache_system_t *cs, *newc; 683 684// is the cache completely empty? 685 686 if (!nobottom && cache_head.prev == &cache_head) 687 { 688 if (hunk_size - hunk_high_used - hunk_low_used < size) 689 Sys_Error ("Cache_TryAlloc: %i is greater then free hunk", size); 690 691 newc = (cache_system_t *) (hunk_base + hunk_low_used); 692 memset (newc, 0, sizeof(*newc)); 693 newc->size = size; 694 695 cache_head.prev = cache_head.next = newc; 696 newc->prev = newc->next = &cache_head; 697 698 Cache_MakeLRU (newc); 699 return newc; 700 } 701 702// search from the bottom up for space 703 704 newc = (cache_system_t *) (hunk_base + hunk_low_used); 705 cs = cache_head.next; 706 707 do 708 { 709 if (!nobottom || cs != cache_head.next) 710 { 711 if ( (byte *)cs - (byte *)newc >= size) 712 { // found space 713 memset (newc, 0, sizeof(*newc)); 714 newc->size = size; 715 716 newc->next = cs; 717 newc->prev = cs->prev; 718 cs->prev->next = newc; 719 cs->prev = newc; 720 721 Cache_MakeLRU (newc); 722 723 return newc; 724 } 725 } 726 727 // continue looking 728 newc = (cache_system_t *)((byte *)cs + cs->size); 729 cs = cs->next; 730 731 } while (cs != &cache_head); 732 733// try to allocate one at the very end 734 if ( hunk_base + hunk_size - hunk_high_used - (byte *)newc >= size) 735 { 736 memset (newc, 0, sizeof(*newc)); 737 newc->size = size; 738 739 newc->next = &cache_head; 740 newc->prev = cache_head.prev; 741 cache_head.prev->next = newc; 742 cache_head.prev = newc; 743 744 Cache_MakeLRU (newc); 745 746 return newc; 747 } 748 749 return NULL; // couldn't allocate 750} 751 752/* 753============ 754Cache_Flush 755 756Throw everything out, so new data will be demand cached 757============ 758*/ 759void Cache_Flush (void) 760{ 761 while (cache_head.next != &cache_head) 762 Cache_Free ( cache_head.next->user ); // reclaim the space 763} 764 765 766/* 767============ 768Cache_Print 769 770============ 771*/ 772void Cache_Print (void) 773{ 774 cache_system_t *cd; 775 776 for (cd = cache_head.next ; cd != &cache_head ; cd = cd->next) 777 { 778 Con_Printf ("%8i : %s\n", cd->size, cd->name); 779 } 780} 781 782/* 783============ 784Cache_Report 785 786============ 787*/ 788void Cache_Report (void) 789{ 790 Con_DPrintf ("%4.1f megabyte data cache\n", (hunk_size - hunk_high_used - hunk_low_used) / (float)(1024*1024) ); 791} 792 793/* 794============ 795Cache_Compact 796 797============ 798*/ 799void Cache_Compact (void) 800{ 801} 802 803/* 804============ 805Cache_Init 806 807============ 808*/ 809void Cache_Init (void) 810{ 811 cache_head.next = cache_head.prev = &cache_head; 812 cache_head.lru_next = cache_head.lru_prev = &cache_head; 813 814 Cmd_AddCommand ("flush", Cache_Flush); 815} 816 817/* 818============== 819Cache_Free 820 821Frees the memory and removes it from the LRU list 822============== 823*/ 824void Cache_Free (cache_user_t *c) 825{ 826 cache_system_t *cs; 827 828 if (!c->data) 829 Sys_Error ("Cache_Free: not allocated"); 830 831 cs = ((cache_system_t *)c->data) - 1; 832 833 cs->prev->next = cs->next; 834 cs->next->prev = cs->prev; 835 cs->next = cs->prev = NULL; 836 837 c->data = NULL; 838 839 Cache_UnlinkLRU (cs); 840} 841 842 843 844/* 845============== 846Cache_Check 847============== 848*/ 849void *Cache_Check (cache_user_t *c) 850{ 851 cache_system_t *cs; 852 853 if (!c->data) 854 return NULL; 855 856 cs = ((cache_system_t *)c->data) - 1; 857 858// move to head of LRU 859 Cache_UnlinkLRU (cs); 860 Cache_MakeLRU (cs); 861 862 return c->data; 863} 864 865 866/* 867============== 868Cache_Alloc 869============== 870*/ 871void *Cache_Alloc (cache_user_t *c, int size, const char *name) 872{ 873 cache_system_t *cs; 874 875 if (c->data) 876 Sys_Error ("Cache_Alloc: allready allocated"); 877 878 if (size <= 0) 879 Sys_Error ("Cache_Alloc: size %i", size); 880 881 size = (size + sizeof(cache_system_t) + 15) & ~15; 882 883// find memory for it 884 while (1) 885 { 886 cs = Cache_TryAlloc (size, false); 887 if (cs) 888 { 889 strncpy (cs->name, name, sizeof(cs->name)-1); 890 c->data = (void *)(cs+1); 891 cs->user = c; 892 break; 893 } 894 895 // free the least recently used cahedat 896 if (cache_head.lru_prev == &cache_head) 897 Sys_Error ("Cache_Alloc: out of memory"); 898 // not enough memory at all 899 Cache_Free ( cache_head.lru_prev->user ); 900 } 901 902 return Cache_Check (c); 903} 904 905//============================================================================ 906 907 908/* 909======================== 910Memory_Init 911======================== 912*/ 913void Memory_Init (void *buf, int size) 914{ 915 int p; 916 int zonesize = DYNAMIC_SIZE; 917 918 hunk_base = (byte*) buf; 919 hunk_size = size; 920 hunk_low_used = 0; 921 hunk_high_used = 0; 922 923 Cache_Init (); 924 p = COM_CheckParm ("-zone"); 925 if (p) 926 { 927 if (p < com_argc-1) 928 zonesize = Q_atoi (com_argv[p+1]) * 1024; 929 else 930 Sys_Error ("Memory_Init: you must specify a size in KB after -zone"); 931 } 932 mainzone = (memzone_t*) Hunk_AllocName (zonesize, "zone" ); 933 Z_ClearZone (mainzone, zonesize); 934} 935 936