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 return ((PHCELL
)Cell
- 1)->Size
;
86 HvGetCellSize(IN PHHIVE Hive
,
92 CellHeader
= (PHCELL
)Address
- 1;
93 Size
= CellHeader
->Size
* -1;
94 Size
-= sizeof(HCELL
);
101 HCELL_INDEX CellIndex
,
107 ASSERT(RegistryHive
->ReadOnly
== FALSE
);
109 CMLTRACE(CMLIB_HCELL_DEBUG
, "%s - Hive %p, CellIndex %08lx, HoldingLock %b\n",
110 __FUNCTION__
, RegistryHive
, CellIndex
, HoldingLock
);
112 if ((CellIndex
& HCELL_TYPE_MASK
) >> HCELL_TYPE_SHIFT
!= Stable
)
115 CellBlock
= (CellIndex
& HCELL_BLOCK_MASK
) >> HCELL_BLOCK_SHIFT
;
116 CellLastBlock
= ((CellIndex
+ HV_BLOCK_SIZE
- 1) & HCELL_BLOCK_MASK
) >> HCELL_BLOCK_SHIFT
;
118 RtlSetBits(&RegistryHive
->DirtyVector
,
119 CellBlock
, CellLastBlock
- CellBlock
);
124 HvIsCellDirty(IN PHHIVE Hive
,
127 BOOLEAN IsDirty
= FALSE
;
130 ASSERT(Hive
->ReadOnly
== FALSE
);
132 /* Volatile cells are always "dirty" */
133 if (HvGetCellType(Cell
) == Volatile
)
136 /* Check if the dirty bit is set */
137 if (RtlCheckBit(&Hive
->DirtyVector
, Cell
/ HV_BLOCK_SIZE
))
140 /* Return result as boolean*/
144 static __inline ULONG CMAPI
145 HvpComputeFreeListIndex(
149 static CCHAR FindFirstSet
[256] = {
150 0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
151 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
152 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
153 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
154 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
155 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
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 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
159 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
160 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
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};
167 Index
= (Size
>> 3) - 1;
173 Index
= FindFirstSet
[Index
] + 7;
179 static NTSTATUS CMAPI
183 HCELL_INDEX FreeIndex
)
185 PHCELL_INDEX FreeBlockData
;
186 HSTORAGE_TYPE Storage
;
189 ASSERT(RegistryHive
!= NULL
);
190 ASSERT(FreeBlock
!= NULL
);
192 Storage
= (FreeIndex
& HCELL_TYPE_MASK
) >> HCELL_TYPE_SHIFT
;
193 Index
= HvpComputeFreeListIndex((ULONG
)FreeBlock
->Size
);
195 FreeBlockData
= (PHCELL_INDEX
)(FreeBlock
+ 1);
196 *FreeBlockData
= RegistryHive
->Storage
[Storage
].FreeDisplay
[Index
];
197 RegistryHive
->Storage
[Storage
].FreeDisplay
[Index
] = FreeIndex
;
199 /* FIXME: Eventually get rid of free bins. */
201 return STATUS_SUCCESS
;
208 HCELL_INDEX CellIndex
)
210 PHCELL_INDEX FreeCellData
;
211 PHCELL_INDEX pFreeCellOffset
;
212 HSTORAGE_TYPE Storage
;
213 ULONG Index
, FreeListIndex
;
215 ASSERT(RegistryHive
->ReadOnly
== FALSE
);
217 Storage
= (CellIndex
& HCELL_TYPE_MASK
) >> HCELL_TYPE_SHIFT
;
218 Index
= HvpComputeFreeListIndex((ULONG
)CellBlock
->Size
);
220 pFreeCellOffset
= &RegistryHive
->Storage
[Storage
].FreeDisplay
[Index
];
221 while (*pFreeCellOffset
!= HCELL_NIL
)
223 FreeCellData
= (PHCELL_INDEX
)HvGetCell(RegistryHive
, *pFreeCellOffset
);
224 if (*pFreeCellOffset
== CellIndex
)
226 *pFreeCellOffset
= *FreeCellData
;
229 pFreeCellOffset
= FreeCellData
;
232 /* Something bad happened, print a useful trace info and bugcheck */
233 CMLTRACE(CMLIB_HCELL_DEBUG
, "-- beginning of HvpRemoveFree trace --\n");
234 CMLTRACE(CMLIB_HCELL_DEBUG
, "block we are about to free: %08x\n", CellIndex
);
235 CMLTRACE(CMLIB_HCELL_DEBUG
, "chosen free list index: %d\n", Index
);
236 for (FreeListIndex
= 0; FreeListIndex
< 24; FreeListIndex
++)
238 CMLTRACE(CMLIB_HCELL_DEBUG
, "free list [%d]: ", FreeListIndex
);
239 pFreeCellOffset
= &RegistryHive
->Storage
[Storage
].FreeDisplay
[FreeListIndex
];
240 while (*pFreeCellOffset
!= HCELL_NIL
)
242 CMLTRACE(CMLIB_HCELL_DEBUG
, "%08x ", *pFreeCellOffset
);
243 FreeCellData
= (PHCELL_INDEX
)HvGetCell(RegistryHive
, *pFreeCellOffset
);
244 pFreeCellOffset
= FreeCellData
;
246 CMLTRACE(CMLIB_HCELL_DEBUG
, "\n");
248 CMLTRACE(CMLIB_HCELL_DEBUG
, "-- end of HvpRemoveFree trace --\n");
253 static HCELL_INDEX CMAPI
257 HSTORAGE_TYPE Storage
)
259 PHCELL_INDEX FreeCellData
;
260 HCELL_INDEX FreeCellOffset
;
261 PHCELL_INDEX pFreeCellOffset
;
264 for (Index
= HvpComputeFreeListIndex(Size
); Index
< 24; Index
++)
266 pFreeCellOffset
= &RegistryHive
->Storage
[Storage
].FreeDisplay
[Index
];
267 while (*pFreeCellOffset
!= HCELL_NIL
)
269 FreeCellData
= (PHCELL_INDEX
)HvGetCell(RegistryHive
, *pFreeCellOffset
);
270 if ((ULONG
)HvpGetCellFullSize(RegistryHive
, FreeCellData
) >= Size
)
272 FreeCellOffset
= *pFreeCellOffset
;
273 *pFreeCellOffset
= *FreeCellData
;
274 return FreeCellOffset
;
276 pFreeCellOffset
= FreeCellData
;
284 HvpCreateHiveFreeCellList(
287 HCELL_INDEX BlockOffset
;
295 /* Initialize the free cell list */
296 for (Index
= 0; Index
< 24; Index
++)
298 Hive
->Storage
[Stable
].FreeDisplay
[Index
] = HCELL_NIL
;
299 Hive
->Storage
[Volatile
].FreeDisplay
[Index
] = HCELL_NIL
;
304 while (BlockIndex
< Hive
->Storage
[Stable
].Length
)
306 Bin
= (PHBIN
)Hive
->Storage
[Stable
].BlockList
[BlockIndex
].BinAddress
;
308 /* Search free blocks and add to list */
309 FreeOffset
= sizeof(HBIN
);
310 while (FreeOffset
< Bin
->Size
)
312 FreeBlock
= (PHCELL
)((ULONG_PTR
)Bin
+ FreeOffset
);
313 if (FreeBlock
->Size
> 0)
315 Status
= HvpAddFree(Hive
, FreeBlock
, Bin
->FileOffset
+ FreeOffset
);
316 if (!NT_SUCCESS(Status
))
319 FreeOffset
+= FreeBlock
->Size
;
323 FreeOffset
-= FreeBlock
->Size
;
327 BlockIndex
+= Bin
->Size
/ HV_BLOCK_SIZE
;
328 BlockOffset
+= Bin
->Size
;
331 return STATUS_SUCCESS
;
338 HSTORAGE_TYPE Storage
,
339 HCELL_INDEX Vicinity
)
342 HCELL_INDEX FreeCellOffset
;
346 ASSERT(RegistryHive
->ReadOnly
== FALSE
);
348 CMLTRACE(CMLIB_HCELL_DEBUG
, "%s - Hive %p, Size %x, %s, Vicinity %08lx\n",
349 __FUNCTION__
, RegistryHive
, Size
, (Storage
== 0) ? "Stable" : "Volatile", Vicinity
);
351 /* Round to 16 bytes multiple. */
352 Size
= ROUND_UP(Size
+ sizeof(HCELL
), 16);
354 /* First search in free blocks. */
355 FreeCellOffset
= HvpFindFree(RegistryHive
, Size
, Storage
);
357 /* If no free cell was found we need to extend the hive file. */
358 if (FreeCellOffset
== HCELL_NIL
)
360 Bin
= HvpAddBin(RegistryHive
, Size
, Storage
);
363 FreeCellOffset
= Bin
->FileOffset
+ sizeof(HBIN
);
364 FreeCellOffset
|= Storage
<< HCELL_TYPE_SHIFT
;
367 FreeCell
= HvpGetCellHeader(RegistryHive
, FreeCellOffset
);
369 /* Split the block in two parts */
371 /* The free block that is created has to be at least
372 sizeof(HCELL) + sizeof(HCELL_INDEX) big, so that free
373 cell list code can work. Moreover we round cell sizes
374 to 16 bytes, so creating a smaller block would result in
375 a cell that would never be allocated. */
376 if ((ULONG
)FreeCell
->Size
> Size
+ 16)
378 NewCell
= (PHCELL
)((ULONG_PTR
)FreeCell
+ Size
);
379 NewCell
->Size
= FreeCell
->Size
- Size
;
380 FreeCell
->Size
= Size
;
381 HvpAddFree(RegistryHive
, NewCell
, FreeCellOffset
+ Size
);
382 if (Storage
== Stable
)
383 HvMarkCellDirty(RegistryHive
, FreeCellOffset
+ Size
, FALSE
);
386 if (Storage
== Stable
)
387 HvMarkCellDirty(RegistryHive
, FreeCellOffset
, FALSE
);
388 FreeCell
->Size
= -FreeCell
->Size
;
389 RtlZeroMemory(FreeCell
+ 1, Size
- sizeof(HCELL
));
391 CMLTRACE(CMLIB_HCELL_DEBUG
, "%s - CellIndex %08lx\n",
392 __FUNCTION__
, FreeCellOffset
);
394 return FreeCellOffset
;
400 HCELL_INDEX CellIndex
,
406 HCELL_INDEX NewCellIndex
;
407 HSTORAGE_TYPE Storage
;
409 ASSERT(CellIndex
!= HCELL_NIL
);
411 CMLTRACE(CMLIB_HCELL_DEBUG
, "%s - Hive %p, CellIndex %08lx, Size %x\n",
412 __FUNCTION__
, RegistryHive
, CellIndex
, Size
);
414 Storage
= (CellIndex
& HCELL_TYPE_MASK
) >> HCELL_TYPE_SHIFT
;
416 OldCell
= HvGetCell(RegistryHive
, CellIndex
);
417 OldCellSize
= HvGetCellSize(RegistryHive
, OldCell
);
418 ASSERT(OldCellSize
> 0);
421 * If new data size is larger than the current, destroy current
422 * data block and allocate a new one.
424 * FIXME: Merge with adjacent free cell if possible.
425 * FIXME: Implement shrinking.
427 if (Size
> (ULONG
)OldCellSize
)
429 NewCellIndex
= HvAllocateCell(RegistryHive
, Size
, Storage
, HCELL_NIL
);
430 if (NewCellIndex
== HCELL_NIL
)
433 NewCell
= HvGetCell(RegistryHive
, NewCellIndex
);
434 RtlCopyMemory(NewCell
, OldCell
, (SIZE_T
)OldCellSize
);
436 HvFreeCell(RegistryHive
, CellIndex
);
447 HCELL_INDEX CellIndex
)
455 ASSERT(RegistryHive
->ReadOnly
== FALSE
);
457 CMLTRACE(CMLIB_HCELL_DEBUG
, "%s - Hive %p, CellIndex %08lx\n",
458 __FUNCTION__
, RegistryHive
, CellIndex
);
460 Free
= HvpGetCellHeader(RegistryHive
, CellIndex
);
462 ASSERT(Free
->Size
< 0);
464 Free
->Size
= -Free
->Size
;
466 CellType
= (CellIndex
& HCELL_TYPE_MASK
) >> HCELL_TYPE_SHIFT
;
467 CellBlock
= (CellIndex
& HCELL_BLOCK_MASK
) >> HCELL_BLOCK_SHIFT
;
469 /* FIXME: Merge free blocks */
470 Bin
= (PHBIN
)RegistryHive
->Storage
[CellType
].BlockList
[CellBlock
].BinAddress
;
472 if ((CellIndex
& ~HCELL_TYPE_MASK
) + Free
->Size
<
473 Bin
->FileOffset
+ Bin
->Size
)
475 Neighbor
= (PHCELL
)((ULONG_PTR
)Free
+ Free
->Size
);
476 if (Neighbor
->Size
> 0)
478 HvpRemoveFree(RegistryHive
, Neighbor
,
479 ((HCELL_INDEX
)((ULONG_PTR
)Neighbor
- (ULONG_PTR
)Bin
+
480 Bin
->FileOffset
)) | (CellIndex
& HCELL_TYPE_MASK
));
481 Free
->Size
+= Neighbor
->Size
;
485 Neighbor
= (PHCELL
)(Bin
+ 1);
486 while (Neighbor
< Free
)
488 if (Neighbor
->Size
> 0)
490 if ((ULONG_PTR
)Neighbor
+ Neighbor
->Size
== (ULONG_PTR
)Free
)
492 HCELL_INDEX NeighborCellIndex
=
493 (HCELL_INDEX
)((ULONG_PTR
)Neighbor
- (ULONG_PTR
)Bin
+
494 Bin
->FileOffset
) | (CellIndex
& HCELL_TYPE_MASK
);
496 if (HvpComputeFreeListIndex(Neighbor
->Size
) !=
497 HvpComputeFreeListIndex(Neighbor
->Size
+ Free
->Size
))
499 HvpRemoveFree(RegistryHive
, Neighbor
, NeighborCellIndex
);
500 Neighbor
->Size
+= Free
->Size
;
501 HvpAddFree(RegistryHive
, Neighbor
, NeighborCellIndex
);
504 Neighbor
->Size
+= Free
->Size
;
506 if (CellType
== Stable
)
507 HvMarkCellDirty(RegistryHive
, NeighborCellIndex
, FALSE
);
511 Neighbor
= (PHCELL
)((ULONG_PTR
)Neighbor
+ Neighbor
->Size
);
515 Neighbor
= (PHCELL
)((ULONG_PTR
)Neighbor
- Neighbor
->Size
);
519 /* Add block to the list of free blocks */
520 HvpAddFree(RegistryHive
, Free
, CellIndex
);
522 if (CellType
== Stable
)
523 HvMarkCellDirty(RegistryHive
, CellIndex
, FALSE
);