kFsCache.c@ 2930

Last change on this file since 2930 was 2930, checked in by bird, 9 years ago
kFsCache: Implemented lazy child hashing and increased the KFSCACHE_CFG_PATH_HASH_TAB_SIZE value from 16384 to 99991 to better deal with large kBuild trees (e.g. VBox).
Property svn:eol-style set to `native` Property svn:keywords set to `Id`
File size: 161.4 KB

Line
1	/* $Id: kFsCache.c 2930 2016-09-18 15:57:25Z bird $ */
2	/** @file
3	* ntdircache.c - NT directory content cache.
4	*/
5
6	/*
7	* Copyright (c) 2016 knut st. osmundsen <bird-kBuild-spamx@anduin.net>
8	*
9	* Permission is hereby granted, free of charge, to any person obtaining a
10	* copy of this software and associated documentation files (the "Software"),
11	* to deal in the Software without restriction, including without limitation
12	* the rights to use, copy, modify, merge, publish, distribute, sublicense,
13	* and/or sell copies of the Software, and to permit persons to whom the
14	* Software is furnished to do so, subject to the following conditions:
15	*
16	* The above copyright notice and this permission notice shall be included
17	* in all copies or substantial portions of the Software.
18	*
19	* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
20	* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
21	* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
22	* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
23	* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
24	* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
25	* IN THE SOFTWARE.
26	*
27	* Alternatively, the content of this file may be used under the terms of the
28	* GPL version 2 or later, or LGPL version 2.1 or later.
29	*/
30
31
32	/*********************************************************************************************************************************
33	* Header Files *
34	*********************************************************************************************************************************/
35	#include <k/kHlp.h>
36
37	#include "nthlp.h"
38	#include "ntstat.h"
39
40	#include <stdio.h>
41	#include <mbstring.h>
42	#include <wchar.h>
43	#ifdef _MSC_VER
44	# include <intrin.h>
45	#endif
46	//#include <setjmp.h>
47	//#include <ctype.h>
48
49
50	//#include <Windows.h>
51	//#include <winternl.h>
52
53	#include "kFsCache.h"
54
55
56	/*********************************************************************************************************************************
57	* Defined Constants And Macros *
58	*********************************************************************************************************************************/
59	/** @def KFSCACHE_LOG2
60	* More logging. */
61	#if 0
62	# define KFSCACHE_LOG2(a) KFSCACHE_LOG(a)
63	#else
64	# define KFSCACHE_LOG2(a) do { } while (0)
65	#endif
66
67
68	/*********************************************************************************************************************************
69	* Structures and Typedefs *
70	*********************************************************************************************************************************/
71	/**
72	* Used by the code re-populating a directory.
73	*/
74	typedef struct KFSDIRREPOP
75	{
76	/** The old papChildren array. */
77	PKFSOBJ *papOldChildren;
78	/** Number of children in the array. */
79	KU32 cOldChildren;
80	/** The index into papOldChildren we expect to find the next entry. */
81	KU32 iNextOldChild;
82	/** Add this to iNextOldChild . */
83	KI32 cNextOldChildInc;
84	/** Pointer to the cache (name changes). */
85	PKFSCACHE pCache;
86	} KFSDIRREPOP;
87	/** Pointer to directory re-population data. */
88	typedef KFSDIRREPOP *PKFSDIRREPOP;
89
90
91
92
93	/**
94	* Retains a reference to a cache object, internal version.
95	*
96	* @returns pObj
97	* @param pObj The object.
98	*/
99	K_INLINE PKFSOBJ kFsCacheObjRetainInternal(PKFSOBJ pObj)
100	{
101	KU32 cRefs = ++pObj->cRefs;
102	kHlpAssert(cRefs < 16384);
103	K_NOREF(cRefs);
104	return pObj;
105	}
106
107
108	#ifndef NDEBUG
109
110	/**
111	* Debug printing.
112	* @param pszFormat Debug format string.
113	* @param ... Format argument.
114	*/
115	void kFsCacheDbgPrintfV(const char *pszFormat, va_list va)
116	{
117	if (1)
118	{
119	DWORD const dwSavedErr = GetLastError();
120
121	fprintf(stderr, "debug: ");
122	vfprintf(stderr, pszFormat, va);
123
124	SetLastError(dwSavedErr);
125	}
126	}
127
128
129	/**
130	* Debug printing.
131	* @param pszFormat Debug format string.
132	* @param ... Format argument.
133	*/
134	void kFsCacheDbgPrintf(const char *pszFormat, ...)
135	{
136	if (1)
137	{
138	va_list va;
139	va_start(va, pszFormat);
140	kFsCacheDbgPrintfV(pszFormat, va);
141	va_end(va);
142	}
143	}
144
145	#endif /* !NDEBUG */
146
147
148
149	/**
150	* Hashes a string.
151	*
152	* @returns 32-bit string hash.
153	* @param pszString String to hash.
154	*/
155	static KU32 kFsCacheStrHash(const char *pszString)
156	{
157	/* This algorithm was created for sdbm (a public-domain reimplementation of
158	ndbm) database library. it was found to do well in scrambling bits,
159	causing better distribution of the keys and fewer splits. it also happens
160	to be a good general hashing function with good distribution. the actual
161	function is hash(i) = hash(i - 1) * 65599 + str[i]; what is included below
162	is the faster version used in gawk. [there is even a faster, duff-device
163	version] the magic constant 65599 was picked out of thin air while
164	experimenting with different constants, and turns out to be a prime.
165	this is one of the algorithms used in berkeley db (see sleepycat) and
166	elsewhere. */
167	KU32 uHash = 0;
168	KU32 uChar;
169	while ((uChar = (unsigned char)*pszString++) != 0)
170	uHash = uChar + (uHash << 6) + (uHash << 16) - uHash;
171	return uHash;
172	}
173
174
175	/**
176	* Hashes a string.
177	*
178	* @returns The string length.
179	* @param pszString String to hash.
180	* @param puHash Where to return the 32-bit string hash.
181	*/
182	static KSIZE kFsCacheStrHashEx(const char pszString, KU32 puHash)
183	{
184	const char * const pszStart = pszString;
185	KU32 uHash = 0;
186	KU32 uChar;
187	while ((uChar = (unsigned char)*pszString) != 0)
188	{
189	uHash = uChar + (uHash << 6) + (uHash << 16) - uHash;
190	pszString++;
191	}
192	*puHash = uHash;
193	return pszString - pszStart;
194	}
195
196
197	/**
198	* Hashes a substring.
199	*
200	* @returns 32-bit substring hash.
201	* @param pchString Pointer to the substring (not terminated).
202	* @param cchString The length of the substring.
203	*/
204	static KU32 kFsCacheStrHashN(const char *pchString, KSIZE cchString)
205	{
206	KU32 uHash = 0;
207	while (cchString-- > 0)
208	{
209	KU32 uChar = (unsigned char)*pchString++;
210	uHash = uChar + (uHash << 6) + (uHash << 16) - uHash;
211	}
212	return uHash;
213	}
214
215
216	/**
217	* Hashes a UTF-16 string.
218	*
219	* @returns The string length in wchar_t units.
220	* @param pwszString String to hash.
221	* @param puHash Where to return the 32-bit string hash.
222	*/
223	static KSIZE kFsCacheUtf16HashEx(const wchar_t pwszString, KU32 puHash)
224	{
225	const wchar_t * const pwszStart = pwszString;
226	KU32 uHash = 0;
227	KU32 uChar;
228	while ((uChar = *pwszString) != 0)
229	{
230	uHash = uChar + (uHash << 6) + (uHash << 16) - uHash;
231	pwszString++;
232	}
233	*puHash = uHash;
234	return pwszString - pwszStart;
235	}
236
237
238	/**
239	* Hashes a UTF-16 substring.
240	*
241	* @returns 32-bit substring hash.
242	* @param pwcString Pointer to the substring (not terminated).
243	* @param cchString The length of the substring (in wchar_t's).
244	*/
245	static KU32 kFsCacheUtf16HashN(const wchar_t *pwcString, KSIZE cwcString)
246	{
247	KU32 uHash = 0;
248	while (cwcString-- > 0)
249	{
250	KU32 uChar = *pwcString++;
251	uHash = uChar + (uHash << 6) + (uHash << 16) - uHash;
252	}
253	return uHash;
254	}
255
256
257	/**
258	* For use when kFsCacheIAreEqualW hit's something non-trivial.
259	*
260	* @returns K_TRUE if equal, K_FALSE if different.
261	* @param pwcName1 The first string.
262	* @param pwcName2 The second string.
263	* @param cwcName The length of the two strings (in wchar_t's).
264	*/
265	KBOOL kFsCacheIAreEqualSlowW(const wchar_t pwcName1, const wchar_t pwcName2, KU16 cwcName)
266	{
267	MY_UNICODE_STRING UniStr1 = { cwcName * sizeof(wchar_t), cwcName * sizeof(wchar_t), (wchar_t *)pwcName1 };
268	MY_UNICODE_STRING UniStr2 = { cwcName * sizeof(wchar_t), cwcName * sizeof(wchar_t), (wchar_t *)pwcName2 };
269	return g_pfnRtlEqualUnicodeString(&UniStr1, &UniStr2, TRUE /fCaseInsensitive/);
270	}
271
272
273	/**
274	* Compares two UTF-16 strings in a case-insensitive fashion.
275	*
276	* You would think we should be using _wscnicmp here instead, however it is
277	* locale dependent and defaults to ASCII upper/lower handling setlocale hasn't
278	* been called.
279	*
280	* @returns K_TRUE if equal, K_FALSE if different.
281	* @param pwcName1 The first string.
282	* @param pwcName2 The second string.
283	* @param cwcName The length of the two strings (in wchar_t's).
284	*/
285	K_INLINE KBOOL kFsCacheIAreEqualW(const wchar_t pwcName1, const wchar_t pwcName2, KU32 cwcName)
286	{
287	while (cwcName > 0)
288	{
289	wchar_t wc1 = *pwcName1;
290	wchar_t wc2 = *pwcName2;
291	if (wc1 == wc2)
292	{ /* not unlikely */ }
293	else if ( (KU16)wc1 < (KU16)0xc0 /* U+00C0 is the first upper/lower letter after 'z'. */
294	&& (KU16)wc2 < (KU16)0xc0)
295	{
296	/* ASCII upper case. */
297	if ((KU16)wc1 - (KU16)0x61 < (KU16)26)
298	wc1 &= ~(wchar_t)0x20;
299	if ((KU16)wc2 - (KU16)0x61 < (KU16)26)
300	wc2 &= ~(wchar_t)0x20;
301	if (wc1 != wc2)
302	return K_FALSE;
303	}
304	else
305	return kFsCacheIAreEqualSlowW(pwcName1, pwcName2, (KU16)cwcName);
306
307	pwcName2++;
308	pwcName1++;
309	cwcName--;
310	}
311
312	return K_TRUE;
313	}
314
315
316	/**
317	* Looks for '..' in the path.
318	*
319	* @returns K_TRUE if '..' component found, K_FALSE if not.
320	* @param pszPath The path.
321	* @param cchPath The length of the path.
322	*/
323	static KBOOL kFsCacheHasDotDotA(const char *pszPath, KSIZE cchPath)
324	{
325	const char pchDot = (const char )kHlpMemChr(pszPath, '.', cchPath);
326	while (pchDot)
327	{
328	if (pchDot[1] != '.')
329	{
330	pchDot++;
331	pchDot = (const char *)kHlpMemChr(pchDot, '.', &pszPath[cchPath] - pchDot);
332	}
333	else
334	{
335	char ch;
336	if ( (ch = pchDot[2]) != '\0'
337	&& IS_SLASH(ch))
338	{
339	if (pchDot == pszPath)
340	return K_TRUE;
341	ch = pchDot[-1];
342	if ( IS_SLASH(ch)
343	\|\| ch == ':')
344	return K_TRUE;
345	}
346	pchDot = (const char *)kHlpMemChr(pchDot + 2, '.', &pszPath[cchPath] - pchDot - 2);
347	}
348	}
349
350	return K_FALSE;
351	}
352
353
354	/**
355	* Looks for '..' in the path.
356	*
357	* @returns K_TRUE if '..' component found, K_FALSE if not.
358	* @param pwszPath The path.
359	* @param cwcPath The length of the path (in wchar_t's).
360	*/
361	static KBOOL kFsCacheHasDotDotW(const wchar_t *pwszPath, KSIZE cwcPath)
362	{
363	const wchar_t *pwcDot = wmemchr(pwszPath, '.', cwcPath);
364	while (pwcDot)
365	{
366	if (pwcDot[1] != '.')
367	{
368	pwcDot++;
369	pwcDot = wmemchr(pwcDot, '.', &pwszPath[cwcPath] - pwcDot);
370	}
371	else
372	{
373	wchar_t wch;
374	if ( (wch = pwcDot[2]) != '\0'
375	&& IS_SLASH(wch))
376	{
377	if (pwcDot == pwszPath)
378	return K_TRUE;
379	wch = pwcDot[-1];
380	if ( IS_SLASH(wch)
381	\|\| wch == ':')
382	return K_TRUE;
383	}
384	pwcDot = wmemchr(pwcDot + 2, '.', &pwszPath[cwcPath] - pwcDot - 2);
385	}
386	}
387
388	return K_FALSE;
389	}
390
391
392	/**
393	* Creates an ANSI hash table entry for the given path.
394	*
395	* @returns The hash table entry or NULL if out of memory.
396	* @param pCache The hash
397	* @param pFsObj The resulting object.
398	* @param pszPath The path.
399	* @param cchPath The length of the path.
400	* @param uHashPath The hash of the path.
401	* @param fAbsolute Whether it can be refreshed using an absolute
402	* lookup or requires the slow treatment.
403	* @parma idxMissingGen The missing generation index.
404	* @param idxHashTab The hash table index of the path.
405	* @param enmError The lookup error.
406	*/
407	static PKFSHASHA kFsCacheCreatePathHashTabEntryA(PKFSCACHE pCache, PKFSOBJ pFsObj, const char *pszPath, KU32 cchPath,
408	KU32 uHashPath, KU32 idxHashTab, BOOL fAbsolute, KU32 idxMissingGen,
409	KFSLOOKUPERROR enmError)
410	{
411	PKFSHASHA pHashEntry = (PKFSHASHA)kHlpAlloc(sizeof(*pHashEntry) + cchPath + 1);
412	if (pHashEntry)
413	{
414	pHashEntry->uHashPath = uHashPath;
415	pHashEntry->cchPath = (KU16)cchPath;
416	pHashEntry->fAbsolute = fAbsolute;
417	pHashEntry->idxMissingGen = (KU8)idxMissingGen;
418	pHashEntry->enmError = enmError;
419	pHashEntry->pszPath = (const char *)kHlpMemCopy(pHashEntry + 1, pszPath, cchPath + 1);
420	if (pFsObj)
421	{
422	pHashEntry->pFsObj = kFsCacheObjRetainInternal(pFsObj);
423	pHashEntry->uCacheGen = pFsObj->bObjType != KFSOBJ_TYPE_MISSING
424	? pCache->auGenerations[ pFsObj->fFlags & KFSOBJ_F_USE_CUSTOM_GEN]
425	: pCache->auGenerationsMissing[pFsObj->fFlags & KFSOBJ_F_USE_CUSTOM_GEN];
426	pFsObj->abUnused[0] += 1; // for debugging
427	}
428	else
429	{
430	pHashEntry->pFsObj = NULL;
431	if (enmError != KFSLOOKUPERROR_UNSUPPORTED)
432	pHashEntry->uCacheGen = pCache->auGenerationsMissing[idxMissingGen];
433	else
434	pHashEntry->uCacheGen = KFSOBJ_CACHE_GEN_IGNORE;
435	}
436
437	pHashEntry->pNext = pCache->apAnsiPaths[idxHashTab];
438	pCache->apAnsiPaths[idxHashTab] = pHashEntry;
439
440	pCache->cbAnsiPaths += sizeof(*pHashEntry) + cchPath + 1;
441	pCache->cAnsiPaths++;
442	if (pHashEntry->pNext)
443	pCache->cAnsiPathCollisions++;
444	}
445	return pHashEntry;
446	}
447
448
449	/**
450	* Creates an UTF-16 hash table entry for the given path.
451	*
452	* @returns The hash table entry or NULL if out of memory.
453	* @param pCache The hash
454	* @param pFsObj The resulting object.
455	* @param pwszPath The path.
456	* @param cwcPath The length of the path (in wchar_t's).
457	* @param uHashPath The hash of the path.
458	* @param fAbsolute Whether it can be refreshed using an absolute
459	* lookup or requires the slow treatment.
460	* @parma idxMissingGen The missing generation index.
461	* @param idxHashTab The hash table index of the path.
462	* @param enmError The lookup error.
463	*/
464	static PKFSHASHW kFsCacheCreatePathHashTabEntryW(PKFSCACHE pCache, PKFSOBJ pFsObj, const wchar_t *pwszPath, KU32 cwcPath,
465	KU32 uHashPath, KU32 idxHashTab, BOOL fAbsolute, KU32 idxMissingGen,
466	KFSLOOKUPERROR enmError)
467	{
468	PKFSHASHW pHashEntry = (PKFSHASHW)kHlpAlloc(sizeof(pHashEntry) + (cwcPath + 1) sizeof(wchar_t));
469	if (pHashEntry)
470	{
471	pHashEntry->uHashPath = uHashPath;
472	pHashEntry->cwcPath = cwcPath;
473	pHashEntry->fAbsolute = fAbsolute;
474	pHashEntry->idxMissingGen = (KU8)idxMissingGen;
475	pHashEntry->enmError = enmError;
476	pHashEntry->pwszPath = (const wchar_t )kHlpMemCopy(pHashEntry + 1, pwszPath, (cwcPath + 1) sizeof(wchar_t));
477	if (pFsObj)
478	{
479	pHashEntry->pFsObj = kFsCacheObjRetainInternal(pFsObj);
480	pHashEntry->uCacheGen = pFsObj->bObjType != KFSOBJ_TYPE_MISSING
481	? pCache->auGenerations[ pFsObj->fFlags & KFSOBJ_F_USE_CUSTOM_GEN]
482	: pCache->auGenerationsMissing[pFsObj->fFlags & KFSOBJ_F_USE_CUSTOM_GEN];
483	pFsObj->abUnused[0] += 1; // for debugging
484	}
485	else
486	{
487	pHashEntry->pFsObj = NULL;
488	if (enmError != KFSLOOKUPERROR_UNSUPPORTED)
489	pHashEntry->uCacheGen = pCache->auGenerationsMissing[idxMissingGen];
490	else
491	pHashEntry->uCacheGen = KFSOBJ_CACHE_GEN_IGNORE;
492	}
493
494	pHashEntry->pNext = pCache->apUtf16Paths[idxHashTab];
495	pCache->apUtf16Paths[idxHashTab] = pHashEntry;
496
497	pCache->cbUtf16Paths += sizeof(pHashEntry) + (cwcPath + 1) sizeof(wchar_t);
498	pCache->cUtf16Paths++;
499	if (pHashEntry->pNext)
500	pCache->cAnsiPathCollisions++;
501	}
502	return pHashEntry;
503	}
504
505
506	/**
507	* Links the child in under the parent.
508	*
509	* @returns K_TRUE on success, K_FALSE if out of memory.
510	* @param pParent The parent node.
511	* @param pChild The child node.
512	*/
513	static KBOOL kFsCacheDirAddChild(PKFSCACHE pCache, PKFSDIR pParent, PKFSOBJ pChild, KFSLOOKUPERROR *penmError)
514	{
515	if (pParent->cChildren >= pParent->cChildrenAllocated)
516	{
517	void pvNew = kHlpRealloc(pParent->papChildren, (pParent->cChildrenAllocated + 16) sizeof(pParent->papChildren[0]));
518	if (!pvNew)
519	return K_FALSE;
520	pParent->papChildren = (PKFSOBJ *)pvNew;
521	pParent->cChildrenAllocated += 16;
522	pCache->cbObjects += 16 * sizeof(pParent->papChildren[0]);
523	}
524	pParent->papChildren[pParent->cChildren++] = kFsCacheObjRetainInternal(pChild);
525	return K_TRUE;
526	}
527
528
529	/**
530	* Creates a new cache object.
531	*
532	* @returns Pointer (with 1 reference) to the new object. The object will not
533	* be linked to the parent directory yet.
534	*
535	* NULL if we're out of memory.
536	*
537	* @param pCache The cache.
538	* @param pParent The parent directory.
539	* @param pszName The ANSI name.
540	* @param cchName The length of the ANSI name.
541	* @param pwszName The UTF-16 name.
542	* @param cwcName The length of the UTF-16 name.
543	* @param pszShortName The ANSI short name, NULL if none.
544	* @param cchShortName The length of the ANSI short name, 0 if none.
545	* @param pwszShortName The UTF-16 short name, NULL if none.
546	* @param cwcShortName The length of the UTF-16 short name, 0 if none.
547	* @param bObjType The objct type.
548	* @param penmError Where to explain failures.
549	*/
550	PKFSOBJ kFsCacheCreateObject(PKFSCACHE pCache, PKFSDIR pParent,
551	char const pszName, KU16 cchName, wchar_t const pwszName, KU16 cwcName,
552	#ifdef KFSCACHE_CFG_SHORT_NAMES
553	char const pszShortName, KU16 cchShortName, wchar_t const pwszShortName, KU16 cwcShortName,
554	#endif
555	KU8 bObjType, KFSLOOKUPERROR *penmError)
556	{
557	/*
558	* Allocate the object.
559	*/
560	KBOOL const fDirish = bObjType != KFSOBJ_TYPE_FILE && bObjType != KFSOBJ_TYPE_OTHER;
561	KSIZE const cbObj = fDirish ? sizeof(KFSDIR) : sizeof(KFSOBJ);
562	KSIZE const cbNames = (cwcName + 1) * sizeof(wchar_t) + cchName + 1
563	#ifdef KFSCACHE_CFG_SHORT_NAMES
564	+ (cwcShortName > 0 ? (cwcShortName + 1) * sizeof(wchar_t) + cchShortName + 1 : 0)
565	#endif
566	;
567	PKFSOBJ pObj;
568	kHlpAssert(pCache->u32Magic == KFSCACHE_MAGIC);
569
570	pObj = (PKFSOBJ)kHlpAlloc(cbObj + cbNames);
571	if (pObj)
572	{
573	KU8 pbExtra = (KU8 )pObj + cbObj;
574
575	pCache->cbObjects += cbObj + cbNames;
576	pCache->cObjects++;
577
578	/*
579	* Initialize the object.
580	*/
581	pObj->u32Magic = KFSOBJ_MAGIC;
582	pObj->cRefs = 1;
583	pObj->uCacheGen = bObjType != KFSOBJ_TYPE_MISSING
584	? pCache->auGenerations[pParent->Obj.fFlags & KFSOBJ_F_USE_CUSTOM_GEN]
585	: pCache->auGenerationsMissing[pParent->Obj.fFlags & KFSOBJ_F_USE_CUSTOM_GEN];
586	pObj->bObjType = bObjType;
587	pObj->fHaveStats = K_FALSE;
588	pObj->abUnused[0] = K_FALSE;
589	pObj->abUnused[1] = K_FALSE;
590	pObj->fFlags = pParent->Obj.fFlags & KFSOBJ_F_INHERITED_MASK;
591	pObj->pParent = pParent;
592	pObj->uNameHash = 0;
593	pObj->pNextNameHash = NULL;
594	pObj->pUserDataHead = NULL;
595
596	#ifdef KFSCACHE_CFG_UTF16
597	pObj->cwcParent = pParent->Obj.cwcParent + pParent->Obj.cwcName + !!pParent->Obj.cwcName;
598	pObj->pwszName = (wchar_t )kHlpMemCopy(pbExtra, pwszName, cwcName sizeof(wchar_t));
599	pObj->cwcName = cwcName;
600	pbExtra += cwcName * sizeof(wchar_t);
601	*pbExtra++ = '\0';
602	*pbExtra++ = '\0';
603	# ifdef KFSCACHE_CFG_SHORT_NAMES
604	pObj->cwcShortParent = pParent->Obj.cwcShortParent + pParent->Obj.cwcShortName + !!pParent->Obj.cwcShortName;
605	if (cwcShortName)
606	{
607	pObj->pwszShortName = (wchar_t )kHlpMemCopy(pbExtra, pwszShortName, cwcShortName sizeof(wchar_t));
608	pObj->cwcShortName = cwcShortName;
609	pbExtra += cwcShortName * sizeof(wchar_t);
610	*pbExtra++ = '\0';
611	*pbExtra++ = '\0';
612	}
613	else
614	{
615	pObj->pwszShortName = pObj->pwszName;
616	pObj->cwcShortName = cwcName;
617	}
618	# endif
619	#endif
620	pObj->cchParent = pParent->Obj.cchParent + pParent->Obj.cchName + !!pParent->Obj.cchName;
621	pObj->pszName = (char *)kHlpMemCopy(pbExtra, pszName, cchName);
622	pObj->cchName = cchName;
623	pbExtra += cchName;
624	*pbExtra++ = '\0';
625	# ifdef KFSCACHE_CFG_SHORT_NAMES
626	pObj->cchShortParent = pParent->Obj.cchShortParent + pParent->Obj.cchShortName + !!pParent->Obj.cchShortName;
627	if (cchShortName)
628	{
629	pObj->pszShortName = (char *)kHlpMemCopy(pbExtra, pszShortName, cchShortName);
630	pObj->cchShortName = cchShortName;
631	pbExtra += cchShortName;
632	*pbExtra++ = '\0';
633	}
634	else
635	{
636	pObj->pszShortName = pObj->pszName;
637	pObj->cchShortName = cchName;
638	}
639	#endif
640	kHlpAssert(pbExtra - (KU8 *)pObj == cbObj);
641
642	/*
643	* Type specific initialization.
644	*/
645	if (fDirish)
646	{
647	PKFSDIR pDirObj = (PKFSDIR)pObj;
648	pDirObj->cChildren = 0;
649	pDirObj->cChildrenAllocated = 0;
650	pDirObj->papChildren = NULL;
651	pDirObj->fHashTabMask = 0;
652	pDirObj->papHashTab = NULL;
653	pDirObj->hDir = INVALID_HANDLE_VALUE;
654	pDirObj->uDevNo = pParent->uDevNo;
655	pDirObj->iLastWrite = 0;
656	pDirObj->fPopulated = K_FALSE;
657	}
658	}
659	else
660	*penmError = KFSLOOKUPERROR_OUT_OF_MEMORY;
661	return pObj;
662	}
663
664
665	/**
666	* Creates a new object given wide char names.
667	*
668	* This function just converts the paths and calls kFsCacheCreateObject.
669	*
670	*
671	* @returns Pointer (with 1 reference) to the new object. The object will not
672	* be linked to the parent directory yet.
673	*
674	* NULL if we're out of memory.
675	*
676	* @param pCache The cache.
677	* @param pParent The parent directory.
678	* @param pszName The ANSI name.
679	* @param cchName The length of the ANSI name.
680	* @param pwszName The UTF-16 name.
681	* @param cwcName The length of the UTF-16 name.
682	* @param pwszShortName The UTF-16 short name, NULL if none.
683	* @param cwcShortName The length of the UTF-16 short name, 0 if none.
684	* @param bObjType The objct type.
685	* @param penmError Where to explain failures.
686	*/
687	PKFSOBJ kFsCacheCreateObjectW(PKFSCACHE pCache, PKFSDIR pParent, wchar_t const *pwszName, KU32 cwcName,
688	#ifdef KFSCACHE_CFG_SHORT_NAMES
689	wchar_t const *pwszShortName, KU32 cwcShortName,
690	#endif
691	KU8 bObjType, KFSLOOKUPERROR *penmError)
692	{
693	/* Convert names to ANSI first so we know their lengths. */
694	char szName[KFSCACHE_CFG_MAX_ANSI_NAME];
695	int cchName = WideCharToMultiByte(CP_ACP, 0, pwszName, cwcName, szName, sizeof(szName) - 1, NULL, NULL);
696	if (cchName >= 0)
697	{
698	#ifdef KFSCACHE_CFG_SHORT_NAMES
699	char szShortName[12*3 + 1];
700	int cchShortName = 0;
701	if ( cwcShortName == 0
702	\|\| (cchShortName = WideCharToMultiByte(CP_ACP, 0, pwszShortName, cwcShortName,
703	szShortName, sizeof(szShortName) - 1, NULL, NULL)) > 0)
704	#endif
705	{
706	return kFsCacheCreateObject(pCache, pParent,
707	szName, cchName, pwszName, cwcName,
708	#ifdef KFSCACHE_CFG_SHORT_NAMES
709	szShortName, cchShortName, pwszShortName, cwcShortName,
710	#endif
711	bObjType, penmError);
712	}
713	}
714	*penmError = KFSLOOKUPERROR_ANSI_CONVERSION_ERROR;
715	return NULL;
716	}
717
718
719	/**
720	* Creates a missing object.
721	*
722	* This is used for caching negative results.
723	*
724	* @returns Pointer to the newly created object on success (already linked into
725	* pParent). No reference.
726	*
727	* NULL on failure.
728	*
729	* @param pCache The cache.
730	* @param pParent The parent directory.
731	* @param pchName The name.
732	* @param cchName The length of the name.
733	* @param penmError Where to return failure explanations.
734	*/
735	static PKFSOBJ kFsCacheCreateMissingA(PKFSCACHE pCache, PKFSDIR pParent, const char *pchName, KU32 cchName,
736	KFSLOOKUPERROR *penmError)
737	{
738	/*
739	* Just convert the name to UTF-16 and call kFsCacheCreateObject to do the job.
740	*/
741	wchar_t wszName[KFSCACHE_CFG_MAX_PATH];
742	int cwcName = MultiByteToWideChar(CP_ACP, 0, pchName, cchName, wszName, KFSCACHE_CFG_MAX_UTF16_NAME - 1);
743	if (cwcName > 0)
744	{
745	/** @todo check that it actually doesn't exists before we add it. We should not
746	* trust the directory enumeration here, or maybe we should?? */
747
748	PKFSOBJ pMissing = kFsCacheCreateObject(pCache, pParent, pchName, cchName, wszName, cwcName,
749	#ifdef KFSCACHE_CFG_SHORT_NAMES
750	NULL, 0, NULL, 0,
751	#endif
752	KFSOBJ_TYPE_MISSING, penmError);
753	if (pMissing)
754	{
755	KBOOL fRc = kFsCacheDirAddChild(pCache, pParent, pMissing, penmError);
756	kFsCacheObjRelease(pCache, pMissing);
757	return fRc ? pMissing : NULL;
758	}
759	return NULL;
760	}
761	*penmError = KFSLOOKUPERROR_UTF16_CONVERSION_ERROR;
762	return NULL;
763	}
764
765
766	/**
767	* Creates a missing object, UTF-16 version.
768	*
769	* This is used for caching negative results.
770	*
771	* @returns Pointer to the newly created object on success (already linked into
772	* pParent). No reference.
773	*
774	* NULL on failure.
775	*
776	* @param pCache The cache.
777	* @param pParent The parent directory.
778	* @param pwcName The name.
779	* @param cwcName The length of the name.
780	* @param penmError Where to return failure explanations.
781	*/
782	static PKFSOBJ kFsCacheCreateMissingW(PKFSCACHE pCache, PKFSDIR pParent, const wchar_t *pwcName, KU32 cwcName,
783	KFSLOOKUPERROR *penmError)
784	{
785	/** @todo check that it actually doesn't exists before we add it. We should not
786	* trust the directory enumeration here, or maybe we should?? */
787	PKFSOBJ pMissing = kFsCacheCreateObjectW(pCache, pParent, pwcName, cwcName,
788	#ifdef KFSCACHE_CFG_SHORT_NAMES
789	NULL, 0,
790	#endif
791	KFSOBJ_TYPE_MISSING, penmError);
792	if (pMissing)
793	{
794	KBOOL fRc = kFsCacheDirAddChild(pCache, pParent, pMissing, penmError);
795	kFsCacheObjRelease(pCache, pMissing);
796	return fRc ? pMissing : NULL;
797	}
798	return NULL;
799	}
800
801	/**
802	* Worker for kFsCacheDirFindOldChild that refreshes the file ID value on an
803	* object found by name.
804	*
805	* @returns Pointer to the existing object if found, NULL if not.
806	* @param pDirRePop Repopulation data.
807	* @param pCur The object to check the names of.
808	* @param idFile The file ID.
809	*/
810	static PKFSOBJ kFsCacheDirRefreshOldChildFileId(PKFSDIRREPOP pDirRePop, PKFSOBJ pCur, KI64 idFile)
811	{
812	KFSCACHE_LOG(("Refreshing %s/%s/ - %s changed file ID from %#llx -> %#llx...\n",
813	pCur->pParent->Obj.pParent->Obj.pszName, pCur->pParent->Obj.pszName, pCur->pszName,
814	pCur->Stats.st_ino, idFile));
815	pCur->Stats.st_ino = idFile;
816	/** @todo inform user data items... */
817	return pCur;
818	}
819
820
821	/**
822	* Worker for kFsCacheDirFindOldChild that checks the names after an old object
823	* has been found the file ID.
824	*
825	* @returns Pointer to the existing object if found, NULL if not.
826	* @param pDirRePop Repopulation data.
827	* @param pCur The object to check the names of.
828	* @param pwcName The file name.
829	* @param cwcName The length of the filename (in wchar_t's).
830	* @param pwcShortName The short name, if present.
831	* @param cwcShortName The length of the short name (in wchar_t's).
832	*/
833	static PKFSOBJ kFsCacheDirRefreshOldChildName(PKFSDIRREPOP pDirRePop, PKFSOBJ pCur, wchar_t const *pwcName, KU32 cwcName
834	#ifdef KFSCACHE_CFG_SHORT_NAMES
835	, wchar_t const *pwcShortName, KU32 cwcShortName
836	#endif
837	)
838	{
839	/*
840	* Convert the names to ANSI first, that way we know all the lengths.
841	*/
842	char szName[KFSCACHE_CFG_MAX_ANSI_NAME];
843	int cchName = WideCharToMultiByte(CP_ACP, 0, pwcName, cwcName, szName, sizeof(szName) - 1, NULL, NULL);
844	if (cchName >= 0)
845	{
846	#ifdef KFSCACHE_CFG_SHORT_NAMES
847	char szShortName[12*3 + 1];
848	int cchShortName = 0;
849	if ( cwcShortName == 0
850	\|\| (cchShortName = WideCharToMultiByte(CP_ACP, 0, pwcShortName, cwcShortName,
851	szShortName, sizeof(szShortName) - 1, NULL, NULL)) > 0)
852	#endif
853	{
854	/*
855	* Shortening is easy for non-directory objects, for
856	* directory object we're only good when the length doesn't change
857	* on any of the components (cchParent et al).
858	*
859	* This deals with your typical xxxx.ext.tmp -> xxxx.ext renames.
860	*/
861	if ( cchName <= pCur->cchName
862	#ifdef KFSCACHE_CFG_UTF16
863	&& cwcName <= pCur->cwcName
864	#endif
865	#ifdef KFSCACHE_CFG_SHORT_NAMES
866	&& ( cchShortName == 0
867	\|\| ( cchShortName <= pCur->cchShortName
868	&& pCur->pszShortName != pCur->pszName
869	# ifdef KFSCACHE_CFG_UTF16
870	&& cwcShortName <= pCur->cwcShortName
871	&& pCur->pwszShortName != pCur->pwszName
872	# endif
873	)
874	)
875	#endif
876	)
877	{
878	if ( pCur->bObjType != KFSOBJ_TYPE_DIR
879	\|\| ( cchName == pCur->cchName
880	#ifdef KFSCACHE_CFG_UTF16
881	&& cwcName == pCur->cwcName
882	#endif
883	#ifdef KFSCACHE_CFG_SHORT_NAMES
884	&& ( cchShortName == 0
885	\|\| ( cchShortName == pCur->cchShortName
886	# ifdef KFSCACHE_CFG_UTF16
887	&& cwcShortName == pCur->cwcShortName
888	)
889	# endif
890	)
891	#endif
892	)
893	)
894	{
895	KFSCACHE_LOG(("Refreshing %ls - name changed to '%.ls'\n", pCur->pwszName, cwcName, cwcName, pwcName));
896	(char )kHlpMemPCopy((void *)pCur->pszName, szName, cchName) = '\0';
897	pCur->cchName = cchName;
898	#ifdef KFSCACHE_CFG_UTF16
899	(wchar_t )kHlpMemPCopy((void )pCur->pwszName, pwcName, cwcName sizeof(wchar_t)) = '\0';
900	pCur->cwcName = cwcName;
901	#endif
902	#ifdef KFSCACHE_CFG_SHORT_NAMES
903	(char )kHlpMemPCopy((void *)pCur->pszShortName, szShortName, cchShortName) = '\0';
904	pCur->cchShortName = cchShortName;
905	# ifdef KFSCACHE_CFG_UTF16
906	(wchar_t )kHlpMemPCopy((void )pCur->pwszShortName, pwcShortName, cwcShortName sizeof(wchar_t)) = '\0';
907	pCur->cwcShortName = cwcShortName;
908	# endif
909	#endif
910	return pCur;
911	}
912	}
913	}
914	}
915
916
917	fprintf(stderr,
918	"kFsCacheDirRefreshOldChildName - not implemented!\n"
919	" Old name: %#x '%ls'\n"
920	" New name: %#x '%.ls'\n"
921	" Old short: %#x '%ls'\n"
922	" New short: %#x '%.ls'\n",
923	pCur->cwcName, pCur->pwszName,
924	cwcName, cwcName, cwcName, pwcName,
925	pCur->cwcShortName, pCur->pwszShortName,
926	cwcShortName, cwcShortName, cwcShortName, pwcShortName);
927	__debugbreak();
928	/** @todo implement this. It's not entirely straight forward, especially if
929	* the name increases! Also, it's something that may happend during
930	* individual object refresh and we might want to share code... */
931
932	return pCur;
933	}
934
935
936	/**
937	* Worker for kFsCacheDirFindOldChild that checks the names after an old object
938	* has been found the file ID.
939	*
940	* @returns Pointer to the existing object if found, NULL if not.
941	* @param pDirRePop Repopulation data.
942	* @param pCur The object to check the names of.
943	* @param pwcName The file name.
944	* @param cwcName The length of the filename (in wchar_t's).
945	* @param pwcShortName The short name, if present.
946	* @param cwcShortName The length of the short name (in wchar_t's).
947	*/
948	K_INLINE PKFSOBJ kFsCacheDirCheckOldChildName(PKFSDIRREPOP pDirRePop, PKFSOBJ pCur, wchar_t const *pwcName, KU32 cwcName
949	#ifdef KFSCACHE_CFG_SHORT_NAMES
950	, wchar_t const *pwcShortName, KU32 cwcShortName
951	#endif
952	)
953	{
954	if ( pCur->cwcName == cwcName
955	&& kHlpMemComp(pCur->pwszName, pwcName, cwcName * sizeof(wchar_t)) == 0)
956	{
957	#ifdef KFSCACHE_CFG_SHORT_NAMES
958	if (cwcShortName == 0
959	? pCur->pwszShortName == pCur->pwszName
960	\|\| ( pCur->cwcShortName == cwcName
961	&& kHlpMemComp(pCur->pwszShortName, pCur->pwszName, cwcName * sizeof(wchar_t)) == 0)
962	: pCur->cwcShortName == cwcShortName
963	&& kHlpMemComp(pCur->pwszShortName, pwcShortName, cwcShortName * sizeof(wchar_t)) == 0 )
964	#endif
965	{
966	return pCur;
967	}
968	}
969	#ifdef KFSCACHE_CFG_SHORT_NAMES
970	return kFsCacheDirRefreshOldChildName(pDirRePop, pCur, pwcName, cwcName, pwcShortName, cwcShortName);
971	#else
972	return kFsCacheDirRefreshOldChildName(pDirRePop, pCur, pwcName, cwcName);
973	#endif
974	}
975
976
977	/**
978	* Worker for kFsCachePopuplateOrRefreshDir that locates an old child object
979	* while re-populating a directory.
980	*
981	* @returns Pointer to the existing object if found, NULL if not.
982	* @param pDirRePop Repopulation data.
983	* @param idFile The file ID, 0 if none.
984	* @param pwcName The file name.
985	* @param cwcName The length of the filename (in wchar_t's).
986	* @param pwcShortName The short name, if present.
987	* @param cwcShortName The length of the short name (in wchar_t's).
988	*/
989	static PKFSOBJ kFsCacheDirFindOldChildSlow(PKFSDIRREPOP pDirRePop, KI64 idFile, wchar_t const *pwcName, KU32 cwcName
990	#ifdef KFSCACHE_CFG_SHORT_NAMES
991	, wchar_t const *pwcShortName, KU32 cwcShortName
992	#endif
993	)
994	{
995	KU32 cOldChildren = pDirRePop->cOldChildren;
996	KU32 const iNextOldChild = K_MIN(pDirRePop->iNextOldChild, cOldChildren - 1);
997	KU32 iCur;
998	KI32 cInc;
999	KI32 cDirLefts;
1000
1001	kHlpAssertReturn(cOldChildren > 0, NULL);
1002
1003	/*
1004	* Search by file ID first, if we've got one.
1005	* ASSUMES that KU32 wraps around when -1 is added to 0.
1006	*/
1007	if ( idFile != 0
1008	&& idFile != KI64_MAX
1009	&& idFile != KI64_MIN)
1010	{
1011	cInc = pDirRePop->cNextOldChildInc;
1012	kHlpAssert(cInc == -1 \|\| cInc == 1);
1013	for (cDirLefts = 2; cDirLefts > 0; cDirLefts--)
1014	{
1015	for (iCur = iNextOldChild; iCur < cOldChildren; iCur += cInc)
1016	{
1017	PKFSOBJ pCur = pDirRePop->papOldChildren[iCur];
1018	if (pCur->Stats.st_ino == idFile)
1019	{
1020	/* Remove it and check the name. */
1021	pDirRePop->cOldChildren = --cOldChildren;
1022	if (iCur < cOldChildren)
1023	pDirRePop->papOldChildren[iCur] = pDirRePop->papOldChildren[cOldChildren];
1024	else
1025	cInc = -1;
1026	pDirRePop->cNextOldChildInc = cInc;
1027	pDirRePop->iNextOldChild = iCur + cInc;
1028
1029	#ifdef KFSCACHE_CFG_SHORT_NAMES
1030	return kFsCacheDirCheckOldChildName(pDirRePop, pCur, pwcName, cwcName, pwcShortName, cwcShortName);
1031	#else
1032	return kFsCacheDirCheckOldChildName(pDirRePop, pCur, pwcName, cwcName, pwcShortName, cwcShortName);
1033	#endif
1034	}
1035	}
1036	cInc = -cInc;
1037	}
1038	}
1039
1040	/*
1041	* Search by name.
1042	* ASSUMES that KU32 wraps around when -1 is added to 0.
1043	*/
1044	cInc = pDirRePop->cNextOldChildInc;
1045	kHlpAssert(cInc == -1 \|\| cInc == 1);
1046	for (cDirLefts = 2; cDirLefts > 0; cDirLefts--)
1047	{
1048	for (iCur = iNextOldChild; iCur < cOldChildren; iCur += cInc)
1049	{
1050	PKFSOBJ pCur = pDirRePop->papOldChildren[iCur];
1051	if ( ( pCur->cwcName == cwcName
1052	&& kFsCacheIAreEqualW(pCur->pwszName, pwcName, cwcName))
1053	#ifdef KFSCACHE_CFG_SHORT_NAMES
1054	\|\| ( pCur->cwcShortName == cwcName
1055	&& pCur->pwszShortName != pCur->pwszName
1056	&& kFsCacheIAreEqualW(pCur->pwszShortName, pwcName, cwcName))
1057	#endif
1058	)
1059	{
1060	/* Do this first so the compiler can share the rest with the above file ID return. */
1061	if (pCur->Stats.st_ino == idFile)
1062	{ /* likely */ }
1063	else
1064	pCur = kFsCacheDirRefreshOldChildFileId(pDirRePop, pCur, idFile);
1065
1066	/* Remove it and check the name. */
1067	pDirRePop->cOldChildren = --cOldChildren;
1068	if (iCur < cOldChildren)
1069	pDirRePop->papOldChildren[iCur] = pDirRePop->papOldChildren[cOldChildren];
1070	else
1071	cInc = -1;
1072	pDirRePop->cNextOldChildInc = cInc;
1073	pDirRePop->iNextOldChild = iCur + cInc;
1074
1075	#ifdef KFSCACHE_CFG_SHORT_NAMES
1076	return kFsCacheDirCheckOldChildName(pDirRePop, pCur, pwcName, cwcName, pwcShortName, cwcShortName);
1077	#else
1078	return kFsCacheDirCheckOldChildName(pDirRePop, pCur, pwcName, cwcName, pwcShortName, cwcShortName);
1079	#endif
1080	}
1081	}
1082	cInc = -cInc;
1083	}
1084
1085	return NULL;
1086	}
1087
1088
1089
1090	/**
1091	* Worker for kFsCachePopuplateOrRefreshDir that locates an old child object
1092	* while re-populating a directory.
1093	*
1094	* @returns Pointer to the existing object if found, NULL if not.
1095	* @param pDirRePop Repopulation data.
1096	* @param idFile The file ID, 0 if none.
1097	* @param pwcName The file name.
1098	* @param cwcName The length of the filename (in wchar_t's).
1099	* @param pwcShortName The short name, if present.
1100	* @param cwcShortName The length of the short name (in wchar_t's).
1101	*/
1102	K_INLINE PKFSOBJ kFsCacheDirFindOldChild(PKFSDIRREPOP pDirRePop, KI64 idFile, wchar_t const *pwcName, KU32 cwcName
1103	#ifdef KFSCACHE_CFG_SHORT_NAMES
1104	, wchar_t const *pwcShortName, KU32 cwcShortName
1105	#endif
1106	)
1107	{
1108	/*
1109	* We only check the iNextOldChild element here, hoping that the compiler
1110	* will actually inline this code, letting the slow version of the function
1111	* do the rest.
1112	*/
1113	KU32 cOldChildren = pDirRePop->cOldChildren;
1114	if (cOldChildren > 0)
1115	{
1116	KU32 const iNextOldChild = K_MIN(pDirRePop->iNextOldChild, cOldChildren);
1117	PKFSOBJ pCur = pDirRePop->papOldChildren[iNextOldChild];
1118
1119	if ( pCur->Stats.st_ino == idFile
1120	&& idFile != 0
1121	&& idFile != KI64_MAX
1122	&& idFile != KI64_MIN)
1123	pCur = kFsCacheDirCheckOldChildName(pDirRePop, pCur, pwcName, cwcName, pwcShortName, cwcShortName);
1124	else if ( pCur->cwcName == cwcName
1125	&& kHlpMemComp(pCur->pwszName, pwcName, cwcName * sizeof(wchar_t)) == 0)
1126	{
1127	if (pCur->Stats.st_ino == idFile)
1128	{ /* likely */ }
1129	else
1130	pCur = kFsCacheDirRefreshOldChildFileId(pDirRePop, pCur, idFile);
1131
1132	#ifdef KFSCACHE_CFG_SHORT_NAMES
1133	if (cwcShortName == 0
1134	? pCur->pwszShortName == pCur->pwszName
1135	\|\| ( pCur->cwcShortName == cwcName
1136	&& kHlpMemComp(pCur->pwszShortName, pCur->pwszName, cwcName * sizeof(wchar_t)) == 0)
1137	: pCur->cwcShortName == cwcShortName
1138	&& kHlpMemComp(pCur->pwszShortName, pwcShortName, cwcShortName * sizeof(wchar_t)) == 0 )
1139	{ /* likely */ }
1140	else
1141	pCur = kFsCacheDirRefreshOldChildName(pDirRePop, pCur, pwcName, cwcName, pwcShortName, cwcShortName);
1142	#endif
1143	}
1144	else
1145	pCur = NULL;
1146	if (pCur)
1147	{
1148	/*
1149	* Got a match. Remove the child from the array, replacing it with
1150	* the last element. (This means we're reversing the second half of
1151	* the elements, which is why we need cNextOldChildInc.)
1152	*/
1153	pDirRePop->cOldChildren = --cOldChildren;
1154	if (iNextOldChild < cOldChildren)
1155	pDirRePop->papOldChildren[iNextOldChild] = pDirRePop->papOldChildren[cOldChildren];
1156	pDirRePop->iNextOldChild = iNextOldChild + pDirRePop->cNextOldChildInc;
1157	return pCur;
1158	}
1159
1160	#ifdef KFSCACHE_CFG_SHORT_NAMES
1161	return kFsCacheDirFindOldChildSlow(pDirRePop, idFile, pwcName, cwcName, pwcShortName, cwcShortName);
1162	#else
1163	return kFsCacheDirFindOldChildSlow(pDirRePop, idFile, pwcName, cwcName);
1164	#endif
1165	}
1166
1167	return NULL;
1168	}
1169
1170
1171
1172	/**
1173	* Does the initial directory populating or refreshes it if it has been
1174	* invalidated.
1175	*
1176	* This assumes the parent directory is opened.
1177	*
1178	* @returns K_TRUE on success, K_FALSE on error.
1179	* @param pCache The cache.
1180	* @param pDir The directory.
1181	* @param penmError Where to store K_FALSE explanation.
1182	*/
1183	static KBOOL kFsCachePopuplateOrRefreshDir(PKFSCACHE pCache, PKFSDIR pDir, KFSLOOKUPERROR *penmError)
1184	{
1185	KBOOL fRefreshing = K_FALSE;
1186	KFSDIRREPOP DirRePop = { NULL, 0, 0, 0, NULL };
1187	MY_UNICODE_STRING UniStrStar = { 1 * sizeof(wchar_t), 2 * sizeof(wchar_t), L"*" };
1188
1189	/** @todo May have to make this more flexible wrt information classes since
1190	* older windows versions (XP, w2K) might not correctly support the
1191	* ones with file ID on all file systems. */
1192	#ifdef KFSCACHE_CFG_SHORT_NAMES
1193	MY_FILE_INFORMATION_CLASS const enmInfoClassWithId = MyFileIdBothDirectoryInformation;
1194	MY_FILE_INFORMATION_CLASS enmInfoClass = MyFileIdBothDirectoryInformation;
1195	#else
1196	MY_FILE_INFORMATION_CLASS const enmInfoClassWithId = MyFileIdFullDirectoryInformation;
1197	MY_FILE_INFORMATION_CLASS enmInfoClass = MyFileIdFullDirectoryInformation;
1198	#endif
1199	MY_NTSTATUS rcNt;
1200	MY_IO_STATUS_BLOCK Ios;
1201	union
1202	{
1203	/* Include the structures for better alignment. */
1204	MY_FILE_ID_BOTH_DIR_INFORMATION WithId;
1205	MY_FILE_ID_FULL_DIR_INFORMATION NoId;
1206	/* Buffer padding. We're using a 56KB buffer here to avoid size troubles with CIFS and such. */
1207	KU8 abBuf[56*1024];
1208	} uBuf;
1209
1210
1211	/*
1212	* Open the directory.
1213	*/
1214	if (pDir->hDir == INVALID_HANDLE_VALUE)
1215	{
1216	MY_OBJECT_ATTRIBUTES ObjAttr;
1217	MY_UNICODE_STRING UniStr;
1218
1219	kHlpAssert(!pDir->fPopulated);
1220
1221	Ios.Information = -1;
1222	Ios.u.Status = -1;
1223
1224	UniStr.Buffer = (wchar_t *)pDir->Obj.pwszName;
1225	UniStr.Length = (USHORT)(pDir->Obj.cwcName * sizeof(wchar_t));
1226	UniStr.MaximumLength = UniStr.Length + sizeof(wchar_t);
1227
1228	kHlpAssertStmtReturn(pDir->Obj.pParent, *penmError = KFSLOOKUPERROR_INTERNAL_ERROR, K_FALSE);
1229	kHlpAssertStmtReturn(pDir->Obj.pParent->hDir != INVALID_HANDLE_VALUE, *penmError = KFSLOOKUPERROR_INTERNAL_ERROR, K_FALSE);
1230	MyInitializeObjectAttributes(&ObjAttr, &UniStr, OBJ_CASE_INSENSITIVE, pDir->Obj.pParent->hDir, NULL /pSecAttr/);
1231
1232	/** @todo FILE_OPEN_REPARSE_POINT? */
1233	rcNt = g_pfnNtCreateFile(&pDir->hDir,
1234	FILE_READ_DATA \| FILE_LIST_DIRECTORY \| FILE_READ_ATTRIBUTES \| SYNCHRONIZE,
1235	&ObjAttr,
1236	&Ios,
1237	NULL, /cbFileInitialAlloc /
1238	FILE_ATTRIBUTE_NORMAL,
1239	FILE_SHARE_READ \| FILE_SHARE_WRITE \| FILE_SHARE_DELETE,
1240	FILE_OPEN,
1241	FILE_DIRECTORY_FILE \| FILE_OPEN_FOR_BACKUP_INTENT \| FILE_SYNCHRONOUS_IO_NONALERT,
1242	NULL, /pEaBuffer/
1243	0); /cbEaBuffer/
1244	if (MY_NT_SUCCESS(rcNt))
1245	{ /* likely */ }
1246	else
1247	{
1248	pDir->hDir = INVALID_HANDLE_VALUE;
1249	*penmError = KFSLOOKUPERROR_DIR_OPEN_ERROR;
1250	return K_FALSE;
1251	}
1252	}
1253	/*
1254	* When re-populating, we replace papChildren in the directory and pick
1255	* from the old one as we go along.
1256	*/
1257	else if (pDir->fPopulated)
1258	{
1259	KU32 cAllocated = K_ALIGN_Z(pDir->cChildren, 16);
1260	void pvNew = kHlpAlloc(sizeof(pDir->papChildren[0]) cAllocated);
1261	if (pvNew)
1262	{
1263	DirRePop.papOldChildren = pDir->papChildren;
1264	DirRePop.cOldChildren = pDir->cChildren;
1265	DirRePop.iNextOldChild = 0;
1266	DirRePop.cNextOldChildInc = 1;
1267	DirRePop.pCache = pCache;
1268
1269	pDir->cChildren = 0;
1270	pDir->cChildrenAllocated = cAllocated;
1271	pDir->papChildren = (PKFSOBJ *)pvNew;
1272	}
1273	else
1274	{
1275	*penmError = KFSLOOKUPERROR_OUT_OF_MEMORY;
1276	return K_FALSE;
1277	}
1278
1279	fRefreshing = K_TRUE;
1280	}
1281	if (!fRefreshing)
1282	KFSCACHE_LOG(("Populating %s...\n", pDir->Obj.pszName));
1283	else
1284	KFSCACHE_LOG(("Refreshing %s...\n", pDir->Obj.pszName));
1285
1286	/*
1287	* Enumerate the directory content.
1288	*
1289	* Note! The "*" filter is necessary because kFsCacheRefreshObj may have
1290	* previously quried a single file name and just passing NULL would
1291	* restart that single file name query.
1292	*/
1293	Ios.Information = -1;
1294	Ios.u.Status = -1;
1295	rcNt = g_pfnNtQueryDirectoryFile(pDir->hDir,
1296	NULL, /* hEvent */
1297	NULL, /* pfnApcComplete */
1298	NULL, /* pvApcCompleteCtx */
1299	&Ios,
1300	&uBuf,
1301	sizeof(uBuf),
1302	enmInfoClass,
1303	FALSE, /* fReturnSingleEntry */
1304	&UniStrStar, /* Filter / restart pos. */
1305	TRUE); /* fRestartScan */
1306	while (MY_NT_SUCCESS(rcNt))
1307	{
1308	/*
1309	* Process the entries in the buffer.
1310	*/
1311	KSIZE offBuf = 0;
1312	for (;;)
1313	{
1314	union
1315	{
1316	KU8 *pb;
1317	#ifdef KFSCACHE_CFG_SHORT_NAMES
1318	MY_FILE_ID_BOTH_DIR_INFORMATION *pWithId;
1319	MY_FILE_BOTH_DIR_INFORMATION *pNoId;
1320	#else
1321	MY_FILE_ID_FULL_DIR_INFORMATION *pWithId;
1322	MY_FILE_FULL_DIR_INFORMATION *pNoId;
1323	#endif
1324	} uPtr;
1325	PKFSOBJ pCur;
1326	KU32 offNext;
1327	KU32 cbMinCur;
1328	wchar_t *pwchFilename;
1329
1330	/* ASSUME only the FileName member differs between the two structures. */
1331	uPtr.pb = &uBuf.abBuf[offBuf];
1332	if (enmInfoClass == enmInfoClassWithId)
1333	{
1334	pwchFilename = &uPtr.pWithId->FileName[0];
1335	cbMinCur = (KU32)((uintptr_t)&uPtr.pWithId->FileName[0] - (uintptr_t)uPtr.pWithId);
1336	cbMinCur += uPtr.pNoId->FileNameLength;
1337	}
1338	else
1339	{
1340	pwchFilename = &uPtr.pNoId->FileName[0];
1341	cbMinCur = (KU32)((uintptr_t)&uPtr.pNoId->FileName[0] - (uintptr_t)uPtr.pNoId);
1342	cbMinCur += uPtr.pNoId->FileNameLength;
1343	}
1344
1345	/* We need to skip the '.' and '..' entries. */
1346	if ( *pwchFilename != '.'
1347	\|\| uPtr.pNoId->FileNameLength > 4
1348	\|\| !( uPtr.pNoId->FileNameLength == 2
1349	\|\| ( uPtr.pNoId->FileNameLength == 4
1350	&& pwchFilename[1] == '.') )
1351	)
1352	{
1353	KBOOL fRc;
1354	KU8 const bObjType = uPtr.pNoId->FileAttributes & FILE_ATTRIBUTE_DIRECTORY ? KFSOBJ_TYPE_DIR
1355	: uPtr.pNoId->FileAttributes & (FILE_ATTRIBUTE_DEVICE \| FILE_ATTRIBUTE_REPARSE_POINT)
1356	? KFSOBJ_TYPE_OTHER : KFSOBJ_TYPE_FILE;
1357
1358	/*
1359	* If refreshing, we must first see if this directory entry already
1360	* exists.
1361	*/
1362	if (!fRefreshing)
1363	pCur = NULL;
1364	else
1365	{
1366	pCur = kFsCacheDirFindOldChild(&DirRePop,
1367	enmInfoClass == enmInfoClassWithId ? uPtr.pWithId->FileId.QuadPart : 0,
1368	pwchFilename, uPtr.pWithId->FileNameLength / sizeof(wchar_t)
1369	#ifdef KFSCACHE_CFG_SHORT_NAMES
1370	, uPtr.pWithId->ShortName, uPtr.pWithId->ShortNameLength / sizeof(wchar_t)
1371	#endif
1372	);
1373	if (pCur)
1374	{
1375	if (pCur->bObjType == bObjType)
1376	{
1377	if (pCur->bObjType == KFSOBJ_TYPE_DIR)
1378	{
1379	PKFSDIR pCurDir = (PKFSDIR)pCur;
1380	if ( !pCurDir->fPopulated
1381	\|\| ( pCurDir->iLastWrite == uPtr.pWithId->LastWriteTime.QuadPart
1382	&& (pCur->fFlags & KFSOBJ_F_WORKING_DIR_MTIME) ) )
1383	{ /* kind of likely */ }
1384	else
1385	{
1386	KFSCACHE_LOG(("Refreshing %s/%s/ - %s/ needs re-populating...\n",
1387	pDir->Obj.pParent->Obj.pszName, pDir->Obj.pszName, pCur->pszName));
1388	pCurDir->fNeedRePopulating = K_TRUE;
1389	}
1390	}
1391	}
1392	else if (pCur->bObjType == KFSOBJ_TYPE_MISSING)
1393	{
1394	KFSCACHE_LOG(("Refreshing %s/%s/ - %s appeared as %u, was missing.\n",
1395	pDir->Obj.pParent->Obj.pszName, pDir->Obj.pszName, pCur->pszName, bObjType));
1396	pCur->bObjType = bObjType;
1397	}
1398	else
1399	{
1400	KFSCACHE_LOG(("Refreshing %s/%s/ - %s changed type from %u to %u! Dropping old object.\n",
1401	pDir->Obj.pParent->Obj.pszName, pDir->Obj.pszName, pCur->pszName,
1402	pCur->bObjType, bObjType));
1403	kFsCacheObjRelease(pCache, pCur);
1404	pCur = NULL;
1405	}
1406	}
1407	else
1408	KFSCACHE_LOG(("Refreshing %s/%s/ - %.ls added.\n", pDir->Obj.pParent->Obj.pszName, pDir->Obj.pszName,
1409	uPtr.pNoId->FileNameLength / sizeof(wchar_t), uPtr.pNoId->FileNameLength / sizeof(wchar_t),
1410	pwchFilename));
1411	}
1412
1413	if (!pCur)
1414	{
1415	/*
1416	* Create the entry (not linked yet).
1417	*/
1418	pCur = kFsCacheCreateObjectW(pCache, pDir, pwchFilename, uPtr.pNoId->FileNameLength / sizeof(wchar_t),
1419	#ifdef KFSCACHE_CFG_SHORT_NAMES
1420	uPtr.pNoId->ShortName, uPtr.pNoId->ShortNameLength / sizeof(wchar_t),
1421	#endif
1422	bObjType, penmError);
1423	if (!pCur)
1424	return K_FALSE;
1425	kHlpAssert(pCur->cRefs == 1);
1426	}
1427
1428	#ifdef KFSCACHE_CFG_SHORT_NAMES
1429	if (enmInfoClass == enmInfoClassWithId)
1430	birdStatFillFromFileIdBothDirInfo(&pCur->Stats, uPtr.pWithId, pCur->pszName);
1431	else
1432	birdStatFillFromFileBothDirInfo(&pCur->Stats, uPtr.pNoId, pCur->pszName);
1433	#else
1434	if (enmInfoClass == enmInfoClassWithId)
1435	birdStatFillFromFileIdFullDirInfo(&pCur->Stats, uPtr.pWithId, pCur->pszName);
1436	else
1437	birdStatFillFromFileFullDirInfo(&pCur->Stats, uPtr.pNoId, pCur->pszName);
1438	#endif
1439	pCur->Stats.st_dev = pDir->uDevNo;
1440	pCur->fHaveStats = K_TRUE;
1441
1442	/*
1443	* Add the entry to the directory.
1444	*/
1445	fRc = kFsCacheDirAddChild(pCache, pDir, pCur, penmError);
1446	kFsCacheObjRelease(pCache, pCur);
1447	if (fRc)
1448	{ /* likely */ }
1449	else
1450	{
1451	rcNt = STATUS_NO_MEMORY;
1452	break;
1453	}
1454	}
1455	/*
1456	* When seeing '.' we update the directory info.
1457	*/
1458	else if (uPtr.pNoId->FileNameLength == 2)
1459	{
1460	pDir->iLastWrite = uPtr.pNoId->LastWriteTime.QuadPart;
1461	#ifdef KFSCACHE_CFG_SHORT_NAMES
1462	if (enmInfoClass == enmInfoClassWithId)
1463	birdStatFillFromFileIdBothDirInfo(&pDir->Obj.Stats, uPtr.pWithId, pDir->Obj.pszName);
1464	else
1465	birdStatFillFromFileBothDirInfo(&pDir->Obj.Stats, uPtr.pNoId, pDir->Obj.pszName);
1466	#else
1467	if (enmInfoClass == enmInfoClassWithId)
1468	birdStatFillFromFileIdFullDirInfo(&pDir->Obj.Stats, uPtr.pWithId, pDir->Obj.pszName);
1469	else
1470	birdStatFillFromFileFullDirInfo(&pDir->Obj.Stats, uPtr.pNoId, pDir->Obj.pszName);
1471	#endif
1472	}
1473
1474	/*
1475	* Advance.
1476	*/
1477	offNext = uPtr.pNoId->NextEntryOffset;
1478	if ( offNext >= cbMinCur
1479	&& offNext < sizeof(uBuf))
1480	offBuf += offNext;
1481	else
1482	break;
1483	}
1484
1485	/*
1486	* Read the next chunk.
1487	*/
1488	rcNt = g_pfnNtQueryDirectoryFile(pDir->hDir,
1489	NULL, /* hEvent */
1490	NULL, /* pfnApcComplete */
1491	NULL, /* pvApcCompleteCtx */
1492	&Ios,
1493	&uBuf,
1494	sizeof(uBuf),
1495	enmInfoClass,
1496	FALSE, /* fReturnSingleEntry */
1497	&UniStrStar, /* Filter / restart pos. */
1498	FALSE); /* fRestartScan */
1499	}
1500
1501	if (rcNt == MY_STATUS_NO_MORE_FILES)
1502	{
1503	/*
1504	* If refreshing, add missing children objects and ditch the rest.
1505	* We ignore errors while adding missing children (lazy bird).
1506	*/
1507	if (!fRefreshing)
1508	{ /* more likely */ }
1509	else
1510	{
1511	while (DirRePop.cOldChildren > 0)
1512	{
1513	KFSLOOKUPERROR enmErrorIgn;
1514	PKFSOBJ pOldChild = DirRePop.papOldChildren[--DirRePop.cOldChildren];
1515	if (pOldChild->bObjType == KFSOBJ_TYPE_MISSING)
1516	kFsCacheDirAddChild(pCache, pDir, pOldChild, &enmErrorIgn);
1517	else
1518	{
1519	KFSCACHE_LOG(("Refreshing %s/%s/ - %s was removed.\n",
1520	pDir->Obj.pParent->Obj.pszName, pDir->Obj.pszName, pOldChild->pszName));
1521	kHlpAssert(pOldChild->bObjType != KFSOBJ_TYPE_DIR);
1522	/* Remove from hash table. */
1523	if (pOldChild->uNameHash != 0)
1524	{
1525	KU32 idx = pOldChild->uNameHash & pDir->fHashTabMask;
1526	PKFSOBJ pPrev = pDir->papHashTab[idx];
1527	if (pPrev == pOldChild)
1528	pDir->papHashTab[idx] = pOldChild->pNextNameHash;
1529	else
1530	{
1531	while (pPrev && pPrev->pNextNameHash != pOldChild)
1532	pPrev = pPrev->pNextNameHash;
1533	kHlpAssert(pPrev);
1534	if (pPrev)
1535	pPrev->pNextNameHash = pOldChild->pNextNameHash;
1536	}
1537	pOldChild->uNameHash = 0;
1538	}
1539	}
1540	kFsCacheObjRelease(pCache, pOldChild);
1541	}
1542	kHlpFree(DirRePop.papOldChildren);
1543	}
1544
1545	/*
1546	* Mark the directory as fully populated and up to date.
1547	*/
1548	pDir->fPopulated = K_TRUE;
1549	pDir->fNeedRePopulating = K_FALSE;
1550	if (pDir->Obj.uCacheGen != KFSOBJ_CACHE_GEN_IGNORE)
1551	pDir->Obj.uCacheGen = pCache->auGenerations[pDir->Obj.fFlags & KFSOBJ_F_USE_CUSTOM_GEN];
1552	return K_TRUE;
1553	}
1554
1555	/*
1556	* If we failed during refresh, add back remaining old children.
1557	*/
1558	if (!fRefreshing)
1559	{
1560	while (DirRePop.cOldChildren > 0)
1561	{
1562	KFSLOOKUPERROR enmErrorIgn;
1563	PKFSOBJ pOldChild = DirRePop.papOldChildren[--DirRePop.cOldChildren];
1564	kFsCacheDirAddChild(pCache, pDir, pOldChild, &enmErrorIgn);
1565	kFsCacheObjRelease(pCache, pOldChild);
1566	}
1567	kHlpFree(DirRePop.papOldChildren);
1568	}
1569
1570	kHlpAssertMsgFailed(("%#x\n", rcNt));
1571	*penmError = KFSLOOKUPERROR_DIR_READ_ERROR;
1572	return K_TRUE;
1573	}
1574
1575
1576	/**
1577	* Does the initial directory populating or refreshes it if it has been
1578	* invalidated.
1579	*
1580	* This assumes the parent directory is opened.
1581	*
1582	* @returns K_TRUE on success, K_FALSE on error.
1583	* @param pCache The cache.
1584	* @param pDir The directory.
1585	* @param penmError Where to store K_FALSE explanation. Optional.
1586	*/
1587	KBOOL kFsCacheDirEnsurePopuplated(PKFSCACHE pCache, PKFSDIR pDir, KFSLOOKUPERROR *penmError)
1588	{
1589	KFSLOOKUPERROR enmIgnored;
1590	if ( pDir->fPopulated
1591	&& !pDir->fNeedRePopulating
1592	&& ( pDir->Obj.uCacheGen == KFSOBJ_CACHE_GEN_IGNORE
1593	\|\| pDir->Obj.uCacheGen == pCache->auGenerations[pDir->Obj.fFlags & KFSOBJ_F_USE_CUSTOM_GEN]) )
1594	return K_TRUE;
1595	return kFsCachePopuplateOrRefreshDir(pCache, pDir, penmError ? penmError : &enmIgnored);
1596	}
1597
1598
1599	/**
1600	* Checks whether the modified timestamp differs on this directory.
1601	*
1602	* @returns K_TRUE if possibly modified, K_FALSE if definitely not modified.
1603	* @param pDir The directory..
1604	*/
1605	static KBOOL kFsCacheDirIsModified(PKFSDIR pDir)
1606	{
1607	if ( pDir->hDir != INVALID_HANDLE_VALUE
1608	&& (pDir->Obj.fFlags & KFSOBJ_F_WORKING_DIR_MTIME) )
1609	{
1610	MY_IO_STATUS_BLOCK Ios;
1611	MY_FILE_BASIC_INFORMATION BasicInfo;
1612	MY_NTSTATUS rcNt;
1613
1614	Ios.Information = -1;
1615	Ios.u.Status = -1;
1616
1617	rcNt = g_pfnNtQueryInformationFile(pDir->hDir, &Ios, &BasicInfo, sizeof(BasicInfo), MyFileBasicInformation);
1618	if (MY_NT_SUCCESS(rcNt))
1619	return BasicInfo.LastWriteTime.QuadPart != pDir->iLastWrite;
1620	}
1621	/* The cache root never changes. */
1622	else if (!pDir->Obj.pParent)
1623	return K_FALSE;
1624
1625	return K_TRUE;
1626	}
1627
1628
1629	static KBOOL kFsCacheRefreshMissing(PKFSCACHE pCache, PKFSOBJ pMissing, KFSLOOKUPERROR *penmError)
1630	{
1631	/*
1632	* If we can, we start by checking whether the parent directory
1633	* has been modified. If it has, we need to check if this entry
1634	* was added or not, most likely it wasn't added.
1635	*/
1636	if (!kFsCacheDirIsModified(pMissing->pParent))
1637	{
1638	KFSCACHE_LOG(("Parent of missing not written to %s/%s\n", pMissing->pParent->Obj.pszName, pMissing->pszName));
1639	pMissing->uCacheGen = pCache->auGenerationsMissing[pMissing->fFlags & KFSOBJ_F_USE_CUSTOM_GEN];
1640	}
1641	else
1642	{
1643	MY_UNICODE_STRING UniStr;
1644	MY_OBJECT_ATTRIBUTES ObjAttr;
1645	MY_FILE_BASIC_INFORMATION BasicInfo;
1646	MY_NTSTATUS rcNt;
1647
1648	UniStr.Buffer = (wchar_t *)pMissing->pwszName;
1649	UniStr.Length = (USHORT)(pMissing->cwcName * sizeof(wchar_t));
1650	UniStr.MaximumLength = UniStr.Length + sizeof(wchar_t);
1651
1652	kHlpAssert(pMissing->pParent->hDir != INVALID_HANDLE_VALUE);
1653	MyInitializeObjectAttributes(&ObjAttr, &UniStr, OBJ_CASE_INSENSITIVE, pMissing->pParent->hDir, NULL /pSecAttr/);
1654
1655	rcNt = g_pfnNtQueryAttributesFile(&ObjAttr, &BasicInfo);
1656	if (!MY_NT_SUCCESS(rcNt))
1657	{
1658	/*
1659	* Probably more likely that a missing node stays missing.
1660	*/
1661	pMissing->uCacheGen = pCache->auGenerationsMissing[pMissing->fFlags & KFSOBJ_F_USE_CUSTOM_GEN];
1662	KFSCACHE_LOG(("Still missing %s/%s\n", pMissing->pParent->Obj.pszName, pMissing->pszName));
1663	}
1664	else
1665	{
1666	/*
1667	* We must metamorphose this node. This is tedious business
1668	* because we need to check the file name casing. We might
1669	* just as well update the parent directory...
1670	*/
1671	KU8 const bObjType = BasicInfo.FileAttributes & FILE_ATTRIBUTE_DIRECTORY ? KFSOBJ_TYPE_DIR
1672	: BasicInfo.FileAttributes & (FILE_ATTRIBUTE_DEVICE \| FILE_ATTRIBUTE_REPARSE_POINT)
1673	? KFSOBJ_TYPE_OTHER : KFSOBJ_TYPE_FILE;
1674
1675	KFSCACHE_LOG(("Birth of %s/%s as %d with attribs %#x...\n",
1676	pMissing->pParent->Obj.pszName, pMissing->pszName, bObjType, BasicInfo.FileAttributes));
1677	pMissing->bObjType = bObjType;
1678	pMissing->uCacheGen = pCache->auGenerations[pMissing->fFlags & KFSOBJ_F_USE_CUSTOM_GEN];
1679	/**
1680	* @todo refresh missing object names when it appears.
1681	*/
1682	}
1683	}
1684
1685	return K_TRUE;
1686	}
1687
1688
1689	static KBOOL kFsCacheRefreshMissingIntermediateDir(PKFSCACHE pCache, PKFSOBJ pMissing, KFSLOOKUPERROR *penmError)
1690	{
1691	if (kFsCacheRefreshMissing(pCache, pMissing, penmError))
1692	{
1693	if ( pMissing->bObjType == KFSOBJ_TYPE_DIR
1694	\|\| pMissing->bObjType == KFSOBJ_TYPE_MISSING)
1695	return K_TRUE;
1696	*penmError = KFSLOOKUPERROR_PATH_COMP_NOT_DIR;
1697	}
1698
1699	return K_FALSE;
1700	}
1701
1702
1703	/**
1704	* Generic object refresh.
1705	*
1706	* This does not refresh the content of directories.
1707	*
1708	* @returns K_TRUE on success. K_FALSE and *penmError on failure.
1709	* @param pCache The cache.
1710	* @param pObj The object.
1711	* @param penmError Where to return error info.
1712	*/
1713	static KBOOL kFsCacheRefreshObj(PKFSCACHE pCache, PKFSOBJ pObj, KFSLOOKUPERROR *penmError)
1714	{
1715	KBOOL fRc;
1716
1717	/*
1718	* Since we generally assume nothing goes away in this cache, we only really
1719	* have a hard time with negative entries. So, missing stuff goes to
1720	* complicated land.
1721	*/
1722	if (pObj->bObjType == KFSOBJ_TYPE_MISSING)
1723	fRc = kFsCacheRefreshMissing(pCache, pObj, penmError);
1724	else
1725	{
1726	/*
1727	* This object is supposed to exist, so all we need to do is query essential
1728	* stats again. Since we've already got handles on directories, there are
1729	* two ways to go about this.
1730	*/
1731	union
1732	{
1733	MY_FILE_NETWORK_OPEN_INFORMATION FullInfo;
1734	MY_FILE_STANDARD_INFORMATION StdInfo;
1735	#ifdef KFSCACHE_CFG_SHORT_NAMES
1736	MY_FILE_ID_BOTH_DIR_INFORMATION WithId;
1737	//MY_FILE_BOTH_DIR_INFORMATION NoId;
1738	#else
1739	MY_FILE_ID_FULL_DIR_INFORMATION WithId;
1740	//MY_FILE_FULL_DIR_INFORMATION NoId;
1741	#endif
1742	KU8 abPadding[ sizeof(wchar_t) * KFSCACHE_CFG_MAX_UTF16_NAME
1743	+ sizeof(MY_FILE_ID_BOTH_DIR_INFORMATION)];
1744	} uBuf;
1745	MY_IO_STATUS_BLOCK Ios;
1746	MY_NTSTATUS rcNt;
1747	if ( pObj->bObjType != KFSOBJ_TYPE_DIR
1748	\|\| ((PKFSDIR)pObj)->hDir == INVALID_HANDLE_VALUE)
1749	{
1750	#if 1
1751	/* This always works and doesn't mess up NtQueryDirectoryFile. */
1752	MY_UNICODE_STRING UniStr;
1753	MY_OBJECT_ATTRIBUTES ObjAttr;
1754
1755	UniStr.Buffer = (wchar_t *)pObj->pwszName;
1756	UniStr.Length = (USHORT)(pObj->cwcName * sizeof(wchar_t));
1757	UniStr.MaximumLength = UniStr.Length + sizeof(wchar_t);
1758
1759	kHlpAssert(pObj->pParent->hDir != INVALID_HANDLE_VALUE);
1760	MyInitializeObjectAttributes(&ObjAttr, &UniStr, OBJ_CASE_INSENSITIVE, pObj->pParent->hDir, NULL /pSecAttr/);
1761
1762	rcNt = g_pfnNtQueryFullAttributesFile(&ObjAttr, &uBuf.FullInfo);
1763	if (MY_NT_SUCCESS(rcNt))
1764	{
1765	pObj->Stats.st_size = uBuf.FullInfo.EndOfFile.QuadPart;
1766	birdNtTimeToTimeSpec(uBuf.FullInfo.CreationTime.QuadPart, &pObj->Stats.st_birthtim);
1767	birdNtTimeToTimeSpec(uBuf.FullInfo.ChangeTime.QuadPart, &pObj->Stats.st_ctim);
1768	birdNtTimeToTimeSpec(uBuf.FullInfo.LastWriteTime.QuadPart, &pObj->Stats.st_mtim);
1769	birdNtTimeToTimeSpec(uBuf.FullInfo.LastAccessTime.QuadPart, &pObj->Stats.st_atim);
1770	pObj->Stats.st_attribs = uBuf.FullInfo.FileAttributes;
1771	pObj->Stats.st_blksize = 65536;
1772	pObj->Stats.st_blocks = (uBuf.FullInfo.AllocationSize.QuadPart + BIRD_STAT_BLOCK_SIZE - 1)
1773	/ BIRD_STAT_BLOCK_SIZE;
1774	}
1775	#else
1776	/* This alternative lets us keep the inode number up to date and
1777	detect name case changes.
1778	Update: This doesn't work on windows 7, it ignores the UniStr
1779	and continue with the "*" search. So, we're using the
1780	above query instead for the time being. */
1781	MY_UNICODE_STRING UniStr;
1782	# ifdef KFSCACHE_CFG_SHORT_NAMES
1783	MY_FILE_INFORMATION_CLASS enmInfoClass = MyFileIdBothDirectoryInformation;
1784	# else
1785	MY_FILE_INFORMATION_CLASS enmInfoClass = MyFileIdFullDirectoryInformation;
1786	# endif
1787
1788	UniStr.Buffer = (wchar_t *)pObj->pwszName;
1789	UniStr.Length = (USHORT)(pObj->cwcName * sizeof(wchar_t));
1790	UniStr.MaximumLength = UniStr.Length + sizeof(wchar_t);
1791
1792	kHlpAssert(pObj->pParent->hDir != INVALID_HANDLE_VALUE);
1793
1794	Ios.Information = -1;
1795	Ios.u.Status = -1;
1796	rcNt = g_pfnNtQueryDirectoryFile(pObj->pParent->hDir,
1797	NULL, /* hEvent */
1798	NULL, /* pfnApcComplete */
1799	NULL, /* pvApcCompleteCtx */
1800	&Ios,
1801	&uBuf,
1802	sizeof(uBuf),
1803	enmInfoClass,
1804	TRUE, /* fReturnSingleEntry */
1805	&UniStr, /* Filter / restart pos. */
1806	TRUE); /* fRestartScan */
1807
1808	if (MY_NT_SUCCESS(rcNt))
1809	{
1810	if (pObj->Stats.st_ino == uBuf.WithId.FileId.QuadPart)
1811	KFSCACHE_LOG(("Refreshing %s/%s, no ID change...\n", pObj->pParent->Obj.pszName, pObj->pszName));
1812	else if ( pObj->cwcName == uBuf.WithId.FileNameLength / sizeof(wchar_t)
1813	# ifdef KFSCACHE_CFG_SHORT_NAMES
1814	&& ( uBuf.WithId.ShortNameLength == 0
1815	? pObj->pwszName == pObj->pwszShortName
1816	\|\| ( pObj->cwcName == pObj->cwcShortName
1817	&& memcmp(pObj->pwszName, pObj->pwszShortName, pObj->cwcName * sizeof(wchar_t)) == 0)
1818	: pObj->cwcShortName == uBuf.WithId.ShortNameLength / sizeof(wchar_t)
1819	&& memcmp(pObj->pwszShortName, uBuf.WithId.ShortName, uBuf.WithId.ShortNameLength) == 0
1820	)
1821	# endif
1822	&& memcmp(pObj->pwszName, uBuf.WithId.FileName, uBuf.WithId.FileNameLength) == 0
1823	)
1824	{
1825	KFSCACHE_LOG(("Refreshing %s/%s, ID changed %#llx -> %#llx...\n",
1826	pObj->pParent->Obj.pszName, pObj->pszName, pObj->Stats.st_ino, uBuf.WithId.FileId.QuadPart));
1827	pObj->Stats.st_ino = uBuf.WithId.FileId.QuadPart;
1828	}
1829	else
1830	{
1831	KFSCACHE_LOG(("Refreshing %s/%s, ID changed %#llx -> %#llx and names too...\n",
1832	pObj->pParent->Obj.pszName, pObj->pszName, pObj->Stats.st_ino, uBuf.WithId.FileId.QuadPart));
1833	fprintf(stderr, "kFsCacheRefreshObj - ID + name change not implemented!!\n");
1834	__debugbreak();
1835	pObj->Stats.st_ino = uBuf.WithId.FileId.QuadPart;
1836	/** @todo implement as needed. */
1837	}
1838
1839	pObj->Stats.st_size = uBuf.WithId.EndOfFile.QuadPart;
1840	birdNtTimeToTimeSpec(uBuf.WithId.CreationTime.QuadPart, &pObj->Stats.st_birthtim);
1841	birdNtTimeToTimeSpec(uBuf.WithId.ChangeTime.QuadPart, &pObj->Stats.st_ctim);
1842	birdNtTimeToTimeSpec(uBuf.WithId.LastWriteTime.QuadPart, &pObj->Stats.st_mtim);
1843	birdNtTimeToTimeSpec(uBuf.WithId.LastAccessTime.QuadPart, &pObj->Stats.st_atim);
1844	pObj->Stats.st_attribs = uBuf.WithId.FileAttributes;
1845	pObj->Stats.st_blksize = 65536;
1846	pObj->Stats.st_blocks = (uBuf.WithId.AllocationSize.QuadPart + BIRD_STAT_BLOCK_SIZE - 1)
1847	/ BIRD_STAT_BLOCK_SIZE;
1848	}
1849	#endif
1850	if (MY_NT_SUCCESS(rcNt))
1851	{
1852	pObj->uCacheGen = pCache->auGenerations[pObj->fFlags & KFSOBJ_F_USE_CUSTOM_GEN];
1853	fRc = K_TRUE;
1854	}
1855	else
1856	{
1857	/* ouch! */
1858	kHlpAssertMsgFailed(("%#x\n", rcNt));
1859	fprintf(stderr, "kFsCacheRefreshObj - rcNt=%#x on non-dir - not implemented!\n", rcNt);
1860	__debugbreak();
1861	fRc = K_FALSE;
1862	}
1863	}
1864	else
1865	{
1866	/*
1867	* An open directory. Query information via the handle, the
1868	* file ID shouldn't have been able to change, so we can use
1869	* NtQueryInformationFile. Right...
1870	*/
1871	PKFSDIR pDir = (PKFSDIR)pObj;
1872	Ios.Information = -1;
1873	Ios.u.Status = -1;
1874	rcNt = g_pfnNtQueryInformationFile(pDir->hDir, &Ios, &uBuf.FullInfo, sizeof(uBuf.FullInfo),
1875	MyFileNetworkOpenInformation);
1876	if (MY_NT_SUCCESS(rcNt))
1877	rcNt = Ios.u.Status;
1878	if (MY_NT_SUCCESS(rcNt))
1879	{
1880	pObj->Stats.st_size = uBuf.FullInfo.EndOfFile.QuadPart;
1881	birdNtTimeToTimeSpec(uBuf.FullInfo.CreationTime.QuadPart, &pObj->Stats.st_birthtim);
1882	birdNtTimeToTimeSpec(uBuf.FullInfo.ChangeTime.QuadPart, &pObj->Stats.st_ctim);
1883	birdNtTimeToTimeSpec(uBuf.FullInfo.LastWriteTime.QuadPart, &pObj->Stats.st_mtim);
1884	birdNtTimeToTimeSpec(uBuf.FullInfo.LastAccessTime.QuadPart, &pObj->Stats.st_atim);
1885	pObj->Stats.st_attribs = uBuf.FullInfo.FileAttributes;
1886	pObj->Stats.st_blksize = 65536;
1887	pObj->Stats.st_blocks = (uBuf.FullInfo.AllocationSize.QuadPart + BIRD_STAT_BLOCK_SIZE - 1)
1888	/ BIRD_STAT_BLOCK_SIZE;
1889
1890	if ( pDir->iLastWrite == uBuf.FullInfo.LastWriteTime.QuadPart
1891	&& (pObj->fFlags & KFSOBJ_F_WORKING_DIR_MTIME) )
1892	KFSCACHE_LOG(("Refreshing %s/%s/ - no re-populating necessary.\n",
1893	pObj->pParent->Obj.pszName, pObj->pszName));
1894	else
1895	{
1896	KFSCACHE_LOG(("Refreshing %s/%s/ - needs re-populating...\n",
1897	pObj->pParent->Obj.pszName, pObj->pszName));
1898	pDir->fNeedRePopulating = K_TRUE;
1899	#if 0
1900	/* Refresh the link count. */
1901	rcNt = g_pfnNtQueryInformationFile(pDir->hDir, &Ios, &StdInfo, sizeof(StdInfo), FileStandardInformation);
1902	if (MY_NT_SUCCESS(rcNt))
1903	rcNt = Ios.s.Status;
1904	if (MY_NT_SUCCESS(rcNt))
1905	pObj->Stats.st_nlink = StdInfo.NumberOfLinks;
1906	#endif
1907	}
1908	}
1909	if (MY_NT_SUCCESS(rcNt))
1910	{
1911	pObj->uCacheGen = pCache->auGenerations[pObj->fFlags & KFSOBJ_F_USE_CUSTOM_GEN];
1912	fRc = K_TRUE;
1913	}
1914	else
1915	{
1916	/* ouch! */
1917	kHlpAssertMsgFailed(("%#x\n", rcNt));
1918	fprintf(stderr, "kFsCacheRefreshObj - rcNt=%#x on dir - not implemented!\n", rcNt);
1919	__debugbreak();
1920	fRc = K_FALSE;
1921	}
1922	}
1923	}
1924
1925	return fRc;
1926	}
1927
1928
1929
1930	/**
1931	* Looks up a drive letter.
1932	*
1933	* Will enter the drive if necessary.
1934	*
1935	* @returns Pointer to the root directory of the drive or an update-to-date
1936	* missing node.
1937	* @param pCache The cache.
1938	* @param chLetter The uppercased drive letter.
1939	* @param fFlags Lookup flags, KFSCACHE_LOOKUP_F_XXX.
1940	* @param penmError Where to return details as to why the lookup
1941	* failed.
1942	*/
1943	static PKFSOBJ kFsCacheLookupDrive(PKFSCACHE pCache, char chLetter, KU32 fFlags, KFSLOOKUPERROR *penmError)
1944	{
1945	KU32 const uNameHash = chLetter - 'A';
1946	PKFSOBJ pCur = pCache->RootDir.papHashTab[uNameHash];
1947
1948	KU32 cLeft;
1949	PKFSOBJ *ppCur;
1950	MY_UNICODE_STRING NtPath;
1951	wchar_t wszTmp[8];
1952	char szTmp[4];
1953
1954	/*
1955	* Custom drive letter hashing.
1956	*/
1957	kHlpAssert((uNameHash & pCache->RootDir.fHashTabMask) == uNameHash);
1958	while (pCur)
1959	{
1960	if ( pCur->uNameHash == uNameHash
1961	&& pCur->cchName == 2
1962	&& pCur->pszName[0] == chLetter
1963	&& pCur->pszName[1] == ':')
1964	{
1965	if (pCur->bObjType == KFSOBJ_TYPE_DIR)
1966	return pCur;
1967	if ( (fFlags & KFSCACHE_LOOKUP_F_NO_REFRESH)
1968	\|\| kFsCacheRefreshMissingIntermediateDir(pCache, pCur, penmError))
1969	return pCur;
1970	return NULL;
1971	}
1972	pCur = pCur->pNextNameHash;
1973	}
1974
1975	/*
1976	* Make 100% sure it's not there.
1977	*/
1978	cLeft = pCache->RootDir.cChildren;
1979	ppCur = pCache->RootDir.papChildren;
1980	while (cLeft-- > 0)
1981	{
1982	pCur = *ppCur++;
1983	if ( pCur->cchName == 2
1984	&& pCur->pszName[0] == chLetter
1985	&& pCur->pszName[1] == ':')
1986	{
1987	if (pCur->bObjType == KFSOBJ_TYPE_DIR)
1988	return pCur;
1989	kHlpAssert(pCur->bObjType == KFSOBJ_TYPE_MISSING);
1990	if ( (fFlags & KFSCACHE_LOOKUP_F_NO_REFRESH)
1991	\|\| kFsCacheRefreshMissingIntermediateDir(pCache, pCur, penmError))
1992	return pCur;
1993	return NULL;
1994	}
1995	}
1996
1997	if (fFlags & KFSCACHE_LOOKUP_F_NO_INSERT)
1998	{
1999	penmError = KFSLOOKUPERROR_PATH_COMP_NOT_FOUND; / close enough */
2000	return NULL;
2001	}
2002
2003	/*
2004	* Need to add it. We always keep the drive letters open for the benefit
2005	* of kFsCachePopuplateOrRefreshDir and others.
2006	*/
2007	wszTmp[0] = szTmp[0] = chLetter;
2008	wszTmp[1] = szTmp[1] = ':';
2009	wszTmp[2] = szTmp[2] = '\\';
2010	wszTmp[3] = '.';
2011	wszTmp[4] = '\0';
2012	szTmp[2] = '\0';
2013
2014	NtPath.Buffer = NULL;
2015	NtPath.Length = 0;
2016	NtPath.MaximumLength = 0;
2017	if (g_pfnRtlDosPathNameToNtPathName_U(wszTmp, &NtPath, NULL, NULL))
2018	{
2019	HANDLE hDir;
2020	MY_NTSTATUS rcNt;
2021	rcNt = birdOpenFileUniStr(&NtPath,
2022	FILE_READ_DATA \| FILE_LIST_DIRECTORY \| FILE_READ_ATTRIBUTES \| SYNCHRONIZE,
2023	FILE_ATTRIBUTE_NORMAL,
2024	FILE_SHARE_READ \| FILE_SHARE_WRITE \| FILE_SHARE_DELETE,
2025	FILE_OPEN,
2026	FILE_DIRECTORY_FILE \| FILE_OPEN_FOR_BACKUP_INTENT \| FILE_SYNCHRONOUS_IO_NONALERT,
2027	OBJ_CASE_INSENSITIVE,
2028	&hDir);
2029	birdFreeNtPath(&NtPath);
2030	if (MY_NT_SUCCESS(rcNt))
2031	{
2032	PKFSDIR pDir = (PKFSDIR)kFsCacheCreateObject(pCache, &pCache->RootDir, szTmp, 2, wszTmp, 2,
2033	#ifdef KFSCACHE_CFG_SHORT_NAMES
2034	NULL, 0, NULL, 0,
2035	#endif
2036	KFSOBJ_TYPE_DIR, penmError);
2037	if (pDir)
2038	{
2039	/*
2040	* We need a little bit of extra info for a drive root. These things are typically
2041	* inherited by subdirectories down the tree, so, we do it all here for till that changes.
2042	*/
2043	union
2044	{
2045	MY_FILE_FS_VOLUME_INFORMATION VolInfo;
2046	MY_FILE_FS_ATTRIBUTE_INFORMATION FsAttrInfo;
2047	char abPadding[sizeof(MY_FILE_FS_VOLUME_INFORMATION) + 512];
2048	} uBuf;
2049	MY_IO_STATUS_BLOCK Ios;
2050	KBOOL fRc;
2051
2052	kHlpAssert(pDir->hDir == INVALID_HANDLE_VALUE);
2053	pDir->hDir = hDir;
2054
2055	if (birdStatHandle(hDir, &pDir->Obj.Stats, pDir->Obj.pszName) == 0)
2056	{
2057	pDir->Obj.fHaveStats = K_TRUE;
2058	pDir->uDevNo = pDir->Obj.Stats.st_dev;
2059	}
2060	else
2061	{
2062	/* Just in case. */
2063	pDir->Obj.fHaveStats = K_FALSE;
2064	rcNt = birdQueryVolumeDeviceNumber(hDir, &uBuf.VolInfo, sizeof(uBuf), &pDir->uDevNo);
2065	kHlpAssertMsg(MY_NT_SUCCESS(rcNt), ("%#x\n", rcNt));
2066	}
2067
2068	/* Get the file system. */
2069	pDir->Obj.fFlags &= ~(KFSOBJ_F_NTFS \| KFSOBJ_F_WORKING_DIR_MTIME);
2070	Ios.Information = -1;
2071	Ios.u.Status = -1;
2072	rcNt = g_pfnNtQueryVolumeInformationFile(hDir, &Ios, &uBuf.FsAttrInfo, sizeof(uBuf),
2073	MyFileFsAttributeInformation);
2074	if (MY_NT_SUCCESS(rcNt))
2075	rcNt = Ios.u.Status;
2076	if (MY_NT_SUCCESS(rcNt))
2077	{
2078	if ( uBuf.FsAttrInfo.FileSystemName[0] == 'N'
2079	&& uBuf.FsAttrInfo.FileSystemName[1] == 'T'
2080	&& uBuf.FsAttrInfo.FileSystemName[2] == 'F'
2081	&& uBuf.FsAttrInfo.FileSystemName[3] == 'S'
2082	&& uBuf.FsAttrInfo.FileSystemName[4] == '\0')
2083	{
2084	DWORD dwDriveType = GetDriveTypeW(wszTmp);
2085	if ( dwDriveType == DRIVE_FIXED
2086	\|\| dwDriveType == DRIVE_RAMDISK)
2087	pDir->Obj.fFlags \|= KFSOBJ_F_NTFS \| KFSOBJ_F_WORKING_DIR_MTIME;
2088	}
2089	}
2090
2091	/*
2092	* Link the new drive letter into the root dir.
2093	*/
2094	fRc = kFsCacheDirAddChild(pCache, &pCache->RootDir, &pDir->Obj, penmError);
2095	kFsCacheObjRelease(pCache, &pDir->Obj);
2096	if (fRc)
2097	{
2098	pDir->Obj.pNextNameHash = pCache->RootDir.papHashTab[uNameHash];
2099	pCache->RootDir.papHashTab[uNameHash] = &pDir->Obj;
2100	return &pDir->Obj;
2101	}
2102	return NULL;
2103	}
2104
2105	g_pfnNtClose(hDir);
2106	return NULL;
2107	}
2108
2109	/* Assume it doesn't exist if this happens... This may be a little to
2110	restrictive wrt status code checks. */
2111	kHlpAssertMsgStmtReturn( rcNt == MY_STATUS_OBJECT_NAME_NOT_FOUND
2112	\|\| rcNt == MY_STATUS_OBJECT_PATH_NOT_FOUND
2113	\|\| rcNt == MY_STATUS_OBJECT_PATH_INVALID
2114	\|\| rcNt == MY_STATUS_OBJECT_PATH_SYNTAX_BAD,
2115	("%#x\n", rcNt),
2116	*penmError = KFSLOOKUPERROR_DIR_OPEN_ERROR,
2117	NULL);
2118	}
2119	else
2120	{
2121	kHlpAssertFailed();
2122	*penmError = KFSLOOKUPERROR_OUT_OF_MEMORY;
2123	return NULL;
2124	}
2125
2126	/*
2127	* Maybe create a missing entry.
2128	*/
2129	if (pCache->fFlags & KFSCACHE_F_MISSING_OBJECTS)
2130	{
2131	PKFSOBJ pMissing = kFsCacheCreateObject(pCache, &pCache->RootDir, szTmp, 2, wszTmp, 2,
2132	#ifdef KFSCACHE_CFG_SHORT_NAMES
2133	NULL, 0, NULL, 0,
2134	#endif
2135	KFSOBJ_TYPE_MISSING, penmError);
2136	if (pMissing)
2137	{
2138	KBOOL fRc = kFsCacheDirAddChild(pCache, &pCache->RootDir, pMissing, penmError);
2139	kFsCacheObjRelease(pCache, pMissing);
2140	return fRc ? pMissing : NULL;
2141	}
2142	}
2143	else
2144	{
2145	/** @todo this isn't necessary correct for a root spec. */
2146	*penmError = KFSLOOKUPERROR_PATH_COMP_NOT_FOUND;
2147	}
2148	return NULL;
2149	}
2150
2151
2152	/**
2153	* Slow path that allocates the child hash table and enters the given one.
2154	*
2155	* Allocation fialures are ignored.
2156	*
2157	* @param pCache The cache (for stats).
2158	* @param pDir The directory.
2159	* @param uNameHash The name hash to enter @a pChild under.
2160	* @param pChild The child to enter into the hash table.
2161	*/
2162	static void kFsCacheDirAllocHashTabAndEnterChild(PKFSCACHE pCache, PKFSDIR pDir, KU32 uNameHash, PKFSOBJ pChild)
2163	{
2164	if (uNameHash != 0) /* paranoia ^ 4! */
2165	{
2166	/*
2167	* Double the current number of children and round up to a multiple of
2168	* two so we can avoid division.
2169	*/
2170	KU32 cbHashTab;
2171	KU32 cEntries;
2172	kHlpAssert(pDir->cChildren > 0);
2173	if (pDir->cChildren <= KU32_MAX / 4)
2174	{
2175	#if defined(_MSC_VER) && 1
2176	KU32 cEntriesRaw = pDir->cChildren * 2;
2177	KU32 cEntriesShift;
2178	kHlpAssert(sizeof(cEntries) == (unsigned long));
2179	if (_BitScanReverse(&cEntriesShift, cEntriesRaw))
2180	{
2181	if ( K_BIT32(cEntriesShift) < cEntriesRaw
2182	&& cEntriesShift < 31U)
2183	cEntriesShift++;
2184	cEntries = K_BIT32(cEntriesShift);
2185	}
2186	else
2187	{
2188	kHlpAssertFailed();
2189	cEntries = KU32_MAX / 2 + 1;
2190	}
2191	#else
2192	cEntries = pDir->cChildren * 2 - 1;
2193	cEntries \|= cEntries >> 1;
2194	cEntries \|= cEntries >> 2;
2195	cEntries \|= cEntries >> 4;
2196	cEntries \|= cEntries >> 8;
2197	cEntries \|= cEntries >> 16;
2198	cEntries++;
2199	#endif
2200	}
2201	else
2202	cEntries = KU32_MAX / 2 + 1;
2203	kHlpAssert((cEntries & (cEntries - 1)) == 0);
2204
2205	cbHashTab = cEntries * sizeof(pDir->papHashTab[0]);
2206	pDir->papHashTab = (PKFSOBJ *)kHlpAllocZ(cbHashTab);
2207	if (pDir->papHashTab)
2208	{
2209	KU32 idx;
2210	pDir->fHashTabMask = cEntries - 1;
2211	pCache->cbObjects += cbHashTab;
2212	pCache->cChildHashTabs++;
2213	pCache->cChildHashEntriesTotal += cEntries;
2214
2215	/*
2216	* Insert it.
2217	*/
2218	pChild->uNameHash = uNameHash;
2219	idx = uNameHash & (pDir->fHashTabMask);
2220	pChild->pNextNameHash = pDir->papHashTab[idx];
2221	pDir->papHashTab[idx] = pChild;
2222	pCache->cChildHashed++;
2223	}
2224	}
2225	}
2226
2227
2228	/**
2229	* Look up a child node, ANSI version.
2230	*
2231	* @returns Pointer to the child if found, NULL if not.
2232	* @param pCache The cache.
2233	* @param pParent The parent directory to search.
2234	* @param pchName The child name to search for (not terminated).
2235	* @param cchName The length of the child name.
2236	*/
2237	static PKFSOBJ kFsCacheFindChildA(PKFSCACHE pCache, PKFSDIR pParent, const char *pchName, KU32 cchName)
2238	{
2239	/*
2240	* Check for '.' first ('..' won't appear).
2241	*/
2242	if (cchName != 1 \|\| *pchName != '.')
2243	{
2244	PKFSOBJ *ppCur;
2245	KU32 cLeft;
2246	KU32 uNameHash;
2247
2248	/*
2249	* Do hash table lookup.
2250	*
2251	* This caches previous lookups, which should be useful when looking up
2252	* intermediate directories at least.
2253	*/
2254	if (pParent->papHashTab != NULL)
2255	{
2256	PKFSOBJ pCur;
2257	uNameHash = kFsCacheStrHashN(pchName, cchName);
2258	pCur = pParent->papHashTab[uNameHash & pParent->fHashTabMask];
2259	while (pCur)
2260	{
2261	if ( pCur->uNameHash == uNameHash
2262	&& ( ( pCur->cchName == cchName
2263	&& _mbsnicmp(pCur->pszName, pchName, cchName) == 0)
2264	#ifdef KFSCACHE_CFG_SHORT_NAMES
2265	\|\| ( pCur->cchShortName == cchName
2266	&& pCur->pszShortName != pCur->pszName
2267	&& _mbsnicmp(pCur->pszShortName, pchName, cchName) == 0)
2268	#endif
2269	)
2270	)
2271	{
2272	pCache->cChildHashHits++;
2273	pCache->cChildSearches++;
2274	return pCur;
2275	}
2276	pCur = pCur->pNextNameHash;
2277	}
2278	}
2279	else
2280	uNameHash = 0;
2281
2282	/*
2283	* Do linear search.
2284	*/
2285	cLeft = pParent->cChildren;
2286	ppCur = pParent->papChildren;
2287	while (cLeft-- > 0)
2288	{
2289	PKFSOBJ pCur = *ppCur++;
2290	if ( ( pCur->cchName == cchName
2291	&& _mbsnicmp(pCur->pszName, pchName, cchName) == 0)
2292	#ifdef KFSCACHE_CFG_SHORT_NAMES
2293	\|\| ( pCur->cchShortName == cchName
2294	&& pCur->pszShortName != pCur->pszName
2295	&& _mbsnicmp(pCur->pszShortName, pchName, cchName) == 0)
2296	#endif
2297	)
2298	{
2299	/*
2300	* Consider entering it into the parent hash table.
2301	* Note! We hash the input, not the name we found.
2302	*/
2303	if ( pCur->uNameHash == 0
2304	&& pParent->cChildren >= 2)
2305	{
2306	if (pParent->papHashTab)
2307	{
2308	if (uNameHash != 0)
2309	{
2310	KU32 idxNameHash = uNameHash & pParent->fHashTabMask;
2311	pCur->uNameHash = uNameHash;
2312	pCur->pNextNameHash = pParent->papHashTab[idxNameHash];
2313	pParent->papHashTab[idxNameHash] = pCur;
2314	if (pCur->pNextNameHash)
2315	pCache->cChildHashCollisions++;
2316	pCache->cChildHashed++;
2317	}
2318	}
2319	else
2320	kFsCacheDirAllocHashTabAndEnterChild(pCache, pParent, kFsCacheStrHashN(pchName, cchName), pCur);
2321	}
2322
2323	pCache->cChildSearches++;
2324	return pCur;
2325	}
2326	}
2327
2328	pCache->cChildSearches++;
2329	return NULL;
2330	}
2331	return &pParent->Obj;
2332	}
2333
2334
2335	/**
2336	* Look up a child node, UTF-16 version.
2337	*
2338	* @returns Pointer to the child if found, NULL if not.
2339	* @param pCache The cache.
2340	* @param pParent The parent directory to search.
2341	* @param pwcName The child name to search for (not terminated).
2342	* @param cwcName The length of the child name (in wchar_t's).
2343	*/
2344	static PKFSOBJ kFsCacheFindChildW(PKFSCACHE pCache, PKFSDIR pParent, const wchar_t *pwcName, KU32 cwcName)
2345	{
2346	/*
2347	* Check for '.' first ('..' won't appear).
2348	*/
2349	if (cwcName != 1 \|\| *pwcName != '.')
2350	{
2351	PKFSOBJ *ppCur;
2352	KU32 cLeft;
2353	KU32 uNameHash;
2354
2355	/*
2356	* Do hash table lookup.
2357	*
2358	* This caches previous lookups, which should be useful when looking up
2359	* intermediate directories at least.
2360	*/
2361	if (pParent->papHashTab != NULL)
2362	{
2363	PKFSOBJ pCur;
2364	uNameHash = kFsCacheUtf16HashN(pwcName, cwcName);
2365	pCur = pParent->papHashTab[uNameHash & pParent->fHashTabMask];
2366	while (pCur)
2367	{
2368	if ( pCur->uNameHash == uNameHash
2369	&& ( ( pCur->cwcName == cwcName
2370	&& kFsCacheIAreEqualW(pCur->pwszName, pwcName, cwcName))
2371	#ifdef KFSCACHE_CFG_SHORT_NAMES
2372	\|\| ( pCur->cwcShortName == cwcName
2373	&& pCur->pwszShortName != pCur->pwszName
2374	&& kFsCacheIAreEqualW(pCur->pwszShortName, pwcName, cwcName))
2375	#endif
2376	)
2377	)
2378	{
2379	pCache->cChildHashHits++;
2380	pCache->cChildSearches++;
2381	return pCur;
2382	}
2383	pCur = pCur->pNextNameHash;
2384	}
2385	}
2386	else
2387	uNameHash = 0;
2388
2389	/*
2390	* Do linear search.
2391	*/
2392	cLeft = pParent->cChildren;
2393	ppCur = pParent->papChildren;
2394	while (cLeft-- > 0)
2395	{
2396	PKFSOBJ pCur = *ppCur++;
2397	if ( ( pCur->cwcName == cwcName
2398	&& kFsCacheIAreEqualW(pCur->pwszName, pwcName, cwcName))
2399	#ifdef KFSCACHE_CFG_SHORT_NAMES
2400	\|\| ( pCur->cwcShortName == cwcName
2401	&& pCur->pwszShortName != pCur->pwszName
2402	&& kFsCacheIAreEqualW(pCur->pwszShortName, pwcName, cwcName))
2403	#endif
2404	)
2405	{
2406	/*
2407	* Consider entering it into the parent hash table.
2408	* Note! We hash the input, not the name we found.
2409	*/
2410	if ( pCur->uNameHash == 0
2411	&& pParent->cChildren >= 4)
2412	{
2413	if (pParent->papHashTab)
2414	{
2415	if (uNameHash != 0)
2416	{
2417	KU32 idxNameHash = uNameHash & pParent->fHashTabMask;
2418	pCur->uNameHash = uNameHash;
2419	pCur->pNextNameHash = pParent->papHashTab[idxNameHash];
2420	pParent->papHashTab[idxNameHash] = pCur;
2421	if (pCur->pNextNameHash)
2422	pCache->cChildHashCollisions++;
2423	pCache->cChildHashed++;
2424	}
2425	}
2426	else
2427	kFsCacheDirAllocHashTabAndEnterChild(pCache, pParent, kFsCacheUtf16HashN(pwcName, cwcName), pCur);
2428	}
2429
2430	pCache->cChildSearches++;
2431	return pCur;
2432	}
2433	}
2434	pCache->cChildSearches++;
2435	return NULL;
2436	}
2437	return &pParent->Obj;
2438	}
2439
2440
2441	/**
2442	* Looks up a UNC share, ANSI version.
2443	*
2444	* We keep both the server and share in the root directory entry. This means we
2445	* have to clean up the entry name before we can insert it.
2446	*
2447	* @returns Pointer to the share root directory or an update-to-date missing
2448	* node.
2449	* @param pCache The cache.
2450	* @param pszPath The path.
2451	* @param fFlags Lookup flags, KFSCACHE_LOOKUP_F_XXX.
2452	* @param poff Where to return the root dire.
2453	* @param penmError Where to return details as to why the lookup
2454	* failed.
2455	*/
2456	static PKFSOBJ kFsCacheLookupUncShareA(PKFSCACHE pCache, const char *pszPath, KU32 fFlags,
2457	KU32 poff, KFSLOOKUPERROR penmError)
2458	{
2459	#if 0 /* later */
2460	KU32 offStartServer;
2461	KU32 offEndServer;
2462	KU32 offStartShare;
2463
2464	KU32 offEnd = 2;
2465	while (IS_SLASH(pszPath[offEnd]))
2466	offEnd++;
2467
2468	offStartServer = offEnd;
2469	while ( (ch = pszPath[offEnd]) != '\0'
2470	&& !IS_SLASH(ch))
2471	offEnd++;
2472	offEndServer = offEnd;
2473
2474	if (ch != '\0')
2475	{ /* likely */ }
2476	else
2477	{
2478	*penmError = KFSLOOKUPERROR_NOT_FOUND;
2479	return NULL;
2480	}
2481
2482	while (IS_SLASH(pszPath[offEnd]))
2483	offEnd++;
2484	offStartServer = offEnd;
2485	while ( (ch = pszPath[offEnd]) != '\0'
2486	&& !IS_SLASH(ch))
2487	offEnd++;
2488	#endif
2489	*penmError = KFSLOOKUPERROR_UNSUPPORTED;
2490	return NULL;
2491	}
2492
2493
2494	/**
2495	* Looks up a UNC share, UTF-16 version.
2496	*
2497	* We keep both the server and share in the root directory entry. This means we
2498	* have to clean up the entry name before we can insert it.
2499	*
2500	* @returns Pointer to the share root directory or an update-to-date missing
2501	* node.
2502	* @param pCache The cache.
2503	* @param pwszPath The path.
2504	* @param fFlags Lookup flags, KFSCACHE_LOOKUP_F_XXX.
2505	* @param poff Where to return the root dire.
2506	* @param penmError Where to return details as to why the lookup
2507	* failed.
2508	*/
2509	static PKFSOBJ kFsCacheLookupUncShareW(PKFSCACHE pCache, const wchar_t *pwszPath, KU32 fFlags,
2510	KU32 poff, KFSLOOKUPERROR penmError)
2511	{
2512	#if 0 /* later */
2513	KU32 offStartServer;
2514	KU32 offEndServer;
2515	KU32 offStartShare;
2516
2517	KU32 offEnd = 2;
2518	while (IS_SLASH(pwszPath[offEnd]))
2519	offEnd++;
2520
2521	offStartServer = offEnd;
2522	while ( (ch = pwszPath[offEnd]) != '\0'
2523	&& !IS_SLASH(ch))
2524	offEnd++;
2525	offEndServer = offEnd;
2526
2527	if (ch != '\0')
2528	{ /* likely */ }
2529	else
2530	{
2531	*penmError = KFSLOOKUPERROR_NOT_FOUND;
2532	return NULL;
2533	}
2534
2535	while (IS_SLASH(pwszPath[offEnd]))
2536	offEnd++;
2537	offStartServer = offEnd;
2538	while ( (ch = pwszPath[offEnd]) != '\0'
2539	&& !IS_SLASH(ch))
2540	offEnd++;
2541	#endif
2542	*penmError = KFSLOOKUPERROR_UNSUPPORTED;
2543	return NULL;
2544	}
2545
2546
2547	/**
2548	* Walks an full path relative to the given directory, ANSI version.
2549	*
2550	* This will create any missing nodes while walking.
2551	*
2552	* The caller will have to do the path hash table insertion of the result.
2553	*
2554	* @returns Pointer to the tree node corresponding to @a pszPath.
2555	* NULL on lookup failure, see @a penmError for details.
2556	* @param pCache The cache.
2557	* @param pParent The directory to start the lookup in.
2558	* @param pszPath The path to walk.
2559	* @param cchPath The length of the path.
2560	* @param fFlags Lookup flags, KFSCACHE_LOOKUP_F_XXX.
2561	* @param penmError Where to return details as to why the lookup
2562	* failed.
2563	* @param ppLastAncestor Where to return the last parent element found
2564	* (referenced) in case of error an path/file not
2565	* found problem. Optional.
2566	*/
2567	PKFSOBJ kFsCacheLookupRelativeToDirA(PKFSCACHE pCache, PKFSDIR pParent, const char *pszPath, KU32 cchPath, KU32 fFlags,
2568	KFSLOOKUPERROR penmError, PKFSOBJ ppLastAncestor)
2569	{
2570	/*
2571	* Walk loop.
2572	*/
2573	KU32 off = 0;
2574	if (ppLastAncestor)
2575	*ppLastAncestor = NULL;
2576	for (;;)
2577	{
2578	PKFSOBJ pChild;
2579
2580	/*
2581	* Find the end of the component, counting trailing slashes.
2582	*/
2583	char ch;
2584	KU32 cchSlashes = 0;
2585	KU32 offEnd = off + 1;
2586	while ((ch = pszPath[offEnd]) != '\0')
2587	{
2588	if (!IS_SLASH(ch))
2589	offEnd++;
2590	else
2591	{
2592	do
2593	cchSlashes++;
2594	while (IS_SLASH(pszPath[offEnd + cchSlashes]));
2595	break;
2596	}
2597	}
2598
2599	/*
2600	* Do we need to populate or refresh this directory first?
2601	*/
2602	if ( !pParent->fNeedRePopulating
2603	&& pParent->fPopulated
2604	&& ( pParent->Obj.uCacheGen == KFSOBJ_CACHE_GEN_IGNORE
2605	\|\| pParent->Obj.uCacheGen == pCache->auGenerations[pParent->Obj.fFlags & KFSOBJ_F_USE_CUSTOM_GEN]) )
2606	{ /* likely */ }
2607	else if ( (fFlags & (KFSCACHE_LOOKUP_F_NO_INSERT \| fFlags & KFSCACHE_LOOKUP_F_NO_REFRESH))
2608	\|\| kFsCachePopuplateOrRefreshDir(pCache, pParent, penmError))
2609	{ /* likely */ }
2610	else
2611	return NULL;
2612
2613	/*
2614	* Search the current node for the name.
2615	*
2616	* If we don't find it, we may insert a missing node depending on
2617	* the cache configuration.
2618	*/
2619	pChild = kFsCacheFindChildA(pCache, pParent, &pszPath[off], offEnd - off);
2620	if (pChild != NULL)
2621	{ /* probably likely */ }
2622	else
2623	{
2624	if ( (pCache->fFlags & KFSCACHE_F_MISSING_OBJECTS)
2625	&& !(fFlags & KFSCACHE_LOOKUP_F_NO_INSERT))
2626	pChild = kFsCacheCreateMissingA(pCache, pParent, &pszPath[off], offEnd - off, penmError);
2627	if (cchSlashes == 0 \|\| offEnd + cchSlashes >= cchPath)
2628	{
2629	if (pChild)
2630	return kFsCacheObjRetainInternal(pChild);
2631	*penmError = KFSLOOKUPERROR_NOT_FOUND;
2632	}
2633	else
2634	*penmError = KFSLOOKUPERROR_PATH_COMP_NOT_FOUND;
2635	if (ppLastAncestor)
2636	*ppLastAncestor = kFsCacheObjRetainInternal(&pParent->Obj);
2637	return NULL;
2638	}
2639
2640	/* Advance off and check if we're done already. */
2641	off = offEnd + cchSlashes;
2642	if ( cchSlashes == 0
2643	\|\| off >= cchPath)
2644	{
2645	if ( pChild->bObjType != KFSOBJ_TYPE_MISSING
2646	\|\| pChild->uCacheGen == KFSOBJ_CACHE_GEN_IGNORE
2647	\|\| pChild->uCacheGen == pCache->auGenerationsMissing[pChild->fFlags & KFSOBJ_F_USE_CUSTOM_GEN]
2648	\|\| (fFlags & KFSCACHE_LOOKUP_F_NO_REFRESH)
2649	\|\| kFsCacheRefreshMissing(pCache, pChild, penmError) )
2650	{ /* likely */ }
2651	else
2652	return NULL;
2653	return kFsCacheObjRetainInternal(pChild);
2654	}
2655
2656	/*
2657	* Check that it's a directory. If a missing entry, we may have to
2658	* refresh it and re-examin it.
2659	*/
2660	if (pChild->bObjType == KFSOBJ_TYPE_DIR)
2661	pParent = (PKFSDIR)pChild;
2662	else if (pChild->bObjType != KFSOBJ_TYPE_MISSING)
2663	{
2664	*penmError = KFSLOOKUPERROR_PATH_COMP_NOT_DIR;
2665	if (ppLastAncestor)
2666	*ppLastAncestor = kFsCacheObjRetainInternal(&pParent->Obj);
2667	return NULL;
2668	}
2669	else if ( pChild->uCacheGen == KFSOBJ_CACHE_GEN_IGNORE
2670	\|\| pChild->uCacheGen == pCache->auGenerationsMissing[pChild->fFlags & KFSOBJ_F_USE_CUSTOM_GEN]
2671	\|\| (fFlags & KFSCACHE_LOOKUP_F_NO_REFRESH))
2672	{
2673	*penmError = KFSLOOKUPERROR_PATH_COMP_NOT_FOUND;
2674	if (ppLastAncestor)
2675	*ppLastAncestor = kFsCacheObjRetainInternal(&pParent->Obj);
2676	return NULL;
2677	}
2678	else if (kFsCacheRefreshMissingIntermediateDir(pCache, pChild, penmError))
2679	pParent = (PKFSDIR)pChild;
2680	else
2681	{
2682	if (ppLastAncestor)
2683	*ppLastAncestor = kFsCacheObjRetainInternal(&pParent->Obj);
2684	return NULL;
2685	}
2686	}
2687
2688	return NULL;
2689
2690	}
2691
2692
2693	/**
2694	* Walks an full path relative to the given directory, UTF-16 version.
2695	*
2696	* This will create any missing nodes while walking.
2697	*
2698	* The caller will have to do the path hash table insertion of the result.
2699	*
2700	* @returns Pointer to the tree node corresponding to @a pszPath.
2701	* NULL on lookup failure, see @a penmError for details.
2702	* @param pCache The cache.
2703	* @param pParent The directory to start the lookup in.
2704	* @param pszPath The path to walk. No dot-dot bits allowed!
2705	* @param cchPath The length of the path.
2706	* @param fFlags Lookup flags, KFSCACHE_LOOKUP_F_XXX.
2707	* @param penmError Where to return details as to why the lookup
2708	* failed.
2709	* @param ppLastAncestor Where to return the last parent element found
2710	* (referenced) in case of error an path/file not
2711	* found problem. Optional.
2712	*/
2713	PKFSOBJ kFsCacheLookupRelativeToDirW(PKFSCACHE pCache, PKFSDIR pParent, const wchar_t *pwszPath, KU32 cwcPath, KU32 fFlags,
2714	KFSLOOKUPERROR penmError, PKFSOBJ ppLastAncestor)
2715	{
2716	/*
2717	* Walk loop.
2718	*/
2719	KU32 off = 0;
2720	if (ppLastAncestor)
2721	*ppLastAncestor = NULL;
2722	for (;;)
2723	{
2724	PKFSOBJ pChild;
2725
2726	/*
2727	* Find the end of the component, counting trailing slashes.
2728	*/
2729	wchar_t wc;
2730	KU32 cwcSlashes = 0;
2731	KU32 offEnd = off + 1;
2732	while ((wc = pwszPath[offEnd]) != '\0')
2733	{
2734	if (!IS_SLASH(wc))
2735	offEnd++;
2736	else
2737	{
2738	do
2739	cwcSlashes++;
2740	while (IS_SLASH(pwszPath[offEnd + cwcSlashes]));
2741	break;
2742	}
2743	}
2744
2745	/*
2746	* Do we need to populate or refresh this directory first?
2747	*/
2748	if ( !pParent->fNeedRePopulating
2749	&& pParent->fPopulated
2750	&& ( pParent->Obj.uCacheGen == KFSOBJ_CACHE_GEN_IGNORE
2751	\|\| pParent->Obj.uCacheGen == pCache->auGenerations[pParent->Obj.fFlags & KFSOBJ_F_USE_CUSTOM_GEN]) )
2752	{ /* likely */ }
2753	else if ( (fFlags & (KFSCACHE_LOOKUP_F_NO_INSERT \| fFlags & KFSCACHE_LOOKUP_F_NO_REFRESH))
2754	\|\| kFsCachePopuplateOrRefreshDir(pCache, pParent, penmError))
2755	{ /* likely */ }
2756	else
2757	return NULL;
2758
2759	/*
2760	* Search the current node for the name.
2761	*
2762	* If we don't find it, we may insert a missing node depending on
2763	* the cache configuration.
2764	*/
2765	pChild = kFsCacheFindChildW(pCache, pParent, &pwszPath[off], offEnd - off);
2766	if (pChild != NULL)
2767	{ /* probably likely */ }
2768	else
2769	{
2770	if ( (pCache->fFlags & KFSCACHE_F_MISSING_OBJECTS)
2771	&& !(fFlags & KFSCACHE_LOOKUP_F_NO_INSERT))
2772	pChild = kFsCacheCreateMissingW(pCache, pParent, &pwszPath[off], offEnd - off, penmError);
2773	if (cwcSlashes == 0 \|\| offEnd + cwcSlashes >= cwcPath)
2774	{
2775	if (pChild)
2776	return kFsCacheObjRetainInternal(pChild);
2777	*penmError = KFSLOOKUPERROR_NOT_FOUND;
2778	}
2779	else
2780	*penmError = KFSLOOKUPERROR_PATH_COMP_NOT_FOUND;
2781	if (ppLastAncestor)
2782	*ppLastAncestor = kFsCacheObjRetainInternal(&pParent->Obj);
2783	return NULL;
2784	}
2785
2786	/* Advance off and check if we're done already. */
2787	off = offEnd + cwcSlashes;
2788	if ( cwcSlashes == 0
2789	\|\| off >= cwcPath)
2790	{
2791	if ( pChild->bObjType != KFSOBJ_TYPE_MISSING
2792	\|\| pChild->uCacheGen == KFSOBJ_CACHE_GEN_IGNORE
2793	\|\| pChild->uCacheGen == pCache->auGenerationsMissing[pChild->fFlags & KFSOBJ_F_USE_CUSTOM_GEN]
2794	\|\| (fFlags & KFSCACHE_LOOKUP_F_NO_REFRESH)
2795	\|\| kFsCacheRefreshMissing(pCache, pChild, penmError) )
2796	{ /* likely */ }
2797	else
2798	return NULL;
2799	return kFsCacheObjRetainInternal(pChild);
2800	}
2801
2802	/*
2803	* Check that it's a directory. If a missing entry, we may have to
2804	* refresh it and re-examin it.
2805	*/
2806	if (pChild->bObjType == KFSOBJ_TYPE_DIR)
2807	pParent = (PKFSDIR)pChild;
2808	else if (pChild->bObjType != KFSOBJ_TYPE_MISSING)
2809	{
2810	*penmError = KFSLOOKUPERROR_PATH_COMP_NOT_DIR;
2811	if (ppLastAncestor)
2812	*ppLastAncestor = kFsCacheObjRetainInternal(&pParent->Obj);
2813	return NULL;
2814	}
2815	else if ( pChild->uCacheGen == KFSOBJ_CACHE_GEN_IGNORE
2816	\|\| pChild->uCacheGen == pCache->auGenerationsMissing[pChild->fFlags & KFSOBJ_F_USE_CUSTOM_GEN]
2817	\|\| (fFlags & KFSCACHE_LOOKUP_F_NO_REFRESH) )
2818
2819	{
2820	*penmError = KFSLOOKUPERROR_PATH_COMP_NOT_FOUND;
2821	if (ppLastAncestor)
2822	*ppLastAncestor = kFsCacheObjRetainInternal(&pParent->Obj);
2823	return NULL;
2824	}
2825	else if (kFsCacheRefreshMissingIntermediateDir(pCache, pChild, penmError))
2826	pParent = (PKFSDIR)pChild;
2827	else
2828	{
2829	if (ppLastAncestor)
2830	*ppLastAncestor = kFsCacheObjRetainInternal(&pParent->Obj);
2831	return NULL;
2832	}
2833	}
2834
2835	return NULL;
2836
2837	}
2838
2839	/**
2840	* Walk the file system tree for the given absolute path, entering it into the
2841	* hash table.
2842	*
2843	* This will create any missing nodes while walking.
2844	*
2845	* The caller will have to do the path hash table insertion of the result.
2846	*
2847	* @returns Pointer to the tree node corresponding to @a pszPath.
2848	* NULL on lookup failure, see @a penmError for details.
2849	* @param pCache The cache.
2850	* @param pszPath The path to walk. No dot-dot bits allowed!
2851	* @param cchPath The length of the path.
2852	* @param fFlags Lookup flags, KFSCACHE_LOOKUP_F_XXX.
2853	* @param penmError Where to return details as to why the lookup
2854	* failed.
2855	* @param ppLastAncestor Where to return the last parent element found
2856	* (referenced) in case of error an path/file not
2857	* found problem. Optional.
2858	*/
2859	static PKFSOBJ kFsCacheLookupAbsoluteA(PKFSCACHE pCache, const char *pszPath, KU32 cchPath, KU32 fFlags,
2860	KFSLOOKUPERROR penmError, PKFSOBJ ppLastAncestor)
2861	{
2862	PKFSOBJ pRoot;
2863	KU32 cchSlashes;
2864	KU32 offEnd;
2865
2866	KFSCACHE_LOG2(("kFsCacheLookupAbsoluteA(%s)\n", pszPath));
2867
2868	/*
2869	* The root "directory" needs special handling, so we keep it outside the
2870	* main search loop. (Special: Cannot enumerate it, UNCs, ++.)
2871	*/
2872	cchSlashes = 0;
2873	if ( pszPath[1] == ':'
2874	&& IS_ALPHA(pszPath[0]))
2875	{
2876	/* Drive letter. */
2877	offEnd = 2;
2878	kHlpAssert(IS_SLASH(pszPath[2]));
2879	pRoot = kFsCacheLookupDrive(pCache, toupper(pszPath[0]), fFlags, penmError);
2880	}
2881	else if ( IS_SLASH(pszPath[0])
2882	&& IS_SLASH(pszPath[1]) )
2883	pRoot = kFsCacheLookupUncShareA(pCache, pszPath, fFlags, &offEnd, penmError);
2884	else
2885	{
2886	*penmError = KFSLOOKUPERROR_UNSUPPORTED;
2887	return NULL;
2888	}
2889	if (pRoot)
2890	{ /* likely */ }
2891	else
2892	return NULL;
2893
2894	/* Count slashes trailing the root spec. */
2895	if (offEnd < cchPath)
2896	{
2897	kHlpAssert(IS_SLASH(pszPath[offEnd]));
2898	do
2899	cchSlashes++;
2900	while (IS_SLASH(pszPath[offEnd + cchSlashes]));
2901	}
2902
2903	/* Done already? */
2904	if (offEnd >= cchPath)
2905	{
2906	if ( pRoot->uCacheGen == KFSOBJ_CACHE_GEN_IGNORE
2907	\|\| pRoot->uCacheGen == ( pRoot->bObjType != KFSOBJ_TYPE_MISSING
2908	? pCache->auGenerations[ pRoot->fFlags & KFSOBJ_F_USE_CUSTOM_GEN]
2909	: pCache->auGenerationsMissing[pRoot->fFlags & KFSOBJ_F_USE_CUSTOM_GEN])
2910	\|\| (fFlags & KFSCACHE_LOOKUP_F_NO_REFRESH)
2911	\|\| kFsCacheRefreshObj(pCache, pRoot, penmError))
2912	return kFsCacheObjRetainInternal(pRoot);
2913	return NULL;
2914	}
2915
2916	/* Check that we've got a valid result and not a cached negative one. */
2917	if (pRoot->bObjType == KFSOBJ_TYPE_DIR)
2918	{ /* likely */ }
2919	else
2920	{
2921	kHlpAssert(pRoot->bObjType == KFSOBJ_TYPE_MISSING);
2922	kHlpAssert( pRoot->uCacheGen == KFSOBJ_CACHE_GEN_IGNORE
2923	\|\| pRoot->uCacheGen == pCache->auGenerationsMissing[pRoot->fFlags & KFSOBJ_F_USE_CUSTOM_GEN]);
2924	return pRoot;
2925	}
2926
2927	/*
2928	* Now that we've found a valid root directory, lookup the
2929	* remainder of the path starting with it.
2930	*/
2931	return kFsCacheLookupRelativeToDirA(pCache, (PKFSDIR)pRoot, &pszPath[offEnd + cchSlashes],
2932	cchPath - offEnd - cchSlashes, fFlags, penmError, ppLastAncestor);
2933	}
2934
2935
2936	/**
2937	* Walk the file system tree for the given absolute path, UTF-16 version.
2938	*
2939	* This will create any missing nodes while walking.
2940	*
2941	* The caller will have to do the path hash table insertion of the result.
2942	*
2943	* @returns Pointer to the tree node corresponding to @a pszPath.
2944	* NULL on lookup failure, see @a penmError for details.
2945	* @param pCache The cache.
2946	* @param pwszPath The path to walk.
2947	* @param cwcPath The length of the path (in wchar_t's).
2948	* @param fFlags Lookup flags, KFSCACHE_LOOKUP_F_XXX.
2949	* @param penmError Where to return details as to why the lookup
2950	* failed.
2951	* @param ppLastAncestor Where to return the last parent element found
2952	* (referenced) in case of error an path/file not
2953	* found problem. Optional.
2954	*/
2955	static PKFSOBJ kFsCacheLookupAbsoluteW(PKFSCACHE pCache, const wchar_t *pwszPath, KU32 cwcPath, KU32 fFlags,
2956	KFSLOOKUPERROR penmError, PKFSOBJ ppLastAncestor)
2957	{
2958	PKFSDIR pParent = &pCache->RootDir;
2959	PKFSOBJ pRoot;
2960	KU32 off;
2961	KU32 cwcSlashes;
2962	KU32 offEnd;
2963
2964	KFSCACHE_LOG2(("kFsCacheLookupAbsoluteW(%ls)\n", pwszPath));
2965
2966	/*
2967	* The root "directory" needs special handling, so we keep it outside the
2968	* main search loop. (Special: Cannot enumerate it, UNCs, ++.)
2969	*/
2970	cwcSlashes = 0;
2971	off = 0;
2972	if ( pwszPath[1] == ':'
2973	&& IS_ALPHA(pwszPath[0]))
2974	{
2975	/* Drive letter. */
2976	offEnd = 2;
2977	kHlpAssert(IS_SLASH(pwszPath[2]));
2978	pRoot = kFsCacheLookupDrive(pCache, toupper(pwszPath[0]), fFlags, penmError);
2979	}
2980	else if ( IS_SLASH(pwszPath[0])
2981	&& IS_SLASH(pwszPath[1]) )
2982	pRoot = kFsCacheLookupUncShareW(pCache, pwszPath, fFlags, &offEnd, penmError);
2983	else
2984	{
2985	*penmError = KFSLOOKUPERROR_UNSUPPORTED;
2986	return NULL;
2987	}
2988	if (pRoot)
2989	{ /* likely */ }
2990	else
2991	return NULL;
2992
2993	/* Count slashes trailing the root spec. */
2994	if (offEnd < cwcPath)
2995	{
2996	kHlpAssert(IS_SLASH(pwszPath[offEnd]));
2997	do
2998	cwcSlashes++;
2999	while (IS_SLASH(pwszPath[offEnd + cwcSlashes]));
3000	}
3001
3002	/* Done already? */
3003	if (offEnd >= cwcPath)
3004	{
3005	if ( pRoot->uCacheGen == KFSOBJ_CACHE_GEN_IGNORE
3006	\|\| pRoot->uCacheGen == (pRoot->bObjType != KFSOBJ_TYPE_MISSING
3007	? pCache->auGenerations[ pRoot->fFlags & KFSOBJ_F_USE_CUSTOM_GEN]
3008	: pCache->auGenerationsMissing[pRoot->fFlags & KFSOBJ_F_USE_CUSTOM_GEN])
3009	\|\| (fFlags & KFSCACHE_LOOKUP_F_NO_REFRESH)
3010	\|\| kFsCacheRefreshObj(pCache, pRoot, penmError))
3011	return kFsCacheObjRetainInternal(pRoot);
3012	return NULL;
3013	}
3014
3015	/* Check that we've got a valid result and not a cached negative one. */
3016	if (pRoot->bObjType == KFSOBJ_TYPE_DIR)
3017	{ /* likely */ }
3018	else
3019	{
3020	kHlpAssert(pRoot->bObjType == KFSOBJ_TYPE_MISSING);
3021	kHlpAssert( pRoot->uCacheGen == KFSOBJ_CACHE_GEN_IGNORE
3022	\|\| pRoot->uCacheGen == pCache->auGenerationsMissing[pRoot->fFlags & KFSOBJ_F_USE_CUSTOM_GEN]);
3023	return pRoot;
3024	}
3025
3026	/*
3027	* Now that we've found a valid root directory, lookup the
3028	* remainder of the path starting with it.
3029	*/
3030	return kFsCacheLookupRelativeToDirW(pCache, (PKFSDIR)pRoot, &pwszPath[offEnd + cwcSlashes],
3031	cwcPath - offEnd - cwcSlashes, fFlags, penmError, ppLastAncestor);
3032	}
3033
3034
3035	/**
3036	* This deals with paths that are relative and paths that contains '..'
3037	* elements, ANSI version.
3038	*
3039	* @returns Pointer to object corresponding to @a pszPath on success.
3040	* NULL if this isn't a path we care to cache.
3041	*
3042	* @param pCache The cache.
3043	* @param pszPath The path.
3044	* @param cchPath The length of the path.
3045	* @param fFlags Lookup flags, KFSCACHE_LOOKUP_F_XXX.
3046	* @param penmError Where to return details as to why the lookup
3047	* failed.
3048	* @param ppLastAncestor Where to return the last parent element found
3049	* (referenced) in case of error an path/file not
3050	* found problem. Optional.
3051	*/
3052	static PKFSOBJ kFsCacheLookupSlowA(PKFSCACHE pCache, const char *pszPath, KU32 cchPath, KU32 fFlags,
3053	KFSLOOKUPERROR penmError, PKFSOBJ ppLastAncestor)
3054	{
3055	/*
3056	* We just call GetFullPathNameA here to do the job as getcwd and _getdcwd
3057	* ends up calling it anyway.
3058	*/
3059	char szFull[KFSCACHE_CFG_MAX_PATH];
3060	UINT cchFull = GetFullPathNameA(pszPath, sizeof(szFull), szFull, NULL);
3061	if ( cchFull >= 3
3062	&& cchFull < sizeof(szFull))
3063	{
3064	KFSCACHE_LOG2(("kFsCacheLookupSlowA(%s)\n", pszPath));
3065	return kFsCacheLookupAbsoluteA(pCache, szFull, cchFull, fFlags, penmError, ppLastAncestor);
3066	}
3067
3068	/* The path is too long! */
3069	kHlpAssertMsgFailed(("'%s' -> cchFull=%u\n", pszPath, cchFull));
3070	*penmError = KFSLOOKUPERROR_PATH_TOO_LONG;
3071	return NULL;
3072	}
3073
3074
3075	/**
3076	* This deals with paths that are relative and paths that contains '..'
3077	* elements, UTF-16 version.
3078	*
3079	* @returns Pointer to object corresponding to @a pszPath on success.
3080	* NULL if this isn't a path we care to cache.
3081	*
3082	* @param pCache The cache.
3083	* @param pwszPath The path.
3084	* @param cwcPath The length of the path (in wchar_t's).
3085	* @param fFlags Lookup flags, KFSCACHE_LOOKUP_F_XXX.
3086	* @param penmError Where to return details as to why the lookup
3087	* failed.
3088	* @param ppLastAncestor Where to return the last parent element found
3089	* (referenced) in case of error an path/file not
3090	* found problem. Optional.
3091	*/
3092	static PKFSOBJ kFsCacheLookupSlowW(PKFSCACHE pCache, const wchar_t *pwszPath, KU32 wcwPath, KU32 fFlags,
3093	KFSLOOKUPERROR penmError, PKFSOBJ ppLastAncestor)
3094	{
3095	/*
3096	* We just call GetFullPathNameA here to do the job as getcwd and _getdcwd
3097	* ends up calling it anyway.
3098	*/
3099	wchar_t wszFull[KFSCACHE_CFG_MAX_PATH];
3100	UINT cwcFull = GetFullPathNameW(pwszPath, KFSCACHE_CFG_MAX_PATH, wszFull, NULL);
3101	if ( cwcFull >= 3
3102	&& cwcFull < KFSCACHE_CFG_MAX_PATH)
3103	{
3104	KFSCACHE_LOG2(("kFsCacheLookupSlowA(%ls)\n", pwszPath));
3105	return kFsCacheLookupAbsoluteW(pCache, wszFull, cwcFull, fFlags, penmError, ppLastAncestor);
3106	}
3107
3108	/* The path is too long! */
3109	kHlpAssertMsgFailed(("'%ls' -> cwcFull=%u\n", pwszPath, cwcFull));
3110	*penmError = KFSLOOKUPERROR_PATH_TOO_LONG;
3111	return NULL;
3112	}
3113
3114
3115	/**
3116	* Refreshes a path hash that has expired, ANSI version.
3117	*
3118	* @returns pHash on success, NULL if removed.
3119	* @param pCache The cache.
3120	* @param pHashEntry The path hash.
3121	* @param idxHashTab The hash table entry.
3122	*/
3123	static PKFSHASHA kFsCacheRefreshPathA(PKFSCACHE pCache, PKFSHASHA pHashEntry, KU32 idxHashTab)
3124	{
3125	PKFSOBJ pLastAncestor = NULL;
3126	if (!pHashEntry->pFsObj)
3127	{
3128	if (pHashEntry->fAbsolute)
3129	pHashEntry->pFsObj = kFsCacheLookupAbsoluteA(pCache, pHashEntry->pszPath, pHashEntry->cchPath, 0 /fFlags/,
3130	&pHashEntry->enmError, &pLastAncestor);
3131	else
3132	pHashEntry->pFsObj = kFsCacheLookupSlowA(pCache, pHashEntry->pszPath, pHashEntry->cchPath, 0 /fFlags/,
3133	&pHashEntry->enmError, &pLastAncestor);
3134	}
3135	else
3136	{
3137	KU8 bOldType = pHashEntry->pFsObj->bObjType;
3138	KFSLOOKUPERROR enmError;
3139	if (kFsCacheRefreshObj(pCache, pHashEntry->pFsObj, &enmError))
3140	{
3141	if (pHashEntry->pFsObj->bObjType == bOldType)
3142	{ }
3143	else
3144	{
3145	kFsCacheObjRelease(pCache, pHashEntry->pFsObj);
3146	if (pHashEntry->fAbsolute)
3147	pHashEntry->pFsObj = kFsCacheLookupAbsoluteA(pCache, pHashEntry->pszPath, pHashEntry->cchPath, 0 /fFlags/,
3148	&pHashEntry->enmError, &pLastAncestor);
3149	else
3150	pHashEntry->pFsObj = kFsCacheLookupSlowA(pCache, pHashEntry->pszPath, pHashEntry->cchPath, 0 /fFlags/,
3151	&pHashEntry->enmError, &pLastAncestor);
3152	}
3153	}
3154	else
3155	{
3156	fprintf(stderr, "kFsCacheRefreshPathA - refresh failure handling not implemented!\n");
3157	__debugbreak();
3158	/** @todo just remove this entry. */
3159	return NULL;
3160	}
3161	}
3162
3163	if (pLastAncestor && !pHashEntry->pFsObj)
3164	pHashEntry->idxMissingGen = pLastAncestor->fFlags & KFSOBJ_F_USE_CUSTOM_GEN;
3165	pHashEntry->uCacheGen = !pHashEntry->pFsObj
3166	? pCache->auGenerationsMissing[pHashEntry->idxMissingGen]
3167	: pHashEntry->pFsObj->bObjType == KFSOBJ_TYPE_MISSING
3168	? pCache->auGenerationsMissing[pHashEntry->pFsObj->fFlags & KFSOBJ_F_USE_CUSTOM_GEN]
3169	: pCache->auGenerations[ pHashEntry->pFsObj->fFlags & KFSOBJ_F_USE_CUSTOM_GEN];
3170	if (pLastAncestor)
3171	kFsCacheObjRelease(pCache, pLastAncestor);
3172	return pHashEntry;
3173	}
3174
3175
3176	/**
3177	* Refreshes a path hash that has expired, UTF-16 version.
3178	*
3179	* @returns pHash on success, NULL if removed.
3180	* @param pCache The cache.
3181	* @param pHashEntry The path hash.
3182	* @param idxHashTab The hash table entry.
3183	*/
3184	static PKFSHASHW kFsCacheRefreshPathW(PKFSCACHE pCache, PKFSHASHW pHashEntry, KU32 idxHashTab)
3185	{
3186	PKFSOBJ pLastAncestor = NULL;
3187	if (!pHashEntry->pFsObj)
3188	{
3189	if (pHashEntry->fAbsolute)
3190	pHashEntry->pFsObj = kFsCacheLookupAbsoluteW(pCache, pHashEntry->pwszPath, pHashEntry->cwcPath, 0 /fFlags/,
3191	&pHashEntry->enmError, &pLastAncestor);
3192	else
3193	pHashEntry->pFsObj = kFsCacheLookupSlowW(pCache, pHashEntry->pwszPath, pHashEntry->cwcPath, 0 /fFlags/,
3194	&pHashEntry->enmError, &pLastAncestor);
3195	}
3196	else
3197	{
3198	KU8 bOldType = pHashEntry->pFsObj->bObjType;
3199	KFSLOOKUPERROR enmError;
3200	if (kFsCacheRefreshObj(pCache, pHashEntry->pFsObj, &enmError))
3201	{
3202	if (pHashEntry->pFsObj->bObjType == bOldType)
3203	{ }
3204	else
3205	{
3206	kFsCacheObjRelease(pCache, pHashEntry->pFsObj);
3207	if (pHashEntry->fAbsolute)
3208	pHashEntry->pFsObj = kFsCacheLookupAbsoluteW(pCache, pHashEntry->pwszPath, pHashEntry->cwcPath, 0 /fFlags/,
3209	&pHashEntry->enmError, &pLastAncestor);
3210	else
3211	pHashEntry->pFsObj = kFsCacheLookupSlowW(pCache, pHashEntry->pwszPath, pHashEntry->cwcPath, 0 /fFlags/,
3212	&pHashEntry->enmError, &pLastAncestor);
3213	}
3214	}
3215	else
3216	{
3217	fprintf(stderr, "kFsCacheRefreshPathW - refresh failure handling not implemented!\n");
3218	__debugbreak();
3219	/** @todo just remove this entry. */
3220	return NULL;
3221	}
3222	}
3223	if (pLastAncestor && !pHashEntry->pFsObj)
3224	pHashEntry->idxMissingGen = pLastAncestor->fFlags & KFSOBJ_F_USE_CUSTOM_GEN;
3225	pHashEntry->uCacheGen = !pHashEntry->pFsObj
3226	? pCache->auGenerationsMissing[pHashEntry->idxMissingGen]
3227	: pHashEntry->pFsObj->bObjType == KFSOBJ_TYPE_MISSING
3228	? pCache->auGenerationsMissing[pHashEntry->pFsObj->fFlags & KFSOBJ_F_USE_CUSTOM_GEN]
3229	: pCache->auGenerations[ pHashEntry->pFsObj->fFlags & KFSOBJ_F_USE_CUSTOM_GEN];
3230	if (pLastAncestor)
3231	kFsCacheObjRelease(pCache, pLastAncestor);
3232	return pHashEntry;
3233	}
3234
3235
3236	/**
3237	* Internal lookup worker that looks up a KFSOBJ for the given ANSI path with
3238	* length and hash.
3239	*
3240	* This will first try the hash table. If not in the hash table, the file
3241	* system cache tree is walked, missing bits filled in and finally a hash table
3242	* entry is created.
3243	*
3244	* Only drive letter paths are cachable. We don't do any UNC paths at this
3245	* point.
3246	*
3247	* @returns Reference to object corresponding to @a pszPath on success, this
3248	* must be released by kFsCacheObjRelease.
3249	* NULL if not a path we care to cache.
3250	* @param pCache The cache.
3251	* @param pchPath The path to lookup.
3252	* @param cchPath The path length.
3253	* @param uHashPath The hash of the path.
3254	* @param penmError Where to return details as to why the lookup
3255	* failed.
3256	*/
3257	static PKFSOBJ kFsCacheLookupHashedA(PKFSCACHE pCache, const char *pchPath, KU32 cchPath, KU32 uHashPath,
3258	KFSLOOKUPERROR *penmError)
3259	{
3260	/*
3261	* Do hash table lookup of the path.
3262	*/
3263	KU32 idxHashTab = uHashPath % K_ELEMENTS(pCache->apAnsiPaths);
3264	PKFSHASHA pHashEntry = pCache->apAnsiPaths[idxHashTab];
3265	kHlpAssert(pCache->u32Magic == KFSCACHE_MAGIC);
3266	if (pHashEntry)
3267	{
3268	do
3269	{
3270	if ( pHashEntry->uHashPath == uHashPath
3271	&& pHashEntry->cchPath == cchPath
3272	&& kHlpMemComp(pHashEntry->pszPath, pchPath, cchPath) == 0)
3273	{
3274	PKFSOBJ pFsObj;
3275	if ( pHashEntry->uCacheGen == KFSOBJ_CACHE_GEN_IGNORE
3276	\|\| pHashEntry->uCacheGen == ( (pFsObj = pHashEntry->pFsObj) != NULL
3277	? pFsObj->bObjType != KFSOBJ_TYPE_MISSING
3278	? pCache->auGenerations[ pFsObj->fFlags & KFSOBJ_F_USE_CUSTOM_GEN]
3279	: pCache->auGenerationsMissing[pFsObj->fFlags & KFSOBJ_F_USE_CUSTOM_GEN]
3280	: pCache->auGenerationsMissing[pHashEntry->idxMissingGen])
3281	\|\| (pHashEntry = kFsCacheRefreshPathA(pCache, pHashEntry, idxHashTab)) )
3282	{
3283	pCache->cLookups++;
3284	pCache->cPathHashHits++;
3285	KFSCACHE_LOG2(("kFsCacheLookupA(%.s) - hit %p\n", cchPath, cchPath, pchPath, pHashEntry->pFsObj));
3286	*penmError = pHashEntry->enmError;
3287	if (pHashEntry->pFsObj)
3288	return kFsCacheObjRetainInternal(pHashEntry->pFsObj);
3289	return NULL;
3290	}
3291	break;
3292	}
3293	pHashEntry = pHashEntry->pNext;
3294	} while (pHashEntry);
3295	}
3296
3297	/*
3298	* Create an entry for it by walking the file system cache and filling in the blanks.
3299	*/
3300	if ( cchPath > 0
3301	&& cchPath < KFSCACHE_CFG_MAX_PATH)
3302	{
3303	PKFSOBJ pFsObj;
3304	KBOOL fAbsolute;
3305	PKFSOBJ pLastAncestor = NULL;
3306
3307	/* Is absolute without any '..' bits? */
3308	if ( cchPath >= 3
3309	&& ( ( pchPath[1] == ':' /* Drive letter */
3310	&& IS_SLASH(pchPath[2])
3311	&& IS_ALPHA(pchPath[0]) )
3312	\|\| ( IS_SLASH(pchPath[0]) /* UNC */
3313	&& IS_SLASH(pchPath[1]) ) )
3314	&& !kFsCacheHasDotDotA(pchPath, cchPath) )
3315	{
3316	pFsObj = kFsCacheLookupAbsoluteA(pCache, pchPath, cchPath, 0 /fFlags/, penmError, &pLastAncestor);
3317	fAbsolute = K_TRUE;
3318	}
3319	else
3320	{
3321	pFsObj = kFsCacheLookupSlowA(pCache, pchPath, cchPath, 0 /fFlags/, penmError, &pLastAncestor);
3322	fAbsolute = K_FALSE;
3323	}
3324	if ( pFsObj
3325	\|\| ( (pCache->fFlags & KFSCACHE_F_MISSING_PATHS)
3326	&& *penmError != KFSLOOKUPERROR_PATH_TOO_LONG)
3327	\|\| *penmError == KFSLOOKUPERROR_UNSUPPORTED )
3328	kFsCacheCreatePathHashTabEntryA(pCache, pFsObj, pchPath, cchPath, uHashPath, idxHashTab, fAbsolute,
3329	pLastAncestor ? pLastAncestor->bObjType & KFSOBJ_F_USE_CUSTOM_GEN : 0, *penmError);
3330	if (pLastAncestor)
3331	kFsCacheObjRelease(pCache, pLastAncestor);
3332
3333	pCache->cLookups++;
3334	if (pFsObj)
3335	pCache->cWalkHits++;
3336	return pFsObj;
3337	}
3338
3339	*penmError = KFSLOOKUPERROR_PATH_TOO_LONG;
3340	return NULL;
3341	}
3342
3343
3344	/**
3345	* Internal lookup worker that looks up a KFSOBJ for the given UTF-16 path with
3346	* length and hash.
3347	*
3348	* This will first try the hash table. If not in the hash table, the file
3349	* system cache tree is walked, missing bits filled in and finally a hash table
3350	* entry is created.
3351	*
3352	* Only drive letter paths are cachable. We don't do any UNC paths at this
3353	* point.
3354	*
3355	* @returns Reference to object corresponding to @a pwcPath on success, this
3356	* must be released by kFsCacheObjRelease.
3357	* NULL if not a path we care to cache.
3358	* @param pCache The cache.
3359	* @param pwcPath The path to lookup.
3360	* @param cwcPath The length of the path (in wchar_t's).
3361	* @param uHashPath The hash of the path.
3362	* @param penmError Where to return details as to why the lookup
3363	* failed.
3364	*/
3365	static PKFSOBJ kFsCacheLookupHashedW(PKFSCACHE pCache, const wchar_t *pwcPath, KU32 cwcPath, KU32 uHashPath,
3366	KFSLOOKUPERROR *penmError)
3367	{
3368	/*
3369	* Do hash table lookup of the path.
3370	*/
3371	KU32 idxHashTab = uHashPath % K_ELEMENTS(pCache->apAnsiPaths);
3372	PKFSHASHW pHashEntry = pCache->apUtf16Paths[idxHashTab];
3373	kHlpAssert(pCache->u32Magic == KFSCACHE_MAGIC);
3374	if (pHashEntry)
3375	{
3376	do
3377	{
3378	if ( pHashEntry->uHashPath == uHashPath
3379	&& pHashEntry->cwcPath == cwcPath
3380	&& kHlpMemComp(pHashEntry->pwszPath, pwcPath, cwcPath) == 0)
3381	{
3382	PKFSOBJ pFsObj;
3383	if ( pHashEntry->uCacheGen == KFSOBJ_CACHE_GEN_IGNORE
3384	\|\| pHashEntry->uCacheGen == ((pFsObj = pHashEntry->pFsObj) != NULL
3385	? pFsObj->bObjType != KFSOBJ_TYPE_MISSING
3386	? pCache->auGenerations[ pFsObj->fFlags & KFSOBJ_F_USE_CUSTOM_GEN]
3387	: pCache->auGenerationsMissing[pFsObj->fFlags & KFSOBJ_F_USE_CUSTOM_GEN]
3388	: pCache->auGenerationsMissing[pHashEntry->idxMissingGen])
3389	\|\| (pHashEntry = kFsCacheRefreshPathW(pCache, pHashEntry, idxHashTab)) )
3390	{
3391	pCache->cLookups++;
3392	pCache->cPathHashHits++;
3393	KFSCACHE_LOG2(("kFsCacheLookupW(%.ls) - hit %p\n", cwcPath, cwcPath, pwcPath, pHashEntry->pFsObj));
3394	*penmError = pHashEntry->enmError;
3395	if (pHashEntry->pFsObj)
3396	return kFsCacheObjRetainInternal(pHashEntry->pFsObj);
3397	return NULL;
3398	}
3399	break;
3400	}
3401	pHashEntry = pHashEntry->pNext;
3402	} while (pHashEntry);
3403	}
3404
3405	/*
3406	* Create an entry for it by walking the file system cache and filling in the blanks.
3407	*/
3408	if ( cwcPath > 0
3409	&& cwcPath < KFSCACHE_CFG_MAX_PATH)
3410	{
3411	PKFSOBJ pFsObj;
3412	KBOOL fAbsolute;
3413	PKFSOBJ pLastAncestor = NULL;
3414
3415	/* Is absolute without any '..' bits? */
3416	if ( cwcPath >= 3
3417	&& ( ( pwcPath[1] == ':' /* Drive letter */
3418	&& IS_SLASH(pwcPath[2])
3419	&& IS_ALPHA(pwcPath[0]) )
3420	\|\| ( IS_SLASH(pwcPath[0]) /* UNC */
3421	&& IS_SLASH(pwcPath[1]) ) )
3422	&& !kFsCacheHasDotDotW(pwcPath, cwcPath) )
3423	{
3424	pFsObj = kFsCacheLookupAbsoluteW(pCache, pwcPath, cwcPath, 0 /fFlags/, penmError, &pLastAncestor);
3425	fAbsolute = K_TRUE;
3426	}
3427	else
3428	{
3429	pFsObj = kFsCacheLookupSlowW(pCache, pwcPath, cwcPath, 0 /fFlags/, penmError, &pLastAncestor);
3430	fAbsolute = K_FALSE;
3431	}
3432	if ( pFsObj
3433	\|\| ( (pCache->fFlags & KFSCACHE_F_MISSING_PATHS)
3434	&& *penmError != KFSLOOKUPERROR_PATH_TOO_LONG)
3435	\|\| *penmError == KFSLOOKUPERROR_UNSUPPORTED )
3436	kFsCacheCreatePathHashTabEntryW(pCache, pFsObj, pwcPath, cwcPath, uHashPath, idxHashTab, fAbsolute,
3437	pLastAncestor ? pLastAncestor->bObjType & KFSOBJ_F_USE_CUSTOM_GEN : 0, *penmError);
3438	if (pLastAncestor)
3439	kFsCacheObjRelease(pCache, pLastAncestor);
3440
3441	pCache->cLookups++;
3442	if (pFsObj)
3443	pCache->cWalkHits++;
3444	return pFsObj;
3445	}
3446
3447	*penmError = KFSLOOKUPERROR_PATH_TOO_LONG;
3448	return NULL;
3449	}
3450
3451
3452
3453	/**
3454	* Looks up a KFSOBJ for the given ANSI path.
3455	*
3456	* This will first try the hash table. If not in the hash table, the file
3457	* system cache tree is walked, missing bits filled in and finally a hash table
3458	* entry is created.
3459	*
3460	* Only drive letter paths are cachable. We don't do any UNC paths at this
3461	* point.
3462	*
3463	* @returns Reference to object corresponding to @a pszPath on success, this
3464	* must be released by kFsCacheObjRelease.
3465	* NULL if not a path we care to cache.
3466	* @param pCache The cache.
3467	* @param pszPath The path to lookup.
3468	* @param penmError Where to return details as to why the lookup
3469	* failed.
3470	*/
3471	PKFSOBJ kFsCacheLookupA(PKFSCACHE pCache, const char pszPath, KFSLOOKUPERROR penmError)
3472	{
3473	KU32 uHashPath;
3474	KU32 cchPath = (KU32)kFsCacheStrHashEx(pszPath, &uHashPath);
3475	return kFsCacheLookupHashedA(pCache, pszPath, cchPath, uHashPath, penmError);
3476	}
3477
3478
3479	/**
3480	* Looks up a KFSOBJ for the given UTF-16 path.
3481	*
3482	* This will first try the hash table. If not in the hash table, the file
3483	* system cache tree is walked, missing bits filled in and finally a hash table
3484	* entry is created.
3485	*
3486	* Only drive letter paths are cachable. We don't do any UNC paths at this
3487	* point.
3488	*
3489	* @returns Reference to object corresponding to @a pwszPath on success, this
3490	* must be released by kFsCacheObjRelease.
3491	* NULL if not a path we care to cache.
3492	* @param pCache The cache.
3493	* @param pwszPath The path to lookup.
3494	* @param penmError Where to return details as to why the lookup
3495	* failed.
3496	*/
3497	PKFSOBJ kFsCacheLookupW(PKFSCACHE pCache, const wchar_t pwszPath, KFSLOOKUPERROR penmError)
3498	{
3499	KU32 uHashPath;
3500	KU32 cwcPath = (KU32)kFsCacheUtf16HashEx(pwszPath, &uHashPath);
3501	return kFsCacheLookupHashedW(pCache, pwszPath, cwcPath, uHashPath, penmError);
3502	}
3503
3504
3505	/**
3506	* Looks up a KFSOBJ for the given ANSI path.
3507	*
3508	* This will first try the hash table. If not in the hash table, the file
3509	* system cache tree is walked, missing bits filled in and finally a hash table
3510	* entry is created.
3511	*
3512	* Only drive letter paths are cachable. We don't do any UNC paths at this
3513	* point.
3514	*
3515	* @returns Reference to object corresponding to @a pchPath on success, this
3516	* must be released by kFsCacheObjRelease.
3517	* NULL if not a path we care to cache.
3518	* @param pCache The cache.
3519	* @param pchPath The path to lookup (does not need to be nul
3520	* terminated).
3521	* @param cchPath The path length.
3522	* @param penmError Where to return details as to why the lookup
3523	* failed.
3524	*/
3525	PKFSOBJ kFsCacheLookupWithLengthA(PKFSCACHE pCache, const char pchPath, KSIZE cchPath, KFSLOOKUPERROR penmError)
3526	{
3527	return kFsCacheLookupHashedA(pCache, pchPath, (KU32)cchPath, kFsCacheStrHashN(pchPath, cchPath), penmError);
3528	}
3529
3530
3531	/**
3532	* Looks up a KFSOBJ for the given UTF-16 path.
3533	*
3534	* This will first try the hash table. If not in the hash table, the file
3535	* system cache tree is walked, missing bits filled in and finally a hash table
3536	* entry is created.
3537	*
3538	* Only drive letter paths are cachable. We don't do any UNC paths at this
3539	* point.
3540	*
3541	* @returns Reference to object corresponding to @a pwchPath on success, this
3542	* must be released by kFsCacheObjRelease.
3543	* NULL if not a path we care to cache.
3544	* @param pCache The cache.
3545	* @param pwcPath The path to lookup (does not need to be nul
3546	* terminated).
3547	* @param cwcPath The path length (in wchar_t's).
3548	* @param penmError Where to return details as to why the lookup
3549	* failed.
3550	*/
3551	PKFSOBJ kFsCacheLookupWithLengthW(PKFSCACHE pCache, const wchar_t pwcPath, KSIZE cwcPath, KFSLOOKUPERROR penmError)
3552	{
3553	return kFsCacheLookupHashedW(pCache, pwcPath, (KU32)cwcPath, kFsCacheUtf16HashN(pwcPath, cwcPath), penmError);
3554	}
3555
3556
3557	/**
3558	* Wrapper around kFsCacheLookupA that drops KFSOBJ_TYPE_MISSING and returns
3559	* KFSLOOKUPERROR_NOT_FOUND instead.
3560	*
3561	* @returns Reference to object corresponding to @a pszPath on success, this
3562	* must be released by kFsCacheObjRelease.
3563	* NULL if not a path we care to cache.
3564	* @param pCache The cache.
3565	* @param pszPath The path to lookup.
3566	* @param penmError Where to return details as to why the lookup
3567	* failed.
3568	*/
3569	PKFSOBJ kFsCacheLookupNoMissingA(PKFSCACHE pCache, const char pszPath, KFSLOOKUPERROR penmError)
3570	{
3571	PKFSOBJ pObj = kFsCacheLookupA(pCache, pszPath, penmError);
3572	if (pObj)
3573	{
3574	if (pObj->bObjType != KFSOBJ_TYPE_MISSING)
3575	return pObj;
3576
3577	kFsCacheObjRelease(pCache, pObj);
3578	*penmError = KFSLOOKUPERROR_NOT_FOUND;
3579	}
3580	return NULL;
3581	}
3582
3583
3584	/**
3585	* Wrapper around kFsCacheLookupW that drops KFSOBJ_TYPE_MISSING and returns
3586	* KFSLOOKUPERROR_NOT_FOUND instead.
3587	*
3588	* @returns Reference to object corresponding to @a pszPath on success, this
3589	* must be released by kFsCacheObjRelease.
3590	* NULL if not a path we care to cache.
3591	* @param pCache The cache.
3592	* @param pwszPath The path to lookup.
3593	* @param penmError Where to return details as to why the lookup
3594	* failed.
3595	*/
3596	PKFSOBJ kFsCacheLookupNoMissingW(PKFSCACHE pCache, const wchar_t pwszPath, KFSLOOKUPERROR penmError)
3597	{
3598	PKFSOBJ pObj = kFsCacheLookupW(pCache, pwszPath, penmError);
3599	if (pObj)
3600	{
3601	if (pObj->bObjType != KFSOBJ_TYPE_MISSING)
3602	return pObj;
3603
3604	kFsCacheObjRelease(pCache, pObj);
3605	*penmError = KFSLOOKUPERROR_NOT_FOUND;
3606	}
3607	return NULL;
3608	}
3609
3610
3611	/**
3612	* Destroys a cache object which has a zero reference count.
3613	*
3614	* @returns 0
3615	* @param pCache The cache.
3616	* @param pObj The object.
3617	*/
3618	KU32 kFsCacheObjDestroy(PKFSCACHE pCache, PKFSOBJ pObj)
3619	{
3620	kHlpAssert(pObj->cRefs == 0);
3621	kHlpAssert(pObj->pParent == NULL);
3622	kHlpAssert(pObj->u32Magic == KFSOBJ_MAGIC);
3623
3624	KFSCACHE_LOG(("Destroying %s/%s, type=%d\n", pObj->pParent ? pObj->pParent->Obj.pszName : "", pObj->pszName, pObj->bObjType));
3625	if (pObj->abUnused[1] != 0)
3626	{
3627	fprintf(stderr, "Destroying %s/%s, type=%d, path hash entries: %d!\n", pObj->pParent ? pObj->pParent->Obj.pszName : "",
3628	pObj->pszName, pObj->bObjType, pObj->abUnused[0]);
3629	__debugbreak();
3630	}
3631
3632	/*
3633	* Invalidate the structure.
3634	*/
3635	pObj->u32Magic = ~KFSOBJ_MAGIC;
3636
3637	/*
3638	* Destroy any user data first.
3639	*/
3640	while (pObj->pUserDataHead != NULL)
3641	{
3642	PKFSUSERDATA pUserData = pObj->pUserDataHead;
3643	pObj->pUserDataHead = pUserData->pNext;
3644	if (pUserData->pfnDestructor)
3645	pUserData->pfnDestructor(pCache, pObj, pUserData);
3646	kHlpFree(pUserData);
3647	}
3648
3649	/*
3650	* Do type specific destruction
3651	*/
3652	switch (pObj->bObjType)
3653	{
3654	case KFSOBJ_TYPE_MISSING:
3655	/* nothing else to do here */
3656	pCache->cbObjects -= sizeof(KFSDIR);
3657	break;
3658
3659	case KFSOBJ_TYPE_DIR:
3660	{
3661	PKFSDIR pDir = (PKFSDIR)pObj;
3662	KU32 cChildren = pDir->cChildren;
3663	pCache->cbObjects -= sizeof(*pDir)
3664	+ K_ALIGN_Z(cChildren, 16) * sizeof(pDir->papChildren)
3665	+ (pDir->fHashTabMask + !!pDir->fHashTabMask) * sizeof(pDir->papHashTab[0]);
3666
3667	pDir->cChildren = 0;
3668	while (cChildren-- > 0)
3669	kFsCacheObjRelease(pCache, pDir->papChildren[cChildren]);
3670	kHlpFree(pDir->papChildren);
3671	pDir->papChildren = NULL;
3672
3673	kHlpFree(pDir->papHashTab);
3674	pDir->papHashTab = NULL;
3675	break;
3676	}
3677
3678	case KFSOBJ_TYPE_FILE:
3679	case KFSOBJ_TYPE_OTHER:
3680	pCache->cbObjects -= sizeof(*pObj);
3681	break;
3682
3683	default:
3684	return 0;
3685	}
3686
3687	/*
3688	* Common bits.
3689	*/
3690	pCache->cbObjects -= pObj->cchName + 1;
3691	#ifdef KFSCACHE_CFG_UTF16
3692	pCache->cbObjects -= (pObj->cwcName + 1) * sizeof(wchar_t);
3693	#endif
3694	#ifdef KFSCACHE_CFG_SHORT_NAMES
3695	if (pObj->pszName != pObj->pszShortName)
3696	{
3697	pCache->cbObjects -= pObj->cchShortName + 1;
3698	# ifdef KFSCACHE_CFG_UTF16
3699	pCache->cbObjects -= (pObj->cwcShortName + 1) * sizeof(wchar_t);
3700	# endif
3701	}
3702	#endif
3703	pCache->cObjects--;
3704
3705	kHlpFree(pObj);
3706	return 0;
3707	}
3708
3709
3710	/**
3711	* Releases a reference to a cache object.
3712	*
3713	* @returns New reference count.
3714	* @param pCache The cache.
3715	* @param pObj The object.
3716	*/
3717	KU32 kFsCacheObjRelease(PKFSCACHE pCache, PKFSOBJ pObj)
3718	{
3719	if (pObj)
3720	{
3721	KU32 cRefs;
3722	kHlpAssert(pCache->u32Magic == KFSCACHE_MAGIC);
3723	kHlpAssert(pObj->u32Magic == KFSOBJ_MAGIC);
3724
3725	cRefs = --pObj->cRefs;
3726	if (cRefs)
3727	return cRefs;
3728	return kFsCacheObjDestroy(pCache, pObj);
3729	}
3730	return 0;
3731	}
3732
3733
3734	/**
3735	* Retains a reference to a cahce object.
3736	*
3737	* @returns New reference count.
3738	* @param pObj The object.
3739	*/
3740	KU32 kFsCacheObjRetain(PKFSOBJ pObj)
3741	{
3742	KU32 cRefs;
3743	kHlpAssert(pCache->u32Magic == KFSCACHE_MAGIC);
3744	kHlpAssert(pObj->u32Magic == KFSOBJ_MAGIC);
3745
3746	cRefs = ++pObj->cRefs;
3747	kHlpAssert(cRefs < 16384);
3748	return cRefs;
3749	}
3750
3751
3752	/**
3753	* Associates an item of user data with the given object.
3754	*
3755	* If the data needs cleaning up before being free, set the
3756	* PKFSUSERDATA::pfnDestructor member of the returned structure.
3757	*
3758	* @returns Pointer to the user data on success.
3759	* NULL if out of memory or key already in use.
3760	*
3761	* @param pCache The cache.
3762	* @param pObj The object.
3763	* @param uKey The user data key.
3764	* @param cbUserData The size of the user data.
3765	*/
3766	PKFSUSERDATA kFsCacheObjAddUserData(PKFSCACHE pCache, PKFSOBJ pObj, KUPTR uKey, KSIZE cbUserData)
3767	{
3768	kHlpAssert(cbUserData >= sizeof(*pNew));
3769	if (kFsCacheObjGetUserData(pCache, pObj, uKey) == NULL)
3770	{
3771	PKFSUSERDATA pNew = (PKFSUSERDATA)kHlpAllocZ(cbUserData);
3772	if (pNew)
3773	{
3774	pNew->uKey = uKey;
3775	pNew->pfnDestructor = NULL;
3776	pNew->pNext = pObj->pUserDataHead;
3777	pObj->pUserDataHead = pNew;
3778	return pNew;
3779	}
3780	}
3781
3782	return NULL;
3783	}
3784
3785
3786	/**
3787	* Retrieves an item of user data associated with the given object.
3788	*
3789	* @returns Pointer to the associated user data if found, otherwise NULL.
3790	* @param pCache The cache.
3791	* @param pObj The object.
3792	* @param uKey The user data key.
3793	*/
3794	PKFSUSERDATA kFsCacheObjGetUserData(PKFSCACHE pCache, PKFSOBJ pObj, KUPTR uKey)
3795	{
3796	PKFSUSERDATA pCur;
3797
3798	kHlpAssert(pCache->u32Magic == KFSCACHE_MAGIC);
3799	kHlpAssert(pObj->u32Magic == KFSOBJ_MAGIC);
3800
3801	for (pCur = pObj->pUserDataHead; pCur; pCur = pCur->pNext)
3802	if (pCur->uKey == uKey)
3803	return pCur;
3804	return NULL;
3805	}
3806
3807
3808	/**
3809	* Gets the full path to @a pObj, ANSI version.
3810	*
3811	* @returns K_TRUE on success, K_FALSE on buffer overflow (nothing stored).
3812	* @param pObj The object to get the full path to.
3813	* @param pszPath Where to return the path
3814	* @param cbPath The size of the output buffer.
3815	* @param chSlash The slash to use.
3816	*/
3817	KBOOL kFsCacheObjGetFullPathA(PKFSOBJ pObj, char *pszPath, KSIZE cbPath, char chSlash)
3818	{
3819	KSIZE off = pObj->cchParent;
3820	kHlpAssert(pObj->u32Magic == KFSOBJ_MAGIC);
3821	if (off > 0)
3822	{
3823	KSIZE offEnd = off + pObj->cchName;
3824	if (offEnd < cbPath)
3825	{
3826	PKFSDIR pAncestor;
3827
3828	pszPath[off + pObj->cchName] = '\0';
3829	memcpy(&pszPath[off], pObj->pszName, pObj->cchName);
3830
3831	for (pAncestor = pObj->pParent; off > 0; pAncestor = pAncestor->Obj.pParent)
3832	{
3833	kHlpAssert(off > 1);
3834	kHlpAssert(pAncestor != NULL);
3835	kHlpAssert(pAncestor->Obj.cchName > 0);
3836	pszPath[--off] = chSlash;
3837	off -= pAncestor->Obj.cchName;
3838	kHlpAssert(pAncestor->Obj.cchParent == off);
3839	memcpy(&pszPath[off], pAncestor->Obj.pszName, pAncestor->Obj.cchName);
3840	}
3841	return K_TRUE;
3842	}
3843	}
3844	else
3845	{
3846	KBOOL const fDriveLetter = pObj->cchName == 2 && pObj->pszName[2] == ':';
3847	off = pObj->cchName;
3848	if (off + fDriveLetter < cbPath)
3849	{
3850	memcpy(pszPath, pObj->pszName, off);
3851	if (fDriveLetter)
3852	pszPath[off++] = chSlash;
3853	pszPath[off] = '\0';
3854	return K_TRUE;
3855	}
3856	}
3857
3858	return K_FALSE;
3859	}
3860
3861
3862	/**
3863	* Gets the full path to @a pObj, UTF-16 version.
3864	*
3865	* @returns K_TRUE on success, K_FALSE on buffer overflow (nothing stored).
3866	* @param pObj The object to get the full path to.
3867	* @param pszPath Where to return the path
3868	* @param cbPath The size of the output buffer.
3869	* @param wcSlash The slash to use.
3870	*/
3871	KBOOL kFsCacheObjGetFullPathW(PKFSOBJ pObj, wchar_t *pwszPath, KSIZE cwcPath, wchar_t wcSlash)
3872	{
3873	KSIZE off = pObj->cwcParent;
3874	kHlpAssert(pObj->u32Magic == KFSOBJ_MAGIC);
3875	if (off > 0)
3876	{
3877	KSIZE offEnd = off + pObj->cwcName;
3878	if (offEnd < cwcPath)
3879	{
3880	PKFSDIR pAncestor;
3881
3882	pwszPath[off + pObj->cwcName] = '\0';
3883	memcpy(&pwszPath[off], pObj->pwszName, pObj->cwcName * sizeof(wchar_t));
3884
3885	for (pAncestor = pObj->pParent; off > 0; pAncestor = pAncestor->Obj.pParent)
3886	{
3887	kHlpAssert(off > 1);
3888	kHlpAssert(pAncestor != NULL);
3889	kHlpAssert(pAncestor->Obj.cwcName > 0);
3890	pwszPath[--off] = wcSlash;
3891	off -= pAncestor->Obj.cwcName;
3892	kHlpAssert(pAncestor->Obj.cwcParent == off);
3893	memcpy(&pwszPath[off], pAncestor->Obj.pwszName, pAncestor->Obj.cwcName * sizeof(wchar_t));
3894	}
3895	return K_TRUE;
3896	}
3897	}
3898	else
3899	{
3900	KBOOL const fDriveLetter = pObj->cchName == 2 && pObj->pszName[2] == ':';
3901	off = pObj->cwcName;
3902	if (off + fDriveLetter < cwcPath)
3903	{
3904	memcpy(pwszPath, pObj->pwszName, off * sizeof(wchar_t));
3905	if (fDriveLetter)
3906	pwszPath[off++] = wcSlash;
3907	pwszPath[off] = '\0';
3908	return K_TRUE;
3909	}
3910	}
3911
3912	return K_FALSE;
3913	}
3914
3915
3916	#ifdef KFSCACHE_CFG_SHORT_NAMES
3917
3918	/**
3919	* Gets the full short path to @a pObj, ANSI version.
3920	*
3921	* @returns K_TRUE on success, K_FALSE on buffer overflow (nothing stored).
3922	* @param pObj The object to get the full path to.
3923	* @param pszPath Where to return the path
3924	* @param cbPath The size of the output buffer.
3925	* @param chSlash The slash to use.
3926	*/
3927	KBOOL kFsCacheObjGetFullShortPathA(PKFSOBJ pObj, char *pszPath, KSIZE cbPath, char chSlash)
3928	{
3929	KSIZE off = pObj->cchShortParent;
3930	kHlpAssert(pObj->u32Magic == KFSOBJ_MAGIC);
3931	if (off > 0)
3932	{
3933	KSIZE offEnd = off + pObj->cchShortName;
3934	if (offEnd < cbPath)
3935	{
3936	PKFSDIR pAncestor;
3937
3938	pszPath[off + pObj->cchShortName] = '\0';
3939	memcpy(&pszPath[off], pObj->pszShortName, pObj->cchShortName);
3940
3941	for (pAncestor = pObj->pParent; off > 0; pAncestor = pAncestor->Obj.pParent)
3942	{
3943	kHlpAssert(off > 1);
3944	kHlpAssert(pAncestor != NULL);
3945	kHlpAssert(pAncestor->Obj.cchShortName > 0);
3946	pszPath[--off] = chSlash;
3947	off -= pAncestor->Obj.cchShortName;
3948	kHlpAssert(pAncestor->Obj.cchShortParent == off);
3949	memcpy(&pszPath[off], pAncestor->Obj.pszShortName, pAncestor->Obj.cchShortName);
3950	}
3951	return K_TRUE;
3952	}
3953	}
3954	else
3955	{
3956	KBOOL const fDriveLetter = pObj->cchShortName == 2 && pObj->pszShortName[2] == ':';
3957	off = pObj->cchShortName;
3958	if (off + fDriveLetter < cbPath)
3959	{
3960	memcpy(pszPath, pObj->pszShortName, off);
3961	if (fDriveLetter)
3962	pszPath[off++] = chSlash;
3963	pszPath[off] = '\0';
3964	return K_TRUE;
3965	}
3966	}
3967
3968	return K_FALSE;
3969	}
3970
3971
3972	/**
3973	* Gets the full short path to @a pObj, UTF-16 version.
3974	*
3975	* @returns K_TRUE on success, K_FALSE on buffer overflow (nothing stored).
3976	* @param pObj The object to get the full path to.
3977	* @param pszPath Where to return the path
3978	* @param cbPath The size of the output buffer.
3979	* @param wcSlash The slash to use.
3980	*/
3981	KBOOL kFsCacheObjGetFullShortPathW(PKFSOBJ pObj, wchar_t *pwszPath, KSIZE cwcPath, wchar_t wcSlash)
3982	{
3983	KSIZE off = pObj->cwcShortParent;
3984	kHlpAssert(pObj->u32Magic == KFSOBJ_MAGIC);
3985	if (off > 0)
3986	{
3987	KSIZE offEnd = off + pObj->cwcShortName;
3988	if (offEnd < cwcPath)
3989	{
3990	PKFSDIR pAncestor;
3991
3992	pwszPath[off + pObj->cwcShortName] = '\0';
3993	memcpy(&pwszPath[off], pObj->pwszShortName, pObj->cwcShortName * sizeof(wchar_t));
3994
3995	for (pAncestor = pObj->pParent; off > 0; pAncestor = pAncestor->Obj.pParent)
3996	{
3997	kHlpAssert(off > 1);
3998	kHlpAssert(pAncestor != NULL);
3999	kHlpAssert(pAncestor->Obj.cwcShortName > 0);
4000	pwszPath[--off] = wcSlash;
4001	off -= pAncestor->Obj.cwcShortName;
4002	kHlpAssert(pAncestor->Obj.cwcShortParent == off);
4003	memcpy(&pwszPath[off], pAncestor->Obj.pwszShortName, pAncestor->Obj.cwcShortName * sizeof(wchar_t));
4004	}
4005	return K_TRUE;
4006	}
4007	}
4008	else
4009	{
4010	KBOOL const fDriveLetter = pObj->cchShortName == 2 && pObj->pszShortName[2] == ':';
4011	off = pObj->cwcShortName;
4012	if (off + fDriveLetter < cwcPath)
4013	{
4014	memcpy(pwszPath, pObj->pwszShortName, off * sizeof(wchar_t));
4015	if (fDriveLetter)
4016	pwszPath[off++] = wcSlash;
4017	pwszPath[off] = '\0';
4018	return K_TRUE;
4019	}
4020	}
4021
4022	return K_FALSE;
4023	}
4024
4025	#endif /* KFSCACHE_CFG_SHORT_NAMES */
4026
4027
4028
4029	/**
4030	* Read the specified bits from the files into the given buffer, simple version.
4031	*
4032	* @returns K_TRUE on success (all requested bytes read),
4033	* K_FALSE on any kind of failure.
4034	*
4035	* @param pCache The cache.
4036	* @param pFileObj The file object.
4037	* @param offStart Where to start reading.
4038	* @param pvBuf Where to store what we read.
4039	* @param cbToRead How much to read (exact).
4040	*/
4041	KBOOL kFsCacheFileSimpleOpenReadClose(PKFSCACHE pCache, PKFSOBJ pFileObj, KU64 offStart, void *pvBuf, KSIZE cbToRead)
4042	{
4043	/*
4044	* Open the file relative to the parent directory.
4045	*/
4046	MY_NTSTATUS rcNt;
4047	HANDLE hFile;
4048	MY_IO_STATUS_BLOCK Ios;
4049	MY_OBJECT_ATTRIBUTES ObjAttr;
4050	MY_UNICODE_STRING UniStr;
4051
4052	kHlpAssertReturn(pFileObj->bObjType == KFSOBJ_TYPE_FILE, K_FALSE);
4053	kHlpAssert(pFileObj->pParent);
4054	kHlpAssertReturn(pFileObj->pParent->hDir != INVALID_HANDLE_VALUE, K_FALSE);
4055	kHlpAssertReturn(offStart == 0, K_FALSE); /** @todo when needed */
4056
4057	Ios.Information = -1;
4058	Ios.u.Status = -1;
4059
4060	UniStr.Buffer = (wchar_t *)pFileObj->pwszName;
4061	UniStr.Length = (USHORT)(pFileObj->cwcName * sizeof(wchar_t));
4062	UniStr.MaximumLength = UniStr.Length + sizeof(wchar_t);
4063
4064	MyInitializeObjectAttributes(&ObjAttr, &UniStr, OBJ_CASE_INSENSITIVE, pFileObj->pParent->hDir, NULL /pSecAttr/);
4065
4066	rcNt = g_pfnNtCreateFile(&hFile,
4067	GENERIC_READ \| SYNCHRONIZE,
4068	&ObjAttr,
4069	&Ios,
4070	NULL, /cbFileInitialAlloc /
4071	FILE_ATTRIBUTE_NORMAL,
4072	FILE_SHARE_READ,
4073	FILE_OPEN,
4074	FILE_NON_DIRECTORY_FILE \| FILE_SYNCHRONOUS_IO_NONALERT,
4075	NULL, /pEaBuffer/
4076	0); /cbEaBuffer/
4077	if (MY_NT_SUCCESS(rcNt))
4078	{
4079	LARGE_INTEGER offFile;
4080	offFile.QuadPart = offStart;
4081
4082	Ios.Information = -1;
4083	Ios.u.Status = -1;
4084	rcNt = g_pfnNtReadFile(hFile, NULL /hEvent/, NULL /pfnApcComplete/, NULL /pvApcCtx/, &Ios,
4085	pvBuf, (KU32)cbToRead, !offStart ? &offFile : NULL, NULL /puKey/);
4086	if (MY_NT_SUCCESS(rcNt))
4087	rcNt = Ios.u.Status;
4088	if (MY_NT_SUCCESS(rcNt))
4089	{
4090	if (Ios.Information == cbToRead)
4091	{
4092	g_pfnNtClose(hFile);
4093	return K_TRUE;
4094	}
4095	KFSCACHE_LOG(("Error reading %#x bytes from '%ls': Information=%p\n", pFileObj->pwszName, Ios.Information));
4096	}
4097	else
4098	KFSCACHE_LOG(("Error reading %#x bytes from '%ls': %#x\n", pFileObj->pwszName, rcNt));
4099	g_pfnNtClose(hFile);
4100	}
4101	else
4102	KFSCACHE_LOG(("Error opening '%ls' for caching: %#x\n", pFileObj->pwszName, rcNt));
4103	return K_FALSE;
4104	}
4105
4106
4107	/**
4108	* Invalidate all cache entries of missing files.
4109	*
4110	* @param pCache The cache.
4111	*/
4112	void kFsCacheInvalidateMissing(PKFSCACHE pCache)
4113	{
4114	kHlpAssert(pCache->u32Magic == KFSOBJ_MAGIC);
4115	pCache->auGenerationsMissing[0]++;
4116	kHlpAssert(pCache->uGenerationMissing < KU32_MAX);
4117	KFSCACHE_LOG(("Invalidate missing %#x\n", pCache->auGenerationsMissing[0]));
4118	}
4119
4120
4121	/**
4122	* Invalidate all cache entries (regular, custom & missing).
4123	*
4124	* @param pCache The cache.
4125	*/
4126	void kFsCacheInvalidateAll(PKFSCACHE pCache)
4127	{
4128	kHlpAssert(pCache->u32Magic == KFSOBJ_MAGIC);
4129
4130	pCache->auGenerationsMissing[0]++;
4131	kHlpAssert(pCache->auGenerationsMissing[0] < KU32_MAX);
4132	pCache->auGenerationsMissing[1]++;
4133	kHlpAssert(pCache->auGenerationsMissing[1] < KU32_MAX);
4134
4135	pCache->auGenerations[0]++;
4136	kHlpAssert(pCache->auGenerations[0] < KU32_MAX);
4137	pCache->auGenerations[1]++;
4138	kHlpAssert(pCache->auGenerations[1] < KU32_MAX);
4139
4140	KFSCACHE_LOG(("Invalidate all - default: %#x/%#x, custom: %#x/%#x\n",
4141	pCache->auGenerationsMissing[0], pCache->auGenerations[0],
4142	pCache->auGenerationsMissing[1], pCache->auGenerations[1]));
4143	}
4144
4145
4146	/**
4147	* Invalidate all cache entries with custom generation handling set.
4148	*
4149	* @see kFsCacheSetupCustomRevisionForTree, KFSOBJ_F_USE_CUSTOM_GEN
4150	* @param pCache The cache.
4151	*/
4152	void kFsCacheInvalidateCustomMissing(PKFSCACHE pCache)
4153	{
4154	kHlpAssert(pCache->u32Magic == KFSOBJ_MAGIC);
4155	pCache->auGenerationsMissing[1]++;
4156	kHlpAssert(pCache->auGenerationsMissing[1] < KU32_MAX);
4157	KFSCACHE_LOG(("Invalidate missing custom %#x\n", pCache->auGenerationsMissing[1]));
4158	}
4159
4160
4161	/**
4162	* Invalidate all cache entries with custom generation handling set, both
4163	* missing and regular present entries.
4164	*
4165	* @see kFsCacheSetupCustomRevisionForTree, KFSOBJ_F_USE_CUSTOM_GEN
4166	* @param pCache The cache.
4167	*/
4168	void kFsCacheInvalidateCustomBoth(PKFSCACHE pCache)
4169	{
4170	kHlpAssert(pCache->u32Magic == KFSOBJ_MAGIC);
4171	pCache->auGenerations[1]++;
4172	kHlpAssert(pCache->auGenerations[1] < KU32_MAX);
4173	pCache->auGenerationsMissing[1]++;
4174	kHlpAssert(pCache->auGenerationsMissing[1] < KU32_MAX);
4175	KFSCACHE_LOG(("Invalidate both custom %#x/%#x\n", pCache->auGenerationsMissing[1], pCache->auGenerations[1]));
4176	}
4177
4178
4179
4180	/**
4181	* Applies the given flags to all the objects in a tree.
4182	*
4183	* @param pRoot Where to start applying the flag changes.
4184	* @param fAndMask The AND mask.
4185	* @param fOrMask The OR mask.
4186	*/
4187	static void kFsCacheApplyFlagsToTree(PKFSDIR pRoot, KU32 fAndMask, KU32 fOrMask)
4188	{
4189	PKFSOBJ *ppCur = ((PKFSDIR)pRoot)->papChildren;
4190	KU32 cLeft = ((PKFSDIR)pRoot)->cChildren;
4191	while (cLeft-- > 0)
4192	{
4193	PKFSOBJ pCur = *ppCur++;
4194	if (pCur->bObjType != KFSOBJ_TYPE_DIR)
4195	pCur->fFlags = (fAndMask & pCur->fFlags) \| fOrMask;
4196	else
4197	kFsCacheApplyFlagsToTree((PKFSDIR)pCur, fAndMask, fOrMask);
4198	}
4199
4200	pRoot->Obj.fFlags = (fAndMask & pRoot->Obj.fFlags) \| fOrMask;
4201	}
4202
4203
4204	/**
4205	* Sets up using custom revisioning for the specified directory tree or file.
4206	*
4207	* There are some restrictions of the current implementation:
4208	* - If the root of the sub-tree is ever deleted from the cache (i.e.
4209	* deleted in real life and reflected in the cache), the setting is lost.
4210	* - It is not automatically applied to the lookup paths caches.
4211	*
4212	* @returns K_TRUE on success, K_FALSE on failure.
4213	* @param pCache The cache.
4214	* @param pRoot The root of the subtree. A non-directory is
4215	* fine, like a missing node.
4216	*/
4217	KBOOL kFsCacheSetupCustomRevisionForTree(PKFSCACHE pCache, PKFSOBJ pRoot)
4218	{
4219	if (pRoot)
4220	{
4221	if (pRoot->bObjType == KFSOBJ_TYPE_DIR)
4222	kFsCacheApplyFlagsToTree((PKFSDIR)pRoot, KU32_MAX, KFSOBJ_F_USE_CUSTOM_GEN);
4223	else
4224	pRoot->fFlags \|= KFSOBJ_F_USE_CUSTOM_GEN;
4225	return K_TRUE;
4226	}
4227	return K_FALSE;
4228	}
4229
4230
4231	/**
4232	* Invalidates a deleted directory, ANSI version.
4233	*
4234	* @returns K_TRUE if found and is a non-root directory. Otherwise K_FALSE.
4235	* @param pCache The cache.
4236	* @param pszDir The directory.
4237	*/
4238	KBOOL kFsCacheInvalidateDeletedDirectoryA(PKFSCACHE pCache, const char *pszDir)
4239	{
4240	KU32 cchDir = (KU32)kHlpStrLen(pszDir);
4241	KFSLOOKUPERROR enmError;
4242	PKFSOBJ pFsObj;
4243
4244	/* Is absolute without any '..' bits? */
4245	if ( cchDir >= 3
4246	&& ( ( pszDir[1] == ':' /* Drive letter */
4247	&& IS_SLASH(pszDir[2])
4248	&& IS_ALPHA(pszDir[0]) )
4249	\|\| ( IS_SLASH(pszDir[0]) /* UNC */
4250	&& IS_SLASH(pszDir[1]) ) )
4251	&& !kFsCacheHasDotDotA(pszDir, cchDir) )
4252	pFsObj = kFsCacheLookupAbsoluteA(pCache, pszDir, cchDir, KFSCACHE_LOOKUP_F_NO_INSERT \| KFSCACHE_LOOKUP_F_NO_REFRESH,
4253	&enmError, NULL);
4254	else
4255	pFsObj = kFsCacheLookupSlowA(pCache, pszDir, cchDir, KFSCACHE_LOOKUP_F_NO_INSERT \| KFSCACHE_LOOKUP_F_NO_REFRESH,
4256	&enmError, NULL);
4257	if (pFsObj)
4258	{
4259	/* Is directory? */
4260	if (pFsObj->bObjType == KFSOBJ_TYPE_DIR)
4261	{
4262	if (pFsObj->pParent != &pCache->RootDir)
4263	{
4264	PKFSDIR pDir = (PKFSDIR)pFsObj;
4265	KFSCACHE_LOG(("kFsCacheInvalidateDeletedDirectoryA: %s hDir=%p\n", pszDir, pDir->hDir));
4266	if (pDir->hDir != INVALID_HANDLE_VALUE)
4267	{
4268	g_pfnNtClose(pDir->hDir);
4269	pDir->hDir = INVALID_HANDLE_VALUE;
4270	}
4271	pDir->fNeedRePopulating = K_TRUE;
4272	pDir->Obj.uCacheGen = pCache->auGenerations[pDir->Obj.fFlags & KFSOBJ_F_USE_CUSTOM_GEN] - 1;
4273	kFsCacheObjRetainInternal(&pDir->Obj);
4274	return K_TRUE;
4275	}
4276	KFSCACHE_LOG(("kFsCacheInvalidateDeletedDirectoryA: Trying to invalidate a root directory was deleted! %s\n", pszDir));
4277	}
4278	else
4279	KFSCACHE_LOG(("kFsCacheInvalidateDeletedDirectoryA: Trying to invalidate a non-directory: bObjType=%d %s\n",
4280	pFsObj->bObjType, pszDir));
4281	kFsCacheObjRetainInternal(pFsObj);
4282	}
4283	else
4284	KFSCACHE_LOG(("kFsCacheInvalidateDeletedDirectoryA: '%s' was not found\n", pszDir));
4285	return K_FALSE;
4286	}
4287
4288
4289	PKFSCACHE kFsCacheCreate(KU32 fFlags)
4290	{
4291	PKFSCACHE pCache;
4292	birdResolveImports();
4293
4294	pCache = (PKFSCACHE)kHlpAllocZ(sizeof(*pCache));
4295	if (pCache)
4296	{
4297	/* Dummy root dir entry. */
4298	pCache->RootDir.Obj.u32Magic = KFSOBJ_MAGIC;
4299	pCache->RootDir.Obj.cRefs = 1;
4300	pCache->RootDir.Obj.uCacheGen = KFSOBJ_CACHE_GEN_IGNORE;
4301	pCache->RootDir.Obj.bObjType = KFSOBJ_TYPE_DIR;
4302	pCache->RootDir.Obj.fHaveStats = K_FALSE;
4303	pCache->RootDir.Obj.pParent = NULL;
4304	pCache->RootDir.Obj.pszName = "";
4305	pCache->RootDir.Obj.cchName = 0;
4306	pCache->RootDir.Obj.cchParent = 0;
4307	#ifdef KFSCACHE_CFG_UTF16
4308	pCache->RootDir.Obj.cwcName = 0;
4309	pCache->RootDir.Obj.cwcParent = 0;
4310	pCache->RootDir.Obj.pwszName = L"";
4311	#endif
4312
4313	#ifdef KFSCACHE_CFG_SHORT_NAMES
4314	pCache->RootDir.Obj.pszShortName = NULL;
4315	pCache->RootDir.Obj.cchShortName = 0;
4316	pCache->RootDir.Obj.cchShortParent = 0;
4317	# ifdef KFSCACHE_CFG_UTF16
4318	pCache->RootDir.Obj.cwcShortName;
4319	pCache->RootDir.Obj.cwcShortParent;
4320	pCache->RootDir.Obj.pwszShortName;
4321	# endif
4322	#endif
4323	pCache->RootDir.cChildren = 0;
4324	pCache->RootDir.cChildrenAllocated = 0;
4325	pCache->RootDir.papChildren = NULL;
4326	pCache->RootDir.hDir = INVALID_HANDLE_VALUE;
4327	pCache->RootDir.fHashTabMask = 255; /* 256: 26 drive letters and 102 UNCs before we're half ways. */
4328	pCache->RootDir.papHashTab = (PKFSOBJ )kHlpAllocZ(256 sizeof(pCache->RootDir.papHashTab[0]));
4329	if (pCache->RootDir.papHashTab)
4330	{
4331	/* The cache itself. */
4332	pCache->u32Magic = KFSCACHE_MAGIC;
4333	pCache->fFlags = fFlags;
4334	pCache->auGenerations[0] = KU32_MAX / 4;
4335	pCache->auGenerations[1] = KU32_MAX / 32;
4336	pCache->auGenerationsMissing[0] = KU32_MAX / 256;
4337	pCache->auGenerationsMissing[1] = 1;
4338	pCache->cObjects = 1;
4339	pCache->cbObjects = sizeof(pCache->RootDir)
4340	+ (pCache->RootDir.fHashTabMask + 1) * sizeof(pCache->RootDir.papHashTab[0]);
4341	pCache->cPathHashHits = 0;
4342	pCache->cWalkHits = 0;
4343	pCache->cChildSearches = 0;
4344	pCache->cChildHashHits = 0;
4345	pCache->cChildHashed = 0;
4346	pCache->cChildHashTabs = 1;
4347	pCache->cChildHashEntriesTotal = pCache->RootDir.fHashTabMask + 1;
4348	pCache->cChildHashCollisions = 0;
4349	pCache->cAnsiPaths = 0;
4350	pCache->cAnsiPathCollisions = 0;
4351	pCache->cbAnsiPaths = 0;
4352	#ifdef KFSCACHE_CFG_UTF16
4353	pCache->cUtf16Paths = 0;
4354	pCache->cUtf16PathCollisions = 0;
4355	pCache->cbUtf16Paths = 0;
4356	#endif
4357	return pCache;
4358	}
4359
4360	kHlpFree(pCache);
4361	}
4362	return NULL;
4363	}
4364

Note: See TracBrowser for help on using the repository browser.

source: kBuild/trunk/src/lib/nt/kFsCache.c@ 2930

Download in other formats: