3d253a507b0266a78c37109a3c97df26c99b9438
[reactos.git] / reactos / 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 %u\n",
113 __FUNCTION__, RegistryHive, CellIndex, HoldingLock);
114
115 if ((CellIndex & HCELL_TYPE_MASK) >> HCELL_TYPE_SHIFT != Stable)
116 return TRUE;
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 RegistryHive->DirtyCount++;
124 return TRUE;
125 }
126
127 BOOLEAN CMAPI
128 HvIsCellDirty(IN PHHIVE Hive,
129 IN HCELL_INDEX Cell)
130 {
131 BOOLEAN IsDirty = FALSE;
132
133 /* Sanity checks */
134 ASSERT(Hive->ReadOnly == FALSE);
135
136 /* Volatile cells are always "dirty" */
137 if (HvGetCellType(Cell) == Volatile)
138 return TRUE;
139
140 /* Check if the dirty bit is set */
141 if (RtlCheckBit(&Hive->DirtyVector, Cell / HV_BLOCK_SIZE))
142 IsDirty = TRUE;
143
144 /* Return result as boolean*/
145 return IsDirty;
146 }
147
148 static __inline ULONG CMAPI
149 HvpComputeFreeListIndex(
150 ULONG Size)
151 {
152 ULONG Index;
153 static CCHAR FindFirstSet[128] = {
154 0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
155 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
156 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
157 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
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 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6};
162
163 ASSERT(Size >= (1 << 3));
164 Index = (Size >> 3) - 1;
165 if (Index >= 16)
166 {
167 if (Index > 127)
168 Index = 23;
169 else
170 Index = FindFirstSet[Index] + 16;
171 }
172
173 return Index;
174 }
175
176 static NTSTATUS CMAPI
177 HvpAddFree(
178 PHHIVE RegistryHive,
179 PHCELL FreeBlock,
180 HCELL_INDEX FreeIndex)
181 {
182 PHCELL_INDEX FreeBlockData;
183 HSTORAGE_TYPE Storage;
184 ULONG Index;
185
186 ASSERT(RegistryHive != NULL);
187 ASSERT(FreeBlock != NULL);
188
189 Storage = (FreeIndex & HCELL_TYPE_MASK) >> HCELL_TYPE_SHIFT;
190 Index = HvpComputeFreeListIndex((ULONG)FreeBlock->Size);
191
192 FreeBlockData = (PHCELL_INDEX)(FreeBlock + 1);
193 *FreeBlockData = RegistryHive->Storage[Storage].FreeDisplay[Index];
194 RegistryHive->Storage[Storage].FreeDisplay[Index] = FreeIndex;
195
196 /* FIXME: Eventually get rid of free bins. */
197
198 return STATUS_SUCCESS;
199 }
200
201 static VOID CMAPI
202 HvpRemoveFree(
203 PHHIVE RegistryHive,
204 PHCELL CellBlock,
205 HCELL_INDEX CellIndex)
206 {
207 PHCELL_INDEX FreeCellData;
208 PHCELL_INDEX pFreeCellOffset;
209 HSTORAGE_TYPE Storage;
210 ULONG Index, FreeListIndex;
211
212 ASSERT(RegistryHive->ReadOnly == FALSE);
213
214 Storage = (CellIndex & HCELL_TYPE_MASK) >> HCELL_TYPE_SHIFT;
215 Index = HvpComputeFreeListIndex((ULONG)CellBlock->Size);
216
217 pFreeCellOffset = &RegistryHive->Storage[Storage].FreeDisplay[Index];
218 while (*pFreeCellOffset != HCELL_NIL)
219 {
220 FreeCellData = (PHCELL_INDEX)HvGetCell(RegistryHive, *pFreeCellOffset);
221 if (*pFreeCellOffset == CellIndex)
222 {
223 *pFreeCellOffset = *FreeCellData;
224 return;
225 }
226 pFreeCellOffset = FreeCellData;
227 }
228
229 /* Something bad happened, print a useful trace info and bugcheck */
230 CMLTRACE(CMLIB_HCELL_DEBUG, "-- beginning of HvpRemoveFree trace --\n");
231 CMLTRACE(CMLIB_HCELL_DEBUG, "block we are about to free: %08x\n", CellIndex);
232 CMLTRACE(CMLIB_HCELL_DEBUG, "chosen free list index: %u\n", Index);
233 for (FreeListIndex = 0; FreeListIndex < 24; FreeListIndex++)
234 {
235 CMLTRACE(CMLIB_HCELL_DEBUG, "free list [%u]: ", FreeListIndex);
236 pFreeCellOffset = &RegistryHive->Storage[Storage].FreeDisplay[FreeListIndex];
237 while (*pFreeCellOffset != HCELL_NIL)
238 {
239 CMLTRACE(CMLIB_HCELL_DEBUG, "%08x ", *pFreeCellOffset);
240 FreeCellData = (PHCELL_INDEX)HvGetCell(RegistryHive, *pFreeCellOffset);
241 pFreeCellOffset = FreeCellData;
242 }
243 CMLTRACE(CMLIB_HCELL_DEBUG, "\n");
244 }
245 CMLTRACE(CMLIB_HCELL_DEBUG, "-- end of HvpRemoveFree trace --\n");
246
247 ASSERT(FALSE);
248 }
249
250 static HCELL_INDEX CMAPI
251 HvpFindFree(
252 PHHIVE RegistryHive,
253 ULONG Size,
254 HSTORAGE_TYPE Storage)
255 {
256 PHCELL_INDEX FreeCellData;
257 HCELL_INDEX FreeCellOffset;
258 PHCELL_INDEX pFreeCellOffset;
259 ULONG Index;
260
261 for (Index = HvpComputeFreeListIndex(Size); Index < 24; Index++)
262 {
263 pFreeCellOffset = &RegistryHive->Storage[Storage].FreeDisplay[Index];
264 while (*pFreeCellOffset != HCELL_NIL)
265 {
266 FreeCellData = (PHCELL_INDEX)HvGetCell(RegistryHive, *pFreeCellOffset);
267 if ((ULONG)HvpGetCellFullSize(RegistryHive, FreeCellData) >= Size)
268 {
269 FreeCellOffset = *pFreeCellOffset;
270 *pFreeCellOffset = *FreeCellData;
271 return FreeCellOffset;
272 }
273 pFreeCellOffset = FreeCellData;
274 }
275 }
276
277 return HCELL_NIL;
278 }
279
280 NTSTATUS CMAPI
281 HvpCreateHiveFreeCellList(
282 PHHIVE Hive)
283 {
284 HCELL_INDEX BlockOffset;
285 PHCELL FreeBlock;
286 ULONG BlockIndex;
287 ULONG FreeOffset;
288 PHBIN Bin;
289 NTSTATUS Status;
290 ULONG Index;
291
292 /* Initialize the free cell list */
293 for (Index = 0; Index < 24; Index++)
294 {
295 Hive->Storage[Stable].FreeDisplay[Index] = HCELL_NIL;
296 Hive->Storage[Volatile].FreeDisplay[Index] = HCELL_NIL;
297 }
298 //__debugbreak();
299 BlockOffset = 0;
300 BlockIndex = 0;
301 while (BlockIndex < Hive->Storage[Stable].Length)
302 {
303 Bin = (PHBIN)Hive->Storage[Stable].BlockList[BlockIndex].BinAddress;
304
305 /* Search free blocks and add to list */
306 FreeOffset = sizeof(HBIN);
307 while (FreeOffset < Bin->Size)
308 {
309 FreeBlock = (PHCELL)((ULONG_PTR)Bin + FreeOffset);
310 if (FreeBlock->Size > 0)
311 {
312 Status = HvpAddFree(Hive, FreeBlock, Bin->FileOffset + FreeOffset);
313 if (!NT_SUCCESS(Status))
314 return Status;
315
316 FreeOffset += FreeBlock->Size;
317 }
318 else
319 {
320 FreeOffset -= FreeBlock->Size;
321 }
322 }
323
324 BlockIndex += Bin->Size / HV_BLOCK_SIZE;
325 BlockOffset += Bin->Size;
326 }
327
328 return STATUS_SUCCESS;
329 }
330
331 HCELL_INDEX CMAPI
332 HvAllocateCell(
333 PHHIVE RegistryHive,
334 ULONG Size,
335 HSTORAGE_TYPE Storage,
336 HCELL_INDEX Vicinity)
337 {
338 PHCELL FreeCell;
339 HCELL_INDEX FreeCellOffset;
340 PHCELL NewCell;
341 PHBIN Bin;
342
343 ASSERT(RegistryHive->ReadOnly == FALSE);
344
345 CMLTRACE(CMLIB_HCELL_DEBUG, "%s - Hive %p, Size %x, %s, Vicinity %08lx\n",
346 __FUNCTION__, RegistryHive, Size, (Storage == 0) ? "Stable" : "Volatile", Vicinity);
347
348 /* Round to 16 bytes multiple. */
349 Size = ROUND_UP(Size + sizeof(HCELL), 16);
350
351 /* First search in free blocks. */
352 FreeCellOffset = HvpFindFree(RegistryHive, Size, Storage);
353
354 /* If no free cell was found we need to extend the hive file. */
355 if (FreeCellOffset == HCELL_NIL)
356 {
357 Bin = HvpAddBin(RegistryHive, Size, Storage);
358 if (Bin == NULL)
359 return HCELL_NIL;
360 FreeCellOffset = Bin->FileOffset + sizeof(HBIN);
361 FreeCellOffset |= Storage << HCELL_TYPE_SHIFT;
362 }
363
364 FreeCell = HvpGetCellHeader(RegistryHive, FreeCellOffset);
365
366 /* Split the block in two parts */
367
368 /* The free block that is created has to be at least
369 sizeof(HCELL) + sizeof(HCELL_INDEX) big, so that free
370 cell list code can work. Moreover we round cell sizes
371 to 16 bytes, so creating a smaller block would result in
372 a cell that would never be allocated. */
373 if ((ULONG)FreeCell->Size > Size + 16)
374 {
375 NewCell = (PHCELL)((ULONG_PTR)FreeCell + Size);
376 NewCell->Size = FreeCell->Size - Size;
377 FreeCell->Size = Size;
378 HvpAddFree(RegistryHive, NewCell, FreeCellOffset + Size);
379 if (Storage == Stable)
380 HvMarkCellDirty(RegistryHive, FreeCellOffset + Size, FALSE);
381 }
382
383 if (Storage == Stable)
384 HvMarkCellDirty(RegistryHive, FreeCellOffset, FALSE);
385 FreeCell->Size = -FreeCell->Size;
386 RtlZeroMemory(FreeCell + 1, Size - sizeof(HCELL));
387
388 CMLTRACE(CMLIB_HCELL_DEBUG, "%s - CellIndex %08lx\n",
389 __FUNCTION__, FreeCellOffset);
390
391 return FreeCellOffset;
392 }
393
394 HCELL_INDEX CMAPI
395 HvReallocateCell(
396 PHHIVE RegistryHive,
397 HCELL_INDEX CellIndex,
398 ULONG Size)
399 {
400 PVOID OldCell;
401 PVOID NewCell;
402 LONG OldCellSize;
403 HCELL_INDEX NewCellIndex;
404 HSTORAGE_TYPE Storage;
405
406 ASSERT(CellIndex != HCELL_NIL);
407
408 CMLTRACE(CMLIB_HCELL_DEBUG, "%s - Hive %p, CellIndex %08lx, Size %x\n",
409 __FUNCTION__, RegistryHive, CellIndex, Size);
410
411 Storage = (CellIndex & HCELL_TYPE_MASK) >> HCELL_TYPE_SHIFT;
412
413 OldCell = HvGetCell(RegistryHive, CellIndex);
414 OldCellSize = HvGetCellSize(RegistryHive, OldCell);
415 ASSERT(OldCellSize > 0);
416
417 /*
418 * If new data size is larger than the current, destroy current
419 * data block and allocate a new one.
420 *
421 * FIXME: Merge with adjacent free cell if possible.
422 * FIXME: Implement shrinking.
423 */
424 if (Size > (ULONG)OldCellSize)
425 {
426 NewCellIndex = HvAllocateCell(RegistryHive, Size, Storage, HCELL_NIL);
427 if (NewCellIndex == HCELL_NIL)
428 return HCELL_NIL;
429
430 NewCell = HvGetCell(RegistryHive, NewCellIndex);
431 RtlCopyMemory(NewCell, OldCell, (SIZE_T)OldCellSize);
432
433 HvFreeCell(RegistryHive, CellIndex);
434
435 return NewCellIndex;
436 }
437
438 return CellIndex;
439 }
440
441 VOID CMAPI
442 HvFreeCell(
443 PHHIVE RegistryHive,
444 HCELL_INDEX CellIndex)
445 {
446 PHCELL Free;
447 PHCELL Neighbor;
448 PHBIN Bin;
449 ULONG CellType;
450 ULONG CellBlock;
451
452 ASSERT(RegistryHive->ReadOnly == FALSE);
453
454 CMLTRACE(CMLIB_HCELL_DEBUG, "%s - Hive %p, CellIndex %08lx\n",
455 __FUNCTION__, RegistryHive, CellIndex);
456
457 Free = HvpGetCellHeader(RegistryHive, CellIndex);
458
459 ASSERT(Free->Size < 0);
460
461 Free->Size = -Free->Size;
462
463 CellType = (CellIndex & HCELL_TYPE_MASK) >> HCELL_TYPE_SHIFT;
464 CellBlock = (CellIndex & HCELL_BLOCK_MASK) >> HCELL_BLOCK_SHIFT;
465
466 /* FIXME: Merge free blocks */
467 Bin = (PHBIN)RegistryHive->Storage[CellType].BlockList[CellBlock].BinAddress;
468
469 if ((CellIndex & ~HCELL_TYPE_MASK) + Free->Size <
470 Bin->FileOffset + Bin->Size)
471 {
472 Neighbor = (PHCELL)((ULONG_PTR)Free + Free->Size);
473 if (Neighbor->Size > 0)
474 {
475 HvpRemoveFree(RegistryHive, Neighbor,
476 ((HCELL_INDEX)((ULONG_PTR)Neighbor - (ULONG_PTR)Bin +
477 Bin->FileOffset)) | (CellIndex & HCELL_TYPE_MASK));
478 Free->Size += Neighbor->Size;
479 }
480 }
481
482 Neighbor = (PHCELL)(Bin + 1);
483 while (Neighbor < Free)
484 {
485 if (Neighbor->Size > 0)
486 {
487 if ((ULONG_PTR)Neighbor + Neighbor->Size == (ULONG_PTR)Free)
488 {
489 HCELL_INDEX NeighborCellIndex =
490 (HCELL_INDEX)((ULONG_PTR)Neighbor - (ULONG_PTR)Bin +
491 Bin->FileOffset) | (CellIndex & HCELL_TYPE_MASK);
492
493 if (HvpComputeFreeListIndex(Neighbor->Size) !=
494 HvpComputeFreeListIndex(Neighbor->Size + Free->Size))
495 {
496 HvpRemoveFree(RegistryHive, Neighbor, NeighborCellIndex);
497 Neighbor->Size += Free->Size;
498 HvpAddFree(RegistryHive, Neighbor, NeighborCellIndex);
499 }
500 else
501 Neighbor->Size += Free->Size;
502
503 if (CellType == Stable)
504 HvMarkCellDirty(RegistryHive, NeighborCellIndex, FALSE);
505
506 return;
507 }
508 Neighbor = (PHCELL)((ULONG_PTR)Neighbor + Neighbor->Size);
509 }
510 else
511 {
512 Neighbor = (PHCELL)((ULONG_PTR)Neighbor - Neighbor->Size);
513 }
514 }
515
516 /* Add block to the list of free blocks */
517 HvpAddFree(RegistryHive, Free, CellIndex);
518
519 if (CellType == Stable)
520 HvMarkCellDirty(RegistryHive, CellIndex, FALSE);
521 }
522
523 BOOLEAN
524 CMAPI
525 HvTrackCellRef(PHV_TRACK_CELL_REF CellRef,
526 PHHIVE Hive,
527 HCELL_INDEX Cell)
528 {
529 /* Sanity checks */
530 ASSERT(CellRef);
531 ASSERT(Hive );
532 ASSERT(Cell != HCELL_NIL);
533
534 /* Less than 4? */
535 if (CellRef->StaticCount < STATIC_CELL_PAIR_COUNT)
536 {
537 /* Add reference */
538 CellRef->StaticArray[CellRef->StaticCount].Hive = Hive;
539 CellRef->StaticArray[CellRef->StaticCount].Cell = Cell;
540 CellRef->StaticCount++;
541 return TRUE;
542 }
543
544 /* FIXME: TODO */
545 ASSERTMSG("ERROR: Too many references\n", FALSE);
546 return FALSE;
547 }
548
549 VOID
550 CMAPI
551 HvReleaseFreeCellRefArray(PHV_TRACK_CELL_REF CellRef)
552 {
553 ULONG i;
554 ASSERT(CellRef);
555
556 /* Any references? */
557 if (CellRef->StaticCount > 0)
558 {
559 /* Sanity check */
560 ASSERT(CellRef->StaticCount <= STATIC_CELL_PAIR_COUNT);
561
562 /* Loop them */
563 for (i = 0; i < CellRef->StaticCount;i++)
564 {
565 /* Release them */
566 HvReleaseCell(CellRef->StaticArray[i].Hive,
567 CellRef->StaticArray[i].Cell);
568 }
569
570 /* Free again */
571 CellRef->StaticCount = 0;
572 }
573 }