[NTOSKRNL]
[reactos.git] / reactos / ntoskrnl / fsrtl / largemcb.c
1 /*
2 * PROJECT: ReactOS Kernel
3 * LICENSE: GPL - See COPYING in the top level directory
4 * FILE: ntoskrnl/fsrtl/largemcb.c
5 * PURPOSE: Large Mapped Control Block (MCB) support for File System Drivers
6 * PROGRAMMERS: Alex Ionescu (alex.ionescu@reactos.org)
7 * Pierre Schweitzer (heis_spiter@hotmail.com)
8 * Art Yerkes (art.yerkes@gmail.com)
9 */
10
11 /* INCLUDES ******************************************************************/
12
13 #include <ntoskrnl.h>
14 #define NDEBUG
15 #include <debug.h>
16
17 /* GLOBALS *******************************************************************/
18
19 #define GET_LIST_HEAD(x) ((PLIST_ENTRY)(&((PRTL_GENERIC_TABLE)x)[1]))
20
21 PAGED_LOOKASIDE_LIST FsRtlFirstMappingLookasideList;
22 NPAGED_LOOKASIDE_LIST FsRtlFastMutexLookasideList;
23
24 typedef struct _LARGE_MCB_MAPPING_ENTRY
25 {
26 LARGE_INTEGER RunStartVbn;
27 LARGE_INTEGER SectorCount;
28 LARGE_INTEGER StartingLbn;
29 LIST_ENTRY Sequence;
30 } LARGE_MCB_MAPPING_ENTRY, *PLARGE_MCB_MAPPING_ENTRY;
31
32 static VOID McbPrintTree(PBASE_MCB Mcb)
33 {
34 PLARGE_MCB_MAPPING_ENTRY Entry;
35 for (Entry = (PLARGE_MCB_MAPPING_ENTRY)
36 RtlEnumerateGenericTable(Mcb->Mapping, TRUE);
37 Entry;
38 Entry = (PLARGE_MCB_MAPPING_ENTRY)
39 RtlEnumerateGenericTable(Mcb->Mapping, FALSE))
40 {
41 DPRINT1
42 ("Vbn %x Lbn %x Count %x\n",
43 Entry->RunStartVbn.LowPart,
44 Entry->StartingLbn.LowPart,
45 Entry->SectorCount.LowPart);
46 }
47 }
48
49 static PVOID NTAPI McbMappingAllocate(PRTL_GENERIC_TABLE Table, CLONG Bytes)
50 {
51 PVOID Result;
52 PBASE_MCB Mcb = (PBASE_MCB)Table->TableContext;
53 Result = ExAllocatePoolWithTag(Mcb->PoolType, Bytes, 'LMCB');
54 DPRINT("McbMappingAllocate(%d) => %p\n", Bytes, Result);
55 return Result;
56 }
57
58 static VOID NTAPI McbMappingFree(PRTL_GENERIC_TABLE Table, PVOID Buffer)
59 {
60 DPRINT("McbMappingFree(%p)\n", Buffer);
61 ExFreePoolWithTag(Buffer, 'LMCB');
62 }
63
64 static RTL_GENERIC_COMPARE_RESULTS NTAPI McbMappingCompare
65 (PRTL_GENERIC_TABLE Table, PVOID PtrA, PVOID PtrB)
66 {
67 PLARGE_MCB_MAPPING_ENTRY A = PtrA, B = PtrB;
68 RTL_GENERIC_COMPARE_RESULTS Result;
69 DPRINT("Starting to compare element %x to element %x\n", PtrA, PtrB);
70 Result =
71 (A->RunStartVbn.QuadPart + A->SectorCount.QuadPart <=
72 B->RunStartVbn.QuadPart) ? GenericLessThan :
73 (A->RunStartVbn.QuadPart >=
74 B->RunStartVbn.QuadPart + B->SectorCount.QuadPart) ?
75 GenericGreaterThan : GenericEqual;
76 DPRINT("Compare(%x:%x): %x:%x to %x:%x => %d\n",
77 A,B,
78 A->RunStartVbn.LowPart, A->SectorCount.LowPart,
79 B->RunStartVbn.LowPart, B->SectorCount.LowPart,
80 Result);
81 return Result;
82 }
83
84 /* PUBLIC FUNCTIONS **********************************************************/
85
86 /*
87 * @implemented
88 */
89 BOOLEAN
90 NTAPI
91 FsRtlAddBaseMcbEntry(IN PBASE_MCB Mcb,
92 IN LONGLONG Vbn,
93 IN LONGLONG Lbn,
94 IN LONGLONG SectorCount)
95 {
96 LARGE_MCB_MAPPING_ENTRY Node;
97 PLARGE_MCB_MAPPING_ENTRY Existing = NULL;
98 BOOLEAN NewElement = FALSE;
99
100 McbPrintTree(Mcb);
101
102 Node.RunStartVbn.QuadPart = Vbn;
103 Node.StartingLbn.QuadPart = Lbn;
104 Node.SectorCount.QuadPart = SectorCount;
105
106 DPRINT("RunStartVbn %x\n", Node.RunStartVbn.LowPart);
107 DPRINT("StartingLbn %x\n", Node.StartingLbn.LowPart);
108 DPRINT("SectorCount %x\n", Node.SectorCount.LowPart);
109
110 while (!NewElement)
111 {
112 DPRINT("Inserting %x:%x\n", Node.RunStartVbn.LowPart, Node.SectorCount.LowPart);
113 Existing = RtlInsertElementGenericTable
114 (Mcb->Mapping, &Node, sizeof(Node), &NewElement);
115 DPRINT("Existing %x\n", Existing);
116 if (!Existing) break;
117
118 DPRINT("NewElement %d\n", NewElement);
119 if (!NewElement)
120 {
121 // We merge the existing runs
122 LARGE_INTEGER StartVbn, FinalVbn;
123 DPRINT("Existing: %x:%x\n",
124 Existing->RunStartVbn.LowPart, Node.SectorCount.LowPart);
125 if (Existing->RunStartVbn.QuadPart < Node.RunStartVbn.QuadPart)
126 {
127 StartVbn = Existing->RunStartVbn;
128 Node.StartingLbn = Existing->StartingLbn;
129 }
130 else
131 {
132 StartVbn = Node.RunStartVbn;
133 }
134 DPRINT("StartVbn %x\n", StartVbn.LowPart);
135 if (Existing->RunStartVbn.QuadPart + Existing->SectorCount.QuadPart >
136 Node.RunStartVbn.QuadPart + Node.SectorCount.QuadPart)
137 {
138 FinalVbn.QuadPart =
139 Existing->RunStartVbn.QuadPart + Existing->SectorCount.QuadPart;
140 }
141 else
142 {
143 FinalVbn.QuadPart =
144 Node.RunStartVbn.QuadPart + Node.SectorCount.QuadPart;
145 }
146 DPRINT("FinalVbn %x\n", FinalVbn.LowPart);
147 Node.RunStartVbn.QuadPart = StartVbn.QuadPart;
148 Node.SectorCount.QuadPart = FinalVbn.QuadPart - StartVbn.QuadPart;
149 RemoveHeadList(&Existing->Sequence);
150 RtlDeleteElementGenericTable(Mcb->Mapping, Existing);
151 Mcb->PairCount--;
152 }
153 else
154 {
155 DPRINT("Mapping added %x\n", Existing);
156 Mcb->MaximumPairCount++;
157 Mcb->PairCount++;
158 InsertHeadList(GET_LIST_HEAD(Mcb->Mapping), &Existing->Sequence);
159 }
160 }
161
162 DPRINT("!!Existing %d\n", !!Existing);
163 McbPrintTree(Mcb);
164 return !!Existing;
165 }
166
167 /*
168 * @implemented
169 */
170 BOOLEAN
171 NTAPI
172 FsRtlAddLargeMcbEntry(IN PLARGE_MCB Mcb,
173 IN LONGLONG Vbn,
174 IN LONGLONG Lbn,
175 IN LONGLONG SectorCount)
176 {
177 BOOLEAN Result;
178
179 DPRINT
180 ("Mcb %x Vbn %x Lbn %x SectorCount %x\n",
181 Mcb, (ULONG)Vbn, (ULONG)Lbn, (ULONG)SectorCount);
182
183 KeAcquireGuardedMutex(Mcb->GuardedMutex);
184 Result = FsRtlAddBaseMcbEntry(&(Mcb->BaseMcb),
185 Vbn,
186 Lbn,
187 SectorCount);
188 KeReleaseGuardedMutex(Mcb->GuardedMutex);
189
190 DPRINT("Done %d\n", Result);
191
192 return Result;
193 }
194
195 /*
196 * @unimplemented
197 */
198 BOOLEAN
199 NTAPI
200 FsRtlGetNextBaseMcbEntry(IN PBASE_MCB Mcb,
201 IN ULONG RunIndex,
202 OUT PLONGLONG Vbn,
203 OUT PLONGLONG Lbn,
204 OUT PLONGLONG SectorCount)
205 {
206 ULONG i = 0;
207 BOOLEAN Result = FALSE;
208 PLARGE_MCB_MAPPING_ENTRY Entry;
209 for (Entry = (PLARGE_MCB_MAPPING_ENTRY)
210 RtlEnumerateGenericTable(Mcb->Mapping, TRUE);
211 Entry && i < RunIndex;
212 Entry = (PLARGE_MCB_MAPPING_ENTRY)
213 RtlEnumerateGenericTable(Mcb->Mapping, FALSE), i++);
214 if (Entry)
215 {
216 Result = TRUE;
217 if (Vbn)
218 *Vbn = Entry->RunStartVbn.QuadPart;
219 if (Lbn)
220 *Lbn = Entry->StartingLbn.QuadPart;
221 if (SectorCount)
222 *SectorCount = Entry->SectorCount.QuadPart;
223 }
224
225 return Result;
226 }
227
228 /*
229 * @implemented
230 */
231 BOOLEAN
232 NTAPI
233 FsRtlGetNextLargeMcbEntry(IN PLARGE_MCB Mcb,
234 IN ULONG RunIndex,
235 OUT PLONGLONG Vbn,
236 OUT PLONGLONG Lbn,
237 OUT PLONGLONG SectorCount)
238 {
239 BOOLEAN Result;
240
241 DPRINT("FsRtlGetNextLargeMcbEntry Mcb %x RunIndex %x\n", Mcb, RunIndex);
242
243 KeAcquireGuardedMutex(Mcb->GuardedMutex);
244 Result = FsRtlGetNextBaseMcbEntry(&(Mcb->BaseMcb),
245 RunIndex,
246 Vbn,
247 Lbn,
248 SectorCount);
249 KeReleaseGuardedMutex(Mcb->GuardedMutex);
250
251 DPRINT("Done %d\n", Result);
252
253 return Result;
254 }
255
256 /*
257 * @implemented
258 */
259 VOID
260 NTAPI
261 FsRtlInitializeBaseMcb(IN PBASE_MCB Mcb,
262 IN POOL_TYPE PoolType)
263 {
264 Mcb->PairCount = 0;
265
266 if (PoolType == PagedPool)
267 {
268 Mcb->Mapping = ExAllocateFromPagedLookasideList(&FsRtlFirstMappingLookasideList);
269 DPRINT("Get from lookaside list\n");
270 }
271 else
272 {
273 Mcb->Mapping = ExAllocatePoolWithTag(PoolType | POOL_RAISE_IF_ALLOCATION_FAILURE,
274 sizeof(RTL_GENERIC_TABLE) + sizeof(LIST_ENTRY),
275 'FSBC');
276 DPRINT("Allocate\n");
277 }
278
279 DPRINT("Mcb->Mapping %x\n", Mcb->Mapping);
280 Mcb->PoolType = PoolType;
281 Mcb->MaximumPairCount = MAXIMUM_PAIR_COUNT;
282 RtlInitializeGenericTable
283 (Mcb->Mapping,
284 McbMappingCompare,
285 McbMappingAllocate,
286 McbMappingFree,
287 Mcb);
288 InitializeListHead(GET_LIST_HEAD(Mcb->Mapping));
289 }
290
291 /*
292 * @implemented
293 */
294 VOID
295 NTAPI
296 FsRtlInitializeLargeMcb(IN PLARGE_MCB Mcb,
297 IN POOL_TYPE PoolType)
298 {
299 Mcb->GuardedMutex = ExAllocateFromNPagedLookasideList(&FsRtlFastMutexLookasideList);
300
301 KeInitializeGuardedMutex(Mcb->GuardedMutex);
302
303 _SEH2_TRY
304 {
305 FsRtlInitializeBaseMcb(&(Mcb->BaseMcb), PoolType);
306 }
307 _SEH2_EXCEPT(EXCEPTION_EXECUTE_HANDLER)
308 {
309 ExFreeToNPagedLookasideList(&FsRtlFastMutexLookasideList,
310 Mcb->GuardedMutex);
311 Mcb->GuardedMutex = NULL;
312 }
313 _SEH2_END;
314 }
315
316 /*
317 * @implemented
318 */
319 VOID
320 NTAPI
321 FsRtlInitializeLargeMcbs(VOID)
322 {
323 /* Initialize the list for the MCB */
324 ExInitializePagedLookasideList(&FsRtlFirstMappingLookasideList,
325 NULL,
326 NULL,
327 POOL_RAISE_IF_ALLOCATION_FAILURE,
328 sizeof(RTL_GENERIC_TABLE) + sizeof(LIST_ENTRY),
329 IFS_POOL_TAG,
330 0); /* FIXME: Should be 4 */
331
332 /* Initialize the list for the guarded mutex */
333 ExInitializeNPagedLookasideList(&FsRtlFastMutexLookasideList,
334 NULL,
335 NULL,
336 POOL_RAISE_IF_ALLOCATION_FAILURE,
337 sizeof(KGUARDED_MUTEX),
338 IFS_POOL_TAG,
339 0); /* FIXME: Should be 32 */
340 }
341
342 /*
343 * @unimplemented
344 */
345 BOOLEAN
346 NTAPI
347 FsRtlLookupBaseMcbEntry(IN PBASE_MCB Mcb,
348 IN LONGLONG Vbn,
349 OUT PLONGLONG Lbn OPTIONAL,
350 OUT PLONGLONG SectorCountFromLbn OPTIONAL,
351 OUT PLONGLONG StartingLbn OPTIONAL,
352 OUT PLONGLONG SectorCountFromStartingLbn OPTIONAL,
353 OUT PULONG Index OPTIONAL)
354 {
355 BOOLEAN Result = FALSE;
356 LARGE_MCB_MAPPING_ENTRY ToLookup;
357 PLARGE_MCB_MAPPING_ENTRY Entry;
358
359 ToLookup.RunStartVbn.QuadPart = Vbn;
360 ToLookup.SectorCount.QuadPart = 1;
361
362 Entry = RtlLookupElementGenericTable(Mcb->Mapping, &ToLookup);
363 if (!Entry)
364 {
365 // Find out if we have a following entry. The spec says we should return
366 // found with Lbn == -1 when we're beneath the largest map.
367 ToLookup.SectorCount.QuadPart = (1ull<<62) - ToLookup.RunStartVbn.QuadPart;
368 Entry = RtlLookupElementGenericTable(Mcb->Mapping, &ToLookup);
369 if (Entry)
370 {
371 Result = TRUE;
372 if (Lbn) *Lbn = ~0ull;
373 }
374 else
375 {
376 Result = FALSE;
377 }
378 }
379 else
380 {
381 LARGE_INTEGER Offset;
382 Offset.QuadPart = Vbn - Entry->RunStartVbn.QuadPart;
383 Result = TRUE;
384 if (Lbn) *Lbn = Entry->StartingLbn.QuadPart + Offset.QuadPart;
385 if (SectorCountFromLbn) *SectorCountFromLbn = Entry->SectorCount.QuadPart - Offset.QuadPart;
386 if (StartingLbn) *StartingLbn = Entry->StartingLbn.QuadPart;
387 if (SectorCountFromStartingLbn) *SectorCountFromStartingLbn = Entry->SectorCount.QuadPart;
388 }
389
390 return Result;
391 }
392
393 /*
394 * @implemented
395 */
396 BOOLEAN
397 NTAPI
398 FsRtlLookupLargeMcbEntry(IN PLARGE_MCB Mcb,
399 IN LONGLONG Vbn,
400 OUT PLONGLONG Lbn OPTIONAL,
401 OUT PLONGLONG SectorCountFromLbn OPTIONAL,
402 OUT PLONGLONG StartingLbn OPTIONAL,
403 OUT PLONGLONG SectorCountFromStartingLbn OPTIONAL,
404 OUT PULONG Index OPTIONAL)
405 {
406 BOOLEAN Result;
407
408 DPRINT("FsRtlLookupLargeMcbEntry Mcb %x Vbn %x\n", Mcb, (ULONG)Vbn);
409
410 KeAcquireGuardedMutex(Mcb->GuardedMutex);
411 Result = FsRtlLookupBaseMcbEntry(&(Mcb->BaseMcb),
412 Vbn,
413 Lbn,
414 SectorCountFromLbn,
415 StartingLbn,
416 SectorCountFromStartingLbn,
417 Index);
418 KeReleaseGuardedMutex(Mcb->GuardedMutex);
419
420 DPRINT("Done %d (%x)\n", Result, Lbn ? (ULONG)*Lbn : 0);
421
422 return Result;
423 }
424
425 /*
426 * @unimplemented
427 */
428 BOOLEAN
429 NTAPI
430 FsRtlLookupLastBaseMcbEntryAndIndex(IN PBASE_MCB OpaqueMcb,
431 IN OUT PLONGLONG LargeVbn,
432 IN OUT PLONGLONG LargeLbn,
433 IN OUT PULONG Index)
434 {
435 ULONG i = 0;
436 BOOLEAN Result = FALSE;
437 PLIST_ENTRY ListEntry;
438 PLARGE_MCB_MAPPING_ENTRY Entry;
439 PLARGE_MCB_MAPPING_ENTRY CountEntry;
440
441 ListEntry = GET_LIST_HEAD(OpaqueMcb->Mapping);
442 if (!IsListEmpty(ListEntry))
443 {
444 Entry = CONTAINING_RECORD(ListEntry->Flink, LARGE_MCB_MAPPING_ENTRY, Sequence);
445 Result = TRUE;
446 *LargeVbn = Entry->RunStartVbn.QuadPart;
447 *LargeLbn = Entry->StartingLbn.QuadPart;
448
449 for (i = 0, CountEntry = RtlEnumerateGenericTable(OpaqueMcb->Mapping, TRUE);
450 CountEntry != Entry;
451 CountEntry = RtlEnumerateGenericTable(OpaqueMcb->Mapping, FALSE));
452
453 *Index = i;
454 }
455
456 return Result;
457 }
458
459 /*
460 * @implemented
461 */
462 BOOLEAN
463 NTAPI
464 FsRtlLookupLastLargeMcbEntryAndIndex(IN PLARGE_MCB OpaqueMcb,
465 OUT PLONGLONG LargeVbn,
466 OUT PLONGLONG LargeLbn,
467 OUT PULONG Index)
468 {
469 BOOLEAN Result;
470
471 DPRINT("FsRtlLookupLastLargeMcbEntryAndIndex %x\n", OpaqueMcb);
472
473 KeAcquireGuardedMutex(OpaqueMcb->GuardedMutex);
474 Result = FsRtlLookupLastBaseMcbEntryAndIndex(&(OpaqueMcb->BaseMcb),
475 LargeVbn,
476 LargeLbn,
477 Index);
478 KeReleaseGuardedMutex(OpaqueMcb->GuardedMutex);
479
480 DPRINT("Done %d\n", Result);
481
482 return Result;
483 }
484
485 /*
486 * @unimplemented
487 */
488 BOOLEAN
489 NTAPI
490 FsRtlLookupLastBaseMcbEntry(IN PBASE_MCB Mcb,
491 OUT PLONGLONG Vbn,
492 OUT PLONGLONG Lbn)
493 {
494 BOOLEAN Result = FALSE;
495 PLIST_ENTRY ListEntry;
496 PLARGE_MCB_MAPPING_ENTRY Entry;
497
498 ListEntry = GET_LIST_HEAD(Mcb->Mapping);
499 if (!IsListEmpty(ListEntry))
500 {
501 Entry = CONTAINING_RECORD(ListEntry->Flink, LARGE_MCB_MAPPING_ENTRY, Sequence);
502 Result = TRUE;
503 *Vbn = Entry->RunStartVbn.QuadPart;
504 *Lbn = Entry->StartingLbn.QuadPart;
505 }
506
507 return Result;
508 }
509
510 /*
511 * @implemented
512 */
513 BOOLEAN
514 NTAPI
515 FsRtlLookupLastLargeMcbEntry(IN PLARGE_MCB Mcb,
516 OUT PLONGLONG Vbn,
517 OUT PLONGLONG Lbn)
518 {
519 BOOLEAN Result;
520
521 DPRINT("FsRtlLookupLastLargeMcbEntry Mcb %x\n", Mcb);
522
523 KeAcquireGuardedMutex(Mcb->GuardedMutex);
524 Result = FsRtlLookupLastBaseMcbEntry(&(Mcb->BaseMcb),
525 Vbn,
526 Lbn);
527 KeReleaseGuardedMutex(Mcb->GuardedMutex);
528
529 DPRINT("Done %d\n", Result);
530
531 return Result;
532 }
533
534 /*
535 * @implemented
536 */
537 ULONG
538 NTAPI
539 FsRtlNumberOfRunsInBaseMcb(IN PBASE_MCB Mcb)
540 {
541 /* Return the count */
542 return Mcb->PairCount;
543 }
544
545 /*
546 * @implemented
547 */
548 ULONG
549 NTAPI
550 FsRtlNumberOfRunsInLargeMcb(IN PLARGE_MCB Mcb)
551 {
552 ULONG NumberOfRuns;
553
554 DPRINT("FsRtlNumberOfRunsInLargeMcb Mcb %x\n", Mcb);
555
556 /* Read the number of runs while holding the MCB lock */
557 KeAcquireGuardedMutex(Mcb->GuardedMutex);
558 NumberOfRuns = Mcb->BaseMcb.PairCount;
559 KeReleaseGuardedMutex(Mcb->GuardedMutex);
560
561 DPRINT("Done %d\n", NumberOfRuns);
562
563 /* Return the count */
564 return NumberOfRuns;
565 }
566
567 /*
568 * @unimplemented
569 */
570 VOID
571 NTAPI
572 FsRtlRemoveBaseMcbEntry(IN PBASE_MCB Mcb,
573 IN LONGLONG Vbn,
574 IN LONGLONG SectorCount)
575 {
576 LARGE_MCB_MAPPING_ENTRY Node;
577 PLARGE_MCB_MAPPING_ENTRY Element;
578
579 Node.RunStartVbn.QuadPart = Vbn;
580 Node.SectorCount.QuadPart = SectorCount;
581
582 while ((Element = RtlLookupElementGenericTable(Mcb->Mapping, &Node)))
583 {
584 // Must split
585 if (Element->RunStartVbn.QuadPart < Node.RunStartVbn.QuadPart &&
586 Element->SectorCount.QuadPart > Node.SectorCount.QuadPart)
587 {
588 LARGE_MCB_MAPPING_ENTRY Upper, Reinsert;
589 PLARGE_MCB_MAPPING_ENTRY Reinserted, Inserted;
590 LARGE_INTEGER StartHole = Node.RunStartVbn;
591 LARGE_INTEGER EndHole;
592 EndHole.QuadPart = Node.RunStartVbn.QuadPart + Node.SectorCount.QuadPart;
593 Upper.RunStartVbn.QuadPart = EndHole.QuadPart;
594 Upper.StartingLbn.QuadPart =
595 Element->StartingLbn.QuadPart +
596 EndHole.QuadPart -
597 Element->RunStartVbn.QuadPart;
598 Upper.SectorCount.QuadPart =
599 Element->SectorCount.QuadPart -
600 (EndHole.QuadPart - Element->RunStartVbn.QuadPart);
601 Reinsert = *Element;
602 Reinsert.SectorCount.QuadPart =
603 Element->RunStartVbn.QuadPart - StartHole.QuadPart;
604 RemoveEntryList(&Element->Sequence);
605 RtlDeleteElementGenericTable(Mcb->Mapping, Element);
606 Mcb->PairCount--;
607
608 Reinserted = RtlInsertElementGenericTable
609 (Mcb->Mapping, &Reinsert, sizeof(Reinsert), NULL);
610 InsertHeadList(GET_LIST_HEAD(Mcb->Mapping), &Reinserted->Sequence);
611 Mcb->PairCount++;
612
613 Inserted = RtlInsertElementGenericTable
614 (Mcb->Mapping, &Upper, sizeof(Upper), NULL);
615 InsertHeadList(GET_LIST_HEAD(Mcb->Mapping), &Inserted->Sequence);
616 Mcb->PairCount++;
617 }
618 else if (Element->RunStartVbn.QuadPart < Node.RunStartVbn.QuadPart)
619 {
620 LARGE_MCB_MAPPING_ENTRY NewElement;
621 PLARGE_MCB_MAPPING_ENTRY Reinserted;
622 LARGE_INTEGER StartHole = Node.RunStartVbn;
623 NewElement.RunStartVbn = Element->RunStartVbn;
624 NewElement.StartingLbn = Element->StartingLbn;
625 NewElement.SectorCount.QuadPart = StartHole.QuadPart - Element->StartingLbn.QuadPart;
626
627 RemoveEntryList(&Element->Sequence);
628 RtlDeleteElementGenericTable(Mcb->Mapping, Element);
629 Mcb->PairCount--;
630
631 Reinserted = RtlInsertElementGenericTable
632 (Mcb->Mapping, &NewElement, sizeof(NewElement), NULL);
633 InsertHeadList(GET_LIST_HEAD(Mcb->Mapping), &Reinserted->Sequence);
634 Mcb->PairCount++;
635 }
636 else
637 {
638 LARGE_MCB_MAPPING_ENTRY NewElement;
639 PLARGE_MCB_MAPPING_ENTRY Reinserted;
640 LARGE_INTEGER EndHole = Element->RunStartVbn;
641 LARGE_INTEGER EndRun;
642 EndRun.QuadPart = Element->RunStartVbn.QuadPart + Element->SectorCount.QuadPart;
643 NewElement.RunStartVbn = EndHole;
644 NewElement.StartingLbn.QuadPart = Element->StartingLbn.QuadPart +
645 (EndHole.QuadPart - Element->RunStartVbn.QuadPart);
646 NewElement.SectorCount.QuadPart = EndRun.QuadPart - EndHole.QuadPart;
647
648 RemoveEntryList(&Element->Sequence);
649 RtlDeleteElementGenericTable(Mcb->Mapping, Element);
650 Mcb->PairCount--;
651
652 Reinserted = RtlInsertElementGenericTable
653 (Mcb->Mapping, &NewElement, sizeof(NewElement), NULL);
654 InsertHeadList(GET_LIST_HEAD(Mcb->Mapping), &Reinserted->Sequence);
655 Mcb->PairCount++;
656 }
657 }
658 }
659
660 /*
661 * @implemented
662 */
663 VOID
664 NTAPI
665 FsRtlRemoveLargeMcbEntry(IN PLARGE_MCB Mcb,
666 IN LONGLONG Vbn,
667 IN LONGLONG SectorCount)
668 {
669 DPRINT("FsRtlRemoveLargeMcbEntry Mcb %x, Vbn %x, SectorCount %x\n", Mcb, (ULONG)Vbn, (ULONG)SectorCount);
670
671 KeAcquireGuardedMutex(Mcb->GuardedMutex);
672 FsRtlRemoveBaseMcbEntry(&(Mcb->BaseMcb),
673 Vbn,
674 SectorCount);
675 KeReleaseGuardedMutex(Mcb->GuardedMutex);
676
677 DPRINT("Done\n");
678 }
679
680 /*
681 * @implemented
682 */
683 VOID
684 NTAPI
685 FsRtlResetBaseMcb(IN PBASE_MCB Mcb)
686 {
687 PLARGE_MCB_MAPPING_ENTRY Element;
688
689 DPRINT("Reset MCB %x\n", Mcb);
690 while (RtlNumberGenericTableElements(Mcb->Mapping) &&
691 (Element = (PLARGE_MCB_MAPPING_ENTRY)RtlGetElementGenericTable(Mcb->Mapping, 0)))
692 {
693 DPRINT("Deleting %x\n", Element);
694 RtlDeleteElementGenericTable(Mcb->Mapping, Element);
695 }
696
697 Mcb->PairCount = 0;
698 Mcb->MaximumPairCount = 0;
699 DPRINT("Done\n");
700 }
701
702 /*
703 * @implemented
704 */
705 VOID
706 NTAPI
707 FsRtlResetLargeMcb(IN PLARGE_MCB Mcb,
708 IN BOOLEAN SelfSynchronized)
709 {
710 if (!SelfSynchronized)
711 {
712 KeAcquireGuardedMutex(Mcb->GuardedMutex);
713 }
714
715 FsRtlResetBaseMcb(&Mcb->BaseMcb);
716
717
718 if (!SelfSynchronized)
719 {
720 KeReleaseGuardedMutex(Mcb->GuardedMutex);
721 }
722 }
723
724 #define MCB_BUMP_NO_MORE 0
725 #define MCB_BUMP_AGAIN 1
726
727 static ULONG NTAPI McbBump(PBASE_MCB Mcb, PLARGE_MCB_MAPPING_ENTRY FixedPart)
728 {
729 LARGE_MCB_MAPPING_ENTRY Reimagined;
730 PLARGE_MCB_MAPPING_ENTRY Found = NULL;
731
732 DPRINT("McbBump %x (%x:%x)\n", Mcb, FixedPart->RunStartVbn.LowPart, FixedPart->SectorCount.LowPart);
733
734 Reimagined = *FixedPart;
735 while ((Found = RtlLookupElementGenericTable(Mcb->Mapping, &Reimagined)))
736 {
737 Reimagined = *Found;
738 Reimagined.RunStartVbn.QuadPart =
739 FixedPart->RunStartVbn.QuadPart + FixedPart->SectorCount.QuadPart;
740 DPRINT("Reimagined %x\n", Reimagined.RunStartVbn.LowPart);
741 }
742
743 DPRINT("Found %x\n", Found);
744 if (!Found) return MCB_BUMP_NO_MORE;
745 DPRINT1
746 ("Moving %x-%x to %x because %x-%x overlaps\n",
747 Found->RunStartVbn.LowPart,
748 Found->RunStartVbn.LowPart + Found->SectorCount.QuadPart,
749 Reimagined.RunStartVbn.LowPart + Reimagined.SectorCount.LowPart,
750 Reimagined.RunStartVbn.LowPart,
751 Reimagined.RunStartVbn.LowPart + Reimagined.SectorCount.LowPart);
752 Found->RunStartVbn.QuadPart = Reimagined.RunStartVbn.QuadPart + Reimagined.SectorCount.QuadPart;
753 Found->StartingLbn.QuadPart = Reimagined.StartingLbn.QuadPart + Reimagined.SectorCount.QuadPart;
754
755 DPRINT("Again\n");
756 return MCB_BUMP_AGAIN;
757 }
758
759 /*
760 * @unimplemented
761 */
762 BOOLEAN
763 NTAPI
764 FsRtlSplitBaseMcb(IN PBASE_MCB Mcb,
765 IN LONGLONG Vbn,
766 IN LONGLONG Amount)
767 {
768 ULONG Result;
769 LARGE_MCB_MAPPING_ENTRY Node;
770 PLARGE_MCB_MAPPING_ENTRY Existing = NULL;
771
772 Node.RunStartVbn.QuadPart = Vbn;
773 Node.SectorCount.QuadPart = 0;
774
775 Existing = RtlLookupElementGenericTable(Mcb->Mapping, &Node);
776
777 if (Existing)
778 {
779 // We're in the middle of a run
780 LARGE_MCB_MAPPING_ENTRY UpperPart;
781 LARGE_MCB_MAPPING_ENTRY LowerPart;
782 PLARGE_MCB_MAPPING_ENTRY InsertedUpper;
783
784 UpperPart.RunStartVbn.QuadPart = Node.RunStartVbn.QuadPart + Amount;
785 UpperPart.SectorCount.QuadPart = Existing->RunStartVbn.QuadPart +
786 (Existing->SectorCount.QuadPart - Node.RunStartVbn.QuadPart);
787 UpperPart.StartingLbn.QuadPart = Existing->StartingLbn.QuadPart +
788 (Node.RunStartVbn.QuadPart - Existing->RunStartVbn.QuadPart);
789 LowerPart.RunStartVbn.QuadPart = Existing->RunStartVbn.QuadPart;
790 LowerPart.SectorCount.QuadPart = Node.RunStartVbn.QuadPart - Existing->RunStartVbn.QuadPart;
791 LowerPart.StartingLbn.QuadPart = Existing->StartingLbn.QuadPart;
792
793 Node = UpperPart;
794
795 DPRINT("Loop: %x\n", Node.RunStartVbn.LowPart);
796 while ((Result = McbBump(Mcb, &Node)) == MCB_BUMP_AGAIN)
797 {
798 DPRINT("Node: %x\n", Node.RunStartVbn.LowPart);
799 }
800 DPRINT("Done\n");
801
802 if (Result == MCB_BUMP_NO_MORE)
803 {
804 Node = *Existing;
805 RemoveHeadList(&Existing->Sequence);
806 RtlDeleteElementGenericTable(Mcb->Mapping, Existing);
807 Mcb->PairCount--;
808
809 // Adjust the element we found.
810 Existing->SectorCount = LowerPart.SectorCount;
811
812 InsertedUpper = RtlInsertElementGenericTable
813 (Mcb->Mapping, &UpperPart, sizeof(UpperPart), NULL);
814 if (!InsertedUpper)
815 {
816 // Just make it like it was
817 Existing->SectorCount = Node.SectorCount;
818 return FALSE;
819 }
820 InsertHeadList(GET_LIST_HEAD(Mcb->Mapping), &InsertedUpper->Sequence);
821 Mcb->PairCount++;
822 }
823 else
824 {
825 Node.RunStartVbn.QuadPart = Vbn;
826 Node.SectorCount.QuadPart = Amount;
827 while ((Result = McbBump(Mcb, &Node)) == MCB_BUMP_AGAIN);
828 return Result == MCB_BUMP_NO_MORE;
829 }
830 }
831
832 DPRINT("Done\n");
833
834 return TRUE;
835 }
836
837 /*
838 * @implemented
839 */
840 BOOLEAN
841 NTAPI
842 FsRtlSplitLargeMcb(IN PLARGE_MCB Mcb,
843 IN LONGLONG Vbn,
844 IN LONGLONG Amount)
845 {
846 BOOLEAN Result;
847
848 DPRINT("FsRtlSplitLargeMcb %x, Vbn %x, Amount %x\n", Mcb, (ULONG)Vbn, (ULONG)Amount);
849
850 KeAcquireGuardedMutex(Mcb->GuardedMutex);
851 Result = FsRtlSplitBaseMcb(&(Mcb->BaseMcb),
852 Vbn,
853 Amount);
854 KeReleaseGuardedMutex(Mcb->GuardedMutex);
855
856 DPRINT("Done %d\n", Result);
857
858 return Result;
859 }
860
861 /*
862 * @unimplemented
863 */
864 VOID
865 NTAPI
866 FsRtlTruncateBaseMcb(IN PBASE_MCB Mcb,
867 IN LONGLONG Vbn)
868 {
869 DPRINT("FsRtlTruncateBaseMcb(%x,%x)\n", Mcb, (ULONG)Vbn);
870 if (!Vbn)
871 {
872 DPRINT("Resetting\n");
873 FsRtlResetBaseMcb(Mcb);
874 }
875 else
876 {
877 LARGE_MCB_MAPPING_ENTRY Truncate;
878 PLARGE_MCB_MAPPING_ENTRY Found;
879 Truncate.RunStartVbn.QuadPart = Vbn;
880 Truncate.SectorCount.QuadPart = (1ull<<62) - Truncate.RunStartVbn.QuadPart;
881 while ((Found = RtlLookupElementGenericTable(Mcb->Mapping, &Truncate)))
882 {
883 DPRINT("Deleting %x\n", Found);
884 RemoveEntryList(&Found->Sequence);
885 RtlDeleteElementGenericTable(Mcb->Mapping, Found);
886 Mcb->PairCount--;
887 }
888 }
889 DPRINT("Done\n");
890 }
891
892 /*
893 * @implemented
894 */
895 VOID
896 NTAPI
897 FsRtlTruncateLargeMcb(IN PLARGE_MCB Mcb,
898 IN LONGLONG Vbn)
899 {
900 DPRINT("FsRtlTruncateLargeMcb %x Vbn %x\n", Mcb, (ULONG)Vbn);
901 KeAcquireGuardedMutex(Mcb->GuardedMutex);
902 FsRtlTruncateBaseMcb(&(Mcb->BaseMcb),
903 Vbn);
904 KeReleaseGuardedMutex(Mcb->GuardedMutex);
905 DPRINT("Done\n");
906 }
907
908 /*
909 * @implemented
910 */
911 VOID
912 NTAPI
913 FsRtlUninitializeBaseMcb(IN PBASE_MCB Mcb)
914 {
915 DPRINT("FsRtlUninitializeBaseMcb(%x)\n", Mcb);
916 FsRtlResetBaseMcb(Mcb);
917
918 DPRINT("Mcb->Mapping %x\n", Mcb->Mapping);
919 if (Mcb->PoolType == PagedPool)
920 {
921 DPRINT("Deallocate to lookaside list\n");
922 ExFreeToPagedLookasideList(&FsRtlFirstMappingLookasideList,
923 Mcb->Mapping);
924 }
925 else
926 {
927 DPRINT("Deallocate\n");
928 ExFreePoolWithTag(Mcb->Mapping, 'FSBC');
929 }
930 Mcb->Mapping = NULL;
931 DPRINT("Done\n");
932 }
933
934 /*
935 * @implemented
936 */
937 VOID
938 NTAPI
939 FsRtlUninitializeLargeMcb(IN PLARGE_MCB Mcb)
940 {
941 if (Mcb->GuardedMutex)
942 {
943 ExFreeToNPagedLookasideList(&FsRtlFastMutexLookasideList,
944 Mcb->GuardedMutex);
945 Mcb->GuardedMutex = NULL;
946 FsRtlUninitializeBaseMcb(&(Mcb->BaseMcb));
947 }
948 }
949
950 // MCB
951
952 /*
953 * @implemented
954 */
955 BOOLEAN
956 NTAPI
957 FsRtlAddMcbEntry(IN PMCB Mcb,
958 IN VBN Vbn,
959 IN LBN Lbn,
960 IN ULONG SectorCount)
961 {
962 /* Call the newer function */
963 return FsRtlAddLargeMcbEntry(&Mcb->
964 DummyFieldThatSizesThisStructureCorrectly,
965 (LONGLONG)Vbn,
966 (LONGLONG)Lbn,
967 (LONGLONG)SectorCount);
968 }
969
970 /*
971 * @implemented
972 */
973 BOOLEAN
974 NTAPI
975 FsRtlGetNextMcbEntry(IN PMCB Mcb,
976 IN ULONG RunIndex,
977 OUT PVBN Vbn,
978 OUT PLBN Lbn,
979 OUT PULONG SectorCount)
980 {
981 BOOLEAN Return = FALSE;
982 LONGLONG llVbn;
983 LONGLONG llLbn;
984 LONGLONG llSectorCount;
985
986 /* Call the Large version */
987 Return = FsRtlGetNextLargeMcbEntry(
988 &Mcb->DummyFieldThatSizesThisStructureCorrectly,
989 RunIndex,
990 &llVbn,
991 &llLbn,
992 &llSectorCount);
993
994 /* Return the lower 32 bits */
995 *Vbn = (ULONG)llVbn;
996 *Lbn = (ULONG)llLbn;
997 *SectorCount = (ULONG)llSectorCount;
998
999 /* And return the original value */
1000 return Return;
1001 }
1002
1003 /*
1004 * @implemented
1005 */
1006 VOID
1007 NTAPI
1008 FsRtlInitializeMcb(IN PMCB Mcb,
1009 IN POOL_TYPE PoolType)
1010 {
1011 /* Call the newer function */
1012 FsRtlInitializeLargeMcb(&Mcb->DummyFieldThatSizesThisStructureCorrectly,
1013 PoolType);
1014 }
1015
1016 /*
1017 * @implemented
1018 */
1019 BOOLEAN
1020 NTAPI
1021 FsRtlLookupLastMcbEntry(IN PMCB Mcb,
1022 OUT PVBN Vbn,
1023 OUT PLBN Lbn)
1024 {
1025 BOOLEAN Return = FALSE;
1026 LONGLONG llVbn = 0;
1027 LONGLONG llLbn = 0;
1028
1029 /* Call the Large version */
1030 Return = FsRtlLookupLastLargeMcbEntry(
1031 &Mcb->DummyFieldThatSizesThisStructureCorrectly,
1032 &llVbn,
1033 &llLbn);
1034
1035 /* Return the lower 32-bits */
1036 *Vbn = (ULONG)llVbn;
1037 *Lbn = (ULONG)llLbn;
1038
1039 /* And return the original value */
1040 return Return;
1041 }
1042
1043 /*
1044 * @implemented
1045 */
1046 BOOLEAN
1047 NTAPI
1048 FsRtlLookupMcbEntry(IN PMCB Mcb,
1049 IN VBN Vbn,
1050 OUT PLBN Lbn,
1051 OUT PULONG SectorCount OPTIONAL,
1052 OUT PULONG Index)
1053 {
1054 BOOLEAN Return = FALSE;
1055 LONGLONG llLbn;
1056 LONGLONG llSectorCount;
1057
1058 /* Call the Large version */
1059 Return = FsRtlLookupLargeMcbEntry(&Mcb->
1060 DummyFieldThatSizesThisStructureCorrectly,
1061 (LONGLONG)Vbn,
1062 &llLbn,
1063 &llSectorCount,
1064 NULL,
1065 NULL,
1066 Index);
1067
1068 /* Return the lower 32-bits */
1069 *Lbn = (ULONG)llLbn;
1070 if (SectorCount) *SectorCount = (ULONG)llSectorCount;
1071
1072 /* And return the original value */
1073 return Return;
1074 }
1075
1076 /*
1077 * @implemented
1078 */
1079 ULONG
1080 NTAPI
1081 FsRtlNumberOfRunsInMcb(IN PMCB Mcb)
1082 {
1083 /* Call the newer function */
1084 return FsRtlNumberOfRunsInLargeMcb(
1085 &Mcb->DummyFieldThatSizesThisStructureCorrectly);
1086 }
1087
1088 /*
1089 * @implemented
1090 */
1091 VOID
1092 NTAPI
1093 FsRtlRemoveMcbEntry(IN PMCB Mcb,
1094 IN VBN Vbn,
1095 IN ULONG SectorCount)
1096 {
1097 /* Call the large function */
1098 FsRtlRemoveLargeMcbEntry(&Mcb->DummyFieldThatSizesThisStructureCorrectly,
1099 (LONGLONG)Vbn,
1100 (LONGLONG)SectorCount);
1101 }
1102
1103 /*
1104 * @implemented
1105 */
1106 VOID
1107 NTAPI
1108 FsRtlTruncateMcb(IN PMCB Mcb,
1109 IN VBN Vbn)
1110 {
1111 /* Call the newer function */
1112 FsRtlTruncateLargeMcb(&Mcb->DummyFieldThatSizesThisStructureCorrectly,
1113 (LONGLONG)Vbn);
1114 }
1115
1116 /*
1117 * @implemented
1118 */
1119 VOID
1120 NTAPI
1121 FsRtlUninitializeMcb(IN PMCB Mcb)
1122 {
1123 /* Call the newer function */
1124 FsRtlUninitializeLargeMcb(&Mcb->DummyFieldThatSizesThisStructureCorrectly);
1125 }
1126