-/*
- * PROJECT: registry manipulation library
- * LICENSE: GPL - See COPYING in the top level directory
- * COPYRIGHT: Copyright 2005 Filip Navara <navaraf@reactos.org>
- * Copyright 2001 - 2005 Eric Kohl
- */
-
-#include "cmlib.h"
-#define NDEBUG
-#include <debug.h>
-
-static PHCELL __inline CMAPI
-HvpGetCellHeader(
- PHHIVE RegistryHive,
- HCELL_INDEX CellIndex)
-{
- PVOID Block;
-
- ASSERT(CellIndex != HCELL_NULL);
- if (!RegistryHive->Flat)
- {
- ULONG CellType;
- ULONG CellBlock;
- ULONG CellOffset;
-
- CellType = (CellIndex & HCELL_TYPE_MASK) >> HCELL_TYPE_SHIFT;
- CellBlock = (CellIndex & HCELL_BLOCK_MASK) >> HCELL_BLOCK_SHIFT;
- CellOffset = (CellIndex & HCELL_OFFSET_MASK) >> HCELL_OFFSET_SHIFT;
- ASSERT(CellBlock < RegistryHive->Storage[CellType].Length);
- Block = (PVOID)RegistryHive->Storage[CellType].BlockList[CellBlock].Block;
- ASSERT(Block != NULL);
- return (PVOID)((ULONG_PTR)Block + CellOffset);
- }
- else
- {
- ASSERT((CellIndex & HCELL_TYPE_MASK) == HvStable);
- return (PVOID)((ULONG_PTR)RegistryHive->HiveHeader + HV_BLOCK_SIZE +
- CellIndex);
- }
-}
-
-PVOID CMAPI
-HvGetCell(
- PHHIVE RegistryHive,
- HCELL_INDEX CellIndex)
-{
- return (PVOID)(HvpGetCellHeader(RegistryHive, CellIndex) + 1);
-}
-
-static LONG __inline CMAPI
-HvpGetCellFullSize(
- PHHIVE RegistryHive,
- PVOID Cell)
-{
- return ((PHCELL)Cell - 1)->Size;
-}
-
-LONG CMAPI
-HvGetCellSize(
- PHHIVE RegistryHive,
- PVOID Cell)
-{
- PHCELL CellHeader;
-
- CellHeader = (PHCELL)Cell - 1;
- if (CellHeader->Size < 0)
- return CellHeader->Size + sizeof(HCELL);
- else
- return CellHeader->Size - sizeof(HCELL);
-}
-
-VOID CMAPI
-HvMarkCellDirty(
- PHHIVE RegistryHive,
- HCELL_INDEX CellIndex)
-{
- LONG CellSize;
- ULONG CellBlock;
- ULONG CellLastBlock;
-
- ASSERT(RegistryHive->ReadOnly == FALSE);
-
- if ((CellIndex & HCELL_TYPE_MASK) >> HCELL_TYPE_SHIFT != HvStable)
- return;
-
- CellBlock = (CellIndex & HCELL_BLOCK_MASK) >> HCELL_BLOCK_SHIFT;
- CellLastBlock = ((CellIndex + HV_BLOCK_SIZE - 1) & HCELL_BLOCK_MASK) >> HCELL_BLOCK_SHIFT;
-
- CellSize = HvpGetCellFullSize(RegistryHive, HvGetCell(RegistryHive, CellIndex));
- if (CellSize < 0)
- CellSize = -CellSize;
-
- RtlSetBits(&RegistryHive->DirtyVector,
- CellBlock, CellLastBlock - CellBlock);
-}
-
-static ULONG __inline CMAPI
-HvpComputeFreeListIndex(
- ULONG Size)
-{
- ULONG Index;
- static CCHAR FindFirstSet[256] = {
- 0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
- 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
- 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
- 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
- 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
- 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
- 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
- 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
- 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
- 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
- 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
- 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
- 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
- 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
- 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
- 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7};
-
- Index = (Size >> 3) - 1;
- if (Index >= 16)
- {
- if (Index > 255)
- Index = 23;
- else
- Index = FindFirstSet[Index] + 7;
- }
-
- return Index;
-}
-
-static NTSTATUS CMAPI
-HvpAddFree(
- PHHIVE RegistryHive,
- PHCELL FreeBlock,
- HCELL_INDEX FreeIndex)
-{
- PHCELL_INDEX FreeBlockData;
- HV_STORAGE_TYPE Storage;
- ULONG Index;
-
- ASSERT(RegistryHive != NULL);
- ASSERT(FreeBlock != NULL);
-
- Storage = (FreeIndex & HCELL_TYPE_MASK) >> HCELL_TYPE_SHIFT;
- Index = HvpComputeFreeListIndex((ULONG)FreeBlock->Size);
-
- FreeBlockData = (PHCELL_INDEX)(FreeBlock + 1);
- *FreeBlockData = RegistryHive->Storage[Storage].FreeDisplay[Index];
- RegistryHive->Storage[Storage].FreeDisplay[Index] = FreeIndex;
-
- /* FIXME: Eventually get rid of free bins. */
-
- return STATUS_SUCCESS;
-}
-
-static VOID CMAPI
-HvpRemoveFree(
- PHHIVE RegistryHive,
- PHCELL CellBlock,
- HCELL_INDEX CellIndex)
-{
- PHCELL_INDEX FreeCellData;
- PHCELL_INDEX pFreeCellOffset;
- HV_STORAGE_TYPE Storage;
- ULONG Index;
-
- ASSERT(RegistryHive->ReadOnly == FALSE);
-
- Storage = (CellIndex & HCELL_TYPE_MASK) >> HCELL_TYPE_SHIFT;
- Index = HvpComputeFreeListIndex((ULONG)CellBlock->Size);
-
- pFreeCellOffset = &RegistryHive->Storage[Storage].FreeDisplay[Index];
- while (*pFreeCellOffset != HCELL_NULL)
- {
- FreeCellData = (PHCELL_INDEX)HvGetCell(RegistryHive, *pFreeCellOffset);
- if (*pFreeCellOffset == CellIndex)
- {
- *pFreeCellOffset = *FreeCellData;
- return;
- }
- pFreeCellOffset = FreeCellData;
- }
-
- ASSERT(FALSE);
-}
-
-static HCELL_INDEX CMAPI
-HvpFindFree(
- PHHIVE RegistryHive,
- ULONG Size,
- HV_STORAGE_TYPE Storage)
-{
- PHCELL_INDEX FreeCellData;
- HCELL_INDEX FreeCellOffset;
- PHCELL_INDEX pFreeCellOffset;
- ULONG Index;
-
- for (Index = HvpComputeFreeListIndex(Size); Index < 24; Index++)
- {
- pFreeCellOffset = &RegistryHive->Storage[Storage].FreeDisplay[Index];
- while (*pFreeCellOffset != HCELL_NULL)
- {
- FreeCellData = (PHCELL_INDEX)HvGetCell(RegistryHive, *pFreeCellOffset);
- if ((ULONG)HvpGetCellFullSize(RegistryHive, FreeCellData) >= Size)
- {
- FreeCellOffset = *pFreeCellOffset;
- *pFreeCellOffset = *FreeCellData;
- return FreeCellOffset;
- }
- pFreeCellOffset = FreeCellData;
- }
- }
-
- return HCELL_NULL;
-}
-
-NTSTATUS CMAPI
-HvpCreateHiveFreeCellList(
- PHHIVE Hive)
-{
- HCELL_INDEX BlockOffset;
- PHCELL FreeBlock;
- ULONG BlockIndex;
- ULONG FreeOffset;
- PHBIN Bin;
- NTSTATUS Status;
- ULONG Index;
-
- /* Initialize the free cell list */
- for (Index = 0; Index < 24; Index++)
- {
- Hive->Storage[HvStable].FreeDisplay[Index] = HCELL_NULL;
- Hive->Storage[HvVolatile].FreeDisplay[Index] = HCELL_NULL;
- }
-
- BlockOffset = 0;
- BlockIndex = 0;
- while (BlockIndex < Hive->Storage[HvStable].Length)
- {
- Bin = (PHBIN)Hive->Storage[HvStable].BlockList[BlockIndex].Bin;
-
- /* Search free blocks and add to list */
- FreeOffset = sizeof(HBIN);
- while (FreeOffset < Bin->Size)
- {
- FreeBlock = (PHCELL)((ULONG_PTR)Bin + FreeOffset);
- if (FreeBlock->Size > 0)
- {
- Status = HvpAddFree(Hive, FreeBlock, Bin->FileOffset + FreeOffset);
- if (!NT_SUCCESS(Status))
- return Status;
-
- FreeOffset += FreeBlock->Size;
- }
- else
- {
- FreeOffset -= FreeBlock->Size;
- }
- }
-
- BlockIndex += Bin->Size / HV_BLOCK_SIZE;
- BlockOffset += Bin->Size;
- }
-
- return STATUS_SUCCESS;
-}
-
-HCELL_INDEX CMAPI
-HvAllocateCell(
- PHHIVE RegistryHive,
- ULONG Size,
- HV_STORAGE_TYPE Storage)
-{
- PHCELL FreeCell;
- HCELL_INDEX FreeCellOffset;
- PHCELL NewCell;
- PHBIN Bin;
-
- ASSERT(RegistryHive->ReadOnly == FALSE);
-
- /* Round to 16 bytes multiple. */
- Size = ROUND_UP(Size + sizeof(HCELL), 16);
-
- /* First search in free blocks. */
- FreeCellOffset = HvpFindFree(RegistryHive, Size, Storage);
-
- /* If no free cell was found we need to extend the hive file. */
- if (FreeCellOffset == HCELL_NULL)
- {
- Bin = HvpAddBin(RegistryHive, Size, Storage);
- if (Bin == NULL)
- return HCELL_NULL;
- FreeCellOffset = Bin->FileOffset + sizeof(HBIN);
- FreeCellOffset |= Storage << HCELL_TYPE_SHIFT;
- }
-
- FreeCell = HvpGetCellHeader(RegistryHive, FreeCellOffset);
-
- /* Split the block in two parts */
- /* FIXME: There is some minimal cell size that we must respect. */
- if ((ULONG)FreeCell->Size > Size + sizeof(HCELL_INDEX))
- {
- NewCell = (PHCELL)((ULONG_PTR)FreeCell + Size);
- NewCell->Size = FreeCell->Size - Size;
- FreeCell->Size = Size;
- HvpAddFree(RegistryHive, NewCell, FreeCellOffset + Size);
- if (Storage == HvStable)
- HvMarkCellDirty(RegistryHive, FreeCellOffset + Size);
- }
-
- if (Storage == HvStable)
- HvMarkCellDirty(RegistryHive, FreeCellOffset);
- FreeCell->Size = -FreeCell->Size;
- RtlZeroMemory(FreeCell + 1, Size - sizeof(HCELL));
-
- return FreeCellOffset;
-}
-
-HCELL_INDEX CMAPI
-HvReallocateCell(
- PHHIVE RegistryHive,
- HCELL_INDEX CellIndex,
- ULONG Size)
-{
- PVOID OldCell;
- PVOID NewCell;
- LONG OldCellSize;
- HCELL_INDEX NewCellIndex;
- HV_STORAGE_TYPE Storage;
-
- ASSERT(CellIndex != HCELL_NULL);
-
- Storage = (CellIndex & HCELL_TYPE_MASK) >> HCELL_TYPE_SHIFT;
-
- OldCell = HvGetCell(RegistryHive, CellIndex);
- OldCellSize = HvGetCellSize(RegistryHive, OldCell);
- ASSERT(OldCellSize < 0);
-
- /*
- * If new data size is larger than the current, destroy current
- * data block and allocate a new one.
- *
- * FIXME: Merge with adjacent free cell if possible.
- * FIXME: Implement shrinking.
- */
- if (Size > (ULONG)-OldCellSize)
- {
- NewCellIndex = HvAllocateCell(RegistryHive, Size, Storage);
- if (NewCellIndex == HCELL_NULL)
- return HCELL_NULL;
-
- NewCell = HvGetCell(RegistryHive, NewCellIndex);
- RtlCopyMemory(NewCell, OldCell, (SIZE_T)-OldCellSize);
-
- HvFreeCell(RegistryHive, CellIndex);
-
- return NewCellIndex;
- }
-
- return CellIndex;
-}
-
-VOID CMAPI
-HvFreeCell(
- PHHIVE RegistryHive,
- HCELL_INDEX CellIndex)
-{
- PHCELL Free;
- PHCELL Neighbor;
- PHBIN Bin;
- ULONG CellType;
- ULONG CellBlock;
-
- ASSERT(RegistryHive->ReadOnly == FALSE);
-
- Free = HvpGetCellHeader(RegistryHive, CellIndex);
-
- ASSERT(Free->Size < 0);
-
- Free->Size = -Free->Size;
-
- CellType = (CellIndex & HCELL_TYPE_MASK) >> HCELL_TYPE_SHIFT;
- CellBlock = (CellIndex & HCELL_BLOCK_MASK) >> HCELL_BLOCK_SHIFT;
-
- /* FIXME: Merge free blocks */
- Bin = (PHBIN)RegistryHive->Storage[CellType].BlockList[CellBlock].Bin;
-
- if ((CellIndex & ~HCELL_TYPE_MASK) + Free->Size <
- Bin->FileOffset + Bin->Size)
- {
- Neighbor = (PHCELL)((ULONG_PTR)Free + Free->Size);
- if (Neighbor->Size > 0)
- {
- HvpRemoveFree(RegistryHive, Neighbor,
- ((HCELL_INDEX)((ULONG_PTR)Neighbor - (ULONG_PTR)Bin +
- Bin->FileOffset)) | (CellIndex & HCELL_TYPE_MASK));
- Free->Size += Neighbor->Size;
- }
- }
-
- Neighbor = (PHCELL)(Bin + 1);
- while (Neighbor < Free)
- {
- if (Neighbor->Size > 0)
- {
- if ((ULONG_PTR)Neighbor + Neighbor->Size == (ULONG_PTR)Free)
- {
- Neighbor->Size += Free->Size;
- if (CellType == HvStable)
- HvMarkCellDirty(RegistryHive,
- (HCELL_INDEX)((ULONG_PTR)Neighbor - (ULONG_PTR)Bin +
- Bin->FileOffset));
- return;
- }
- Neighbor = (PHCELL)((ULONG_PTR)Neighbor + Neighbor->Size);
- }
- else
- {
- Neighbor = (PHCELL)((ULONG_PTR)Neighbor - Neighbor->Size);
- }
- }
-
- /* Add block to the list of free blocks */
- HvpAddFree(RegistryHive, Free, CellIndex);
-
- if (CellType == HvStable)
- HvMarkCellDirty(RegistryHive, CellIndex);
-}
+/*\r
+ * PROJECT: registry manipulation library\r
+ * LICENSE: GPL - See COPYING in the top level directory\r
+ * COPYRIGHT: Copyright 2005 Filip Navara <navaraf@reactos.org>\r
+ * Copyright 2001 - 2005 Eric Kohl\r
+ */\r
+\r
+#include "cmlib.h"\r
+#define NDEBUG\r
+#include <debug.h>\r
+\r
+static PHCELL __inline CMAPI\r
+HvpGetCellHeader(\r
+ PHHIVE RegistryHive,\r
+ HCELL_INDEX CellIndex)\r
+{\r
+ PVOID Block;\r
+\r
+ ASSERT(CellIndex != HCELL_NULL);\r
+ if (!RegistryHive->Flat)\r
+ {\r
+ ULONG CellType;\r
+ ULONG CellBlock;\r
+ ULONG CellOffset;\r
+\r
+ CellType = (CellIndex & HCELL_TYPE_MASK) >> HCELL_TYPE_SHIFT;\r
+ CellBlock = (CellIndex & HCELL_BLOCK_MASK) >> HCELL_BLOCK_SHIFT;\r
+ CellOffset = (CellIndex & HCELL_OFFSET_MASK) >> HCELL_OFFSET_SHIFT;\r
+ ASSERT(CellBlock < RegistryHive->Storage[CellType].Length);\r
+ Block = (PVOID)RegistryHive->Storage[CellType].BlockList[CellBlock].Block;\r
+ ASSERT(Block != NULL);\r
+ return (PVOID)((ULONG_PTR)Block + CellOffset);\r
+ }\r
+ else\r
+ {\r
+ ASSERT((CellIndex & HCELL_TYPE_MASK) == HvStable);\r
+ return (PVOID)((ULONG_PTR)RegistryHive->HiveHeader + HV_BLOCK_SIZE +\r
+ CellIndex);\r
+ }\r
+}\r
+\r
+PVOID CMAPI\r
+HvGetCell(\r
+ PHHIVE RegistryHive,\r
+ HCELL_INDEX CellIndex)\r
+{\r
+ return (PVOID)(HvpGetCellHeader(RegistryHive, CellIndex) + 1);\r
+}\r
+\r
+static LONG __inline CMAPI\r
+HvpGetCellFullSize(\r
+ PHHIVE RegistryHive,\r
+ PVOID Cell)\r
+{\r
+ return ((PHCELL)Cell - 1)->Size;\r
+}\r
+\r
+LONG CMAPI\r
+HvGetCellSize(\r
+ PHHIVE RegistryHive,\r
+ PVOID Cell)\r
+{\r
+ PHCELL CellHeader;\r
+\r
+ CellHeader = (PHCELL)Cell - 1;\r
+ if (CellHeader->Size < 0)\r
+ return CellHeader->Size + sizeof(HCELL);\r
+ else\r
+ return CellHeader->Size - sizeof(HCELL);\r
+}\r
+\r
+VOID CMAPI\r
+HvMarkCellDirty(\r
+ PHHIVE RegistryHive,\r
+ HCELL_INDEX CellIndex)\r
+{\r
+ LONG CellSize;\r
+ ULONG CellBlock;\r
+ ULONG CellLastBlock;\r
+\r
+ ASSERT(RegistryHive->ReadOnly == FALSE);\r
+\r
+ if ((CellIndex & HCELL_TYPE_MASK) >> HCELL_TYPE_SHIFT != HvStable)\r
+ return;\r
+\r
+ CellBlock = (CellIndex & HCELL_BLOCK_MASK) >> HCELL_BLOCK_SHIFT;\r
+ CellLastBlock = ((CellIndex + HV_BLOCK_SIZE - 1) & HCELL_BLOCK_MASK) >> HCELL_BLOCK_SHIFT;\r
+\r
+ CellSize = HvpGetCellFullSize(RegistryHive, HvGetCell(RegistryHive, CellIndex));\r
+ if (CellSize < 0)\r
+ CellSize = -CellSize;\r
+\r
+ RtlSetBits(&RegistryHive->DirtyVector,\r
+ CellBlock, CellLastBlock - CellBlock);\r
+}\r
+\r
+static ULONG __inline CMAPI\r
+HvpComputeFreeListIndex(\r
+ ULONG Size)\r
+{\r
+ ULONG Index;\r
+ static CCHAR FindFirstSet[256] = {\r
+ 0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,\r
+ 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,\r
+ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,\r
+ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,\r
+ 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,\r
+ 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,\r
+ 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,\r
+ 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,\r
+ 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,\r
+ 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,\r
+ 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,\r
+ 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,\r
+ 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,\r
+ 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,\r
+ 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,\r
+ 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7};\r
+\r
+ Index = (Size >> 3) - 1;\r
+ if (Index >= 16)\r
+ {\r
+ if (Index > 255)\r
+ Index = 23;\r
+ else\r
+ Index = FindFirstSet[Index] + 7;\r
+ }\r
+\r
+ return Index;\r
+}\r
+\r
+static NTSTATUS CMAPI\r
+HvpAddFree(\r
+ PHHIVE RegistryHive,\r
+ PHCELL FreeBlock,\r
+ HCELL_INDEX FreeIndex)\r
+{\r
+ PHCELL_INDEX FreeBlockData;\r
+ HV_STORAGE_TYPE Storage;\r
+ ULONG Index;\r
+\r
+ ASSERT(RegistryHive != NULL);\r
+ ASSERT(FreeBlock != NULL);\r
+\r
+ Storage = (FreeIndex & HCELL_TYPE_MASK) >> HCELL_TYPE_SHIFT;\r
+ Index = HvpComputeFreeListIndex((ULONG)FreeBlock->Size);\r
+\r
+ FreeBlockData = (PHCELL_INDEX)(FreeBlock + 1);\r
+ *FreeBlockData = RegistryHive->Storage[Storage].FreeDisplay[Index];\r
+ RegistryHive->Storage[Storage].FreeDisplay[Index] = FreeIndex;\r
+\r
+ /* FIXME: Eventually get rid of free bins. */\r
+\r
+ return STATUS_SUCCESS;\r
+}\r
+\r
+static VOID CMAPI\r
+HvpRemoveFree(\r
+ PHHIVE RegistryHive,\r
+ PHCELL CellBlock,\r
+ HCELL_INDEX CellIndex)\r
+{\r
+ PHCELL_INDEX FreeCellData;\r
+ PHCELL_INDEX pFreeCellOffset;\r
+ HV_STORAGE_TYPE Storage;\r
+ ULONG Index;\r
+\r
+ ASSERT(RegistryHive->ReadOnly == FALSE);\r
+\r
+ Storage = (CellIndex & HCELL_TYPE_MASK) >> HCELL_TYPE_SHIFT;\r
+ Index = HvpComputeFreeListIndex((ULONG)CellBlock->Size);\r
+\r
+ pFreeCellOffset = &RegistryHive->Storage[Storage].FreeDisplay[Index];\r
+ while (*pFreeCellOffset != HCELL_NULL)\r
+ {\r
+ FreeCellData = (PHCELL_INDEX)HvGetCell(RegistryHive, *pFreeCellOffset);\r
+ if (*pFreeCellOffset == CellIndex)\r
+ {\r
+ *pFreeCellOffset = *FreeCellData;\r
+ return;\r
+ }\r
+ pFreeCellOffset = FreeCellData;\r
+ }\r
+\r
+ ASSERT(FALSE);\r
+}\r
+\r
+static HCELL_INDEX CMAPI\r
+HvpFindFree(\r
+ PHHIVE RegistryHive,\r
+ ULONG Size,\r
+ HV_STORAGE_TYPE Storage)\r
+{\r
+ PHCELL_INDEX FreeCellData;\r
+ HCELL_INDEX FreeCellOffset;\r
+ PHCELL_INDEX pFreeCellOffset;\r
+ ULONG Index;\r
+\r
+ for (Index = HvpComputeFreeListIndex(Size); Index < 24; Index++)\r
+ {\r
+ pFreeCellOffset = &RegistryHive->Storage[Storage].FreeDisplay[Index];\r
+ while (*pFreeCellOffset != HCELL_NULL)\r
+ {\r
+ FreeCellData = (PHCELL_INDEX)HvGetCell(RegistryHive, *pFreeCellOffset);\r
+ if ((ULONG)HvpGetCellFullSize(RegistryHive, FreeCellData) >= Size)\r
+ {\r
+ FreeCellOffset = *pFreeCellOffset;\r
+ *pFreeCellOffset = *FreeCellData;\r
+ return FreeCellOffset;\r
+ }\r
+ pFreeCellOffset = FreeCellData;\r
+ }\r
+ }\r
+\r
+ return HCELL_NULL;\r
+}\r
+\r
+NTSTATUS CMAPI\r
+HvpCreateHiveFreeCellList(\r
+ PHHIVE Hive)\r
+{\r
+ HCELL_INDEX BlockOffset;\r
+ PHCELL FreeBlock;\r
+ ULONG BlockIndex;\r
+ ULONG FreeOffset;\r
+ PHBIN Bin;\r
+ NTSTATUS Status;\r
+ ULONG Index;\r
+\r
+ /* Initialize the free cell list */\r
+ for (Index = 0; Index < 24; Index++)\r
+ {\r
+ Hive->Storage[HvStable].FreeDisplay[Index] = HCELL_NULL;\r
+ Hive->Storage[HvVolatile].FreeDisplay[Index] = HCELL_NULL;\r
+ }\r
+\r
+ BlockOffset = 0;\r
+ BlockIndex = 0;\r
+ while (BlockIndex < Hive->Storage[HvStable].Length)\r
+ {\r
+ Bin = (PHBIN)Hive->Storage[HvStable].BlockList[BlockIndex].Bin;\r
+\r
+ /* Search free blocks and add to list */\r
+ FreeOffset = sizeof(HBIN);\r
+ while (FreeOffset < Bin->Size)\r
+ {\r
+ FreeBlock = (PHCELL)((ULONG_PTR)Bin + FreeOffset);\r
+ if (FreeBlock->Size > 0)\r
+ {\r
+ Status = HvpAddFree(Hive, FreeBlock, Bin->FileOffset + FreeOffset);\r
+ if (!NT_SUCCESS(Status))\r
+ return Status;\r
+\r
+ FreeOffset += FreeBlock->Size;\r
+ }\r
+ else\r
+ {\r
+ FreeOffset -= FreeBlock->Size;\r
+ }\r
+ }\r
+\r
+ BlockIndex += Bin->Size / HV_BLOCK_SIZE;\r
+ BlockOffset += Bin->Size;\r
+ }\r
+\r
+ return STATUS_SUCCESS;\r
+}\r
+\r
+HCELL_INDEX CMAPI\r
+HvAllocateCell(\r
+ PHHIVE RegistryHive,\r
+ ULONG Size,\r
+ HV_STORAGE_TYPE Storage)\r
+{\r
+ PHCELL FreeCell;\r
+ HCELL_INDEX FreeCellOffset;\r
+ PHCELL NewCell;\r
+ PHBIN Bin;\r
+\r
+ ASSERT(RegistryHive->ReadOnly == FALSE);\r
+\r
+ /* Round to 16 bytes multiple. */\r
+ Size = ROUND_UP(Size + sizeof(HCELL), 16);\r
+\r
+ /* First search in free blocks. */\r
+ FreeCellOffset = HvpFindFree(RegistryHive, Size, Storage);\r
+\r
+ /* If no free cell was found we need to extend the hive file. */\r
+ if (FreeCellOffset == HCELL_NULL)\r
+ {\r
+ Bin = HvpAddBin(RegistryHive, Size, Storage);\r
+ if (Bin == NULL)\r
+ return HCELL_NULL;\r
+ FreeCellOffset = Bin->FileOffset + sizeof(HBIN);\r
+ FreeCellOffset |= Storage << HCELL_TYPE_SHIFT;\r
+ }\r
+\r
+ FreeCell = HvpGetCellHeader(RegistryHive, FreeCellOffset);\r
+\r
+ /* Split the block in two parts */\r
+ /* FIXME: There is some minimal cell size that we must respect. */\r
+ if ((ULONG)FreeCell->Size > Size + sizeof(HCELL_INDEX))\r
+ {\r
+ NewCell = (PHCELL)((ULONG_PTR)FreeCell + Size);\r
+ NewCell->Size = FreeCell->Size - Size;\r
+ FreeCell->Size = Size;\r
+ HvpAddFree(RegistryHive, NewCell, FreeCellOffset + Size);\r
+ if (Storage == HvStable)\r
+ HvMarkCellDirty(RegistryHive, FreeCellOffset + Size);\r
+ }\r
+\r
+ if (Storage == HvStable)\r
+ HvMarkCellDirty(RegistryHive, FreeCellOffset);\r
+ FreeCell->Size = -FreeCell->Size;\r
+ RtlZeroMemory(FreeCell + 1, Size - sizeof(HCELL));\r
+\r
+ return FreeCellOffset;\r
+}\r
+\r
+HCELL_INDEX CMAPI\r
+HvReallocateCell(\r
+ PHHIVE RegistryHive,\r
+ HCELL_INDEX CellIndex,\r
+ ULONG Size)\r
+{\r
+ PVOID OldCell;\r
+ PVOID NewCell;\r
+ LONG OldCellSize;\r
+ HCELL_INDEX NewCellIndex;\r
+ HV_STORAGE_TYPE Storage;\r
+\r
+ ASSERT(CellIndex != HCELL_NULL);\r
+\r
+ Storage = (CellIndex & HCELL_TYPE_MASK) >> HCELL_TYPE_SHIFT;\r
+\r
+ OldCell = HvGetCell(RegistryHive, CellIndex);\r
+ OldCellSize = HvGetCellSize(RegistryHive, OldCell);\r
+ ASSERT(OldCellSize < 0);\r
+ \r
+ /*\r
+ * If new data size is larger than the current, destroy current\r
+ * data block and allocate a new one.\r
+ *\r
+ * FIXME: Merge with adjacent free cell if possible.\r
+ * FIXME: Implement shrinking.\r
+ */\r
+ if (Size > (ULONG)-OldCellSize)\r
+ {\r
+ NewCellIndex = HvAllocateCell(RegistryHive, Size, Storage);\r
+ if (NewCellIndex == HCELL_NULL)\r
+ return HCELL_NULL;\r
+\r
+ NewCell = HvGetCell(RegistryHive, NewCellIndex);\r
+ RtlCopyMemory(NewCell, OldCell, (SIZE_T)-OldCellSize);\r
+ \r
+ HvFreeCell(RegistryHive, CellIndex);\r
+\r
+ return NewCellIndex;\r
+ }\r
+\r
+ return CellIndex;\r
+}\r
+\r
+VOID CMAPI\r
+HvFreeCell(\r
+ PHHIVE RegistryHive,\r
+ HCELL_INDEX CellIndex)\r
+{\r
+ PHCELL Free;\r
+ PHCELL Neighbor;\r
+ PHBIN Bin;\r
+ ULONG CellType;\r
+ ULONG CellBlock;\r
+\r
+ ASSERT(RegistryHive->ReadOnly == FALSE);\r
+ \r
+ Free = HvpGetCellHeader(RegistryHive, CellIndex);\r
+\r
+ ASSERT(Free->Size < 0); \r
+ \r
+ Free->Size = -Free->Size;\r
+\r
+ CellType = (CellIndex & HCELL_TYPE_MASK) >> HCELL_TYPE_SHIFT;\r
+ CellBlock = (CellIndex & HCELL_BLOCK_MASK) >> HCELL_BLOCK_SHIFT;\r
+\r
+ /* FIXME: Merge free blocks */\r
+ Bin = (PHBIN)RegistryHive->Storage[CellType].BlockList[CellBlock].Bin;\r
+\r
+ if ((CellIndex & ~HCELL_TYPE_MASK) + Free->Size <\r
+ Bin->FileOffset + Bin->Size)\r
+ {\r
+ Neighbor = (PHCELL)((ULONG_PTR)Free + Free->Size);\r
+ if (Neighbor->Size > 0)\r
+ {\r
+ HvpRemoveFree(RegistryHive, Neighbor,\r
+ ((HCELL_INDEX)((ULONG_PTR)Neighbor - (ULONG_PTR)Bin +\r
+ Bin->FileOffset)) | (CellIndex & HCELL_TYPE_MASK));\r
+ Free->Size += Neighbor->Size;\r
+ }\r
+ }\r
+\r
+ Neighbor = (PHCELL)(Bin + 1);\r
+ while (Neighbor < Free)\r
+ {\r
+ if (Neighbor->Size > 0)\r
+ {\r
+ if ((ULONG_PTR)Neighbor + Neighbor->Size == (ULONG_PTR)Free)\r
+ {\r
+ Neighbor->Size += Free->Size;\r
+ if (CellType == HvStable)\r
+ HvMarkCellDirty(RegistryHive,\r
+ (HCELL_INDEX)((ULONG_PTR)Neighbor - (ULONG_PTR)Bin +\r
+ Bin->FileOffset));\r
+ return;\r
+ }\r
+ Neighbor = (PHCELL)((ULONG_PTR)Neighbor + Neighbor->Size);\r
+ }\r
+ else\r
+ {\r
+ Neighbor = (PHCELL)((ULONG_PTR)Neighbor - Neighbor->Size);\r
+ }\r
+ }\r
+\r
+ /* Add block to the list of free blocks */\r
+ HvpAddFree(RegistryHive, Free, CellIndex);\r
+\r
+ if (CellType == HvStable)\r
+ HvMarkCellDirty(RegistryHive, CellIndex);\r
+}\r