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