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    ASSERT(CellIndex != HCELL_NULL);
  20    if (!RegistryHive->Flat)
  21    {
  22       ULONG CellType;
  23       ULONG CellBlock;
  24       ULONG CellOffset;
  25
  26       CellType = (CellIndex & HCELL_TYPE_MASK) >> HCELL_TYPE_SHIFT;
  27       CellBlock = (CellIndex & HCELL_BLOCK_MASK) >> HCELL_BLOCK_SHIFT;
  28       CellOffset = (CellIndex & HCELL_OFFSET_MASK) >> HCELL_OFFSET_SHIFT;
  29       ASSERT(CellBlock < RegistryHive->Storage[CellType].Length);
  30       Block = (PVOID)RegistryHive->Storage[CellType].BlockList[CellBlock].Block;
  31       ASSERT(Block != NULL);
  32       return (PVOID)((ULONG_PTR)Block + CellOffset);
  33    }
  34    else
  35    {
  36       ASSERT((CellIndex & HCELL_TYPE_MASK) == HvStable);
  37       return (PVOID)((ULONG_PTR)RegistryHive->HiveHeader + HV_BLOCK_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) return TRUE;
  50
  51     /* Otherwise, get the type and make sure it's valid */
  52     Type = HvGetCellType(CellIndex);
  53     if (((CellIndex % ~HCELL_TYPE_MASK) > RegistryHive->Storage[Type].Length) ||
  54         (CellIndex % (RegistryHive->Version >= 2 ? 8 : 16)))
  55     {
  56         /* Invalid cell index */
  57         return FALSE;
  58     }
  59
  60     /* Try to get the cell block */
  61     Block = (CellIndex & HCELL_BLOCK_MASK) >> HCELL_BLOCK_SHIFT;
  62     if (RegistryHive->Storage[Type].BlockList[Block].Block) return TRUE;
  63
  64     /* No valid block, fail */
  65     return FALSE;
  66 }
  67
  68 PVOID CMAPI
  69 HvGetCell(
  70    PHHIVE RegistryHive,
  71    HCELL_INDEX CellIndex)
  72 {
  73    return (PVOID)(HvpGetCellHeader(RegistryHive, CellIndex) + 1);
  74 }
  75
  76 static LONG __inline CMAPI
  77 HvpGetCellFullSize(
  78    PHHIVE RegistryHive,
  79    PVOID Cell)
  80 {
  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     CellHeader = (PHCELL)Address - 1;
  92     Size = CellHeader->Size * -1;
  93     Size -= sizeof(HCELL);
  94     return Size;
  95 }
  96
  97 VOID CMAPI
  98 HvMarkCellDirty(
  99    PHHIVE RegistryHive,
 100    HCELL_INDEX CellIndex)
 101 {
 102    LONG CellSize;
 103    ULONG CellBlock;
 104    ULONG CellLastBlock;
 105
 106    ASSERT(RegistryHive->ReadOnly == FALSE);
 107
 108    if ((CellIndex & HCELL_TYPE_MASK) >> HCELL_TYPE_SHIFT != HvStable)
 109       return;
 110
 111    CellBlock = (CellIndex & HCELL_BLOCK_MASK) >> HCELL_BLOCK_SHIFT;
 112    CellLastBlock = ((CellIndex + HV_BLOCK_SIZE - 1) & HCELL_BLOCK_MASK) >> HCELL_BLOCK_SHIFT;
 113
 114    CellSize = HvpGetCellFullSize(RegistryHive, HvGetCell(RegistryHive, CellIndex));
 115    if (CellSize < 0)
 116       CellSize = -CellSize;
 117
 118    RtlSetBits(&RegistryHive->DirtyVector,
 119               CellBlock, CellLastBlock - CellBlock);
 120 }
 121
 122 BOOLEAN CMAPI
 123 HvIsCellDirty(IN PHHIVE Hive,
 124               IN HCELL_INDEX Cell)
 125 {
 126     /* Sanity checks */
 127     ASSERT(Hive->ReadOnly == FALSE);
 128
 129     /* Volatile cells are always "dirty" */
 130     if (HvGetCellType(Cell) == HvVolatile) return TRUE;
 131
 132     /* Check if the dirty bit is set */
 133     return RtlCheckBit(&Hive->DirtyVector, Cell / HV_BLOCK_SIZE);
 134 }
 135
 136 static ULONG __inline CMAPI
 137 HvpComputeFreeListIndex(
 138    ULONG Size)
 139 {
 140    ULONG Index;
 141    static CCHAR FindFirstSet[256] = {
 142       0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
 143       4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
 144       5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
 145       5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
 146       6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
 147       6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
 148       6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
 149       6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
 150       7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 151       7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 152       7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 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
 159    Index = (Size >> 3) - 1;
 160    if (Index >= 16)
 161    {
 162       if (Index > 255)
 163          Index = 23;
 164       else
 165          Index = FindFirstSet[Index] + 7;
 166    }
 167
 168    return Index;
 169 }
 170
 171 static NTSTATUS CMAPI
 172 HvpAddFree(
 173    PHHIVE RegistryHive,
 174    PHCELL FreeBlock,
 175    HCELL_INDEX FreeIndex)
 176 {
 177    PHCELL_INDEX FreeBlockData;
 178    HV_STORAGE_TYPE Storage;
 179    ULONG Index;
 180
 181    ASSERT(RegistryHive != NULL);
 182    ASSERT(FreeBlock != NULL);
 183
 184    Storage = (FreeIndex & HCELL_TYPE_MASK) >> HCELL_TYPE_SHIFT;
 185    Index = HvpComputeFreeListIndex((ULONG)FreeBlock->Size);
 186
 187    FreeBlockData = (PHCELL_INDEX)(FreeBlock + 1);
 188    *FreeBlockData = RegistryHive->Storage[Storage].FreeDisplay[Index];
 189    RegistryHive->Storage[Storage].FreeDisplay[Index] = FreeIndex;
 190
 191    /* FIXME: Eventually get rid of free bins. */
 192
 193    return STATUS_SUCCESS;
 194 }
 195
 196 static VOID CMAPI
 197 HvpRemoveFree(
 198    PHHIVE RegistryHive,
 199    PHCELL CellBlock,
 200    HCELL_INDEX CellIndex)
 201 {
 202    PHCELL_INDEX FreeCellData;
 203    PHCELL_INDEX pFreeCellOffset;
 204    HV_STORAGE_TYPE Storage;
 205    ULONG Index;
 206
 207    ASSERT(RegistryHive->ReadOnly == FALSE);
 208
 209    Storage = (CellIndex & HCELL_TYPE_MASK) >> HCELL_TYPE_SHIFT;
 210    Index = HvpComputeFreeListIndex((ULONG)CellBlock->Size);
 211
 212    pFreeCellOffset = &RegistryHive->Storage[Storage].FreeDisplay[Index];
 213    while (*pFreeCellOffset != HCELL_NULL)
 214    {
 215       FreeCellData = (PHCELL_INDEX)HvGetCell(RegistryHive, *pFreeCellOffset);
 216       if (*pFreeCellOffset == CellIndex)
 217       {
 218          *pFreeCellOffset = *FreeCellData;
 219          return;
 220       }
 221       pFreeCellOffset = FreeCellData;
 222    }
 223
 224    //ASSERT(FALSE);
 225 }
 226
 227 static HCELL_INDEX CMAPI
 228 HvpFindFree(
 229    PHHIVE RegistryHive,
 230    ULONG Size,
 231    HV_STORAGE_TYPE Storage)
 232 {
 233    PHCELL_INDEX FreeCellData;
 234    HCELL_INDEX FreeCellOffset;
 235    PHCELL_INDEX pFreeCellOffset;
 236    ULONG Index;
 237
 238    for (Index = HvpComputeFreeListIndex(Size); Index < 24; Index++)
 239    {
 240       pFreeCellOffset = &RegistryHive->Storage[Storage].FreeDisplay[Index];
 241       while (*pFreeCellOffset != HCELL_NULL)
 242       {
 243          FreeCellData = (PHCELL_INDEX)HvGetCell(RegistryHive, *pFreeCellOffset);
 244          if ((ULONG)HvpGetCellFullSize(RegistryHive, FreeCellData) >= Size)
 245          {
 246             FreeCellOffset = *pFreeCellOffset;
 247             *pFreeCellOffset = *FreeCellData;
 248             return FreeCellOffset;
 249          }
 250          pFreeCellOffset = FreeCellData;
 251       }
 252    }
 253
 254    return HCELL_NULL;
 255 }
 256
 257 NTSTATUS CMAPI
 258 HvpCreateHiveFreeCellList(
 259    PHHIVE Hive)
 260 {
 261    HCELL_INDEX BlockOffset;
 262    PHCELL FreeBlock;
 263    ULONG BlockIndex;
 264    ULONG FreeOffset;
 265    PHBIN Bin;
 266    NTSTATUS Status;
 267    ULONG Index;
 268
 269    /* Initialize the free cell list */
 270    for (Index = 0; Index < 24; Index++)
 271    {
 272       Hive->Storage[HvStable].FreeDisplay[Index] = HCELL_NULL;
 273       Hive->Storage[HvVolatile].FreeDisplay[Index] = HCELL_NULL;
 274    }
 275
 276    BlockOffset = 0;
 277    BlockIndex = 0;
 278    while (BlockIndex < Hive->Storage[HvStable].Length)
 279    {
 280       Bin = (PHBIN)Hive->Storage[HvStable].BlockList[BlockIndex].Bin;
 281
 282       /* Search free blocks and add to list */
 283       FreeOffset = sizeof(HBIN);
 284       while (FreeOffset < Bin->Size)
 285       {
 286          FreeBlock = (PHCELL)((ULONG_PTR)Bin + FreeOffset);
 287          if (FreeBlock->Size > 0)
 288          {
 289             Status = HvpAddFree(Hive, FreeBlock, Bin->FileOffset + FreeOffset);
 290             if (!NT_SUCCESS(Status))
 291                return Status;
 292
 293             FreeOffset += FreeBlock->Size;
 294          }
 295          else
 296          {
 297             FreeOffset -= FreeBlock->Size;
 298          }
 299       }
 300
 301       BlockIndex += Bin->Size / HV_BLOCK_SIZE;
 302       BlockOffset += Bin->Size;
 303    }
 304
 305    return STATUS_SUCCESS;
 306 }
 307
 308 HCELL_INDEX CMAPI
 309 HvAllocateCell(
 310    PHHIVE RegistryHive,
 311    SIZE_T Size,
 312    HV_STORAGE_TYPE Storage)
 313 {
 314    PHCELL FreeCell;
 315    HCELL_INDEX FreeCellOffset;
 316    PHCELL NewCell;
 317    PHBIN Bin;
 318
 319    ASSERT(RegistryHive->ReadOnly == FALSE);
 320
 321    /* Round to 16 bytes multiple. */
 322    Size = ROUND_UP(Size + sizeof(HCELL), 16);
 323
 324    /* First search in free blocks. */
 325    FreeCellOffset = HvpFindFree(RegistryHive, Size, Storage);
 326
 327    /* If no free cell was found we need to extend the hive file. */
 328    if (FreeCellOffset == HCELL_NULL)
 329    {
 330       Bin = HvpAddBin(RegistryHive, Size, Storage);
 331       if (Bin == NULL)
 332          return HCELL_NULL;
 333       FreeCellOffset = Bin->FileOffset + sizeof(HBIN);
 334       FreeCellOffset |= Storage << HCELL_TYPE_SHIFT;
 335    }
 336
 337    FreeCell = HvpGetCellHeader(RegistryHive, FreeCellOffset);
 338
 339    /* Split the block in two parts */
 340    /* FIXME: There is some minimal cell size that we must respect. */
 341    if ((ULONG)FreeCell->Size > Size + sizeof(HCELL_INDEX))
 342    {
 343       NewCell = (PHCELL)((ULONG_PTR)FreeCell + Size);
 344       NewCell->Size = FreeCell->Size - Size;
 345       FreeCell->Size = Size;
 346       HvpAddFree(RegistryHive, NewCell, FreeCellOffset + Size);
 347       if (Storage == HvStable)
 348          HvMarkCellDirty(RegistryHive, FreeCellOffset + Size);
 349    }
 350
 351    if (Storage == HvStable)
 352       HvMarkCellDirty(RegistryHive, FreeCellOffset);
 353    FreeCell->Size = -FreeCell->Size;
 354    RtlZeroMemory(FreeCell + 1, Size - sizeof(HCELL));
 355
 356    return FreeCellOffset;
 357 }
 358
 359 HCELL_INDEX CMAPI
 360 HvReallocateCell(
 361    PHHIVE RegistryHive,
 362    HCELL_INDEX CellIndex,
 363    ULONG Size)
 364 {
 365    PVOID OldCell;
 366    PVOID NewCell;
 367    LONG OldCellSize;
 368    HCELL_INDEX NewCellIndex;
 369    HV_STORAGE_TYPE Storage;
 370
 371    ASSERT(CellIndex != HCELL_NULL);
 372
 373    Storage = (CellIndex & HCELL_TYPE_MASK) >> HCELL_TYPE_SHIFT;
 374
 375    OldCell = HvGetCell(RegistryHive, CellIndex);
 376    OldCellSize = HvGetCellSize(RegistryHive, OldCell);
 377    ASSERT(OldCellSize > 0);
 378
 379    /*
 380     * If new data size is larger than the current, destroy current
 381     * data block and allocate a new one.
 382     *
 383     * FIXME: Merge with adjacent free cell if possible.
 384     * FIXME: Implement shrinking.
 385     */
 386    if (Size > OldCellSize)
 387    {
 388       NewCellIndex = HvAllocateCell(RegistryHive, Size, Storage);
 389       if (NewCellIndex == HCELL_NULL)
 390          return HCELL_NULL;
 391
 392       NewCell = HvGetCell(RegistryHive, NewCellIndex);
 393       RtlCopyMemory(NewCell, OldCell, (SIZE_T)OldCellSize);
 394
 395       HvFreeCell(RegistryHive, CellIndex);
 396
 397       return NewCellIndex;
 398    }
 399
 400    return CellIndex;
 401 }
 402
 403 VOID CMAPI
 404 HvFreeCell(
 405    PHHIVE RegistryHive,
 406    HCELL_INDEX CellIndex)
 407 {
 408    PHCELL Free;
 409    PHCELL Neighbor;
 410    PHBIN Bin;
 411    ULONG CellType;
 412    ULONG CellBlock;
 413
 414    ASSERT(RegistryHive->ReadOnly == FALSE);
 415
 416    Free = HvpGetCellHeader(RegistryHive, CellIndex);
 417
 418    ASSERT(Free->Size < 0);
 419
 420    Free->Size = -Free->Size;
 421
 422    CellType = (CellIndex & HCELL_TYPE_MASK) >> HCELL_TYPE_SHIFT;
 423    CellBlock = (CellIndex & HCELL_BLOCK_MASK) >> HCELL_BLOCK_SHIFT;
 424
 425    /* FIXME: Merge free blocks */
 426    Bin = (PHBIN)RegistryHive->Storage[CellType].BlockList[CellBlock].Bin;
 427
 428    if ((CellIndex & ~HCELL_TYPE_MASK) + Free->Size <
 429        Bin->FileOffset + Bin->Size)
 430    {
 431       Neighbor = (PHCELL)((ULONG_PTR)Free + Free->Size);
 432       if (Neighbor->Size > 0)
 433       {
 434          HvpRemoveFree(RegistryHive, Neighbor,
 435                        ((HCELL_INDEX)((ULONG_PTR)Neighbor - (ULONG_PTR)Bin +
 436                        Bin->FileOffset)) | (CellIndex & HCELL_TYPE_MASK));
 437          Free->Size += Neighbor->Size;
 438       }
 439    }
 440
 441    Neighbor = (PHCELL)(Bin + 1);
 442    while (Neighbor < Free)
 443    {
 444       if (Neighbor->Size > 0)
 445       {
 446          if ((ULONG_PTR)Neighbor + Neighbor->Size == (ULONG_PTR)Free)
 447          {
 448             Neighbor->Size += Free->Size;
 449             if (CellType == HvStable)
 450                HvMarkCellDirty(RegistryHive,
 451                                (HCELL_INDEX)((ULONG_PTR)Neighbor - (ULONG_PTR)Bin +
 452                                Bin->FileOffset));
 453             return;
 454          }
 455          Neighbor = (PHCELL)((ULONG_PTR)Neighbor + Neighbor->Size);
 456       }
 457       else
 458       {
 459          Neighbor = (PHCELL)((ULONG_PTR)Neighbor - Neighbor->Size);
 460       }
 461    }
 462
 463    /* Add block to the list of free blocks */
 464    HvpAddFree(RegistryHive, Free, CellIndex);
 465
 466    if (CellType == HvStable)
 467       HvMarkCellDirty(RegistryHive, CellIndex);
 468 }