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