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
)
25 ULONG CellType
= HvGetCellType(CellIndex
);
26 ULONG CellBlock
= HvGetCellBlock(CellIndex
);
27 ULONG CellOffset
= (CellIndex
& HCELL_OFFSET_MASK
) >> HCELL_OFFSET_SHIFT
;
29 ASSERT(CellBlock
< RegistryHive
->Storage
[CellType
].Length
);
30 Block
= (PVOID
)RegistryHive
->Storage
[CellType
].BlockList
[CellBlock
].BlockAddress
;
31 ASSERT(Block
!= NULL
);
32 return (PVOID
)((ULONG_PTR
)Block
+ CellOffset
);
36 ASSERT(HvGetCellType(CellIndex
) == Stable
);
37 return (PVOID
)((ULONG_PTR
)RegistryHive
->BaseBlock
+ HBLOCK_SIZE
+
43 HvIsCellAllocated(IN PHHIVE RegistryHive
,
44 IN HCELL_INDEX CellIndex
)
48 /* If it's a flat hive, the cell is always allocated */
49 if (RegistryHive
->Flat
)
52 /* Otherwise, get the type and make sure it's valid */
53 Type
= HvGetCellType(CellIndex
);
54 Block
= HvGetCellBlock(CellIndex
);
55 if (Block
>= RegistryHive
->Storage
[Type
].Length
)
58 /* Try to get the cell block */
59 if (RegistryHive
->Storage
[Type
].BlockList
[Block
].BlockAddress
)
62 /* No valid block, fail */
69 HCELL_INDEX CellIndex
)
71 ASSERT(CellIndex
!= HCELL_NIL
);
72 return (PVOID
)(HvpGetCellHeader(RegistryHive
, CellIndex
) + 1);
75 static __inline LONG CMAPI
80 UNREFERENCED_PARAMETER(RegistryHive
);
81 return ((PHCELL
)Cell
- 1)->Size
;
85 HvGetCellSize(IN PHHIVE Hive
,
91 UNREFERENCED_PARAMETER(Hive
);
93 CellHeader
= (PHCELL
)Address
- 1;
94 Size
= CellHeader
->Size
* -1;
95 Size
-= sizeof(HCELL
);
102 HCELL_INDEX CellIndex
,
108 ASSERT(RegistryHive
->ReadOnly
== FALSE
);
110 CMLTRACE(CMLIB_HCELL_DEBUG
, "%s - Hive %p, CellIndex %08lx, HoldingLock %u\n",
111 __FUNCTION__
, RegistryHive
, CellIndex
, HoldingLock
);
113 if (HvGetCellType(CellIndex
) != Stable
)
116 CellBlock
= HvGetCellBlock(CellIndex
);
117 CellLastBlock
= HvGetCellBlock(CellIndex
+ HBLOCK_SIZE
- 1);
119 RtlSetBits(&RegistryHive
->DirtyVector
,
120 CellBlock
, CellLastBlock
- CellBlock
);
121 RegistryHive
->DirtyCount
++;
126 HvIsCellDirty(IN PHHIVE Hive
,
129 BOOLEAN IsDirty
= FALSE
;
132 ASSERT(Hive
->ReadOnly
== FALSE
);
134 /* Volatile cells are always "dirty" */
135 if (HvGetCellType(Cell
) == Volatile
)
138 /* Check if the dirty bit is set */
139 if (RtlCheckBit(&Hive
->DirtyVector
, Cell
/ HBLOCK_SIZE
))
142 /* Return result as boolean*/
146 static __inline ULONG CMAPI
147 HvpComputeFreeListIndex(
151 static CCHAR FindFirstSet
[128] = {
152 0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
153 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
154 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
155 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
156 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
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};
161 ASSERT(Size
>= (1 << 3));
162 Index
= (Size
>> 3) - 1;
168 Index
= FindFirstSet
[Index
] + 16;
174 static NTSTATUS CMAPI
178 HCELL_INDEX FreeIndex
)
180 PHCELL_INDEX FreeBlockData
;
181 HSTORAGE_TYPE Storage
;
184 ASSERT(RegistryHive
!= NULL
);
185 ASSERT(FreeBlock
!= NULL
);
187 Storage
= HvGetCellType(FreeIndex
);
188 Index
= HvpComputeFreeListIndex((ULONG
)FreeBlock
->Size
);
190 FreeBlockData
= (PHCELL_INDEX
)(FreeBlock
+ 1);
191 *FreeBlockData
= RegistryHive
->Storage
[Storage
].FreeDisplay
[Index
];
192 RegistryHive
->Storage
[Storage
].FreeDisplay
[Index
] = FreeIndex
;
194 /* FIXME: Eventually get rid of free bins. */
196 return STATUS_SUCCESS
;
203 HCELL_INDEX CellIndex
)
205 PHCELL_INDEX FreeCellData
;
206 PHCELL_INDEX pFreeCellOffset
;
207 HSTORAGE_TYPE Storage
;
208 ULONG Index
, FreeListIndex
;
210 ASSERT(RegistryHive
->ReadOnly
== FALSE
);
212 Storage
= HvGetCellType(CellIndex
);
213 Index
= HvpComputeFreeListIndex((ULONG
)CellBlock
->Size
);
215 pFreeCellOffset
= &RegistryHive
->Storage
[Storage
].FreeDisplay
[Index
];
216 while (*pFreeCellOffset
!= HCELL_NIL
)
218 FreeCellData
= (PHCELL_INDEX
)HvGetCell(RegistryHive
, *pFreeCellOffset
);
219 if (*pFreeCellOffset
== CellIndex
)
221 *pFreeCellOffset
= *FreeCellData
;
224 pFreeCellOffset
= FreeCellData
;
227 /* Something bad happened, print a useful trace info and bugcheck */
228 CMLTRACE(CMLIB_HCELL_DEBUG
, "-- beginning of HvpRemoveFree trace --\n");
229 CMLTRACE(CMLIB_HCELL_DEBUG
, "block we are about to free: %08x\n", CellIndex
);
230 CMLTRACE(CMLIB_HCELL_DEBUG
, "chosen free list index: %u\n", Index
);
231 for (FreeListIndex
= 0; FreeListIndex
< 24; FreeListIndex
++)
233 CMLTRACE(CMLIB_HCELL_DEBUG
, "free list [%u]: ", FreeListIndex
);
234 pFreeCellOffset
= &RegistryHive
->Storage
[Storage
].FreeDisplay
[FreeListIndex
];
235 while (*pFreeCellOffset
!= HCELL_NIL
)
237 CMLTRACE(CMLIB_HCELL_DEBUG
, "%08x ", *pFreeCellOffset
);
238 FreeCellData
= (PHCELL_INDEX
)HvGetCell(RegistryHive
, *pFreeCellOffset
);
239 pFreeCellOffset
= FreeCellData
;
241 CMLTRACE(CMLIB_HCELL_DEBUG
, "\n");
243 CMLTRACE(CMLIB_HCELL_DEBUG
, "-- end of HvpRemoveFree trace --\n");
248 static HCELL_INDEX CMAPI
252 HSTORAGE_TYPE Storage
)
254 PHCELL_INDEX FreeCellData
;
255 HCELL_INDEX FreeCellOffset
;
256 PHCELL_INDEX pFreeCellOffset
;
259 for (Index
= HvpComputeFreeListIndex(Size
); Index
< 24; Index
++)
261 pFreeCellOffset
= &RegistryHive
->Storage
[Storage
].FreeDisplay
[Index
];
262 while (*pFreeCellOffset
!= HCELL_NIL
)
264 FreeCellData
= (PHCELL_INDEX
)HvGetCell(RegistryHive
, *pFreeCellOffset
);
265 if ((ULONG
)HvpGetCellFullSize(RegistryHive
, FreeCellData
) >= Size
)
267 FreeCellOffset
= *pFreeCellOffset
;
268 *pFreeCellOffset
= *FreeCellData
;
269 return FreeCellOffset
;
271 pFreeCellOffset
= FreeCellData
;
279 HvpCreateHiveFreeCellList(
282 HCELL_INDEX BlockOffset
;
290 /* Initialize the free cell list */
291 for (Index
= 0; Index
< 24; Index
++)
293 Hive
->Storage
[Stable
].FreeDisplay
[Index
] = HCELL_NIL
;
294 Hive
->Storage
[Volatile
].FreeDisplay
[Index
] = HCELL_NIL
;
299 while (BlockIndex
< Hive
->Storage
[Stable
].Length
)
301 Bin
= (PHBIN
)Hive
->Storage
[Stable
].BlockList
[BlockIndex
].BinAddress
;
303 /* Search free blocks and add to list */
304 FreeOffset
= sizeof(HBIN
);
305 while (FreeOffset
< Bin
->Size
)
307 FreeBlock
= (PHCELL
)((ULONG_PTR
)Bin
+ FreeOffset
);
308 if (FreeBlock
->Size
> 0)
310 Status
= HvpAddFree(Hive
, FreeBlock
, Bin
->FileOffset
+ FreeOffset
);
311 if (!NT_SUCCESS(Status
))
314 FreeOffset
+= FreeBlock
->Size
;
318 FreeOffset
-= FreeBlock
->Size
;
322 BlockIndex
+= Bin
->Size
/ HBLOCK_SIZE
;
323 BlockOffset
+= Bin
->Size
;
326 return STATUS_SUCCESS
;
333 HSTORAGE_TYPE Storage
,
334 HCELL_INDEX Vicinity
)
337 HCELL_INDEX FreeCellOffset
;
341 ASSERT(RegistryHive
->ReadOnly
== FALSE
);
343 CMLTRACE(CMLIB_HCELL_DEBUG
, "%s - Hive %p, Size %x, %s, Vicinity %08lx\n",
344 __FUNCTION__
, RegistryHive
, Size
, (Storage
== 0) ? "Stable" : "Volatile", Vicinity
);
346 /* Round to 16 bytes multiple. */
347 Size
= ROUND_UP(Size
+ sizeof(HCELL
), 16);
349 /* First search in free blocks. */
350 FreeCellOffset
= HvpFindFree(RegistryHive
, Size
, Storage
);
352 /* If no free cell was found we need to extend the hive file. */
353 if (FreeCellOffset
== HCELL_NIL
)
355 Bin
= HvpAddBin(RegistryHive
, Size
, Storage
);
358 FreeCellOffset
= Bin
->FileOffset
+ sizeof(HBIN
);
359 FreeCellOffset
|= Storage
<< HCELL_TYPE_SHIFT
;
362 FreeCell
= HvpGetCellHeader(RegistryHive
, FreeCellOffset
);
364 /* Split the block in two parts */
366 /* The free block that is created has to be at least
367 sizeof(HCELL) + sizeof(HCELL_INDEX) big, so that free
368 cell list code can work. Moreover we round cell sizes
369 to 16 bytes, so creating a smaller block would result in
370 a cell that would never be allocated. */
371 if ((ULONG
)FreeCell
->Size
> Size
+ 16)
373 NewCell
= (PHCELL
)((ULONG_PTR
)FreeCell
+ Size
);
374 NewCell
->Size
= FreeCell
->Size
- Size
;
375 FreeCell
->Size
= Size
;
376 HvpAddFree(RegistryHive
, NewCell
, FreeCellOffset
+ Size
);
377 if (Storage
== Stable
)
378 HvMarkCellDirty(RegistryHive
, FreeCellOffset
+ Size
, FALSE
);
381 if (Storage
== Stable
)
382 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
= HvGetCellType(CellIndex
);
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
= HvGetCellType(CellIndex
);
463 CellBlock
= HvGetCellBlock(CellIndex
);
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;