Main Page | Class Hierarchy | Class List | File List | Class Members | File Members

hivecell.c

Go to the documentation of this file.
00001 /*++ 00002 00003 Copyright (c) 1991 Microsoft Corporation 00004 00005 Module Name: 00006 00007 hivecell.c 00008 00009 Abstract: 00010 00011 This module implements hive cell procedures. 00012 00013 Author: 00014 00015 Bryan M. Willman (bryanwi) 27-Mar-92 00016 00017 Environment: 00018 00019 00020 Revision History: 00021 Dragos C. Sambotin (dragoss) 22-Dec-98 00022 Requests for cells bigger than 1K are doubled. This way 00023 we avoid fragmentation and we make the value-growing 00024 process more flexible. 00025 Dragos C. Sambotin (dragoss) 13-Jan-99 00026 At boot time, order the free cells list ascending. 00027 00028 --*/ 00029 00030 #include "cmp.h" 00031 00032 // 00033 // Private procedures 00034 // 00035 HCELL_INDEX 00036 HvpDoAllocateCell( 00037 PHHIVE Hive, 00038 ULONG NewSize, 00039 HSTORAGE_TYPE Type 00040 ); 00041 00042 ULONG 00043 HvpAllocateInBin( 00044 PHHIVE Hive, 00045 PHBIN Bin, 00046 ULONG Size, 00047 ULONG Type 00048 ); 00049 00050 BOOLEAN 00051 HvpMakeBinPresent( 00052 IN PHHIVE Hive, 00053 IN HCELL_INDEX Cell, 00054 IN PHMAP_ENTRY Map 00055 ); 00056 00057 BOOLEAN 00058 HvpIsFreeNeighbor( 00059 PHHIVE Hive, 00060 PHBIN Bin, 00061 PHCELL FreeCell, 00062 PHCELL *FreeNeighbor, 00063 HSTORAGE_TYPE Type 00064 ); 00065 00066 VOID 00067 HvpDelistBinFreeCells( 00068 PHHIVE Hive, 00069 PHBIN Bin, 00070 HSTORAGE_TYPE Type, 00071 PHCELL_INDEX TailDisplay OPTIONAL 00072 ); 00073 00074 #define CmpFindFirstSetRight KiFindFirstSetRight 00075 extern CCHAR KiFindFirstSetRight[256]; 00076 #define CmpFindFirstSetLeft KiFindFirstSetLeft 00077 extern CCHAR KiFindFirstSetLeft[256]; 00078 00079 #define HvpComputeIndex(Index, Size) \ 00080 { \ 00081 Index = (Size >> HHIVE_FREE_DISPLAY_SHIFT) - 1; \ 00082 if (Index >= HHIVE_LINEAR_INDEX ) { \ 00083 \ 00084 /* \ 00085 ** Too big for the linear lists, compute the exponential \ 00086 ** list. \ 00087 */ \ 00088 \ 00089 if (Index > 255) { \ 00090 /* \ 00091 ** Too big for all the lists, use the last index. \ 00092 */ \ 00093 Index = HHIVE_FREE_DISPLAY_SIZE-1; \ 00094 } else { \ 00095 Index = CmpFindFirstSetLeft[Index] + \ 00096 HHIVE_FREE_DISPLAY_BIAS; \ 00097 } \ 00098 } \ 00099 } 00100 00101 #define ONE_K 1024 00102 00103 // Double requests bigger than 1KB 00104 // CmpSetValueKeyExisting always allocates a bigger data 00105 // value cell exactly the required size. This creates 00106 // problems when somebody slowly grows a value one DWORD 00107 // at a time to some enormous size. An easy fix for this 00108 // would be to set a certain threshold (like 1K). Once a 00109 // value size crosses that threshold, allocate a new cell 00110 // that is twice the old size. So the actual allocated 00111 // size would grow to 1k, then 2k, 4k, 8k, 16k, 32k,etc. 00112 // This will reduce the fragmentation. 00113 00114 #define HvpAdjustCellSize(Size) \ 00115 { \ 00116 ULONG onek = ONE_K; \ 00117 ULONG Limit = 0; \ 00118 \ 00119 while( Size > onek ) { \ 00120 onek<<=1; \ 00121 Limit++; \ 00122 } \ 00123 \ 00124 Size = Limit?onek:Size; \ 00125 } 00126 00127 00128 #ifdef ALLOC_PRAGMA 00129 #pragma alloc_text(PAGE,HvpGetCellPaged) 00130 #pragma alloc_text(PAGE,HvpGetCellFlat) 00131 #pragma alloc_text(PAGE,HvpGetCellMap) 00132 #pragma alloc_text(PAGE,HvGetCellSize) 00133 #pragma alloc_text(PAGE,HvAllocateCell) 00134 #pragma alloc_text(PAGE,HvpDoAllocateCell) 00135 #pragma alloc_text(PAGE,HvFreeCell) 00136 #pragma alloc_text(PAGE,HvpIsFreeNeighbor) 00137 #pragma alloc_text(PAGE,HvpEnlistFreeCell) 00138 #pragma alloc_text(PAGE,HvpDelistFreeCell) 00139 #pragma alloc_text(PAGE,HvReallocateCell) 00140 #pragma alloc_text(PAGE,HvIsCellAllocated) 00141 #pragma alloc_text(PAGE,HvpAllocateInBin) 00142 #pragma alloc_text(PAGE,HvpMakeBinPresent) 00143 #pragma alloc_text(PAGE,HvpDelistBinFreeCells) 00144 #endif 00145 00146 00147 // 00148 // Cell Procedures 00149 // 00150 struct _CELL_DATA * 00151 HvpGetCellPaged( 00152 PHHIVE Hive, 00153 HCELL_INDEX Cell 00154 ) 00155 /*++ 00156 00157 Routine Description: 00158 00159 Returns the memory address for the specified Cell. Will never 00160 return failure, but may assert. Use HvIsCellAllocated to check 00161 validity of Cell. 00162 00163 This routine should never be called directly, always call it 00164 via the HvGetCell() macro. 00165 00166 This routine provides GetCell support for hives with full maps. 00167 It is the normal version of the routine. 00168 00169 Arguments: 00170 00171 Hive - supplies a pointer to the hive control structure for the 00172 hive of interest 00173 00174 Cell - supplies HCELL_INDEX of cell to return address for 00175 00176 Return Value: 00177 00178 Address of Cell in memory. Assert or BugCheck if error. 00179 00180 --*/ 00181 { 00182 ULONG Type; 00183 ULONG Table; 00184 ULONG Block; 00185 ULONG Offset; 00186 PHCELL pcell; 00187 PHMAP_ENTRY Map; 00188 00189 CMLOG(CML_FLOW, CMS_MAP) { 00190 KdPrint(("HvGetCellPaged:\n")); 00191 KdPrint(("\tHive=%08lx Cell=%08lx\n",Hive,Cell)); 00192 } 00193 ASSERT(Hive->Signature == HHIVE_SIGNATURE); 00194 ASSERT(Cell != HCELL_NIL); 00195 ASSERT(Hive->Flat == FALSE); 00196 ASSERT((Cell & (HCELL_PAD(Hive)-1))==0); 00197 ASSERT_CM_LOCK_OWNED(); 00198 #if DBG 00199 if (HvGetCellType(Cell) == Stable) { 00200 ASSERT(Cell >= sizeof(HBIN)); 00201 } else { 00202 ASSERT(Cell >= (HCELL_TYPE_MASK + sizeof(HBIN))); 00203 } 00204 #endif 00205 00206 Type = HvGetCellType(Cell); 00207 Table = (Cell & HCELL_TABLE_MASK) >> HCELL_TABLE_SHIFT; 00208 Block = (Cell & HCELL_BLOCK_MASK) >> HCELL_BLOCK_SHIFT; 00209 Offset = (Cell & HCELL_OFFSET_MASK); 00210 00211 ASSERT((Cell - (Type * HCELL_TYPE_MASK)) < Hive->Storage[Type].Length); 00212 00213 Map = &((Hive->Storage[Type].Map)->Directory[Table]->Table[Block]); 00214 ASSERT((Map->BinAddress & HMAP_BASE) != 0); 00215 ASSERT((Map->BinAddress & HMAP_DISCARDABLE) == 0); 00216 pcell = (PHCELL)((ULONG_PTR)(Map->BlockAddress) + Offset); 00217 if (USE_OLD_CELL(Hive)) { 00218 return (struct _CELL_DATA *)&(pcell->u.OldCell.u.UserData); 00219 } else { 00220 return (struct _CELL_DATA *)&(pcell->u.NewCell.u.UserData); 00221 } 00222 } 00223 00224 00225 struct _CELL_DATA * 00226 HvpGetCellFlat( 00227 PHHIVE Hive, 00228 HCELL_INDEX Cell 00229 ) 00230 /*++ 00231 00232 Routine Description: 00233 00234 Returns the memory address for the specified Cell. Will never 00235 return failure, but may assert. Use HvIsCellAllocated to check 00236 validity of Cell. 00237 00238 This routine should never be called directly, always call it 00239 via the HvGetCell() macro. 00240 00241 This routine provides GetCell support for read only hives with 00242 single allocation flat images. Such hives do not have cell 00243 maps ("page tables"), instead, we compute addresses by 00244 arithmetic against the base image address. 00245 00246 Such hives cannot have volatile cells. 00247 00248 Arguments: 00249 00250 Hive - supplies a pointer to the hive control structure for the 00251 hive of interest 00252 00253 Cell - supplies HCELL_INDEX of cell to return address for 00254 00255 Return Value: 00256 00257 Address of Cell in memory. Assert or BugCheck if error. 00258 00259 --*/ 00260 { 00261 PUCHAR base; 00262 PHCELL pcell; 00263 00264 CMLOG(CML_FLOW, CMS_MAP) { 00265 KdPrint(("HvGetCellFlat:\n")); 00266 KdPrint(("\tHive=%08lx Cell=%08lx\n",Hive,Cell)); 00267 } 00268 ASSERT(Hive->Signature == HHIVE_SIGNATURE); 00269 ASSERT(Cell != HCELL_NIL); 00270 ASSERT(Hive->Flat == TRUE); 00271 ASSERT(HvGetCellType(Cell) == Stable); 00272 ASSERT(Cell >= sizeof(HBIN)); 00273 ASSERT(Cell < Hive->BaseBlock->Length); 00274 ASSERT((Cell & 0x7)==0); 00275 00276 // 00277 // Address is base of Hive image + Cell 00278 // 00279 base = (PUCHAR)(Hive->BaseBlock) + HBLOCK_SIZE; 00280 pcell = (PHCELL)(base + Cell); 00281 if (USE_OLD_CELL(Hive)) { 00282 return (struct _CELL_DATA *)&(pcell->u.OldCell.u.UserData); 00283 } else { 00284 return (struct _CELL_DATA *)&(pcell->u.NewCell.u.UserData); 00285 } 00286 } 00287 00288 00289 PHMAP_ENTRY 00290 HvpGetCellMap( 00291 PHHIVE Hive, 00292 HCELL_INDEX Cell 00293 ) 00294 /*++ 00295 00296 Routine Description: 00297 00298 Returns the address of the HMAP_ENTRY for the cell. 00299 00300 Arguments: 00301 00302 Hive - supplies a pointer to the hive control structure for the 00303 hive of interest 00304 00305 Cell - supplies HCELL_INDEX of cell to return map entry address for 00306 00307 Return Value: 00308 00309 Address of MAP_ENTRY in memory. NULL if no such cell or other error. 00310 00311 --*/ 00312 { 00313 ULONG Type; 00314 ULONG Table; 00315 ULONG Block; 00316 PHMAP_TABLE ptab; 00317 00318 CMLOG(CML_FLOW, CMS_MAP) { 00319 KdPrint(("HvpGetCellMapPaged:\n")); 00320 KdPrint(("\tHive=%08lx Cell=%08lx\n",Hive,Cell)); 00321 } 00322 ASSERT(Hive->Signature == HHIVE_SIGNATURE); 00323 ASSERT(Hive->Flat == FALSE); 00324 ASSERT((Cell & (HCELL_PAD(Hive)-1))==0); 00325 00326 Type = HvGetCellType(Cell); 00327 Table = (Cell & HCELL_TABLE_MASK) >> HCELL_TABLE_SHIFT; 00328 Block = (Cell & HCELL_BLOCK_MASK) >> HCELL_BLOCK_SHIFT; 00329 00330 if ((Cell - (Type * HCELL_TYPE_MASK)) >= Hive->Storage[Type].Length) { 00331 return NULL; 00332 } 00333 00334 ptab = (Hive->Storage[Type].Map)->Directory[Table]; 00335 return &(ptab->Table[Block]); 00336 } 00337 00338 00339 LONG 00340 HvGetCellSize( 00341 IN PHHIVE Hive, 00342 IN PVOID Address 00343 ) 00344 /*++ 00345 00346 Routine Description: 00347 00348 Returns the size of the specified Cell, based on its MEMORY 00349 ADDRESS. Must always call HvGetCell first to get that 00350 address. 00351 00352 NOTE: This should be a macro if speed is issue. 00353 00354 NOTE: If you pass in some random pointer, you will get some 00355 random answer. Only pass in valid Cell addresses. 00356 00357 Arguments: 00358 00359 Hive - supplies hive control structure for the given cell 00360 00361 Address - address in memory of the cell, returned by HvGetCell() 00362 00363 Return Value: 00364 00365 Allocated size in bytes of the cell. 00366 00367 If Negative, Cell is free, or Address is bogus. 00368 00369 --*/ 00370 { 00371 LONG size; 00372 00373 CMLOG(CML_FLOW, CMS_MAP) { 00374 KdPrint(("HvGetCellSize:\n")); 00375 KdPrint(("\tAddress=%08lx\n", Address)); 00376 } 00377 00378 if (USE_OLD_CELL(Hive)) { 00379 size = ( (CONTAINING_RECORD(Address, HCELL, u.OldCell.u.UserData))->Size ) * -1; 00380 size -= FIELD_OFFSET(HCELL, u.OldCell.u.UserData); 00381 } else { 00382 size = ( (CONTAINING_RECORD(Address, HCELL, u.NewCell.u.UserData))->Size ) * -1; 00383 size -= FIELD_OFFSET(HCELL, u.NewCell.u.UserData); 00384 } 00385 return size; 00386 } 00387 00388 00389 00390 HCELL_INDEX 00391 HvAllocateCell( 00392 PHHIVE Hive, 00393 ULONG NewSize, 00394 HSTORAGE_TYPE Type 00395 ) 00396 /*++ 00397 00398 Routine Description: 00399 00400 Allocates the space and the cell index for a new cell. 00401 00402 Arguments: 00403 00404 Hive - supplies a pointer to the hive control structure for the 00405 hive of interest 00406 00407 NewSize - size in bytes of the cell to allocate 00408 00409 Type - indicates whether Stable or Volatile storage is desired. 00410 00411 Return Value: 00412 00413 New HCELL_INDEX if success, HCELL_NIL if failure. 00414 00415 --*/ 00416 { 00417 HCELL_INDEX NewCell; 00418 00419 CMLOG(CML_MAJOR, CMS_HIVE) { 00420 KdPrint(("HvAllocateCell:\n")); 00421 KdPrint(("\tHive=%08lx NewSize=%08lx\n",Hive,NewSize)); 00422 } 00423 ASSERT(Hive->Signature == HHIVE_SIGNATURE); 00424 ASSERT(Hive->ReadOnly == FALSE); 00425 ASSERT_CM_LOCK_OWNED_EXCLUSIVE(); 00426 00427 // 00428 // Make room for overhead fields and round up to HCELL_PAD boundary 00429 // 00430 if (USE_OLD_CELL(Hive)) { 00431 NewSize += FIELD_OFFSET(HCELL, u.OldCell.u.UserData); 00432 } else { 00433 NewSize += FIELD_OFFSET(HCELL, u.NewCell.u.UserData); 00434 } 00435 NewSize = ROUND_UP(NewSize, HCELL_PAD(Hive)); 00436 00437 // 00438 // Adjust the size (an easy fix for granularity) 00439 // 00440 HvpAdjustCellSize(NewSize); 00441 // 00442 // reject impossible/unreasonable values 00443 // 00444 if (NewSize > HSANE_CELL_MAX) { 00445 return HCELL_NIL; 00446 } 00447 00448 // 00449 // Do the actual storage allocation 00450 // 00451 NewCell = HvpDoAllocateCell(Hive, NewSize, Type); 00452 00453 #if DBG 00454 if (NewCell != HCELL_NIL) { 00455 ASSERT(HvIsCellAllocated(Hive, NewCell)); 00456 } 00457 #endif 00458 00459 00460 CMLOG(CML_FLOW, CMS_HIVE) { 00461 KdPrint(("\tNewCell=%08lx\n", NewCell)); 00462 } 00463 return NewCell; 00464 } 00465 00466 00467 HCELL_INDEX 00468 HvpDoAllocateCell( 00469 PHHIVE Hive, 00470 ULONG NewSize, 00471 HSTORAGE_TYPE Type 00472 ) 00473 /*++ 00474 00475 Routine Description: 00476 00477 Allocates space in the hive. Does not affect cell map in any way. 00478 00479 Arguments: 00480 00481 Hive - supplies a pointer to the hive control structure for the 00482 hive of interest 00483 00484 NewSize - size in bytes of the cell to allocate 00485 00486 Type - indicates whether Stable or Volatile storage is desired. 00487 00488 Return Value: 00489 00490 HCELL_INDEX of new cell, HCELL_NIL if failure 00491 00492 --*/ 00493 { 00494 ULONG Index; 00495 ULONG Summary; 00496 HCELL_INDEX cell; 00497 PHCELL pcell; 00498 HCELL_INDEX tcell; 00499 PHCELL ptcell; 00500 PHBIN Bin; 00501 PHMAP_ENTRY Me; 00502 ULONG offset; 00503 PHCELL next; 00504 ULONG MinFreeSize; 00505 00506 00507 CMLOG(CML_MINOR, CMS_HIVE) { 00508 KdPrint(("HvDoAllocateCell:\n")); 00509 KdPrint(("\tHive=%08lx NewSize=%08lx Type=%08lx\n",Hive,NewSize,Type)); 00510 } 00511 ASSERT(Hive->ReadOnly == FALSE); 00512 00513 00514 // 00515 // Compute Index into Display 00516 // 00517 HvpComputeIndex(Index, NewSize); 00518 00519 // 00520 // Compute Summary vector of Display entries that are non null 00521 // 00522 Summary = Hive->Storage[Type].FreeSummary; 00523 Summary = Summary & ~((1 << Index) - 1); 00524 00525 // 00526 // We now have a summary of lists that are non-null and may 00527 // contain entries large enough to satisfy the request. 00528 // Iterate through the list and pull the first cell that is 00529 // big enough. If no cells are big enough, advance to the 00530 // next non-null list. 00531 // 00532 00533 ASSERT(HHIVE_FREE_DISPLAY_SIZE == 24); 00534 while (Summary != 0) { 00535 if (Summary & 0xff) { 00536 Index = CmpFindFirstSetRight[Summary & 0xff]; 00537 } else if (Summary & 0xff00) { 00538 Index = CmpFindFirstSetRight[(Summary & 0xff00) >> 8] + 8; 00539 } else { 00540 ASSERT(Summary & 0xff0000); 00541 Index = CmpFindFirstSetRight[(Summary & 0xff0000) >> 16] + 16; 00542 } 00543 00544 // 00545 // Walk through the list until we find a cell large enough 00546 // to satisfy the allocation. If we find one, pull it from 00547 // the list and use it. If we don't find one, clear this 00548 // list's bit in the Summary and try the next larger list. 00549 // 00550 00551 // 00552 // look for a large enough cell in the list 00553 // 00554 cell = Hive->Storage[Type].FreeDisplay[Index]; 00555 while (cell != HCELL_NIL) { 00556 00557 pcell = HvpGetHCell(Hive, cell); 00558 00559 if (NewSize <= (ULONG)pcell->Size) { 00560 00561 // 00562 // Found a big enough cell. 00563 // 00564 if (! HvMarkCellDirty(Hive, cell)) { 00565 return HCELL_NIL; 00566 } 00567 00568 HvpDelistFreeCell(Hive, pcell, Type, NULL); 00569 00570 ASSERT(pcell->Size > 0); 00571 ASSERT(NewSize <= (ULONG)pcell->Size); 00572 goto UseIt; 00573 } 00574 // DbgPrint("cell %08lx (%lx) too small (%d < %d), trying next at",cell,pcell,pcell->Size,NewSize); 00575 if (USE_OLD_CELL(Hive)) { 00576 cell = pcell->u.OldCell.u.Next; 00577 } else { 00578 cell = pcell->u.NewCell.u.Next; 00579 } 00580 // DbgPrint(" %08lx\n",cell); 00581 } 00582 00583 // 00584 // No suitable cell was found on that list. 00585 // Clear the bit in the summary and try the 00586 // next biggest list. 00587 // 00588 // DbgPrint("No suitable cell, Index %d, Summary %08lx -> ",Index, Summary); 00589 ASSERT(Summary & (1 << Index)); 00590 Summary = Summary & ~(1 << Index); 00591 // DbgPrint("%08lx\n",Summary); 00592 } 00593 00594 if (Summary == 0) { 00595 // 00596 // No suitable cells were found on any free list. 00597 // 00598 // Either there is no large enough cell, or we 00599 // have no free cells left at all. In either case, allocate a 00600 // new bin, with a new free cell certain to be large enough in 00601 // it, and use that cell. 00602 // 00603 00604 // 00605 // Attempt to create a new bin 00606 // 00607 if ((Bin = HvpAddBin(Hive, NewSize, Type)) != NULL) { 00608 00609 // 00610 // It worked. Use single large cell in Bin. 00611 // 00612 DHvCheckBin(Hive,Bin); 00613 cell = (Bin->FileOffset) + sizeof(HBIN) + (Type*HCELL_TYPE_MASK); 00614 pcell = HvpGetHCell(Hive, cell); 00615 } else { 00616 return HCELL_NIL; 00617 } 00618 } 00619 00620 UseIt: 00621 00622 // 00623 // cell refers to a free cell we have pulled from its list 00624 // if it is too big, give the residue back 00625 // ("too big" means there is at least one HCELL of extra space) 00626 // always mark it allocated 00627 // return it as our function value 00628 // 00629 00630 ASSERT(pcell->Size > 0); 00631 if (USE_OLD_CELL(Hive)) { 00632 MinFreeSize = FIELD_OFFSET(HCELL, u.OldCell.u.Next) + sizeof(HCELL_INDEX); 00633 } else { 00634 MinFreeSize = FIELD_OFFSET(HCELL, u.NewCell.u.Next) + sizeof(HCELL_INDEX); 00635 } 00636 if ((NewSize + MinFreeSize) < (ULONG)pcell->Size) { 00637 00638 // 00639 // Crack the cell, use part we need, put rest on 00640 // free list. 00641 // 00642 Me = HvpGetCellMap(Hive, cell); 00643 VALIDATE_CELL_MAP(__LINE__,Me,Hive,cell); 00644 Bin = (PHBIN)((Me->BinAddress) & HMAP_BASE); 00645 offset = (ULONG)((ULONG_PTR)pcell - (ULONG_PTR)Bin); 00646 00647 ptcell = (PHCELL)((PUCHAR)pcell + NewSize); 00648 if (USE_OLD_CELL(Hive)) { 00649 ptcell->u.OldCell.Last = offset; 00650 } 00651 ptcell->Size = pcell->Size - NewSize; 00652 00653 if ((offset + pcell->Size) < Bin->Size) { 00654 next = (PHCELL)((PUCHAR)pcell + pcell->Size); 00655 if (USE_OLD_CELL(Hive)) { 00656 next->u.OldCell.Last = offset + NewSize; 00657 } 00658 } 00659 00660 pcell->Size = NewSize; 00661 tcell = (HCELL_INDEX)((ULONG)cell + NewSize); 00662 00663 HvpEnlistFreeCell(Hive, tcell, ptcell->Size, Type, TRUE,NULL); 00664 } 00665 00666 // 00667 // return the cell we found. 00668 // 00669 #if DBG 00670 if (USE_OLD_CELL(Hive)) { 00671 RtlFillMemory( 00672 &(pcell->u.OldCell.u.UserData), 00673 (pcell->Size - FIELD_OFFSET(HCELL, u.OldCell.u.UserData)), 00674 HCELL_ALLOCATE_FILL 00675 ); 00676 } else { 00677 RtlFillMemory( 00678 &(pcell->u.NewCell.u.UserData), 00679 (pcell->Size - FIELD_OFFSET(HCELL, u.NewCell.u.UserData)), 00680 HCELL_ALLOCATE_FILL 00681 ); 00682 } 00683 #endif 00684 pcell->Size *= -1; 00685 00686 return cell; 00687 } 00688 00689 00690 00691 00692 VOID 00693 HvFreeCell( 00694 PHHIVE Hive, 00695 HCELL_INDEX Cell 00696 ) 00697 /*++ 00698 00699 Routine Description: 00700 00701 00702 Frees the storage for a cell. 00703 00704 NOTE: CALLER is expected to mark relevent data dirty, so as to 00705 allow this call to always succeed. 00706 00707 Arguments: 00708 00709 Hive - supplies a pointer to the hive control structure for the 00710 hive of interest 00711 00712 Cell - HCELL_INDEX of Cell to free. 00713 00714 Return Value: 00715 00716 FALSE - failed, presumably for want of log space. 00717 00718 TRUE - it worked 00719 00720 --*/ 00721 { 00722 PHBIN Bin; 00723 PHCELL tmp; 00724 HCELL_INDEX newfreecell; 00725 PHCELL freebase; 00726 ULONG savesize; 00727 PHCELL neighbor; 00728 ULONG Type; 00729 PHMAP_ENTRY Me; 00730 00731 00732 CMLOG(CML_MINOR, CMS_HIVE) { 00733 KdPrint(("HvFreeCell:\n")); 00734 KdPrint(("\tHive=%08lx Cell=%08lx\n",Hive,Cell)); 00735 } 00736 ASSERT(Hive->ReadOnly == FALSE); 00737 ASSERT_CM_LOCK_OWNED_EXCLUSIVE(); 00738 00739 // 00740 // Get sizes and addresses 00741 // 00742 Me = HvpGetCellMap(Hive, Cell); 00743 VALIDATE_CELL_MAP(__LINE__,Me,Hive,Cell); 00744 Type = HvGetCellType(Cell); 00745 00746 Bin = (PHBIN)((Me->BinAddress) & HMAP_BASE); 00747 DHvCheckBin(Hive,Bin); 00748 00749 freebase = HvpGetHCell(Hive, Cell); 00750 00751 // 00752 // go do actual frees, cannot fail from this point on 00753 // 00754 ASSERT(freebase->Size < 0); 00755 freebase->Size *= -1; 00756 00757 savesize = freebase->Size; 00758 00759 // 00760 // Look for free neighbors and coalesce them. We will never travel 00761 // around this loop more than twice. 00762 // 00763 while ( 00764 HvpIsFreeNeighbor( 00765 Hive, 00766 Bin, 00767 freebase, 00768 &neighbor, 00769 Type 00770 ) == TRUE 00771 ) 00772 { 00773 00774 if (neighbor > freebase) { 00775 00776 // 00777 // Neighboring free cell is immediately above us in memory. 00778 // 00779 if (USE_OLD_CELL(Hive)) { 00780 tmp = (PHCELL)((PUCHAR)neighbor + neighbor->Size); 00781 if ( ((ULONG)((ULONG_PTR)tmp - (ULONG_PTR)Bin)) < Bin->Size) { 00782 tmp->u.OldCell.Last = (ULONG)((ULONG_PTR)freebase - (ULONG_PTR)Bin); 00783 } 00784 } 00785 freebase->Size += neighbor->Size; 00786 00787 } else { 00788 00789 // 00790 // Neighboring free cell is immediately below us in memory. 00791 // 00792 00793 if (USE_OLD_CELL(Hive)) { 00794 tmp = (PHCELL)((PUCHAR)freebase + freebase->Size); 00795 if ( ((ULONG)((ULONG_PTR)tmp - (ULONG_PTR)Bin)) < Bin->Size ) { 00796 tmp->u.OldCell.Last = (ULONG)((ULONG_PTR)neighbor - (ULONG_PTR)Bin); 00797 } 00798 } 00799 neighbor->Size += freebase->Size; 00800 freebase = neighbor; 00801 } 00802 } 00803 00804 // 00805 // freebase now points to the biggest free cell we could make, none 00806 // of which is on the free list. So put it on the list. 00807 // 00808 newfreecell = (Bin->FileOffset) + 00809 ((ULONG)((ULONG_PTR)freebase - (ULONG_PTR)Bin)) + 00810 (Type*HCELL_TYPE_MASK); 00811 00812 ASSERT(HvpGetHCell(Hive, newfreecell) == freebase); 00813 00814 #if DBG 00815 if (USE_OLD_CELL(Hive)) { 00816 RtlFillMemory( 00817 &(freebase->u.OldCell.u.UserData), 00818 (freebase->Size - FIELD_OFFSET(HCELL, u.OldCell.u.UserData)), 00819 HCELL_FREE_FILL 00820 ); 00821 } else { 00822 RtlFillMemory( 00823 &(freebase->u.NewCell.u.UserData), 00824 (freebase->Size - FIELD_OFFSET(HCELL, u.NewCell.u.UserData)), 00825 HCELL_FREE_FILL 00826 ); 00827 } 00828 #endif 00829 00830 HvpEnlistFreeCell(Hive, newfreecell, freebase->Size, Type, TRUE,NULL); 00831 00832 return; 00833 } 00834 00835 00836 BOOLEAN 00837 HvpIsFreeNeighbor( 00838 PHHIVE Hive, 00839 PHBIN Bin, 00840 PHCELL FreeCell, 00841 PHCELL *FreeNeighbor, 00842 HSTORAGE_TYPE Type 00843 ) 00844 /*++ 00845 00846 Routine Description: 00847 00848 Reports on whether FreeCell has at least one free neighbor and 00849 if so where. Free neighbor will be cut out of the free list. 00850 00851 Arguments: 00852 00853 Hive - hive we're working on 00854 00855 Bin - pointer to the storage bin 00856 00857 FreeCell - supplies a pointer to a cell that has been freed, or 00858 the result of a coalesce. 00859 00860 FreeNeighbor - supplies a pointer to a variable to receive the address 00861 of a free neigbhor of FreeCell, if such exists 00862 00863 Type - storage type of the cell 00864 00865 Return Value: 00866 00867 TRUE if a free neighbor was found, else false. 00868 00869 00870 --*/ 00871 { 00872 PHCELL ptcell; 00873 00874 CMLOG(CML_MINOR, CMS_HIVE) { 00875 KdPrint(("HvpIsFreeNeighbor:\n\tBin=%08lx",Bin)); 00876 KdPrint(("FreeCell=%08lx\n", FreeCell)); 00877 } 00878 ASSERT(Hive->ReadOnly == FALSE); 00879 00880 // 00881 // Neighbor above us? 00882 // 00883 *FreeNeighbor = NULL; 00884 ptcell = (PHCELL)((PUCHAR)FreeCell + FreeCell->Size); 00885 ASSERT( ((ULONG)((ULONG_PTR)ptcell - (ULONG_PTR)Bin)) <= Bin->Size); 00886 if (((ULONG)((ULONG_PTR)ptcell - (ULONG_PTR)Bin)) < Bin->Size) { 00887 if (ptcell->Size > 0) { 00888 *FreeNeighbor = ptcell; 00889 goto FoundNeighbor; 00890 } 00891 } 00892 00893 // 00894 // Neighbor below us? 00895 // 00896 if (USE_OLD_CELL(Hive)) { 00897 if (FreeCell->u.OldCell.Last != HBIN_NIL) { 00898 ptcell = (PHCELL)((PUCHAR)Bin + FreeCell->u.OldCell.Last); 00899 if (ptcell->Size > 0) { 00900 *FreeNeighbor = ptcell; 00901 goto FoundNeighbor; 00902 } 00903 } 00904 } else { 00905 ptcell = (PHCELL)(Bin+1); 00906 while (ptcell < FreeCell) { 00907 00908 // 00909 // scan through the cells from the start of the bin looking for neighbor. 00910 // 00911 if (ptcell->Size > 0) { 00912 00913 if ((PHCELL)((PUCHAR)ptcell + ptcell->Size) == FreeCell) { 00914 *FreeNeighbor = ptcell; 00915 // 00916 // Try and mark it dirty, since we will be changing 00917 // the size field. If this fails, ignore 00918 // the free neighbor, we will not fail the free 00919 // just because we couldn't mark the cell dirty 00920 // so it could be coalesced. 00921 // 00922 // Note we only bother doing this for new hives, 00923 // for old format hives we always mark the whole 00924 // bin dirty. 00925 // 00926 if ((Type == Volatile) || 00927 (HvMarkCellDirty(Hive, (ULONG)((ULONG_PTR)ptcell-(ULONG_PTR)Bin) + Bin->FileOffset))) { 00928 goto FoundNeighbor; 00929 } else { 00930 return(FALSE); 00931 } 00932 00933 } else { 00934 ptcell = (PHCELL)((PUCHAR)ptcell + ptcell->Size); 00935 } 00936 } else { 00937 ptcell = (PHCELL)((PUCHAR)ptcell - ptcell->Size); 00938 } 00939 } 00940 } 00941 00942 return(FALSE); 00943 00944 FoundNeighbor: 00945 00946 HvpDelistFreeCell(Hive, *FreeNeighbor, Type, NULL); 00947 return TRUE; 00948 } 00949 00950 00951 VOID 00952 HvpEnlistFreeCell( 00953 PHHIVE Hive, 00954 HCELL_INDEX Cell, 00955 ULONG Size, 00956 HSTORAGE_TYPE Type, 00957 BOOLEAN CoalesceForward, 00958 PHCELL_INDEX TailDisplay OPTIONAL 00959 ) 00960 /*++ 00961 00962 Routine Description: 00963 00964 Puts the newly freed cell on the appropriate list. 00965 00966 Arguments: 00967 00968 Hive - supplies a pointer to the hive control structure for the 00969 hive of interest 00970 00971 Cell - supplies index of cell to enlist 00972 00973 Size - size of cell 00974 00975 Type - indicates whether Stable or Volatile storage is desired. 00976 00977 CoalesceForward - indicates whether we can coalesce forward or not. 00978 For the case where we have not finished scanning the hive and 00979 enlisting free cells, we do not want to coalesce forward. 00980 00981 Return Value: 00982 00983 NONE. 00984 00985 --*/ 00986 { 00987 PHCELL_INDEX Last; 00988 PHCELL_INDEX First; 00989 PHMAP_ENTRY Map; 00990 PHCELL pcell; 00991 PHCELL pcellLast; 00992 PHCELL FirstCell; 00993 ULONG Index; 00994 PHBIN Bin; 00995 HCELL_INDEX FreeCell; 00996 PFREE_HBIN FreeBin; 00997 PHBIN FirstBin; 00998 PHBIN LastBin; 00999 01000 HvpComputeIndex(Index, Size); 01001 01002 01003 First = &(Hive->Storage[Type].FreeDisplay[Index]); 01004 pcell = HvpGetHCell(Hive, Cell); 01005 ASSERT(pcell->Size > 0); 01006 ASSERT(Size == (ULONG)pcell->Size); 01007 01008 if (ARGUMENT_PRESENT(TailDisplay)) { 01009 // 01010 // This should only happen once, at boot time; Then, we want to sort the list ascedending 01011 // 01012 Last = &TailDisplay[Index]; 01013 if( *Last != HCELL_NIL ) { 01014 // 01015 // there is a last cell; insert current cell right after it. 01016 // and set the next cell pointer for the current cell to NIL 01017 // 01018 pcellLast = HvpGetHCell(Hive,*Last); 01019 ASSERT(pcellLast->Size > 0); 01020 01021 if (USE_OLD_CELL(Hive)) { 01022 pcellLast->u.OldCell.u.Next = Cell; 01023 pcell->u.OldCell.u.Next = HCELL_NIL; 01024 } else { 01025 pcellLast->u.NewCell.u.Next = Cell; 01026 pcell->u.NewCell.u.Next = HCELL_NIL; 01027 } 01028 } else { 01029 // 01030 // No Last cell; Insert it at the begining and set the last cell pointing to it as well 01031 // Sanity check: First cell should be also NIL 01032 // 01033 ASSERT( *First == HCELL_NIL ); 01034 01035 if (USE_OLD_CELL(Hive)) { 01036 pcell->u.OldCell.u.Next = *First; 01037 } else { 01038 pcell->u.NewCell.u.Next = *First; 01039 } 01040 *First = Cell; 01041 } 01042 // 01043 // The current cell becomes the last cell 01044 // 01045 *Last = Cell; 01046 } else { 01047 // 01048 // Normal case, insert the cell at the begining of the list (speed reasons). 01049 // 01050 if (USE_OLD_CELL(Hive)) { 01051 pcell->u.OldCell.u.Next = *First; 01052 } else { 01053 pcell->u.NewCell.u.Next = *First; 01054 } 01055 *First = Cell; 01056 } 01057 01058 01059 // 01060 // Check to see if this is the first cell in the bin and if the entire 01061 // bin consists just of this cell. 01062 // 01063 Map = HvpGetCellMap(Hive, Cell); 01064 VALIDATE_CELL_MAP(__LINE__,Map,Hive,Cell); 01065 Bin = (PHBIN)(Map->BinAddress & ~HMAP_NEWALLOC); 01066 if ((pcell == (PHCELL)(Bin + 1)) && 01067 (Size == Bin->Size-sizeof(HBIN))) { 01068 01069 // 01070 // We have a bin that is entirely free. But we cannot do anything with it 01071 // unless the memalloc that contains the bin is entirely free. Walk the 01072 // bins backwards until we find the first one in the alloc, then walk forwards 01073 // until we find the last one. If any of the other bins in the memalloc 01074 // are not free, bail out. 01075 // 01076 FirstBin = Bin; 01077 while (FirstBin->MemAlloc == 0) { 01078 Map=HvpGetCellMap(Hive,(FirstBin->FileOffset - HBLOCK_SIZE) + 01079 (Type * HCELL_TYPE_MASK)); 01080 VALIDATE_CELL_MAP(__LINE__,Map,Hive,(FirstBin->FileOffset - HBLOCK_SIZE) +(Type * HCELL_TYPE_MASK)); 01081 FirstBin = (PHBIN)(Map->BinAddress & HMAP_BASE); 01082 FirstCell = (PHCELL)(FirstBin+1); 01083 if ((ULONG)(FirstCell->Size) != FirstBin->Size-sizeof(HBIN)) { 01084 // 01085 // The first cell in the bin is either allocated, or not the only 01086 // cell in the HBIN. We cannot free any HBINs. 01087 // 01088 goto Done; 01089 } 01090 } 01091 01092 // 01093 // We can never discard the first bin of a hive as that always gets marked dirty 01094 // and written out. 01095 // 01096 if (FirstBin->FileOffset == 0) { 01097 goto Done; 01098 } 01099 01100 LastBin = Bin; 01101 while (LastBin->FileOffset+LastBin->Size < FirstBin->FileOffset+FirstBin->MemAlloc) { 01102 if (!CoalesceForward) { 01103 // 01104 // We are at the end of what's been built up. Just return and this 01105 // will get freed up when the next HBIN is added. 01106 // 01107 goto Done; 01108 } 01109 Map = HvpGetCellMap(Hive, (LastBin->FileOffset+LastBin->Size) + 01110 (Type * HCELL_TYPE_MASK)); 01111 VALIDATE_CELL_MAP(__LINE__,Map,Hive,(LastBin->FileOffset+LastBin->Size) + (Type * HCELL_TYPE_MASK)); 01112 01113 ASSERT(Map->BinAddress != 0); 01114 01115 LastBin = (PHBIN)(Map->BinAddress & HMAP_BASE); 01116 FirstCell = (PHCELL)(LastBin + 1); 01117 if ((ULONG)(FirstCell->Size) != LastBin->Size-sizeof(HBIN)) { 01118 // 01119 // The first cell in the bin is either allocated, or not the only 01120 // cell in the HBIN. We cannot free any HBINs. 01121 // 01122 goto Done; 01123 } 01124 } 01125 01126 // 01127 // All the bins in this alloc are freed. Coalesce all the bins into 01128 // one alloc-sized bin, then either discard the bin or mark it as 01129 // discardable. 01130 // 01131 if (FirstBin->Size != FirstBin->MemAlloc) { 01132 // 01133 // Mark the first HBLOCK of the first HBIN dirty, since 01134 // we will need to update the on disk field for the bin size 01135 // 01136 if (!HvMarkDirty(Hive, 01137 FirstBin->FileOffset + (Type * HCELL_TYPE_MASK), 01138 sizeof(HBIN) + sizeof(HCELL))) { 01139 goto Done; 01140 } 01141 01142 } 01143 01144 01145 FreeBin = (Hive->Allocate)(sizeof(FREE_HBIN), FALSE); 01146 if (FreeBin == NULL) { 01147 goto Done; 01148 } 01149 01150 // 01151 // Walk through the bins and delist each free cell 01152 // 01153 Bin = FirstBin; 01154 do { 01155 FirstCell = (PHCELL)(Bin+1); 01156 HvpDelistFreeCell(Hive, FirstCell, Type, TailDisplay); 01157 if (Bin==LastBin) { 01158 break; 01159 } 01160 Map = HvpGetCellMap(Hive, (Bin->FileOffset+Bin->Size)+ 01161 (Type * HCELL_TYPE_MASK)); 01162 VALIDATE_CELL_MAP(__LINE__,Map,Hive,(Bin->FileOffset+Bin->Size)+(Type * HCELL_TYPE_MASK)); 01163 Bin = (PHBIN)(Map->BinAddress & HMAP_BASE); 01164 01165 } while ( TRUE ); 01166 01167 // 01168 // Coalesce them all into one bin. 01169 // 01170 FirstBin->Size = FirstBin->MemAlloc; 01171 01172 FreeBin->Size = FirstBin->Size; 01173 FreeBin->FileOffset = FirstBin->FileOffset; 01174 FirstCell = (PHCELL)(FirstBin+1); 01175 FirstCell->Size = FirstBin->Size - sizeof(HBIN); 01176 if (USE_OLD_CELL(Hive)) { 01177 FirstCell->u.OldCell.Last = (ULONG)HBIN_NIL; 01178 } 01179 01180 InsertHeadList(&Hive->Storage[Type].FreeBins, &FreeBin->ListEntry); 01181 ASSERT_LISTENTRY(&FreeBin->ListEntry); 01182 ASSERT_LISTENTRY(FreeBin->ListEntry.Flink); 01183 01184 FreeCell = FirstBin->FileOffset+(Type*HCELL_TYPE_MASK); 01185 FreeBin->Flags = FREE_HBIN_DISCARDABLE; 01186 while (FreeCell-FirstBin->FileOffset < FirstBin->Size) { 01187 Map = HvpGetCellMap(Hive, FreeCell); 01188 VALIDATE_CELL_MAP(__LINE__,Map,Hive,FreeCell); 01189 if (Map->BinAddress & HMAP_NEWALLOC) { 01190 Map->BinAddress = (ULONG_PTR)FirstBin | HMAP_DISCARDABLE | HMAP_NEWALLOC; 01191 } else { 01192 Map->BinAddress = (ULONG_PTR)FirstBin | HMAP_DISCARDABLE; 01193 } 01194 Map->BlockAddress = (ULONG_PTR)FreeBin; 01195 FreeCell += HBLOCK_SIZE; 01196 } 01197 } 01198 01199 01200 Done: 01201 Hive->Storage[Type].FreeSummary |= (1 << Index); 01202 return; 01203 } 01204 01205 01206 01207 VOID 01208 HvpDelistFreeCell( 01209 PHHIVE Hive, 01210 PHCELL Pcell, 01211 HSTORAGE_TYPE Type, 01212 PHCELL_INDEX TailDisplay OPTIONAL 01213 ) 01214 /*++ 01215 01216 Routine Description: 01217 01218 Removes a free cell from its list, and clears the Summary 01219 bit for it if need be. 01220 01221 Arguments: 01222 01223 Hive - supplies a pointer to the hive control structure for the 01224 hive of interest 01225 01226 Pcell - supplies a pointer to the HCELL structure of interest 01227 01228 Type - Stable vs. Volatile 01229 01230 Return Value: 01231 01232 NONE. 01233 01234 --*/ 01235 { 01236 PHCELL_INDEX List; 01237 HCELL_INDEX Prev = HCELL_NIL; 01238 ULONG Index; 01239 01240 HvpComputeIndex(Index, Pcell->Size); 01241 List = &(Hive->Storage[Type].FreeDisplay[Index]); 01242 01243 // 01244 // Find previous cell on list 01245 // 01246 ASSERT(*List != HCELL_NIL); 01247 while (HvpGetHCell(Hive,*List) != Pcell) { 01248 Prev = *List; 01249 List = (PHCELL_INDEX)HvGetCell(Hive,*List); 01250 ASSERT(*List != HCELL_NIL); 01251 } 01252 01253 if (ARGUMENT_PRESENT(TailDisplay)) { 01254 // 01255 // This should only happen once, at boot time; Then, we want to sort the list ascedending 01256 // 01257 if( *List == TailDisplay[Index] ) { 01258 // 01259 // this cell is also the last cell on list; so it should be reset 01260 // 01261 01262 #if DBG 01263 // 01264 // consistency checks 01265 // 01266 if (USE_OLD_CELL(Hive)) { 01267 ASSERT(Pcell->u.OldCell.u.Next == HCELL_NIL); 01268 } else { 01269 ASSERT(Pcell->u.NewCell.u.Next == HCELL_NIL); 01270 } 01271 #endif 01272 01273 TailDisplay[Index] = Prev; 01274 } 01275 } 01276 01277 // 01278 // Remove Pcell from list. 01279 // 01280 if (USE_OLD_CELL(Hive)) { 01281 *List = Pcell->u.OldCell.u.Next; 01282 } else { 01283 *List = Pcell->u.NewCell.u.Next; 01284 } 01285 01286 if (Hive->Storage[Type].FreeDisplay[Index] == HCELL_NIL) { 01287 // 01288 // consistency check 01289 // 01290 ASSERT(Prev == HCELL_NIL); 01291 01292 Hive->Storage[Type].FreeSummary &= ~(1 << Index); 01293 } 01294 01295 return; 01296 } 01297 01298 01299 HCELL_INDEX 01300 HvReallocateCell( 01301 PHHIVE Hive, 01302 HCELL_INDEX Cell, 01303 ULONG NewSize 01304 ) 01305 /*++ 01306 01307 Routine Description: 01308 01309 Grows or shrinks a cell. 01310 01311 NOTE: 01312 01313 MUST NOT FAIL if the cell is being made smaller. Can be 01314 a noop, but must work. 01315 01316 WARNING: 01317 01318 If the cell is grown, it will get a NEW and DIFFERENT HCELL_INDEX!!! 01319 01320 Arguments: 01321 01322 Hive - supplies a pointer to the hive control structure for the 01323 hive of interest 01324 01325 Cell - supplies index of cell to grow or shrink 01326 01327 NewSize - desired size of cell (this is an absolute size, not an 01328 increment or decrement.) 01329 01330 Return Value: 01331 01332 New HCELL_INDEX for cell, or HCELL_NIL if failure. 01333 01334 If return is HCELL_NIL, either old cell did not exist, or it did exist 01335 and we could not make a new one. In either case, nothing has changed. 01336 01337 If return is NOT HCELL_NIL, then it is the HCELL_INDEX for the Cell, 01338 which very probably moved. 01339 01340 --*/ 01341 { 01342 PUCHAR oldaddress; 01343 LONG oldsize; 01344 ULONG oldalloc; 01345 HCELL_INDEX NewCell; // return value 01346 PUCHAR newaddress; 01347 ULONG Type; 01348 01349 CMLOG(CML_MAJOR, CMS_HIVE) { 01350 KdPrint(("HvReallocateCell:\n")); 01351 KdPrint(("\tHive=%08lx Cell=%08lx NewSize=%08lx\n",Hive,Cell,NewSize)); 01352 } 01353 ASSERT(Hive->Signature == HHIVE_SIGNATURE); 01354 ASSERT(Hive->ReadOnly == FALSE); 01355 ASSERT_CM_LOCK_OWNED_EXCLUSIVE(); 01356 01357 // 01358 // Make room for overhead fields and round up to HCELL_PAD boundary 01359 // 01360 if (USE_OLD_CELL(Hive)) { 01361 NewSize += FIELD_OFFSET(HCELL, u.OldCell.u.UserData); 01362 } else { 01363 NewSize += FIELD_OFFSET(HCELL, u.NewCell.u.UserData); 01364 } 01365 NewSize = ROUND_UP(NewSize, HCELL_PAD(Hive)); 01366 01367 // 01368 // Adjust the size (an easy fix for granularity) 01369 // 01370 HvpAdjustCellSize(NewSize); 01371 01372 // 01373 // reject impossible/unreasonable values 01374 // 01375 if (NewSize > HSANE_CELL_MAX) { 01376 CMLOG(CML_FLOW, CMS_HIVE) { 01377 KdPrint(("\tNewSize=%08lx\n", NewSize)); 01378 } 01379 return HCELL_NIL; 01380 } 01381 01382 // 01383 // Get sizes and addresses 01384 // 01385 oldaddress = (PUCHAR)HvGetCell(Hive, Cell); 01386 oldsize = HvGetCellSize(Hive, oldaddress); 01387 ASSERT(oldsize > 0); 01388 if (USE_OLD_CELL(Hive)) { 01389 oldalloc = (ULONG)(oldsize + FIELD_OFFSET(HCELL, u.OldCell.u.UserData)); 01390 } else { 01391 oldalloc = (ULONG)(oldsize + FIELD_OFFSET(HCELL, u.NewCell.u.UserData)); 01392 } 01393 Type = HvGetCellType(Cell); 01394 01395 DHvCheckHive(Hive); 01396 01397 if (NewSize == oldalloc) { 01398 01399 // 01400 // This is a noop, return the same cell 01401 // 01402 NewCell = Cell; 01403 01404 } else if (NewSize < oldalloc) { 01405 01406 // 01407 // This is a shrink. 01408 // 01409 // PERFNOTE - IMPLEMENT THIS. Do nothing for now. 01410 // 01411 NewCell = Cell; 01412 01413 } else { 01414 01415 // 01416 // This is a grow. 01417 // 01418 01419 // 01420 // PERFNOTE - Someday we want to detect that there is a free neighbor 01421 // above us and grow into that neighbor if possible. 01422 // For now, always do the allocate, copy, free gig. 01423 // 01424 01425 // 01426 // Allocate a new block of memory to hold the cell 01427 // 01428 01429 if ((NewCell = HvpDoAllocateCell(Hive, NewSize, Type)) == HCELL_NIL) { 01430 return HCELL_NIL; 01431 } 01432 ASSERT(HvIsCellAllocated(Hive, NewCell)); 01433 newaddress = (PUCHAR)HvGetCell(Hive, NewCell); 01434 01435 // 01436 // oldaddress points to the old data block for the cell, 01437 // newaddress points to the new data block, copy the data 01438 // 01439 RtlMoveMemory(newaddress, oldaddress, oldsize); 01440 01441 // 01442 // Free the old block of memory 01443 // 01444 HvFreeCell(Hive, Cell); 01445 } 01446 01447 DHvCheckHive(Hive); 01448 return NewCell; 01449 } 01450 01451 01452 01453 // 01454 // Procedure used for checking only (used in production systems, so 01455 // must always be here.) 01456 // 01457 BOOLEAN 01458 HvIsCellAllocated( 01459 PHHIVE Hive, 01460 HCELL_INDEX Cell 01461 ) 01462 /*++ 01463 01464 Routine Description: 01465 01466 Report whether the requested cell is allocated or not. 01467 01468 Arguments: 01469 01470 Hive - containing Hive. 01471 01472 Cell - cel of interest 01473 01474 Return Value: 01475 01476 TRUE if allocated, FALSE if not. 01477 01478 --*/ 01479 { 01480 ULONG Type; 01481 PHCELL Address; 01482 PHCELL Below; 01483 PHMAP_ENTRY Me; 01484 PHBIN Bin; 01485 ULONG Offset; 01486 LONG Size; 01487 01488 01489 ASSERT(Hive->Signature == HHIVE_SIGNATURE); 01490 01491 if (Hive->Flat == TRUE) { 01492 return TRUE; 01493 } 01494 01495 Type = HvGetCellType(Cell); 01496 01497 if ( ((Cell & ~HCELL_TYPE_MASK) > Hive->Storage[Type].Length) || // off end 01498 (Cell % HCELL_PAD(Hive) != 0) // wrong alignment 01499 ) 01500 { 01501 return FALSE; 01502 } 01503 01504 Address = HvpGetHCell(Hive, Cell); 01505 Me = HvpGetCellMap(Hive, Cell); 01506 if (Me == NULL) { 01507 return FALSE; 01508 } 01509 Bin = (PHBIN)((ULONG_PTR)(Me->BinAddress) & HMAP_BASE); 01510 Offset = (ULONG)((ULONG_PTR)Address - (ULONG_PTR)Bin); 01511 Size = Address->Size * -1; 01512 01513 if ( (Address->Size > 0) || // not allocated 01514 ((Offset + (ULONG)Size) > Bin->Size) || // runs off bin, or too big 01515 (Offset < sizeof(HBIN)) // pts into bin header 01516 ) 01517 { 01518 return FALSE; 01519 } 01520 01521 if (USE_OLD_CELL(Hive)) { 01522 if (Address->u.OldCell.Last != HBIN_NIL) { 01523 01524 if (Address->u.OldCell.Last > Bin->Size) { // bogus back pointer 01525 return FALSE; 01526 } 01527 01528 Below = (PHCELL)((PUCHAR)Bin + Address->u.OldCell.Last); 01529 Size = (Below->Size < 0) ? 01530 Below->Size * -1 : 01531 Below->Size; 01532 01533 if ( ((ULONG_PTR)Below + Size) != (ULONG_PTR)Address ) { // no pt back 01534 return FALSE; 01535 } 01536 } 01537 } 01538 01539 01540 return TRUE; 01541 } 01542 01543 VOID 01544 HvpDelistBinFreeCells( 01545 PHHIVE Hive, 01546 PHBIN Bin, 01547 HSTORAGE_TYPE Type, 01548 PHCELL_INDEX TailDisplay OPTIONAL 01549 ) 01550 /*++ 01551 01552 Routine Description: 01553 01554 If we are here, the hive needs recovery. 01555 01556 Walks through the entire bin and removes its free cells from the list. 01557 If the bin is marked as free, it just delist it from the freebins list. 01558 01559 Arguments: 01560 01561 Hive - supplies a pointer to the hive control structure for the 01562 hive of interest 01563 01564 Bin - supplies a pointer to the HBIN of interest 01565 01566 Type - Stable vs. Volatile 01567 01568 Return Value: 01569 01570 NONE. 01571 01572 --*/ 01573 { 01574 PHCELL p; 01575 ULONG size; 01576 HCELL_INDEX Cell; 01577 PHMAP_ENTRY Map; 01578 PFREE_HBIN FreeBin; 01579 PLIST_ENTRY Entry; 01580 01581 Cell = Bin->FileOffset+(Type*HCELL_TYPE_MASK); 01582 Map = HvpGetCellMap(Hive, Cell); 01583 VALIDATE_CELL_MAP(__LINE__,Map,Hive,Cell); 01584 01585 // 01586 // When loading, bins are always in separate chunks (each bin in it's owns chunk) 01587 // 01588 ASSERT( Map->BinAddress == ((ULONG_PTR)Bin | HMAP_NEWALLOC) ); 01589 01590 if( Map->BinAddress & HMAP_DISCARDABLE ) { 01591 // 01592 // The bin has been added to the freebins list 01593 // we have to take it out. No free cell from this bin is on the 01594 // freecells list, so we don't have to delist them. 01595 // 01596 01597 Entry = Hive->Storage[Type].FreeBins.Flink; 01598 while (Entry != &Hive->Storage[Type].FreeBins) { 01599 FreeBin = CONTAINING_RECORD(Entry, 01600 FREE_HBIN, 01601 ListEntry); 01602 01603 01604 if( FreeBin->FileOffset == Bin->FileOffset ){ 01605 // 01606 // that's the bin we're looking for 01607 // 01608 01609 // sanity checks 01610 ASSERT( FreeBin->Size == Bin->Size ); 01611 ASSERT_LISTENTRY(&FreeBin->ListEntry); 01612 01613 RemoveEntryList(&FreeBin->ListEntry); 01614 (Hive->Free)(FreeBin, sizeof(FREE_HBIN)); 01615 return; 01616 } 01617 01618 // advance to the new bin 01619 Entry = Entry->Flink; 01620 } 01621 01622 // we shouldn't get here 01623 CM_BUGCHECK(REGISTRY_ERROR,14,(ULONG)Cell,(ULONG_PTR)Map,0); 01624 return; 01625 } 01626 01627 // 01628 // Scan all the cells in the bin, total free and allocated, check 01629 // for impossible pointers. 01630 // 01631 p = (PHCELL)((PUCHAR)Bin + sizeof(HBIN)); 01632 01633 while (p < (PHCELL)((PUCHAR)Bin + Bin->Size)) { 01634 01635 // 01636 // if free cell, remove it from the list of the hive 01637 // 01638 if (p->Size >= 0) { 01639 01640 size = (ULONG)p->Size; 01641 01642 // 01643 // Enlist this free cell, but do not coalesce with the next free cell 01644 // as we haven't gotten that far yet. 01645 // 01646 HvpDelistFreeCell(Hive, p, Type, TailDisplay); 01647 01648 } else { 01649 01650 size = (ULONG)(p->Size * -1); 01651 01652 } 01653 01654 ASSERT(size >= 0); 01655 p = (PHCELL)((PUCHAR)p + size); 01656 } 01657 01658 return; 01659 }

Generated on Sat May 15 19:40:17 2004 for test by doxygen 1.3.7