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 PHCELL __inline 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
) return TRUE
;
54 /* Otherwise, get the type and make sure it's valid */
55 Type
= HvGetCellType(CellIndex
);
56 if (((CellIndex
% ~HCELL_TYPE_MASK
) > RegistryHive
->Storage
[Type
].Length
) ||
57 (CellIndex
% (RegistryHive
->Version
>= 2 ? 8 : 16)))
59 /* Invalid cell index */
63 /* Try to get the cell block */
64 Block
= (CellIndex
& HCELL_BLOCK_MASK
) >> HCELL_BLOCK_SHIFT
;
65 if (RegistryHive
->Storage
[Type
].BlockList
[Block
].BlockAddress
) return TRUE
;
67 /* No valid block, fail */
74 HCELL_INDEX CellIndex
)
76 return (PVOID
)(HvpGetCellHeader(RegistryHive
, CellIndex
) + 1);
79 static LONG __inline CMAPI
84 return ((PHCELL
)Cell
- 1)->Size
;
88 HvGetCellSize(IN PHHIVE Hive
,
94 CellHeader
= (PHCELL
)Address
- 1;
95 Size
= CellHeader
->Size
* -1;
96 Size
-= sizeof(HCELL
);
103 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 CellSize
= HvpGetCellFullSize(RegistryHive
, HvGetCell(RegistryHive
, CellIndex
));
123 CellSize
= -CellSize
;
125 RtlSetBits(&RegistryHive
->DirtyVector
,
126 CellBlock
, CellLastBlock
- CellBlock
);
131 HvIsCellDirty(IN PHHIVE Hive
,
135 ASSERT(Hive
->ReadOnly
== FALSE
);
137 /* Volatile cells are always "dirty" */
138 if (HvGetCellType(Cell
) == Volatile
) return TRUE
;
140 /* Check if the dirty bit is set */
141 return RtlCheckBit(&Hive
->DirtyVector
, Cell
/ HV_BLOCK_SIZE
);
144 static ULONG __inline 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
;
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
;
235 static HCELL_INDEX CMAPI
239 HSTORAGE_TYPE Storage
)
241 PHCELL_INDEX FreeCellData
;
242 HCELL_INDEX FreeCellOffset
;
243 PHCELL_INDEX pFreeCellOffset
;
246 for (Index
= HvpComputeFreeListIndex(Size
); Index
< 24; Index
++)
248 pFreeCellOffset
= &RegistryHive
->Storage
[Storage
].FreeDisplay
[Index
];
249 while (*pFreeCellOffset
!= HCELL_NIL
)
251 FreeCellData
= (PHCELL_INDEX
)HvGetCell(RegistryHive
, *pFreeCellOffset
);
252 if ((ULONG
)HvpGetCellFullSize(RegistryHive
, FreeCellData
) >= Size
)
254 FreeCellOffset
= *pFreeCellOffset
;
255 *pFreeCellOffset
= *FreeCellData
;
256 return FreeCellOffset
;
258 pFreeCellOffset
= FreeCellData
;
266 HvpCreateHiveFreeCellList(
269 HCELL_INDEX BlockOffset
;
277 /* Initialize the free cell list */
278 for (Index
= 0; Index
< 24; Index
++)
280 Hive
->Storage
[Stable
].FreeDisplay
[Index
] = HCELL_NIL
;
281 Hive
->Storage
[Volatile
].FreeDisplay
[Index
] = HCELL_NIL
;
286 while (BlockIndex
< Hive
->Storage
[Stable
].Length
)
288 Bin
= (PHBIN
)Hive
->Storage
[Stable
].BlockList
[BlockIndex
].BinAddress
;
290 /* Search free blocks and add to list */
291 FreeOffset
= sizeof(HBIN
);
292 while (FreeOffset
< Bin
->Size
)
294 FreeBlock
= (PHCELL
)((ULONG_PTR
)Bin
+ FreeOffset
);
295 if (FreeBlock
->Size
> 0)
297 Status
= HvpAddFree(Hive
, FreeBlock
, Bin
->FileOffset
+ FreeOffset
);
298 if (!NT_SUCCESS(Status
))
301 FreeOffset
+= FreeBlock
->Size
;
305 FreeOffset
-= FreeBlock
->Size
;
309 BlockIndex
+= Bin
->Size
/ HV_BLOCK_SIZE
;
310 BlockOffset
+= Bin
->Size
;
313 return STATUS_SUCCESS
;
320 HSTORAGE_TYPE Storage
,
321 HCELL_INDEX Vicinity
)
324 HCELL_INDEX FreeCellOffset
;
328 ASSERT(RegistryHive
->ReadOnly
== FALSE
);
330 CMLTRACE(CMLIB_HCELL_DEBUG
, "%s - Hive %p, Size %x, %s, Vicinity %08lx\n",
331 __FUNCTION__
, RegistryHive
, Size
, (Storage
== 0) ? "Stable" : "Volatile", Vicinity
);
333 /* Round to 16 bytes multiple. */
334 Size
= ROUND_UP(Size
+ sizeof(HCELL
), 16);
336 /* First search in free blocks. */
337 FreeCellOffset
= HvpFindFree(RegistryHive
, Size
, Storage
);
339 /* If no free cell was found we need to extend the hive file. */
340 if (FreeCellOffset
== HCELL_NIL
)
342 Bin
= HvpAddBin(RegistryHive
, Size
, Storage
);
345 FreeCellOffset
= Bin
->FileOffset
+ sizeof(HBIN
);
346 FreeCellOffset
|= Storage
<< HCELL_TYPE_SHIFT
;
349 FreeCell
= HvpGetCellHeader(RegistryHive
, FreeCellOffset
);
351 /* Split the block in two parts */
352 /* FIXME: There is some minimal cell size that we must respect. */
353 if ((ULONG
)FreeCell
->Size
> Size
+ sizeof(HCELL_INDEX
))
355 NewCell
= (PHCELL
)((ULONG_PTR
)FreeCell
+ Size
);
356 NewCell
->Size
= FreeCell
->Size
- Size
;
357 FreeCell
->Size
= Size
;
358 HvpAddFree(RegistryHive
, NewCell
, FreeCellOffset
+ Size
);
359 if (Storage
== Stable
)
360 HvMarkCellDirty(RegistryHive
, FreeCellOffset
+ Size
, FALSE
);
363 if (Storage
== Stable
)
364 HvMarkCellDirty(RegistryHive
, FreeCellOffset
, FALSE
);
365 FreeCell
->Size
= -FreeCell
->Size
;
366 RtlZeroMemory(FreeCell
+ 1, Size
- sizeof(HCELL
));
368 CMLTRACE(CMLIB_HCELL_DEBUG
, "%s - CellIndex %08lx\n",
369 __FUNCTION__
, FreeCellOffset
);
371 return FreeCellOffset
;
377 HCELL_INDEX CellIndex
,
383 HCELL_INDEX NewCellIndex
;
384 HSTORAGE_TYPE Storage
;
386 ASSERT(CellIndex
!= HCELL_NIL
);
388 CMLTRACE(CMLIB_HCELL_DEBUG
, "%s - Hive %p, CellIndex %08lx, Size %x\n",
389 __FUNCTION__
, RegistryHive
, CellIndex
, Size
);
391 Storage
= (CellIndex
& HCELL_TYPE_MASK
) >> HCELL_TYPE_SHIFT
;
393 OldCell
= HvGetCell(RegistryHive
, CellIndex
);
394 OldCellSize
= HvGetCellSize(RegistryHive
, OldCell
);
395 ASSERT(OldCellSize
> 0);
398 * If new data size is larger than the current, destroy current
399 * data block and allocate a new one.
401 * FIXME: Merge with adjacent free cell if possible.
402 * FIXME: Implement shrinking.
404 if (Size
> OldCellSize
)
406 NewCellIndex
= HvAllocateCell(RegistryHive
, Size
, Storage
, HCELL_NIL
);
407 if (NewCellIndex
== HCELL_NIL
)
410 NewCell
= HvGetCell(RegistryHive
, NewCellIndex
);
411 RtlCopyMemory(NewCell
, OldCell
, (SIZE_T
)OldCellSize
);
413 HvFreeCell(RegistryHive
, CellIndex
);
424 HCELL_INDEX CellIndex
)
432 ASSERT(RegistryHive
->ReadOnly
== FALSE
);
434 CMLTRACE(CMLIB_HCELL_DEBUG
, "%s - Hive %p, CellIndex %08lx\n",
435 __FUNCTION__
, RegistryHive
, CellIndex
);
437 Free
= HvpGetCellHeader(RegistryHive
, CellIndex
);
439 ASSERT(Free
->Size
< 0);
441 Free
->Size
= -Free
->Size
;
443 CellType
= (CellIndex
& HCELL_TYPE_MASK
) >> HCELL_TYPE_SHIFT
;
444 CellBlock
= (CellIndex
& HCELL_BLOCK_MASK
) >> HCELL_BLOCK_SHIFT
;
446 /* FIXME: Merge free blocks */
447 Bin
= (PHBIN
)RegistryHive
->Storage
[CellType
].BlockList
[CellBlock
].BinAddress
;
449 if ((CellIndex
& ~HCELL_TYPE_MASK
) + Free
->Size
<
450 Bin
->FileOffset
+ Bin
->Size
)
452 Neighbor
= (PHCELL
)((ULONG_PTR
)Free
+ Free
->Size
);
453 if (Neighbor
->Size
> 0)
455 HvpRemoveFree(RegistryHive
, Neighbor
,
456 ((HCELL_INDEX
)((ULONG_PTR
)Neighbor
- (ULONG_PTR
)Bin
+
457 Bin
->FileOffset
)) | (CellIndex
& HCELL_TYPE_MASK
));
458 Free
->Size
+= Neighbor
->Size
;
462 Neighbor
= (PHCELL
)(Bin
+ 1);
463 while (Neighbor
< Free
)
465 if (Neighbor
->Size
> 0)
467 if ((ULONG_PTR
)Neighbor
+ Neighbor
->Size
== (ULONG_PTR
)Free
)
469 Neighbor
->Size
+= Free
->Size
;
470 if (CellType
== Stable
)
471 HvMarkCellDirty(RegistryHive
,
472 (HCELL_INDEX
)((ULONG_PTR
)Neighbor
- (ULONG_PTR
)Bin
+
473 Bin
->FileOffset
), FALSE
);
476 Neighbor
= (PHCELL
)((ULONG_PTR
)Neighbor
+ Neighbor
->Size
);
480 Neighbor
= (PHCELL
)((ULONG_PTR
)Neighbor
- Neighbor
->Size
);
484 /* Add block to the list of free blocks */
485 HvpAddFree(RegistryHive
, Free
, CellIndex
);
487 if (CellType
== Stable
)
488 HvMarkCellDirty(RegistryHive
, CellIndex
, FALSE
);