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 Fat Name lookup Suport routines 12 13 14 --*/ 15 16 #include "fatprocs.h" 17 18 // 19 // The Bug check file id for this module 20 // 21 22 #define BugCheckFileId (FAT_BUG_CHECK_SPLAYSUP) 23 24 // 25 // The debug trace level for this module 26 // 27 28 #define Dbg (DEBUG_TRACE_SPLAYSUP) 29 30 #ifdef ALLOC_PRAGMA 31 #pragma alloc_text(PAGE, FatInsertName) 32 #pragma alloc_text(PAGE, FatRemoveNames) 33 #pragma alloc_text(PAGE, FatFindFcb) 34 #pragma alloc_text(PAGE, FatCompareNames) 35 #endif 36 37 38 VOID 39 FatInsertName ( 40 IN PIRP_CONTEXT IrpContext, 41 IN PRTL_SPLAY_LINKS *RootNode, 42 IN PFILE_NAME_NODE Name 43 ) 44 45 /*++ 46 47 Routine Description: 48 49 This routine will insert a name in the splay tree pointed to 50 by RootNode. 51 52 The name must not already exist in the splay tree. 53 54 Arguments: 55 56 RootNode - Supplies a pointer to the table. 57 58 Name - Contains the New name to enter. 59 60 Return Value: 61 62 None. 63 64 --*/ 65 66 { 67 COMPARISON Comparison; 68 PFILE_NAME_NODE Node; 69 70 PAGED_CODE(); 71 72 RtlInitializeSplayLinks(&Name->Links); 73 74 Restart: 75 76 // 77 // If we are the first entry in the tree, just become the root. 78 // 79 80 if (*RootNode == NULL) { 81 82 *RootNode = &Name->Links; 83 84 return; 85 } 86 87 Node = CONTAINING_RECORD( *RootNode, FILE_NAME_NODE, Links ); 88 89 while (TRUE) { 90 91 // 92 // Compare the prefix in the tree with the prefix we want 93 // to insert. Note that Oem here doesn't mean anything. 94 // 95 96 Comparison = CompareNames(&Node->Name.Oem, &Name->Name.Oem); 97 98 // 99 // We should never find the name in the table already. 100 // 101 102 if (Comparison == IsEqual) { 103 104 // 105 // Almost. If the removable media was taken to another machine and 106 // back, and we have something like: 107 // 108 // Old: abcdef~1 / abcdefxyz 109 // New: abcdef~1 / abcdefxyzxyz 110 // 111 // but a handle was kept open to abcdefxyz so we couldn't purge 112 // away the Fcb in the verify path ... opening abcdefxyzxyz will 113 // try to insert a duplicate shortname. Bang! 114 // 115 // Invalidate it and the horse it came in on. This new one wins. 116 // The old one is gone. Only if the old one is in normal state 117 // do we really have a problem. 118 // 119 120 if (Node->Fcb->FcbState == FcbGood) { 121 122 #ifdef _MSC_VER 123 #pragma prefast( suppress:28159, "things are seriously wrong if we get here" ) 124 #endif 125 FatBugCheck( (ULONG_PTR)*RootNode, (ULONG_PTR)Name, (ULONG_PTR)Node ); 126 } 127 128 // 129 // Note, once we zap the prefix links we need to restart our walk 130 // of the tree. Note that we aren't properly synchronized to 131 // recursively mark bad. 132 // 133 134 FatMarkFcbCondition( IrpContext, Node->Fcb, FcbBad, FALSE ); 135 FatRemoveNames( IrpContext, Node->Fcb ); 136 137 goto Restart; 138 } 139 140 // 141 // If the tree prefix is greater than the new prefix then 142 // we go down the left subtree 143 // 144 145 if (Comparison == IsGreaterThan) { 146 147 // 148 // We want to go down the left subtree, first check to see 149 // if we have a left subtree 150 // 151 152 if (RtlLeftChild(&Node->Links) == NULL) { 153 154 // 155 // there isn't a left child so we insert ourselves as the 156 // new left child 157 // 158 159 RtlInsertAsLeftChild(&Node->Links, &Name->Links); 160 161 // 162 // and exit the while loop 163 // 164 165 break; 166 167 } else { 168 169 // 170 // there is a left child so simply go down that path, and 171 // go back to the top of the loop 172 // 173 174 Node = CONTAINING_RECORD( RtlLeftChild(&Node->Links), 175 FILE_NAME_NODE, 176 Links ); 177 } 178 179 } else { 180 181 // 182 // The tree prefix is either less than or a proper prefix 183 // of the new string. We treat both cases a less than when 184 // we do insert. So we want to go down the right subtree, 185 // first check to see if we have a right subtree 186 // 187 188 if (RtlRightChild(&Node->Links) == NULL) { 189 190 // 191 // These isn't a right child so we insert ourselves as the 192 // new right child 193 // 194 195 RtlInsertAsRightChild(&Node->Links, &Name->Links); 196 197 // 198 // and exit the while loop 199 // 200 201 break; 202 203 } else { 204 205 // 206 // there is a right child so simply go down that path, and 207 // go back to the top of the loop 208 // 209 210 Node = CONTAINING_RECORD( RtlRightChild(&Node->Links), 211 FILE_NAME_NODE, 212 Links ); 213 } 214 215 } 216 } 217 218 return; 219 } 220 221 VOID 222 FatRemoveNames ( 223 IN PIRP_CONTEXT IrpContext, 224 IN PFCB Fcb 225 ) 226 227 /*++ 228 229 Routine Description: 230 231 This routine will remove the short name and any long names associated 232 with the files from their repsective splay tree. 233 234 Arguments: 235 236 Name - Supplies the Fcb to process. 237 238 Return Value: 239 240 None. 241 242 --*/ 243 244 { 245 PDCB Parent; 246 PRTL_SPLAY_LINKS NewRoot; 247 248 PAGED_CODE(); 249 UNREFERENCED_PARAMETER( IrpContext ); 250 251 Parent = Fcb->ParentDcb; 252 253 // 254 // We used to assert this condition, but it really isn't good. If 255 // someone rapidly renames a directory multiple times and we can't 256 // flush the lower fcbs fast enough (that didn't go away synch.) 257 // well, well hit some of them again. 258 // 259 // NT_ASSERT( FlagOn( Fcb->FcbState, FCB_STATE_NAMES_IN_SPLAY_TREE )); 260 // 261 262 if (FlagOn( Fcb->FcbState, FCB_STATE_NAMES_IN_SPLAY_TREE )) { 263 264 // 265 // Delete the node short name. 266 // 267 268 NewRoot = RtlDelete(&Fcb->ShortName.Links); 269 270 Parent->Specific.Dcb.RootOemNode = NewRoot; 271 272 // 273 // Now check for the presence of long name and delete it. 274 // 275 276 if (FlagOn( Fcb->FcbState, FCB_STATE_HAS_OEM_LONG_NAME )) { 277 278 NewRoot = RtlDelete(&Fcb->LongName.Oem.Links); 279 280 Parent->Specific.Dcb.RootOemNode = NewRoot; 281 282 RtlFreeOemString( &Fcb->LongName.Oem.Name.Oem ); 283 284 ClearFlag( Fcb->FcbState, FCB_STATE_HAS_OEM_LONG_NAME ); 285 } 286 287 if (FlagOn( Fcb->FcbState, FCB_STATE_HAS_UNICODE_LONG_NAME )) { 288 289 NewRoot = RtlDelete(&Fcb->LongName.Unicode.Links); 290 291 Parent->Specific.Dcb.RootUnicodeNode = NewRoot; 292 293 RtlFreeUnicodeString( &Fcb->LongName.Unicode.Name.Unicode ); 294 295 ClearFlag( Fcb->FcbState, FCB_STATE_HAS_UNICODE_LONG_NAME ); 296 } 297 298 ClearFlag( Fcb->FcbState, FCB_STATE_NAMES_IN_SPLAY_TREE ); 299 } 300 301 return; 302 } 303 304 305 PFCB 306 FatFindFcb ( 307 IN PIRP_CONTEXT IrpContext, 308 IN OUT PRTL_SPLAY_LINKS *RootNode, 309 IN PSTRING Name, 310 OUT PBOOLEAN FileNameDos OPTIONAL 311 ) 312 313 /*++ 314 315 Routine Description: 316 317 This routine searches either the Oem or Unicode splay tree looking 318 for an Fcb with the specified name. In the case the Fcb is found, 319 rebalance the tree. 320 321 Arguments: 322 323 RootNode - Supplies the parent to search. 324 325 Name - If present, search the Oem tree. 326 327 UnicodeName - If present, search the Unicode tree. 328 329 Return Value: 330 331 PFCB - The Fcb, or NULL if none was found. 332 333 --*/ 334 335 { 336 COMPARISON Comparison; 337 PFILE_NAME_NODE Node; 338 PRTL_SPLAY_LINKS Links; 339 340 PAGED_CODE(); 341 UNREFERENCED_PARAMETER( IrpContext ); 342 343 Links = *RootNode; 344 345 while (Links != NULL) { 346 347 Node = CONTAINING_RECORD(Links, FILE_NAME_NODE, Links); 348 349 // 350 // Compare the prefix in the tree with the full name 351 // 352 353 Comparison = CompareNames(&Node->Name.Oem, Name); 354 355 // 356 // See if they don't match 357 // 358 359 if (Comparison == IsGreaterThan) { 360 361 // 362 // The prefix is greater than the full name 363 // so we go down the left child 364 // 365 366 Links = RtlLeftChild(Links); 367 368 // 369 // And continue searching down this tree 370 // 371 372 } else if (Comparison == IsLessThan) { 373 374 // 375 // The prefix is less than the full name 376 // so we go down the right child 377 // 378 379 Links = RtlRightChild(Links); 380 381 // 382 // And continue searching down this tree 383 // 384 385 } else { 386 387 // 388 // We found it. 389 // 390 // Splay the tree and save the new root. 391 // 392 393 *RootNode = RtlSplay(Links); 394 395 // 396 // Tell the caller what kind of name we hit 397 // 398 399 if (FileNameDos) { 400 401 *FileNameDos = Node->FileNameDos; 402 } 403 404 return Node->Fcb; 405 } 406 } 407 408 // 409 // We didn't find the Fcb. 410 // 411 412 return NULL; 413 } 414 415 416 // 417 // Local support routine 418 // 419 420 COMPARISON 421 FatCompareNames ( 422 IN PSTRING NameA, 423 IN PSTRING NameB 424 ) 425 426 /*++ 427 428 Routine Description: 429 430 This function compares two names as fast as possible. Note that since 431 this comparison is case sensitive, I neither know nor case if the names 432 are UNICODE or OEM. All that is important is that the result is 433 deterministic. 434 435 Arguments: 436 437 NameA & NameB - The names to compare. 438 439 Return Value: 440 441 COMPARISON - returns 442 443 IsLessThan if NameA < NameB lexicalgraphically, 444 IsGreaterThan if NameA > NameB lexicalgraphically, 445 IsEqual if NameA is equal to NameB 446 447 --*/ 448 449 { 450 ULONG i; 451 ULONG MinLength; 452 453 PAGED_CODE(); 454 455 // 456 // Figure out the minimum of the two lengths 457 // 458 459 MinLength = NameA->Length < NameB->Length ? NameA->Length : 460 NameB->Length; 461 462 // 463 // Loop through looking at all of the characters in both strings 464 // testing for equalilty, less than, and greater than 465 // 466 467 i = (ULONG)RtlCompareMemory( NameA->Buffer, NameB->Buffer, MinLength ); 468 469 470 if (i < MinLength) { 471 472 return NameA->Buffer[i] < NameB->Buffer[i] ? IsLessThan : 473 IsGreaterThan; 474 } 475 476 if (NameA->Length < NameB->Length) { 477 478 return IsLessThan; 479 } 480 481 if (NameA->Length > NameB->Length) { 482 483 return IsGreaterThan; 484 } 485 486 return IsEqual; 487 } 488 489