reactos/sdk/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   = HvGetCellType(CellIndex);
  26         ULONG CellBlock  = HvGetCellBlock(CellIndex);
  27         ULONG CellOffset = (CellIndex & HCELL_OFFSET_MASK) >> HCELL_OFFSET_SHIFT;
  28
  29         ASSERT(CellBlock < RegistryHive->Storage[CellType].Length);
  30         Block = (PVOID)RegistryHive->Storage[CellType].BlockList[CellBlock].BlockAddress;
  31         ASSERT(Block != NULL);
  32         return (PVOID)((ULONG_PTR)Block + CellOffset);
  33     }
  34     else
  35     {
  36         ASSERT(HvGetCellType(CellIndex) == Stable);
  37         return (PVOID)((ULONG_PTR)RegistryHive->BaseBlock + HBLOCK_SIZE +
  38                        CellIndex);
  39     }
  40 }
  41
  42 BOOLEAN CMAPI
  43 HvIsCellAllocated(IN PHHIVE RegistryHive,
  44                   IN HCELL_INDEX CellIndex)
  45 {
  46     ULONG Type, Block;
  47
  48     /* If it's a flat hive, the cell is always allocated */
  49     if (RegistryHive->Flat)
  50         return TRUE;
  51
  52     /* Otherwise, get the type and make sure it's valid */
  53     Type = HvGetCellType(CellIndex);
  54     Block = HvGetCellBlock(CellIndex);
  55     if (Block >= RegistryHive->Storage[Type].Length)
  56         return FALSE;
  57
  58     /* Try to get the cell block */
  59     if (RegistryHive->Storage[Type].BlockList[Block].BlockAddress)
  60         return TRUE;
  61
  62     /* No valid block, fail */
  63     return FALSE;
  64 }
  65
  66 PVOID CMAPI
  67 HvGetCell(
  68     PHHIVE RegistryHive,
  69     HCELL_INDEX CellIndex)
  70 {
  71     ASSERT(CellIndex != HCELL_NIL);
  72     return (PVOID)(HvpGetCellHeader(RegistryHive, CellIndex) + 1);
  73 }
  74
  75 static __inline LONG CMAPI
  76 HvpGetCellFullSize(
  77     PHHIVE RegistryHive,
  78     PVOID Cell)
  79 {
  80     UNREFERENCED_PARAMETER(RegistryHive);
  81     return ((PHCELL)Cell - 1)->Size;
  82 }
  83
  84 LONG CMAPI
  85 HvGetCellSize(IN PHHIVE Hive,
  86               IN PVOID Address)
  87 {
  88     PHCELL CellHeader;
  89     LONG Size;
  90
  91     UNREFERENCED_PARAMETER(Hive);
  92
  93     CellHeader = (PHCELL)Address - 1;
  94     Size = CellHeader->Size * -1;
  95     Size -= sizeof(HCELL);
  96     return Size;
  97 }
  98
  99 BOOLEAN CMAPI
 100 HvMarkCellDirty(
 101     PHHIVE RegistryHive,
 102     HCELL_INDEX CellIndex,
 103     BOOLEAN HoldingLock)
 104 {
 105     ULONG CellBlock;
 106     ULONG CellLastBlock;
 107
 108     ASSERT(RegistryHive->ReadOnly == FALSE);
 109
 110     CMLTRACE(CMLIB_HCELL_DEBUG, "%s - Hive %p, CellIndex %08lx, HoldingLock %u\n",
 111              __FUNCTION__, RegistryHive, CellIndex, HoldingLock);
 112
 113     if (HvGetCellType(CellIndex) != Stable)
 114         return TRUE;
 115
 116     CellBlock     = HvGetCellBlock(CellIndex);
 117     CellLastBlock = HvGetCellBlock(CellIndex + HBLOCK_SIZE - 1);
 118
 119     RtlSetBits(&RegistryHive->DirtyVector,
 120                CellBlock, CellLastBlock - CellBlock);
 121     RegistryHive->DirtyCount++;
 122     return TRUE;
 123 }
 124
 125 BOOLEAN CMAPI
 126 HvIsCellDirty(IN PHHIVE Hive,
 127               IN HCELL_INDEX Cell)
 128 {
 129     BOOLEAN IsDirty = FALSE;
 130
 131     /* Sanity checks */
 132     ASSERT(Hive->ReadOnly == FALSE);
 133
 134     /* Volatile cells are always "dirty" */
 135     if (HvGetCellType(Cell) == Volatile)
 136         return TRUE;
 137
 138     /* Check if the dirty bit is set */
 139     if (RtlCheckBit(&Hive->DirtyVector, Cell / HBLOCK_SIZE))
 140         IsDirty = TRUE;
 141
 142     /* Return result as boolean*/
 143     return IsDirty;
 144 }
 145
 146 static __inline ULONG CMAPI
 147 HvpComputeFreeListIndex(
 148     ULONG Size)
 149 {
 150     ULONG Index;
 151     static CCHAR FindFirstSet[128] = {
 152         0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
 153         4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
 154         5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
 155         5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
 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         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
 161     ASSERT(Size >= (1 << 3));
 162     Index = (Size >> 3) - 1;
 163     if (Index >= 16)
 164     {
 165         if (Index > 127)
 166             Index = 23;
 167         else
 168             Index = FindFirstSet[Index] + 16;
 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 = HvGetCellType(FreeIndex);
 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 = HvGetCellType(CellIndex);
 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: %u\n", Index);
 231     for (FreeListIndex = 0; FreeListIndex < 24; FreeListIndex++)
 232     {
 233         CMLTRACE(CMLIB_HCELL_DEBUG, "free list [%u]: ", 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 / HBLOCK_SIZE;
 323         BlockOffset += Bin->Size;
 324     }
 325
 326     return STATUS_SUCCESS;
 327 }
 328
 329 HCELL_INDEX CMAPI
 330 HvAllocateCell(
 331     PHHIVE RegistryHive,
 332     ULONG 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
 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 = HvGetCellType(CellIndex);
 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 = HvGetCellType(CellIndex);
 463     CellBlock = HvGetCellBlock(CellIndex);
 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 }