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
12 static __inline PHCELL CMAPI
15 HCELL_INDEX CellIndex
)
19 CMLTRACE(CMLIB_HCELL_DEBUG
, "%s - Hive %p, CellIndex %08lx\n",
20 __FUNCTION__
, RegistryHive
, CellIndex
);
22 ASSERT(CellIndex
!= HCELL_NIL
);
23 if (!RegistryHive
->Flat
)
29 CellType
= (CellIndex
& HCELL_TYPE_MASK
) >> HCELL_TYPE_SHIFT
;
30 CellBlock
= (CellIndex
& HCELL_BLOCK_MASK
) >> HCELL_BLOCK_SHIFT
;
31 CellOffset
= (CellIndex
& HCELL_OFFSET_MASK
) >> HCELL_OFFSET_SHIFT
;
32 ASSERT(CellBlock
< RegistryHive
->Storage
[CellType
].Length
);
33 Block
= (PVOID
)RegistryHive
->Storage
[CellType
].BlockList
[CellBlock
].BlockAddress
;
34 ASSERT(Block
!= NULL
);
35 return (PVOID
)((ULONG_PTR
)Block
+ CellOffset
);
39 ASSERT((CellIndex
& HCELL_TYPE_MASK
) == Stable
);
40 return (PVOID
)((ULONG_PTR
)RegistryHive
->BaseBlock
+ HV_BLOCK_SIZE
+
46 HvIsCellAllocated(IN PHHIVE RegistryHive
,
47 IN HCELL_INDEX CellIndex
)
51 /* If it's a flat hive, the cell is always allocated */
52 if (RegistryHive
->Flat
)
55 /* Otherwise, get the type and make sure it's valid */
56 Type
= HvGetCellType(CellIndex
);
57 Block
= HvGetCellBlock(CellIndex
);
58 if (Block
>= RegistryHive
->Storage
[Type
].Length
)
61 /* Try to get the cell block */
62 if (RegistryHive
->Storage
[Type
].BlockList
[Block
].BlockAddress
)
65 /* No valid block, fail */
72 HCELL_INDEX CellIndex
)
74 return (PVOID
)(HvpGetCellHeader(RegistryHive
, CellIndex
) + 1);
77 static __inline LONG CMAPI
82 UNREFERENCED_PARAMETER(RegistryHive
);
83 return ((PHCELL
)Cell
- 1)->Size
;
87 HvGetCellSize(IN PHHIVE Hive
,
93 UNREFERENCED_PARAMETER(Hive
);
95 CellHeader
= (PHCELL
)Address
- 1;
96 Size
= CellHeader
->Size
* -1;
97 Size
-= sizeof(HCELL
);
104 HCELL_INDEX CellIndex
,
110 ASSERT(RegistryHive
->ReadOnly
== FALSE
);
112 CMLTRACE(CMLIB_HCELL_DEBUG
, "%s - Hive %p, CellIndex %08lx, HoldingLock %u\n",
113 __FUNCTION__
, RegistryHive
, CellIndex
, HoldingLock
);
115 if ((CellIndex
& HCELL_TYPE_MASK
) >> HCELL_TYPE_SHIFT
!= Stable
)
118 CellBlock
= (CellIndex
& HCELL_BLOCK_MASK
) >> HCELL_BLOCK_SHIFT
;
119 CellLastBlock
= ((CellIndex
+ HV_BLOCK_SIZE
- 1) & HCELL_BLOCK_MASK
) >> HCELL_BLOCK_SHIFT
;
121 RtlSetBits(&RegistryHive
->DirtyVector
,
122 CellBlock
, CellLastBlock
- CellBlock
);
127 HvIsCellDirty(IN PHHIVE Hive
,
130 BOOLEAN IsDirty
= FALSE
;
133 ASSERT(Hive
->ReadOnly
== FALSE
);
135 /* Volatile cells are always "dirty" */
136 if (HvGetCellType(Cell
) == Volatile
)
139 /* Check if the dirty bit is set */
140 if (RtlCheckBit(&Hive
->DirtyVector
, Cell
/ HV_BLOCK_SIZE
))
143 /* Return result as boolean*/
147 static __inline ULONG CMAPI
148 HvpComputeFreeListIndex(
152 static CCHAR FindFirstSet
[128] = {
153 0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
154 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
155 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
156 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
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 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6};
162 ASSERT(Size
>= (1 << 3));
163 Index
= (Size
>> 3) - 1;
169 Index
= FindFirstSet
[Index
] + 16;
175 static NTSTATUS CMAPI
179 HCELL_INDEX FreeIndex
)
181 PHCELL_INDEX FreeBlockData
;
182 HSTORAGE_TYPE Storage
;
185 ASSERT(RegistryHive
!= NULL
);
186 ASSERT(FreeBlock
!= NULL
);
188 Storage
= (FreeIndex
& HCELL_TYPE_MASK
) >> HCELL_TYPE_SHIFT
;
189 Index
= HvpComputeFreeListIndex((ULONG
)FreeBlock
->Size
);
191 FreeBlockData
= (PHCELL_INDEX
)(FreeBlock
+ 1);
192 *FreeBlockData
= RegistryHive
->Storage
[Storage
].FreeDisplay
[Index
];
193 RegistryHive
->Storage
[Storage
].FreeDisplay
[Index
] = FreeIndex
;
195 /* FIXME: Eventually get rid of free bins. */
197 return STATUS_SUCCESS
;
204 HCELL_INDEX CellIndex
)
206 PHCELL_INDEX FreeCellData
;
207 PHCELL_INDEX pFreeCellOffset
;
208 HSTORAGE_TYPE Storage
;
209 ULONG Index
, FreeListIndex
;
211 ASSERT(RegistryHive
->ReadOnly
== FALSE
);
213 Storage
= (CellIndex
& HCELL_TYPE_MASK
) >> HCELL_TYPE_SHIFT
;
214 Index
= HvpComputeFreeListIndex((ULONG
)CellBlock
->Size
);
216 pFreeCellOffset
= &RegistryHive
->Storage
[Storage
].FreeDisplay
[Index
];
217 while (*pFreeCellOffset
!= HCELL_NIL
)
219 FreeCellData
= (PHCELL_INDEX
)HvGetCell(RegistryHive
, *pFreeCellOffset
);
220 if (*pFreeCellOffset
== CellIndex
)
222 *pFreeCellOffset
= *FreeCellData
;
225 pFreeCellOffset
= FreeCellData
;
228 /* Something bad happened, print a useful trace info and bugcheck */
229 CMLTRACE(CMLIB_HCELL_DEBUG
, "-- beginning of HvpRemoveFree trace --\n");
230 CMLTRACE(CMLIB_HCELL_DEBUG
, "block we are about to free: %08x\n", CellIndex
);
231 CMLTRACE(CMLIB_HCELL_DEBUG
, "chosen free list index: %u\n", Index
);
232 for (FreeListIndex
= 0; FreeListIndex
< 24; FreeListIndex
++)
234 CMLTRACE(CMLIB_HCELL_DEBUG
, "free list [%u]: ", FreeListIndex
);
235 pFreeCellOffset
= &RegistryHive
->Storage
[Storage
].FreeDisplay
[FreeListIndex
];
236 while (*pFreeCellOffset
!= HCELL_NIL
)
238 CMLTRACE(CMLIB_HCELL_DEBUG
, "%08x ", *pFreeCellOffset
);
239 FreeCellData
= (PHCELL_INDEX
)HvGetCell(RegistryHive
, *pFreeCellOffset
);
240 pFreeCellOffset
= FreeCellData
;
242 CMLTRACE(CMLIB_HCELL_DEBUG
, "\n");
244 CMLTRACE(CMLIB_HCELL_DEBUG
, "-- end of HvpRemoveFree trace --\n");
249 static HCELL_INDEX CMAPI
253 HSTORAGE_TYPE Storage
)
255 PHCELL_INDEX FreeCellData
;
256 HCELL_INDEX FreeCellOffset
;
257 PHCELL_INDEX pFreeCellOffset
;
260 for (Index
= HvpComputeFreeListIndex(Size
); Index
< 24; Index
++)
262 pFreeCellOffset
= &RegistryHive
->Storage
[Storage
].FreeDisplay
[Index
];
263 while (*pFreeCellOffset
!= HCELL_NIL
)
265 FreeCellData
= (PHCELL_INDEX
)HvGetCell(RegistryHive
, *pFreeCellOffset
);
266 if ((ULONG
)HvpGetCellFullSize(RegistryHive
, FreeCellData
) >= Size
)
268 FreeCellOffset
= *pFreeCellOffset
;
269 *pFreeCellOffset
= *FreeCellData
;
270 return FreeCellOffset
;
272 pFreeCellOffset
= FreeCellData
;
280 HvpCreateHiveFreeCellList(
283 HCELL_INDEX BlockOffset
;
291 /* Initialize the free cell list */
292 for (Index
= 0; Index
< 24; Index
++)
294 Hive
->Storage
[Stable
].FreeDisplay
[Index
] = HCELL_NIL
;
295 Hive
->Storage
[Volatile
].FreeDisplay
[Index
] = HCELL_NIL
;
300 while (BlockIndex
< Hive
->Storage
[Stable
].Length
)
302 Bin
= (PHBIN
)Hive
->Storage
[Stable
].BlockList
[BlockIndex
].BinAddress
;
304 /* Search free blocks and add to list */
305 FreeOffset
= sizeof(HBIN
);
306 while (FreeOffset
< Bin
->Size
)
308 FreeBlock
= (PHCELL
)((ULONG_PTR
)Bin
+ FreeOffset
);
309 if (FreeBlock
->Size
> 0)
311 Status
= HvpAddFree(Hive
, FreeBlock
, Bin
->FileOffset
+ FreeOffset
);
312 if (!NT_SUCCESS(Status
))
315 FreeOffset
+= FreeBlock
->Size
;
319 FreeOffset
-= FreeBlock
->Size
;
323 BlockIndex
+= Bin
->Size
/ HV_BLOCK_SIZE
;
324 BlockOffset
+= Bin
->Size
;
327 return STATUS_SUCCESS
;
334 HSTORAGE_TYPE Storage
,
335 HCELL_INDEX Vicinity
)
338 HCELL_INDEX FreeCellOffset
;
342 ASSERT(RegistryHive
->ReadOnly
== FALSE
);
344 CMLTRACE(CMLIB_HCELL_DEBUG
, "%s - Hive %p, Size %x, %s, Vicinity %08lx\n",
345 __FUNCTION__
, RegistryHive
, Size
, (Storage
== 0) ? "Stable" : "Volatile", Vicinity
);
347 /* Round to 16 bytes multiple. */
348 Size
= ROUND_UP(Size
+ sizeof(HCELL
), 16);
350 /* First search in free blocks. */
351 FreeCellOffset
= HvpFindFree(RegistryHive
, Size
, Storage
);
353 /* If no free cell was found we need to extend the hive file. */
354 if (FreeCellOffset
== HCELL_NIL
)
356 Bin
= HvpAddBin(RegistryHive
, Size
, Storage
);
359 FreeCellOffset
= Bin
->FileOffset
+ sizeof(HBIN
);
360 FreeCellOffset
|= Storage
<< HCELL_TYPE_SHIFT
;
363 FreeCell
= HvpGetCellHeader(RegistryHive
, FreeCellOffset
);
365 /* Split the block in two parts */
367 /* The free block that is created has to be at least
368 sizeof(HCELL) + sizeof(HCELL_INDEX) big, so that free
369 cell list code can work. Moreover we round cell sizes
370 to 16 bytes, so creating a smaller block would result in
371 a cell that would never be allocated. */
372 if ((ULONG
)FreeCell
->Size
> Size
+ 16)
374 NewCell
= (PHCELL
)((ULONG_PTR
)FreeCell
+ Size
);
375 NewCell
->Size
= FreeCell
->Size
- Size
;
376 FreeCell
->Size
= Size
;
377 HvpAddFree(RegistryHive
, NewCell
, FreeCellOffset
+ Size
);
378 if (Storage
== Stable
)
379 HvMarkCellDirty(RegistryHive
, FreeCellOffset
+ Size
, FALSE
);
382 if (Storage
== Stable
)
383 HvMarkCellDirty(RegistryHive
, FreeCellOffset
, FALSE
);
384 FreeCell
->Size
= -FreeCell
->Size
;
385 RtlZeroMemory(FreeCell
+ 1, Size
- sizeof(HCELL
));
387 CMLTRACE(CMLIB_HCELL_DEBUG
, "%s - CellIndex %08lx\n",
388 __FUNCTION__
, FreeCellOffset
);
390 return FreeCellOffset
;
396 HCELL_INDEX CellIndex
,
402 HCELL_INDEX NewCellIndex
;
403 HSTORAGE_TYPE Storage
;
405 ASSERT(CellIndex
!= HCELL_NIL
);
407 CMLTRACE(CMLIB_HCELL_DEBUG
, "%s - Hive %p, CellIndex %08lx, Size %x\n",
408 __FUNCTION__
, RegistryHive
, CellIndex
, Size
);
410 Storage
= (CellIndex
& HCELL_TYPE_MASK
) >> HCELL_TYPE_SHIFT
;
412 OldCell
= HvGetCell(RegistryHive
, CellIndex
);
413 OldCellSize
= HvGetCellSize(RegistryHive
, OldCell
);
414 ASSERT(OldCellSize
> 0);
417 * If new data size is larger than the current, destroy current
418 * data block and allocate a new one.
420 * FIXME: Merge with adjacent free cell if possible.
421 * FIXME: Implement shrinking.
423 if (Size
> (ULONG
)OldCellSize
)
425 NewCellIndex
= HvAllocateCell(RegistryHive
, Size
, Storage
, HCELL_NIL
);
426 if (NewCellIndex
== HCELL_NIL
)
429 NewCell
= HvGetCell(RegistryHive
, NewCellIndex
);
430 RtlCopyMemory(NewCell
, OldCell
, (SIZE_T
)OldCellSize
);
432 HvFreeCell(RegistryHive
, CellIndex
);
443 HCELL_INDEX CellIndex
)
451 ASSERT(RegistryHive
->ReadOnly
== FALSE
);
453 CMLTRACE(CMLIB_HCELL_DEBUG
, "%s - Hive %p, CellIndex %08lx\n",
454 __FUNCTION__
, RegistryHive
, CellIndex
);
456 Free
= HvpGetCellHeader(RegistryHive
, CellIndex
);
458 ASSERT(Free
->Size
< 0);
460 Free
->Size
= -Free
->Size
;
462 CellType
= (CellIndex
& HCELL_TYPE_MASK
) >> HCELL_TYPE_SHIFT
;
463 CellBlock
= (CellIndex
& HCELL_BLOCK_MASK
) >> HCELL_BLOCK_SHIFT
;
465 /* FIXME: Merge free blocks */
466 Bin
= (PHBIN
)RegistryHive
->Storage
[CellType
].BlockList
[CellBlock
].BinAddress
;
468 if ((CellIndex
& ~HCELL_TYPE_MASK
) + Free
->Size
<
469 Bin
->FileOffset
+ Bin
->Size
)
471 Neighbor
= (PHCELL
)((ULONG_PTR
)Free
+ Free
->Size
);
472 if (Neighbor
->Size
> 0)
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
;
481 Neighbor
= (PHCELL
)(Bin
+ 1);
482 while (Neighbor
< Free
)
484 if (Neighbor
->Size
> 0)
486 if ((ULONG_PTR
)Neighbor
+ Neighbor
->Size
== (ULONG_PTR
)Free
)
488 HCELL_INDEX NeighborCellIndex
=
489 (HCELL_INDEX
)((ULONG_PTR
)Neighbor
- (ULONG_PTR
)Bin
+
490 Bin
->FileOffset
) | (CellIndex
& HCELL_TYPE_MASK
);
492 if (HvpComputeFreeListIndex(Neighbor
->Size
) !=
493 HvpComputeFreeListIndex(Neighbor
->Size
+ Free
->Size
))
495 HvpRemoveFree(RegistryHive
, Neighbor
, NeighborCellIndex
);
496 Neighbor
->Size
+= Free
->Size
;
497 HvpAddFree(RegistryHive
, Neighbor
, NeighborCellIndex
);
500 Neighbor
->Size
+= Free
->Size
;
502 if (CellType
== Stable
)
503 HvMarkCellDirty(RegistryHive
, NeighborCellIndex
, FALSE
);
507 Neighbor
= (PHCELL
)((ULONG_PTR
)Neighbor
+ Neighbor
->Size
);
511 Neighbor
= (PHCELL
)((ULONG_PTR
)Neighbor
- Neighbor
->Size
);
515 /* Add block to the list of free blocks */
516 HvpAddFree(RegistryHive
, Free
, CellIndex
);
518 if (CellType
== Stable
)
519 HvMarkCellDirty(RegistryHive
, CellIndex
, FALSE
);
524 HvTrackCellRef(PHV_TRACK_CELL_REF CellRef
,
531 ASSERT(Cell
!= HCELL_NIL
);
534 if (CellRef
->StaticCount
< STATIC_CELL_PAIR_COUNT
)
537 CellRef
->StaticArray
[CellRef
->StaticCount
].Hive
= Hive
;
538 CellRef
->StaticArray
[CellRef
->StaticCount
].Cell
= Cell
;
539 CellRef
->StaticCount
++;
544 ASSERTMSG("ERROR: Too many references\n", FALSE
);
550 HvReleaseFreeCellRefArray(PHV_TRACK_CELL_REF CellRef
)
555 /* Any references? */
556 if (CellRef
->StaticCount
> 0)
559 ASSERT(CellRef
->StaticCount
<= STATIC_CELL_PAIR_COUNT
);
562 for (i
= 0; i
< CellRef
->StaticCount
;i
++)
565 HvReleaseCell(CellRef
->StaticArray
[i
].Hive
,
566 CellRef
->StaticArray
[i
].Cell
);
570 CellRef
->StaticCount
= 0;