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     IN 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     IN PFCB Fcb,
  55     IN PCD_NAME Name,
  56     IN BOOLEAN IgnoreCase,
  57     IN BOOLEAN ShortNameMatch,
  58     IN 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     IN 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     //
 233     //  Start with the short name prefix entry.
 234     //
 235
 236     if (Fcb->ShortNamePrefix != NULL) {
 237
 238         if (FlagOn( Fcb->ShortNamePrefix->PrefixFlags, PREFIX_FLAG_IGNORE_CASE_IN_TREE )) {
 239
 240             Fcb->ParentFcb->IgnoreCaseRoot = RtlDelete( &Fcb->ShortNamePrefix->IgnoreCaseName.Links );
 241         }
 242
 243         if (FlagOn( Fcb->ShortNamePrefix->PrefixFlags, PREFIX_FLAG_EXACT_CASE_IN_TREE )) {
 244
 245             Fcb->ParentFcb->ExactCaseRoot = RtlDelete( &Fcb->ShortNamePrefix->ExactCaseName.Links );
 246         }
 247
 248         ClearFlag( Fcb->ShortNamePrefix->PrefixFlags,
 249                    PREFIX_FLAG_IGNORE_CASE_IN_TREE | PREFIX_FLAG_EXACT_CASE_IN_TREE );
 250     }
 251
 252     //
 253     //  Now do the long name prefix entries.
 254     //
 255
 256     if (FlagOn( Fcb->FileNamePrefix.PrefixFlags, PREFIX_FLAG_IGNORE_CASE_IN_TREE )) {
 257
 258         Fcb->ParentFcb->IgnoreCaseRoot = RtlDelete( &Fcb->FileNamePrefix.IgnoreCaseName.Links );
 259     }
 260
 261     if (FlagOn( Fcb->FileNamePrefix.PrefixFlags, PREFIX_FLAG_EXACT_CASE_IN_TREE )) {
 262
 263         Fcb->ParentFcb->ExactCaseRoot = RtlDelete( &Fcb->FileNamePrefix.ExactCaseName.Links );
 264     }
 265
 266     ClearFlag( Fcb->FileNamePrefix.PrefixFlags,
 267                PREFIX_FLAG_IGNORE_CASE_IN_TREE | PREFIX_FLAG_EXACT_CASE_IN_TREE );
 268
 269     //
 270     //  Deallocate any buffer we may have allocated.
 271     //
 272
 273     if ((Fcb->FileNamePrefix.ExactCaseName.FileName.Buffer != (PWCHAR) &Fcb->FileNamePrefix.FileNameBuffer) &&
 274         (Fcb->FileNamePrefix.ExactCaseName.FileName.Buffer != NULL)) {
 275
 276         CdFreePool( &Fcb->FileNamePrefix.ExactCaseName.FileName.Buffer );
 277         Fcb->FileNamePrefix.ExactCaseName.FileName.Buffer = NULL;
 278     }
 279
 280     return;
 281 }
 282
 283 \f
 284 VOID
 285 CdFindPrefix (
 286     IN PIRP_CONTEXT IrpContext,
 287     IN OUT PFCB *CurrentFcb,
 288     IN OUT PUNICODE_STRING RemainingName,
 289     IN BOOLEAN IgnoreCase
 290     )
 291
 292 /*++
 293
 294 Routine Description:
 295
 296     This routine begins from the given CurrentFcb and walks through all of
 297     components of the name looking for the longest match in the prefix
 298     splay trees.  The search is relative to the starting Fcb so the
 299     full name may not begin with a '\'.  On return this routine will
 300     update Current Fcb with the lowest point it has travelled in the
 301     tree.  It will also hold only that resource on return and it must
 302     hold that resource.
 303
 304 Arguments:
 305
 306     CurrentFcb - Address to store the lowest Fcb we find on this search.
 307         On return we will have acquired this Fcb.  On entry this is the
 308         Fcb to examine.
 309
 310     RemainingName - Supplies a buffer to store the exact case of the name being
 311         searched for.  Initially will contain the upcase name based on the
 312         IgnoreCase flag.
 313
 314     IgnoreCase - Indicates if we are doing a case-insensitive compare.
 315
 316 Return Value:
 317
 318     None
 319
 320 --*/
 321
 322 {
 323     UNICODE_STRING LocalRemainingName;
 324
 325     UNICODE_STRING FinalName;
 326
 327     PNAME_LINK NameLink;
 328     PPREFIX_ENTRY PrefixEntry;
 329
 330     PAGED_CODE();
 331
 332     //
 333     //  Make a local copy of the input strings.
 334     //
 335
 336     LocalRemainingName = *RemainingName;
 337
 338     //
 339     //  Loop until we find the longest matching prefix.
 340     //
 341
 342     while (TRUE) {
 343
 344         //
 345         //  If there are no characters left or we are not at an IndexFcb then
 346         //  return immediately.
 347         //
 348
 349         if ((LocalRemainingName.Length == 0) ||
 350             (SafeNodeType( *CurrentFcb ) != CDFS_NTC_FCB_INDEX)) {
 351
 352             return;
 353         }
 354
 355         //
 356         //  Split off the next component from the name.
 357         //
 358
 359         CdDissectName( IrpContext,
 360                        &LocalRemainingName,
 361                        &FinalName );
 362
 363         //
 364         //  Check if this name is in the splay tree for this Scb.
 365         //
 366
 367         if (IgnoreCase) {
 368
 369             NameLink = CdFindNameLink( IrpContext,
 370                                        &(*CurrentFcb)->IgnoreCaseRoot,
 371                                        &FinalName );
 372
 373             //
 374             //  Get the prefix entry from this NameLink.  Don't access any
 375             //  fields within it until we verify we have a name link.
 376             //
 377
 378             PrefixEntry = (PPREFIX_ENTRY) CONTAINING_RECORD( NameLink,
 379                                                              PREFIX_ENTRY,
 380                                                              IgnoreCaseName );
 381
 382         } else {
 383
 384             NameLink = CdFindNameLink( IrpContext,
 385                                        &(*CurrentFcb)->ExactCaseRoot,
 386                                        &FinalName );
 387
 388             PrefixEntry = (PPREFIX_ENTRY) CONTAINING_RECORD( NameLink,
 389                                                              PREFIX_ENTRY,
 390                                                              ExactCaseName );
 391         }
 392
 393         //
 394         //  If we didn't find a match then exit.
 395         //
 396
 397         if (NameLink == NULL) { return; }
 398
 399         //
 400         //  If this is a case-insensitive match then copy the exact case of the name into
 401         //  the input buffer.
 402         //
 403
 404         if (IgnoreCase) {
 405
 406             RtlCopyMemory( FinalName.Buffer,
 407                            PrefixEntry->ExactCaseName.FileName.Buffer,
 408                            PrefixEntry->ExactCaseName.FileName.Length );
 409         }
 410
 411         //
 412         //  Update the caller's remaining name string to reflect the fact that we found
 413         //  a match.
 414         //
 415
 416         *RemainingName = LocalRemainingName;
 417
 418         //
 419         //  Move down to the next component in the tree.  Acquire without waiting.
 420         //  If this fails then lock the Fcb to reference this Fcb and then drop
 421         //  the parent and acquire the child.
 422         //
 423
 424         if (!CdAcquireFcbExclusive( IrpContext, PrefixEntry->Fcb, TRUE )) {
 425
 426             //
 427             //  If we can't wait then raise CANT_WAIT.
 428             //
 429
 430             if (!FlagOn( IrpContext->Flags, IRP_CONTEXT_FLAG_WAIT )) {
 431
 432                 CdRaiseStatus( IrpContext, STATUS_CANT_WAIT );
 433             }
 434
 435             CdLockVcb( IrpContext, IrpContext->Vcb );
 436             PrefixEntry->Fcb->FcbReference += 1;
 437             CdUnlockVcb( IrpContext, IrpContext->Vcb );
 438
 439             CdReleaseFcb( IrpContext, *CurrentFcb );
 440             CdAcquireFcbExclusive( IrpContext, PrefixEntry->Fcb, FALSE );
 441
 442             CdLockVcb( IrpContext, IrpContext->Vcb );
 443             PrefixEntry->Fcb->FcbReference -= 1;
 444             CdUnlockVcb( IrpContext, IrpContext->Vcb );
 445
 446         } else {
 447
 448             CdReleaseFcb( IrpContext, *CurrentFcb );
 449         }
 450
 451         *CurrentFcb = PrefixEntry->Fcb;
 452     }
 453 }
 454
 455 \f
 456 //
 457 //  Local support routine
 458 //
 459
 460 PNAME_LINK
 461 CdFindNameLink (
 462     IN PIRP_CONTEXT IrpContext,
 463     IN PRTL_SPLAY_LINKS *RootNode,
 464     IN PUNICODE_STRING Name
 465     )
 466
 467 /*++
 468
 469 Routine Description:
 470
 471     This routine searches through a splay link tree looking for a match for the
 472     input name.  If we find the corresponding name we will rebalance the
 473     tree.
 474
 475 Arguments:
 476
 477     RootNode - Supplies the parent to search.
 478
 479     Name - This is the name to search for.  Note if we are doing a case
 480         insensitive search the name would have been upcased already.
 481
 482 Return Value:
 483
 484     PNAME_LINK - The name link found or NULL if there is no match.
 485
 486 --*/
 487
 488 {
 489     FSRTL_COMPARISON_RESULT Comparison;
 490     PNAME_LINK Node;
 491     PRTL_SPLAY_LINKS Links;
 492
 493     PAGED_CODE();
 494
 495     Links = *RootNode;
 496
 497     while (Links != NULL) {
 498
 499         Node = CONTAINING_RECORD( Links, NAME_LINK, Links );
 500
 501         //
 502         //  Compare the prefix in the tree with the full name
 503         //
 504
 505         Comparison = CdFullCompareNames( IrpContext, &Node->FileName, Name );
 506
 507         //
 508         //  See if they don't match
 509         //
 510
 511         if (Comparison == GreaterThan) {
 512
 513             //
 514             //  The prefix is greater than the full name
 515             //  so we go down the left child
 516             //
 517
 518             Links = RtlLeftChild( Links );
 519
 520             //
 521             //  And continue searching down this tree
 522             //
 523
 524         } else if (Comparison == LessThan) {
 525
 526             //
 527             //  The prefix is less than the full name
 528             //  so we go down the right child
 529             //
 530
 531             Links = RtlRightChild( Links );
 532
 533             //
 534             //  And continue searching down this tree
 535             //
 536
 537         } else {
 538
 539             //
 540             //  We found it.
 541             //
 542             //  Splay the tree and save the new root.
 543             //
 544
 545             *RootNode = RtlSplay( Links );
 546
 547             return Node;
 548         }
 549     }
 550
 551     //
 552     //  We didn't find the Link.
 553     //
 554
 555     return NULL;
 556 }
 557
 558 \f
 559 //
 560 //  Local support routine
 561 //
 562
 563 BOOLEAN
 564 CdInsertNameLink (
 565     IN PIRP_CONTEXT IrpContext,
 566     IN PRTL_SPLAY_LINKS *RootNode,
 567     IN PNAME_LINK NameLink
 568     )
 569
 570 /*++
 571
 572 Routine Description:
 573
 574     This routine will insert a name in the splay tree pointed to
 575     by RootNode.
 576
 577     The name could already exist in this tree for a case-insensitive tree.
 578     In that case we simply return FALSE and do nothing.
 579
 580 Arguments:
 581
 582     RootNode - Supplies a pointer to the table.
 583
 584     NameLink - Contains the new link to enter.
 585
 586 Return Value:
 587
 588     BOOLEAN - TRUE if the name is inserted, FALSE otherwise.
 589
 590 --*/
 591
 592 {
 593     FSRTL_COMPARISON_RESULT Comparison;
 594     PNAME_LINK Node;
 595
 596     PAGED_CODE();
 597
 598     RtlInitializeSplayLinks( &NameLink->Links );
 599
 600     //
 601     //  If we are the first entry in the tree, just become the root.
 602     //
 603
 604     if (*RootNode == NULL) {
 605
 606         *RootNode = &NameLink->Links;
 607
 608         return TRUE;
 609     }
 610
 611     Node = CONTAINING_RECORD( *RootNode, NAME_LINK, Links );
 612
 613     while (TRUE) {
 614
 615         //
 616         //  Compare the prefix in the tree with the prefix we want
 617         //  to insert.
 618         //
 619
 620         Comparison = CdFullCompareNames( IrpContext, &Node->FileName, &NameLink->FileName );
 621
 622         //
 623         //  If we found the entry, return immediately.
 624         //
 625
 626         if (Comparison == EqualTo) { return FALSE; }
 627
 628         //
 629         //  If the tree prefix is greater than the new prefix then
 630         //  we go down the left subtree
 631         //
 632
 633         if (Comparison == GreaterThan) {
 634
 635             //
 636             //  We want to go down the left subtree, first check to see
 637             //  if we have a left subtree
 638             //
 639
 640             if (RtlLeftChild( &Node->Links ) == NULL) {
 641
 642                 //
 643                 //  there isn't a left child so we insert ourselves as the
 644                 //  new left child
 645                 //
 646
 647                 RtlInsertAsLeftChild( &Node->Links, &NameLink->Links );
 648
 649                 //
 650                 //  and exit the while loop
 651                 //
 652
 653                 break;
 654
 655             } else {
 656
 657                 //
 658                 //  there is a left child so simply go down that path, and
 659                 //  go back to the top of the loop
 660                 //
 661
 662                 Node = CONTAINING_RECORD( RtlLeftChild( &Node->Links ),
 663                                           NAME_LINK,
 664                                           Links );
 665             }
 666
 667         } else {
 668
 669             //
 670             //  The tree prefix is either less than or a proper prefix
 671             //  of the new string.  We treat both cases as less than when
 672             //  we do insert.  So we want to go down the right subtree,
 673             //  first check to see if we have a right subtree
 674             //
 675
 676             if (RtlRightChild( &Node->Links ) == NULL) {
 677
 678                 //
 679                 //  These isn't a right child so we insert ourselves as the
 680                 //  new right child
 681                 //
 682
 683                 RtlInsertAsRightChild( &Node->Links, &NameLink->Links );
 684
 685                 //
 686                 //  and exit the while loop
 687                 //
 688
 689                 break;
 690
 691             } else {
 692
 693                 //
 694                 //  there is a right child so simply go down that path, and
 695                 //  go back to the top of the loop
 696                 //
 697
 698                 Node = CONTAINING_RECORD( RtlRightChild( &Node->Links ),
 699                                           NAME_LINK,
 700                                           Links );
 701             }
 702         }
 703     }
 704
 705     return TRUE;
 706 }
 707
 708
 709
 710
 711