test: prefxsup.c File Reference

00565 : 00566 00567 This routine searches through a splay link tree looking for a match for the 00568 input name. If we find the corresponding name we will rebalance the 00569 tree. 00570 00571 Arguments: 00572 00573 RootNode - Supplies the parent to search. 00574 00575 Name - This is the name to search for. Note if we are doing a case 00576 insensitive search the name would have been upcased already. 00577 00578 Return Value: 00579 00580 PLCB - The name link found or NULL if there is no match. 00581 00582 --*/ 00583 00584 { 00585 FSRTL_COMPARISON_RESULT Comparison; 00586 PLCB Node; 00587 PRTL_SPLAY_LINKS Links; 00588 00589 PAGED_CODE(); 00590 00591 Links = *RootNode; 00592 00593 while (Links != NULL) { 00594 00595 Node = CONTAINING_RECORD( Links, LCB, Links ); 00596 00597 // 00598 // Compare the prefix in the tree with the full name 00599 // 00600 00601 Comparison = UdfFullCompareNames( IrpContext, &Node->FileName, Name ); 00602 00603 // 00604 // See if they don't match 00605 // 00606 00607 if (Comparison == GreaterThan) { 00608 00609 // 00610 // The prefix is greater than the full name 00611 // so we go down the left child 00612 // 00613 00614 Links = RtlLeftChild( Links ); 00615 00616 // 00617 // And continue searching down this tree 00618 // 00619 00620 } else if (Comparison == LessThan) { 00621 00622 // 00623 // The prefix is less than the full name 00624 // so we go down the right child 00625 // 00626 00627 Links = RtlRightChild( Links ); 00628 00629 // 00630 // And continue searching down this tree 00631 // 00632 00633 } else { 00634 00635 // 00636 // We found it. 00637 // 00638 // Splay the tree and save the new root. 00639 // 00640 00641 *RootNode = RtlSplay( Links ); 00642 00643 return Node; 00644 } 00645 } 00646 00647 // 00648 // We didn't find the Link. 00649 // 00650 00651 return NULL; 00652 }

00333 : 00334 00335 This routine begins from the given CurrentFcb and walks through all of 00336 components of the name looking for the longest match in the prefix 00337 splay trees. The search is relative to the starting Fcb so the 00338 full name may not begin with a '\'. On return this routine will 00339 update Current Fcb with the lowest point it has travelled in the 00340 tree. It will also hold only that resource on return and it must 00341 hold that resource. 00342 00343 Arguments: 00344 00345 CurrentFcb - Address to store the lowest Fcb we find on this search. 00346 On return we will have acquired this Fcb. On entry this is the 00347 Fcb to examine. 00348 00349 RemainingName - Supplies a buffer to store the exact case of the name being 00350 searched for. Initially will contain the upcase name based on the 00351 IgnoreCase flag. 00352 00353 IgnoreCase - Indicates if we are doing a case-insensitive compare. 00354 00355 Return Value: 00356 00357 The Lcb used to find the current Fcb, NULL if we didn't find any prefix 00358 Fcbs. 00359 00360 --*/ 00361 00362 { 00363 UNICODE_STRING LocalRemainingName; 00364 UNICODE_STRING FinalName; 00365 00366 PLCB NameLink; 00367 PLCB CurrentLcb = NULL; 00368 00369 PAGED_CODE(); 00370 00371 // 00372 // Check inputs. 00373 // 00374 00375 ASSERT_IRP_CONTEXT( IrpContext ); 00376 ASSERT_FCB( *CurrentFcb ); 00377 ASSERT_EXCLUSIVE_FCB( *CurrentFcb ); 00378 00379 // 00380 // Make a local copy of the input strings. 00381 // 00382 00383 LocalRemainingName = *RemainingName; 00384 00385 // 00386 // Loop until we find the longest matching prefix. 00387 // 00388 00389 while (TRUE) { 00390 00391 // 00392 // If there are no characters left or we are not at an IndexFcb then 00393 // return immediately. 00394 // 00395 00396 if ((LocalRemainingName.Length == 0) || 00397 (SafeNodeType( *CurrentFcb ) != UDFS_NTC_FCB_INDEX)) { 00398 00399 return CurrentLcb; 00400 } 00401 00402 // 00403 // Split off the next component from the name. 00404 // 00405 00406 UdfDissectName( IrpContext, 00407 &LocalRemainingName, 00408 &FinalName ); 00409 00410 // 00411 // Check if this name is in the splay tree for this Scb. 00412 // 00413 00414 if (IgnoreCase) { 00415 00416 NameLink = UdfFindNameLink( IrpContext, 00417 &(*CurrentFcb)->IgnoreCaseRoot, 00418 &FinalName ); 00419 00420 } else { 00421 00422 NameLink = UdfFindNameLink( IrpContext, 00423 &(*CurrentFcb)->ExactCaseRoot, 00424 &FinalName ); 00425 } 00426 00427 // 00428 // If we didn't find a match then exit. 00429 // 00430 00431 if (NameLink == NULL) { 00432 00433 break; 00434 } 00435 00436 CurrentLcb = NameLink; 00437 00438 // 00439 // If this is a case-insensitive match then copy the exact case of the name into 00440 // the input buffer. 00441 // 00442 00443 if (IgnoreCase) { 00444 00445 RtlCopyMemory( FinalName.Buffer, 00446 NameLink->FileName.Buffer, 00447 NameLink->FileName.Length ); 00448 } 00449 00450 // 00451 // Update the caller's remaining name string to reflect the fact that we found 00452 // a match. 00453 // 00454 00455 *RemainingName = LocalRemainingName; 00456 00457 // 00458 // Move down to the next component in the tree. Acquire without waiting. 00459 // If this fails then lock the Fcb to reference this Fcb and then drop 00460 // the parent and acquire the child. 00461 // 00462 00463 ASSERT( NameLink->ParentFcb == *CurrentFcb ); 00464 00465 if (!UdfAcquireFcbExclusive( IrpContext, NameLink->ChildFcb, TRUE )) { 00466 00467 // 00468 // If we can't wait then raise CANT_WAIT. 00469 // 00470 00471 if (!FlagOn( IrpContext->Flags, IRP_CONTEXT_FLAG_WAIT )) { 00472 00473 UdfRaiseStatus( IrpContext, STATUS_CANT_WAIT ); 00474 } 00475 00476 UdfLockVcb( IrpContext, IrpContext->Vcb ); 00477 NameLink->ChildFcb->FcbReference += 1; 00478 NameLink->Reference += 1; 00479 UdfUnlockVcb( IrpContext, IrpContext->Vcb ); 00480 00481 UdfReleaseFcb( IrpContext, *CurrentFcb ); 00482 UdfAcquireFcbExclusive( IrpContext, NameLink->ChildFcb, FALSE ); 00483 00484 UdfLockVcb( IrpContext, IrpContext->Vcb ); 00485 NameLink->ChildFcb->FcbReference -= 1; 00486 NameLink->Reference -= 1; 00487 UdfUnlockVcb( IrpContext, IrpContext->Vcb ); 00488 00489 } else { 00490 00491 UdfReleaseFcb( IrpContext, *CurrentFcb ); 00492 } 00493 00494 *CurrentFcb = NameLink->ChildFcb; 00495 } 00496 00497 return CurrentLcb; 00498 }

00511 : 00512 00513 This routine performs common initialization of Lcbs from found directory 00514 entries. 00515 00516 Arguments: 00517 00518 Lcb - the Lcb to initialize. 00519 00520 DirContext - the directory enumeration context, enumerated to the FID associated 00521 with this Lcb. 00522 00523 Return Value: 00524 00525 None. 00526 00527 --*/ 00528 00529 { 00530 PAGED_CODE(); 00531 00532 // 00533 // Check inputs. 00534 // 00535 00536 ASSERT_IRP_CONTEXT( IrpContext ); 00537 ASSERT_LCB( Lcb ); 00538 00539 ASSERT( DirContext->Fid != NULL ); 00540 00541 // 00542 // This is falling down trivial now. Simply update the hidden flag in the Lcb. 00543 // 00544 00545 if (FlagOn( DirContext->Fid->Flags, NSR_FID_F_HIDDEN )) { 00546 00547 SetFlag( Lcb->FileAttributes, FILE_ATTRIBUTE_HIDDEN ); 00548 } 00549 }

00668 : 00669 00670 This routine will insert a name in the splay tree pointed to 00671 by RootNode. 00672 00673 Arguments: 00674 00675 RootNode - Supplies a pointer to the table. 00676 00677 NameLink - Contains the new link to enter. 00678 00679 Return Value: 00680 00681 BOOLEAN - TRUE if the name is inserted, FALSE otherwise. 00682 00683 --*/ 00684 00685 { 00686 FSRTL_COMPARISON_RESULT Comparison; 00687 PLCB Node; 00688 00689 PAGED_CODE(); 00690 00691 // 00692 // Check inputs. 00693 // 00694 00695 ASSERT_IRP_CONTEXT( IrpContext ); 00696 00697 RtlInitializeSplayLinks( &NameLink->Links ); 00698 00699 // 00700 // If we are the first entry in the tree, just become the root. 00701 // 00702 00703 if (*RootNode == NULL) { 00704 00705 *RootNode = &NameLink->Links; 00706 00707 return TRUE; 00708 } 00709 00710 Node = CONTAINING_RECORD( *RootNode, LCB, Links ); 00711 00712 while (TRUE) { 00713 00714 // 00715 // Compare the prefix in the tree with the prefix we want 00716 // to insert. 00717 // 00718 00719 Comparison = UdfFullCompareNames( IrpContext, &Node->FileName, &NameLink->FileName ); 00720 00721 // 00722 // If we found the entry, return immediately. 00723 // 00724 00725 if (Comparison == EqualTo) { return FALSE; } 00726 00727 // 00728 // If the tree prefix is greater than the new prefix then 00729 // we go down the left subtree 00730 // 00731 00732 if (Comparison == GreaterThan) { 00733 00734 // 00735 // We want to go down the left subtree, first check to see 00736 // if we have a left subtree 00737 // 00738 00739 if (RtlLeftChild( &Node->Links ) == NULL) { 00740 00741 // 00742 // there isn't a left child so we insert ourselves as the 00743 // new left child 00744 // 00745 00746 RtlInsertAsLeftChild( &Node->Links, &NameLink->Links ); 00747 00748 // 00749 // and exit the while loop 00750 // 00751 00752 break; 00753 00754 } else { 00755 00756 // 00757 // there is a left child so simply go down that path, and 00758 // go back to the top of the loop 00759 // 00760 00761 Node = CONTAINING_RECORD( RtlLeftChild( &Node->Links ), 00762 LCB, 00763 Links ); 00764 } 00765 00766 } else { 00767 00768 // 00769 // The tree prefix is either less than or a proper prefix 00770 // of the new string. We treat both cases as less than when 00771 // we do insert. So we want to go down the right subtree, 00772 // first check to see if we have a right subtree 00773 // 00774 00775 if (RtlRightChild( &Node->Links ) == NULL) { 00776 00777 // 00778 // These isn't a right child so we insert ourselves as the 00779 // new right child 00780 // 00781 00782 RtlInsertAsRightChild( &Node->Links, &NameLink->Links ); 00783 00784 // 00785 // and exit the while loop 00786 // 00787 00788 break; 00789 00790 } else { 00791 00792 // 00793 // there is a right child so simply go down that path, and 00794 // go back to the top of the loop 00795 // 00796 00797 Node = CONTAINING_RECORD( RtlRightChild( &Node->Links ), 00798 LCB, 00799 Links ); 00800 } 00801 } 00802 } 00803 00804 return TRUE; 00805 }

00075 : 00076 00077 This routine inserts an Lcb linking the two Fcbs together. 00078 00079 Arguments: 00080 00081 Fcb - This is the Fcb whose name is being inserted into the tree. 00082 00083 Name - This is the name for the component. 00084 00085 ShortNameMatch - Indicates whether this name was found on an explicit 8.3 search 00086 00087 IgnoreCase - Indicates if we should insert into the case-insensitive tree. 00088 00089 ParentFcb - This is the ParentFcb. The prefix tree is attached to this. 00090 00091 Return Value: 00092 00093 PLCB - the Lcb inserted. 00094 00095 --*/ 00096 00097 { 00098 PLCB Lcb; 00099 PRTL_SPLAY_LINKS *TreeRoot; 00100 PLIST_ENTRY ListLinks; 00101 ULONG Flags; 00102 00103 PWCHAR NameBuffer; 00104 00105 PAGED_CODE(); 00106 00107 // 00108 // Check inputs. 00109 // 00110 00111 ASSERT_IRP_CONTEXT( IrpContext ); 00112 ASSERT_FCB( Fcb ); 00113 00114 ASSERT_EXCLUSIVE_FCB( Fcb ); 00115 ASSERT_EXCLUSIVE_FCB( ParentFcb ); 00116 ASSERT_FCB_INDEX( ParentFcb ); 00117 00118 // 00119 // It must be the case that an index Fcb is only referenced by a single index. Now 00120 // we walk the child's Lcb queue to insure that if any prefixes have already been 00121 // inserted, they all refer to the index Fcb we are linking to. This is the only way 00122 // we can detect directory cross-linkage. 00123 // 00124 00125 if (SafeNodeType( Fcb ) == UDFS_NTC_FCB_INDEX) { 00126 00127 for (ListLinks = Fcb->ParentLcbQueue.Flink; 00128 ListLinks != &Fcb->ParentLcbQueue; 00129 ListLinks = ListLinks->Flink) { 00130 00131 Lcb = CONTAINING_RECORD( ListLinks, LCB, ChildFcbLinks ); 00132 00133 if (Lcb->ParentFcb != ParentFcb) { 00134 00135 UdfRaiseStatus( IrpContext, STATUS_DISK_CORRUPT_ERROR ); 00136 } 00137 } 00138 } 00139 00140 // 00141 // Capture the separate cases. 00142 // 00143 00144 if (IgnoreCase) { 00145 00146 TreeRoot = &ParentFcb->IgnoreCaseRoot; 00147 Flags = LCB_FLAG_IGNORE_CASE; 00148 00149 } else { 00150 00151 TreeRoot = &ParentFcb->ExactCaseRoot; 00152 Flags = 0; 00153 } 00154 00155 if (ShortNameMatch) { 00156 00157 SetFlag( Flags, LCB_FLAG_SHORT_NAME ); 00158 } 00159 00160 // 00161 // Allocate space for the Lcb. 00162 // 00163 00164 if ( sizeof( LCB ) + Name->Length > SIZEOF_LOOKASIDE_LCB ) { 00165 00166 Lcb = FsRtlAllocatePoolWithTag( UdfPagedPool, 00167 sizeof( LCB ) + Name->Length, 00168 TAG_LCB ); 00169 00170 SetFlag( Flags, LCB_FLAG_POOL_ALLOCATED ); 00171 00172 } else { 00173 00174 Lcb = ExAllocateFromPagedLookasideList( &UdfLcbLookasideList ); 00175 } 00176 00177 // 00178 // Set the type and size. 00179 // 00180 00181 Lcb->NodeTypeCode = UDFS_NTC_LCB; 00182 Lcb->NodeByteSize = sizeof( LCB ) + Name->Length; 00183 00184 // 00185 // Initialize the name-based file attributes. 00186 // 00187 00188 Lcb->FileAttributes = 0; 00189 00190 // 00191 // Set up the filename in the Lcb. 00192 // 00193 00194 Lcb->FileName.Length = 00195 Lcb->FileName.MaximumLength = Name->Length; 00196 00197 Lcb->FileName.Buffer = Add2Ptr( Lcb, sizeof( LCB ), PWCHAR ); 00198 00199 RtlCopyMemory( Lcb->FileName.Buffer, 00200 Name->Buffer, 00201 Name->Length ); 00202 00203 // 00204 // Insert the Lcb into the prefix tree. 00205 // 00206 00207 Lcb->Flags = Flags; 00208 00209 if (!UdfInsertNameLink( IrpContext, 00210 TreeRoot, 00211 Lcb )) { 00212 00213 // 00214 // This will very rarely occur. 00215 // 00216 00217 UdfFreePool( &Lcb ); 00218 00219 Lcb = UdfFindNameLink( IrpContext, 00220 TreeRoot, 00221 Name ); 00222 00223 if (Lcb == NULL) { 00224 00225 // 00226 // Even worse. 00227 // 00228 00229 UdfRaiseStatus( IrpContext, STATUS_DRIVER_INTERNAL_ERROR ); 00230 } 00231 00232 return Lcb; 00233 } 00234 00235 // 00236 // Link the Fcbs together through the Lcb. 00237 // 00238 00239 Lcb->ParentFcb = ParentFcb; 00240 Lcb->ChildFcb = Fcb; 00241 00242 InsertHeadList( &ParentFcb->ChildLcbQueue, &Lcb->ParentFcbLinks ); 00243 InsertHeadList( &Fcb->ParentLcbQueue, &Lcb->ChildFcbLinks ); 00244 00245 // 00246 // Initialize the reference count. 00247 // 00248 00249 Lcb->Reference = 0; 00250 00251 return Lcb; 00252 }

00263 : 00264 00265 This routine is called to remove a given prefix of an Fcb. 00266 00267 Arguments: 00268 00269 Lcb - the prefix being removed. 00270 00271 Return Value: 00272 00273 None 00274 00275 --*/ 00276 00277 { 00278 PAGED_CODE(); 00279 00280 // 00281 // Check inputs. 00282 // 00283 00284 ASSERT_IRP_CONTEXT( IrpContext ); 00285 ASSERT_LCB( Lcb ); 00286 00287 // 00288 // Check the acquisition of the two Fcbs. 00289 // 00290 00291 ASSERT_EXCLUSIVE_FCB_OR_VCB( Lcb->ParentFcb ); 00292 ASSERT_EXCLUSIVE_FCB_OR_VCB( Lcb->ChildFcb ); 00293 00294 // 00295 // Now remove the linkage and delete the Lcb. 00296 // 00297 00298 RemoveEntryList( &Lcb->ParentFcbLinks ); 00299 RemoveEntryList( &Lcb->ChildFcbLinks ); 00300 00301 if (FlagOn( Lcb->Flags, LCB_FLAG_IGNORE_CASE )) { 00302 00303 Lcb->ParentFcb->IgnoreCaseRoot = RtlDelete( &Lcb->Links ); 00304 00305 } else { 00306 00307 Lcb->ParentFcb->ExactCaseRoot = RtlDelete( &Lcb->Links ); 00308 } 00309 00310 if (FlagOn( Lcb->Flags, LCB_FLAG_POOL_ALLOCATED )) { 00311 00312 ExFreePool( Lcb ); 00313 00314 } else { 00315 00316 ExFreeToPagedLookasideList( &UdfLcbLookasideList, Lcb ); 00317 } 00318 00319 return; 00320 }


Defines
#define	BugCheckFileId (UDFS_BUG_CHECK_PREFXSUP)
#define	Dbg (UDFS_DEBUG_LEVEL_READ)
Functions
PLCB	UdfFindNameLink (IN PIRP_CONTEXT IrpContext, IN PRTL_SPLAY_LINKS *RootNode, IN PUNICODE_STRING Name)
BOOLEAN	UdfInsertNameLink (IN PIRP_CONTEXT IrpContext, IN PRTL_SPLAY_LINKS *RootNode, IN PLCB NameLink)
PLCB	UdfInsertPrefix (IN PIRP_CONTEXT IrpContext, IN PFCB Fcb, IN PUNICODE_STRING Name, IN BOOLEAN ShortNameMatch, IN BOOLEAN IgnoreCase, IN PFCB ParentFcb)
VOID	UdfRemovePrefix (IN PIRP_CONTEXT IrpContext, IN PLCB Lcb)
PLCB	UdfFindPrefix (IN PIRP_CONTEXT IrpContext, IN OUT PFCB *CurrentFcb, IN OUT PUNICODE_STRING RemainingName, IN BOOLEAN IgnoreCase)
VOID	UdfInitializeLcbFromDirContext (IN PIRP_CONTEXT IrpContext, IN PLCB Lcb, IN PDIR_ENUM_CONTEXT DirContext)

prefxsup.c File Reference

Defines

Functions

Define Documentation

Function Documentation