Revert 45697:
[reactos.git] / lib / cmlib / hivecell.c
1 /*
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
6 */
7
8 #include "cmlib.h"
9 #define NDEBUG
10 #include <debug.h>
11
12 static __inline PHCELL CMAPI
13 HvpGetCellHeader(
14 PHHIVE RegistryHive,
15 HCELL_INDEX CellIndex)
16 {
17 PVOID Block;
18
19 CMLTRACE(CMLIB_HCELL_DEBUG, "%s - Hive %p, CellIndex %08lx\n",
20 __FUNCTION__, RegistryHive, CellIndex);
21
22 ASSERT(CellIndex != HCELL_NIL);
23 if (!RegistryHive->Flat)
24 {
25 ULONG CellType;
26 ULONG CellBlock;
27 ULONG CellOffset;
28
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);
36 }
37 else
38 {
39 ASSERT((CellIndex & HCELL_TYPE_MASK) == Stable);
40 return (PVOID)((ULONG_PTR)RegistryHive->BaseBlock + HV_BLOCK_SIZE +
41 CellIndex);
42 }
43 }
44
45 BOOLEAN CMAPI
46 HvIsCellAllocated(IN PHHIVE RegistryHive,
47 IN HCELL_INDEX CellIndex)
48 {
49 ULONG Type, Block;
50
51 /* If it's a flat hive, the cell is always allocated */
52 if (RegistryHive->Flat)
53 return TRUE;
54
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)
59 return FALSE;
60
61 /* Try to get the cell block */
62 if (RegistryHive->Storage[Type].BlockList[Block].BlockAddress)
63 return TRUE;
64
65 /* No valid block, fail */
66 return FALSE;
67 }
68
69 PVOID CMAPI
70 HvGetCell(
71 PHHIVE RegistryHive,
72 HCELL_INDEX CellIndex)
73 {
74 return (PVOID)(HvpGetCellHeader(RegistryHive, CellIndex) + 1);
75 }
76
77 static __inline LONG CMAPI
78 HvpGetCellFullSize(
79 PHHIVE RegistryHive,
80 PVOID Cell)
81 {
82 UNREFERENCED_PARAMETER(RegistryHive);
83 return ((PHCELL)Cell - 1)->Size;
84 }
85
86 LONG CMAPI
87 HvGetCellSize(IN PHHIVE Hive,
88 IN PVOID Address)
89 {
90 PHCELL CellHeader;
91 LONG Size;
92
93 UNREFERENCED_PARAMETER(Hive);
94
95 CellHeader = (PHCELL)Address - 1;
96 Size = CellHeader->Size * -1;
97 Size -= sizeof(HCELL);
98 return Size;
99 }
100
101 BOOLEAN CMAPI
102 HvMarkCellDirty(
103 PHHIVE RegistryHive,
104 HCELL_INDEX CellIndex,
105 BOOLEAN HoldingLock)
106 {
107 ULONG CellBlock;
108 ULONG CellLastBlock;
109
110 ASSERT(RegistryHive->ReadOnly == FALSE);
111
112 CMLTRACE(CMLIB_HCELL_DEBUG, "%s - Hive %p, CellIndex %08lx, HoldingLock %b\n",
113 __FUNCTION__, RegistryHive, CellIndex, HoldingLock);
114
115 if ((CellIndex & HCELL_TYPE_MASK) >> HCELL_TYPE_SHIFT != Stable)
116 return FALSE;
117
118 CellBlock = (CellIndex & HCELL_BLOCK_MASK) >> HCELL_BLOCK_SHIFT;
119 CellLastBlock = ((CellIndex + HV_BLOCK_SIZE - 1) & HCELL_BLOCK_MASK) >> HCELL_BLOCK_SHIFT;
120
121 RtlSetBits(&RegistryHive->DirtyVector,
122 CellBlock, CellLastBlock - CellBlock);
123 return TRUE;
124 }
125
126 BOOLEAN CMAPI
127 HvIsCellDirty(IN PHHIVE Hive,
128 IN HCELL_INDEX Cell)
129 {
130 BOOLEAN IsDirty = FALSE;
131
132 /* Sanity checks */
133 ASSERT(Hive->ReadOnly == FALSE);
134
135 /* Volatile cells are always "dirty" */
136 if (HvGetCellType(Cell) == Volatile)
137 return TRUE;
138
139 /* Check if the dirty bit is set */
140 if (RtlCheckBit(&Hive->DirtyVector, Cell / HV_BLOCK_SIZE))
141 IsDirty = TRUE;
142
143 /* Return result as boolean*/
144 return IsDirty;
145 }
146
147 static __inline ULONG CMAPI
148 HvpComputeFreeListIndex(
149 ULONG Size)
150 {
151 ULONG Index;
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};
169
170 Index = (Size >> 3) - 1;
171 if (Index >= 16)
172 {
173 if (Index > 255)
174 Index = 23;
175 else
176 Index = FindFirstSet[Index] + 7;
177 }
178
179 return Index;
180 }
181
182 static NTSTATUS CMAPI
183 HvpAddFree(
184 PHHIVE RegistryHive,
185 PHCELL FreeBlock,
186 HCELL_INDEX FreeIndex)
187 {
188 PHCELL_INDEX FreeBlockData;
189 HSTORAGE_TYPE Storage;
190 ULONG Index;
191
192 ASSERT(RegistryHive != NULL);
193 ASSERT(FreeBlock != NULL);
194
195 Storage = (FreeIndex & HCELL_TYPE_MASK) >> HCELL_TYPE_SHIFT;
196 Index = HvpComputeFreeListIndex((ULONG)FreeBlock->Size);
197
198 FreeBlockData = (PHCELL_INDEX)(FreeBlock + 1);
199 *FreeBlockData = RegistryHive->Storage[Storage].FreeDisplay[Index];
200 RegistryHive->Storage[Storage].FreeDisplay[Index] = FreeIndex;
201
202 /* FIXME: Eventually get rid of free bins. */
203
204 return STATUS_SUCCESS;
205 }
206
207 static VOID CMAPI
208 HvpRemoveFree(
209 PHHIVE RegistryHive,
210 PHCELL CellBlock,
211 HCELL_INDEX CellIndex)
212 {
213 PHCELL_INDEX FreeCellData;
214 PHCELL_INDEX pFreeCellOffset;
215 HSTORAGE_TYPE Storage;
216 ULONG Index, FreeListIndex;
217
218 ASSERT(RegistryHive->ReadOnly == FALSE);
219
220 Storage = (CellIndex & HCELL_TYPE_MASK) >> HCELL_TYPE_SHIFT;
221 Index = HvpComputeFreeListIndex((ULONG)CellBlock->Size);
222
223 pFreeCellOffset = &RegistryHive->Storage[Storage].FreeDisplay[Index];
224 while (*pFreeCellOffset != HCELL_NIL)
225 {
226 FreeCellData = (PHCELL_INDEX)HvGetCell(RegistryHive, *pFreeCellOffset);
227 if (*pFreeCellOffset == CellIndex)
228 {
229 *pFreeCellOffset = *FreeCellData;
230 return;
231 }
232 pFreeCellOffset = FreeCellData;
233 }
234
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: %d\n", Index);
239 for (FreeListIndex = 0; FreeListIndex < 24; FreeListIndex++)
240 {
241 CMLTRACE(CMLIB_HCELL_DEBUG, "free list [%d]: ", FreeListIndex);
242 pFreeCellOffset = &RegistryHive->Storage[Storage].FreeDisplay[FreeListIndex];
243 while (*pFreeCellOffset != HCELL_NIL)
244 {
245 CMLTRACE(CMLIB_HCELL_DEBUG, "%08x ", *pFreeCellOffset);
246 FreeCellData = (PHCELL_INDEX)HvGetCell(RegistryHive, *pFreeCellOffset);
247 pFreeCellOffset = FreeCellData;
248 }
249 CMLTRACE(CMLIB_HCELL_DEBUG, "\n");
250 }
251 CMLTRACE(CMLIB_HCELL_DEBUG, "-- end of HvpRemoveFree trace --\n");
252
253 ASSERT(FALSE);
254 }
255
256 static HCELL_INDEX CMAPI
257 HvpFindFree(
258 PHHIVE RegistryHive,
259 ULONG Size,
260 HSTORAGE_TYPE Storage)
261 {
262 PHCELL_INDEX FreeCellData;
263 HCELL_INDEX FreeCellOffset;
264 PHCELL_INDEX pFreeCellOffset;
265 ULONG Index;
266
267 for (Index = HvpComputeFreeListIndex(Size); Index < 24; Index++)
268 {
269 pFreeCellOffset = &RegistryHive->Storage[Storage].FreeDisplay[Index];
270 while (*pFreeCellOffset != HCELL_NIL)
271 {
272 FreeCellData = (PHCELL_INDEX)HvGetCell(RegistryHive, *pFreeCellOffset);
273 if ((ULONG)HvpGetCellFullSize(RegistryHive, FreeCellData) >= Size)
274 {
275 FreeCellOffset = *pFreeCellOffset;
276 *pFreeCellOffset = *FreeCellData;
277 return FreeCellOffset;
278 }
279 pFreeCellOffset = FreeCellData;
280 }
281 }
282
283 return HCELL_NIL;
284 }
285
286 NTSTATUS CMAPI
287 HvpCreateHiveFreeCellList(
288 PHHIVE Hive)
289 {
290 HCELL_INDEX BlockOffset;
291 PHCELL FreeBlock;
292 ULONG BlockIndex;
293 ULONG FreeOffset;
294 PHBIN Bin;
295 NTSTATUS Status;
296 ULONG Index;
297
298 /* Initialize the free cell list */
299 for (Index = 0; Index < 24; Index++)
300 {
301 Hive->Storage[Stable].FreeDisplay[Index] = HCELL_NIL;
302 Hive->Storage[Volatile].FreeDisplay[Index] = HCELL_NIL;
303 }
304
305 BlockOffset = 0;
306 BlockIndex = 0;
307 while (BlockIndex < Hive->Storage[Stable].Length)
308 {
309 Bin = (PHBIN)Hive->Storage[Stable].BlockList[BlockIndex].BinAddress;
310
311 /* Search free blocks and add to list */
312 FreeOffset = sizeof(HBIN);
313 while (FreeOffset < Bin->Size)
314 {
315 FreeBlock = (PHCELL)((ULONG_PTR)Bin + FreeOffset);
316 if (FreeBlock->Size > 0)
317 {
318 Status = HvpAddFree(Hive, FreeBlock, Bin->FileOffset + FreeOffset);
319 if (!NT_SUCCESS(Status))
320 return Status;
321
322 FreeOffset += FreeBlock->Size;
323 }
324 else
325 {
326 FreeOffset -= FreeBlock->Size;
327 }
328 }
329
330 BlockIndex += Bin->Size / HV_BLOCK_SIZE;
331 BlockOffset += Bin->Size;
332 }
333
334 return STATUS_SUCCESS;
335 }
336
337 HCELL_INDEX CMAPI
338 HvAllocateCell(
339 PHHIVE RegistryHive,
340 SIZE_T Size,
341 HSTORAGE_TYPE Storage,
342 HCELL_INDEX Vicinity)
343 {
344 PHCELL FreeCell;
345 HCELL_INDEX FreeCellOffset;
346 PHCELL NewCell;
347 PHBIN Bin;
348
349 ASSERT(RegistryHive->ReadOnly == FALSE);
350
351 CMLTRACE(CMLIB_HCELL_DEBUG, "%s - Hive %p, Size %x, %s, Vicinity %08lx\n",
352 __FUNCTION__, RegistryHive, Size, (Storage == 0) ? "Stable" : "Volatile", Vicinity);
353
354 /* Round to 16 bytes multiple. */
355 Size = ROUND_UP(Size + sizeof(HCELL), 16);
356
357 /* First search in free blocks. */
358 FreeCellOffset = HvpFindFree(RegistryHive, Size, Storage);
359
360 /* If no free cell was found we need to extend the hive file. */
361 if (FreeCellOffset == HCELL_NIL)
362 {
363 Bin = HvpAddBin(RegistryHive, Size, Storage);
364 if (Bin == NULL)
365 return HCELL_NIL;
366 FreeCellOffset = Bin->FileOffset + sizeof(HBIN);
367 FreeCellOffset |= Storage << HCELL_TYPE_SHIFT;
368 }
369
370 FreeCell = HvpGetCellHeader(RegistryHive, FreeCellOffset);
371
372 /* Split the block in two parts */
373
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)
380 {
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);
387 }
388
389 if (Storage == Stable)
390 HvMarkCellDirty(RegistryHive, FreeCellOffset, FALSE);
391 FreeCell->Size = -FreeCell->Size;
392 RtlZeroMemory(FreeCell + 1, Size - sizeof(HCELL));
393
394 CMLTRACE(CMLIB_HCELL_DEBUG, "%s - CellIndex %08lx\n",
395 __FUNCTION__, FreeCellOffset);
396
397 return FreeCellOffset;
398 }
399
400 HCELL_INDEX CMAPI
401 HvReallocateCell(
402 PHHIVE RegistryHive,
403 HCELL_INDEX CellIndex,
404 ULONG Size)
405 {
406 PVOID OldCell;
407 PVOID NewCell;
408 LONG OldCellSize;
409 HCELL_INDEX NewCellIndex;
410 HSTORAGE_TYPE Storage;
411
412 ASSERT(CellIndex != HCELL_NIL);
413
414 CMLTRACE(CMLIB_HCELL_DEBUG, "%s - Hive %p, CellIndex %08lx, Size %x\n",
415 __FUNCTION__, RegistryHive, CellIndex, Size);
416
417 Storage = (CellIndex & HCELL_TYPE_MASK) >> HCELL_TYPE_SHIFT;
418
419 OldCell = HvGetCell(RegistryHive, CellIndex);
420 OldCellSize = HvGetCellSize(RegistryHive, OldCell);
421 ASSERT(OldCellSize > 0);
422
423 /*
424 * If new data size is larger than the current, destroy current
425 * data block and allocate a new one.
426 *
427 * FIXME: Merge with adjacent free cell if possible.
428 * FIXME: Implement shrinking.
429 */
430 if (Size > (ULONG)OldCellSize)
431 {
432 NewCellIndex = HvAllocateCell(RegistryHive, Size, Storage, HCELL_NIL);
433 if (NewCellIndex == HCELL_NIL)
434 return HCELL_NIL;
435
436 NewCell = HvGetCell(RegistryHive, NewCellIndex);
437 RtlCopyMemory(NewCell, OldCell, (SIZE_T)OldCellSize);
438
439 HvFreeCell(RegistryHive, CellIndex);
440
441 return NewCellIndex;
442 }
443
444 return CellIndex;
445 }
446
447 VOID CMAPI
448 HvFreeCell(
449 PHHIVE RegistryHive,
450 HCELL_INDEX CellIndex)
451 {
452 PHCELL Free;
453 PHCELL Neighbor;
454 PHBIN Bin;
455 ULONG CellType;
456 ULONG CellBlock;
457
458 ASSERT(RegistryHive->ReadOnly == FALSE);
459
460 CMLTRACE(CMLIB_HCELL_DEBUG, "%s - Hive %p, CellIndex %08lx\n",
461 __FUNCTION__, RegistryHive, CellIndex);
462
463 Free = HvpGetCellHeader(RegistryHive, CellIndex);
464
465 ASSERT(Free->Size < 0);
466
467 Free->Size = -Free->Size;
468
469 CellType = (CellIndex & HCELL_TYPE_MASK) >> HCELL_TYPE_SHIFT;
470 CellBlock = (CellIndex & HCELL_BLOCK_MASK) >> HCELL_BLOCK_SHIFT;
471
472 /* FIXME: Merge free blocks */
473 Bin = (PHBIN)RegistryHive->Storage[CellType].BlockList[CellBlock].BinAddress;
474
475 if ((CellIndex & ~HCELL_TYPE_MASK) + Free->Size <
476 Bin->FileOffset + Bin->Size)
477 {
478 Neighbor = (PHCELL)((ULONG_PTR)Free + Free->Size);
479 if (Neighbor->Size > 0)
480 {
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;
485 }
486 }
487
488 Neighbor = (PHCELL)(Bin + 1);
489 while (Neighbor < Free)
490 {
491 if (Neighbor->Size > 0)
492 {
493 if ((ULONG_PTR)Neighbor + Neighbor->Size == (ULONG_PTR)Free)
494 {
495 HCELL_INDEX NeighborCellIndex =
496 (HCELL_INDEX)((ULONG_PTR)Neighbor - (ULONG_PTR)Bin +
497 Bin->FileOffset) | (CellIndex & HCELL_TYPE_MASK);
498
499 if (HvpComputeFreeListIndex(Neighbor->Size) !=
500 HvpComputeFreeListIndex(Neighbor->Size + Free->Size))
501 {
502 HvpRemoveFree(RegistryHive, Neighbor, NeighborCellIndex);
503 Neighbor->Size += Free->Size;
504 HvpAddFree(RegistryHive, Neighbor, NeighborCellIndex);
505 }
506 else
507 Neighbor->Size += Free->Size;
508
509 if (CellType == Stable)
510 HvMarkCellDirty(RegistryHive, NeighborCellIndex, FALSE);
511
512 return;
513 }
514 Neighbor = (PHCELL)((ULONG_PTR)Neighbor + Neighbor->Size);
515 }
516 else
517 {
518 Neighbor = (PHCELL)((ULONG_PTR)Neighbor - Neighbor->Size);
519 }
520 }
521
522 /* Add block to the list of free blocks */
523 HvpAddFree(RegistryHive, Free, CellIndex);
524
525 if (CellType == Stable)
526 HvMarkCellDirty(RegistryHive, CellIndex, FALSE);
527 }