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