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