kFsCache.c@ 2940

Last change on this file since 2940 was 2940, checked in by bird, 9 years ago
kWorker: Fixed busted read-only caching, checking out using memory mapped files for it. Made the CreateFileW interceptor not callCreateFileA for read-only cached files. Deal with ?\ prefixed paths (long paths) and other moc.exe related fixes.
Property svn:eol-style set to `native` Property svn:keywords set to `Id`
File size: 162.2 KB

Line
1	/* $Id: kFsCache.c 2940 2016-09-19 18:34:43Z bird $ */
2	/** @file
3	* ntdircache.c - NT directory content cache.
4	*/
5
6	/*
7	* Copyright (c) 2016 knut st. osmundsen <[email protected]>
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	/*
2460	* Special case: Long path prefix w/ drive letter following it.
2461	* Note! Must've been converted from wide char to ANSI.
2462	*/
2463	if ( IS_SLASH(pszPath[0])
2464	&& IS_SLASH(pszPath[1])
2465	&& pszPath[2] == '?'
2466	&& IS_SLASH(pszPath[3])
2467	&& IS_ALPHA(pszPath[4])
2468	&& pszPath[5] == ':'
2469	&& IS_SLASH(pszPath[6]) )
2470	{
2471	*poff = 4 + 2;
2472	return kFsCacheLookupDrive(pCache, pszPath[4], fFlags, penmError);
2473	}
2474
2475	#if 0 /* later */
2476	KU32 offStartServer;
2477	KU32 offEndServer;
2478	KU32 offStartShare;
2479
2480	KU32 offEnd = 2;
2481	while (IS_SLASH(pszPath[offEnd]))
2482	offEnd++;
2483
2484	offStartServer = offEnd;
2485	while ( (ch = pszPath[offEnd]) != '\0'
2486	&& !IS_SLASH(ch))
2487	offEnd++;
2488	offEndServer = offEnd;
2489
2490	if (ch != '\0')
2491	{ /* likely */ }
2492	else
2493	{
2494	*penmError = KFSLOOKUPERROR_NOT_FOUND;
2495	return NULL;
2496	}
2497
2498	while (IS_SLASH(pszPath[offEnd]))
2499	offEnd++;
2500	offStartServer = offEnd;
2501	while ( (ch = pszPath[offEnd]) != '\0'
2502	&& !IS_SLASH(ch))
2503	offEnd++;
2504	#endif
2505	*penmError = KFSLOOKUPERROR_UNSUPPORTED;
2506	return NULL;
2507	}
2508
2509
2510	/**
2511	* Looks up a UNC share, UTF-16 version.
2512	*
2513	* We keep both the server and share in the root directory entry. This means we
2514	* have to clean up the entry name before we can insert it.
2515	*
2516	* @returns Pointer to the share root directory or an update-to-date missing
2517	* node.
2518	* @param pCache The cache.
2519	* @param pwszPath The path.
2520	* @param fFlags Lookup flags, KFSCACHE_LOOKUP_F_XXX.
2521	* @param poff Where to return the root dir.
2522	* @param penmError Where to return details as to why the lookup
2523	* failed.
2524	*/
2525	static PKFSOBJ kFsCacheLookupUncShareW(PKFSCACHE pCache, const wchar_t *pwszPath, KU32 fFlags,
2526	KU32 poff, KFSLOOKUPERROR penmError)
2527	{
2528	/*
2529	* Special case: Long path prefix w/ drive letter following it.
2530	*/
2531	if ( IS_SLASH(pwszPath[0])
2532	&& IS_SLASH(pwszPath[1])
2533	&& pwszPath[2] == '?'
2534	&& IS_SLASH(pwszPath[3])
2535	&& IS_ALPHA(pwszPath[4])
2536	&& pwszPath[5] == ':'
2537	&& IS_SLASH(pwszPath[6]) )
2538	{
2539	*poff = 4 + 2;
2540	return kFsCacheLookupDrive(pCache, (char)pwszPath[4], fFlags, penmError);
2541	}
2542
2543
2544	#if 0 /* later */
2545	KU32 offStartServer;
2546	KU32 offEndServer;
2547	KU32 offStartShare;
2548
2549	KU32 offEnd = 2;
2550	while (IS_SLASH(pwszPath[offEnd]))
2551	offEnd++;
2552
2553	offStartServer = offEnd;
2554	while ( (ch = pwszPath[offEnd]) != '\0'
2555	&& !IS_SLASH(ch))
2556	offEnd++;
2557	offEndServer = offEnd;
2558
2559	if (ch != '\0')
2560	{ /* likely */ }
2561	else
2562	{
2563	*penmError = KFSLOOKUPERROR_NOT_FOUND;
2564	return NULL;
2565	}
2566
2567	while (IS_SLASH(pwszPath[offEnd]))
2568	offEnd++;
2569	offStartServer = offEnd;
2570	while ( (ch = pwszPath[offEnd]) != '\0'
2571	&& !IS_SLASH(ch))
2572	offEnd++;
2573	#endif
2574	*penmError = KFSLOOKUPERROR_UNSUPPORTED;
2575	return NULL;
2576	}
2577
2578
2579	/**
2580	* Walks an full path relative to the given directory, ANSI version.
2581	*
2582	* This will create any missing nodes while walking.
2583	*
2584	* The caller will have to do the path hash table insertion of the result.
2585	*
2586	* @returns Pointer to the tree node corresponding to @a pszPath.
2587	* NULL on lookup failure, see @a penmError for details.
2588	* @param pCache The cache.
2589	* @param pParent The directory to start the lookup in.
2590	* @param pszPath The path to walk.
2591	* @param cchPath The length of the path.
2592	* @param fFlags Lookup flags, KFSCACHE_LOOKUP_F_XXX.
2593	* @param penmError Where to return details as to why the lookup
2594	* failed.
2595	* @param ppLastAncestor Where to return the last parent element found
2596	* (referenced) in case of error an path/file not
2597	* found problem. Optional.
2598	*/
2599	PKFSOBJ kFsCacheLookupRelativeToDirA(PKFSCACHE pCache, PKFSDIR pParent, const char *pszPath, KU32 cchPath, KU32 fFlags,
2600	KFSLOOKUPERROR penmError, PKFSOBJ ppLastAncestor)
2601	{
2602	/*
2603	* Walk loop.
2604	*/
2605	KU32 off = 0;
2606	if (ppLastAncestor)
2607	*ppLastAncestor = NULL;
2608	for (;;)
2609	{
2610	PKFSOBJ pChild;
2611
2612	/*
2613	* Find the end of the component, counting trailing slashes.
2614	*/
2615	char ch;
2616	KU32 cchSlashes = 0;
2617	KU32 offEnd = off + 1;
2618	while ((ch = pszPath[offEnd]) != '\0')
2619	{
2620	if (!IS_SLASH(ch))
2621	offEnd++;
2622	else
2623	{
2624	do
2625	cchSlashes++;
2626	while (IS_SLASH(pszPath[offEnd + cchSlashes]));
2627	break;
2628	}
2629	}
2630
2631	/*
2632	* Do we need to populate or refresh this directory first?
2633	*/
2634	if ( !pParent->fNeedRePopulating
2635	&& pParent->fPopulated
2636	&& ( pParent->Obj.uCacheGen == KFSOBJ_CACHE_GEN_IGNORE
2637	\|\| pParent->Obj.uCacheGen == pCache->auGenerations[pParent->Obj.fFlags & KFSOBJ_F_USE_CUSTOM_GEN]) )
2638	{ /* likely */ }
2639	else if ( (fFlags & (KFSCACHE_LOOKUP_F_NO_INSERT \| fFlags & KFSCACHE_LOOKUP_F_NO_REFRESH))
2640	\|\| kFsCachePopuplateOrRefreshDir(pCache, pParent, penmError))
2641	{ /* likely */ }
2642	else
2643	return NULL;
2644
2645	/*
2646	* Search the current node for the name.
2647	*
2648	* If we don't find it, we may insert a missing node depending on
2649	* the cache configuration.
2650	*/
2651	pChild = kFsCacheFindChildA(pCache, pParent, &pszPath[off], offEnd - off);
2652	if (pChild != NULL)
2653	{ /* probably likely */ }
2654	else
2655	{
2656	if ( (pCache->fFlags & KFSCACHE_F_MISSING_OBJECTS)
2657	&& !(fFlags & KFSCACHE_LOOKUP_F_NO_INSERT))
2658	pChild = kFsCacheCreateMissingA(pCache, pParent, &pszPath[off], offEnd - off, penmError);
2659	if (cchSlashes == 0 \|\| offEnd + cchSlashes >= cchPath)
2660	{
2661	if (pChild)
2662	return kFsCacheObjRetainInternal(pChild);
2663	*penmError = KFSLOOKUPERROR_NOT_FOUND;
2664	}
2665	else
2666	*penmError = KFSLOOKUPERROR_PATH_COMP_NOT_FOUND;
2667	if (ppLastAncestor)
2668	*ppLastAncestor = kFsCacheObjRetainInternal(&pParent->Obj);
2669	return NULL;
2670	}
2671
2672	/* Advance off and check if we're done already. */
2673	off = offEnd + cchSlashes;
2674	if ( cchSlashes == 0
2675	\|\| off >= cchPath)
2676	{
2677	if ( pChild->bObjType != KFSOBJ_TYPE_MISSING
2678	\|\| pChild->uCacheGen == KFSOBJ_CACHE_GEN_IGNORE
2679	\|\| pChild->uCacheGen == pCache->auGenerationsMissing[pChild->fFlags & KFSOBJ_F_USE_CUSTOM_GEN]
2680	\|\| (fFlags & KFSCACHE_LOOKUP_F_NO_REFRESH)
2681	\|\| kFsCacheRefreshMissing(pCache, pChild, penmError) )
2682	{ /* likely */ }
2683	else
2684	return NULL;
2685	return kFsCacheObjRetainInternal(pChild);
2686	}
2687
2688	/*
2689	* Check that it's a directory. If a missing entry, we may have to
2690	* refresh it and re-examin it.
2691	*/
2692	if (pChild->bObjType == KFSOBJ_TYPE_DIR)
2693	pParent = (PKFSDIR)pChild;
2694	else if (pChild->bObjType != KFSOBJ_TYPE_MISSING)
2695	{
2696	*penmError = KFSLOOKUPERROR_PATH_COMP_NOT_DIR;
2697	if (ppLastAncestor)
2698	*ppLastAncestor = kFsCacheObjRetainInternal(&pParent->Obj);
2699	return NULL;
2700	}
2701	else if ( pChild->uCacheGen == KFSOBJ_CACHE_GEN_IGNORE
2702	\|\| pChild->uCacheGen == pCache->auGenerationsMissing[pChild->fFlags & KFSOBJ_F_USE_CUSTOM_GEN]
2703	\|\| (fFlags & KFSCACHE_LOOKUP_F_NO_REFRESH))
2704	{
2705	*penmError = KFSLOOKUPERROR_PATH_COMP_NOT_FOUND;
2706	if (ppLastAncestor)
2707	*ppLastAncestor = kFsCacheObjRetainInternal(&pParent->Obj);
2708	return NULL;
2709	}
2710	else if (kFsCacheRefreshMissingIntermediateDir(pCache, pChild, penmError))
2711	pParent = (PKFSDIR)pChild;
2712	else
2713	{
2714	if (ppLastAncestor)
2715	*ppLastAncestor = kFsCacheObjRetainInternal(&pParent->Obj);
2716	return NULL;
2717	}
2718	}
2719
2720	return NULL;
2721
2722	}
2723
2724
2725	/**
2726	* Walks an full path relative to the given directory, UTF-16 version.
2727	*
2728	* This will create any missing nodes while walking.
2729	*
2730	* The caller will have to do the path hash table insertion of the result.
2731	*
2732	* @returns Pointer to the tree node corresponding to @a pszPath.
2733	* NULL on lookup failure, see @a penmError for details.
2734	* @param pCache The cache.
2735	* @param pParent The directory to start the lookup in.
2736	* @param pszPath The path to walk. No dot-dot bits allowed!
2737	* @param cchPath The length of the path.
2738	* @param fFlags Lookup flags, KFSCACHE_LOOKUP_F_XXX.
2739	* @param penmError Where to return details as to why the lookup
2740	* failed.
2741	* @param ppLastAncestor Where to return the last parent element found
2742	* (referenced) in case of error an path/file not
2743	* found problem. Optional.
2744	*/
2745	PKFSOBJ kFsCacheLookupRelativeToDirW(PKFSCACHE pCache, PKFSDIR pParent, const wchar_t *pwszPath, KU32 cwcPath, KU32 fFlags,
2746	KFSLOOKUPERROR penmError, PKFSOBJ ppLastAncestor)
2747	{
2748	/*
2749	* Walk loop.
2750	*/
2751	KU32 off = 0;
2752	if (ppLastAncestor)
2753	*ppLastAncestor = NULL;
2754	for (;;)
2755	{
2756	PKFSOBJ pChild;
2757
2758	/*
2759	* Find the end of the component, counting trailing slashes.
2760	*/
2761	wchar_t wc;
2762	KU32 cwcSlashes = 0;
2763	KU32 offEnd = off + 1;
2764	while ((wc = pwszPath[offEnd]) != '\0')
2765	{
2766	if (!IS_SLASH(wc))
2767	offEnd++;
2768	else
2769	{
2770	do
2771	cwcSlashes++;
2772	while (IS_SLASH(pwszPath[offEnd + cwcSlashes]));
2773	break;
2774	}
2775	}
2776
2777	/*
2778	* Do we need to populate or refresh this directory first?
2779	*/
2780	if ( !pParent->fNeedRePopulating
2781	&& pParent->fPopulated
2782	&& ( pParent->Obj.uCacheGen == KFSOBJ_CACHE_GEN_IGNORE
2783	\|\| pParent->Obj.uCacheGen == pCache->auGenerations[pParent->Obj.fFlags & KFSOBJ_F_USE_CUSTOM_GEN]) )
2784	{ /* likely */ }
2785	else if ( (fFlags & (KFSCACHE_LOOKUP_F_NO_INSERT \| fFlags & KFSCACHE_LOOKUP_F_NO_REFRESH))
2786	\|\| kFsCachePopuplateOrRefreshDir(pCache, pParent, penmError))
2787	{ /* likely */ }
2788	else
2789	return NULL;
2790
2791	/*
2792	* Search the current node for the name.
2793	*
2794	* If we don't find it, we may insert a missing node depending on
2795	* the cache configuration.
2796	*/
2797	pChild = kFsCacheFindChildW(pCache, pParent, &pwszPath[off], offEnd - off);
2798	if (pChild != NULL)
2799	{ /* probably likely */ }
2800	else
2801	{
2802	if ( (pCache->fFlags & KFSCACHE_F_MISSING_OBJECTS)
2803	&& !(fFlags & KFSCACHE_LOOKUP_F_NO_INSERT))
2804	pChild = kFsCacheCreateMissingW(pCache, pParent, &pwszPath[off], offEnd - off, penmError);
2805	if (cwcSlashes == 0 \|\| offEnd + cwcSlashes >= cwcPath)
2806	{
2807	if (pChild)
2808	return kFsCacheObjRetainInternal(pChild);
2809	*penmError = KFSLOOKUPERROR_NOT_FOUND;
2810	}
2811	else
2812	*penmError = KFSLOOKUPERROR_PATH_COMP_NOT_FOUND;
2813	if (ppLastAncestor)
2814	*ppLastAncestor = kFsCacheObjRetainInternal(&pParent->Obj);
2815	return NULL;
2816	}
2817
2818	/* Advance off and check if we're done already. */
2819	off = offEnd + cwcSlashes;
2820	if ( cwcSlashes == 0
2821	\|\| off >= cwcPath)
2822	{
2823	if ( pChild->bObjType != KFSOBJ_TYPE_MISSING
2824	\|\| pChild->uCacheGen == KFSOBJ_CACHE_GEN_IGNORE
2825	\|\| pChild->uCacheGen == pCache->auGenerationsMissing[pChild->fFlags & KFSOBJ_F_USE_CUSTOM_GEN]
2826	\|\| (fFlags & KFSCACHE_LOOKUP_F_NO_REFRESH)
2827	\|\| kFsCacheRefreshMissing(pCache, pChild, penmError) )
2828	{ /* likely */ }
2829	else
2830	return NULL;
2831	return kFsCacheObjRetainInternal(pChild);
2832	}
2833
2834	/*
2835	* Check that it's a directory. If a missing entry, we may have to
2836	* refresh it and re-examin it.
2837	*/
2838	if (pChild->bObjType == KFSOBJ_TYPE_DIR)
2839	pParent = (PKFSDIR)pChild;
2840	else if (pChild->bObjType != KFSOBJ_TYPE_MISSING)
2841	{
2842	*penmError = KFSLOOKUPERROR_PATH_COMP_NOT_DIR;
2843	if (ppLastAncestor)
2844	*ppLastAncestor = kFsCacheObjRetainInternal(&pParent->Obj);
2845	return NULL;
2846	}
2847	else if ( pChild->uCacheGen == KFSOBJ_CACHE_GEN_IGNORE
2848	\|\| pChild->uCacheGen == pCache->auGenerationsMissing[pChild->fFlags & KFSOBJ_F_USE_CUSTOM_GEN]
2849	\|\| (fFlags & KFSCACHE_LOOKUP_F_NO_REFRESH) )
2850
2851	{
2852	*penmError = KFSLOOKUPERROR_PATH_COMP_NOT_FOUND;
2853	if (ppLastAncestor)
2854	*ppLastAncestor = kFsCacheObjRetainInternal(&pParent->Obj);
2855	return NULL;
2856	}
2857	else if (kFsCacheRefreshMissingIntermediateDir(pCache, pChild, penmError))
2858	pParent = (PKFSDIR)pChild;
2859	else
2860	{
2861	if (ppLastAncestor)
2862	*ppLastAncestor = kFsCacheObjRetainInternal(&pParent->Obj);
2863	return NULL;
2864	}
2865	}
2866
2867	return NULL;
2868
2869	}
2870
2871	/**
2872	* Walk the file system tree for the given absolute path, entering it into the
2873	* hash table.
2874	*
2875	* This will create any missing nodes while walking.
2876	*
2877	* The caller will have to do the path hash table insertion of the result.
2878	*
2879	* @returns Pointer to the tree node corresponding to @a pszPath.
2880	* NULL on lookup failure, see @a penmError for details.
2881	* @param pCache The cache.
2882	* @param pszPath The path to walk. No dot-dot bits allowed!
2883	* @param cchPath The length of the path.
2884	* @param fFlags Lookup flags, KFSCACHE_LOOKUP_F_XXX.
2885	* @param penmError Where to return details as to why the lookup
2886	* failed.
2887	* @param ppLastAncestor Where to return the last parent element found
2888	* (referenced) in case of error an path/file not
2889	* found problem. Optional.
2890	*/
2891	static PKFSOBJ kFsCacheLookupAbsoluteA(PKFSCACHE pCache, const char *pszPath, KU32 cchPath, KU32 fFlags,
2892	KFSLOOKUPERROR penmError, PKFSOBJ ppLastAncestor)
2893	{
2894	PKFSOBJ pRoot;
2895	KU32 cchSlashes;
2896	KU32 offEnd;
2897
2898	KFSCACHE_LOG2(("kFsCacheLookupAbsoluteA(%s)\n", pszPath));
2899
2900	/*
2901	* The root "directory" needs special handling, so we keep it outside the
2902	* main search loop. (Special: Cannot enumerate it, UNCs, ++.)
2903	*/
2904	cchSlashes = 0;
2905	if ( pszPath[1] == ':'
2906	&& IS_ALPHA(pszPath[0]))
2907	{
2908	/* Drive letter. */
2909	offEnd = 2;
2910	kHlpAssert(IS_SLASH(pszPath[2]));
2911	pRoot = kFsCacheLookupDrive(pCache, toupper(pszPath[0]), fFlags, penmError);
2912	}
2913	else if ( IS_SLASH(pszPath[0])
2914	&& IS_SLASH(pszPath[1]) )
2915	pRoot = kFsCacheLookupUncShareA(pCache, pszPath, fFlags, &offEnd, penmError);
2916	else
2917	{
2918	*penmError = KFSLOOKUPERROR_UNSUPPORTED;
2919	return NULL;
2920	}
2921	if (pRoot)
2922	{ /* likely */ }
2923	else
2924	return NULL;
2925
2926	/* Count slashes trailing the root spec. */
2927	if (offEnd < cchPath)
2928	{
2929	kHlpAssert(IS_SLASH(pszPath[offEnd]));
2930	do
2931	cchSlashes++;
2932	while (IS_SLASH(pszPath[offEnd + cchSlashes]));
2933	}
2934
2935	/* Done already? */
2936	if (offEnd >= cchPath)
2937	{
2938	if ( pRoot->uCacheGen == KFSOBJ_CACHE_GEN_IGNORE
2939	\|\| pRoot->uCacheGen == ( pRoot->bObjType != KFSOBJ_TYPE_MISSING
2940	? pCache->auGenerations[ pRoot->fFlags & KFSOBJ_F_USE_CUSTOM_GEN]
2941	: pCache->auGenerationsMissing[pRoot->fFlags & KFSOBJ_F_USE_CUSTOM_GEN])
2942	\|\| (fFlags & KFSCACHE_LOOKUP_F_NO_REFRESH)
2943	\|\| kFsCacheRefreshObj(pCache, pRoot, penmError))
2944	return kFsCacheObjRetainInternal(pRoot);
2945	return NULL;
2946	}
2947
2948	/* Check that we've got a valid result and not a cached negative one. */
2949	if (pRoot->bObjType == KFSOBJ_TYPE_DIR)
2950	{ /* likely */ }
2951	else
2952	{
2953	kHlpAssert(pRoot->bObjType == KFSOBJ_TYPE_MISSING);
2954	kHlpAssert( pRoot->uCacheGen == KFSOBJ_CACHE_GEN_IGNORE
2955	\|\| pRoot->uCacheGen == pCache->auGenerationsMissing[pRoot->fFlags & KFSOBJ_F_USE_CUSTOM_GEN]);
2956	return pRoot;
2957	}
2958
2959	/*
2960	* Now that we've found a valid root directory, lookup the
2961	* remainder of the path starting with it.
2962	*/
2963	return kFsCacheLookupRelativeToDirA(pCache, (PKFSDIR)pRoot, &pszPath[offEnd + cchSlashes],
2964	cchPath - offEnd - cchSlashes, fFlags, penmError, ppLastAncestor);
2965	}
2966
2967
2968	/**
2969	* Walk the file system tree for the given absolute path, UTF-16 version.
2970	*
2971	* This will create any missing nodes while walking.
2972	*
2973	* The caller will have to do the path hash table insertion of the result.
2974	*
2975	* @returns Pointer to the tree node corresponding to @a pszPath.
2976	* NULL on lookup failure, see @a penmError for details.
2977	* @param pCache The cache.
2978	* @param pwszPath The path to walk.
2979	* @param cwcPath The length of the path (in wchar_t's).
2980	* @param fFlags Lookup flags, KFSCACHE_LOOKUP_F_XXX.
2981	* @param penmError Where to return details as to why the lookup
2982	* failed.
2983	* @param ppLastAncestor Where to return the last parent element found
2984	* (referenced) in case of error an path/file not
2985	* found problem. Optional.
2986	*/
2987	static PKFSOBJ kFsCacheLookupAbsoluteW(PKFSCACHE pCache, const wchar_t *pwszPath, KU32 cwcPath, KU32 fFlags,
2988	KFSLOOKUPERROR penmError, PKFSOBJ ppLastAncestor)
2989	{
2990	PKFSDIR pParent = &pCache->RootDir;
2991	PKFSOBJ pRoot;
2992	KU32 off;
2993	KU32 cwcSlashes;
2994	KU32 offEnd;
2995
2996	KFSCACHE_LOG2(("kFsCacheLookupAbsoluteW(%ls)\n", pwszPath));
2997
2998	/*
2999	* The root "directory" needs special handling, so we keep it outside the
3000	* main search loop. (Special: Cannot enumerate it, UNCs, ++.)
3001	*/
3002	cwcSlashes = 0;
3003	off = 0;
3004	if ( pwszPath[1] == ':'
3005	&& IS_ALPHA(pwszPath[0]))
3006	{
3007	/* Drive letter. */
3008	offEnd = 2;
3009	kHlpAssert(IS_SLASH(pwszPath[2]));
3010	pRoot = kFsCacheLookupDrive(pCache, toupper(pwszPath[0]), fFlags, penmError);
3011	}
3012	else if ( IS_SLASH(pwszPath[0])
3013	&& IS_SLASH(pwszPath[1]) )
3014	pRoot = kFsCacheLookupUncShareW(pCache, pwszPath, fFlags, &offEnd, penmError);
3015	else
3016	{
3017	*penmError = KFSLOOKUPERROR_UNSUPPORTED;
3018	return NULL;
3019	}
3020	if (pRoot)
3021	{ /* likely */ }
3022	else
3023	return NULL;
3024
3025	/* Count slashes trailing the root spec. */
3026	if (offEnd < cwcPath)
3027	{
3028	kHlpAssert(IS_SLASH(pwszPath[offEnd]));
3029	do
3030	cwcSlashes++;
3031	while (IS_SLASH(pwszPath[offEnd + cwcSlashes]));
3032	}
3033
3034	/* Done already? */
3035	if (offEnd >= cwcPath)
3036	{
3037	if ( pRoot->uCacheGen == KFSOBJ_CACHE_GEN_IGNORE
3038	\|\| pRoot->uCacheGen == (pRoot->bObjType != KFSOBJ_TYPE_MISSING
3039	? pCache->auGenerations[ pRoot->fFlags & KFSOBJ_F_USE_CUSTOM_GEN]
3040	: pCache->auGenerationsMissing[pRoot->fFlags & KFSOBJ_F_USE_CUSTOM_GEN])
3041	\|\| (fFlags & KFSCACHE_LOOKUP_F_NO_REFRESH)
3042	\|\| kFsCacheRefreshObj(pCache, pRoot, penmError))
3043	return kFsCacheObjRetainInternal(pRoot);
3044	return NULL;
3045	}
3046
3047	/* Check that we've got a valid result and not a cached negative one. */
3048	if (pRoot->bObjType == KFSOBJ_TYPE_DIR)
3049	{ /* likely */ }
3050	else
3051	{
3052	kHlpAssert(pRoot->bObjType == KFSOBJ_TYPE_MISSING);
3053	kHlpAssert( pRoot->uCacheGen == KFSOBJ_CACHE_GEN_IGNORE
3054	\|\| pRoot->uCacheGen == pCache->auGenerationsMissing[pRoot->fFlags & KFSOBJ_F_USE_CUSTOM_GEN]);
3055	return pRoot;
3056	}
3057
3058	/*
3059	* Now that we've found a valid root directory, lookup the
3060	* remainder of the path starting with it.
3061	*/
3062	return kFsCacheLookupRelativeToDirW(pCache, (PKFSDIR)pRoot, &pwszPath[offEnd + cwcSlashes],
3063	cwcPath - offEnd - cwcSlashes, fFlags, penmError, ppLastAncestor);
3064	}
3065
3066
3067	/**
3068	* This deals with paths that are relative and paths that contains '..'
3069	* elements, ANSI version.
3070	*
3071	* @returns Pointer to object corresponding to @a pszPath on success.
3072	* NULL if this isn't a path we care to cache.
3073	*
3074	* @param pCache The cache.
3075	* @param pszPath The path.
3076	* @param cchPath The length of the path.
3077	* @param fFlags Lookup flags, KFSCACHE_LOOKUP_F_XXX.
3078	* @param penmError Where to return details as to why the lookup
3079	* failed.
3080	* @param ppLastAncestor Where to return the last parent element found
3081	* (referenced) in case of error an path/file not
3082	* found problem. Optional.
3083	*/
3084	static PKFSOBJ kFsCacheLookupSlowA(PKFSCACHE pCache, const char *pszPath, KU32 cchPath, KU32 fFlags,
3085	KFSLOOKUPERROR penmError, PKFSOBJ ppLastAncestor)
3086	{
3087	/*
3088	* We just call GetFullPathNameA here to do the job as getcwd and _getdcwd
3089	* ends up calling it anyway.
3090	*/
3091	char szFull[KFSCACHE_CFG_MAX_PATH];
3092	UINT cchFull = GetFullPathNameA(pszPath, sizeof(szFull), szFull, NULL);
3093	if ( cchFull >= 3
3094	&& cchFull < sizeof(szFull))
3095	{
3096	KFSCACHE_LOG2(("kFsCacheLookupSlowA(%s)\n", pszPath));
3097	return kFsCacheLookupAbsoluteA(pCache, szFull, cchFull, fFlags, penmError, ppLastAncestor);
3098	}
3099
3100	/* The path is too long! */
3101	kHlpAssertMsgFailed(("'%s' -> cchFull=%u\n", pszPath, cchFull));
3102	*penmError = KFSLOOKUPERROR_PATH_TOO_LONG;
3103	return NULL;
3104	}
3105
3106
3107	/**
3108	* This deals with paths that are relative and paths that contains '..'
3109	* elements, UTF-16 version.
3110	*
3111	* @returns Pointer to object corresponding to @a pszPath on success.
3112	* NULL if this isn't a path we care to cache.
3113	*
3114	* @param pCache The cache.
3115	* @param pwszPath The path.
3116	* @param cwcPath The length of the path (in wchar_t's).
3117	* @param fFlags Lookup flags, KFSCACHE_LOOKUP_F_XXX.
3118	* @param penmError Where to return details as to why the lookup
3119	* failed.
3120	* @param ppLastAncestor Where to return the last parent element found
3121	* (referenced) in case of error an path/file not
3122	* found problem. Optional.
3123	*/
3124	static PKFSOBJ kFsCacheLookupSlowW(PKFSCACHE pCache, const wchar_t *pwszPath, KU32 wcwPath, KU32 fFlags,
3125	KFSLOOKUPERROR penmError, PKFSOBJ ppLastAncestor)
3126	{
3127	/*
3128	* We just call GetFullPathNameA here to do the job as getcwd and _getdcwd
3129	* ends up calling it anyway.
3130	*/
3131	wchar_t wszFull[KFSCACHE_CFG_MAX_PATH];
3132	UINT cwcFull = GetFullPathNameW(pwszPath, KFSCACHE_CFG_MAX_PATH, wszFull, NULL);
3133	if ( cwcFull >= 3
3134	&& cwcFull < KFSCACHE_CFG_MAX_PATH)
3135	{
3136	KFSCACHE_LOG2(("kFsCacheLookupSlowA(%ls)\n", pwszPath));
3137	return kFsCacheLookupAbsoluteW(pCache, wszFull, cwcFull, fFlags, penmError, ppLastAncestor);
3138	}
3139
3140	/* The path is too long! */
3141	kHlpAssertMsgFailed(("'%ls' -> cwcFull=%u\n", pwszPath, cwcFull));
3142	*penmError = KFSLOOKUPERROR_PATH_TOO_LONG;
3143	return NULL;
3144	}
3145
3146
3147	/**
3148	* Refreshes a path hash that has expired, ANSI version.
3149	*
3150	* @returns pHash on success, NULL if removed.
3151	* @param pCache The cache.
3152	* @param pHashEntry The path hash.
3153	* @param idxHashTab The hash table entry.
3154	*/
3155	static PKFSHASHA kFsCacheRefreshPathA(PKFSCACHE pCache, PKFSHASHA pHashEntry, KU32 idxHashTab)
3156	{
3157	PKFSOBJ pLastAncestor = NULL;
3158	if (!pHashEntry->pFsObj)
3159	{
3160	if (pHashEntry->fAbsolute)
3161	pHashEntry->pFsObj = kFsCacheLookupAbsoluteA(pCache, pHashEntry->pszPath, pHashEntry->cchPath, 0 /fFlags/,
3162	&pHashEntry->enmError, &pLastAncestor);
3163	else
3164	pHashEntry->pFsObj = kFsCacheLookupSlowA(pCache, pHashEntry->pszPath, pHashEntry->cchPath, 0 /fFlags/,
3165	&pHashEntry->enmError, &pLastAncestor);
3166	}
3167	else
3168	{
3169	KU8 bOldType = pHashEntry->pFsObj->bObjType;
3170	KFSLOOKUPERROR enmError;
3171	if (kFsCacheRefreshObj(pCache, pHashEntry->pFsObj, &enmError))
3172	{
3173	if (pHashEntry->pFsObj->bObjType == bOldType)
3174	{ }
3175	else
3176	{
3177	kFsCacheObjRelease(pCache, pHashEntry->pFsObj);
3178	if (pHashEntry->fAbsolute)
3179	pHashEntry->pFsObj = kFsCacheLookupAbsoluteA(pCache, pHashEntry->pszPath, pHashEntry->cchPath, 0 /fFlags/,
3180	&pHashEntry->enmError, &pLastAncestor);
3181	else
3182	pHashEntry->pFsObj = kFsCacheLookupSlowA(pCache, pHashEntry->pszPath, pHashEntry->cchPath, 0 /fFlags/,
3183	&pHashEntry->enmError, &pLastAncestor);
3184	}
3185	}
3186	else
3187	{
3188	fprintf(stderr, "kFsCacheRefreshPathA - refresh failure handling not implemented!\n");
3189	__debugbreak();
3190	/** @todo just remove this entry. */
3191	return NULL;
3192	}
3193	}
3194
3195	if (pLastAncestor && !pHashEntry->pFsObj)
3196	pHashEntry->idxMissingGen = pLastAncestor->fFlags & KFSOBJ_F_USE_CUSTOM_GEN;
3197	pHashEntry->uCacheGen = !pHashEntry->pFsObj
3198	? pCache->auGenerationsMissing[pHashEntry->idxMissingGen]
3199	: pHashEntry->pFsObj->bObjType == KFSOBJ_TYPE_MISSING
3200	? pCache->auGenerationsMissing[pHashEntry->pFsObj->fFlags & KFSOBJ_F_USE_CUSTOM_GEN]
3201	: pCache->auGenerations[ pHashEntry->pFsObj->fFlags & KFSOBJ_F_USE_CUSTOM_GEN];
3202	if (pLastAncestor)
3203	kFsCacheObjRelease(pCache, pLastAncestor);
3204	return pHashEntry;
3205	}
3206
3207
3208	/**
3209	* Refreshes a path hash that has expired, UTF-16 version.
3210	*
3211	* @returns pHash on success, NULL if removed.
3212	* @param pCache The cache.
3213	* @param pHashEntry The path hash.
3214	* @param idxHashTab The hash table entry.
3215	*/
3216	static PKFSHASHW kFsCacheRefreshPathW(PKFSCACHE pCache, PKFSHASHW pHashEntry, KU32 idxHashTab)
3217	{
3218	PKFSOBJ pLastAncestor = NULL;
3219	if (!pHashEntry->pFsObj)
3220	{
3221	if (pHashEntry->fAbsolute)
3222	pHashEntry->pFsObj = kFsCacheLookupAbsoluteW(pCache, pHashEntry->pwszPath, pHashEntry->cwcPath, 0 /fFlags/,
3223	&pHashEntry->enmError, &pLastAncestor);
3224	else
3225	pHashEntry->pFsObj = kFsCacheLookupSlowW(pCache, pHashEntry->pwszPath, pHashEntry->cwcPath, 0 /fFlags/,
3226	&pHashEntry->enmError, &pLastAncestor);
3227	}
3228	else
3229	{
3230	KU8 bOldType = pHashEntry->pFsObj->bObjType;
3231	KFSLOOKUPERROR enmError;
3232	if (kFsCacheRefreshObj(pCache, pHashEntry->pFsObj, &enmError))
3233	{
3234	if (pHashEntry->pFsObj->bObjType == bOldType)
3235	{ }
3236	else
3237	{
3238	kFsCacheObjRelease(pCache, pHashEntry->pFsObj);
3239	if (pHashEntry->fAbsolute)
3240	pHashEntry->pFsObj = kFsCacheLookupAbsoluteW(pCache, pHashEntry->pwszPath, pHashEntry->cwcPath, 0 /fFlags/,
3241	&pHashEntry->enmError, &pLastAncestor);
3242	else
3243	pHashEntry->pFsObj = kFsCacheLookupSlowW(pCache, pHashEntry->pwszPath, pHashEntry->cwcPath, 0 /fFlags/,
3244	&pHashEntry->enmError, &pLastAncestor);
3245	}
3246	}
3247	else
3248	{
3249	fprintf(stderr, "kFsCacheRefreshPathW - refresh failure handling not implemented!\n");
3250	__debugbreak();
3251	/** @todo just remove this entry. */
3252	return NULL;
3253	}
3254	}
3255	if (pLastAncestor && !pHashEntry->pFsObj)
3256	pHashEntry->idxMissingGen = pLastAncestor->fFlags & KFSOBJ_F_USE_CUSTOM_GEN;
3257	pHashEntry->uCacheGen = !pHashEntry->pFsObj
3258	? pCache->auGenerationsMissing[pHashEntry->idxMissingGen]
3259	: pHashEntry->pFsObj->bObjType == KFSOBJ_TYPE_MISSING
3260	? pCache->auGenerationsMissing[pHashEntry->pFsObj->fFlags & KFSOBJ_F_USE_CUSTOM_GEN]
3261	: pCache->auGenerations[ pHashEntry->pFsObj->fFlags & KFSOBJ_F_USE_CUSTOM_GEN];
3262	if (pLastAncestor)
3263	kFsCacheObjRelease(pCache, pLastAncestor);
3264	return pHashEntry;
3265	}
3266
3267
3268	/**
3269	* Internal lookup worker that looks up a KFSOBJ for the given ANSI path with
3270	* length and hash.
3271	*
3272	* This will first try the hash table. If not in the hash table, the file
3273	* system cache tree is walked, missing bits filled in and finally a hash table
3274	* entry is created.
3275	*
3276	* Only drive letter paths are cachable. We don't do any UNC paths at this
3277	* point.
3278	*
3279	* @returns Reference to object corresponding to @a pszPath on success, this
3280	* must be released by kFsCacheObjRelease.
3281	* NULL if not a path we care to cache.
3282	* @param pCache The cache.
3283	* @param pchPath The path to lookup.
3284	* @param cchPath The path length.
3285	* @param uHashPath The hash of the path.
3286	* @param penmError Where to return details as to why the lookup
3287	* failed.
3288	*/
3289	static PKFSOBJ kFsCacheLookupHashedA(PKFSCACHE pCache, const char *pchPath, KU32 cchPath, KU32 uHashPath,
3290	KFSLOOKUPERROR *penmError)
3291	{
3292	/*
3293	* Do hash table lookup of the path.
3294	*/
3295	KU32 idxHashTab = uHashPath % K_ELEMENTS(pCache->apAnsiPaths);
3296	PKFSHASHA pHashEntry = pCache->apAnsiPaths[idxHashTab];
3297	kHlpAssert(pCache->u32Magic == KFSCACHE_MAGIC);
3298	if (pHashEntry)
3299	{
3300	do
3301	{
3302	if ( pHashEntry->uHashPath == uHashPath
3303	&& pHashEntry->cchPath == cchPath
3304	&& kHlpMemComp(pHashEntry->pszPath, pchPath, cchPath) == 0)
3305	{
3306	PKFSOBJ pFsObj;
3307	if ( pHashEntry->uCacheGen == KFSOBJ_CACHE_GEN_IGNORE
3308	\|\| pHashEntry->uCacheGen == ( (pFsObj = pHashEntry->pFsObj) != NULL
3309	? pFsObj->bObjType != KFSOBJ_TYPE_MISSING
3310	? pCache->auGenerations[ pFsObj->fFlags & KFSOBJ_F_USE_CUSTOM_GEN]
3311	: pCache->auGenerationsMissing[pFsObj->fFlags & KFSOBJ_F_USE_CUSTOM_GEN]
3312	: pCache->auGenerationsMissing[pHashEntry->idxMissingGen])
3313	\|\| (pHashEntry = kFsCacheRefreshPathA(pCache, pHashEntry, idxHashTab)) )
3314	{
3315	pCache->cLookups++;
3316	pCache->cPathHashHits++;
3317	KFSCACHE_LOG2(("kFsCacheLookupA(%.s) - hit %p\n", cchPath, cchPath, pchPath, pHashEntry->pFsObj));
3318	*penmError = pHashEntry->enmError;
3319	if (pHashEntry->pFsObj)
3320	return kFsCacheObjRetainInternal(pHashEntry->pFsObj);
3321	return NULL;
3322	}
3323	break;
3324	}
3325	pHashEntry = pHashEntry->pNext;
3326	} while (pHashEntry);
3327	}
3328
3329	/*
3330	* Create an entry for it by walking the file system cache and filling in the blanks.
3331	*/
3332	if ( cchPath > 0
3333	&& cchPath < KFSCACHE_CFG_MAX_PATH)
3334	{
3335	PKFSOBJ pFsObj;
3336	KBOOL fAbsolute;
3337	PKFSOBJ pLastAncestor = NULL;
3338
3339	/* Is absolute without any '..' bits? */
3340	if ( cchPath >= 3
3341	&& ( ( pchPath[1] == ':' /* Drive letter */
3342	&& IS_SLASH(pchPath[2])
3343	&& IS_ALPHA(pchPath[0]) )
3344	\|\| ( IS_SLASH(pchPath[0]) /* UNC */
3345	&& IS_SLASH(pchPath[1]) ) )
3346	&& !kFsCacheHasDotDotA(pchPath, cchPath) )
3347	{
3348	pFsObj = kFsCacheLookupAbsoluteA(pCache, pchPath, cchPath, 0 /fFlags/, penmError, &pLastAncestor);
3349	fAbsolute = K_TRUE;
3350	}
3351	else
3352	{
3353	pFsObj = kFsCacheLookupSlowA(pCache, pchPath, cchPath, 0 /fFlags/, penmError, &pLastAncestor);
3354	fAbsolute = K_FALSE;
3355	}
3356	if ( pFsObj
3357	\|\| ( (pCache->fFlags & KFSCACHE_F_MISSING_PATHS)
3358	&& *penmError != KFSLOOKUPERROR_PATH_TOO_LONG)
3359	\|\| *penmError == KFSLOOKUPERROR_UNSUPPORTED )
3360	kFsCacheCreatePathHashTabEntryA(pCache, pFsObj, pchPath, cchPath, uHashPath, idxHashTab, fAbsolute,
3361	pLastAncestor ? pLastAncestor->bObjType & KFSOBJ_F_USE_CUSTOM_GEN : 0, *penmError);
3362	if (pLastAncestor)
3363	kFsCacheObjRelease(pCache, pLastAncestor);
3364
3365	pCache->cLookups++;
3366	if (pFsObj)
3367	pCache->cWalkHits++;
3368	return pFsObj;
3369	}
3370
3371	*penmError = KFSLOOKUPERROR_PATH_TOO_LONG;
3372	return NULL;
3373	}
3374
3375
3376	/**
3377	* Internal lookup worker that looks up a KFSOBJ for the given UTF-16 path with
3378	* length and hash.
3379	*
3380	* This will first try the hash table. If not in the hash table, the file
3381	* system cache tree is walked, missing bits filled in and finally a hash table
3382	* entry is created.
3383	*
3384	* Only drive letter paths are cachable. We don't do any UNC paths at this
3385	* point.
3386	*
3387	* @returns Reference to object corresponding to @a pwcPath on success, this
3388	* must be released by kFsCacheObjRelease.
3389	* NULL if not a path we care to cache.
3390	* @param pCache The cache.
3391	* @param pwcPath The path to lookup.
3392	* @param cwcPath The length of the path (in wchar_t's).
3393	* @param uHashPath The hash of the path.
3394	* @param penmError Where to return details as to why the lookup
3395	* failed.
3396	*/
3397	static PKFSOBJ kFsCacheLookupHashedW(PKFSCACHE pCache, const wchar_t *pwcPath, KU32 cwcPath, KU32 uHashPath,
3398	KFSLOOKUPERROR *penmError)
3399	{
3400	/*
3401	* Do hash table lookup of the path.
3402	*/
3403	KU32 idxHashTab = uHashPath % K_ELEMENTS(pCache->apAnsiPaths);
3404	PKFSHASHW pHashEntry = pCache->apUtf16Paths[idxHashTab];
3405	kHlpAssert(pCache->u32Magic == KFSCACHE_MAGIC);
3406	if (pHashEntry)
3407	{
3408	do
3409	{
3410	if ( pHashEntry->uHashPath == uHashPath
3411	&& pHashEntry->cwcPath == cwcPath
3412	&& kHlpMemComp(pHashEntry->pwszPath, pwcPath, cwcPath) == 0)
3413	{
3414	PKFSOBJ pFsObj;
3415	if ( pHashEntry->uCacheGen == KFSOBJ_CACHE_GEN_IGNORE
3416	\|\| pHashEntry->uCacheGen == ((pFsObj = pHashEntry->pFsObj) != NULL
3417	? pFsObj->bObjType != KFSOBJ_TYPE_MISSING
3418	? pCache->auGenerations[ pFsObj->fFlags & KFSOBJ_F_USE_CUSTOM_GEN]
3419	: pCache->auGenerationsMissing[pFsObj->fFlags & KFSOBJ_F_USE_CUSTOM_GEN]
3420	: pCache->auGenerationsMissing[pHashEntry->idxMissingGen])
3421	\|\| (pHashEntry = kFsCacheRefreshPathW(pCache, pHashEntry, idxHashTab)) )
3422	{
3423	pCache->cLookups++;
3424	pCache->cPathHashHits++;
3425	KFSCACHE_LOG2(("kFsCacheLookupW(%.ls) - hit %p\n", cwcPath, cwcPath, pwcPath, pHashEntry->pFsObj));
3426	*penmError = pHashEntry->enmError;
3427	if (pHashEntry->pFsObj)
3428	return kFsCacheObjRetainInternal(pHashEntry->pFsObj);
3429	return NULL;
3430	}
3431	break;
3432	}
3433	pHashEntry = pHashEntry->pNext;
3434	} while (pHashEntry);
3435	}
3436
3437	/*
3438	* Create an entry for it by walking the file system cache and filling in the blanks.
3439	*/
3440	if ( cwcPath > 0
3441	&& cwcPath < KFSCACHE_CFG_MAX_PATH)
3442	{
3443	PKFSOBJ pFsObj;
3444	KBOOL fAbsolute;
3445	PKFSOBJ pLastAncestor = NULL;
3446
3447	/* Is absolute without any '..' bits? */
3448	if ( cwcPath >= 3
3449	&& ( ( pwcPath[1] == ':' /* Drive letter */
3450	&& IS_SLASH(pwcPath[2])
3451	&& IS_ALPHA(pwcPath[0]) )
3452	\|\| ( IS_SLASH(pwcPath[0]) /* UNC */
3453	&& IS_SLASH(pwcPath[1]) ) )
3454	&& !kFsCacheHasDotDotW(pwcPath, cwcPath) )
3455	{
3456	pFsObj = kFsCacheLookupAbsoluteW(pCache, pwcPath, cwcPath, 0 /fFlags/, penmError, &pLastAncestor);
3457	fAbsolute = K_TRUE;
3458	}
3459	else
3460	{
3461	pFsObj = kFsCacheLookupSlowW(pCache, pwcPath, cwcPath, 0 /fFlags/, penmError, &pLastAncestor);
3462	fAbsolute = K_FALSE;
3463	}
3464	if ( pFsObj
3465	\|\| ( (pCache->fFlags & KFSCACHE_F_MISSING_PATHS)
3466	&& *penmError != KFSLOOKUPERROR_PATH_TOO_LONG)
3467	\|\| *penmError == KFSLOOKUPERROR_UNSUPPORTED )
3468	kFsCacheCreatePathHashTabEntryW(pCache, pFsObj, pwcPath, cwcPath, uHashPath, idxHashTab, fAbsolute,
3469	pLastAncestor ? pLastAncestor->bObjType & KFSOBJ_F_USE_CUSTOM_GEN : 0, *penmError);
3470	if (pLastAncestor)
3471	kFsCacheObjRelease(pCache, pLastAncestor);
3472
3473	pCache->cLookups++;
3474	if (pFsObj)
3475	pCache->cWalkHits++;
3476	return pFsObj;
3477	}
3478
3479	*penmError = KFSLOOKUPERROR_PATH_TOO_LONG;
3480	return NULL;
3481	}
3482
3483
3484
3485	/**
3486	* Looks up a KFSOBJ for the given ANSI path.
3487	*
3488	* This will first try the hash table. If not in the hash table, the file
3489	* system cache tree is walked, missing bits filled in and finally a hash table
3490	* entry is created.
3491	*
3492	* Only drive letter paths are cachable. We don't do any UNC paths at this
3493	* point.
3494	*
3495	* @returns Reference to object corresponding to @a pszPath on success, this
3496	* must be released by kFsCacheObjRelease.
3497	* NULL if not a path we care to cache.
3498	* @param pCache The cache.
3499	* @param pszPath The path to lookup.
3500	* @param penmError Where to return details as to why the lookup
3501	* failed.
3502	*/
3503	PKFSOBJ kFsCacheLookupA(PKFSCACHE pCache, const char pszPath, KFSLOOKUPERROR penmError)
3504	{
3505	KU32 uHashPath;
3506	KU32 cchPath = (KU32)kFsCacheStrHashEx(pszPath, &uHashPath);
3507	return kFsCacheLookupHashedA(pCache, pszPath, cchPath, uHashPath, penmError);
3508	}
3509
3510
3511	/**
3512	* Looks up a KFSOBJ for the given UTF-16 path.
3513	*
3514	* This will first try the hash table. If not in the hash table, the file
3515	* system cache tree is walked, missing bits filled in and finally a hash table
3516	* entry is created.
3517	*
3518	* Only drive letter paths are cachable. We don't do any UNC paths at this
3519	* point.
3520	*
3521	* @returns Reference to object corresponding to @a pwszPath on success, this
3522	* must be released by kFsCacheObjRelease.
3523	* NULL if not a path we care to cache.
3524	* @param pCache The cache.
3525	* @param pwszPath The path to lookup.
3526	* @param penmError Where to return details as to why the lookup
3527	* failed.
3528	*/
3529	PKFSOBJ kFsCacheLookupW(PKFSCACHE pCache, const wchar_t pwszPath, KFSLOOKUPERROR penmError)
3530	{
3531	KU32 uHashPath;
3532	KU32 cwcPath = (KU32)kFsCacheUtf16HashEx(pwszPath, &uHashPath);
3533	return kFsCacheLookupHashedW(pCache, pwszPath, cwcPath, uHashPath, penmError);
3534	}
3535
3536
3537	/**
3538	* Looks up a KFSOBJ for the given ANSI path.
3539	*
3540	* This will first try the hash table. If not in the hash table, the file
3541	* system cache tree is walked, missing bits filled in and finally a hash table
3542	* entry is created.
3543	*
3544	* Only drive letter paths are cachable. We don't do any UNC paths at this
3545	* point.
3546	*
3547	* @returns Reference to object corresponding to @a pchPath on success, this
3548	* must be released by kFsCacheObjRelease.
3549	* NULL if not a path we care to cache.
3550	* @param pCache The cache.
3551	* @param pchPath The path to lookup (does not need to be nul
3552	* terminated).
3553	* @param cchPath The path length.
3554	* @param penmError Where to return details as to why the lookup
3555	* failed.
3556	*/
3557	PKFSOBJ kFsCacheLookupWithLengthA(PKFSCACHE pCache, const char pchPath, KSIZE cchPath, KFSLOOKUPERROR penmError)
3558	{
3559	return kFsCacheLookupHashedA(pCache, pchPath, (KU32)cchPath, kFsCacheStrHashN(pchPath, cchPath), penmError);
3560	}
3561
3562
3563	/**
3564	* Looks up a KFSOBJ for the given UTF-16 path.
3565	*
3566	* This will first try the hash table. If not in the hash table, the file
3567	* system cache tree is walked, missing bits filled in and finally a hash table
3568	* entry is created.
3569	*
3570	* Only drive letter paths are cachable. We don't do any UNC paths at this
3571	* point.
3572	*
3573	* @returns Reference to object corresponding to @a pwchPath on success, this
3574	* must be released by kFsCacheObjRelease.
3575	* NULL if not a path we care to cache.
3576	* @param pCache The cache.
3577	* @param pwcPath The path to lookup (does not need to be nul
3578	* terminated).
3579	* @param cwcPath The path length (in wchar_t's).
3580	* @param penmError Where to return details as to why the lookup
3581	* failed.
3582	*/
3583	PKFSOBJ kFsCacheLookupWithLengthW(PKFSCACHE pCache, const wchar_t pwcPath, KSIZE cwcPath, KFSLOOKUPERROR penmError)
3584	{
3585	return kFsCacheLookupHashedW(pCache, pwcPath, (KU32)cwcPath, kFsCacheUtf16HashN(pwcPath, cwcPath), penmError);
3586	}
3587
3588
3589	/**
3590	* Wrapper around kFsCacheLookupA that drops KFSOBJ_TYPE_MISSING and returns
3591	* KFSLOOKUPERROR_NOT_FOUND instead.
3592	*
3593	* @returns Reference to object corresponding to @a pszPath on success, this
3594	* must be released by kFsCacheObjRelease.
3595	* NULL if not a path we care to cache.
3596	* @param pCache The cache.
3597	* @param pszPath The path to lookup.
3598	* @param penmError Where to return details as to why the lookup
3599	* failed.
3600	*/
3601	PKFSOBJ kFsCacheLookupNoMissingA(PKFSCACHE pCache, const char pszPath, KFSLOOKUPERROR penmError)
3602	{
3603	PKFSOBJ pObj = kFsCacheLookupA(pCache, pszPath, penmError);
3604	if (pObj)
3605	{
3606	if (pObj->bObjType != KFSOBJ_TYPE_MISSING)
3607	return pObj;
3608
3609	kFsCacheObjRelease(pCache, pObj);
3610	*penmError = KFSLOOKUPERROR_NOT_FOUND;
3611	}
3612	return NULL;
3613	}
3614
3615
3616	/**
3617	* Wrapper around kFsCacheLookupW that drops KFSOBJ_TYPE_MISSING and returns
3618	* KFSLOOKUPERROR_NOT_FOUND instead.
3619	*
3620	* @returns Reference to object corresponding to @a pszPath on success, this
3621	* must be released by kFsCacheObjRelease.
3622	* NULL if not a path we care to cache.
3623	* @param pCache The cache.
3624	* @param pwszPath The path to lookup.
3625	* @param penmError Where to return details as to why the lookup
3626	* failed.
3627	*/
3628	PKFSOBJ kFsCacheLookupNoMissingW(PKFSCACHE pCache, const wchar_t pwszPath, KFSLOOKUPERROR penmError)
3629	{
3630	PKFSOBJ pObj = kFsCacheLookupW(pCache, pwszPath, penmError);
3631	if (pObj)
3632	{
3633	if (pObj->bObjType != KFSOBJ_TYPE_MISSING)
3634	return pObj;
3635
3636	kFsCacheObjRelease(pCache, pObj);
3637	*penmError = KFSLOOKUPERROR_NOT_FOUND;
3638	}
3639	return NULL;
3640	}
3641
3642
3643	/**
3644	* Destroys a cache object which has a zero reference count.
3645	*
3646	* @returns 0
3647	* @param pCache The cache.
3648	* @param pObj The object.
3649	*/
3650	KU32 kFsCacheObjDestroy(PKFSCACHE pCache, PKFSOBJ pObj)
3651	{
3652	kHlpAssert(pObj->cRefs == 0);
3653	kHlpAssert(pObj->pParent == NULL);
3654	kHlpAssert(pObj->u32Magic == KFSOBJ_MAGIC);
3655
3656	KFSCACHE_LOG(("Destroying %s/%s, type=%d\n", pObj->pParent ? pObj->pParent->Obj.pszName : "", pObj->pszName, pObj->bObjType));
3657	if (pObj->abUnused[1] != 0)
3658	{
3659	fprintf(stderr, "Destroying %s/%s, type=%d, path hash entries: %d!\n", pObj->pParent ? pObj->pParent->Obj.pszName : "",
3660	pObj->pszName, pObj->bObjType, pObj->abUnused[0]);
3661	__debugbreak();
3662	}
3663
3664	/*
3665	* Invalidate the structure.
3666	*/
3667	pObj->u32Magic = ~KFSOBJ_MAGIC;
3668
3669	/*
3670	* Destroy any user data first.
3671	*/
3672	while (pObj->pUserDataHead != NULL)
3673	{
3674	PKFSUSERDATA pUserData = pObj->pUserDataHead;
3675	pObj->pUserDataHead = pUserData->pNext;
3676	if (pUserData->pfnDestructor)
3677	pUserData->pfnDestructor(pCache, pObj, pUserData);
3678	kHlpFree(pUserData);
3679	}
3680
3681	/*
3682	* Do type specific destruction
3683	*/
3684	switch (pObj->bObjType)
3685	{
3686	case KFSOBJ_TYPE_MISSING:
3687	/* nothing else to do here */
3688	pCache->cbObjects -= sizeof(KFSDIR);
3689	break;
3690
3691	case KFSOBJ_TYPE_DIR:
3692	{
3693	PKFSDIR pDir = (PKFSDIR)pObj;
3694	KU32 cChildren = pDir->cChildren;
3695	pCache->cbObjects -= sizeof(*pDir)
3696	+ K_ALIGN_Z(cChildren, 16) * sizeof(pDir->papChildren)
3697	+ (pDir->fHashTabMask + !!pDir->fHashTabMask) * sizeof(pDir->papHashTab[0]);
3698
3699	pDir->cChildren = 0;
3700	while (cChildren-- > 0)
3701	kFsCacheObjRelease(pCache, pDir->papChildren[cChildren]);
3702	kHlpFree(pDir->papChildren);
3703	pDir->papChildren = NULL;
3704
3705	kHlpFree(pDir->papHashTab);
3706	pDir->papHashTab = NULL;
3707	break;
3708	}
3709
3710	case KFSOBJ_TYPE_FILE:
3711	case KFSOBJ_TYPE_OTHER:
3712	pCache->cbObjects -= sizeof(*pObj);
3713	break;
3714
3715	default:
3716	return 0;
3717	}
3718
3719	/*
3720	* Common bits.
3721	*/
3722	pCache->cbObjects -= pObj->cchName + 1;
3723	#ifdef KFSCACHE_CFG_UTF16
3724	pCache->cbObjects -= (pObj->cwcName + 1) * sizeof(wchar_t);
3725	#endif
3726	#ifdef KFSCACHE_CFG_SHORT_NAMES
3727	if (pObj->pszName != pObj->pszShortName)
3728	{
3729	pCache->cbObjects -= pObj->cchShortName + 1;
3730	# ifdef KFSCACHE_CFG_UTF16
3731	pCache->cbObjects -= (pObj->cwcShortName + 1) * sizeof(wchar_t);
3732	# endif
3733	}
3734	#endif
3735	pCache->cObjects--;
3736
3737	kHlpFree(pObj);
3738	return 0;
3739	}
3740
3741
3742	/**
3743	* Releases a reference to a cache object.
3744	*
3745	* @returns New reference count.
3746	* @param pCache The cache.
3747	* @param pObj The object.
3748	*/
3749	KU32 kFsCacheObjRelease(PKFSCACHE pCache, PKFSOBJ pObj)
3750	{
3751	if (pObj)
3752	{
3753	KU32 cRefs;
3754	kHlpAssert(pCache->u32Magic == KFSCACHE_MAGIC);
3755	kHlpAssert(pObj->u32Magic == KFSOBJ_MAGIC);
3756
3757	cRefs = --pObj->cRefs;
3758	if (cRefs)
3759	return cRefs;
3760	return kFsCacheObjDestroy(pCache, pObj);
3761	}
3762	return 0;
3763	}
3764
3765
3766	/**
3767	* Retains a reference to a cahce object.
3768	*
3769	* @returns New reference count.
3770	* @param pObj The object.
3771	*/
3772	KU32 kFsCacheObjRetain(PKFSOBJ pObj)
3773	{
3774	KU32 cRefs;
3775	kHlpAssert(pCache->u32Magic == KFSCACHE_MAGIC);
3776	kHlpAssert(pObj->u32Magic == KFSOBJ_MAGIC);
3777
3778	cRefs = ++pObj->cRefs;
3779	kHlpAssert(cRefs < 16384);
3780	return cRefs;
3781	}
3782
3783
3784	/**
3785	* Associates an item of user data with the given object.
3786	*
3787	* If the data needs cleaning up before being free, set the
3788	* PKFSUSERDATA::pfnDestructor member of the returned structure.
3789	*
3790	* @returns Pointer to the user data on success.
3791	* NULL if out of memory or key already in use.
3792	*
3793	* @param pCache The cache.
3794	* @param pObj The object.
3795	* @param uKey The user data key.
3796	* @param cbUserData The size of the user data.
3797	*/
3798	PKFSUSERDATA kFsCacheObjAddUserData(PKFSCACHE pCache, PKFSOBJ pObj, KUPTR uKey, KSIZE cbUserData)
3799	{
3800	kHlpAssert(cbUserData >= sizeof(*pNew));
3801	if (kFsCacheObjGetUserData(pCache, pObj, uKey) == NULL)
3802	{
3803	PKFSUSERDATA pNew = (PKFSUSERDATA)kHlpAllocZ(cbUserData);
3804	if (pNew)
3805	{
3806	pNew->uKey = uKey;
3807	pNew->pfnDestructor = NULL;
3808	pNew->pNext = pObj->pUserDataHead;
3809	pObj->pUserDataHead = pNew;
3810	return pNew;
3811	}
3812	}
3813
3814	return NULL;
3815	}
3816
3817
3818	/**
3819	* Retrieves an item of user data associated with the given object.
3820	*
3821	* @returns Pointer to the associated user data if found, otherwise NULL.
3822	* @param pCache The cache.
3823	* @param pObj The object.
3824	* @param uKey The user data key.
3825	*/
3826	PKFSUSERDATA kFsCacheObjGetUserData(PKFSCACHE pCache, PKFSOBJ pObj, KUPTR uKey)
3827	{
3828	PKFSUSERDATA pCur;
3829
3830	kHlpAssert(pCache->u32Magic == KFSCACHE_MAGIC);
3831	kHlpAssert(pObj->u32Magic == KFSOBJ_MAGIC);
3832
3833	for (pCur = pObj->pUserDataHead; pCur; pCur = pCur->pNext)
3834	if (pCur->uKey == uKey)
3835	return pCur;
3836	return NULL;
3837	}
3838
3839
3840	/**
3841	* Gets the full path to @a pObj, ANSI version.
3842	*
3843	* @returns K_TRUE on success, K_FALSE on buffer overflow (nothing stored).
3844	* @param pObj The object to get the full path to.
3845	* @param pszPath Where to return the path
3846	* @param cbPath The size of the output buffer.
3847	* @param chSlash The slash to use.
3848	*/
3849	KBOOL kFsCacheObjGetFullPathA(PKFSOBJ pObj, char *pszPath, KSIZE cbPath, char chSlash)
3850	{
3851	KSIZE off = pObj->cchParent;
3852	kHlpAssert(pObj->u32Magic == KFSOBJ_MAGIC);
3853	if (off > 0)
3854	{
3855	KSIZE offEnd = off + pObj->cchName;
3856	if (offEnd < cbPath)
3857	{
3858	PKFSDIR pAncestor;
3859
3860	pszPath[off + pObj->cchName] = '\0';
3861	memcpy(&pszPath[off], pObj->pszName, pObj->cchName);
3862
3863	for (pAncestor = pObj->pParent; off > 0; pAncestor = pAncestor->Obj.pParent)
3864	{
3865	kHlpAssert(off > 1);
3866	kHlpAssert(pAncestor != NULL);
3867	kHlpAssert(pAncestor->Obj.cchName > 0);
3868	pszPath[--off] = chSlash;
3869	off -= pAncestor->Obj.cchName;
3870	kHlpAssert(pAncestor->Obj.cchParent == off);
3871	memcpy(&pszPath[off], pAncestor->Obj.pszName, pAncestor->Obj.cchName);
3872	}
3873	return K_TRUE;
3874	}
3875	}
3876	else
3877	{
3878	KBOOL const fDriveLetter = pObj->cchName == 2 && pObj->pszName[2] == ':';
3879	off = pObj->cchName;
3880	if (off + fDriveLetter < cbPath)
3881	{
3882	memcpy(pszPath, pObj->pszName, off);
3883	if (fDriveLetter)
3884	pszPath[off++] = chSlash;
3885	pszPath[off] = '\0';
3886	return K_TRUE;
3887	}
3888	}
3889
3890	return K_FALSE;
3891	}
3892
3893
3894	/**
3895	* Gets the full path to @a pObj, UTF-16 version.
3896	*
3897	* @returns K_TRUE on success, K_FALSE on buffer overflow (nothing stored).
3898	* @param pObj The object to get the full path to.
3899	* @param pszPath Where to return the path
3900	* @param cbPath The size of the output buffer.
3901	* @param wcSlash The slash to use.
3902	*/
3903	KBOOL kFsCacheObjGetFullPathW(PKFSOBJ pObj, wchar_t *pwszPath, KSIZE cwcPath, wchar_t wcSlash)
3904	{
3905	KSIZE off = pObj->cwcParent;
3906	kHlpAssert(pObj->u32Magic == KFSOBJ_MAGIC);
3907	if (off > 0)
3908	{
3909	KSIZE offEnd = off + pObj->cwcName;
3910	if (offEnd < cwcPath)
3911	{
3912	PKFSDIR pAncestor;
3913
3914	pwszPath[off + pObj->cwcName] = '\0';
3915	memcpy(&pwszPath[off], pObj->pwszName, pObj->cwcName * sizeof(wchar_t));
3916
3917	for (pAncestor = pObj->pParent; off > 0; pAncestor = pAncestor->Obj.pParent)
3918	{
3919	kHlpAssert(off > 1);
3920	kHlpAssert(pAncestor != NULL);
3921	kHlpAssert(pAncestor->Obj.cwcName > 0);
3922	pwszPath[--off] = wcSlash;
3923	off -= pAncestor->Obj.cwcName;
3924	kHlpAssert(pAncestor->Obj.cwcParent == off);
3925	memcpy(&pwszPath[off], pAncestor->Obj.pwszName, pAncestor->Obj.cwcName * sizeof(wchar_t));
3926	}
3927	return K_TRUE;
3928	}
3929	}
3930	else
3931	{
3932	KBOOL const fDriveLetter = pObj->cchName == 2 && pObj->pszName[2] == ':';
3933	off = pObj->cwcName;
3934	if (off + fDriveLetter < cwcPath)
3935	{
3936	memcpy(pwszPath, pObj->pwszName, off * sizeof(wchar_t));
3937	if (fDriveLetter)
3938	pwszPath[off++] = wcSlash;
3939	pwszPath[off] = '\0';
3940	return K_TRUE;
3941	}
3942	}
3943
3944	return K_FALSE;
3945	}
3946
3947
3948	#ifdef KFSCACHE_CFG_SHORT_NAMES
3949
3950	/**
3951	* Gets the full short path to @a pObj, ANSI version.
3952	*
3953	* @returns K_TRUE on success, K_FALSE on buffer overflow (nothing stored).
3954	* @param pObj The object to get the full path to.
3955	* @param pszPath Where to return the path
3956	* @param cbPath The size of the output buffer.
3957	* @param chSlash The slash to use.
3958	*/
3959	KBOOL kFsCacheObjGetFullShortPathA(PKFSOBJ pObj, char *pszPath, KSIZE cbPath, char chSlash)
3960	{
3961	KSIZE off = pObj->cchShortParent;
3962	kHlpAssert(pObj->u32Magic == KFSOBJ_MAGIC);
3963	if (off > 0)
3964	{
3965	KSIZE offEnd = off + pObj->cchShortName;
3966	if (offEnd < cbPath)
3967	{
3968	PKFSDIR pAncestor;
3969
3970	pszPath[off + pObj->cchShortName] = '\0';
3971	memcpy(&pszPath[off], pObj->pszShortName, pObj->cchShortName);
3972
3973	for (pAncestor = pObj->pParent; off > 0; pAncestor = pAncestor->Obj.pParent)
3974	{
3975	kHlpAssert(off > 1);
3976	kHlpAssert(pAncestor != NULL);
3977	kHlpAssert(pAncestor->Obj.cchShortName > 0);
3978	pszPath[--off] = chSlash;
3979	off -= pAncestor->Obj.cchShortName;
3980	kHlpAssert(pAncestor->Obj.cchShortParent == off);
3981	memcpy(&pszPath[off], pAncestor->Obj.pszShortName, pAncestor->Obj.cchShortName);
3982	}
3983	return K_TRUE;
3984	}
3985	}
3986	else
3987	{
3988	KBOOL const fDriveLetter = pObj->cchShortName == 2 && pObj->pszShortName[2] == ':';
3989	off = pObj->cchShortName;
3990	if (off + fDriveLetter < cbPath)
3991	{
3992	memcpy(pszPath, pObj->pszShortName, off);
3993	if (fDriveLetter)
3994	pszPath[off++] = chSlash;
3995	pszPath[off] = '\0';
3996	return K_TRUE;
3997	}
3998	}
3999
4000	return K_FALSE;
4001	}
4002
4003
4004	/**
4005	* Gets the full short path to @a pObj, UTF-16 version.
4006	*
4007	* @returns K_TRUE on success, K_FALSE on buffer overflow (nothing stored).
4008	* @param pObj The object to get the full path to.
4009	* @param pszPath Where to return the path
4010	* @param cbPath The size of the output buffer.
4011	* @param wcSlash The slash to use.
4012	*/
4013	KBOOL kFsCacheObjGetFullShortPathW(PKFSOBJ pObj, wchar_t *pwszPath, KSIZE cwcPath, wchar_t wcSlash)
4014	{
4015	KSIZE off = pObj->cwcShortParent;
4016	kHlpAssert(pObj->u32Magic == KFSOBJ_MAGIC);
4017	if (off > 0)
4018	{
4019	KSIZE offEnd = off + pObj->cwcShortName;
4020	if (offEnd < cwcPath)
4021	{
4022	PKFSDIR pAncestor;
4023
4024	pwszPath[off + pObj->cwcShortName] = '\0';
4025	memcpy(&pwszPath[off], pObj->pwszShortName, pObj->cwcShortName * sizeof(wchar_t));
4026
4027	for (pAncestor = pObj->pParent; off > 0; pAncestor = pAncestor->Obj.pParent)
4028	{
4029	kHlpAssert(off > 1);
4030	kHlpAssert(pAncestor != NULL);
4031	kHlpAssert(pAncestor->Obj.cwcShortName > 0);
4032	pwszPath[--off] = wcSlash;
4033	off -= pAncestor->Obj.cwcShortName;
4034	kHlpAssert(pAncestor->Obj.cwcShortParent == off);
4035	memcpy(&pwszPath[off], pAncestor->Obj.pwszShortName, pAncestor->Obj.cwcShortName * sizeof(wchar_t));
4036	}
4037	return K_TRUE;
4038	}
4039	}
4040	else
4041	{
4042	KBOOL const fDriveLetter = pObj->cchShortName == 2 && pObj->pszShortName[2] == ':';
4043	off = pObj->cwcShortName;
4044	if (off + fDriveLetter < cwcPath)
4045	{
4046	memcpy(pwszPath, pObj->pwszShortName, off * sizeof(wchar_t));
4047	if (fDriveLetter)
4048	pwszPath[off++] = wcSlash;
4049	pwszPath[off] = '\0';
4050	return K_TRUE;
4051	}
4052	}
4053
4054	return K_FALSE;
4055	}
4056
4057	#endif /* KFSCACHE_CFG_SHORT_NAMES */
4058
4059
4060
4061	/**
4062	* Read the specified bits from the files into the given buffer, simple version.
4063	*
4064	* @returns K_TRUE on success (all requested bytes read),
4065	* K_FALSE on any kind of failure.
4066	*
4067	* @param pCache The cache.
4068	* @param pFileObj The file object.
4069	* @param offStart Where to start reading.
4070	* @param pvBuf Where to store what we read.
4071	* @param cbToRead How much to read (exact).
4072	*/
4073	KBOOL kFsCacheFileSimpleOpenReadClose(PKFSCACHE pCache, PKFSOBJ pFileObj, KU64 offStart, void *pvBuf, KSIZE cbToRead)
4074	{
4075	/*
4076	* Open the file relative to the parent directory.
4077	*/
4078	MY_NTSTATUS rcNt;
4079	HANDLE hFile;
4080	MY_IO_STATUS_BLOCK Ios;
4081	MY_OBJECT_ATTRIBUTES ObjAttr;
4082	MY_UNICODE_STRING UniStr;
4083
4084	kHlpAssertReturn(pFileObj->bObjType == KFSOBJ_TYPE_FILE, K_FALSE);
4085	kHlpAssert(pFileObj->pParent);
4086	kHlpAssertReturn(pFileObj->pParent->hDir != INVALID_HANDLE_VALUE, K_FALSE);
4087	kHlpAssertReturn(offStart == 0, K_FALSE); /** @todo when needed */
4088
4089	Ios.Information = -1;
4090	Ios.u.Status = -1;
4091
4092	UniStr.Buffer = (wchar_t *)pFileObj->pwszName;
4093	UniStr.Length = (USHORT)(pFileObj->cwcName * sizeof(wchar_t));
4094	UniStr.MaximumLength = UniStr.Length + sizeof(wchar_t);
4095
4096	MyInitializeObjectAttributes(&ObjAttr, &UniStr, OBJ_CASE_INSENSITIVE, pFileObj->pParent->hDir, NULL /pSecAttr/);
4097
4098	rcNt = g_pfnNtCreateFile(&hFile,
4099	GENERIC_READ \| SYNCHRONIZE,
4100	&ObjAttr,
4101	&Ios,
4102	NULL, /cbFileInitialAlloc /
4103	FILE_ATTRIBUTE_NORMAL,
4104	FILE_SHARE_READ,
4105	FILE_OPEN,
4106	FILE_NON_DIRECTORY_FILE \| FILE_SYNCHRONOUS_IO_NONALERT,
4107	NULL, /pEaBuffer/
4108	0); /cbEaBuffer/
4109	if (MY_NT_SUCCESS(rcNt))
4110	{
4111	LARGE_INTEGER offFile;
4112	offFile.QuadPart = offStart;
4113
4114	Ios.Information = -1;
4115	Ios.u.Status = -1;
4116	rcNt = g_pfnNtReadFile(hFile, NULL /hEvent/, NULL /pfnApcComplete/, NULL /pvApcCtx/, &Ios,
4117	pvBuf, (KU32)cbToRead, !offStart ? &offFile : NULL, NULL /puKey/);
4118	if (MY_NT_SUCCESS(rcNt))
4119	rcNt = Ios.u.Status;
4120	if (MY_NT_SUCCESS(rcNt))
4121	{
4122	if (Ios.Information == cbToRead)
4123	{
4124	g_pfnNtClose(hFile);
4125	return K_TRUE;
4126	}
4127	KFSCACHE_LOG(("Error reading %#x bytes from '%ls': Information=%p\n", pFileObj->pwszName, Ios.Information));
4128	}
4129	else
4130	KFSCACHE_LOG(("Error reading %#x bytes from '%ls': %#x\n", pFileObj->pwszName, rcNt));
4131	g_pfnNtClose(hFile);
4132	}
4133	else
4134	KFSCACHE_LOG(("Error opening '%ls' for caching: %#x\n", pFileObj->pwszName, rcNt));
4135	return K_FALSE;
4136	}
4137
4138
4139	/**
4140	* Invalidate all cache entries of missing files.
4141	*
4142	* @param pCache The cache.
4143	*/
4144	void kFsCacheInvalidateMissing(PKFSCACHE pCache)
4145	{
4146	kHlpAssert(pCache->u32Magic == KFSOBJ_MAGIC);
4147	pCache->auGenerationsMissing[0]++;
4148	kHlpAssert(pCache->uGenerationMissing < KU32_MAX);
4149	KFSCACHE_LOG(("Invalidate missing %#x\n", pCache->auGenerationsMissing[0]));
4150	}
4151
4152
4153	/**
4154	* Invalidate all cache entries (regular, custom & missing).
4155	*
4156	* @param pCache The cache.
4157	*/
4158	void kFsCacheInvalidateAll(PKFSCACHE pCache)
4159	{
4160	kHlpAssert(pCache->u32Magic == KFSOBJ_MAGIC);
4161
4162	pCache->auGenerationsMissing[0]++;
4163	kHlpAssert(pCache->auGenerationsMissing[0] < KU32_MAX);
4164	pCache->auGenerationsMissing[1]++;
4165	kHlpAssert(pCache->auGenerationsMissing[1] < KU32_MAX);
4166
4167	pCache->auGenerations[0]++;
4168	kHlpAssert(pCache->auGenerations[0] < KU32_MAX);
4169	pCache->auGenerations[1]++;
4170	kHlpAssert(pCache->auGenerations[1] < KU32_MAX);
4171
4172	KFSCACHE_LOG(("Invalidate all - default: %#x/%#x, custom: %#x/%#x\n",
4173	pCache->auGenerationsMissing[0], pCache->auGenerations[0],
4174	pCache->auGenerationsMissing[1], pCache->auGenerations[1]));
4175	}
4176
4177
4178	/**
4179	* Invalidate all cache entries with custom generation handling set.
4180	*
4181	* @see kFsCacheSetupCustomRevisionForTree, KFSOBJ_F_USE_CUSTOM_GEN
4182	* @param pCache The cache.
4183	*/
4184	void kFsCacheInvalidateCustomMissing(PKFSCACHE pCache)
4185	{
4186	kHlpAssert(pCache->u32Magic == KFSOBJ_MAGIC);
4187	pCache->auGenerationsMissing[1]++;
4188	kHlpAssert(pCache->auGenerationsMissing[1] < KU32_MAX);
4189	KFSCACHE_LOG(("Invalidate missing custom %#x\n", pCache->auGenerationsMissing[1]));
4190	}
4191
4192
4193	/**
4194	* Invalidate all cache entries with custom generation handling set, both
4195	* missing and regular present entries.
4196	*
4197	* @see kFsCacheSetupCustomRevisionForTree, KFSOBJ_F_USE_CUSTOM_GEN
4198	* @param pCache The cache.
4199	*/
4200	void kFsCacheInvalidateCustomBoth(PKFSCACHE pCache)
4201	{
4202	kHlpAssert(pCache->u32Magic == KFSOBJ_MAGIC);
4203	pCache->auGenerations[1]++;
4204	kHlpAssert(pCache->auGenerations[1] < KU32_MAX);
4205	pCache->auGenerationsMissing[1]++;
4206	kHlpAssert(pCache->auGenerationsMissing[1] < KU32_MAX);
4207	KFSCACHE_LOG(("Invalidate both custom %#x/%#x\n", pCache->auGenerationsMissing[1], pCache->auGenerations[1]));
4208	}
4209
4210
4211
4212	/**
4213	* Applies the given flags to all the objects in a tree.
4214	*
4215	* @param pRoot Where to start applying the flag changes.
4216	* @param fAndMask The AND mask.
4217	* @param fOrMask The OR mask.
4218	*/
4219	static void kFsCacheApplyFlagsToTree(PKFSDIR pRoot, KU32 fAndMask, KU32 fOrMask)
4220	{
4221	PKFSOBJ *ppCur = ((PKFSDIR)pRoot)->papChildren;
4222	KU32 cLeft = ((PKFSDIR)pRoot)->cChildren;
4223	while (cLeft-- > 0)
4224	{
4225	PKFSOBJ pCur = *ppCur++;
4226	if (pCur->bObjType != KFSOBJ_TYPE_DIR)
4227	pCur->fFlags = (fAndMask & pCur->fFlags) \| fOrMask;
4228	else
4229	kFsCacheApplyFlagsToTree((PKFSDIR)pCur, fAndMask, fOrMask);
4230	}
4231
4232	pRoot->Obj.fFlags = (fAndMask & pRoot->Obj.fFlags) \| fOrMask;
4233	}
4234
4235
4236	/**
4237	* Sets up using custom revisioning for the specified directory tree or file.
4238	*
4239	* There are some restrictions of the current implementation:
4240	* - If the root of the sub-tree is ever deleted from the cache (i.e.
4241	* deleted in real life and reflected in the cache), the setting is lost.
4242	* - It is not automatically applied to the lookup paths caches.
4243	*
4244	* @returns K_TRUE on success, K_FALSE on failure.
4245	* @param pCache The cache.
4246	* @param pRoot The root of the subtree. A non-directory is
4247	* fine, like a missing node.
4248	*/
4249	KBOOL kFsCacheSetupCustomRevisionForTree(PKFSCACHE pCache, PKFSOBJ pRoot)
4250	{
4251	if (pRoot)
4252	{
4253	if (pRoot->bObjType == KFSOBJ_TYPE_DIR)
4254	kFsCacheApplyFlagsToTree((PKFSDIR)pRoot, KU32_MAX, KFSOBJ_F_USE_CUSTOM_GEN);
4255	else
4256	pRoot->fFlags \|= KFSOBJ_F_USE_CUSTOM_GEN;
4257	return K_TRUE;
4258	}
4259	return K_FALSE;
4260	}
4261
4262
4263	/**
4264	* Invalidates a deleted directory, ANSI version.
4265	*
4266	* @returns K_TRUE if found and is a non-root directory. Otherwise K_FALSE.
4267	* @param pCache The cache.
4268	* @param pszDir The directory.
4269	*/
4270	KBOOL kFsCacheInvalidateDeletedDirectoryA(PKFSCACHE pCache, const char *pszDir)
4271	{
4272	KU32 cchDir = (KU32)kHlpStrLen(pszDir);
4273	KFSLOOKUPERROR enmError;
4274	PKFSOBJ pFsObj;
4275
4276	/* Is absolute without any '..' bits? */
4277	if ( cchDir >= 3
4278	&& ( ( pszDir[1] == ':' /* Drive letter */
4279	&& IS_SLASH(pszDir[2])
4280	&& IS_ALPHA(pszDir[0]) )
4281	\|\| ( IS_SLASH(pszDir[0]) /* UNC */
4282	&& IS_SLASH(pszDir[1]) ) )
4283	&& !kFsCacheHasDotDotA(pszDir, cchDir) )
4284	pFsObj = kFsCacheLookupAbsoluteA(pCache, pszDir, cchDir, KFSCACHE_LOOKUP_F_NO_INSERT \| KFSCACHE_LOOKUP_F_NO_REFRESH,
4285	&enmError, NULL);
4286	else
4287	pFsObj = kFsCacheLookupSlowA(pCache, pszDir, cchDir, KFSCACHE_LOOKUP_F_NO_INSERT \| KFSCACHE_LOOKUP_F_NO_REFRESH,
4288	&enmError, NULL);
4289	if (pFsObj)
4290	{
4291	/* Is directory? */
4292	if (pFsObj->bObjType == KFSOBJ_TYPE_DIR)
4293	{
4294	if (pFsObj->pParent != &pCache->RootDir)
4295	{
4296	PKFSDIR pDir = (PKFSDIR)pFsObj;
4297	KFSCACHE_LOG(("kFsCacheInvalidateDeletedDirectoryA: %s hDir=%p\n", pszDir, pDir->hDir));
4298	if (pDir->hDir != INVALID_HANDLE_VALUE)
4299	{
4300	g_pfnNtClose(pDir->hDir);
4301	pDir->hDir = INVALID_HANDLE_VALUE;
4302	}
4303	pDir->fNeedRePopulating = K_TRUE;
4304	pDir->Obj.uCacheGen = pCache->auGenerations[pDir->Obj.fFlags & KFSOBJ_F_USE_CUSTOM_GEN] - 1;
4305	kFsCacheObjRetainInternal(&pDir->Obj);
4306	return K_TRUE;
4307	}
4308	KFSCACHE_LOG(("kFsCacheInvalidateDeletedDirectoryA: Trying to invalidate a root directory was deleted! %s\n", pszDir));
4309	}
4310	else
4311	KFSCACHE_LOG(("kFsCacheInvalidateDeletedDirectoryA: Trying to invalidate a non-directory: bObjType=%d %s\n",
4312	pFsObj->bObjType, pszDir));
4313	kFsCacheObjRetainInternal(pFsObj);
4314	}
4315	else
4316	KFSCACHE_LOG(("kFsCacheInvalidateDeletedDirectoryA: '%s' was not found\n", pszDir));
4317	return K_FALSE;
4318	}
4319
4320
4321	PKFSCACHE kFsCacheCreate(KU32 fFlags)
4322	{
4323	PKFSCACHE pCache;
4324	birdResolveImports();
4325
4326	pCache = (PKFSCACHE)kHlpAllocZ(sizeof(*pCache));
4327	if (pCache)
4328	{
4329	/* Dummy root dir entry. */
4330	pCache->RootDir.Obj.u32Magic = KFSOBJ_MAGIC;
4331	pCache->RootDir.Obj.cRefs = 1;
4332	pCache->RootDir.Obj.uCacheGen = KFSOBJ_CACHE_GEN_IGNORE;
4333	pCache->RootDir.Obj.bObjType = KFSOBJ_TYPE_DIR;
4334	pCache->RootDir.Obj.fHaveStats = K_FALSE;
4335	pCache->RootDir.Obj.pParent = NULL;
4336	pCache->RootDir.Obj.pszName = "";
4337	pCache->RootDir.Obj.cchName = 0;
4338	pCache->RootDir.Obj.cchParent = 0;
4339	#ifdef KFSCACHE_CFG_UTF16
4340	pCache->RootDir.Obj.cwcName = 0;
4341	pCache->RootDir.Obj.cwcParent = 0;
4342	pCache->RootDir.Obj.pwszName = L"";
4343	#endif
4344
4345	#ifdef KFSCACHE_CFG_SHORT_NAMES
4346	pCache->RootDir.Obj.pszShortName = NULL;
4347	pCache->RootDir.Obj.cchShortName = 0;
4348	pCache->RootDir.Obj.cchShortParent = 0;
4349	# ifdef KFSCACHE_CFG_UTF16
4350	pCache->RootDir.Obj.cwcShortName;
4351	pCache->RootDir.Obj.cwcShortParent;
4352	pCache->RootDir.Obj.pwszShortName;
4353	# endif
4354	#endif
4355	pCache->RootDir.cChildren = 0;
4356	pCache->RootDir.cChildrenAllocated = 0;
4357	pCache->RootDir.papChildren = NULL;
4358	pCache->RootDir.hDir = INVALID_HANDLE_VALUE;
4359	pCache->RootDir.fHashTabMask = 255; /* 256: 26 drive letters and 102 UNCs before we're half ways. */
4360	pCache->RootDir.papHashTab = (PKFSOBJ )kHlpAllocZ(256 sizeof(pCache->RootDir.papHashTab[0]));
4361	if (pCache->RootDir.papHashTab)
4362	{
4363	/* The cache itself. */
4364	pCache->u32Magic = KFSCACHE_MAGIC;
4365	pCache->fFlags = fFlags;
4366	pCache->auGenerations[0] = KU32_MAX / 4;
4367	pCache->auGenerations[1] = KU32_MAX / 32;
4368	pCache->auGenerationsMissing[0] = KU32_MAX / 256;
4369	pCache->auGenerationsMissing[1] = 1;
4370	pCache->cObjects = 1;
4371	pCache->cbObjects = sizeof(pCache->RootDir)
4372	+ (pCache->RootDir.fHashTabMask + 1) * sizeof(pCache->RootDir.papHashTab[0]);
4373	pCache->cPathHashHits = 0;
4374	pCache->cWalkHits = 0;
4375	pCache->cChildSearches = 0;
4376	pCache->cChildHashHits = 0;
4377	pCache->cChildHashed = 0;
4378	pCache->cChildHashTabs = 1;
4379	pCache->cChildHashEntriesTotal = pCache->RootDir.fHashTabMask + 1;
4380	pCache->cChildHashCollisions = 0;
4381	pCache->cAnsiPaths = 0;
4382	pCache->cAnsiPathCollisions = 0;
4383	pCache->cbAnsiPaths = 0;
4384	#ifdef KFSCACHE_CFG_UTF16
4385	pCache->cUtf16Paths = 0;
4386	pCache->cUtf16PathCollisions = 0;
4387	pCache->cbUtf16Paths = 0;
4388	#endif
4389	return pCache;
4390	}
4391
4392	kHlpFree(pCache);
4393	}
4394	return NULL;
4395	}
4396

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

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

Download in other formats: