Changeset 2507 for trunk/src/win32k/misc/rmalloc_avl.c
- Timestamp:
- Jan 24, 2000, 2:45:21 AM (26 years ago)
- File:
-
- 1 edited
-
trunk/src/win32k/misc/rmalloc_avl.c (modified) (30 diffs)
Legend:
- Unmodified
- Added
- Removed
-
trunk/src/win32k/misc/rmalloc_avl.c
r2503 r2507 1 /* $Id: rmalloc_avl.c,v 1. 2 2000-01-23 03:20:53bird Exp $1 /* $Id: rmalloc_avl.c,v 1.3 2000-01-24 01:45:20 bird Exp $ 2 2 * 3 3 * Resident Heap - AVL. … … 6 6 * Use with care! We're running at Ring-0! 7 7 * 8 * Copyright (c) 1999 knut st. osmundsen8 * Copyright (c) 1999-2000 knut st. osmundsen 9 9 * 10 10 * Project Odin Software License can be found in LICENSE.TXT … … 12 12 */ 13 13 14 #define static 14 15 15 /******************************************************************************* 16 16 * Defined Constants And Macros * … … 18 18 #ifdef DEBUG 19 19 #define DEBUG_ALLOC 20 # undefALLWAYS_HEAPCHECK20 #define ALLWAYS_HEAPCHECK 21 21 #endif 22 22 … … 167 167 PMEMBLOCKFREE pmbfTmp; 168 168 169 pmbfTmp = (PMEMBLOCKFREE)AVLGetWithParent( (PPAVLNODECORE)&pha->pcoreFreeSize,169 pmbfTmp = (PMEMBLOCKFREE)AVLGetWithParent(&pha->pcoreFreeSize, 170 170 (PPAVLNODECORE)SSToDS(&pmbfParent), 171 171 pmbf->coreFree.Key); … … 191 191 if (pmbfTmp->pmbfNext == NULL) 192 192 { /* no list - no other nodes of this size: simply remove it. */ 193 AVLRemove( (PPAVLNODECORE)&pha->pcoreFreeSize, pmbf->coreFree.Key);193 AVLRemove(&pha->pcoreFreeSize, pmbf->coreFree.Key); 194 194 } 195 195 else … … 200 200 pmbfParent = MEMBLOCKFREE_FROM_FREESIZENODE(pmbfParent); 201 201 if (pmbfTmp->coreFree.Key < pmbfParent->coreFree.Key) 202 pmbfParent->coreFree.pLeft = (PAVLNODECORE)&pmbf->pmbfNext->coreFree;202 pmbfParent->coreFree.pLeft = &pmbf->pmbfNext->coreFree; 203 203 else 204 pmbfParent->coreFree.pRight = (PAVLNODECORE)&pmbf->pmbfNext->coreFree;204 pmbfParent->coreFree.pRight = &pmbf->pmbfNext->coreFree; 205 205 } 206 206 else 207 pha->pcoreFreeSize = (PAVLNODECORE)&pmbf->pmbfNext->coreFree;207 pha->pcoreFreeSize = &pmbf->pmbfNext->coreFree; 208 208 } 209 209 } … … 221 221 PMEMBLOCKFREE pmbfTmp; 222 222 223 pmbfTmp = (PMEMBLOCKFREE)AVLGet( (PPAVLNODECORE)&pha->pcoreFreeSize, pmbf->coreFree.Key);223 pmbfTmp = (PMEMBLOCKFREE)AVLGet(&pha->pcoreFreeSize, pmbf->coreFree.Key); 224 224 if (pmbfTmp != NULL) 225 225 { … … 234 234 { 235 235 pmbf->pmbfNext = NULL; 236 AVLInsert( (PPAVLNODECORE)&pha->pcoreFreeSize, &pmbf->coreFree);236 AVLInsert(&pha->pcoreFreeSize, &pmbf->coreFree); 237 237 } 238 238 } … … 248 248 static void resInsertFree(PHEAPANCHOR pha, PMEMBLOCK pmb) 249 249 { 250 /* some more work left here... */251 250 PMEMBLOCKFREE pmbf = (PMEMBLOCKFREE)pmb; 252 251 PMEMBLOCKFREE pmbfRight; … … 401 400 register PHEAPANCHOR pha = *ppha; 402 401 PMEMBLOCK pmb; 402 memset(pha, 0, sizeof(*pha)); 403 403 404 404 /* anchor block */ … … 407 407 #endif 408 408 pha->cbSize = cbBlockSize; 409 pha->pmbUsed = NULL;410 pha->cbUsed = 0;411 pha->cbFree = 0;412 pha->pcoreFreeSize = NULL;413 409 414 410 /* free memblock */ … … 458 454 * NULL is allowed. 459 455 * @param pvUser User pointer to find the block to. 460 * @param fWithin When this flag is set, the pointer may point anywhere within the block.461 * When clear, it has to point exactly at the start of the user data area.462 456 */ 463 457 static PMEMBLOCK resFindUsedBlock(PHEAPANCHOR *ppha, void *pvUser) 464 458 { 465 if (pvUser != NULL && ppha != NULL)459 if (pvUser != NULL) 466 460 { 467 461 register PHEAPANCHOR pha = phaFirst; … … 524 518 if (pha->ulSignature != HEAPANCHOR_SIGNATURE) 525 519 { 526 kprintf(("resFind UsedBlock: Invalid heapanchor signature.\n"));520 kprintf(("resFindWithinUsedBlock: Invalid heapanchor signature.\n")); 527 521 return NULL; 528 522 } … … 534 528 if (pmb != NULL 535 529 && (unsigned)pmb + pmb->cbSize + CB_HDR > (unsigned)pvUser 536 && (unsigned)pmb + CB_HDR >= (unsigned)pvUser530 && (unsigned)pmb + CB_HDR <= (unsigned)pvUser 537 531 ) 538 532 { … … 558 552 * @param cbSizeMax Maximum heapsize in bytes. 559 553 */ 560 int ResHeapInit(unsigned cbSizeInit, unsigned cbSizeMax)554 int resHeapInit(unsigned cbSizeInit, unsigned cbSizeMax) 561 555 { 562 556 unsigned cbSize = MAX(BLOCKSIZE, cbSizeInit); … … 600 594 #ifdef ALLWAYS_HEAPCHECK 601 595 if (!_res_heap_check()) 602 { 603 /* error! */604 kprintf(("%s: _res_heap_check failed!\n", "heapInit"));596 { /* error! */ 597 kprintf(("resHeapInit: _res_heap_check failed!\n")); 598 #ifdef DEBUG 605 599 Int3(); 600 #endif 606 601 return -2; 607 602 } … … 623 618 void * rmalloc(unsigned cbSize) 624 619 { 625 void *pvRet = NULL;626 627 620 #ifdef ALLWAYS_HEAPCHECK 628 629 630 631 632 621 if (!_res_heap_check()) 622 { 623 kprintf(("rmalloc: _res_heap_check failed!\n")); 624 return NULL; 625 } 633 626 #endif 634 627 … … 640 633 { 641 634 resInsertUsed(pha, pmb); 642 pvRet =&pmb->achUserData[0];635 return &pmb->achUserData[0]; 643 636 } 644 637 } 645 638 else 646 { /* error! */647 639 kprintf(("rmalloc: error cbSize = 0\n")); 648 } 649 650 return pvRet; 640 641 return NULL; 651 642 } 652 643 … … 665 656 666 657 #ifdef ALLWAYS_HEAPCHECK 667 668 669 kprintf(("rmalloc: _res_heap_check failed!\n"));670 671 658 if (!_res_heap_check()) 659 { 660 kprintf(("rrealloc: _res_heap_check failed!\n")); 661 return NULL; 662 } 672 663 #endif 673 664 pmb = resFindUsedBlock(SSToDS(&pha), pv); … … 684 675 PMEMBLOCKFREE pmbfNew = (PMEMBLOCKFREE)((unsigned)pmb + CB_HDR + cbNew); 685 676 #ifdef DEBUG_ALLOC 686 677 pmbfNew->ulSignature = MEMBLOCK_SIGNATURE; 687 678 #endif 688 679 pha->cbUsed -= pmb->cbSize - cbNew; … … 691 682 resInsertFree(pha, (PMEMBLOCK)pmbfNew); 692 683 #ifdef ALLWAYS_HEAPCHECK 693 if (!_res_heap_check()) 684 if (!_res_heap_check()) 685 { 686 kprintf(("rrealloc: _res_heap_check failed!\n")); 687 return NULL; 688 } 689 #endif 690 } 691 } 692 else 693 { /* expand block - this code may be optimized... */ 694 #if 0 695 pvRet = rmalloc(cbNew); 696 if (pvRet != NULL) 697 { 698 memcpy(pvRet, pv, pmb->cbSize); 699 rfree(pv); 700 } 701 #else 702 /* optimized FIXME! */ 703 PMEMBLOCKFREE pmbfRightParent; 704 PMEMBLOCKFREE pmbfRight = (PMEMBLOCKFREE)AVLGetWithParent((PPAVLNODECORE)&pha->pmbFree, 705 (PPAVLNODECORE)SSToDS(&pmbfRightParent), 706 (AVLKEY)PNEXT_BLOCK(pmb)); 707 if (pmbfRight != NULL && pmbfRight->coreFree.Key + pmb->cbSize + CB_HDR >= cbNew) 708 { 709 pvRet = pv; 710 /* split the free block? */ 711 if (pmbfRight->coreFree.Key + pmb->cbSize + CB_HDR - sizeof(MEMBLOCKFREE) >= cbNew) 712 { 713 unsigned cb = pmbfRight->coreFree.Key; 714 PMEMBLOCKFREE pmbfNew = (PMEMBLOCKFREE)((unsigned)pmb + CB_HDR + cbNew); 715 resRemoveFromFreeSize(pha, pmbfRight); 716 pmbfNew->coreFree.Key = cb + pmb->cbSize - cbNew; 717 memmove((void*)&pmbfNew->core, (void*)&pmbfRight->core, sizeof(pmbfNew->core)); 718 pmbfNew->core.Key = (AVLKEY)pmbfNew; 719 #ifdef DEBUG_ALLOC 720 pmbfNew->ulSignature = MEMBLOCK_SIGNATURE; 721 #endif 722 if (pmbfRightParent != NULL) 694 723 { 695 kprintf(("rrealloc: _res_heap_check failed!\n")); 724 if (pmbfNew < pmbfRightParent) 725 pmbfRightParent->core.pLeft = &pmbfNew->core; 726 else 727 pmbfRightParent->core.pRight = &pmbfNew->core; 728 } 729 else 730 pha->pmbFree = (PMEMBLOCK)pmbfNew; 731 732 resInsertIntoFreeSize(pha, pmbfNew); 733 pha->cbUsed += cbNew - pmb->cbSize; 734 pha->cbFree -= cb - pmbfNew->coreFree.Key; 735 pmb->cbSize = cbNew; 736 } 737 else 738 { 739 if (AVLRemove((PPAVLNODECORE)&pha->pmbFree, (AVLKEY)pmbfRight) != (PAVLNODECORE)pmbfRight) 740 { 741 kprintf(("rrealloc: AVLRemove failed for pmbfRight - hmm!\n")); 696 742 return NULL; 697 743 } 698 #endif 744 resRemoveFromFreeSize(pha, pmbfRight); 745 pmb->cbSize += pmbfRight->coreFree.Key + CB_HDR; 746 pha->cbFree -= pmbfRight->coreFree.Key; 747 pha->cbUsed += pmbfRight->coreFree.Key + CB_HDR; 748 } 749 699 750 } 700 } 701 else 702 { /* expand block - this code may be more optimized... */ 703 #if 1 751 else 752 { /* worst case: allocate a new block, copy data and free the old block. */ 704 753 pvRet = rmalloc(cbNew); 705 754 if (pvRet != NULL) … … 708 757 rfree(pv); 709 758 } 710 #else 711 /* optimized */ 712 PMEMBLOCK pmb 759 } 713 760 #endif 714 761 } … … 779 826 #ifdef ALLWAYS_HEAPCHECK 780 827 if (!_res_heap_check()) 781 kprintf(("_ msize: _res_heap_check failed!\n"));828 kprintf(("_res_msize: _res_heap_check failed!\n")); 782 829 #endif 783 830 … … 799 846 #ifdef ALLWAYS_HEAPCHECK 800 847 if (!_res_heap_check()) 801 kprintf(("_ validptr: _res_heap_check failed!\n"));848 kprintf(("_res_validptr: _res_heap_check failed!\n")); 802 849 #endif 803 850 … … 820 867 #ifdef ALLWAYS_HEAPCHECK 821 868 if (!_res_heap_check()) 822 kprintf(("_ validptr: _res_heap_check failed!\n"));869 kprintf(("_res_validptr: _res_heap_check failed!\n")); 823 870 #endif 824 871 … … 843 890 #ifdef ALLWAYS_HEAPCHECK 844 891 if (!_res_heap_check()) 845 kprintf((" res_memfree: _res_heap_check failed!\n"));892 kprintf(("_res_memfree: _res_heap_check failed!\n")); 846 893 #endif 847 894 … … 988 1035 else 989 1036 { 990 PMEMBLOCKFREE pmbf = (PMEMBLOCKFREE)AVLGet( (PPAVLNODECORE)&pha->pcoreFreeSize, pmbFree->cbSize);1037 PMEMBLOCKFREE pmbf = (PMEMBLOCKFREE)AVLGet(&pha->pcoreFreeSize, pmbFree->cbSize); 991 1038 if (pmbf != NULL) 992 1039 { … … 1127 1174 if (pNode == NULL) 1128 1175 return 0; 1129 if (pNode->Key < 4 || (pNode->Key % 4) != 0)1176 if (pNode->Key < 4 || (pNode->Key % ALIGNMENT) != 0) 1130 1177 { 1131 1178 kprintf(("resCheckAVLTreeFree: Invalid Key! 0x%08x\n", pNode->Key)); … … 1208 1255 #endif 1209 1256 if (rc != NO_ERROR) 1210 kprintf(("_res_heapmin: DosFreeMem failed for pha=0x%08x, rc = %d\n",1257 kprintf(("_res_heapmin: DosFreeMem/D32Help_VMFree failed for pha=0x%08x, rc = %d\n", 1211 1258 pha, rc)); 1212 1259 }
Note:
See TracChangeset
for help on using the changeset viewer.
