ReactOS 0.4.16-dev-297-gc569aee
prefxsup.c
Go to the documentation of this file.
1/*++
2
3Copyright (c) 1989-2000 Microsoft Corporation
4
5Module Name:
6
7 PrefxSup.c
8
9Abstract:
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
30 _In_ PIRP_CONTEXT IrpContext,
33 );
34
37 _In_ PIRP_CONTEXT IrpContext,
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
51VOID
53 _In_ PIRP_CONTEXT IrpContext,
57 _In_ BOOLEAN ShortNameMatch,
59 )
60
61/*++
62
63Routine Description:
64
65 This routine inserts the names in the given Lcb into the links for the
66 parent.
67
68Arguments:
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
81Return 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
110 sizeof( PREFIX_ENTRY ),
112
113 if (Fcb->ShortNamePrefix == NULL) { return; }
114
116 }
117
118 PrefixEntry = Fcb->ShortNamePrefix;
119 }
120
121 //
122 // Capture the local variables for the separate cases.
123 //
124
125 if (IgnoreCase) {
126
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,
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
155 Name->FileName.Length * 2,
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
175 PrefixEntry->IgnoreCaseName.FileName.Length =
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
206VOID
208 _In_ PIRP_CONTEXT IrpContext,
210 )
211
212/*++
213
214Routine Description:
215
216 This routine is called to remove all of the previx entries of a
217 given Fcb from its parent Fcb.
218
219Arguments:
220
221 Fcb - Fcb whose entries are to be removed.
222
223Return 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
241
243 }
244
246
248 }
249
252 }
253
254 //
255 // Now do the long name prefix entries.
256 //
257
259
261 }
262
264
266 }
267
270
271 //
272 // Deallocate any buffer we may have allocated.
273 //
274
277
280 }
281
282 return;
283}
284
285
286
287_Requires_lock_held_(_Global_critical_region_)
288VOID
289CdFindPrefix (
290 _In_ PIRP_CONTEXT IrpContext,
294 )
295
296/*++
297
298Routine 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
308Arguments:
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
320Return 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) ||
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,
384 IgnoreCaseName );
385
386 } else {
387
388 NameLink = CdFindNameLink( IrpContext,
389 &(*CurrentFcb)->ExactCaseRoot,
390 &FinalName );
391
392 PrefixEntry = (PPREFIX_ENTRY) CONTAINING_RECORD( NameLink,
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
466 _In_ PIRP_CONTEXT IrpContext,
469 )
470
471/*++
472
473Routine 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
479Arguments:
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
486Return 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;
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
569 _In_ PIRP_CONTEXT IrpContext,
571 _In_ PNAME_LINK NameLink
572 )
573
574/*++
575
576Routine 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
584Arguments:
585
586 RootNode - Supplies a pointer to the table.
587
588 NameLink - Contains the new link to enter.
589
590Return Value:
591
592 BOOLEAN - TRUE if the name is inserted, FALSE otherwise.
593
594--*/
595
596{
597 FSRTL_COMPARISON_RESULT Comparison;
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
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
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
703 NAME_LINK,
704 Links );
705 }
706 }
707 }
708
709 return TRUE;
710}
711
712
713
714
715
#define PAGED_CODE()
unsigned char BOOLEAN
BOOLEAN CdInsertNameLink(_In_ PIRP_CONTEXT IrpContext, _Inout_ PRTL_SPLAY_LINKS *RootNode, _In_ PNAME_LINK NameLink)
Definition: prefxsup.c:568
VOID CdInsertPrefix(_In_ PIRP_CONTEXT IrpContext, _Inout_ PFCB Fcb, _In_ PCD_NAME Name, _In_ BOOLEAN IgnoreCase, _In_ BOOLEAN ShortNameMatch, _Inout_ PFCB ParentFcb)
Definition: prefxsup.c:52
PNAME_LINK CdFindNameLink(_In_ PIRP_CONTEXT IrpContext, _In_ PRTL_SPLAY_LINKS *RootNode, _In_ PUNICODE_STRING Name)
Definition: prefxsup.c:465
VOID CdRemovePrefix(_In_ PIRP_CONTEXT IrpContext, _Inout_ PFCB Fcb)
Definition: prefxsup.c:207
#define TAG_PREFIX_NAME
Definition: cdprocs.h:102
_In_ PFCB ParentFcb
Definition: cdprocs.h:736
FSRTL_COMPARISON_RESULT CdFullCompareNames(_In_ PIRP_CONTEXT IrpContext, _In_ PUNICODE_STRING NameA, _In_ PUNICODE_STRING NameB)
Definition: namesup.c:1064
VOID CdDissectName(_In_ PIRP_CONTEXT IrpContext, _Inout_ PUNICODE_STRING RemainingName, _Out_ PUNICODE_STRING FinalName)
Definition: namesup.c:301
#define CdReleaseFcb(IC, F)
Definition: cdprocs.h:1012
#define CdLockVcb(IC, V)
Definition: cdprocs.h:1023
_Inout_ PFCB _Inout_ PUNICODE_STRING RemainingName
Definition: cdprocs.h:802
#define CdUnlockVcb(IC, V)
Definition: cdprocs.h:1028
_In_ PFCB Fcb
Definition: cdprocs.h:159
#define CdAcquireFcbExclusive(IC, F, I)
Definition: cdprocs.h:1006
_Inout_ PFCB * CurrentFcb
Definition: cdprocs.h:801
#define CdFreePool(x)
Definition: cdprocs.h:2190
#define CdPagedPool
Definition: cdprocs.h:1380
#define CdRaiseStatus(IC, S)
Definition: cdprocs.h:1859
#define TAG_PREFIX_ENTRY
Definition: cdprocs.h:101
PREFIX_ENTRY * PPREFIX_ENTRY
Definition: cdstruc.h:304
#define IRP_CONTEXT_FLAG_WAIT
Definition: cdstruc.h:1215
#define PREFIX_FLAG_IGNORE_CASE_IN_TREE
Definition: cdstruc.h:307
#define PREFIX_FLAG_EXACT_CASE_IN_TREE
Definition: cdstruc.h:306
#define BYTE_COUNT_EMBEDDED_NAME
Definition: cdstruc.h:171
#define _Requires_lock_held_(lock)
#define IgnoreCase
Definition: cdprocs.h:461
#define NULL
Definition: types.h:112
#define TRUE
Definition: types.h:120
#define FALSE
Definition: types.h:117
union node Node
Definition: types.h:1255
#define SafeNodeType(Ptr)
Definition: nodetype.h:54
#define CDFS_NTC_FCB_INDEX
Definition: nodetype.h:30
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
#define ClearFlag(_F, _SF)
Definition: ext2fs.h:191
#define SetFlag(_F, _SF)
Definition: ext2fs.h:187
#define FlagOn(_F, _SF)
Definition: ext2fs.h:179
@ LessThan
Definition: fsrtltypes.h:77
@ GreaterThan
Definition: fsrtltypes.h:79
@ EqualTo
Definition: fsrtltypes.h:78
enum _FSRTL_COMPARISON_RESULT FSRTL_COMPARISON_RESULT
#define Add2Ptr(PTR, INC)
PCONFIGURATION_COMPONENT_DATA RootNode
Definition: macharm.c:19
#define _Inout_
Definition: no_sal2.h:162
#define _In_
Definition: no_sal2.h:158
#define UNREFERENCED_PARAMETER(P)
Definition: ntbasedef.h:325
#define STATUS_CANT_WAIT
Definition: ntstatus.h:452
Definition: cdstruc.h:902
PREFIX_ENTRY FileNamePrefix
Definition: cdstruc.h:1024
struct _FCB * ParentFcb
Definition: cdstruc.h:940
PPREFIX_ENTRY ShortNamePrefix
Definition: cdstruc.h:1023
Definition: cdstruc.h:275
struct _FCB * Fcb
Definition: cdstruc.h:281
ULONG PrefixFlags
Definition: cdstruc.h:287
NAME_LINK IgnoreCaseName
Definition: cdstruc.h:299
NAME_LINK ExactCaseName
Definition: cdstruc.h:293
WCHAR FileNameBuffer[BYTE_COUNT_EMBEDDED_NAME]
Definition: cdstruc.h:301
USHORT MaximumLength
Definition: env_spec_w32.h:370
#define RtlCopyMemory(Destination, Source, Length)
Definition: typedefs.h:263
#define RtlZeroMemory(Destination, Length)
Definition: typedefs.h:262
uint16_t * PWCHAR
Definition: typedefs.h:56
#define CONTAINING_RECORD(address, type, field)
Definition: typedefs.h:260
uint32_t ULONG
Definition: typedefs.h:59
Definition: dlist.c:348
#define RtlRightChild(Links)
#define RtlLeftChild(Links)
NTSYSAPI PRTL_SPLAY_LINKS NTAPI RtlSplay(_Inout_ PRTL_SPLAY_LINKS Links)
#define RtlInsertAsRightChild(ParentLinks, ChildLinks)
NTSYSAPI PRTL_SPLAY_LINKS NTAPI RtlDelete(_In_ PRTL_SPLAY_LINKS Links)
#define RtlInitializeSplayLinks(Links)
#define RtlInsertAsLeftChild(ParentLinks, ChildLinks)