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