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