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
51 VOID
CdInsertPrefix(_In_ PIRP_CONTEXT IrpContext,_Inout_ PFCB Fcb,_In_ PCD_NAME Name,_In_ BOOLEAN IgnoreCase,_In_ BOOLEAN ShortNameMatch,_Inout_ PFCB ParentFcb)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
206 VOID
CdRemovePrefix(_In_ PIRP_CONTEXT IrpContext,_Inout_ PFCB Fcb)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
286
_Requires_lock_held_(_Global_critical_region_)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
460 //
461 // Local support routine
462 //
463
464 PNAME_LINK
CdFindNameLink(_In_ PIRP_CONTEXT IrpContext,_In_ PRTL_SPLAY_LINKS * RootNode,_In_ PUNICODE_STRING Name)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
563 //
564 // Local support routine
565 //
566
567 BOOLEAN
CdInsertNameLink(_In_ PIRP_CONTEXT IrpContext,_Inout_ PRTL_SPLAY_LINKS * RootNode,_In_ PNAME_LINK NameLink)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
716