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