drivers/filesystems/cdfs_new/prefxsup.c

   1 /*++
   2
   3 Copyright (c) 1989-2000 Microsoft Corporation
   4
   5 Module Name:
   6
   7     PrefxSup.c
   8
   9 Abstract:
  10
  11     This module implements the Cdfs Prefix support routines
  12
  13
  14 --*/
  15
  16 #include "cdprocs.h"
  17
  18 //
  19 //  The Bug check file id for this module
  20 //
  21
  22 #define BugCheckFileId                   (CDFS_BUG_CHECK_PREFXSUP)
  23
  24 //
  25 //  Local support routines.
  26 //
  27
  28 PNAME_LINK
  29 CdFindNameLink (
  30     _In_ PIRP_CONTEXT IrpContext,
  31     _In_ PRTL_SPLAY_LINKS *RootNode,
  32     _In_ PUNICODE_STRING Name
  33     );
  34
  35 BOOLEAN
  36 CdInsertNameLink (
  37     _In_ PIRP_CONTEXT IrpContext,
  38     _Inout_ PRTL_SPLAY_LINKS *RootNode,
  39     _In_ PNAME_LINK NameLink
  40     );
  41
  42 #ifdef ALLOC_PRAGMA
  43 #pragma alloc_text(PAGE, CdFindNameLink)
  44 #pragma alloc_text(PAGE, CdFindPrefix)
  45 #pragma alloc_text(PAGE, CdInsertNameLink)
  46 #pragma alloc_text(PAGE, CdInsertPrefix)
  47 #pragma alloc_text(PAGE, CdRemovePrefix)
  48 #endif
  49
  50 \f
  51 VOID
  52 CdInsertPrefix (
  53     _In_ PIRP_CONTEXT IrpContext,
  54     _Inout_ PFCB Fcb,
  55     _In_ PCD_NAME Name,
  56     _In_ BOOLEAN IgnoreCase,
  57     _In_ BOOLEAN ShortNameMatch,
  58     _Inout_ PFCB ParentFcb
  59     )
  60
  61 /*++
  62
  63 Routine Description:
  64
  65     This routine inserts the names in the given Lcb into the links for the
  66     parent.
  67
  68 Arguments:
  69
  70     Fcb - This is the Fcb whose name is being inserted into the tree.
  71
  72     Name - This is the name for the component.  The IgnoreCase flag tells
  73         us which entry this belongs to.
  74
  75     IgnoreCase - Indicates if we should insert the case-insensitive name.
  76
  77     ShortNameMatch - Indicates if this is the short name.
  78
  79     ParentFcb - This is the ParentFcb.  The prefix tree is attached to this.
  80
  81 Return Value:
  82
  83     None.
  84
  85 --*/
  86
  87 {
  88     ULONG PrefixFlags;
  89     PNAME_LINK NameLink;
  90     PPREFIX_ENTRY PrefixEntry;
  91     PRTL_SPLAY_LINKS *TreeRoot;
  92
  93     PWCHAR NameBuffer;
  94
  95     PAGED_CODE();
  96
  97     //
  98     //  Check if we need to allocate a prefix entry for the short name.
  99     //  If we can't allocate one then fail quietly.  We don't have to
 100     //  insert the name.
 101     //
 102
 103     PrefixEntry = &Fcb->FileNamePrefix;
 104
 105     if (ShortNameMatch) {
 106
 107         if (Fcb->ShortNamePrefix == NULL) {
 108
 109             Fcb->ShortNamePrefix = ExAllocatePoolWithTag( CdPagedPool,
 110                                                           sizeof( PREFIX_ENTRY ),
 111                                                           TAG_PREFIX_ENTRY );
 112
 113             if (Fcb->ShortNamePrefix == NULL) { return; }
 114
 115             RtlZeroMemory( Fcb->ShortNamePrefix, sizeof( PREFIX_ENTRY ));
 116         }
 117
 118         PrefixEntry = Fcb->ShortNamePrefix;
 119     }
 120
 121     //
 122     //  Capture the local variables for the separate cases.
 123     //
 124
 125     if (IgnoreCase) {
 126
 127         PrefixFlags = PREFIX_FLAG_IGNORE_CASE_IN_TREE;
 128         NameLink = &PrefixEntry->IgnoreCaseName;
 129         TreeRoot = &ParentFcb->IgnoreCaseRoot;
 130
 131     } else {
 132
 133         PrefixFlags = PREFIX_FLAG_EXACT_CASE_IN_TREE;
 134         NameLink = &PrefixEntry->ExactCaseName;
 135         TreeRoot = &ParentFcb->ExactCaseRoot;
 136     }
 137
 138     //
 139     //  If neither name is in the tree then check whether we have a buffer for this
 140     //  name
 141     //
 142
 143     if (!FlagOn( PrefixEntry->PrefixFlags,
 144                  PREFIX_FLAG_EXACT_CASE_IN_TREE | PREFIX_FLAG_IGNORE_CASE_IN_TREE )) {
 145
 146         //
 147         //  Allocate a new buffer if the embedded buffer is too small.
 148         //
 149
 150         NameBuffer = PrefixEntry->FileNameBuffer;
 151
 152         if (Name->FileName.Length > BYTE_COUNT_EMBEDDED_NAME) {
 153
 154             NameBuffer = ExAllocatePoolWithTag( CdPagedPool,
 155                                                 Name->FileName.Length * 2,
 156                                                 TAG_PREFIX_NAME );
 157
 158             //
 159             //  Exit if no name buffer.
 160             //
 161
 162             if (NameBuffer == NULL) { return; }
 163         }
 164
 165         //
 166         //  Split the buffer and fill in the separate components.
 167         //
 168
 169         PrefixEntry->ExactCaseName.FileName.Buffer = NameBuffer;
 170         PrefixEntry->IgnoreCaseName.FileName.Buffer = Add2Ptr( NameBuffer,
 171                                                                Name->FileName.Length,
 172                                                                PWCHAR );
 173
 174         PrefixEntry->IgnoreCaseName.FileName.MaximumLength =
 175         PrefixEntry->IgnoreCaseName.FileName.Length =
 176         PrefixEntry->ExactCaseName.FileName.MaximumLength =
 177         PrefixEntry->ExactCaseName.FileName.Length = Name->FileName.Length;
 178     }
 179
 180     //
 181     //  Only insert the name if not already present.
 182     //
 183
 184     if (!FlagOn( PrefixEntry->PrefixFlags, PrefixFlags )) {
 185
 186         //
 187         //  Initialize the name in the prefix entry.
 188         //
 189
 190         RtlCopyMemory( NameLink->FileName.Buffer,
 191                        Name->FileName.Buffer,
 192                        Name->FileName.Length );
 193
 194         CdInsertNameLink( IrpContext,
 195                           TreeRoot,
 196                           NameLink );
 197
 198         PrefixEntry->Fcb = Fcb;
 199         SetFlag( PrefixEntry->PrefixFlags, PrefixFlags );
 200     }
 201
 202     return;
 203 }
 204
 205 \f
 206 VOID
 207 CdRemovePrefix (
 208     _In_ PIRP_CONTEXT IrpContext,
 209     _Inout_ PFCB Fcb
 210     )
 211
 212 /*++
 213
 214 Routine Description:
 215
 216     This routine is called to remove all of the previx entries of a
 217     given Fcb from its parent Fcb.
 218
 219 Arguments:
 220
 221     Fcb - Fcb whose entries are to be removed.
 222
 223 Return Value:
 224
 225     None
 226
 227 --*/
 228
 229 {
 230     PAGED_CODE();
 231
 232     UNREFERENCED_PARAMETER( IrpContext );
 233
 234     //
 235     //  Start with the short name prefix entry.
 236     //
 237
 238     if (Fcb->ShortNamePrefix != NULL) {
 239
 240         if (FlagOn( Fcb->ShortNamePrefix->PrefixFlags, PREFIX_FLAG_IGNORE_CASE_IN_TREE )) {
 241
 242             Fcb->ParentFcb->IgnoreCaseRoot = RtlDelete( &Fcb->ShortNamePrefix->IgnoreCaseName.Links );
 243         }
 244
 245         if (FlagOn( Fcb->ShortNamePrefix->PrefixFlags, PREFIX_FLAG_EXACT_CASE_IN_TREE )) {
 246
 247             Fcb->ParentFcb->ExactCaseRoot = RtlDelete( &Fcb->ShortNamePrefix->ExactCaseName.Links );
 248         }
 249
 250         ClearFlag( Fcb->ShortNamePrefix->PrefixFlags,
 251                    PREFIX_FLAG_IGNORE_CASE_IN_TREE | PREFIX_FLAG_EXACT_CASE_IN_TREE );
 252     }
 253
 254     //
 255     //  Now do the long name prefix entries.
 256     //
 257
 258     if (FlagOn( Fcb->FileNamePrefix.PrefixFlags, PREFIX_FLAG_IGNORE_CASE_IN_TREE )) {
 259
 260         Fcb->ParentFcb->IgnoreCaseRoot = RtlDelete( &Fcb->FileNamePrefix.IgnoreCaseName.Links );
 261     }
 262
 263     if (FlagOn( Fcb->FileNamePrefix.PrefixFlags, PREFIX_FLAG_EXACT_CASE_IN_TREE )) {
 264
 265         Fcb->ParentFcb->ExactCaseRoot = RtlDelete( &Fcb->FileNamePrefix.ExactCaseName.Links );
 266     }
 267
 268     ClearFlag( Fcb->FileNamePrefix.PrefixFlags,
 269                PREFIX_FLAG_IGNORE_CASE_IN_TREE | PREFIX_FLAG_EXACT_CASE_IN_TREE );
 270
 271     //
 272     //  Deallocate any buffer we may have allocated.
 273     //
 274
 275     if ((Fcb->FileNamePrefix.ExactCaseName.FileName.Buffer != (PWCHAR) &Fcb->FileNamePrefix.FileNameBuffer) &&
 276         (Fcb->FileNamePrefix.ExactCaseName.FileName.Buffer != NULL)) {
 277
 278         CdFreePool( &Fcb->FileNamePrefix.ExactCaseName.FileName.Buffer );
 279         Fcb->FileNamePrefix.ExactCaseName.FileName.Buffer = NULL;
 280     }
 281
 282     return;
 283 }
 284
 285 \f
 286
 287 _Requires_lock_held_(_Global_critical_region_)
 288 VOID
 289 CdFindPrefix (
 290     _In_ PIRP_CONTEXT IrpContext,
 291     _Inout_ PFCB *CurrentFcb,
 292     _Inout_ PUNICODE_STRING RemainingName,
 293     _In_ BOOLEAN IgnoreCase
 294     )
 295
 296 /*++
 297
 298 Routine Description:
 299
 300     This routine begins from the given CurrentFcb and walks through all of
 301     components of the name looking for the longest match in the prefix
 302     splay trees.  The search is relative to the starting Fcb so the
 303     full name may not begin with a '\'.  On return this routine will
 304     update Current Fcb with the lowest point it has travelled in the
 305     tree.  It will also hold only that resource on return and it must
 306     hold that resource.
 307
 308 Arguments:
 309
 310     CurrentFcb - Address to store the lowest Fcb we find on this search.
 311         On return we will have acquired this Fcb.  On entry this is the
 312         Fcb to examine.
 313
 314     RemainingName - Supplies a buffer to store the exact case of the name being
 315         searched for.  Initially will contain the upcase name based on the
 316         IgnoreCase flag.
 317
 318     IgnoreCase - Indicates if we are doing a case-insensitive compare.
 319
 320 Return Value:
 321
 322     None
 323
 324 --*/
 325
 326 {
 327     UNICODE_STRING LocalRemainingName;
 328
 329     UNICODE_STRING FinalName;
 330
 331     PNAME_LINK NameLink;
 332     PPREFIX_ENTRY PrefixEntry;
 333
 334     PAGED_CODE();
 335
 336     //
 337     //  Make a local copy of the input strings.
 338     //
 339
 340     LocalRemainingName = *RemainingName;
 341
 342     //
 343     //  Loop until we find the longest matching prefix.
 344     //
 345
 346     while (TRUE) {
 347
 348         //
 349         //  If there are no characters left or we are not at an IndexFcb then
 350         //  return immediately.
 351         //
 352
 353         if ((LocalRemainingName.Length == 0) ||
 354             (SafeNodeType( *CurrentFcb ) != CDFS_NTC_FCB_INDEX)) {
 355
 356             return;
 357         }
 358
 359         //
 360         //  Split off the next component from the name.
 361         //
 362
 363         CdDissectName( IrpContext,
 364                        &LocalRemainingName,
 365                        &FinalName );
 366
 367         //
 368         //  Check if this name is in the splay tree for this Scb.
 369         //
 370
 371         if (IgnoreCase) {
 372
 373             NameLink = CdFindNameLink( IrpContext,
 374                                        &(*CurrentFcb)->IgnoreCaseRoot,
 375                                        &FinalName );
 376
 377             //
 378             //  Get the prefix entry from this NameLink.  Don't access any
 379             //  fields within it until we verify we have a name link.
 380             //
 381
 382             PrefixEntry = (PPREFIX_ENTRY) CONTAINING_RECORD( NameLink,
 383                                                              PREFIX_ENTRY,
 384                                                              IgnoreCaseName );
 385
 386         } else {
 387
 388             NameLink = CdFindNameLink( IrpContext,
 389                                        &(*CurrentFcb)->ExactCaseRoot,
 390                                        &FinalName );
 391
 392             PrefixEntry = (PPREFIX_ENTRY) CONTAINING_RECORD( NameLink,
 393                                                              PREFIX_ENTRY,
 394                                                              ExactCaseName );
 395         }
 396
 397         //
 398         //  If we didn't find a match then exit.
 399         //
 400
 401         if (NameLink == NULL) { return; }
 402
 403         //
 404         //  If this is a case-insensitive match then copy the exact case of the name into
 405         //  the input buffer.
 406         //
 407
 408         if (IgnoreCase) {
 409
 410             RtlCopyMemory( FinalName.Buffer,
 411                            PrefixEntry->ExactCaseName.FileName.Buffer,
 412                            PrefixEntry->ExactCaseName.FileName.Length );
 413         }
 414
 415         //
 416         //  Update the caller's remaining name string to reflect the fact that we found
 417         //  a match.
 418         //
 419
 420         *RemainingName = LocalRemainingName;
 421
 422         //
 423         //  Move down to the next component in the tree.  Acquire without waiting.
 424         //  If this fails then lock the Fcb to reference this Fcb and then drop
 425         //  the parent and acquire the child.
 426         //
 427
 428         if (!CdAcquireFcbExclusive( IrpContext, PrefixEntry->Fcb, TRUE )) {
 429
 430             //
 431             //  If we can't wait then raise CANT_WAIT.
 432             //
 433
 434             if (!FlagOn( IrpContext->Flags, IRP_CONTEXT_FLAG_WAIT )) {
 435
 436                 CdRaiseStatus( IrpContext, STATUS_CANT_WAIT );
 437             }
 438
 439             CdLockVcb( IrpContext, IrpContext->Vcb );
 440             PrefixEntry->Fcb->FcbReference += 1;
 441             CdUnlockVcb( IrpContext, IrpContext->Vcb );
 442
 443             CdReleaseFcb( IrpContext, *CurrentFcb );
 444             CdAcquireFcbExclusive( IrpContext, PrefixEntry->Fcb, FALSE );
 445
 446             CdLockVcb( IrpContext, IrpContext->Vcb );
 447             PrefixEntry->Fcb->FcbReference -= 1;
 448             CdUnlockVcb( IrpContext, IrpContext->Vcb );
 449
 450         } else {
 451
 452             CdReleaseFcb( IrpContext, *CurrentFcb );
 453         }
 454
 455         *CurrentFcb = PrefixEntry->Fcb;
 456     }
 457 }
 458
 459 \f
 460 //
 461 //  Local support routine
 462 //
 463
 464 PNAME_LINK
 465 CdFindNameLink (
 466     _In_ PIRP_CONTEXT IrpContext,
 467     _In_ PRTL_SPLAY_LINKS *RootNode,
 468     _In_ PUNICODE_STRING Name
 469     )
 470
 471 /*++
 472
 473 Routine Description:
 474
 475     This routine searches through a splay link tree looking for a match for the
 476     input name.  If we find the corresponding name we will rebalance the
 477     tree.
 478
 479 Arguments:
 480
 481     RootNode - Supplies the parent to search.
 482
 483     Name - This is the name to search for.  Note if we are doing a case
 484         insensitive search the name would have been upcased already.
 485
 486 Return Value:
 487
 488     PNAME_LINK - The name link found or NULL if there is no match.
 489
 490 --*/
 491
 492 {
 493     FSRTL_COMPARISON_RESULT Comparison;
 494     PNAME_LINK Node;
 495     PRTL_SPLAY_LINKS Links;
 496
 497     PAGED_CODE();
 498
 499     Links = *RootNode;
 500
 501     while (Links != NULL) {
 502
 503         Node = CONTAINING_RECORD( Links, NAME_LINK, Links );
 504
 505         //
 506         //  Compare the prefix in the tree with the full name
 507         //
 508
 509         Comparison = CdFullCompareNames( IrpContext, &Node->FileName, Name );
 510
 511         //
 512         //  See if they don't match
 513         //
 514
 515         if (Comparison == GreaterThan) {
 516
 517             //
 518             //  The prefix is greater than the full name
 519             //  so we go down the left child
 520             //
 521
 522             Links = RtlLeftChild( Links );
 523
 524             //
 525             //  And continue searching down this tree
 526             //
 527
 528         } else if (Comparison == LessThan) {
 529
 530             //
 531             //  The prefix is less than the full name
 532             //  so we go down the right child
 533             //
 534
 535             Links = RtlRightChild( Links );
 536
 537             //
 538             //  And continue searching down this tree
 539             //
 540
 541         } else {
 542
 543             //
 544             //  We found it.
 545             //
 546             //  Splay the tree and save the new root.
 547             //
 548
 549             *RootNode = RtlSplay( Links );
 550
 551             return Node;
 552         }
 553     }
 554
 555     //
 556     //  We didn't find the Link.
 557     //
 558
 559     return NULL;
 560 }
 561
 562 \f
 563 //
 564 //  Local support routine
 565 //
 566
 567 BOOLEAN
 568 CdInsertNameLink (
 569     _In_ PIRP_CONTEXT IrpContext,
 570     _Inout_ PRTL_SPLAY_LINKS *RootNode,
 571     _In_ PNAME_LINK NameLink
 572     )
 573
 574 /*++
 575
 576 Routine Description:
 577
 578     This routine will insert a name in the splay tree pointed to
 579     by RootNode.
 580
 581     The name could already exist in this tree for a case-insensitive tree.
 582     In that case we simply return FALSE and do nothing.
 583
 584 Arguments:
 585
 586     RootNode - Supplies a pointer to the table.
 587
 588     NameLink - Contains the new link to enter.
 589
 590 Return Value:
 591
 592     BOOLEAN - TRUE if the name is inserted, FALSE otherwise.
 593
 594 --*/
 595
 596 {
 597     FSRTL_COMPARISON_RESULT Comparison;
 598     PNAME_LINK Node;
 599
 600     PAGED_CODE();
 601
 602     RtlInitializeSplayLinks( &NameLink->Links );
 603
 604     //
 605     //  If we are the first entry in the tree, just become the root.
 606     //
 607
 608     if (*RootNode == NULL) {
 609
 610         *RootNode = &NameLink->Links;
 611
 612         return TRUE;
 613     }
 614
 615     Node = CONTAINING_RECORD( *RootNode, NAME_LINK, Links );
 616
 617     while (TRUE) {
 618
 619         //
 620         //  Compare the prefix in the tree with the prefix we want
 621         //  to insert.
 622         //
 623
 624         Comparison = CdFullCompareNames( IrpContext, &Node->FileName, &NameLink->FileName );
 625
 626         //
 627         //  If we found the entry, return immediately.
 628         //
 629
 630         if (Comparison == EqualTo) { return FALSE; }
 631
 632         //
 633         //  If the tree prefix is greater than the new prefix then
 634         //  we go down the left subtree
 635         //
 636
 637         if (Comparison == GreaterThan) {
 638
 639             //
 640             //  We want to go down the left subtree, first check to see
 641             //  if we have a left subtree
 642             //
 643
 644             if (RtlLeftChild( &Node->Links ) == NULL) {
 645
 646                 //
 647                 //  there isn't a left child so we insert ourselves as the
 648                 //  new left child
 649                 //
 650
 651                 RtlInsertAsLeftChild( &Node->Links, &NameLink->Links );
 652
 653                 //
 654                 //  and exit the while loop
 655                 //
 656
 657                 break;
 658
 659             } else {
 660
 661                 //
 662                 //  there is a left child so simply go down that path, and
 663                 //  go back to the top of the loop
 664                 //
 665
 666                 Node = CONTAINING_RECORD( RtlLeftChild( &Node->Links ),
 667                                           NAME_LINK,
 668                                           Links );
 669             }
 670
 671         } else {
 672
 673             //
 674             //  The tree prefix is either less than or a proper prefix
 675             //  of the new string.  We treat both cases as less than when
 676             //  we do insert.  So we want to go down the right subtree,
 677             //  first check to see if we have a right subtree
 678             //
 679
 680             if (RtlRightChild( &Node->Links ) == NULL) {
 681
 682                 //
 683                 //  These isn't a right child so we insert ourselves as the
 684                 //  new right child
 685                 //
 686
 687                 RtlInsertAsRightChild( &Node->Links, &NameLink->Links );
 688
 689                 //
 690                 //  and exit the while loop
 691                 //
 692
 693                 break;
 694
 695             } else {
 696
 697                 //
 698                 //  there is a right child so simply go down that path, and
 699                 //  go back to the top of the loop
 700                 //
 701
 702                 Node = CONTAINING_RECORD( RtlRightChild( &Node->Links ),
 703                                           NAME_LINK,
 704                                           Links );
 705             }
 706         }
 707     }
 708
 709     return TRUE;
 710 }
 711
 712
 713
 714
 715