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 %b\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
[256] = {
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,
161 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
162 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
163 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
164 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
165 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
166 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
167 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
168 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7};
170 Index
= (Size
>> 3) - 1;
176 Index
= FindFirstSet
[Index
] + 7;
182 static NTSTATUS CMAPI
186 HCELL_INDEX FreeIndex
)
188 PHCELL_INDEX FreeBlockData
;
189 HSTORAGE_TYPE Storage
;
192 ASSERT(RegistryHive
!= NULL
);
193 ASSERT(FreeBlock
!= NULL
);
195 Storage
= (FreeIndex
& HCELL_TYPE_MASK
) >> HCELL_TYPE_SHIFT
;
196 Index
= HvpComputeFreeListIndex((ULONG
)FreeBlock
->Size
);
198 FreeBlockData
= (PHCELL_INDEX
)(FreeBlock
+ 1);
199 *FreeBlockData
= RegistryHive
->Storage
[Storage
].FreeDisplay
[Index
];
200 RegistryHive
->Storage
[Storage
].FreeDisplay
[Index
] = FreeIndex
;
202 /* FIXME: Eventually get rid of free bins. */
204 return STATUS_SUCCESS
;
211 HCELL_INDEX CellIndex
)
213 PHCELL_INDEX FreeCellData
;
214 PHCELL_INDEX pFreeCellOffset
;
215 HSTORAGE_TYPE Storage
;
216 ULONG Index
, FreeListIndex
;
218 ASSERT(RegistryHive
->ReadOnly
== FALSE
);
220 Storage
= (CellIndex
& HCELL_TYPE_MASK
) >> HCELL_TYPE_SHIFT
;
221 Index
= HvpComputeFreeListIndex((ULONG
)CellBlock
->Size
);
223 pFreeCellOffset
= &RegistryHive
->Storage
[Storage
].FreeDisplay
[Index
];
224 while (*pFreeCellOffset
!= HCELL_NIL
)
226 FreeCellData
= (PHCELL_INDEX
)HvGetCell(RegistryHive
, *pFreeCellOffset
);
227 if (*pFreeCellOffset
== CellIndex
)
229 *pFreeCellOffset
= *FreeCellData
;
232 pFreeCellOffset
= FreeCellData
;
235 /* Something bad happened, print a useful trace info and bugcheck */
236 CMLTRACE(CMLIB_HCELL_DEBUG
, "-- beginning of HvpRemoveFree trace --\n");
237 CMLTRACE(CMLIB_HCELL_DEBUG
, "block we are about to free: %08x\n", CellIndex
);
238 CMLTRACE(CMLIB_HCELL_DEBUG
, "chosen free list index: %u\n", Index
);
239 for (FreeListIndex
= 0; FreeListIndex
< 24; FreeListIndex
++)
241 CMLTRACE(CMLIB_HCELL_DEBUG
, "free list [%u]: ", FreeListIndex
);
242 pFreeCellOffset
= &RegistryHive
->Storage
[Storage
].FreeDisplay
[FreeListIndex
];
243 while (*pFreeCellOffset
!= HCELL_NIL
)
245 CMLTRACE(CMLIB_HCELL_DEBUG
, "%08x ", *pFreeCellOffset
);
246 FreeCellData
= (PHCELL_INDEX
)HvGetCell(RegistryHive
, *pFreeCellOffset
);
247 pFreeCellOffset
= FreeCellData
;
249 CMLTRACE(CMLIB_HCELL_DEBUG
, "\n");
251 CMLTRACE(CMLIB_HCELL_DEBUG
, "-- end of HvpRemoveFree trace --\n");
256 static HCELL_INDEX CMAPI
260 HSTORAGE_TYPE Storage
)
262 PHCELL_INDEX FreeCellData
;
263 HCELL_INDEX FreeCellOffset
;
264 PHCELL_INDEX pFreeCellOffset
;
267 for (Index
= HvpComputeFreeListIndex(Size
); Index
< 24; Index
++)
269 pFreeCellOffset
= &RegistryHive
->Storage
[Storage
].FreeDisplay
[Index
];
270 while (*pFreeCellOffset
!= HCELL_NIL
)
272 FreeCellData
= (PHCELL_INDEX
)HvGetCell(RegistryHive
, *pFreeCellOffset
);
273 if ((ULONG
)HvpGetCellFullSize(RegistryHive
, FreeCellData
) >= Size
)
275 FreeCellOffset
= *pFreeCellOffset
;
276 *pFreeCellOffset
= *FreeCellData
;
277 return FreeCellOffset
;
279 pFreeCellOffset
= FreeCellData
;
287 HvpCreateHiveFreeCellList(
290 HCELL_INDEX BlockOffset
;
298 /* Initialize the free cell list */
299 for (Index
= 0; Index
< 24; Index
++)
301 Hive
->Storage
[Stable
].FreeDisplay
[Index
] = HCELL_NIL
;
302 Hive
->Storage
[Volatile
].FreeDisplay
[Index
] = HCELL_NIL
;
307 while (BlockIndex
< Hive
->Storage
[Stable
].Length
)
309 Bin
= (PHBIN
)Hive
->Storage
[Stable
].BlockList
[BlockIndex
].BinAddress
;
311 /* Search free blocks and add to list */
312 FreeOffset
= sizeof(HBIN
);
313 while (FreeOffset
< Bin
->Size
)
315 FreeBlock
= (PHCELL
)((ULONG_PTR
)Bin
+ FreeOffset
);
316 if (FreeBlock
->Size
> 0)
318 Status
= HvpAddFree(Hive
, FreeBlock
, Bin
->FileOffset
+ FreeOffset
);
319 if (!NT_SUCCESS(Status
))
322 FreeOffset
+= FreeBlock
->Size
;
326 FreeOffset
-= FreeBlock
->Size
;
330 BlockIndex
+= Bin
->Size
/ HV_BLOCK_SIZE
;
331 BlockOffset
+= Bin
->Size
;
334 return STATUS_SUCCESS
;
341 HSTORAGE_TYPE Storage
,
342 HCELL_INDEX Vicinity
)
345 HCELL_INDEX FreeCellOffset
;
349 ASSERT(RegistryHive
->ReadOnly
== FALSE
);
351 CMLTRACE(CMLIB_HCELL_DEBUG
, "%s - Hive %p, Size %x, %s, Vicinity %08lx\n",
352 __FUNCTION__
, RegistryHive
, Size
, (Storage
== 0) ? "Stable" : "Volatile", Vicinity
);
354 /* Round to 16 bytes multiple. */
355 Size
= ROUND_UP(Size
+ sizeof(HCELL
), 16);
357 /* First search in free blocks. */
358 FreeCellOffset
= HvpFindFree(RegistryHive
, Size
, Storage
);
360 /* If no free cell was found we need to extend the hive file. */
361 if (FreeCellOffset
== HCELL_NIL
)
363 Bin
= HvpAddBin(RegistryHive
, Size
, Storage
);
366 FreeCellOffset
= Bin
->FileOffset
+ sizeof(HBIN
);
367 FreeCellOffset
|= Storage
<< HCELL_TYPE_SHIFT
;
370 FreeCell
= HvpGetCellHeader(RegistryHive
, FreeCellOffset
);
372 /* Split the block in two parts */
374 /* The free block that is created has to be at least
375 sizeof(HCELL) + sizeof(HCELL_INDEX) big, so that free
376 cell list code can work. Moreover we round cell sizes
377 to 16 bytes, so creating a smaller block would result in
378 a cell that would never be allocated. */
379 if ((ULONG
)FreeCell
->Size
> Size
+ 16)
381 NewCell
= (PHCELL
)((ULONG_PTR
)FreeCell
+ Size
);
382 NewCell
->Size
= FreeCell
->Size
- Size
;
383 FreeCell
->Size
= Size
;
384 HvpAddFree(RegistryHive
, NewCell
, FreeCellOffset
+ Size
);
385 if (Storage
== Stable
)
386 HvMarkCellDirty(RegistryHive
, FreeCellOffset
+ Size
, FALSE
);
389 if (Storage
== Stable
)
390 HvMarkCellDirty(RegistryHive
, FreeCellOffset
, FALSE
);
391 FreeCell
->Size
= -FreeCell
->Size
;
392 RtlZeroMemory(FreeCell
+ 1, Size
- sizeof(HCELL
));
394 CMLTRACE(CMLIB_HCELL_DEBUG
, "%s - CellIndex %08lx\n",
395 __FUNCTION__
, FreeCellOffset
);
397 return FreeCellOffset
;
403 HCELL_INDEX CellIndex
,
409 HCELL_INDEX NewCellIndex
;
410 HSTORAGE_TYPE Storage
;
412 ASSERT(CellIndex
!= HCELL_NIL
);
414 CMLTRACE(CMLIB_HCELL_DEBUG
, "%s - Hive %p, CellIndex %08lx, Size %x\n",
415 __FUNCTION__
, RegistryHive
, CellIndex
, Size
);
417 Storage
= (CellIndex
& HCELL_TYPE_MASK
) >> HCELL_TYPE_SHIFT
;
419 OldCell
= HvGetCell(RegistryHive
, CellIndex
);
420 OldCellSize
= HvGetCellSize(RegistryHive
, OldCell
);
421 ASSERT(OldCellSize
> 0);
424 * If new data size is larger than the current, destroy current
425 * data block and allocate a new one.
427 * FIXME: Merge with adjacent free cell if possible.
428 * FIXME: Implement shrinking.
430 if (Size
> (ULONG
)OldCellSize
)
432 NewCellIndex
= HvAllocateCell(RegistryHive
, Size
, Storage
, HCELL_NIL
);
433 if (NewCellIndex
== HCELL_NIL
)
436 NewCell
= HvGetCell(RegistryHive
, NewCellIndex
);
437 RtlCopyMemory(NewCell
, OldCell
, (SIZE_T
)OldCellSize
);
439 HvFreeCell(RegistryHive
, CellIndex
);
450 HCELL_INDEX CellIndex
)
458 ASSERT(RegistryHive
->ReadOnly
== FALSE
);
460 CMLTRACE(CMLIB_HCELL_DEBUG
, "%s - Hive %p, CellIndex %08lx\n",
461 __FUNCTION__
, RegistryHive
, CellIndex
);
463 Free
= HvpGetCellHeader(RegistryHive
, CellIndex
);
465 ASSERT(Free
->Size
< 0);
467 Free
->Size
= -Free
->Size
;
469 CellType
= (CellIndex
& HCELL_TYPE_MASK
) >> HCELL_TYPE_SHIFT
;
470 CellBlock
= (CellIndex
& HCELL_BLOCK_MASK
) >> HCELL_BLOCK_SHIFT
;
472 /* FIXME: Merge free blocks */
473 Bin
= (PHBIN
)RegistryHive
->Storage
[CellType
].BlockList
[CellBlock
].BinAddress
;
475 if ((CellIndex
& ~HCELL_TYPE_MASK
) + Free
->Size
<
476 Bin
->FileOffset
+ Bin
->Size
)
478 Neighbor
= (PHCELL
)((ULONG_PTR
)Free
+ Free
->Size
);
479 if (Neighbor
->Size
> 0)
481 HvpRemoveFree(RegistryHive
, Neighbor
,
482 ((HCELL_INDEX
)((ULONG_PTR
)Neighbor
- (ULONG_PTR
)Bin
+
483 Bin
->FileOffset
)) | (CellIndex
& HCELL_TYPE_MASK
));
484 Free
->Size
+= Neighbor
->Size
;
488 Neighbor
= (PHCELL
)(Bin
+ 1);
489 while (Neighbor
< Free
)
491 if (Neighbor
->Size
> 0)
493 if ((ULONG_PTR
)Neighbor
+ Neighbor
->Size
== (ULONG_PTR
)Free
)
495 HCELL_INDEX NeighborCellIndex
=
496 (HCELL_INDEX
)((ULONG_PTR
)Neighbor
- (ULONG_PTR
)Bin
+
497 Bin
->FileOffset
) | (CellIndex
& HCELL_TYPE_MASK
);
499 if (HvpComputeFreeListIndex(Neighbor
->Size
) !=
500 HvpComputeFreeListIndex(Neighbor
->Size
+ Free
->Size
))
502 HvpRemoveFree(RegistryHive
, Neighbor
, NeighborCellIndex
);
503 Neighbor
->Size
+= Free
->Size
;
504 HvpAddFree(RegistryHive
, Neighbor
, NeighborCellIndex
);
507 Neighbor
->Size
+= Free
->Size
;
509 if (CellType
== Stable
)
510 HvMarkCellDirty(RegistryHive
, NeighborCellIndex
, FALSE
);
514 Neighbor
= (PHCELL
)((ULONG_PTR
)Neighbor
+ Neighbor
->Size
);
518 Neighbor
= (PHCELL
)((ULONG_PTR
)Neighbor
- Neighbor
->Size
);
522 /* Add block to the list of free blocks */
523 HvpAddFree(RegistryHive
, Free
, CellIndex
);
525 if (CellType
== Stable
)
526 HvMarkCellDirty(RegistryHive
, CellIndex
, FALSE
);
531 HvTrackCellRef(PHV_TRACK_CELL_REF CellRef
,
538 ASSERT(Cell
!= HCELL_NIL
);
541 if (CellRef
->StaticCount
< STATIC_CELL_PAIR_COUNT
)
544 CellRef
->StaticArray
[CellRef
->StaticCount
].Hive
= Hive
;
545 CellRef
->StaticArray
[CellRef
->StaticCount
].Cell
= Cell
;
546 CellRef
->StaticCount
++;
551 DPRINT1("ERROR: Too many references\n");
558 HvReleaseFreeCellRefArray(PHV_TRACK_CELL_REF CellRef
)
563 /* Any references? */
564 if (CellRef
->StaticCount
> 0)
567 ASSERT(CellRef
->StaticCount
<= STATIC_CELL_PAIR_COUNT
);
570 for (i
= 0; i
< CellRef
->StaticCount
;i
++)
573 HvReleaseCell(CellRef
->StaticArray
[i
].Hive
,
574 CellRef
->StaticArray
[i
].Cell
);
578 CellRef
->StaticCount
= 0;