reactos/lib/cmlib/hivecell.c

   1 /*
   2  * PROJECT:   registry manipulation library
   3  * LICENSE:   GPL - See COPYING in the top level directory
   4  * COPYRIGHT: Copyright 2005 Filip Navara <navaraf@reactos.org>
   5  *            Copyright 2001 - 2005 Eric Kohl
   6  */
   7
   8 #include "cmlib.h"
   9 #define NDEBUG
  10 #include <debug.h>
  11
  12 static PHCELL __inline CMAPI
  13 HvpGetCellHeader(
  14    PHHIVE RegistryHive,
  15    HCELL_INDEX CellIndex)
  16 {
  17    PVOID Block;
  18
  19    CMLTRACE(CMLIB_HCELL_DEBUG, "%s - Hive %p, CellIndex %08lx\n",
  20        __FUNCTION__, RegistryHive, CellIndex);
  21
  22    ASSERT(CellIndex != HCELL_NIL);
  23    if (!RegistryHive->Flat)
  24    {
  25       ULONG CellType;
  26       ULONG CellBlock;
  27       ULONG CellOffset;
  28
  29       CellType = (CellIndex & HCELL_TYPE_MASK) >> HCELL_TYPE_SHIFT;
  30       CellBlock = (CellIndex & HCELL_BLOCK_MASK) >> HCELL_BLOCK_SHIFT;
  31       CellOffset = (CellIndex & HCELL_OFFSET_MASK) >> HCELL_OFFSET_SHIFT;
  32       ASSERT(CellBlock < RegistryHive->Storage[CellType].Length);
  33       Block = (PVOID)RegistryHive->Storage[CellType].BlockList[CellBlock].BlockAddress;
  34       ASSERT(Block != NULL);
  35       return (PVOID)((ULONG_PTR)Block + CellOffset);
  36    }
  37    else
  38    {
  39       ASSERT((CellIndex & HCELL_TYPE_MASK) == Stable);
  40       return (PVOID)((ULONG_PTR)RegistryHive->BaseBlock + HV_BLOCK_SIZE +
  41                      CellIndex);
  42    }
  43 }
  44
  45 BOOLEAN CMAPI
  46 HvIsCellAllocated(IN PHHIVE RegistryHive,
  47                   IN HCELL_INDEX CellIndex)
  48 {
  49    ULONG Type, Block;
  50
  51    /* If it's a flat hive, the cell is always allocated */
  52    if (RegistryHive->Flat)
  53       return TRUE;
  54
  55    /* Otherwise, get the type and make sure it's valid */
  56    Type = HvGetCellType(CellIndex);
  57    Block = HvGetCellBlock(CellIndex);
  58    if (Block >= RegistryHive->Storage[Type].Length)
  59       return FALSE;
  60
  61    /* Try to get the cell block */
  62    if (RegistryHive->Storage[Type].BlockList[Block].BlockAddress)
  63       return TRUE;
  64
  65    /* No valid block, fail */
  66    return FALSE;
  67 }
  68
  69 PVOID CMAPI
  70 HvGetCell(
  71    PHHIVE RegistryHive,
  72    HCELL_INDEX CellIndex)
  73 {
  74    return (PVOID)(HvpGetCellHeader(RegistryHive, CellIndex) + 1);
  75 }
  76
  77 static LONG __inline CMAPI
  78 HvpGetCellFullSize(
  79    PHHIVE RegistryHive,
  80    PVOID Cell)
  81 {
  82    return ((PHCELL)Cell - 1)->Size;
  83 }
  84
  85 LONG CMAPI
  86 HvGetCellSize(IN PHHIVE Hive,
  87               IN PVOID Address)
  88 {
  89    PHCELL CellHeader;
  90    LONG Size;
  91
  92    CellHeader = (PHCELL)Address - 1;
  93    Size = CellHeader->Size * -1;
  94    Size -= sizeof(HCELL);
  95    return Size;
  96 }
  97
  98 BOOLEAN CMAPI
  99 HvMarkCellDirty(
 100    PHHIVE RegistryHive,
 101    HCELL_INDEX CellIndex,
 102    BOOLEAN HoldingLock)
 103 {
 104    ULONG CellBlock;
 105    ULONG CellLastBlock;
 106
 107    ASSERT(RegistryHive->ReadOnly == FALSE);
 108
 109    CMLTRACE(CMLIB_HCELL_DEBUG, "%s - Hive %p, CellIndex %08lx, HoldingLock %b\n",
 110        __FUNCTION__, RegistryHive, CellIndex, HoldingLock);
 111
 112    if ((CellIndex & HCELL_TYPE_MASK) >> HCELL_TYPE_SHIFT != Stable)
 113       return FALSE;
 114
 115    CellBlock = (CellIndex & HCELL_BLOCK_MASK) >> HCELL_BLOCK_SHIFT;
 116    CellLastBlock = ((CellIndex + HV_BLOCK_SIZE - 1) & HCELL_BLOCK_MASK) >> HCELL_BLOCK_SHIFT;
 117
 118    RtlSetBits(&RegistryHive->DirtyVector,
 119               CellBlock, CellLastBlock - CellBlock);
 120    return TRUE;
 121 }
 122
 123 BOOLEAN CMAPI
 124 HvIsCellDirty(IN PHHIVE Hive,
 125               IN HCELL_INDEX Cell)
 126 {
 127    /* Sanity checks */
 128    ASSERT(Hive->ReadOnly == FALSE);
 129
 130    /* Volatile cells are always "dirty" */
 131    if (HvGetCellType(Cell) == Volatile)
 132       return TRUE;
 133
 134    /* Check if the dirty bit is set */
 135    return RtlCheckBit(&Hive->DirtyVector, Cell / HV_BLOCK_SIZE);
 136 }
 137
 138 static ULONG __inline CMAPI
 139 HvpComputeFreeListIndex(
 140    ULONG Size)
 141 {
 142    ULONG Index;
 143    static CCHAR FindFirstSet[256] = {
 144       0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
 145       4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
 146       5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
 147       5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
 148       6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
 149       6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
 150       6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
 151       6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
 152       7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 153       7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 154       7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 155       7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 156       7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 157       7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 158       7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 159       7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7};
 160
 161    Index = (Size >> 3) - 1;
 162    if (Index >= 16)
 163    {
 164       if (Index > 255)
 165          Index = 23;
 166       else
 167          Index = FindFirstSet[Index] + 7;
 168    }
 169
 170    return Index;
 171 }
 172
 173 static NTSTATUS CMAPI
 174 HvpAddFree(
 175    PHHIVE RegistryHive,
 176    PHCELL FreeBlock,
 177    HCELL_INDEX FreeIndex)
 178 {
 179    PHCELL_INDEX FreeBlockData;
 180    HSTORAGE_TYPE Storage;
 181    ULONG Index;
 182
 183    ASSERT(RegistryHive != NULL);
 184    ASSERT(FreeBlock != NULL);
 185
 186    Storage = (FreeIndex & HCELL_TYPE_MASK) >> HCELL_TYPE_SHIFT;
 187    Index = HvpComputeFreeListIndex((ULONG)FreeBlock->Size);
 188
 189    FreeBlockData = (PHCELL_INDEX)(FreeBlock + 1);
 190    *FreeBlockData = RegistryHive->Storage[Storage].FreeDisplay[Index];
 191    RegistryHive->Storage[Storage].FreeDisplay[Index] = FreeIndex;
 192
 193    /* FIXME: Eventually get rid of free bins. */
 194
 195    return STATUS_SUCCESS;
 196 }
 197
 198 static VOID CMAPI
 199 HvpRemoveFree(
 200    PHHIVE RegistryHive,
 201    PHCELL CellBlock,
 202    HCELL_INDEX CellIndex)
 203 {
 204    PHCELL_INDEX FreeCellData;
 205    PHCELL_INDEX pFreeCellOffset;
 206    HSTORAGE_TYPE Storage;
 207    ULONG Index, FreeListIndex;
 208
 209    ASSERT(RegistryHive->ReadOnly == FALSE);
 210
 211    Storage = (CellIndex & HCELL_TYPE_MASK) >> HCELL_TYPE_SHIFT;
 212    Index = HvpComputeFreeListIndex((ULONG)CellBlock->Size);
 213
 214    pFreeCellOffset = &RegistryHive->Storage[Storage].FreeDisplay[Index];
 215    while (*pFreeCellOffset != HCELL_NIL)
 216    {
 217       FreeCellData = (PHCELL_INDEX)HvGetCell(RegistryHive, *pFreeCellOffset);
 218       if (*pFreeCellOffset == CellIndex)
 219       {
 220          *pFreeCellOffset = *FreeCellData;
 221          return;
 222       }
 223       pFreeCellOffset = FreeCellData;
 224    }
 225
 226    /* Something bad happened, print a useful trace info and bugcheck */
 227    CMLTRACE(CMLIB_HCELL_DEBUG, "-- beginning of HvpRemoveFree trace --\n");
 228    CMLTRACE(CMLIB_HCELL_DEBUG, "block we are about to free: %08x\n", CellIndex);
 229    CMLTRACE(CMLIB_HCELL_DEBUG, "chosen free list index: %d\n", Index);
 230    for (FreeListIndex = 0; FreeListIndex < 24; FreeListIndex++)
 231    {
 232       CMLTRACE(CMLIB_HCELL_DEBUG, "free list [%d]: ", FreeListIndex);
 233       pFreeCellOffset = &RegistryHive->Storage[Storage].FreeDisplay[FreeListIndex];
 234       while (*pFreeCellOffset != HCELL_NIL)
 235       {
 236          CMLTRACE(CMLIB_HCELL_DEBUG, "%08x ", *pFreeCellOffset);
 237          FreeCellData = (PHCELL_INDEX)HvGetCell(RegistryHive, *pFreeCellOffset);
 238          pFreeCellOffset = FreeCellData;
 239       }
 240       CMLTRACE(CMLIB_HCELL_DEBUG, "\n");
 241    }
 242    CMLTRACE(CMLIB_HCELL_DEBUG, "-- end of HvpRemoveFree trace --\n");
 243
 244    ASSERT(FALSE);
 245 }
 246
 247 static HCELL_INDEX CMAPI
 248 HvpFindFree(
 249    PHHIVE RegistryHive,
 250    ULONG Size,
 251    HSTORAGE_TYPE Storage)
 252 {
 253    PHCELL_INDEX FreeCellData;
 254    HCELL_INDEX FreeCellOffset;
 255    PHCELL_INDEX pFreeCellOffset;
 256    ULONG Index;
 257
 258    for (Index = HvpComputeFreeListIndex(Size); Index < 24; Index++)
 259    {
 260       pFreeCellOffset = &RegistryHive->Storage[Storage].FreeDisplay[Index];
 261       while (*pFreeCellOffset != HCELL_NIL)
 262       {
 263          FreeCellData = (PHCELL_INDEX)HvGetCell(RegistryHive, *pFreeCellOffset);
 264          if ((ULONG)HvpGetCellFullSize(RegistryHive, FreeCellData) >= Size)
 265          {
 266             FreeCellOffset = *pFreeCellOffset;
 267             *pFreeCellOffset = *FreeCellData;
 268             return FreeCellOffset;
 269          }
 270          pFreeCellOffset = FreeCellData;
 271       }
 272    }
 273
 274    return HCELL_NIL;
 275 }
 276
 277 NTSTATUS CMAPI
 278 HvpCreateHiveFreeCellList(
 279    PHHIVE Hive)
 280 {
 281    HCELL_INDEX BlockOffset;
 282    PHCELL FreeBlock;
 283    ULONG BlockIndex;
 284    ULONG FreeOffset;
 285    PHBIN Bin;
 286    NTSTATUS Status;
 287    ULONG Index;
 288
 289    /* Initialize the free cell list */
 290    for (Index = 0; Index < 24; Index++)
 291    {
 292       Hive->Storage[Stable].FreeDisplay[Index] = HCELL_NIL;
 293       Hive->Storage[Volatile].FreeDisplay[Index] = HCELL_NIL;
 294    }
 295
 296    BlockOffset = 0;
 297    BlockIndex = 0;
 298    while (BlockIndex < Hive->Storage[Stable].Length)
 299    {
 300       Bin = (PHBIN)Hive->Storage[Stable].BlockList[BlockIndex].BinAddress;
 301
 302       /* Search free blocks and add to list */
 303       FreeOffset = sizeof(HBIN);
 304       while (FreeOffset < Bin->Size)
 305       {
 306          FreeBlock = (PHCELL)((ULONG_PTR)Bin + FreeOffset);
 307          if (FreeBlock->Size > 0)
 308          {
 309             Status = HvpAddFree(Hive, FreeBlock, Bin->FileOffset + FreeOffset);
 310             if (!NT_SUCCESS(Status))
 311                return Status;
 312
 313             FreeOffset += FreeBlock->Size;
 314          }
 315          else
 316          {
 317             FreeOffset -= FreeBlock->Size;
 318          }
 319       }
 320
 321       BlockIndex += Bin->Size / HV_BLOCK_SIZE;
 322       BlockOffset += Bin->Size;
 323    }
 324
 325    return STATUS_SUCCESS;
 326 }
 327
 328 HCELL_INDEX CMAPI
 329 HvAllocateCell(
 330    PHHIVE RegistryHive,
 331    SIZE_T Size,
 332    HSTORAGE_TYPE Storage,
 333    HCELL_INDEX Vicinity)
 334 {
 335    PHCELL FreeCell;
 336    HCELL_INDEX FreeCellOffset;
 337    PHCELL NewCell;
 338    PHBIN Bin;
 339
 340    ASSERT(RegistryHive->ReadOnly == FALSE);
 341
 342    CMLTRACE(CMLIB_HCELL_DEBUG, "%s - Hive %p, Size %x, %s, Vicinity %08lx\n",
 343        __FUNCTION__, RegistryHive, Size, (Storage == 0) ? "Stable" : "Volatile", Vicinity);
 344
 345    /* Round to 16 bytes multiple. */
 346    Size = ROUND_UP(Size + sizeof(HCELL), 16);
 347
 348    /* First search in free blocks. */
 349    FreeCellOffset = HvpFindFree(RegistryHive, Size, Storage);
 350
 351    /* If no free cell was found we need to extend the hive file. */
 352    if (FreeCellOffset == HCELL_NIL)
 353    {
 354       Bin = HvpAddBin(RegistryHive, Size, Storage);
 355       if (Bin == NULL)
 356          return HCELL_NIL;
 357       FreeCellOffset = Bin->FileOffset + sizeof(HBIN);
 358       FreeCellOffset |= Storage << HCELL_TYPE_SHIFT;
 359    }
 360
 361    FreeCell = HvpGetCellHeader(RegistryHive, FreeCellOffset);
 362
 363    /* Split the block in two parts */
 364
 365    /* The free block that is created has to be at least
 366       sizeof(HCELL) + sizeof(HCELL_INDEX) big, so that free
 367       cell list code can work. Moreover we round cell sizes
 368       to 16 bytes, so creating a smaller block would result in
 369       a cell that would never be allocated. */
 370    if ((ULONG)FreeCell->Size > Size + 16)
 371    {
 372       NewCell = (PHCELL)((ULONG_PTR)FreeCell + Size);
 373       NewCell->Size = FreeCell->Size - Size;
 374       FreeCell->Size = Size;
 375       HvpAddFree(RegistryHive, NewCell, FreeCellOffset + Size);
 376       if (Storage == Stable)
 377          HvMarkCellDirty(RegistryHive, FreeCellOffset + Size, FALSE);
 378    }
 379
 380    if (Storage == Stable)
 381       HvMarkCellDirty(RegistryHive, FreeCellOffset, FALSE);
 382    FreeCell->Size = -FreeCell->Size;
 383    RtlZeroMemory(FreeCell + 1, Size - sizeof(HCELL));
 384
 385    CMLTRACE(CMLIB_HCELL_DEBUG, "%s - CellIndex %08lx\n",
 386        __FUNCTION__, FreeCellOffset);
 387
 388    return FreeCellOffset;
 389 }
 390
 391 HCELL_INDEX CMAPI
 392 HvReallocateCell(
 393    PHHIVE RegistryHive,
 394    HCELL_INDEX CellIndex,
 395    ULONG Size)
 396 {
 397    PVOID OldCell;
 398    PVOID NewCell;
 399    LONG OldCellSize;
 400    HCELL_INDEX NewCellIndex;
 401    HSTORAGE_TYPE Storage;
 402
 403    ASSERT(CellIndex != HCELL_NIL);
 404
 405    CMLTRACE(CMLIB_HCELL_DEBUG, "%s - Hive %p, CellIndex %08lx, Size %x\n",
 406        __FUNCTION__, RegistryHive, CellIndex, Size);
 407
 408    Storage = (CellIndex & HCELL_TYPE_MASK) >> HCELL_TYPE_SHIFT;
 409
 410    OldCell = HvGetCell(RegistryHive, CellIndex);
 411    OldCellSize = HvGetCellSize(RegistryHive, OldCell);
 412    ASSERT(OldCellSize > 0);
 413
 414    /*
 415     * If new data size is larger than the current, destroy current
 416     * data block and allocate a new one.
 417     *
 418     * FIXME: Merge with adjacent free cell if possible.
 419     * FIXME: Implement shrinking.
 420     */
 421    if (Size > OldCellSize)
 422    {
 423       NewCellIndex = HvAllocateCell(RegistryHive, Size, Storage, HCELL_NIL);
 424       if (NewCellIndex == HCELL_NIL)
 425          return HCELL_NIL;
 426
 427       NewCell = HvGetCell(RegistryHive, NewCellIndex);
 428       RtlCopyMemory(NewCell, OldCell, (SIZE_T)OldCellSize);
 429
 430       HvFreeCell(RegistryHive, CellIndex);
 431
 432       return NewCellIndex;
 433    }
 434
 435    return CellIndex;
 436 }
 437
 438 VOID CMAPI
 439 HvFreeCell(
 440    PHHIVE RegistryHive,
 441    HCELL_INDEX CellIndex)
 442 {
 443    PHCELL Free;
 444    PHCELL Neighbor;
 445    PHBIN Bin;
 446    ULONG CellType;
 447    ULONG CellBlock;
 448
 449    ASSERT(RegistryHive->ReadOnly == FALSE);
 450
 451    CMLTRACE(CMLIB_HCELL_DEBUG, "%s - Hive %p, CellIndex %08lx\n",
 452        __FUNCTION__, RegistryHive, CellIndex);
 453
 454    Free = HvpGetCellHeader(RegistryHive, CellIndex);
 455
 456    ASSERT(Free->Size < 0);
 457
 458    Free->Size = -Free->Size;
 459
 460    CellType = (CellIndex & HCELL_TYPE_MASK) >> HCELL_TYPE_SHIFT;
 461    CellBlock = (CellIndex & HCELL_BLOCK_MASK) >> HCELL_BLOCK_SHIFT;
 462
 463    /* FIXME: Merge free blocks */
 464    Bin = (PHBIN)RegistryHive->Storage[CellType].BlockList[CellBlock].BinAddress;
 465
 466    if ((CellIndex & ~HCELL_TYPE_MASK) + Free->Size <
 467        Bin->FileOffset + Bin->Size)
 468    {
 469       Neighbor = (PHCELL)((ULONG_PTR)Free + Free->Size);
 470       if (Neighbor->Size > 0)
 471       {
 472          HvpRemoveFree(RegistryHive, Neighbor,
 473                        ((HCELL_INDEX)((ULONG_PTR)Neighbor - (ULONG_PTR)Bin +
 474                        Bin->FileOffset)) | (CellIndex & HCELL_TYPE_MASK));
 475          Free->Size += Neighbor->Size;
 476       }
 477    }
 478
 479    Neighbor = (PHCELL)(Bin + 1);
 480    while (Neighbor < Free)
 481    {
 482       if (Neighbor->Size > 0)
 483       {
 484          if ((ULONG_PTR)Neighbor + Neighbor->Size == (ULONG_PTR)Free)
 485          {
 486             HCELL_INDEX NeighborCellIndex =
 487                (HCELL_INDEX)((ULONG_PTR)Neighbor - (ULONG_PTR)Bin +
 488                Bin->FileOffset) | (CellIndex & HCELL_TYPE_MASK);
 489
 490             if (HvpComputeFreeListIndex(Neighbor->Size) !=
 491                 HvpComputeFreeListIndex(Neighbor->Size + Free->Size))
 492             {
 493                HvpRemoveFree(RegistryHive, Neighbor, NeighborCellIndex);
 494                Neighbor->Size += Free->Size;
 495                HvpAddFree(RegistryHive, Neighbor, NeighborCellIndex);
 496             }
 497             else
 498                Neighbor->Size += Free->Size;
 499
 500             if (CellType == Stable)
 501                HvMarkCellDirty(RegistryHive, NeighborCellIndex, FALSE);
 502
 503             return;
 504          }
 505          Neighbor = (PHCELL)((ULONG_PTR)Neighbor + Neighbor->Size);
 506       }
 507       else
 508       {
 509          Neighbor = (PHCELL)((ULONG_PTR)Neighbor - Neighbor->Size);
 510       }
 511    }
 512
 513    /* Add block to the list of free blocks */
 514    HvpAddFree(RegistryHive, Free, CellIndex);
 515
 516    if (CellType == Stable)
 517       HvMarkCellDirty(RegistryHive, CellIndex, FALSE);
 518 }