-/*\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
+/*
+ * 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);
+}