1cdc3eed91c25a1759a99bf1f6811ba872b45379
[reactos.git] / reactos / ntoskrnl / fsrtl / largemcb.c
1 /*
2 * PROJECT: ReactOS Kernel
3 * LICENSE: GPL v2 - 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: Aleksey Bragin <aleksey@reactos.org>
7 * Jan Kratochvil <project-captive@jankratochvil.net>
8 */
9
10 /* INCLUDES ******************************************************************/
11
12 #include <ntoskrnl.h>
13 #define NDEBUG
14 #include <debug.h>
15
16 #define MIN(x,y) (((x)<(y))?(x):(y))
17 #define MAX(x,y) (((x)>(y))?(x):(y))
18
19 /* GLOBALS *******************************************************************/
20
21 PAGED_LOOKASIDE_LIST FsRtlFirstMappingLookasideList;
22 NPAGED_LOOKASIDE_LIST FsRtlFastMutexLookasideList;
23
24 /* We use only real 'mapping' runs; we do not store 'holes' to our GTree. */
25 typedef struct _LARGE_MCB_MAPPING_ENTRY // run
26 {
27 LARGE_INTEGER RunStartVbn;
28 LARGE_INTEGER RunEndVbn; /* RunStartVbn+SectorCount; that means +1 after the last sector */
29 LARGE_INTEGER StartingLbn; /* Lbn of 'RunStartVbn' */
30 } LARGE_MCB_MAPPING_ENTRY, *PLARGE_MCB_MAPPING_ENTRY;
31
32 typedef struct _LARGE_MCB_MAPPING // mcb_priv
33 {
34 RTL_GENERIC_TABLE Table;
35 } LARGE_MCB_MAPPING, *PLARGE_MCB_MAPPING;
36
37 typedef struct _BASE_MCB_INTERNAL {
38 ULONG MaximumPairCount;
39 ULONG PairCount;
40 USHORT PoolType;
41 USHORT Flags;
42 PLARGE_MCB_MAPPING Mapping;
43 } BASE_MCB_INTERNAL, *PBASE_MCB_INTERNAL;
44
45 static LARGE_MCB_MAPPING_ENTRY StaticRunBelow0 = {
46 {{-1}}, /* ignored */
47 {{0}},
48 {{-1}}, /* ignored */
49 };
50
51 static PVOID NTAPI McbMappingAllocate(PRTL_GENERIC_TABLE Table, CLONG Bytes)
52 {
53 PVOID Result;
54 PBASE_MCB Mcb = (PBASE_MCB)Table->TableContext;
55 Result = ExAllocatePoolWithTag(Mcb->PoolType, Bytes, 'LMCB');
56 DPRINT("McbMappingAllocate(%lu) => %p\n", Bytes, Result);
57 return Result;
58 }
59
60 static VOID NTAPI McbMappingFree(PRTL_GENERIC_TABLE Table, PVOID Buffer)
61 {
62 DPRINT("McbMappingFree(%p)\n", Buffer);
63 ExFreePoolWithTag(Buffer, 'LMCB');
64 }
65
66 static
67 RTL_GENERIC_COMPARE_RESULTS
68 NTAPI
69 McbMappingCompare(PRTL_GENERIC_TABLE Table,
70 PVOID PtrA,
71 PVOID PtrB)
72 {
73 PLARGE_MCB_MAPPING_ENTRY A = PtrA, B = PtrB;
74 RTL_GENERIC_COMPARE_RESULTS Res;
75
76 ASSERT(A);
77 ASSERT(B);
78
79 if (A->RunStartVbn.QuadPart == B->RunStartVbn.QuadPart && A->RunEndVbn.QuadPart == B->RunEndVbn.QuadPart)
80 Res = GenericEqual;
81 else if (A->RunEndVbn.QuadPart <= B->RunStartVbn.QuadPart)
82 Res = GenericLessThan;
83 else if (A->RunEndVbn.QuadPart >= B->RunStartVbn.QuadPart)
84 Res = GenericGreaterThan;
85 else
86 {
87 ASSERT(FALSE);
88 Res = GenericEqual;
89 }
90
91 return Res;
92 }
93
94 static RTL_GENERIC_COMPARE_RESULTS NTAPI McbMappingIntersectCompare(PRTL_GENERIC_TABLE Table, PVOID PtrA, PVOID PtrB)
95 {
96 PLARGE_MCB_MAPPING_ENTRY A = PtrA, B = PtrB;
97 RTL_GENERIC_COMPARE_RESULTS Res;
98
99 if (A->RunStartVbn.QuadPart <= B->RunStartVbn.QuadPart && A->RunEndVbn.QuadPart > B->RunStartVbn.QuadPart)
100 Res = GenericEqual;
101 else if (A->RunStartVbn.QuadPart >= B->RunStartVbn.QuadPart && B->RunEndVbn.QuadPart > A->RunStartVbn.QuadPart)
102 Res = GenericEqual;
103 else if (A->RunStartVbn.QuadPart < B->RunStartVbn.QuadPart)
104 Res = GenericLessThan;
105 else if (A->RunStartVbn.QuadPart > B->RunStartVbn.QuadPart)
106 Res = GenericGreaterThan;
107 else
108 Res = GenericEqual;
109
110 return Res;
111 }
112
113
114 /* PUBLIC FUNCTIONS **********************************************************/
115
116 /*
117 * @implemented
118 * @Mcb: #PLARGE_MCB initialized by FsRtlInitializeLargeMcb().
119 * %NULL value is forbidden.
120 * @Vbn: Starting virtual block number of the wished range.
121 * @Lbn: Starting logical block number of the wished range.
122 * @SectorCount: Length of the wished range.
123 * Value less or equal to %0 is forbidden; FIXME: Is the reject of %0 W32 compliant?
124 *
125 * Adds the specified range @Vbn ... @Vbn+@SectorCount-1 to @Mcb.
126 * Any mappings previously in this range are deleted first.
127 *
128 * Returns: %TRUE if successful.
129 */
130 BOOLEAN
131 NTAPI
132 FsRtlAddBaseMcbEntry(IN PBASE_MCB OpaqueMcb,
133 IN LONGLONG Vbn,
134 IN LONGLONG Lbn,
135 IN LONGLONG SectorCount)
136 {
137 PBASE_MCB_INTERNAL Mcb = (PBASE_MCB_INTERNAL)OpaqueMcb;
138 LARGE_MCB_MAPPING_ENTRY Node, NeedleRun;
139 PLARGE_MCB_MAPPING_ENTRY LowerRun, HigherRun;
140 BOOLEAN NewElement;
141
142 if (Vbn < 0) return FALSE;
143 if (SectorCount <= 0) return FALSE;
144
145 /* clean any possible previous entries in our range */
146 FsRtlRemoveBaseMcbEntry(OpaqueMcb, Vbn, SectorCount);
147
148 // We need to map [Vbn, Vbn+SectorCount) to [Lbn, Lbn+SectorCount),
149 // taking in account the fact that we need to merge these runs if
150 // they are adjacent or overlap, but fail if new run fully fits into another run
151
152 /* initially we think we will be inserted as a separate run */
153 Node.RunStartVbn.QuadPart = Vbn;
154 Node.RunEndVbn.QuadPart = Vbn + SectorCount;
155 Node.StartingLbn.QuadPart = Lbn;
156
157 /* optionally merge with lower run */
158 NeedleRun.RunStartVbn.QuadPart = Node.RunStartVbn.QuadPart - 1;
159 NeedleRun.RunEndVbn.QuadPart = NeedleRun.RunStartVbn.QuadPart + 1;
160 NeedleRun.StartingLbn.QuadPart = ~0ULL;
161 Mcb->Mapping->Table.CompareRoutine = McbMappingIntersectCompare;
162 if ((LowerRun = RtlLookupElementGenericTable(&Mcb->Mapping->Table, &NeedleRun)))
163 {
164 ASSERT(LowerRun->RunEndVbn.QuadPart == Node.RunStartVbn.QuadPart);
165 Node.RunStartVbn.QuadPart = LowerRun->RunStartVbn.QuadPart;
166 Node.StartingLbn.QuadPart = LowerRun->StartingLbn.QuadPart;
167 Mcb->Mapping->Table.CompareRoutine = McbMappingCompare;
168 RtlDeleteElementGenericTable(&Mcb->Mapping->Table, LowerRun);
169 DPRINT("Intersecting lower run found (%I64d,%I64d) Lbn: %I64d\n", LowerRun->RunStartVbn.QuadPart, LowerRun->RunEndVbn.QuadPart, LowerRun->StartingLbn.QuadPart);
170 }
171
172 /* optionally merge with higher run */
173 NeedleRun.RunStartVbn.QuadPart = Node.RunEndVbn.QuadPart;
174 NeedleRun.RunEndVbn.QuadPart = NeedleRun.RunStartVbn.QuadPart + 1;
175 Mcb->Mapping->Table.CompareRoutine = McbMappingIntersectCompare;
176 if ((HigherRun = RtlLookupElementGenericTable(&Mcb->Mapping->Table, &NeedleRun)))
177 {
178 ASSERT(HigherRun->RunStartVbn.QuadPart == Node.RunEndVbn.QuadPart);
179 Node.RunEndVbn.QuadPart = HigherRun->RunEndVbn.QuadPart;
180 Mcb->Mapping->Table.CompareRoutine = McbMappingCompare;
181 RtlDeleteElementGenericTable(&Mcb->Mapping->Table, HigherRun);
182 DPRINT("Intersecting higher run found (%I64d,%I64d) Lbn: %I64d\n", HigherRun->RunStartVbn.QuadPart, HigherRun->RunEndVbn.QuadPart, HigherRun->StartingLbn.QuadPart);
183 }
184 Mcb->Mapping->Table.CompareRoutine = McbMappingCompare;
185
186 /* finally insert the resulting run */
187 RtlInsertElementGenericTable(&Mcb->Mapping->Table, &Node, sizeof(Node), &NewElement);
188 ASSERT(NewElement);
189 Node.RunStartVbn.QuadPart = Vbn;
190 Node.RunEndVbn.QuadPart = Vbn + SectorCount;
191 Node.StartingLbn.QuadPart = Lbn;
192
193 // NB: Two consecutive runs can only be merged, if actual LBNs also match!
194
195 /* 1.
196 Existing->RunStartVbn
197 |
198 |///////|
199 |/////////////|
200 |
201 Node->RunStartVbn
202
203 2.
204 Existing->RunStartVbn
205 |
206 |///////|
207 |//////|
208 |
209 Node->RunStartVbn
210
211 3.
212 Existing->RunStartVbn
213 |
214 |///////|
215 |///|
216 |
217 Node->RunStartVbn
218
219 4.
220 Existing->RunStartVbn
221 |
222 |///////|
223 |///////////////|
224 |
225 Node->RunStartVbn
226
227
228 Situation with holes:
229 1. Holes at both ends
230 2. Hole at the right, new run merged with the previous run
231 3. Hole at the right, new run is not merged with the previous run
232 4. Hole at the left, new run merged with the next run
233 5. Hole at the left, new run is not merged with the next run
234 6. No holes, exact fit to merge with both previous and next runs
235 7. No holes, merges only with the next run
236 8. No holes, merges only with the previous run
237 9. No holes, does not merge with next or prev runs
238
239
240 Overwriting existing mapping is not possible and results in FALSE being returned
241 */
242 return TRUE;
243 }
244
245 /*
246 * @implemented
247 */
248 BOOLEAN
249 NTAPI
250 FsRtlAddLargeMcbEntry(IN PLARGE_MCB Mcb,
251 IN LONGLONG Vbn,
252 IN LONGLONG Lbn,
253 IN LONGLONG SectorCount)
254 {
255 BOOLEAN Result;
256
257 DPRINT("Mcb %p Vbn %I64d Lbn %I64d SectorCount %I64d\n", Mcb, Vbn, Lbn, SectorCount);
258
259 KeAcquireGuardedMutex(Mcb->GuardedMutex);
260 Result = FsRtlAddBaseMcbEntry(&(Mcb->BaseMcb),
261 Vbn,
262 Lbn,
263 SectorCount);
264 KeReleaseGuardedMutex(Mcb->GuardedMutex);
265
266 DPRINT("Done %u\n", Result);
267
268 return Result;
269 }
270
271 /*
272 * @implemented
273 * @Mcb: #PLARGE_MCB initialized by FsRtlInitializeLargeMcb().
274 * %NULL value is forbidden.
275 * @RunIndex: Requested range index to retrieve.
276 * @Vbn: Returns the starting virtual block number of the wished range.
277 * %NULL pointer is forbidden.
278 * @Lbn: Returns the starting logical block number of the wished range (or -1 if it is a hole).
279 * %NULL pointer is forbidden.
280 * @SectorCount: Returns the length of the wished range.
281 * %NULL pointer is forbidden.
282 * Value less or equal to %0 is forbidden; FIXME: Is the reject of %0 W32 compliant?
283 *
284 * Retrieves the parameters of the specified run with index @RunIndex.
285 *
286 * Mapping %0 always starts at virtual block %0, either as 'hole' or as 'real' mapping.
287 * libcaptive does not store 'hole' information to its #GTree.
288 * Last run is always a 'real' run. 'hole' runs appear as mapping to constant @Lbn value %-1.
289 *
290 * Returns: %TRUE if successful.
291 */
292 BOOLEAN
293 NTAPI
294 FsRtlGetNextBaseMcbEntry(IN PBASE_MCB OpaqueMcb,
295 IN ULONG RunIndex,
296 OUT PLONGLONG Vbn,
297 OUT PLONGLONG Lbn,
298 OUT PLONGLONG SectorCount)
299 {
300 PBASE_MCB_INTERNAL Mcb = (PBASE_MCB_INTERNAL)OpaqueMcb;
301 ULONG RunIndexRemaining;
302 PLARGE_MCB_MAPPING_ENTRY Run, RunFound = NULL, RunFoundLower = NULL, RunFoundHigher = NULL;
303 BOOLEAN First = TRUE;
304
305 RunIndexRemaining = RunIndex;
306
307 /* Traverse the tree */
308 for (Run = (PLARGE_MCB_MAPPING_ENTRY)RtlEnumerateGenericTable(&Mcb->Mapping->Table, TRUE);
309 Run;
310 Run = (PLARGE_MCB_MAPPING_ENTRY)RtlEnumerateGenericTable(&Mcb->Mapping->Table, FALSE))
311 {
312 if (First)
313 {
314 /* Take care when we must emulate missing 'hole' run at start of our run list. */
315 if (Run->RunStartVbn.QuadPart > 0)
316 {
317 if (RunIndexRemaining == 0)
318 {
319 RunFoundLower = &StaticRunBelow0;
320 RunFoundHigher = Run;
321
322 /* stop the traversal */
323 break;
324 }
325 /* If someone wants RunIndex #1 we are already on it. */
326 RunIndexRemaining--;
327 }
328 First = FALSE;
329 }
330
331 if (RunIndexRemaining > 0)
332 {
333 /* FIXME: performance: non-linear direct seek to the requested RunIndex */
334 RunIndexRemaining--;
335 if (RunIndexRemaining == 0)
336 RunFoundLower = Run;
337 else
338 RunIndexRemaining--;
339
340 /* continue the traversal */
341 continue;
342 }
343
344 if (RunFoundLower)
345 RunFoundHigher = Run;
346 else
347 RunFound = Run;
348
349 /* stop the traversal */
350 break;
351 }
352
353 if (RunFound) DPRINT("RunFound(%lu %lu %lu)\n", RunFound->RunStartVbn.LowPart, RunFound->RunEndVbn.LowPart, RunFound->StartingLbn.LowPart);
354 if (RunFoundLower) DPRINT("RunFoundLower(%lu %lu %lu)\n", RunFoundLower->RunStartVbn.LowPart, RunFoundLower->RunEndVbn.LowPart, RunFoundLower->StartingLbn.LowPart);
355 if (RunFoundHigher) DPRINT("RunFoundHigher(%lu %lu %lu)\n", RunFoundHigher->RunStartVbn.LowPart, RunFoundHigher->RunEndVbn.LowPart, RunFoundHigher->StartingLbn.LowPart);
356
357 if (RunFound)
358 {
359 ASSERT(RunFoundLower == NULL);
360 ASSERT(RunFoundHigher == NULL);
361
362 if (Vbn)
363 *Vbn = RunFound->RunStartVbn.QuadPart;
364 if (Lbn)
365 *Lbn = RunFound->StartingLbn.QuadPart;
366 if (SectorCount)
367 *SectorCount = RunFound->RunEndVbn.QuadPart - RunFound->RunStartVbn.QuadPart;
368
369 return TRUE;
370 }
371
372 if (RunFoundLower && RunFoundHigher)
373 {
374 //ASSERT(RunFoundHigher != NULL);
375
376 if (Vbn)
377 *Vbn = RunFoundLower->RunEndVbn.QuadPart;
378 if (Lbn)
379 *Lbn = -1;
380 if (SectorCount)
381 *SectorCount = RunFoundHigher->RunStartVbn.QuadPart - RunFoundLower->RunEndVbn.QuadPart;
382
383 return TRUE;
384 }
385
386 ASSERT(RunFoundHigher == NULL);
387 return FALSE;
388 }
389
390 /*
391 * @implemented
392 */
393 BOOLEAN
394 NTAPI
395 FsRtlGetNextLargeMcbEntry(IN PLARGE_MCB Mcb,
396 IN ULONG RunIndex,
397 OUT PLONGLONG Vbn,
398 OUT PLONGLONG Lbn,
399 OUT PLONGLONG SectorCount)
400 {
401 BOOLEAN Result;
402
403 DPRINT("FsRtlGetNextLargeMcbEntry Mcb %p RunIndex %lu\n", Mcb, RunIndex);
404
405 KeAcquireGuardedMutex(Mcb->GuardedMutex);
406 Result = FsRtlGetNextBaseMcbEntry(&(Mcb->BaseMcb),
407 RunIndex,
408 Vbn,
409 Lbn,
410 SectorCount);
411 KeReleaseGuardedMutex(Mcb->GuardedMutex);
412
413 DPRINT("Done %u\n", Result);
414
415 return Result;
416 }
417
418 /*
419 * @implemented
420 */
421 VOID
422 NTAPI
423 FsRtlInitializeBaseMcb(IN PBASE_MCB OpaqueMcb,
424 IN POOL_TYPE PoolType)
425 {
426 PBASE_MCB_INTERNAL Mcb = (PBASE_MCB_INTERNAL)OpaqueMcb;
427
428 if (PoolType == PagedPool)
429 {
430 Mcb->Mapping = ExAllocateFromPagedLookasideList(&FsRtlFirstMappingLookasideList);
431 }
432 else
433 {
434 Mcb->Mapping = ExAllocatePoolWithTag(PoolType | POOL_RAISE_IF_ALLOCATION_FAILURE,
435 sizeof(LARGE_MCB_MAPPING),
436 'FSBC');
437 }
438
439 Mcb->PoolType = PoolType;
440 Mcb->PairCount = 0;
441 Mcb->MaximumPairCount = MAXIMUM_PAIR_COUNT;
442 RtlInitializeGenericTable(&Mcb->Mapping->Table,
443 McbMappingCompare,
444 McbMappingAllocate,
445 McbMappingFree,
446 Mcb);
447 }
448
449 /*
450 * @implemented
451 */
452 VOID
453 NTAPI
454 FsRtlInitializeLargeMcb(IN PLARGE_MCB Mcb,
455 IN POOL_TYPE PoolType)
456 {
457 Mcb->GuardedMutex = ExAllocateFromNPagedLookasideList(&FsRtlFastMutexLookasideList);
458
459 KeInitializeGuardedMutex(Mcb->GuardedMutex);
460
461 _SEH2_TRY
462 {
463 FsRtlInitializeBaseMcb(&(Mcb->BaseMcb), PoolType);
464 }
465 _SEH2_EXCEPT(EXCEPTION_EXECUTE_HANDLER)
466 {
467 ExFreeToNPagedLookasideList(&FsRtlFastMutexLookasideList,
468 Mcb->GuardedMutex);
469 Mcb->GuardedMutex = NULL;
470 }
471 _SEH2_END;
472 }
473
474 /*
475 * @implemented
476 */
477 INIT_FUNCTION
478 VOID
479 NTAPI
480 FsRtlInitializeLargeMcbs(VOID)
481 {
482 /* Initialize the list for the MCB */
483 ExInitializePagedLookasideList(&FsRtlFirstMappingLookasideList,
484 NULL,
485 NULL,
486 POOL_RAISE_IF_ALLOCATION_FAILURE,
487 sizeof(LARGE_MCB_MAPPING),
488 IFS_POOL_TAG,
489 0); /* FIXME: Should be 4 */
490
491 /* Initialize the list for the guarded mutex */
492 ExInitializeNPagedLookasideList(&FsRtlFastMutexLookasideList,
493 NULL,
494 NULL,
495 POOL_RAISE_IF_ALLOCATION_FAILURE,
496 sizeof(KGUARDED_MUTEX),
497 IFS_POOL_TAG,
498 0); /* FIXME: Should be 32 */
499 }
500
501 /*
502 * @unimplemented
503 */
504 BOOLEAN
505 NTAPI
506 FsRtlLookupBaseMcbEntry(IN PBASE_MCB OpaqueMcb,
507 IN LONGLONG Vbn,
508 OUT PLONGLONG Lbn OPTIONAL,
509 OUT PLONGLONG SectorCountFromLbn OPTIONAL,
510 OUT PLONGLONG StartingLbn OPTIONAL,
511 OUT PLONGLONG SectorCountFromStartingLbn OPTIONAL,
512 OUT PULONG Index OPTIONAL)
513 {
514 PBASE_MCB_INTERNAL Mcb = (PBASE_MCB_INTERNAL)OpaqueMcb;
515
516
517 ULONG RunIndex = 0;
518 PLARGE_MCB_MAPPING_ENTRY Run, RunFound = NULL, RunFoundLower = NULL, RunFoundHigher = NULL;
519 BOOLEAN First = TRUE;
520
521 /* Traverse the tree */
522 for (Run = (PLARGE_MCB_MAPPING_ENTRY)RtlEnumerateGenericTable(&Mcb->Mapping->Table, TRUE);
523 Run;
524 Run = (PLARGE_MCB_MAPPING_ENTRY)RtlEnumerateGenericTable(&Mcb->Mapping->Table, FALSE))
525 {
526 if (First)
527 {
528 /* Take care when we must emulate missing 'hole' run at start of our run list. */
529 if (Run->RunStartVbn.QuadPart > 0)
530 {
531 RunIndex++;
532 RunFoundLower = &StaticRunBelow0;
533 }
534 First = FALSE;
535 }
536
537 if (Run->RunStartVbn.QuadPart <= Vbn && Vbn < Run->RunEndVbn.QuadPart)
538 {
539 RunFound = Run;
540 RunFoundLower = NULL;
541 /* stop the traversal; hit */
542 break;
543 }
544
545 if (Run->RunEndVbn.QuadPart <= Vbn)
546 {
547 RunFoundLower = Run;
548 if (Run->StartingLbn.QuadPart > 0)
549 {
550 RunIndex += 2;
551 }
552 /* continue the traversal; not yet crossed by the run */
553 continue;
554 }
555
556 if (Vbn < Run->RunStartVbn.QuadPart)
557 {
558 RunFoundHigher = Run;
559 RunIndex++;
560 /* stop the traversal; the run skipped us */
561 break;
562 }
563
564 ASSERT(FALSE);
565 /* stop the traversal */
566 break;
567 }
568
569 if (RunFound)
570 {
571 ASSERT(RunFoundLower == NULL);
572 ASSERT(RunFoundHigher == NULL);
573
574 if (Lbn)
575 *Lbn = RunFound->StartingLbn.QuadPart + (Vbn - RunFound->RunStartVbn.QuadPart);
576
577 if (SectorCountFromLbn) /* FIXME: 'after' means including current 'Lbn' or without it? */
578 *SectorCountFromLbn = RunFound->RunEndVbn.QuadPart - Vbn;
579 if (StartingLbn)
580 *StartingLbn = RunFound->StartingLbn.QuadPart;
581 if (SectorCountFromStartingLbn)
582 *SectorCountFromStartingLbn = RunFound->RunEndVbn.QuadPart - RunFound->RunStartVbn.QuadPart;
583 if (Index)
584 *Index = RunIndex;
585
586 return TRUE;
587 }
588
589 if (RunFoundHigher)
590 {
591 /* search for hole */
592 ASSERT(RunFoundLower != NULL);
593
594 if (Lbn)
595 *Lbn = ~0ull;
596 if (SectorCountFromLbn) /* FIXME: 'after' means including current 'Lbn' or without it? */
597 *SectorCountFromLbn = RunFoundHigher->RunStartVbn.QuadPart - Vbn;
598 if (StartingLbn)
599 *StartingLbn = ~0ull;
600 if (SectorCountFromStartingLbn)
601 *SectorCountFromStartingLbn = RunFoundHigher->RunStartVbn.QuadPart - RunFoundLower->RunEndVbn.QuadPart;
602 if (Index)
603 *Index = RunIndex - 2;
604
605 return TRUE;
606 }
607
608 /* We may have some 'RunFoundLower'. */
609 return FALSE;
610 }
611
612 /*
613 * @implemented
614 */
615 BOOLEAN
616 NTAPI
617 FsRtlLookupLargeMcbEntry(IN PLARGE_MCB Mcb,
618 IN LONGLONG Vbn,
619 OUT PLONGLONG Lbn OPTIONAL,
620 OUT PLONGLONG SectorCountFromLbn OPTIONAL,
621 OUT PLONGLONG StartingLbn OPTIONAL,
622 OUT PLONGLONG SectorCountFromStartingLbn OPTIONAL,
623 OUT PULONG Index OPTIONAL)
624 {
625 BOOLEAN Result;
626
627 DPRINT("FsRtlLookupLargeMcbEntry Mcb %p Vbn %I64d\n", Mcb, Vbn);
628
629 KeAcquireGuardedMutex(Mcb->GuardedMutex);
630 Result = FsRtlLookupBaseMcbEntry(&(Mcb->BaseMcb),
631 Vbn,
632 Lbn,
633 SectorCountFromLbn,
634 StartingLbn,
635 SectorCountFromStartingLbn,
636 Index);
637 KeReleaseGuardedMutex(Mcb->GuardedMutex);
638
639 DPRINT("Done %u\n", Result);
640
641 return Result;
642 }
643
644 static BOOLEAN
645 NTAPI
646 FsRtlLookupLastLargeMcbEntryAndIndex_internal(IN PBASE_MCB_INTERNAL Mcb,
647 OUT PLONGLONG Vbn,
648 OUT PLONGLONG Lbn,
649 OUT PULONG Index OPTIONAL)
650 {
651 ULONG RunIndex = 0;
652 PLARGE_MCB_MAPPING_ENTRY Run, RunFound = NULL;
653 LONGLONG LastVbn = 0;
654
655 for (Run = (PLARGE_MCB_MAPPING_ENTRY)RtlEnumerateGenericTable(&Mcb->Mapping->Table, TRUE);
656 Run;
657 Run = (PLARGE_MCB_MAPPING_ENTRY)RtlEnumerateGenericTable(&Mcb->Mapping->Table, FALSE))
658 {
659 /* Take care when we must emulate missing 'hole' runs. */
660 if (Run->RunStartVbn.QuadPart > LastVbn)
661 {
662 RunIndex++;
663 }
664 LastVbn = Run->RunEndVbn.QuadPart;
665 RunIndex++;
666 RunFound = Run;
667 }
668
669 if (!RunFound)
670 {
671 return FALSE;
672 }
673
674 if (Vbn)
675 {
676 *Vbn = RunFound->RunEndVbn.QuadPart - 1;
677 }
678 if (Lbn)
679 {
680 if (1)
681 {
682 *Lbn = RunFound->StartingLbn.QuadPart + (RunFound->RunEndVbn.QuadPart - RunFound->RunStartVbn.QuadPart) - 1;
683 }
684 else
685 {
686 *Lbn = ~0ULL;
687 }
688 }
689 if (Index)
690 {
691 *Index = RunIndex - 1;
692 }
693
694 return TRUE;
695 }
696
697
698 /*
699 * @implemented
700 */
701 BOOLEAN
702 NTAPI
703 FsRtlLookupLastBaseMcbEntryAndIndex(IN PBASE_MCB OpaqueMcb,
704 IN OUT PLONGLONG LargeVbn,
705 IN OUT PLONGLONG LargeLbn,
706 IN OUT PULONG Index)
707 {
708 PBASE_MCB_INTERNAL Mcb = (PBASE_MCB_INTERNAL)OpaqueMcb;
709
710 return FsRtlLookupLastLargeMcbEntryAndIndex_internal(Mcb, LargeVbn, LargeLbn, Index);
711 }
712
713 /*
714 * @implemented
715 */
716 BOOLEAN
717 NTAPI
718 FsRtlLookupLastLargeMcbEntryAndIndex(IN PLARGE_MCB OpaqueMcb,
719 OUT PLONGLONG LargeVbn,
720 OUT PLONGLONG LargeLbn,
721 OUT PULONG Index)
722 {
723 BOOLEAN Result;
724
725 DPRINT("FsRtlLookupLastLargeMcbEntryAndIndex %p\n", OpaqueMcb);
726
727 KeAcquireGuardedMutex(OpaqueMcb->GuardedMutex);
728 Result = FsRtlLookupLastBaseMcbEntryAndIndex(&(OpaqueMcb->BaseMcb),
729 LargeVbn,
730 LargeLbn,
731 Index);
732 KeReleaseGuardedMutex(OpaqueMcb->GuardedMutex);
733
734 DPRINT("Done %u\n", Result);
735
736 return Result;
737 }
738
739 /*
740 * @unimplemented
741 */
742 BOOLEAN
743 NTAPI
744 FsRtlLookupLastBaseMcbEntry(IN PBASE_MCB OpaqueMcb,
745 OUT PLONGLONG Vbn,
746 OUT PLONGLONG Lbn)
747 {
748 PBASE_MCB_INTERNAL Mcb = (PBASE_MCB_INTERNAL)OpaqueMcb;
749
750 return FsRtlLookupLastLargeMcbEntryAndIndex_internal(Mcb, Vbn, Lbn, NULL); /* Index */
751 }
752
753 /*
754 * @implemented
755 */
756 BOOLEAN
757 NTAPI
758 FsRtlLookupLastLargeMcbEntry(IN PLARGE_MCB Mcb,
759 OUT PLONGLONG Vbn,
760 OUT PLONGLONG Lbn)
761 {
762 BOOLEAN Result;
763
764 DPRINT("FsRtlLookupLastLargeMcbEntry Mcb %p\n", Mcb);
765
766 KeAcquireGuardedMutex(Mcb->GuardedMutex);
767 Result = FsRtlLookupLastBaseMcbEntry(&(Mcb->BaseMcb),
768 Vbn,
769 Lbn);
770 KeReleaseGuardedMutex(Mcb->GuardedMutex);
771
772 DPRINT("Done %u\n", Result);
773
774 return Result;
775 }
776
777 /*
778 * @implemented
779 */
780 ULONG
781 NTAPI
782 FsRtlNumberOfRunsInBaseMcb(IN PBASE_MCB OpaqueMcb)
783 {
784 PBASE_MCB_INTERNAL Mcb = (PBASE_MCB_INTERNAL)OpaqueMcb;
785 LONGLONG LbnAtVbn0 = -1;
786 ULONG Nodes = RtlNumberGenericTableElements(&Mcb->Mapping->Table);
787
788 if (Nodes == 0) return 0;
789
790 FsRtlLookupBaseMcbEntry(OpaqueMcb,
791 0, /* Vbn */
792 &LbnAtVbn0, /* Lbn */
793 NULL, NULL, NULL, NULL); /* 4 output arguments - not interested in them */
794
795
796 /* Return the count */
797 //return Mcb->PairCount;
798 /* Return the number of 'real' and 'hole' runs.
799 * If we do not have sector 0 as 'real' emulate a 'hole' there.
800 */
801 return Nodes * 2 - (LbnAtVbn0 != -1 ? 1 : 0); /* include holes as runs */
802 }
803
804 /*
805 * @implemented
806 */
807 ULONG
808 NTAPI
809 FsRtlNumberOfRunsInLargeMcb(IN PLARGE_MCB Mcb)
810 {
811 ULONG NumberOfRuns;
812
813 DPRINT("FsRtlNumberOfRunsInLargeMcb Mcb %p\n", Mcb);
814
815 /* Read the number of runs while holding the MCB lock */
816 KeAcquireGuardedMutex(Mcb->GuardedMutex);
817 NumberOfRuns = FsRtlNumberOfRunsInBaseMcb(&(Mcb->BaseMcb));
818 KeReleaseGuardedMutex(Mcb->GuardedMutex);
819
820 DPRINT("Done %lu\n", NumberOfRuns);
821
822 /* Return the count */
823 return NumberOfRuns;
824 }
825
826 /*
827 * @implemented
828 * @Mcb: #PLARGE_MCB initialized by FsRtlInitializeLargeMcb().
829 * %NULL value is forbidden.
830 * @Vbn: Starting virtual block number to specify the range to delete.
831 * @SectorCount: Length of the range to delete.
832 * Value less or equal to %0 is forbidden; FIXME: Is the reject of %0 W32 compliant?
833 *
834 * Deletes any possible @Mcb mappings in the given range @Vbn ... @Vbn+@SectorCount-1.
835 * This call has no problems if no mappings exist there yet.
836 */
837 BOOLEAN
838 NTAPI
839 FsRtlRemoveBaseMcbEntry(IN PBASE_MCB OpaqueMcb,
840 IN LONGLONG Vbn,
841 IN LONGLONG SectorCount)
842 {
843 PBASE_MCB_INTERNAL Mcb = (PBASE_MCB_INTERNAL)OpaqueMcb;
844 LARGE_MCB_MAPPING_ENTRY NeedleRun;
845 PLARGE_MCB_MAPPING_ENTRY HaystackRun;
846
847 if (Vbn < 0 || SectorCount <= 0) return FALSE;
848 if (Vbn + SectorCount <= Vbn) return FALSE;
849
850 NeedleRun.RunStartVbn.QuadPart = Vbn;
851 NeedleRun.RunEndVbn.QuadPart = Vbn + SectorCount;
852 NeedleRun.StartingLbn.QuadPart = ~0ULL;
853
854 /* adjust/destroy all intersecting ranges */
855 Mcb->Mapping->Table.CompareRoutine = McbMappingIntersectCompare;
856 while ((HaystackRun = RtlLookupElementGenericTable(&Mcb->Mapping->Table, &NeedleRun)))
857 {
858 if (HaystackRun->RunStartVbn.QuadPart < NeedleRun.RunStartVbn.QuadPart)
859 {
860 ASSERT(HaystackRun->RunEndVbn.QuadPart > NeedleRun.RunStartVbn.QuadPart);
861 HaystackRun->RunEndVbn.QuadPart = NeedleRun.RunStartVbn.QuadPart;
862 }
863 else if (HaystackRun->RunEndVbn.QuadPart > NeedleRun.RunEndVbn.QuadPart)
864 {
865 ASSERT(HaystackRun->RunStartVbn.QuadPart < NeedleRun.RunEndVbn.QuadPart);
866 HaystackRun->RunStartVbn.QuadPart = NeedleRun.RunEndVbn.QuadPart;
867 }
868 else
869 {
870 //ASSERT(NeedleRun.RunStartVbn.QuadPart >= HaystackRun->RunStartVbn.QuadPart);
871 //ASSERT(NeedleRun.RunEndVbn.QuadPart <= HaystackRun->RunEndVbn.QuadPart);
872 Mcb->Mapping->Table.CompareRoutine = McbMappingCompare;
873 RtlDeleteElementGenericTable(&Mcb->Mapping->Table, HaystackRun);
874 Mcb->Mapping->Table.CompareRoutine = McbMappingIntersectCompare;
875 }
876 }
877 Mcb->Mapping->Table.CompareRoutine = McbMappingCompare;
878
879 return TRUE;
880 }
881
882 /*
883 * @implemented
884 */
885 VOID
886 NTAPI
887 FsRtlRemoveLargeMcbEntry(IN PLARGE_MCB Mcb,
888 IN LONGLONG Vbn,
889 IN LONGLONG SectorCount)
890 {
891 DPRINT("FsRtlRemoveLargeMcbEntry Mcb %p, Vbn %I64d, SectorCount %I64d\n", Mcb, Vbn, SectorCount);
892
893 KeAcquireGuardedMutex(Mcb->GuardedMutex);
894 FsRtlRemoveBaseMcbEntry(&(Mcb->BaseMcb), Vbn, SectorCount);
895 KeReleaseGuardedMutex(Mcb->GuardedMutex);
896
897 DPRINT("Done\n");
898 }
899
900 /*
901 * @implemented
902 */
903 VOID
904 NTAPI
905 FsRtlResetBaseMcb(IN PBASE_MCB OpaqueMcb)
906 {
907 PBASE_MCB_INTERNAL Mcb = (PBASE_MCB_INTERNAL)OpaqueMcb;
908 PLARGE_MCB_MAPPING_ENTRY Element;
909
910 while (RtlNumberGenericTableElements(&Mcb->Mapping->Table) &&
911 (Element = (PLARGE_MCB_MAPPING_ENTRY)RtlGetElementGenericTable(&Mcb->Mapping->Table, 0)))
912 {
913 RtlDeleteElementGenericTable(&Mcb->Mapping->Table, Element);
914 }
915
916 Mcb->PairCount = 0;
917 Mcb->MaximumPairCount = 0;
918 }
919
920 /*
921 * @implemented
922 */
923 VOID
924 NTAPI
925 FsRtlResetLargeMcb(IN PLARGE_MCB Mcb,
926 IN BOOLEAN SelfSynchronized)
927 {
928 if (!SelfSynchronized)
929 KeAcquireGuardedMutex(Mcb->GuardedMutex);
930
931 FsRtlResetBaseMcb(&Mcb->BaseMcb);
932
933 if (!SelfSynchronized)
934 KeReleaseGuardedMutex(Mcb->GuardedMutex);
935 }
936
937 /*
938 * @unimplemented
939 */
940 BOOLEAN
941 NTAPI
942 FsRtlSplitBaseMcb(IN PBASE_MCB OpaqueMcb,
943 IN LONGLONG Vbn,
944 IN LONGLONG Amount)
945 {
946 PBASE_MCB_INTERNAL Mcb = (PBASE_MCB_INTERNAL)OpaqueMcb;
947 PLARGE_MCB_MAPPING_ENTRY Run, InsertLowerRun = NULL, ExistingRun = NULL;
948 BOOLEAN NewElement;
949
950 /* Traverse the tree */
951 for (Run = (PLARGE_MCB_MAPPING_ENTRY)RtlEnumerateGenericTable(&Mcb->Mapping->Table, TRUE);
952 Run;
953 Run = (PLARGE_MCB_MAPPING_ENTRY)RtlEnumerateGenericTable(&Mcb->Mapping->Table, FALSE))
954 {
955 /* unaffected run? */
956 /* FIXME: performance: effective skip of all 'lower' runs without traversing them */
957 if (Vbn >= Run->RunEndVbn.QuadPart) { DPRINT("Skipping it\n"); continue; }
958
959 /* crossing run to be split?
960 * 'lower_run' is created on the original place; just shortened.
961 * current 'run' is shifted up later
962 */
963 if (Vbn < Run->RunEndVbn.QuadPart)
964 {
965 /* FIXME: shift 'run->Lbn_start' ? */
966 Run->RunStartVbn.QuadPart = Vbn;
967
968 InsertLowerRun = NULL;
969 }
970
971 /* Shift the current 'run'.
972 * Ordering is not changed in Generic Tree so I hope I do not need to reinsert it.
973 */
974 Run->RunStartVbn.QuadPart += Amount;
975 ASSERT(Run->RunEndVbn.QuadPart + Amount > Run->RunEndVbn.QuadPart); /* overflow? */
976 Run->RunEndVbn.QuadPart += Amount;
977 /* FIXME: shift 'run->Lbn_start' ? */
978
979 /* continue the traversal */
980 }
981
982 if (InsertLowerRun)
983 ExistingRun = RtlInsertElementGenericTable(&Mcb->Mapping->Table, InsertLowerRun, sizeof(*InsertLowerRun), &NewElement);
984
985 ASSERT(ExistingRun == NULL);
986
987 return TRUE;
988 }
989
990 /*
991 * @implemented
992 */
993 BOOLEAN
994 NTAPI
995 FsRtlSplitLargeMcb(IN PLARGE_MCB Mcb,
996 IN LONGLONG Vbn,
997 IN LONGLONG Amount)
998 {
999 BOOLEAN Result;
1000
1001 DPRINT("FsRtlSplitLargeMcb %p, Vbn %I64d, Amount %I64d\n", Mcb, Vbn, Amount);
1002
1003 KeAcquireGuardedMutex(Mcb->GuardedMutex);
1004 Result = FsRtlSplitBaseMcb(&(Mcb->BaseMcb),
1005 Vbn,
1006 Amount);
1007 KeReleaseGuardedMutex(Mcb->GuardedMutex);
1008
1009 DPRINT("Done %u\n", Result);
1010
1011 return Result;
1012 }
1013
1014 /*
1015 * @unimplemented
1016 */
1017 VOID
1018 NTAPI
1019 FsRtlTruncateBaseMcb(IN PBASE_MCB OpaqueMcb,
1020 IN LONGLONG Vbn)
1021 {
1022 DPRINT("Mcb=%p, Vbn=%I64d\n", OpaqueMcb, Vbn);
1023 FsRtlRemoveBaseMcbEntry(OpaqueMcb, Vbn, MAXLONG - Vbn + 1);
1024 }
1025
1026 /*
1027 * @implemented
1028 */
1029 VOID
1030 NTAPI
1031 FsRtlTruncateLargeMcb(IN PLARGE_MCB Mcb,
1032 IN LONGLONG Vbn)
1033 {
1034 DPRINT("FsRtlTruncateLargeMcb %p Vbn %I64d\n", Mcb, Vbn);
1035 KeAcquireGuardedMutex(Mcb->GuardedMutex);
1036 FsRtlTruncateBaseMcb(&(Mcb->BaseMcb), Vbn);
1037 KeReleaseGuardedMutex(Mcb->GuardedMutex);
1038 DPRINT("Done\n");
1039 }
1040
1041 /*
1042 * @implemented
1043 */
1044 VOID
1045 NTAPI
1046 FsRtlUninitializeBaseMcb(IN PBASE_MCB Mcb)
1047 {
1048 FsRtlResetBaseMcb(Mcb);
1049
1050 if ((Mcb->PoolType == PagedPool)/* && (Mcb->MaximumPairCount == MAXIMUM_PAIR_COUNT)*/)
1051 {
1052 ExFreeToPagedLookasideList(&FsRtlFirstMappingLookasideList,
1053 Mcb->Mapping);
1054 }
1055 else
1056 {
1057 ExFreePoolWithTag(Mcb->Mapping, 'FSBC');
1058 }
1059 }
1060
1061 /*
1062 * @implemented
1063 */
1064 VOID
1065 NTAPI
1066 FsRtlUninitializeLargeMcb(IN PLARGE_MCB Mcb)
1067 {
1068 if (Mcb->GuardedMutex)
1069 {
1070 ExFreeToNPagedLookasideList(&FsRtlFastMutexLookasideList,
1071 Mcb->GuardedMutex);
1072 FsRtlUninitializeBaseMcb(&(Mcb->BaseMcb));
1073 }
1074 }