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 0x20000 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, *new, *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 new = (memblock_t *) ((byte *)base + size ); 191 new->size = extra; 192 new->tag = 0; // free block 193 new->prev = base; 194 new->id = ZONEID; 195 new->next = base->next; 196 new->next->prev = new; 197 base->next = new; 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, 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#ifdef _WIN32 415 Sys_Error ("Not enough RAM allocated. Try starting using \"-heapsize 16000\" on the QuakeWorld command line."); 416#else 417 Sys_Error ("Not enough RAM allocated. Try starting using \"-mem 16\" on the QuakeWorld command line."); 418#endif 419 420 h = (hunk_t *)(hunk_base + hunk_low_used); 421 hunk_low_used += size; 422 423 Cache_FreeLow (hunk_low_used); 424 425 memset (h, 0, size); 426 427 h->size = size; 428 h->sentinal = HUNK_SENTINAL; 429 Q_strncpy (h->name, name, 8); 430 431 return (void *)(h+1); 432} 433 434/* 435=================== 436Hunk_Alloc 437=================== 438*/ 439void *Hunk_Alloc (int size) 440{ 441 return Hunk_AllocName (size, "unknown"); 442} 443 444int Hunk_LowMark (void) 445{ 446 return hunk_low_used; 447} 448 449void Hunk_FreeToLowMark (int mark) 450{ 451 if (mark < 0 || mark > hunk_low_used) 452 Sys_Error ("Hunk_FreeToLowMark: bad mark %i", mark); 453 memset (hunk_base + mark, 0, hunk_low_used - mark); 454 hunk_low_used = mark; 455} 456 457int Hunk_HighMark (void) 458{ 459 if (hunk_tempactive) 460 { 461 hunk_tempactive = false; 462 Hunk_FreeToHighMark (hunk_tempmark); 463 } 464 465 return hunk_high_used; 466} 467 468void Hunk_FreeToHighMark (int mark) 469{ 470 if (hunk_tempactive) 471 { 472 hunk_tempactive = false; 473 Hunk_FreeToHighMark (hunk_tempmark); 474 } 475 if (mark < 0 || mark > hunk_high_used) 476 Sys_Error ("Hunk_FreeToHighMark: bad mark %i", mark); 477 memset (hunk_base + hunk_size - hunk_high_used, 0, hunk_high_used - mark); 478 hunk_high_used = mark; 479} 480 481 482/* 483=================== 484Hunk_HighAllocName 485=================== 486*/ 487void *Hunk_HighAllocName (int size, char *name) 488{ 489 hunk_t *h; 490 491 if (size < 0) 492 Sys_Error ("Hunk_HighAllocName: bad size: %i", size); 493 494 if (hunk_tempactive) 495 { 496 Hunk_FreeToHighMark (hunk_tempmark); 497 hunk_tempactive = false; 498 } 499 500#ifdef PARANOID 501 Hunk_Check (); 502#endif 503 504 size = sizeof(hunk_t) + ((size+15)&~15); 505 506 if (hunk_size - hunk_low_used - hunk_high_used < size) 507 { 508 Con_Printf ("Hunk_HighAlloc: failed on %i bytes\n",size); 509 return NULL; 510 } 511 512 hunk_high_used += size; 513 Cache_FreeHigh (hunk_high_used); 514 515 h = (hunk_t *)(hunk_base + hunk_size - hunk_high_used); 516 517 memset (h, 0, size); 518 h->size = size; 519 h->sentinal = HUNK_SENTINAL; 520 Q_strncpy (h->name, name, 8); 521 522 return (void *)(h+1); 523} 524 525 526/* 527================= 528Hunk_TempAlloc 529 530Return space from the top of the hunk 531================= 532*/ 533void *Hunk_TempAlloc (int size) 534{ 535 void *buf; 536 537 size = (size+15)&~15; 538 539 if (hunk_tempactive) 540 { 541 Hunk_FreeToHighMark (hunk_tempmark); 542 hunk_tempactive = false; 543 } 544 545 hunk_tempmark = Hunk_HighMark (); 546 547 buf = Hunk_HighAllocName (size, "temp"); 548 549 hunk_tempactive = true; 550 551 return buf; 552} 553 554/* 555=============================================================================== 556 557CACHE MEMORY 558 559=============================================================================== 560*/ 561 562typedef struct cache_system_s 563{ 564 int size; // including this header 565 cache_user_t *user; 566 char name[16]; 567 struct cache_system_s *prev, *next; 568 struct cache_system_s *lru_prev, *lru_next; // for LRU flushing 569} cache_system_t; 570 571cache_system_t *Cache_TryAlloc (int size, qboolean nobottom); 572 573cache_system_t cache_head; 574 575/* 576=========== 577Cache_Move 578=========== 579*/ 580void Cache_Move ( cache_system_t *c) 581{ 582 cache_system_t *new; 583 584// we are clearing up space at the bottom, so only allocate it late 585 new = Cache_TryAlloc (c->size, true); 586 if (new) 587 { 588// Con_Printf ("cache_move ok\n"); 589 590 Q_memcpy ( new+1, c+1, c->size - sizeof(cache_system_t) ); 591 new->user = c->user; 592 Q_memcpy (new->name, c->name, sizeof(new->name)); 593 Cache_Free (c->user); 594 new->user->data = (void *)(new+1); 595 } 596 else 597 { 598// Con_Printf ("cache_move failed\n"); 599 600 Cache_Free (c->user); // tough luck... 601 } 602} 603 604/* 605============ 606Cache_FreeLow 607 608Throw things out until the hunk can be expanded to the given point 609============ 610*/ 611void Cache_FreeLow (int new_low_hunk) 612{ 613 cache_system_t *c; 614 615 while (1) 616 { 617 c = cache_head.next; 618 if (c == &cache_head) 619 return; // nothing in cache at all 620 if ((byte *)c >= hunk_base + new_low_hunk) 621 return; // there is space to grow the hunk 622 Cache_Move ( c ); // reclaim the space 623 } 624} 625 626/* 627============ 628Cache_FreeHigh 629 630Throw things out until the hunk can be expanded to the given point 631============ 632*/ 633void Cache_FreeHigh (int new_high_hunk) 634{ 635 cache_system_t *c, *prev; 636 637 prev = NULL; 638 while (1) 639 { 640 c = cache_head.prev; 641 if (c == &cache_head) 642 return; // nothing in cache at all 643 if ( (byte *)c + c->size <= hunk_base + hunk_size - new_high_hunk) 644 return; // there is space to grow the hunk 645 if (c == prev) 646 Cache_Free (c->user); // didn't move out of the way 647 else 648 { 649 Cache_Move (c); // try to move it 650 prev = c; 651 } 652 } 653} 654 655void Cache_UnlinkLRU (cache_system_t *cs) 656{ 657 if (!cs->lru_next || !cs->lru_prev) 658 Sys_Error ("Cache_UnlinkLRU: NULL link"); 659 660 cs->lru_next->lru_prev = cs->lru_prev; 661 cs->lru_prev->lru_next = cs->lru_next; 662 663 cs->lru_prev = cs->lru_next = NULL; 664} 665 666void Cache_MakeLRU (cache_system_t *cs) 667{ 668 if (cs->lru_next || cs->lru_prev) 669 Sys_Error ("Cache_MakeLRU: active link"); 670 671 cache_head.lru_next->lru_prev = cs; 672 cs->lru_next = cache_head.lru_next; 673 cs->lru_prev = &cache_head; 674 cache_head.lru_next = cs; 675} 676 677/* 678============ 679Cache_TryAlloc 680 681Looks for a free block of memory between the high and low hunk marks 682Size should already include the header and padding 683============ 684*/ 685cache_system_t *Cache_TryAlloc (int size, qboolean nobottom) 686{ 687 cache_system_t *cs, *new; 688 689// is the cache completely empty? 690 691 if (!nobottom && cache_head.prev == &cache_head) 692 { 693 if (hunk_size - hunk_high_used - hunk_low_used < size) 694 Sys_Error ("Cache_TryAlloc: %i is greater then free hunk", size); 695 696 new = (cache_system_t *) (hunk_base + hunk_low_used); 697 memset (new, 0, sizeof(*new)); 698 new->size = size; 699 700 cache_head.prev = cache_head.next = new; 701 new->prev = new->next = &cache_head; 702 703 Cache_MakeLRU (new); 704 return new; 705 } 706 707// search from the bottom up for space 708 709 new = (cache_system_t *) (hunk_base + hunk_low_used); 710 cs = cache_head.next; 711 712 do 713 { 714 if (!nobottom || cs != cache_head.next) 715 { 716 if ( (byte *)cs - (byte *)new >= size) 717 { // found space 718 memset (new, 0, sizeof(*new)); 719 new->size = size; 720 721 new->next = cs; 722 new->prev = cs->prev; 723 cs->prev->next = new; 724 cs->prev = new; 725 726 Cache_MakeLRU (new); 727 728 return new; 729 } 730 } 731 732 // continue looking 733 new = (cache_system_t *)((byte *)cs + cs->size); 734 cs = cs->next; 735 736 } while (cs != &cache_head); 737 738// try to allocate one at the very end 739 if ( hunk_base + hunk_size - hunk_high_used - (byte *)new >= size) 740 { 741 memset (new, 0, sizeof(*new)); 742 new->size = size; 743 744 new->next = &cache_head; 745 new->prev = cache_head.prev; 746 cache_head.prev->next = new; 747 cache_head.prev = new; 748 749 Cache_MakeLRU (new); 750 751 return new; 752 } 753 754 return NULL; // couldn't allocate 755} 756 757/* 758============ 759Cache_Flush 760 761Throw everything out, so new data will be demand cached 762============ 763*/ 764void Cache_Flush (void) 765{ 766 while (cache_head.next != &cache_head) 767 Cache_Free ( cache_head.next->user ); // reclaim the space 768} 769 770 771/* 772============ 773Cache_Print 774 775============ 776*/ 777void Cache_Print (void) 778{ 779 cache_system_t *cd; 780 781 for (cd = cache_head.next ; cd != &cache_head ; cd = cd->next) 782 { 783 Con_Printf ("%8i : %s\n", cd->size, cd->name); 784 } 785} 786 787/* 788============ 789Cache_Report 790 791============ 792*/ 793void Cache_Report (void) 794{ 795 Con_DPrintf ("%4.1f megabyte data cache\n", (hunk_size - hunk_high_used - hunk_low_used) / (float)(1024*1024) ); 796} 797 798/* 799============ 800Cache_Compact 801 802============ 803*/ 804void Cache_Compact (void) 805{ 806} 807 808/* 809============ 810Cache_Init 811 812============ 813*/ 814void Cache_Init (void) 815{ 816 cache_head.next = cache_head.prev = &cache_head; 817 cache_head.lru_next = cache_head.lru_prev = &cache_head; 818 819 Cmd_AddCommand ("flush", Cache_Flush); 820} 821 822/* 823============== 824Cache_Free 825 826Frees the memory and removes it from the LRU list 827============== 828*/ 829void Cache_Free (cache_user_t *c) 830{ 831 cache_system_t *cs; 832 833 if (!c->data) 834 Sys_Error ("Cache_Free: not allocated"); 835 836 cs = ((cache_system_t *)c->data) - 1; 837 838 cs->prev->next = cs->next; 839 cs->next->prev = cs->prev; 840 cs->next = cs->prev = NULL; 841 842 c->data = NULL; 843 844 Cache_UnlinkLRU (cs); 845} 846 847 848 849/* 850============== 851Cache_Check 852============== 853*/ 854void *Cache_Check (cache_user_t *c) 855{ 856 cache_system_t *cs; 857 858 if (!c->data) 859 return NULL; 860 861 cs = ((cache_system_t *)c->data) - 1; 862 863// move to head of LRU 864 Cache_UnlinkLRU (cs); 865 Cache_MakeLRU (cs); 866 867 return c->data; 868} 869 870 871/* 872============== 873Cache_Alloc 874============== 875*/ 876void *Cache_Alloc (cache_user_t *c, int size, char *name) 877{ 878 cache_system_t *cs; 879 880 if (c->data) 881 Sys_Error ("Cache_Alloc: allready allocated"); 882 883 if (size <= 0) 884 Sys_Error ("Cache_Alloc: size %i", size); 885 886 size = (size + sizeof(cache_system_t) + 15) & ~15; 887 888// find memory for it 889 while (1) 890 { 891 cs = Cache_TryAlloc (size, false); 892 if (cs) 893 { 894 strncpy (cs->name, name, sizeof(cs->name)-1); 895 c->data = (void *)(cs+1); 896 cs->user = c; 897 break; 898 } 899 900 // free the least recently used cahedat 901 if (cache_head.lru_prev == &cache_head) 902 Sys_Error ("Cache_Alloc: out of memory"); 903 // not enough memory at all 904 Cache_Free ( cache_head.lru_prev->user ); 905 } 906 907 return Cache_Check (c); 908} 909 910//============================================================================ 911 912 913/* 914======================== 915Memory_Init 916======================== 917*/ 918void Memory_Init (void *buf, int size) 919{ 920 int p; 921 int zonesize = DYNAMIC_SIZE; 922 923 hunk_base = buf; 924 hunk_size = size; 925 hunk_low_used = 0; 926 hunk_high_used = 0; 927 928 Cache_Init (); 929 p = COM_CheckParm ("-zone"); 930 if (p) 931 { 932 if (p < com_argc-1) 933 zonesize = Q_atoi (com_argv[p+1]) * 1024; 934 else 935 Sys_Error ("Memory_Init: you must specify a size in KB after -zone"); 936 } 937 mainzone = Hunk_AllocName ( zonesize, "zone" ); 938 Z_ClearZone (mainzone, zonesize); 939} 940 941