test: hivebin.c Source File

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

# hivebin.c

Go to the documentation of this file.

    00001 /*++
    00002
    00003 Copyright (c) 1991  Microsoft Corporation
    00004
    00005 Module Name:
    00006
    00007     hivebin.c
    00008
    00009 Abstract:
    00010
    00011     This module implements HvpAddBin - used to grow a hive.
    00012
    00013 Author:
    00014
    00015     Bryan M. Willman (bryanwi) 27-Mar-92
    00016
    00017 Environment:
    00018
    00019
    00020 Revision History:
    00021
    00022 --*/
    00023
    00024 #include    "cmp.h"
    00025
    00026 //
    00027 // Private function prototypes
    00028 //
    00029 BOOLEAN
    00030 HvpCoalesceDiscardedBins(
    00031     IN PHHIVE Hive,
    00032     IN ULONG NeededSize,
    00033     IN HSTORAGE_TYPE Type
    00034     );
    00035
    00036 #ifdef ALLOC_PRAGMA
    00037 #pragma alloc_text(PAGE,HvpAddBin)
    00038 #pragma alloc_text(PAGE,HvpFreeMap)
    00039 #pragma alloc_text(PAGE,HvpAllocateMap)
    00040 #pragma alloc_text(PAGE,HvpCoalesceDiscardedBins)
    00041 #endif
    00042
    00043
    00044
    00045 PHBIN
    00046 HvpAddBin(
    00047     IN PHHIVE  Hive,
    00048     IN ULONG   NewSize,
    00049     IN HSTORAGE_TYPE   Type
    00050     )
    00051 /*++
    00052
    00053 Routine Description:
    00054
    00055     Grows either the Stable or Volatile storage of a hive by adding
    00056     a new bin.  Bin will be allocated space in Stable store (e.g. file)
    00057     if Type == Stable.  Memory image will be allocated and initialized.
    00058     Map will be grown and filled in to describe the new bin.
    00059
    00060 Arguments:
    00061
    00062     Hive - supplies a pointer to the hive control structure for the
    00063             hive of interest
    00064
    00065     NewSize - size of the object caller wishes to put in the hive.  New
    00066                 bin will be at least large enough to hold this.
    00067
    00068     Type - Stable or Volatile
    00069
    00070 Return Value:
    00071
    00072     Pointer to the new BIN if we succeeded, NULL if we failed.
    00073
    00074 --*/
    00075 {
    00076     BOOLEAN         UseForIo;
    00077     PHBIN           NewBin;
    00078     ULONG           OldLength;
    00079     ULONG           NewLength;
    00080     ULONG           OldMap;
    00081     ULONG           NewMap;
    00082     ULONG           OldTable;
    00083     ULONG           NewTable;
    00084     PHMAP_DIRECTORY Dir;
    00085     PHMAP_TABLE     newt;
    00086     PHMAP_ENTRY     Me;
    00087     PHCELL          t;
    00088     ULONG           i;
    00089     ULONG           j;
    00090     PULONG          NewVector;
    00091     PLIST_ENTRY     Entry;
    00092     PFREE_HBIN      FreeBin;
    00093     ULONG           TotalDiscardedSize;
    00094
    00095
    00096     CMLOG(CML_FLOW, CMS_HIVE) {
    00097         KdPrint(("HvpAddBin:\n"));
    00098         KdPrint(("\tHive=%08lx NewSize=%08lx\n",Hive,NewSize));
    00099     }
    00100
    00101     //
    00102     //  Round size up to account for bin overhead.  Caller should
    00103     //  have accounted for cell overhead.
    00104     //
    00105     NewSize += sizeof(HBIN);
    00106     if ((NewSize < HCELL_BIG_ROUND) &&
    00107         ((NewSize % HBLOCK_SIZE) > HBIN_THRESHOLD)) {
    00108         NewSize += HBLOCK_SIZE;
    00109     }
    00110
    00111     //
    00112     // Try not to create HBINs smaller than the page size of the machine
    00113     //  (it is not illegal to have bins smaller than the page size, but it
    00114     //  is less efficient)
    00115     //
    00116     NewSize = ROUND_UP(NewSize, ((HBLOCK_SIZE >= PAGE_SIZE) ? HBLOCK_SIZE : PAGE_SIZE));
    00117
    00118     //
    00119     // see if there's a discarded HBIN of the right size
    00120     //
    00121     TotalDiscardedSize = 0;
    00122
    00123 Retry:
    00124
    00125     Entry = Hive->Storage[Type].FreeBins.Flink;
    00126     while (Entry != &Hive->Storage[Type].FreeBins) {
    00127         FreeBin = CONTAINING_RECORD(Entry,
    00128                                     FREE_HBIN,
    00129                                     ListEntry);
    00130         TotalDiscardedSize += FreeBin->Size;
    00131         if (FreeBin->Size >= NewSize) {
    00132
    00133             if (!HvMarkDirty(Hive,
    00134                              FreeBin->FileOffset + (Type * HCELL_TYPE_MASK),
    00135                              FreeBin->Size)) {
    00136                 goto ErrorExit1;
    00137             }
    00138             NewSize = FreeBin->Size;
    00139             ASSERT_LISTENTRY(&FreeBin->ListEntry);
    00140             RemoveEntryList(&FreeBin->ListEntry);
    00141             if (FreeBin->Flags & FREE_HBIN_DISCARDABLE) {
    00142                 //
    00143                 // HBIN is still in memory, don't need any more allocs, just
    00144                 // fill in the block addresses.
    00145                 //
    00146                 for (i=0;i<NewSize;i+=HBLOCK_SIZE) {
    00147                     Me = HvpGetCellMap(Hive, FreeBin->FileOffset+i+(Type*HCELL_TYPE_MASK));
    00148                     VALIDATE_CELL_MAP(__LINE__,Me,Hive,FreeBin->FileOffset+i+(Type*HCELL_TYPE_MASK));
    00149                     Me->BlockAddress = (Me->BinAddress & HMAP_BASE)+i;
    00150                     Me->BinAddress &= ~HMAP_DISCARDABLE;
    00151                 }
    00152                 (Hive->Free)(FreeBin, sizeof(FREE_HBIN));
    00153                 return((PHBIN)(Me->BinAddress & HMAP_BASE));
    00154             }
    00155             break;
    00156         }
    00157         Entry = Entry->Flink;
    00158     }
    00159
    00160     if ((Entry == &Hive->Storage[Type].FreeBins) &&
    00161         (TotalDiscardedSize >= NewSize)) {
    00162         //
    00163         // No sufficiently large discarded bin was found,
    00164         // but the total discarded space is large enough.
    00165         // Attempt to coalesce adjacent discarded bins into
    00166         // a larger bin and retry.
    00167         //
    00168         if (HvpCoalesceDiscardedBins(Hive, NewSize, Type)) {
    00169             goto Retry;
    00170         }
    00171     }
    00172
    00173     //
    00174     //  Attempt to allocate the bin.
    00175     //
    00176     UseForIo = (BOOLEAN)((Type == Stable) ? TRUE : FALSE);
    00177     if (Entry != &Hive->Storage[Type].FreeBins) {
    00178         //
    00179         // Note we use ExAllocatePool directly here to avoid
    00180         // charging quota for this bin again. When a bin
    00181         // is discarded, its quota is not returned. This prevents
    00182         // sparse hives from requiring more quota after
    00183         // a reboot than on a running system.
    00184         //
    00185         NewBin = ExAllocatePoolWithTag((UseForIo) ? PagedPoolCacheAligned : PagedPool,
    00186                                        NewSize,
    00187                                        CM_POOL_TAG);
    00188         if (NewBin == NULL) {
    00189             InsertHeadList(&Hive->Storage[Type].FreeBins, Entry);
    00190             HvMarkClean(Hive, FreeBin->FileOffset, FreeBin->Size);
    00191             goto ErrorExit1;
    00192         }
    00193     } else {
    00194         NewBin = (Hive->Allocate)(NewSize, UseForIo);
    00195         if (NewBin == NULL) {
    00196             goto ErrorExit1;
    00197         }
    00198     }
    00199
    00200     //
    00201     // Init the bin
    00202     //
    00203     NewBin->Signature = HBIN_SIGNATURE;
    00204     NewBin->Size = NewSize;
    00205     NewBin->MemAlloc = NewSize;
    00206
    00207     t = (PHCELL)((PUCHAR)NewBin + sizeof(HBIN));
    00208     t->Size = NewSize - sizeof(HBIN);
    00209     if (USE_OLD_CELL(Hive)) {
    00210         t->u.OldCell.Last = (ULONG)HBIN_NIL;
    00211     }
    00212
    00213     if (Entry != &Hive->Storage[Type].FreeBins) {
    00214         //
    00215         // found a discarded HBIN we can use, just fill in the map and we
    00216         // are done.
    00217         //
    00218         for (i=0;i<NewSize;i+=HBLOCK_SIZE) {
    00219             Me = HvpGetCellMap(Hive, FreeBin->FileOffset+i+(Type*HCELL_TYPE_MASK));
    00220             VALIDATE_CELL_MAP(__LINE__,Me,Hive,FreeBin->FileOffset+i+(Type*HCELL_TYPE_MASK));
    00221             Me->BlockAddress = (ULONG_PTR)NewBin + i;
    00222             Me->BinAddress = (ULONG_PTR)NewBin;
    00223             if (i==0) {
    00224                 Me->BinAddress |= HMAP_NEWALLOC;
    00225             }
    00226         }
    00227
    00228         NewBin->FileOffset = FreeBin->FileOffset;
    00229
    00230         (Hive->Free)(FreeBin, sizeof(FREE_HBIN));
    00231
    00232         return(NewBin);
    00233     }
    00234
    00235
    00236     //
    00237     // Compute map growth needed, grow the map
    00238     //
    00239     OldLength = Hive->Storage[Type].Length;
    00240     NewLength = OldLength + NewSize;
    00241
    00242
    00243     NewBin->FileOffset = OldLength;
    00244
    00245     ASSERT((OldLength % HBLOCK_SIZE) == 0);
    00246     ASSERT((NewLength % HBLOCK_SIZE) == 0);
    00247
    00248     if (OldLength == 0) {
    00249         //
    00250         // Need to create the first table
    00251         //
    00252         newt = (PVOID)((Hive->Allocate)(sizeof(HMAP_TABLE), FALSE));
    00253         if (newt == NULL) {
    00254             goto ErrorExit2;
    00255         }
    00256         RtlZeroMemory(newt, sizeof(HMAP_TABLE));
    00257         Hive->Storage[Type].SmallDir = newt;
    00258         Hive->Storage[Type].Map = (PHMAP_DIRECTORY)&(Hive->Storage[Type].SmallDir);
    00259     }
    00260
    00261     if (OldLength > 0) {
    00262         OldMap = (OldLength-1) / HBLOCK_SIZE;
    00263     } else {
    00264         OldMap = 0;
    00265     }
    00266     NewMap = (NewLength-1) / HBLOCK_SIZE;
    00267
    00268     OldTable = OldMap / HTABLE_SLOTS;
    00269     NewTable = NewMap / HTABLE_SLOTS;
    00270
    00271     if (NewTable != OldTable) {
    00272
    00273         //
    00274         // Need some new Tables
    00275         //
    00276         if (OldTable == 0) {
    00277
    00278             //
    00279             // We can get here even if the real directory has already been created.
    00280             // This can happen if we create the directory then fail on something
    00281             // later. So we need to handle the case where a directory already exists.
    00282             //
    00283             if (Hive->Storage[Type].Map == (PHMAP_DIRECTORY)&Hive->Storage[Type].SmallDir) {
    00284                 ASSERT(Hive->Storage[Type].SmallDir != NULL);
    00285
    00286                 //
    00287                 // Need a real directory
    00288                 //
    00289                 Dir = (Hive->Allocate)(sizeof(HMAP_DIRECTORY), FALSE);
    00290                 if (Dir == NULL) {
    00291                     goto ErrorExit2;
    00292                 }
    00293                 RtlZeroMemory(Dir, sizeof(HMAP_DIRECTORY));
    00294
    00295                 Dir->Directory[0] = Hive->Storage[Type].SmallDir;
    00296                 Hive->Storage[Type].SmallDir = NULL;
    00297
    00298                 Hive->Storage[Type].Map = Dir;
    00299             } else {
    00300                 ASSERT(Hive->Storage[Type].SmallDir == NULL);
    00301             }
    00302
    00303         }
    00304         Dir = Hive->Storage[Type].Map;
    00305
    00306         //
    00307         // Fill in directory with new tables
    00308         //
    00309         if (HvpAllocateMap(Hive, Dir, OldTable+1, NewTable) ==  FALSE) {
    00310             goto ErrorExit3;
    00311         }
    00312     }
    00313
    00314     //
    00315     // If Type == Stable, and the hive is not marked WholeHiveVolatile,
    00316     // grow the file, the log, and the DirtyVector
    00317     //
    00318     Hive->Storage[Type].Length = NewLength;
    00319     if ((Type == Stable) && (!(Hive->HiveFlags & HIVE_VOLATILE))) {
    00320
    00321         //
    00322         // Grow the dirtyvector
    00323         //
    00324         NewVector = (PULONG)(Hive->Allocate)(ROUND_UP(NewMap+1,sizeof(ULONG)), TRUE);
    00325         if (NewVector == NULL) {
    00326             goto ErrorExit3;
    00327         }
    00328
    00329         RtlZeroMemory(NewVector, NewMap+1);
    00330
    00331         if (Hive->DirtyVector.Buffer != NULL) {
    00332
    00333             RtlCopyMemory(
    00334                 (PVOID)NewVector,
    00335                 (PVOID)Hive->DirtyVector.Buffer,
    00336                 OldMap+1
    00337                 );
    00338             (Hive->Free)(Hive->DirtyVector.Buffer, Hive->DirtyAlloc);
    00339         }
    00340
    00341         RtlInitializeBitMap(
    00342             &(Hive->DirtyVector),
    00343             NewVector,
    00344             NewLength / HSECTOR_SIZE
    00345             );
    00346         Hive->DirtyAlloc = NewMap+1;
    00347
    00348         //
    00349         // Grow the log
    00350         //
    00351         if ( ! (HvpGrowLog2(Hive, NewSize))) {
    00352             goto ErrorExit4;
    00353         }
    00354
    00355         //
    00356         // Grow the primary
    00357         //
    00358         if ( !  (Hive->FileSetSize)(
    00359                     Hive,
    00360                     HFILE_TYPE_PRIMARY,
    00361                     NewLength+HBLOCK_SIZE
    00362                     ) )
    00363         {
    00364             goto ErrorExit4;
    00365         }
    00366
    00367         //
    00368         // Grow the alternate if it exists
    00369         //
    00370         if (Hive->Alternate == TRUE) {
    00371             if ( ! (Hive->FileSetSize)(
    00372                         Hive,
    00373                         HFILE_TYPE_ALTERNATE,
    00374                         NewLength+HBLOCK_SIZE
    00375                         ) )
    00376             {
    00377                 (Hive->FileSetSize)(
    00378                     Hive,
    00379                     HFILE_TYPE_PRIMARY,
    00380                     OldLength+HBLOCK_SIZE
    00381                     );
    00382                 goto ErrorExit4;
    00383             }
    00384         }
    00385
    00386         //
    00387         // Mark new bin dirty so all control structures get written at next sync
    00388         //
    00389         if ( ! HvMarkDirty(Hive, OldLength, NewSize)) {
    00390             goto ErrorExit4;
    00391         }
    00392     }
    00393
    00394     //
    00395     // Fill in the map, mark new allocation.
    00396     //
    00397     j = 0;
    00398     for (i = OldLength; i < NewLength; i += HBLOCK_SIZE) {
    00399         Me = HvpGetCellMap(Hive, i + (Type*HCELL_TYPE_MASK));
    00400         VALIDATE_CELL_MAP(__LINE__,Me,Hive,i + (Type*HCELL_TYPE_MASK));
    00401         Me->BlockAddress = (ULONG_PTR)NewBin + j;
    00402         Me->BinAddress = (ULONG_PTR)NewBin;
    00403
    00404         if (j == 0) {
    00405             //
    00406             // First block of allocation, mark it.
    00407             //
    00408             Me->BinAddress |= HMAP_NEWALLOC;
    00409         }
    00410         j += HBLOCK_SIZE;
    00411     }
    00412
    00413     return NewBin;
    00414
    00415 ErrorExit4:
    00416     RtlInitializeBitMap(&Hive->DirtyVector,
    00417                         NewVector,
    00418                         OldLength / HSECTOR_SIZE);
    00419     Hive->DirtyCount = RtlNumberOfSetBits(&Hive->DirtyVector);
    00420
    00421 ErrorExit3:
    00422     Hive->Storage[Type].Length = OldLength;
    00423     HvpFreeMap(Hive, Dir, OldTable+1, NewTable);
    00424
    00425 ErrorExit2:
    00426     (Hive->Free)(NewBin, NewSize);
    00427
    00428 ErrorExit1:
    00429     return NULL;
    00430 }
    00431
    00432
    00433 BOOLEAN
    00434 HvpCoalesceDiscardedBins(
    00435     IN PHHIVE Hive,
    00436     IN ULONG NeededSize,
    00437     IN HSTORAGE_TYPE Type
    00438     )
    00439
    00440 /*++
    00441
    00442 Routine Description:
    00443
    00444     Walks through the list of discarded bins and attempts to
    00445     coalesce adjacent discarded bins into one larger bin in
    00446     order to satisfy an allocation request.
    00447
    00448 Arguments:
    00449
    00450     Hive - Supplies pointer to hive control block.
    00451
    00452     NeededSize - Supplies size of allocation needed.
    00453
    00454     Type - Stable or Volatile
    00455
    00456 Return Value:
    00457
    00458     TRUE - A bin of the desired size was created.
    00459
    00460     FALSE - No bin of the desired size could be created.
    00461
    00462 --*/
    00463
    00464 {
    00465     PLIST_ENTRY List;
    00466     PFREE_HBIN FreeBin;
    00467     PFREE_HBIN PreviousFreeBin;
    00468     PFREE_HBIN NextFreeBin;
    00469     PHMAP_ENTRY Map;
    00470     PHMAP_ENTRY PreviousMap;
    00471     PHMAP_ENTRY NextMap;
    00472     ULONG MapBlock;
    00473
    00474     List = Hive->Storage[Type].FreeBins.Flink;
    00475
    00476     while (List != &Hive->Storage[Type].FreeBins) {
    00477         FreeBin = CONTAINING_RECORD(List, FREE_HBIN, ListEntry);
    00478
    00479         if ((FreeBin->Flags & FREE_HBIN_DISCARDABLE)==0) {
    00480
    00481             Map = HvpGetCellMap(Hive, FreeBin->FileOffset);
    00482             VALIDATE_CELL_MAP(__LINE__,Map,Hive,FreeBin->FileOffset);
    00483
    00484             //
    00485             // Scan backwards, coalescing previous discarded bins
    00486             //
    00487             while (FreeBin->FileOffset > 0) {
    00488                 PreviousMap = HvpGetCellMap(Hive, FreeBin->FileOffset - HBLOCK_SIZE);
    00489                 VALIDATE_CELL_MAP(__LINE__,PreviousMap,Hive,FreeBin->FileOffset - HBLOCK_SIZE);
    00490                 if (PreviousMap->BinAddress & HMAP_DISCARDABLE) {
    00491                     PreviousFreeBin = (PFREE_HBIN)PreviousMap->BlockAddress;
    00492
    00493                     if (PreviousFreeBin->Flags & FREE_HBIN_DISCARDABLE) {
    00494                         break;
    00495                     }
    00496                     RemoveEntryList(&PreviousFreeBin->ListEntry);
    00497
    00498                     //
    00499                     // Fill in all the old map entries with the new one.
    00500                     //
    00501                     for (MapBlock = 0; MapBlock < PreviousFreeBin->Size; MapBlock += HBLOCK_SIZE) {
    00502                         PreviousMap = HvpGetCellMap(Hive, PreviousFreeBin->FileOffset + MapBlock);
    00503                         VALIDATE_CELL_MAP(__LINE__,PreviousMap,Hive,PreviousFreeBin->FileOffset + MapBlock);
    00504                         PreviousMap->BlockAddress = (ULONG_PTR)FreeBin;
    00505                     }
    00506
    00507                     FreeBin->FileOffset = PreviousFreeBin->FileOffset;
    00508                     FreeBin->Size += PreviousFreeBin->Size;
    00509                     (Hive->Free)(PreviousFreeBin, sizeof(FREE_HBIN));
    00510                 } else {
    00511                     break;
    00512                 }
    00513             }
    00514
    00515             //
    00516             // Scan forwards, coalescing subsequent discarded bins
    00517             //
    00518             while ((FreeBin->FileOffset + FreeBin->Size) < Hive->BaseBlock->Length) {
    00519                 NextMap = HvpGetCellMap(Hive, FreeBin->FileOffset + FreeBin->Size);
    00520                 VALIDATE_CELL_MAP(__LINE__,NextMap,Hive,FreeBin->FileOffset + FreeBin->Size);
    00521                 if (NextMap->BinAddress & HMAP_DISCARDABLE) {
    00522                     NextFreeBin = (PFREE_HBIN)NextMap->BlockAddress;
    00523
    00524                     if (NextFreeBin->Flags & FREE_HBIN_DISCARDABLE) {
    00525                         break;
    00526                     }
    00527
    00528                     RemoveEntryList(&NextFreeBin->ListEntry);
    00529
    00530                     //
    00531                     // Fill in all the old map entries with the new one.
    00532                     //
    00533                     for (MapBlock = 0; MapBlock < NextFreeBin->Size; MapBlock += HBLOCK_SIZE) {
    00534                         NextMap = HvpGetCellMap(Hive, NextFreeBin->FileOffset + MapBlock);
    00535                         VALIDATE_CELL_MAP(__LINE__,NextMap,Hive,NextFreeBin->FileOffset + MapBlock);
    00536                         NextMap->BlockAddress = (ULONG_PTR)FreeBin;
    00537                     }
    00538
    00539                     FreeBin->Size += NextFreeBin->Size;
    00540                     (Hive->Free)(NextFreeBin, sizeof(FREE_HBIN));
    00541                 } else {
    00542                     break;
    00543                 }
    00544             }
    00545             if (FreeBin->Size >= NeededSize) {
    00546                 return(TRUE);
    00547             }
    00548         }
    00549         List=List->Flink;
    00550     }
    00551     return(FALSE);
    00552 }
    00553
    00554