test: hivecell.c Source File

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 }