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
FatInsertName(IN PIRP_CONTEXT IrpContext,IN PRTL_SPLAY_LINKS * RootNode,IN PFILE_NAME_NODE Name)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
FatRemoveNames(IN PIRP_CONTEXT IrpContext,IN PFCB Fcb)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
FatFindFcb(IN PIRP_CONTEXT IrpContext,IN OUT PRTL_SPLAY_LINKS * RootNode,IN PSTRING Name,OUT PBOOLEAN FileNameDos OPTIONAL)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
FatCompareNames(IN PSTRING NameA,IN PSTRING NameB)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