ReactOS  0.4.14-dev-593-g1793dcc
prefxsup.c
Go to the documentation of this file.
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 
30  _In_ PIRP_CONTEXT IrpContext,
33  );
34 
35 BOOLEAN
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 
51 VOID
53  _In_ PIRP_CONTEXT IrpContext,
57  _In_ BOOLEAN ShortNameMatch,
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 
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 
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,
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
208  _In_ PIRP_CONTEXT IrpContext,
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 
241 
242  Fcb->ParentFcb->IgnoreCaseRoot = RtlDelete( &Fcb->ShortNamePrefix->IgnoreCaseName.Links );
243  }
244 
246 
247  Fcb->ParentFcb->ExactCaseRoot = RtlDelete( &Fcb->ShortNamePrefix->ExactCaseName.Links );
248  }
249 
252  }
253 
254  //
255  // Now do the long name prefix entries.
256  //
257 
259 
260  Fcb->ParentFcb->IgnoreCaseRoot = RtlDelete( &Fcb->FileNamePrefix.IgnoreCaseName.Links );
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_)
288 VOID
289 CdFindPrefix (
290  _In_ PIRP_CONTEXT IrpContext,
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) ||
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 
466  _In_ PIRP_CONTEXT IrpContext,
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;
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
569  _In_ PIRP_CONTEXT IrpContext,
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;
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 
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 
703  NAME_LINK,
704  Links );
705  }
706  }
707  }
708 
709  return TRUE;
710 }
711 
712 
713 
714 
715 
NTSYSAPI PRTL_SPLAY_LINKS NTAPI RtlSplay(_Inout_ PRTL_SPLAY_LINKS Links)
#define TRUE
Definition: types.h:120
NTSYSAPI VOID NTAPI RtlCopyMemory(VOID UNALIGNED *Destination, CONST VOID UNALIGNED *Source, ULONG Length)
#define IRP_CONTEXT_FLAG_WAIT
Definition: cdstruc.h:1221
_Inout_ PFCB * CurrentFcb
Definition: cdprocs.h:806
#define Add2Ptr(PTR, INC)
PREFIX_ENTRY * PPREFIX_ENTRY
Definition: cdstruc.h:310
FSRTL_COMPARISON_RESULT CdFullCompareNames(_In_ PIRP_CONTEXT IrpContext, _In_ PUNICODE_STRING NameA, _In_ PUNICODE_STRING NameB)
Definition: namesup.c:1064
USHORT MaximumLength
Definition: env_spec_w32.h:370
#define TAG_PREFIX_NAME
Definition: cdprocs.h:94
#define UNREFERENCED_PARAMETER(P)
Definition: ntbasedef.h:323
Definition: cdstruc.h:908
#define RtlInsertAsRightChild(ParentLinks, ChildLinks)
#define SafeNodeType(Ptr)
Definition: nodetype.h:54
#define CdReleaseFcb(IC, F)
Definition: cdprocs.h:1017
ULONG PrefixFlags
Definition: cdstruc.h:293
uint16_t * PWCHAR
Definition: typedefs.h:54
#define PREFIX_FLAG_EXACT_CASE_IN_TREE
Definition: cdstruc.h:312
#define CdAcquireFcbExclusive(IC, F, I)
Definition: cdprocs.h:1011
#define CDFS_NTC_FCB_INDEX
Definition: nodetype.h:30
#define PAGED_CODE()
Definition: video.h:57
#define RtlInsertAsLeftChild(ParentLinks, ChildLinks)
PREFIX_ENTRY FileNamePrefix
Definition: cdstruc.h:1030
NAME_LINK ExactCaseName
Definition: cdstruc.h:299
union node Node
Definition: types.h:1255
PNAME_LINK CdFindNameLink(_In_ PIRP_CONTEXT IrpContext, _In_ PRTL_SPLAY_LINKS *RootNode, _In_ PUNICODE_STRING Name)
Definition: prefxsup.c:465
#define RtlInitializeSplayLinks(Links)
unsigned char BOOLEAN
smooth NULL
Definition: ftsmooth.c:416
PFLT_MESSAGE_WAITER_QUEUE CONTAINING_RECORD(Csq, DEVICE_EXTENSION, IrpQueue)) -> WaiterQ.mLock) _IRQL_raises_(DISPATCH_LEVEL) VOID NTAPI FltpAcquireMessageWaiterLock(_In_ PIO_CSQ Csq, _Out_ PKIRQL Irql)
Definition: Messaging.c:560
Definition: cdstruc.h:281
NTSYSAPI PRTL_SPLAY_LINKS NTAPI RtlDelete(_In_ PRTL_SPLAY_LINKS Links)
#define CdUnlockVcb(IC, V)
Definition: cdprocs.h:1033
_Requires_lock_held_(_Global_critical_region_)
Definition: prefxsup.c:287
#define CdPagedPool
Definition: cdprocs.h:1385
#define _Inout_
Definition: no_sal2.h:244
#define RtlLeftChild(Links)
_In_ PFCB ParentFcb
Definition: cdprocs.h:741
#define CdLockVcb(IC, V)
Definition: cdprocs.h:1028
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
#define FlagOn(_F, _SF)
Definition: ext2fs.h:179
ClearFlag(Dirent->Flags, DIRENT_FLAG_NOT_PERSISTENT)
VOID CdDissectName(_In_ PIRP_CONTEXT IrpContext, _Inout_ PUNICODE_STRING RemainingName, _Out_ PUNICODE_STRING FinalName)
Definition: namesup.c:301
#define _In_
Definition: no_sal2.h:204
#define SetFlag(_F, _SF)
Definition: ext2fs.h:187
#define CdFreePool(x)
Definition: cdprocs.h:2200
#define IgnoreCase
Definition: cdprocs.h:464
#define CdRaiseStatus(IC, S)
Definition: cdprocs.h:1869
PPREFIX_ENTRY ShortNamePrefix
Definition: cdstruc.h:1029
struct _FCB * Fcb
Definition: cdstruc.h:287
#define TAG_PREFIX_ENTRY
Definition: cdprocs.h:93
BOOLEAN CdInsertNameLink(_In_ PIRP_CONTEXT IrpContext, _Inout_ PRTL_SPLAY_LINKS *RootNode, _In_ PNAME_LINK NameLink)
Definition: prefxsup.c:568
enum _FSRTL_COMPARISON_RESULT FSRTL_COMPARISON_RESULT
#define BYTE_COUNT_EMBEDDED_NAME
Definition: cdstruc.h:171
unsigned int ULONG
Definition: retypes.h:1
#define RtlZeroMemory(Destination, Length)
Definition: typedefs.h:261
struct _FCB * ParentFcb
Definition: cdstruc.h:946
#define RtlRightChild(Links)
_In_ PFCB Fcb
Definition: cdprocs.h:151
VOID CdRemovePrefix(_In_ PIRP_CONTEXT IrpContext, _Inout_ PFCB Fcb)
Definition: prefxsup.c:207
NAME_LINK IgnoreCaseName
Definition: cdstruc.h:305
WCHAR FileNameBuffer[BYTE_COUNT_EMBEDDED_NAME]
Definition: cdstruc.h:307
#define PREFIX_FLAG_IGNORE_CASE_IN_TREE
Definition: cdstruc.h:313
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
PCONFIGURATION_COMPONENT_DATA RootNode
Definition: macharm.c:19
Definition: dlist.c:348
#define STATUS_CANT_WAIT
Definition: ntstatus.h:438
_Inout_ PFCB _Inout_ PUNICODE_STRING RemainingName
Definition: cdprocs.h:806