kFsCache.c@ 2854

Last change on this file since 2854 was 2854, checked in by bird, 9 years ago
updates
Property svn:eol-style set to `native` Property svn:keywords set to `Id`
File size: 79.1 KB

Line
1	/* $Id: kFsCache.c 2854 2016-08-31 20:57:17Z bird $ */
2	/** @file
3	* ntdircache.c - NT directory content cache.
4	*/
5
6	/*
7	* Copyright (c) 2016 knut st. osmundsen <bird-kBuild-spamx@anduin.net>
8	*
9	* Permission is hereby granted, free of charge, to any person obtaining a
10	* copy of this software and associated documentation files (the "Software"),
11	* to deal in the Software without restriction, including without limitation
12	* the rights to use, copy, modify, merge, publish, distribute, sublicense,
13	* and/or sell copies of the Software, and to permit persons to whom the
14	* Software is furnished to do so, subject to the following conditions:
15	*
16	* The above copyright notice and this permission notice shall be included
17	* in all copies or substantial portions of the Software.
18	*
19	* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
20	* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
21	* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
22	* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
23	* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
24	* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
25	* IN THE SOFTWARE.
26	*
27	* Alternatively, the content of this file may be used under the terms of the
28	* GPL version 2 or later, or LGPL version 2.1 or later.
29	*/
30
31
32	/*********************************************************************************************************************************
33	* Header Files *
34	*********************************************************************************************************************************/
35	#include <k/kHlp.h>
36
37	#include "nthlp.h"
38	#include "ntstat.h"
39
40	#include <stdio.h>
41	#include <mbstring.h>
42	#include <wchar.h>
43	//#include <intrin.h>
44	//#include <setjmp.h>
45	//#include <ctype.h>
46
47
48	//#include <Windows.h>
49	//#include <winternl.h>
50
51	#include "kFsCache.h"
52
53
54
55
56
57	/**
58	* Retains a reference to a cache object, internal version.
59	*
60	* @returns pObj
61	* @param pObj The object.
62	*/
63	K_INLINE PKFSOBJ kFsCacheObjRetainInternal(PKFSOBJ pObj)
64	{
65	KU32 cRefs = ++pObj->cRefs;
66	kHlpAssert(cRefs < 16384);
67	K_NOREF(cRefs);
68	return pObj;
69	}
70
71
72	#ifndef NDEBUG
73
74	/**
75	* Debug printing.
76	* @param pszFormat Debug format string.
77	* @param ... Format argument.
78	*/
79	void kFsCacheDbgPrintfV(const char *pszFormat, va_list va)
80	{
81	if (1)
82	{
83	DWORD const dwSavedErr = GetLastError();
84
85	fprintf(stderr, "debug: ");
86	vfprintf(stderr, pszFormat, va);
87
88	SetLastError(dwSavedErr);
89	}
90	}
91
92
93	/**
94	* Debug printing.
95	* @param pszFormat Debug format string.
96	* @param ... Format argument.
97	*/
98	void kFsCacheDbgPrintf(const char *pszFormat, ...)
99	{
100	if (1)
101	{
102	va_list va;
103	va_start(va, pszFormat);
104	kFsCacheDbgPrintfV(pszFormat, va);
105	va_end(va);
106	}
107	}
108
109	#endif /* !NDEBUG */
110
111
112
113	/**
114	* Hashes a string.
115	*
116	* @returns 32-bit string hash.
117	* @param pszString String to hash.
118	*/
119	static KU32 kFsCacheStrHash(const char *pszString)
120	{
121	/* This algorithm was created for sdbm (a public-domain reimplementation of
122	ndbm) database library. it was found to do well in scrambling bits,
123	causing better distribution of the keys and fewer splits. it also happens
124	to be a good general hashing function with good distribution. the actual
125	function is hash(i) = hash(i - 1) * 65599 + str[i]; what is included below
126	is the faster version used in gawk. [there is even a faster, duff-device
127	version] the magic constant 65599 was picked out of thin air while
128	experimenting with different constants, and turns out to be a prime.
129	this is one of the algorithms used in berkeley db (see sleepycat) and
130	elsewhere. */
131	KU32 uHash = 0;
132	KU32 uChar;
133	while ((uChar = (unsigned char)*pszString++) != 0)
134	uHash = uChar + (uHash << 6) + (uHash << 16) - uHash;
135	return uHash;
136	}
137
138
139	/**
140	* Hashes a string.
141	*
142	* @returns The string length.
143	* @param pszString String to hash.
144	* @param puHash Where to return the 32-bit string hash.
145	*/
146	static KSIZE kFsCacheStrHashEx(const char pszString, KU32 puHash)
147	{
148	const char * const pszStart = pszString;
149	KU32 uHash = 0;
150	KU32 uChar;
151	while ((uChar = (unsigned char)*pszString) != 0)
152	{
153	uHash = uChar + (uHash << 6) + (uHash << 16) - uHash;
154	pszString++;
155	}
156	*puHash = uHash;
157	return pszString - pszStart;
158	}
159
160
161	/**
162	* Hashes a string.
163	*
164	* @returns The string length in wchar_t units.
165	* @param pwszString String to hash.
166	* @param puHash Where to return the 32-bit string hash.
167	*/
168	static KSIZE kFsCacheUtf16HashEx(const wchar_t pwszString, KU32 puHash)
169	{
170	const wchar_t * const pwszStart = pwszString;
171	KU32 uHash = 0;
172	KU32 uChar;
173	while ((uChar = *pwszString) != 0)
174	{
175	uHash = uChar + (uHash << 6) + (uHash << 16) - uHash;
176	pwszString++;
177	}
178	*puHash = uHash;
179	return pwszString - pwszStart;
180	}
181
182	#if 0
183
184	/**
185	* Converts the given string to unicode.
186	*
187	* @returns Length of the resulting string in wchar_t's.
188	* @param pszSrc The source string.
189	* @param pwszDst The destination buffer.
190	* @param cwcDst The size of the destination buffer in wchar_t's.
191	*/
192	static KSIZE kwStrToUtf16(const char pszSrc, wchar_t pwszDst, KSIZE cwcDst)
193	{
194	/* Just to the quick ASCII stuff for now. correct ansi code page stuff later some time. */
195	KSIZE offDst = 0;
196	while (offDst < cwcDst)
197	{
198	char ch = *pszSrc++;
199	pwszDst[offDst++] = ch;
200	if (!ch)
201	return offDst - 1;
202	kHlpAssert((unsigned)ch < 127);
203	}
204
205	pwszDst[offDst - 1] = '\0';
206	return offDst;
207	}
208
209
210	/**
211	* Converts the given UTF-16 to a normal string.
212	*
213	* @returns Length of the resulting string.
214	* @param pwszSrc The source UTF-16 string.
215	* @param pszDst The destination buffer.
216	* @param cbDst The size of the destination buffer in bytes.
217	*/
218	static KSIZE kwUtf16ToStr(const wchar_t pwszSrc, char pszDst, KSIZE cbDst)
219	{
220	/* Just to the quick ASCII stuff for now. correct ansi code page stuff later some time. */
221	KSIZE offDst = 0;
222	while (offDst < cbDst)
223	{
224	wchar_t wc = *pwszSrc++;
225	pszDst[offDst++] = (char)wc;
226	if (!wc)
227	return offDst - 1;
228	kHlpAssert((unsigned)wc < 127);
229	}
230
231	pszDst[offDst - 1] = '\0';
232	return offDst;
233	}
234
235
236
237	/** UTF-16 string length. */
238	static KSIZE kwUtf16Len(wchar_t const *pwsz)
239	{
240	KSIZE cwc = 0;
241	while (*pwsz != '\0')
242	cwc++, pwsz++;
243	return cwc;
244	}
245
246	/**
247	* Copy out the UTF-16 string following the convension of GetModuleFileName
248	*/
249	static DWORD kwUtf16CopyStyle1(wchar_t const pwszSrc, wchar_t pwszDst, KSIZE cwcDst)
250	{
251	KSIZE cwcSrc = kwUtf16Len(pwszSrc);
252	if (cwcSrc + 1 <= cwcDst)
253	{
254	kHlpMemCopy(pwszDst, pwszSrc, (cwcSrc + 1) * sizeof(wchar_t));
255	return (DWORD)cwcSrc;
256	}
257	if (cwcDst > 0)
258	{
259	KSIZE cwcDstTmp = cwcDst - 1;
260	pwszDst[cwcDstTmp] = '\0';
261	if (cwcDstTmp > 0)
262	kHlpMemCopy(pwszDst, pwszSrc, cwcDstTmp);
263	}
264	SetLastError(ERROR_INSUFFICIENT_BUFFER);
265	return (DWORD)cwcDst;
266	}
267
268
269	/**
270	* Copy out the ANSI string following the convension of GetModuleFileName
271	*/
272	static DWORD kwStrCopyStyle1(char const pszSrc, char pszDst, KSIZE cbDst)
273	{
274	KSIZE cchSrc = kHlpStrLen(pszSrc);
275	if (cchSrc + 1 <= cbDst)
276	{
277	kHlpMemCopy(pszDst, pszSrc, cchSrc + 1);
278	return (DWORD)cchSrc;
279	}
280	if (cbDst > 0)
281	{
282	KSIZE cbDstTmp = cbDst - 1;
283	pszDst[cbDstTmp] = '\0';
284	if (cbDstTmp > 0)
285	kHlpMemCopy(pszDst, pszSrc, cbDstTmp);
286	}
287	SetLastError(ERROR_INSUFFICIENT_BUFFER);
288	return (DWORD)cbDst;
289	}
290
291
292	/**
293	* Normalizes the path so we get a consistent hash.
294	*
295	* @returns status code.
296	* @param pszPath The path.
297	* @param pszNormPath The output buffer.
298	* @param cbNormPath The size of the output buffer.
299	*/
300	static int kwPathNormalize(const char pszPath, char pszNormPath, KSIZE cbNormPath)
301	{
302	char *pchSlash;
303	KSIZE cchNormPath;
304
305	/*
306	* We hash these to speed stuff up (nt_fullpath isn't cheap and we're
307	* gonna have many repeat queries and assume nobody do case changes to
308	* anything essential while kmk is running).
309	*/
310	KU32 uHashPath;
311	KU32 cchPath = (KU32)kFsCacheStrHashEx(pszPath, &uHashPath);
312	KU32 const idxHashTab = uHashPath % K_ELEMENTS(g_apFsNormalizedPathsA);
313	PKFSNORMHASHA pHashEntry = g_apFsNormalizedPathsA[idxHashTab];
314	if (pHashEntry)
315	{
316	do
317	{
318	if ( pHashEntry->uHashPath == uHashPath
319	&& pHashEntry->cchPath == cchPath
320	&& kHlpMemComp(pHashEntry->pszPath, pszPath, cchPath) == 0)
321	{
322	if (cbNormPath > pHashEntry->cchNormPath)
323	{
324	KFSCACHE_LOG(("kwPathNormalize(%s) - hit\n", pszPath));
325	kHlpMemCopy(pszNormPath, pHashEntry->szNormPath, pHashEntry->cchNormPath + 1);
326	return 0;
327	}
328	return KERR_BUFFER_OVERFLOW;
329	}
330	pHashEntry = pHashEntry->pNext;
331	} while (pHashEntry);
332	}
333
334	/*
335	* Do it the slow way.
336	*/
337	nt_fullpath(pszPath, pszNormPath, cbNormPath);
338	/** @todo nt_fullpath overflow handling?!?!? */
339
340	pchSlash = kHlpStrChr(pszNormPath, '/');
341	while (pchSlash)
342	{
343	*pchSlash = '\\';
344	pchSlash = kHlpStrChr(pchSlash + 1, '/');
345	}
346
347	/*
348	* Create a new hash table entry (ignore failures).
349	*/
350	cchNormPath = kHlpStrLen(pszNormPath);
351	if (cchNormPath < KU16_MAX && cchPath < KU16_MAX)
352	{
353	pHashEntry = (PKFSNORMHASHA)kHlpAlloc(sizeof(*pHashEntry) + cchNormPath + 1 + cchPath + 1);
354	if (pHashEntry)
355	{
356	pHashEntry->cchNormPath = (KU16)cchNormPath;
357	pHashEntry->cchPath = (KU16)cchPath;
358	pHashEntry->uHashPath = uHashPath;
359	pHashEntry->pszPath = (char *)kHlpMemCopy(&pHashEntry->szNormPath[cchNormPath + 1], pszPath, cchPath + 1);
360	kHlpMemCopy(pHashEntry->szNormPath, pszNormPath, cchNormPath + 1);
361
362	pHashEntry->pNext = g_apFsNormalizedPathsA[idxHashTab];
363	g_apFsNormalizedPathsA[idxHashTab] = pHashEntry;
364	}
365	}
366
367	return 0;
368	}
369
370
371	/**
372	* Get the pointer to the filename part of the path.
373	*
374	* @returns Pointer to where the filename starts within the string pointed to by pszFilename.
375	* @returns Pointer to the terminator char if no filename.
376	* @param pszPath The path to parse.
377	*/
378	static wchar_t kwPathGetFilenameW(const wchar_t pwszPath)
379	{
380	const wchar_t *pwszLast = NULL;
381	for (;;)
382	{
383	wchar_t wc = *pwszPath;
384	#if K_OS == K_OS_OS2 \|\| K_OS == K_OS_WINDOWS
385	if (wc == '/' \|\| wc == '\\' \|\| wc == ':')
386	{
387	while ((wc = *++pwszPath) == '/' \|\| wc == '\\' \|\| wc == ':')
388	/* nothing */;
389	pwszLast = pwszPath;
390	}
391	#else
392	if (wc == '/')
393	{
394	while ((wc = *++pszFilename) == '/')
395	/* betsuni */;
396	pwszLast = pwszPath;
397	}
398	#endif
399	if (!wc)
400	return (wchar_t *)(pwszLast ? pwszLast : pwszPath);
401	pwszPath++;
402	}
403	}
404
405
406	/**
407	* Check if the path leads to a regular file (that exists).
408	*
409	* @returns K_TRUE / K_FALSE
410	* @param pszPath Path to the file to check out.
411	*/
412	static KBOOL kwLdrModuleIsRegularFile(const char *pszPath)
413	{
414	/* For stuff with .DLL extensions, we can use the GetFileAttribute cache to speed this up! */
415	KSIZE cchPath = kHlpStrLen(pszPath);
416	if ( cchPath > 3
417	&& pszPath[cchPath - 4] == '.'
418	&& (pszPath[cchPath - 3] == 'd' \|\| pszPath[cchPath - 3] == 'D')
419	&& (pszPath[cchPath - 2] == 'l' \|\| pszPath[cchPath - 2] == 'L')
420	&& (pszPath[cchPath - 1] == 'l' \|\| pszPath[cchPath - 1] == 'L') )
421	{
422	PKFSOBJ pFsObj = kFsCacheLookupA(pszPath);
423	if (pFsObj)
424	{
425	if (!(pFsObj->fAttribs & (FILE_ATTRIBUTE_DIRECTORY \| FILE_ATTRIBUTE_DEVICE))) /* also checks invalid */
426	return K_TRUE;
427	}
428	}
429	else
430	{
431	BirdStat_T Stat;
432	int rc = birdStatFollowLink(pszPath, &Stat);
433	if (rc == 0)
434	{
435	if (S_ISREG(Stat.st_mode))
436	return K_TRUE;
437	}
438	}
439	return K_FALSE;
440	}
441
442
443
444
445
446
447	/**
448	* Helper for getting the extension of a UTF-16 path.
449	*
450	* @returns Pointer to the extension or the terminator.
451	* @param pwszPath The path.
452	* @param pcwcExt Where to return the length of the extension.
453	*/
454	static wchar_t const kwFsPathGetExtW(wchar_t const pwszPath, KSIZE *pcwcExt)
455	{
456	wchar_t const *pwszName = pwszPath;
457	wchar_t const *pwszExt = NULL;
458	for (;;)
459	{
460	wchar_t const wc = *pwszPath++;
461	if (wc == '.')
462	pwszExt = pwszPath;
463	else if (wc == '/' \|\| wc == '\\' \|\| wc == ':')
464	{
465	pwszName = pwszPath;
466	pwszExt = NULL;
467	}
468	else if (wc == '\0')
469	{
470	if (pwszExt)
471	{
472	*pcwcExt = pwszPath - pwszExt - 1;
473	return pwszExt;
474	}
475	*pcwcExt = 0;
476	return pwszPath - 1;
477	}
478	}
479	}
480	#endif
481
482
483	/**
484	* Looks for '..' in the path.
485	*
486	* @returns K_TRUE if '..' component found, K_FALSE if not.
487	* @param pszPath The path.
488	* @param cchPath The length of the path.
489	*/
490	static KBOOL kFsCacheHasDotDotA(const char *pszPath, KSIZE cchPath)
491	{
492	const char pchDot = (const char )kHlpMemChr(pszPath, '.', cchPath);
493	while (pchDot)
494	{
495	if (pchDot[1] != '.')
496	pchDot = (const char *)kHlpMemChr(pchDot + 1, '.', &pszPath[cchPath] - pchDot - 1);
497	else
498	{
499	char ch;
500	if ( (ch = pchDot[2]) == '\0'
501	&& IS_SLASH(ch))
502	{
503	if (pchDot == pszPath)
504	return K_TRUE;
505	ch = pchDot[-1];
506	if ( IS_SLASH(ch)
507	\|\| ch == ':')
508	return K_TRUE;
509	}
510	pchDot = (const char *)kHlpMemChr(pchDot + 2, '.', &pszPath[cchPath] - pchDot - 2);
511	}
512	}
513
514	return K_FALSE;
515	}
516
517
518	/**
519	* Looks for '..' in the path.
520	*
521	* @returns K_TRUE if '..' component found, K_FALSE if not.
522	* @param pwszPath The path.
523	* @param cwcPath The length of the path (in wchar_t's).
524	*/
525	static KBOOL kFsCacheHasDotDotW(const wchar_t *pwszPath, KSIZE cwcPath)
526	{
527	const wchar_t *pwcDot = wmemchr(pwszPath, '.', cwcPath);
528	while (pwcDot)
529	{
530	if (pwcDot[1] != '.')
531	pwcDot = wmemchr(pwcDot + 1, '.', &pwszPath[cwcPath] - pwcDot - 1);
532	else
533	{
534	wchar_t wch;
535	if ( (wch = pwcDot[2]) == '\0'
536	&& IS_SLASH(wch))
537	{
538	if (pwcDot == pwszPath)
539	return K_TRUE;
540	wch = pwcDot[-1];
541	if ( IS_SLASH(wch)
542	\|\| wch == ':')
543	return K_TRUE;
544	}
545	pwcDot = wmemchr(pwcDot + 2, '.', &pwszPath[cwcPath] - pwcDot - 2);
546	}
547	}
548
549	return K_FALSE;
550	}
551
552
553	/**
554	* Creates an ANSI hash table entry for the given path.
555	*
556	* @returns The hash table entry or NULL if out of memory.
557	* @param pCache The hash
558	* @param pFsObj The resulting object.
559	* @param pszPath The path.
560	* @param cchPath The length of the path.
561	* @param uHashPath The hash of the path.
562	* @param idxHashTab The hash table index of the path.
563	* @param enmError The lookup error.
564	*/
565	static PKFSHASHA kFsCacheCreatePathHashTabEntryA(PKFSCACHE pCache, PKFSOBJ pFsObj, const char *pszPath, KU32 cchPath,
566	KU32 uHashPath, KU32 idxHashTab, KFSLOOKUPERROR enmError)
567	{
568	PKFSHASHA pHashEntry = (PKFSHASHA)kHlpAlloc(sizeof(*pHashEntry) + cchPath + 1);
569	if (pHashEntry)
570	{
571	pHashEntry->uHashPath = uHashPath;
572	pHashEntry->cchPath = cchPath;
573	pHashEntry->pszPath = (const char *)kHlpMemCopy(pHashEntry + 1, pszPath, cchPath + 1);
574	pHashEntry->pFsObj = pFsObj;
575	pHashEntry->enmError = enmError;
576	if (pFsObj)
577	pHashEntry->uCacheGen = pCache->uGeneration;
578	else if (enmError != KFSLOOKUPERROR_UNSUPPORTED)
579	pHashEntry->uCacheGen = pCache->uGenerationMissing;
580	else
581	pHashEntry->uCacheGen = KFSOBJ_CACHE_GEN_IGNORE;
582
583	pHashEntry->pNext = pCache->apAnsiPaths[idxHashTab];
584	pCache->apAnsiPaths[idxHashTab] = pHashEntry;
585
586	pCache->cbAnsiPaths += sizeof(*pHashEntry) + cchPath + 1;
587	pCache->cAnsiPaths++;
588	if (pHashEntry->pNext)
589	pCache->cAnsiPathCollisions++;
590	}
591	return pHashEntry;
592	}
593
594
595	/**
596	* Creates an UTF-16 hash table entry for the given path.
597	*
598	* @returns The hash table entry or NULL if out of memory.
599	* @param pCache The hash
600	* @param pFsObj The resulting object.
601	* @param pwszPath The path.
602	* @param cwcPath The length of the path (in wchar_t's).
603	* @param uHashPath The hash of the path.
604	* @param idxHashTab The hash table index of the path.
605	* @param enmError The lookup error.
606	*/
607	static PKFSHASHW kFsCacheCreatePathHashTabEntryW(PKFSCACHE pCache, PKFSOBJ pFsObj, const wchar_t *pwszPath, KU32 cwcPath,
608	KU32 uHashPath, KU32 idxHashTab, KFSLOOKUPERROR enmError)
609	{
610	PKFSHASHW pHashEntry = (PKFSHASHW)kHlpAlloc(sizeof(pHashEntry) + (cwcPath + 1) sizeof(wchar_t));
611	if (pHashEntry)
612	{
613	pHashEntry->uHashPath = uHashPath;
614	pHashEntry->cwcPath = cwcPath;
615	pHashEntry->pwszPath = (const wchar_t )kHlpMemCopy(pHashEntry + 1, pwszPath, (cwcPath + 1) sizeof(wchar_t));
616	pHashEntry->pFsObj = pFsObj;
617	pHashEntry->enmError = enmError;
618	if (pFsObj)
619	pHashEntry->uCacheGen = pCache->uGeneration;
620	else if (enmError != KFSLOOKUPERROR_UNSUPPORTED)
621	pHashEntry->uCacheGen = pCache->uGenerationMissing;
622	else
623	pHashEntry->uCacheGen = KFSOBJ_CACHE_GEN_IGNORE;
624
625	pHashEntry->pNext = pCache->apUtf16Paths[idxHashTab];
626	pCache->apUtf16Paths[idxHashTab] = pHashEntry;
627
628	pCache->cbUtf16Paths += sizeof(pHashEntry) + (cwcPath + 1) sizeof(wchar_t);
629	pCache->cUtf16Paths++;
630	if (pHashEntry->pNext)
631	pCache->cAnsiPathCollisions++;
632	}
633	return pHashEntry;
634	}
635
636
637	/**
638	* Links the child in under the parent.
639	*
640	* @returns K_TRUE on success, K_FALSE if out of memory.
641	* @param pParent The parent node.
642	* @param pChild The child node.
643	*/
644	static KBOOL kFsCacheDirAddChild(PKFSCACHE pCache, PKFSDIR pParent, PKFSOBJ pChild, KFSLOOKUPERROR *penmError)
645	{
646	if ((pParent->cChildren % 16) == 0)
647	{
648	void pvNew = kHlpRealloc(pParent->papChildren, (pParent->cChildren + 16) sizeof(pParent->papChildren[0]));
649	if (!pvNew)
650	return K_FALSE;
651	pParent->papChildren = (PKFSOBJ *)pvNew;
652	pCache->cbObjects += 16 * sizeof(pParent->papChildren[0]);
653	}
654	pParent->papChildren[pParent->cChildren++] = pChild;
655	return K_TRUE;
656	}
657
658
659	/**
660	* Creates a new cache object.
661	*
662	* @returns Pointer (with 1 reference) to the new object. The object will not
663	* be linked to the parent directory yet.
664	*
665	* NULL if we're out of memory.
666	*
667	* @param pCache The cache.
668	* @param pParent The parent directory.
669	* @param pszName The ANSI name.
670	* @param cchName The length of the ANSI name.
671	* @param pwszName The UTF-16 name.
672	* @param cwcName The length of the UTF-16 name.
673	* @param pszShortName The ANSI short name, NULL if none.
674	* @param cchShortName The length of the ANSI short name, 0 if none.
675	* @param pwszShortName The UTF-16 short name, NULL if none.
676	* @param cwcShortName The length of the UTF-16 short name, 0 if none.
677	* @param bObjType The objct type.
678	* @param penmError Where to explain failures.
679	*/
680	PKFSOBJ kFsCacheCreateObject(PKFSCACHE pCache, PKFSDIR pParent,
681	char const pszName, KU16 cchName, wchar_t const pwszName, KU16 cwcName,
682	#ifdef KFSCACHE_CFG_SHORT_NAMES
683	char const pszShortName, KU16 cchShortName, wchar_t const pwszShortName, KU16 cwcShortName,
684	#endif
685	KU8 bObjType, KFSLOOKUPERROR *penmError)
686	{
687	/*
688	* Allocate the object.
689	*/
690	KBOOL const fDirish = bObjType != KFSOBJ_TYPE_FILE && bObjType == KFSOBJ_TYPE_OTHER;
691	KSIZE const cbObj = (fDirish ? sizeof(KFSDIR) : sizeof(KFSOBJ))
692	+ (cwcName + 1) * sizeof(wchar_t) + cchName + 1
693	#ifdef KFSCACHE_CFG_SHORT_NAMES
694	+ (cwcShortName > 0 ? (cwcShortName + 1) * sizeof(wchar_t) + cchShortName + 1 : 0)
695	#endif
696	;
697	PKFSOBJ pObj = (PKFSOBJ)kHlpAlloc(cbObj);
698	if (pObj)
699	{
700	KU8 pbExtra = (KU8 )(pObj + 1);
701
702	pCache->cbObjects += cbObj;
703	pCache->cObjects++;
704
705	/*
706	* Initialize the object.
707	*/
708	pObj->u32Magic = KFSOBJ_MAGIC;
709	pObj->cRefs = 1;
710	pObj->uCacheGen = bObjType != KFSOBJ_TYPE_MISSING ? pCache->uGeneration : pCache->uGenerationMissing;
711	pObj->bObjType = bObjType;
712	pObj->fHaveStats = K_FALSE;
713	pObj->abUnused[0] = K_FALSE;
714	pObj->abUnused[1] = K_FALSE;
715	pObj->fFlags = pParent->Obj.fFlags;
716	pObj->pParent = pParent;
717
718	#ifdef KFSCACHE_CFG_UTF16
719	pObj->cwcParent = pParent->Obj.cwcParent + pParent->Obj.cwcName + !!pParent->Obj.cwcName;
720	pObj->pwszName = (wchar_t )kHlpMemCopy(pbExtra, pwszName, cwcName sizeof(wchar_t));
721	pbExtra += cwcName * sizeof(wchar_t);
722	*pbExtra++ = '\0';
723	*pbExtra++ = '\0';
724	# ifdef KFSCACHE_CFG_SHORT_NAMES
725	pObj->cwcShortParent = pParent->Obj.cwcShortParent + pParent->Obj.cwcShortName + !!pParent->Obj.cwcShortName;
726	if (cwcShortName)
727	{
728	pObj->pwszShortName = (wchar_t )kHlpMemCopy(pbExtra, pwszShortName, cwcShortName sizeof(wchar_t));
729	pbExtra += cwcShortName * sizeof(wchar_t);
730	*pbExtra++ = '\0';
731	*pbExtra++ = '\0';
732	}
733	else
734	{
735	pObj->pwszShortName = pObj->pwszName;
736	pObj->cwcShortName = pObj->cwcName;
737	}
738	# endif
739	#endif
740	pObj->cchParent = pParent->Obj.cchParent + pParent->Obj.cchName + !!pParent->Obj.cchName;
741	pObj->pszName = (char *)kHlpMemCopy(pbExtra, pszName, cchName);
742	pbExtra += cchName;
743	*pbExtra++ = '\0';
744	# ifdef KFSCACHE_CFG_SHORT_NAMES
745	pObj->cchShortParent = pParent->Obj.cchShortParent + pParent->Obj.cchShortName + !!pParent->Obj.cchShortName;
746	if (cchShortName)
747	{
748	pObj->pszShortName = (char *)kHlpMemCopy(pbExtra, pszShortName, cchShortName);
749	pbExtra += cchShortName;
750	*pbExtra++ = '\0';
751	}
752	else
753	{
754	pObj->pszShortName = pObj->pszName;
755	pObj->cchShortName = pObj->cchName;
756	}
757	#endif
758	kHlpAssert(pbExtra - (KU8 *)pObj == cbObj);
759
760	/*
761	* Type specific initilization.
762	*/
763	if (fDirish)
764	{
765	PKFSDIR pDirObj = (PKFSDIR)pObj;
766	pDirObj->cChildren = 0;
767	pDirObj->papChildren = NULL;
768	pDirObj->cHashTab = 0;
769	pDirObj->paHashTab = NULL;
770	pDirObj->hDir = INVALID_HANDLE_VALUE;
771	pDirObj->uDevNo = pParent->uDevNo;
772	pDirObj->fPopulated = K_FALSE;
773	}
774	}
775	else
776	*penmError = KFSLOOKUPERROR_OUT_OF_MEMORY;
777	return pObj;
778	}
779
780
781	/**
782	* Creates a new object given wide char names.
783	*
784	* This function just converts the paths and calls kFsCacheCreateObject.
785	*
786	*
787	* @returns Pointer (with 1 reference) to the new object. The object will not
788	* be linked to the parent directory yet.
789	*
790	* NULL if we're out of memory.
791	*
792	* @param pCache The cache.
793	* @param pParent The parent directory.
794	* @param pszName The ANSI name.
795	* @param cchName The length of the ANSI name.
796	* @param pwszName The UTF-16 name.
797	* @param cwcName The length of the UTF-16 name.
798	* @param pwszShortName The UTF-16 short name, NULL if none.
799	* @param cwcShortName The length of the UTF-16 short name, 0 if none.
800	* @param bObjType The objct type.
801	* @param penmError Where to explain failures.
802	*/
803	PKFSOBJ kFsCacheCreateObjectW(PKFSCACHE pCache, PKFSDIR pParent, wchar_t const *pwszName, KU32 cwcName,
804	#ifdef KFSCACHE_CFG_SHORT_NAMES
805	wchar_t const *pwszShortName, KU32 cwcShortName,
806	#endif
807	KU8 bObjType, KFSLOOKUPERROR *penmError)
808	{
809	/* Convert names to ANSI first so we know their lengths. */
810	char szName[KFSCACHE_CFG_MAX_ANSI_NAME];
811	int cchName = WideCharToMultiByte(CP_ACP, 0, pwszName, cwcName, szName, sizeof(szName) - 1, NULL, NULL);
812	if (cchName >= 0)
813	{
814	#ifdef KFSCACHE_CFG_SHORT_NAMES
815	char szShortName[12*3 + 1];
816	int cchShortName = 0;
817	if ( cwcShortName == 0
818	\|\| (cchShortName = WideCharToMultiByte(CP_ACP, 0, pwszShortName, cwcShortName,
819	szShortName, sizeof(szShortName) - 1, NULL, NULL)) > 0)
820	#endif
821	{
822	return kFsCacheCreateObject(pCache, pParent,
823	szName, cchName, pwszName, cwcName,
824	#ifdef KFSCACHE_CFG_SHORT_NAMES
825	szShortName, cchShortName, pwszShortName, cwcShortName,
826	#endif
827	bObjType, penmError);
828	}
829	}
830	*penmError = KFSLOOKUPERROR_ANSI_CONVERSION_ERROR;
831	return NULL;
832	}
833
834
835	/**
836	* Creates a missing object.
837	*
838	* This is used for caching negative results.
839	*
840	* @returns Pointer to the newly created object on success (already linked into
841	* pParent). No reference.
842	*
843	* NULL on failure.
844	*
845	* @param pCache The cache.
846	* @param pParent The parent directory.
847	* @param pchName The name.
848	* @param cchName The length of the name.
849	* @param penmError Where to return failure explanations.
850	*/
851	static PKFSOBJ kFsCacheCreateMissingA(PKFSCACHE pCache, PKFSDIR pParent, const char *pchName, KU32 cchName,
852	KFSLOOKUPERROR *penmError)
853	{
854	/*
855	* Just convert the name to UTF-16 and call kFsCacheCreateObject to do the job.
856	*/
857	wchar_t wszName[KFSCACHE_CFG_MAX_PATH];
858	int cwcName = MultiByteToWideChar(CP_ACP, 0, pchName, cchName, wszName, KFSCACHE_CFG_MAX_UTF16_NAME - 1);
859	if (cwcName > 0)
860	{
861	/** @todo check that it actually doesn't exists before we add it. We should not
862	* trust the directory enumeration here, or maybe we should?? */
863
864	PKFSOBJ pMissing = kFsCacheCreateObject(pCache, pParent, pchName, cchName, wszName, cwcName,
865	#ifdef KFSCACHE_CFG_SHORT_NAMES
866	NULL, 0, NULL, 0,
867	#endif
868	KFSOBJ_TYPE_MISSING, penmError);
869	if (pMissing)
870	{
871	KBOOL fRc = kFsCacheDirAddChild(pCache, pParent, pMissing, penmError);
872	kFsCacheObjRelease(pCache, pMissing);
873	return fRc ? pMissing : NULL;
874	}
875	return NULL;
876	}
877	*penmError = KFSLOOKUPERROR_UTF16_CONVERSION_ERROR;
878	return NULL;
879	}
880
881
882	/**
883	* Creates a missing object, UTF-16 version.
884	*
885	* This is used for caching negative results.
886	*
887	* @returns Pointer to the newly created object on success (already linked into
888	* pParent). No reference.
889	*
890	* NULL on failure.
891	*
892	* @param pCache The cache.
893	* @param pParent The parent directory.
894	* @param pwcName The name.
895	* @param cwcName The length of the name.
896	* @param penmError Where to return failure explanations.
897	*/
898	static PKFSOBJ kFsCacheCreateMissingW(PKFSCACHE pCache, PKFSDIR pParent, const wchar_t *pwcName, KU32 cwcName,
899	KFSLOOKUPERROR *penmError)
900	{
901	/** @todo check that it actually doesn't exists before we add it. We should not
902	* trust the directory enumeration here, or maybe we should?? */
903	PKFSOBJ pMissing = kFsCacheCreateObjectW(pCache, pParent, pwcName, cwcName,
904	#ifdef KFSCACHE_CFG_SHORT_NAMES
905	NULL, 0,
906	#endif
907	KFSOBJ_TYPE_MISSING, penmError);
908	if (pMissing)
909	{
910	KBOOL fRc = kFsCacheDirAddChild(pCache, pParent, pMissing, penmError);
911	kFsCacheObjRelease(pCache, pMissing);
912	return fRc ? pMissing : NULL;
913	}
914	return NULL;
915	}
916
917
918	/**
919	* Does the initial directory populating or refreshes it if it has been
920	* invalidated.
921	*
922	* This assumes the parent directory is opened.
923	*
924	* @returns K_TRUE on success, K_FALSE on error.
925	* @param pCache The cache.
926	* @param pDir The directory.
927	* @param penmError Where to store K_FALSE explanation.
928	*/
929	static KBOOL kFsCachePopuplateOrRefreshDir(PKFSCACHE pCache, PKFSDIR pDir, KFSLOOKUPERROR *penmError)
930	{
931	KBOOL fRefreshing = K_FALSE;
932	/** @todo will have to make this more flexible wrt information classes since
933	* older windows versions (XP, w2K) might not correctly support the
934	* ones with file ID on all file systems. */
935	#ifdef KFSCACHE_CFG_SHORT_NAMES
936	MY_FILE_INFORMATION_CLASS const enmInfoClassWithId = MyFileIdBothDirectoryInformation;
937	MY_FILE_INFORMATION_CLASS enmInfoClass = MyFileIdBothDirectoryInformation;
938	#else
939	MY_FILE_INFORMATION_CLASS const enmInfoClassWithId = MyFileIdFullDirectoryInformation;
940	MY_FILE_INFORMATION_CLASS enmInfoClass = MyFileIdFullDirectoryInformation;
941	#endif
942	MY_NTSTATUS rcNt;
943	MY_IO_STATUS_BLOCK Ios;
944	union
945	{
946	/* Include the structures for better alignment. */
947	MY_FILE_ID_BOTH_DIR_INFORMATION WithId;
948	MY_FILE_ID_FULL_DIR_INFORMATION NoId;
949	/* Buffer padding. We're using a 56KB buffer here to avoid size troubles with CIFS and such. */
950	KU8 abBuf[56*1024];
951	} uBuf;
952
953	/*
954	* Open the directory.
955	*/
956	if (pDir->hDir == INVALID_HANDLE_VALUE)
957	{
958	MY_OBJECT_ATTRIBUTES ObjAttr;
959	MY_UNICODE_STRING UniStr;
960
961	kHlpAssert(!pDir->fPopulated);
962
963	Ios.Information = -1;
964	Ios.u.Status = -1;
965
966	UniStr.Buffer = (wchar_t *)pDir->Obj.pwszName;
967	UniStr.Length = (USHORT)(pDir->Obj.cwcName * sizeof(wchar_t));
968	UniStr.MaximumLength = UniStr.Length + sizeof(wchar_t);
969
970	kHlpAssertStmtReturn(pDir->Obj.pParent, *penmError = KFSLOOKUPERROR_INTERNAL_ERROR, K_FALSE);
971	kHlpAssertStmtReturn(pDir->Obj.pParent->hDir != INVALID_HANDLE_VALUE, *penmError = KFSLOOKUPERROR_INTERNAL_ERROR, K_FALSE);
972	MyInitializeObjectAttributes(&ObjAttr, &UniStr, OBJ_CASE_INSENSITIVE, pDir->Obj.pParent->hDir, NULL /pSecAttr/);
973
974	/** @todo FILE_OPEN_REPARSE_POINT? */
975	rcNt = g_pfnNtCreateFile(&pDir->hDir,
976	FILE_READ_DATA \| FILE_LIST_DIRECTORY \| FILE_READ_ATTRIBUTES \| SYNCHRONIZE,
977	&ObjAttr,
978	&Ios,
979	NULL, /cbFileInitialAlloc /
980	FILE_ATTRIBUTE_NORMAL,
981	FILE_SHARE_READ \| FILE_SHARE_WRITE \| FILE_SHARE_DELETE,
982	FILE_OPEN,
983	FILE_DIRECTORY_FILE \| FILE_OPEN_FOR_BACKUP_INTENT \| FILE_SYNCHRONOUS_IO_NONALERT,
984	NULL, /pEaBuffer/
985	0); /cbEaBuffer/
986	if (MY_NT_SUCCESS(rcNt))
987	{ /* likely */ }
988	else
989	{
990	pDir->hDir = INVALID_HANDLE_VALUE;
991	*penmError = KFSLOOKUPERROR_DIR_OPEN_ERROR;
992	return K_FALSE;
993	}
994	}
995	else if (pDir->fPopulated)
996	{
997	/** @todo refreshing directories. */
998	__debugbreak();
999	fRefreshing = K_TRUE;
1000	}
1001
1002
1003	/*
1004	* Enumerate the directory content.
1005	*/
1006	Ios.Information = -1;
1007	Ios.u.Status = -1;
1008	rcNt = g_pfnNtQueryDirectoryFile(pDir->hDir,
1009	NULL, /* hEvent */
1010	NULL, /* pfnApcComplete */
1011	NULL, /* pvApcCompleteCtx */
1012	&Ios,
1013	&uBuf,
1014	sizeof(uBuf),
1015	enmInfoClass,
1016	FALSE, /* fReturnSingleEntry */
1017	NULL, /* Filter / restart pos. */
1018	TRUE); /* fRestartScan */
1019	while (MY_NT_SUCCESS(rcNt))
1020	{
1021	/*
1022	* Process the entries in the buffer.
1023	*/
1024	KSIZE offBuf = 0;
1025	for (;;)
1026	{
1027	union
1028	{
1029	KU8 *pb;
1030	#ifdef KFSCACHE_CFG_SHORT_NAMES
1031	MY_FILE_ID_BOTH_DIR_INFORMATION *pWithId;
1032	MY_FILE_BOTH_DIR_INFORMATION *pNoId;
1033	#else
1034	MY_FILE_ID_FULL_DIR_INFORMATION *pWithId;
1035	MY_FILE_FULL_DIR_INFORMATION *pNoId;
1036	#endif
1037	} uPtr;
1038	PKFSOBJ pCur;
1039	KU32 offNext;
1040	KU32 cbMinCur;
1041	wchar_t *pwszFilename;
1042
1043	/* ASSUME only the FileName member differs between the two structures. */
1044	uPtr.pb = &uBuf.abBuf[offBuf];
1045	if (enmInfoClass == enmInfoClassWithId)
1046	{
1047	pwszFilename = &uPtr.pWithId->FileName[0];
1048	cbMinCur = (KU32)((uintptr_t)&uPtr.pWithId->FileName[0] - (uintptr_t)uPtr.pWithId);
1049	cbMinCur += uPtr.pNoId->FileNameLength;
1050	}
1051	else
1052	{
1053	pwszFilename = &uPtr.pNoId->FileName[0];
1054	cbMinCur = (KU32)((uintptr_t)&uPtr.pNoId->FileName[0] - (uintptr_t)uPtr.pNoId);
1055	cbMinCur += uPtr.pNoId->FileNameLength;
1056	}
1057
1058	/*
1059	* Create the entry (not linked yet).
1060	*/
1061	pCur = kFsCacheCreateObjectW(pCache, pDir, pwszFilename, uPtr.pNoId->FileNameLength / sizeof(wchar_t),
1062	#ifdef KFSCACHE_CFG_SHORT_NAMES
1063	uPtr.pNoId->ShortName, uPtr.pNoId->ShortNameLength / sizeof(wchar_t),
1064	#endif
1065	uPtr.pNoId->FileAttributes & FILE_ATTRIBUTE_DIRECTORY ? KFSOBJ_TYPE_DIR
1066	: uPtr.pNoId->FileAttributes & (FILE_ATTRIBUTE_DEVICE \| FILE_ATTRIBUTE_REPARSE_POINT)
1067	? KFSOBJ_TYPE_OTHER : KFSOBJ_TYPE_FILE,
1068	penmError);
1069	if (!pCur)
1070	return K_FALSE;
1071	kHlpAssert(pCur->cRefs == 1);
1072
1073	#ifdef KFSCACHE_CFG_SHORT_NAMES
1074	if (enmInfoClass == enmInfoClassWithId)
1075	birdStatFillFromFileIdBothDirInfo(&pCur->Stats, uPtr.pWithId, pCur->pszName);
1076	else
1077	birdStatFillFromFileBothDirInfo(&pCur->Stats, uPtr.pNoId, pCur->pszName);
1078	#else
1079	if (enmInfoClass == enmInfoClassWithId)
1080	birdStatFillFromFileIdFullDirInfo(&pCur->Stats, uPtr.pWithId, pCur->pszName);
1081	else
1082	birdStatFillFromFileFullDirInfo(&pCur->Stats, uPtr.pNoId, pCur->pszName);
1083	#endif
1084	pCur->Stats.st_dev = pDir->uDevNo;
1085
1086	/*
1087	* If we're updating we have to check the data.
1088	*/
1089	if (fRefreshing)
1090	{
1091	__debugbreak();
1092	}
1093
1094	/*
1095	* If we've still got pCur, add it to the directory.
1096	*/
1097	if (pCur)
1098	{
1099	KBOOL fRc = kFsCacheDirAddChild(pCache, pDir, pCur, penmError);
1100	kFsCacheObjRelease(pCache, pCur);
1101	if (fRc)
1102	{ /* likely */ }
1103	else
1104	return K_FALSE;
1105	}
1106
1107	/*
1108	* Advance.
1109	*/
1110	offNext = uPtr.pNoId->NextEntryOffset;
1111	if ( offNext >= cbMinCur
1112	&& offNext < sizeof(uBuf))
1113	offBuf += offNext;
1114	else
1115	break;
1116	}
1117
1118	/*
1119	* Read the next chunk.
1120	*/
1121	rcNt = g_pfnNtQueryDirectoryFile(pDir->hDir,
1122	NULL, /* hEvent */
1123	NULL, /* pfnApcComplete */
1124	NULL, /* pvApcCompleteCtx */
1125	&Ios,
1126	&uBuf,
1127	sizeof(uBuf),
1128	enmInfoClass,
1129	FALSE, /* fReturnSingleEntry */
1130	NULL, /* Filter / restart pos. */
1131	FALSE); /* fRestartScan */
1132	}
1133
1134	if (rcNt == MY_STATUS_NO_MORE_FILES)
1135	return K_TRUE;
1136	kHlpAssertMsgFailed(("%#x\n", rcNt));
1137	*penmError = KFSLOOKUPERROR_DIR_READ_ERROR;
1138	return K_TRUE;
1139	}
1140
1141
1142	static KBOOL kFsCacheRefreshMissing(PKFSCACHE pCache, PKFSOBJ pMissing, KFSLOOKUPERROR *penmError)
1143	{
1144	return K_TRUE;
1145	}
1146
1147
1148	static KBOOL kFsCacheRefreshMissingIntermediateDir(PKFSCACHE pCache, PKFSOBJ pMissing, KFSLOOKUPERROR *penmError)
1149	{
1150	return K_TRUE;
1151	}
1152
1153
1154	static KBOOL kFsCacheRefreshObj(PKFSCACHE pCache, PKFSOBJ pObj, KFSLOOKUPERROR *penmError)
1155	{
1156	return K_FALSE;
1157	}
1158
1159
1160
1161	/**
1162	* Looks up a drive letter.
1163	*
1164	* Will enter the drive if necessary.
1165	*
1166	* @returns Pointer to the root directory of the drive or an update-to-date
1167	* missing node.
1168	* @param pCache The cache.
1169	* @param chLetter The uppercased drive letter.
1170	* @param penmError Where to return details as to why the lookup
1171	* failed.
1172	*/
1173	static PKFSOBJ kFswCacheLookupDrive(PKFSCACHE pCache, char chLetter, KFSLOOKUPERROR *penmError)
1174	{
1175	KU32 const uHash = chLetter - 'A';
1176	KU32 cLeft;
1177	PKFSOBJ *ppCur;
1178
1179	MY_UNICODE_STRING NtPath;
1180	wchar_t wszTmp[8];
1181	MY_NTSTATUS rcNt;
1182	char szTmp[4];
1183
1184	/*
1185	* Custom drive letter hashing.
1186	*/
1187	if (pCache->RootDir.paHashTab)
1188	{
1189	/** @todo PKFSOBJHASH pHash = */
1190	}
1191
1192	/*
1193	* Special cased lookup.
1194	*/
1195	cLeft = pCache->RootDir.cChildren;
1196	ppCur = pCache->RootDir.papChildren;
1197	while (cLeft-- > 0)
1198	{
1199	PKFSOBJ pCur = *ppCur++;
1200	if ( pCur->cchName == 2
1201	&& pCur->pszName[0] == chLetter
1202	&& pCur->pszName[1] == ':')
1203	{
1204	if (pCur->bObjType == KFSOBJ_TYPE_DIR)
1205	return pCur;
1206	kHlpAssert(pCur->bObjType == KFSOBJ_TYPE_MISSING);
1207	if (kFsCacheRefreshMissingIntermediateDir(pCache, pCur, penmError))
1208	return pCur;
1209	return NULL;
1210	}
1211	}
1212
1213	/*
1214	* Need to add it. We always keep the drive letters open for the benefit
1215	* of kFsCachePopuplateOrRefreshDir and others.
1216	*/
1217	wszTmp[0] = szTmp[0] = chLetter;
1218	wszTmp[1] = szTmp[1] = ':';
1219	wszTmp[2] = szTmp[2] = '\\';
1220	wszTmp[3] = '.';
1221	wszTmp[4] = '\0';
1222	szTmp[2] = '\0';
1223
1224	NtPath.Buffer = NULL;
1225	NtPath.Length = 0;
1226	NtPath.MaximumLength = 0;
1227	if (g_pfnRtlDosPathNameToNtPathName_U(wszTmp, &NtPath, NULL, NULL))
1228	{
1229	HANDLE hDir;
1230	rcNt = birdOpenFileUniStr(&NtPath,
1231	FILE_READ_DATA \| FILE_LIST_DIRECTORY \| FILE_READ_ATTRIBUTES \| SYNCHRONIZE,
1232	FILE_ATTRIBUTE_NORMAL,
1233	FILE_SHARE_READ \| FILE_SHARE_WRITE \| FILE_SHARE_DELETE,
1234	FILE_OPEN,
1235	FILE_DIRECTORY_FILE \| FILE_OPEN_FOR_BACKUP_INTENT \| FILE_SYNCHRONOUS_IO_NONALERT,
1236	OBJ_CASE_INSENSITIVE,
1237	&hDir);
1238	birdFreeNtPath(&NtPath);
1239	if (MY_NT_SUCCESS(rcNt))
1240	{
1241	PKFSDIR pDir = (PKFSDIR)kFsCacheCreateObject(pCache, &pCache->RootDir, szTmp, 2, wszTmp, 2,
1242	#ifdef KFSCACHE_CFG_SHORT_NAMES
1243	NULL, 0, NULL, 0,
1244	#endif
1245	KFSOBJ_TYPE_DIR, penmError);
1246	if (pDir)
1247	{
1248	/*
1249	* We need a little bit of extra info for a drive root. These things are typically
1250	* inherited by subdirectories down the tree, so, we do it all here for till that changes.
1251	*/
1252	union
1253	{
1254	MY_FILE_FS_VOLUME_INFORMATION VolInfo;
1255	MY_FILE_FS_ATTRIBUTE_INFORMATION FsAttrInfo;
1256	char abPadding[sizeof(MY_FILE_FS_VOLUME_INFORMATION) + 512];
1257	} uBuf;
1258	MY_IO_STATUS_BLOCK Ios;
1259	KBOOL fRc;
1260
1261	kHlpAssert(pDir->hDir == INVALID_HANDLE_VALUE);
1262	pDir->hDir = hDir;
1263
1264	/* Get the device number. */
1265	rcNt = birdQueryVolumeDeviceNumber(hDir, &uBuf.VolInfo, sizeof(uBuf), &pDir->uDevNo);
1266	kHlpAssertMsg(MY_NT_SUCCESS(rcNt), ("%#x\n", rcNt));
1267
1268	/* Get the file system. */
1269	pDir->Obj.fFlags &= ~(KFSOBJ_F_NTFS \| KFSOBJ_F_WORKING_DIR_MTIME);
1270	Ios.Information = -1;
1271	Ios.u.Status = -1;
1272	rcNt = g_pfnNtQueryVolumeInformationFile(hDir, &Ios, &uBuf.FsAttrInfo, sizeof(uBuf),
1273	MyFileFsAttributeInformation);
1274	if (MY_NT_SUCCESS(rcNt))
1275	rcNt = Ios.u.Status;
1276	if (MY_NT_SUCCESS(rcNt))
1277	{
1278	if ( uBuf.FsAttrInfo.FileSystemName[0] == 'N'
1279	&& uBuf.FsAttrInfo.FileSystemName[1] == 'T'
1280	&& uBuf.FsAttrInfo.FileSystemName[2] == 'F'
1281	&& uBuf.FsAttrInfo.FileSystemName[3] == 'S'
1282	&& uBuf.FsAttrInfo.FileSystemName[4] == '\0')
1283	{
1284	DWORD dwDriveType = GetDriveTypeW(wszTmp);
1285	if ( dwDriveType == DRIVE_FIXED
1286	\|\| dwDriveType == DRIVE_RAMDISK)
1287	pDir->Obj.fFlags \|= KFSOBJ_F_NTFS \| KFSOBJ_F_WORKING_DIR_MTIME;
1288	}
1289	}
1290
1291	/*
1292	* Link the new drive letter into the root dir.
1293	*/
1294	fRc = kFsCacheDirAddChild(pCache, &pCache->RootDir, &pDir->Obj, penmError);
1295	kFsCacheObjRelease(pCache, &pDir->Obj);
1296	return fRc ? &pDir->Obj : NULL;
1297	}
1298
1299	g_pfnNtClose(hDir);
1300	return NULL;
1301	}
1302
1303	/* Assume it doesn't exist if this happens... This may be a little to
1304	restrictive wrt status code checks. */
1305	kHlpAssertMsgStmtReturn( rcNt == MY_STATUS_OBJECT_NAME_NOT_FOUND
1306	\|\| rcNt == MY_STATUS_OBJECT_PATH_NOT_FOUND
1307	\|\| rcNt == MY_STATUS_OBJECT_PATH_INVALID
1308	\|\| rcNt == MY_STATUS_OBJECT_PATH_SYNTAX_BAD,
1309	("%#x\n", rcNt),
1310	*penmError = KFSLOOKUPERROR_DIR_OPEN_ERROR,
1311	NULL);
1312	}
1313	else
1314	{
1315	kHlpAssertFailed();
1316	*penmError = KFSLOOKUPERROR_OUT_OF_MEMORY;
1317	return NULL;
1318	}
1319
1320	/*
1321	* Maybe create a missing entry.
1322	*/
1323	if (pCache->fFlags & KFSCACHE_F_MISSING_OBJECTS)
1324	{
1325	PKFSOBJ pMissing = kFsCacheCreateObject(pCache, &pCache->RootDir, szTmp, 2, wszTmp, 2,
1326	#ifdef KFSCACHE_CFG_SHORT_NAMES
1327	NULL, 0, NULL, 0,
1328	#endif
1329	KFSOBJ_TYPE_MISSING, penmError);
1330	if (pMissing)
1331	{
1332	KBOOL fRc = kFsCacheDirAddChild(pCache, &pCache->RootDir, pMissing, penmError);
1333	kFsCacheObjRelease(pCache, pMissing);
1334	return fRc ? pMissing : NULL;
1335	}
1336	}
1337	else
1338	{
1339	/** @todo this isn't necessary correct for a root spec. */
1340	*penmError = KFSLOOKUPERROR_PATH_COMP_NOT_FOUND;
1341	}
1342	return NULL;
1343	}
1344
1345
1346	/**
1347	* Look up a child node, ANSI version.
1348	*
1349	* @returns Pointer to the child if found, NULL if not.
1350	* @param pCache The cache.
1351	* @param pParent The parent directory to search.
1352	* @param pchName The child name to search for (not terminated).
1353	* @param cchName The length of the child name.
1354	*/
1355	static PKFSOBJ kFsCacheFindChildA(PKFSCACHE pCache, PKFSDIR pParent, const char *pchName, KU32 cchName)
1356	{
1357	/* Check for '.' first. */
1358	if (cchName != 1 \|\| *pchName != '.')
1359	{
1360	KU32 cLeft;
1361	PKFSOBJ *ppCur;
1362
1363	if (pParent->paHashTab != NULL)
1364	{
1365	/** @todo directory hash table lookup. */
1366	}
1367
1368	/* Linear search. */
1369	cLeft = pParent->cChildren;
1370	ppCur = pParent->papChildren;
1371	while (cLeft-- > 0)
1372	{
1373	PKFSOBJ pCur = *ppCur++;
1374	if ( ( pCur->cchName == cchName
1375	&& _mbsnicmp(pCur->pszName, pchName, cchName) == 0)
1376	#ifdef KFSCACHE_CFG_SHORT_NAMES
1377	\|\| ( pCur->cchShortName == cchName
1378	&& pCur->pszShortName != pCur->pszName
1379	&& _mbsnicmp(pCur->pszShortName, pchName, cchName) == 0)
1380	#endif
1381	)
1382	return pCur;
1383	}
1384	return NULL;
1385	}
1386	return &pParent->Obj;
1387	}
1388
1389
1390	/**
1391	* For use when kFsCacheIAreEqualW hit's something non-trivial.
1392	*
1393	* @returns K_TRUE if equal, K_FALSE if different.
1394	* @param pwcName1 The first string.
1395	* @param pwcName2 The second string.
1396	* @param cwcName The length of the two strings (in wchar_t's).
1397	*/
1398	KBOOL kFsCacheIAreEqualSlowW(const wchar_t pwcName1, const wchar_t pwcName2, KU16 cwcName)
1399	{
1400	MY_UNICODE_STRING UniStr1 = { cwcName * sizeof(wchar_t), cwcName * sizeof(wchar_t), (wchar_t *)pwcName1 };
1401	MY_UNICODE_STRING UniStr2 = { cwcName * sizeof(wchar_t), cwcName * sizeof(wchar_t), (wchar_t *)pwcName2 };
1402	return g_pfnRtlEqualUnicodeString(&UniStr1, &UniStr2, TRUE /fCaseInsensitive/);
1403	}
1404
1405
1406	/**
1407	* Compares two UTF-16 strings in a case-insensitive fashion.
1408	*
1409	* You would think we should be using _wscnicmp here instead, however it is
1410	* locale dependent and defaults to ASCII upper/lower handling setlocale hasn't
1411	* been called.
1412	*
1413	* @returns K_TRUE if equal, K_FALSE if different.
1414	* @param pwcName1 The first string.
1415	* @param pwcName2 The second string.
1416	* @param cwcName The length of the two strings (in wchar_t's).
1417	*/
1418	K_INLINE KBOOL kFsCacheIAreEqualW(const wchar_t pwcName1, const wchar_t pwcName2, KU32 cwcName)
1419	{
1420	while (cwcName > 0)
1421	{
1422	wchar_t wc1 = *pwcName1;
1423	wchar_t wc2 = *pwcName2;
1424	if (wc1 == wc2)
1425	{ /* not unlikely */ }
1426	else if ( (KU16)wc1 < (KU16)0xc0 /* U+00C0 is the first upper/lower letter after 'z'. */
1427	&& (KU16)wc2 < (KU16)0xc0)
1428	{
1429	/* ASCII upper case. */
1430	if ((KU16)wc1 - (KU16)0x61 < (KU16)26)
1431	wc1 &= ~(wchar_t)0x20;
1432	if ((KU16)wc2 - (KU16)0x61 < (KU16)26)
1433	wc2 &= ~(wchar_t)0x20;
1434	if (wc1 != wc2)
1435	return K_FALSE;
1436	}
1437	else
1438	return kFsCacheIAreEqualSlowW(pwcName1, pwcName2, (KU16)cwcName);
1439
1440	pwcName2++;
1441	pwcName1++;
1442	cwcName--;
1443	}
1444
1445	return K_TRUE;
1446	}
1447
1448
1449	/**
1450	* Look up a child node, UTF-16 version.
1451	*
1452	* @returns Pointer to the child if found, NULL if not.
1453	* @param pCache The cache.
1454	* @param pParent The parent directory to search.
1455	* @param pwcName The child name to search for (not terminated).
1456	* @param cwcName The length of the child name (in wchar_t's).
1457	*/
1458	static PKFSOBJ kFsCacheFindChildW(PKFSCACHE pCache, PKFSDIR pParent, const wchar_t *pwcName, KU32 cwcName)
1459	{
1460	/* Check for '.' first. */
1461	if (cwcName != 1 \|\| *pwcName != '.')
1462	{
1463	KU32 cLeft;
1464	PKFSOBJ *ppCur;
1465
1466	if (pParent->paHashTab != NULL)
1467	{
1468	/** @todo directory hash table lookup. */
1469	}
1470
1471	/* Linear search. */
1472	cLeft = pParent->cChildren;
1473	ppCur = pParent->papChildren;
1474	while (cLeft-- > 0)
1475	{
1476	PKFSOBJ pCur = *ppCur++;
1477	if ( ( pCur->cwcName == cwcName
1478	&& kFsCacheIAreEqualW(pCur->pwszName, pwcName, cwcName))
1479	#ifdef KFSCACHE_CFG_SHORT_NAMES
1480	\|\| ( pCur->cwcShortName == cwcName
1481	&& pCur->pwszShortName != pCur->pwszName
1482	&& kFsCacheIAreEqualW(pCur->pwszShortName, pwcName, cwcName))
1483	#endif
1484	)
1485	return pCur;
1486	}
1487	return NULL;
1488	}
1489	return &pParent->Obj;
1490	}
1491
1492
1493	/**
1494	* Looks up a UNC share, ANSI version.
1495	*
1496	* We keep both the server and share in the root directory entry. This means we
1497	* have to clean up the entry name before we can insert it.
1498	*
1499	* @returns Pointer to the share root directory or an update-to-date missing
1500	* node.
1501	* @param pCache The cache.
1502	* @param pszPath The path.
1503	* @param poff Where to return the root dire.
1504	* @param penmError Where to return details as to why the lookup
1505	* failed.
1506	*/
1507	static PKFSOBJ kFswCacheLookupUncShareA(PKFSCACHE pCache, const char pszPath, KU32 poff, KFSLOOKUPERROR *penmError)
1508	{
1509	#if 0 /* later */
1510	KU32 offStartServer;
1511	KU32 offEndServer;
1512	KU32 offStartShare;
1513
1514	KU32 offEnd = 2;
1515	while (IS_SLASH(pszPath[offEnd]))
1516	offEnd++;
1517
1518	offStartServer = offEnd;
1519	while ( (ch = pszPath[offEnd]) != '\0'
1520	&& !IS_SLASH(ch))
1521	offEnd++;
1522	offEndServer = offEnd;
1523
1524	if (ch != '\0')
1525	{ /* likely */ }
1526	else
1527	{
1528	*penmError = KFSLOOKUPERROR_NOT_FOUND;
1529	return NULL;
1530	}
1531
1532	while (IS_SLASH(pszPath[offEnd]))
1533	offEnd++;
1534	offStartServer = offEnd;
1535	while ( (ch = pszPath[offEnd]) != '\0'
1536	&& !IS_SLASH(ch))
1537	offEnd++;
1538	#endif
1539	*penmError = KFSLOOKUPERROR_UNSUPPORTED;
1540	return NULL;
1541	}
1542
1543
1544	/**
1545	* Looks up a UNC share, UTF-16 version.
1546	*
1547	* We keep both the server and share in the root directory entry. This means we
1548	* have to clean up the entry name before we can insert it.
1549	*
1550	* @returns Pointer to the share root directory or an update-to-date missing
1551	* node.
1552	* @param pCache The cache.
1553	* @param pwszPath The path.
1554	* @param poff Where to return the root dire.
1555	* @param penmError Where to return details as to why the lookup
1556	* failed.
1557	*/
1558	static PKFSOBJ kFswCacheLookupUncShareW(PKFSCACHE pCache, const wchar_t pwszPath, KU32 poff, KFSLOOKUPERROR *penmError)
1559	{
1560	#if 0 /* later */
1561	KU32 offStartServer;
1562	KU32 offEndServer;
1563	KU32 offStartShare;
1564
1565	KU32 offEnd = 2;
1566	while (IS_SLASH(pwszPath[offEnd]))
1567	offEnd++;
1568
1569	offStartServer = offEnd;
1570	while ( (ch = pwszPath[offEnd]) != '\0'
1571	&& !IS_SLASH(ch))
1572	offEnd++;
1573	offEndServer = offEnd;
1574
1575	if (ch != '\0')
1576	{ /* likely */ }
1577	else
1578	{
1579	*penmError = KFSLOOKUPERROR_NOT_FOUND;
1580	return NULL;
1581	}
1582
1583	while (IS_SLASH(pwszPath[offEnd]))
1584	offEnd++;
1585	offStartServer = offEnd;
1586	while ( (ch = pwszPath[offEnd]) != '\0'
1587	&& !IS_SLASH(ch))
1588	offEnd++;
1589	#endif
1590	*penmError = KFSLOOKUPERROR_UNSUPPORTED;
1591	return NULL;
1592	}
1593
1594
1595	/**
1596	* Walk the file system tree for the given absolute path, entering it into the
1597	* hash table.
1598	*
1599	* This will create any missing nodes while walking.
1600	*
1601	* The caller will have to do the path hash table insertion of the result.
1602	*
1603	* @returns Pointer to the tree node corresponding to @a pszPath.
1604	* NULL on lookup failure, see @a penmError for details.
1605	* @param pCache The cache.
1606	* @param pszPath The path to walk.
1607	* @param cchPath The length of the path.
1608	* @param penmError Where to return details as to why the lookup
1609	* failed.
1610	*/
1611	static PKFSOBJ kFsCacheLookupAbsoluteA(PKFSCACHE pCache, const char pszPath, KU32 cchPath, KFSLOOKUPERROR penmError)
1612	{
1613	PKFSDIR pParent = &pCache->RootDir;
1614	PKFSOBJ pChild;
1615	KU32 off;
1616	KU32 cchSlashes;
1617	KU32 offEnd;
1618
1619	KFSCACHE_LOG(("kFsCacheLookupAbsoluteA(%s)\n", pszPath));
1620
1621	/*
1622	* The root "directory" needs special handling, so we keep it outside the
1623	* main search loop. (Special: Cannot enumerate it, UNCs, ++.)
1624	*/
1625	cchSlashes = 0;
1626	off = 0;
1627	if ( pszPath[1] == ':'
1628	&& IS_ALPHA(pszPath[0]))
1629	{
1630	/* Drive letter. */
1631	offEnd = 2;
1632	kHlpAssert(IS_SLASH(pszPath[2]));
1633	pChild = kFswCacheLookupDrive(pCache, toupper(pszPath[0]), penmError);
1634	}
1635	else if ( IS_SLASH(pszPath[0])
1636	&& IS_SLASH(pszPath[1]) )
1637	pChild = kFswCacheLookupUncShareA(pCache, pszPath, &offEnd, penmError);
1638	else
1639	{
1640	*penmError = KFSLOOKUPERROR_UNSUPPORTED;
1641	return NULL;
1642	}
1643	if (pChild)
1644	{ /* likely */ }
1645	else
1646	return NULL;
1647
1648	/* Count slashes trailing the root spec. */
1649	if (offEnd < cchPath)
1650	{
1651	kHlpAssert(IS_SLASH(pszPath[offEnd]));
1652	do
1653	cchSlashes++;
1654	while (IS_SLASH(pszPath[offEnd + cchSlashes]));
1655	}
1656
1657	/* Done already? */
1658	if (offEnd >= cchPath)
1659	{
1660	if ( pChild->uCacheGen == KFSOBJ_CACHE_GEN_IGNORE
1661	\|\| pChild->uCacheGen == (pChild->bObjType != KFSOBJ_TYPE_MISSING ? pCache->uGeneration : pCache->uGenerationMissing)
1662	\|\| kFsCacheRefreshObj(pCache, pChild, penmError))
1663	return kFsCacheObjRetainInternal(pChild);
1664	return NULL;
1665	}
1666
1667	/* Check that we've got a valid result and not a cached negative one. */
1668	if (pChild->bObjType == KFSOBJ_TYPE_DIR)
1669	{ /* likely */ }
1670	else
1671	{
1672	kHlpAssert(pChild->bObjType == KFSOBJ_TYPE_MISSING);
1673	kHlpAssert(pChild->uCacheGen == KFSOBJ_CACHE_GEN_IGNORE \|\| pChild->uCacheGen == pCache->uGenerationMissing);
1674	return pChild;
1675	}
1676
1677	/* Next component. */
1678	pParent = (PKFSDIR)pChild;
1679	off = offEnd + cchSlashes;
1680
1681
1682	/*
1683	* Walk loop.
1684	*/
1685	for (;;)
1686	{
1687	/*
1688	* Find the end of the component, counting trailing slashes.
1689	*/
1690	char ch;
1691	cchSlashes = 0;
1692	offEnd = off + 1;
1693	while ((ch = pszPath[offEnd]) != '\0')
1694	{
1695	if (!IS_SLASH(ch))
1696	offEnd++;
1697	else
1698	{
1699	do
1700	cchSlashes++;
1701	while (IS_SLASH(pszPath[offEnd + cchSlashes]));
1702	break;
1703	}
1704	}
1705
1706	/*
1707	* Do we need to populate or refresh this directory first?
1708	*/
1709	if ( pParent->fPopulated
1710	&& ( pParent->Obj.uCacheGen == KFSOBJ_CACHE_GEN_IGNORE
1711	\|\| pParent->Obj.uCacheGen == pCache->uGeneration) )
1712	{ /* likely */ }
1713	else if (kFsCachePopuplateOrRefreshDir(pCache, pParent, penmError))
1714	{ /* likely */ }
1715	else
1716	return NULL;
1717
1718	/*
1719	* Search the current node for the name.
1720	*
1721	* If we don't find it, we may insert a missing node depending on
1722	* the cache configuration.
1723	*/
1724	pChild = kFsCacheFindChildA(pCache, pParent, &pszPath[off], offEnd - off);
1725	if (pChild != NULL)
1726	{ /* probably likely */ }
1727	else
1728	{
1729	if (pCache->fFlags & KFSCACHE_F_MISSING_OBJECTS)
1730	pChild = kFsCacheCreateMissingA(pCache, pParent, &pszPath[off], offEnd - off, penmError);
1731	if (cchSlashes == 0 \|\| offEnd + cchSlashes >= cchPath)
1732	{
1733	if (pChild)
1734	return pChild;
1735	*penmError = KFSLOOKUPERROR_NOT_FOUND;
1736	}
1737	else
1738	*penmError = KFSLOOKUPERROR_PATH_COMP_NOT_FOUND;
1739	return NULL;
1740	}
1741
1742	/* Advance off and check if we're done already. */
1743	off = offEnd + cchSlashes;
1744	if ( cchSlashes == 0
1745	\|\| off >= cchPath)
1746	{
1747	if ( pChild->bObjType != KFSOBJ_TYPE_MISSING
1748	\|\| pChild->uCacheGen == KFSOBJ_CACHE_GEN_IGNORE
1749	\|\| pChild->uCacheGen == pCache->uGenerationMissing
1750	\|\| kFsCacheRefreshMissing(pCache, pChild, penmError) )
1751	{ /* likely */ }
1752	else
1753	return NULL;
1754	return pChild;
1755	}
1756
1757	/*
1758	* Check that it's a directory. If a missing entry, we may have to
1759	* refresh it and re-examin it.
1760	*/
1761	if (pChild->bObjType == KFSOBJ_TYPE_DIR)
1762	pParent = (PKFSDIR)pChild;
1763	else if (pChild->bObjType != KFSOBJ_TYPE_MISSING)
1764	{
1765	*penmError = KFSLOOKUPERROR_PATH_COMP_NOT_DIR;
1766	return NULL;
1767	}
1768	else if ( pChild->uCacheGen == KFSOBJ_CACHE_GEN_IGNORE
1769	\|\| pChild->uCacheGen == pCache->uGenerationMissing)
1770	{
1771	*penmError = KFSLOOKUPERROR_PATH_COMP_NOT_FOUND;
1772	return NULL;
1773	}
1774	else if (kFsCacheRefreshMissingIntermediateDir(pCache, pChild, penmError))
1775	pParent = (PKFSDIR)pChild;
1776	else
1777	return NULL;
1778	}
1779
1780	return NULL;
1781	}
1782
1783
1784	/**
1785	* Walk the file system tree for the given absolute path, UTF-16 version.
1786	*
1787	* This will create any missing nodes while walking.
1788	*
1789	* The caller will have to do the path hash table insertion of the result.
1790	*
1791	* @returns Pointer to the tree node corresponding to @a pszPath.
1792	* NULL on lookup failure, see @a penmError for details.
1793	* @param pCache The cache.
1794	* @param pwszPath The path to walk.
1795	* @param cwcPath The length of the path (in wchar_t's).
1796	* @param penmError Where to return details as to why the lookup
1797	* failed.
1798	*/
1799	static PKFSOBJ kFsCacheLookupAbsoluteW(PKFSCACHE pCache, const wchar_t pwszPath, KU32 cwcPath, KFSLOOKUPERROR penmError)
1800	{
1801	PKFSDIR pParent = &pCache->RootDir;
1802	PKFSOBJ pChild;
1803	KU32 off;
1804	KU32 cwcSlashes;
1805	KU32 offEnd;
1806
1807	KFSCACHE_LOG(("kFsCacheLookupAbsoluteW(%ls)\n", pwszPath));
1808
1809	/*
1810	* The root "directory" needs special handling, so we keep it outside the
1811	* main search loop. (Special: Cannot enumerate it, UNCs, ++.)
1812	*/
1813	cwcSlashes = 0;
1814	off = 0;
1815	if ( pwszPath[1] == ':'
1816	&& IS_ALPHA(pwszPath[0]))
1817	{
1818	/* Drive letter. */
1819	offEnd = 2;
1820	kHlpAssert(IS_SLASH(pwszPath[2]));
1821	pChild = kFswCacheLookupDrive(pCache, toupper(pwszPath[0]), penmError);
1822	}
1823	else if ( IS_SLASH(pwszPath[0])
1824	&& IS_SLASH(pwszPath[1]) )
1825	pChild = kFswCacheLookupUncShareW(pCache, pwszPath, &offEnd, penmError);
1826	else
1827	{
1828	*penmError = KFSLOOKUPERROR_UNSUPPORTED;
1829	return NULL;
1830	}
1831	if (pChild)
1832	{ /* likely */ }
1833	else
1834	return NULL;
1835
1836	/* Count slashes trailing the root spec. */
1837	if (offEnd < cwcPath)
1838	{
1839	kHlpAssert(IS_SLASH(pwszPath[offEnd]));
1840	do
1841	cwcSlashes++;
1842	while (IS_SLASH(pwszPath[offEnd + cwcSlashes]));
1843	}
1844
1845	/* Done already? */
1846	if (offEnd >= cwcPath)
1847	{
1848	if ( pChild->uCacheGen == KFSOBJ_CACHE_GEN_IGNORE
1849	\|\| pChild->uCacheGen == (pChild->bObjType != KFSOBJ_TYPE_MISSING ? pCache->uGeneration : pCache->uGenerationMissing)
1850	\|\| kFsCacheRefreshObj(pCache, pChild, penmError))
1851	return kFsCacheObjRetainInternal(pChild);
1852	return NULL;
1853	}
1854
1855	/* Check that we've got a valid result and not a cached negative one. */
1856	if (pChild->bObjType == KFSOBJ_TYPE_DIR)
1857	{ /* likely */ }
1858	else
1859	{
1860	kHlpAssert(pChild->bObjType == KFSOBJ_TYPE_MISSING);
1861	kHlpAssert(pChild->uCacheGen == KFSOBJ_CACHE_GEN_IGNORE \|\| pChild->uCacheGen == pCache->uGenerationMissing);
1862	return pChild;
1863	}
1864
1865	/* Next component. */
1866	pParent = (PKFSDIR)pChild;
1867	off = offEnd + cwcSlashes;
1868
1869
1870	/*
1871	* Walk loop.
1872	*/
1873	for (;;)
1874	{
1875	/*
1876	* Find the end of the component, counting trailing slashes.
1877	*/
1878	wchar_t wc;
1879	cwcSlashes = 0;
1880	offEnd = off + 1;
1881	while ((wc = pwszPath[offEnd]) != '\0')
1882	{
1883	if (!IS_SLASH(wc))
1884	offEnd++;
1885	else
1886	{
1887	do
1888	cwcSlashes++;
1889	while (IS_SLASH(pwszPath[offEnd + cwcSlashes]));
1890	break;
1891	}
1892	}
1893
1894	/*
1895	* Do we need to populate or refresh this directory first?
1896	*/
1897	if ( pParent->fPopulated
1898	&& ( pParent->Obj.uCacheGen == KFSOBJ_CACHE_GEN_IGNORE
1899	\|\| pParent->Obj.uCacheGen == pCache->uGeneration) )
1900	{ /* likely */ }
1901	else if (kFsCachePopuplateOrRefreshDir(pCache, pParent, penmError))
1902	{ /* likely */ }
1903	else
1904	return NULL;
1905
1906	/*
1907	* Search the current node for the name.
1908	*
1909	* If we don't find it, we may insert a missing node depending on
1910	* the cache configuration.
1911	*/
1912	pChild = kFsCacheFindChildW(pCache, pParent, &pwszPath[off], offEnd - off);
1913	if (pChild != NULL)
1914	{ /* probably likely */ }
1915	else
1916	{
1917	if (pCache->fFlags & KFSCACHE_F_MISSING_OBJECTS)
1918	pChild = kFsCacheCreateMissingW(pCache, pParent, &pwszPath[off], offEnd - off, penmError);
1919	if (cwcSlashes == 0 \|\| offEnd + cwcSlashes >= cwcPath)
1920	{
1921	if (pChild)
1922	return pChild;
1923	*penmError = KFSLOOKUPERROR_NOT_FOUND;
1924	}
1925	else
1926	*penmError = KFSLOOKUPERROR_PATH_COMP_NOT_FOUND;
1927	return NULL;
1928	}
1929
1930	/* Advance off and check if we're done already. */
1931	off = offEnd + cwcSlashes;
1932	if ( cwcSlashes == 0
1933	\|\| off >= cwcPath)
1934	{
1935	if ( pChild->bObjType != KFSOBJ_TYPE_MISSING
1936	\|\| pChild->uCacheGen == KFSOBJ_CACHE_GEN_IGNORE
1937	\|\| pChild->uCacheGen == pCache->uGenerationMissing
1938	\|\| kFsCacheRefreshMissing(pCache, pChild, penmError) )
1939	{ /* likely */ }
1940	else
1941	return NULL;
1942	return pChild;
1943	}
1944
1945	/*
1946	* Check that it's a directory. If a missing entry, we may have to
1947	* refresh it and re-examin it.
1948	*/
1949	if (pChild->bObjType == KFSOBJ_TYPE_DIR)
1950	pParent = (PKFSDIR)pChild;
1951	else if (pChild->bObjType != KFSOBJ_TYPE_MISSING)
1952	{
1953	*penmError = KFSLOOKUPERROR_PATH_COMP_NOT_DIR;
1954	return NULL;
1955	}
1956	else if ( pChild->uCacheGen == KFSOBJ_CACHE_GEN_IGNORE
1957	\|\| pChild->uCacheGen == pCache->uGenerationMissing)
1958	{
1959	*penmError = KFSLOOKUPERROR_PATH_COMP_NOT_FOUND;
1960	return NULL;
1961	}
1962	else if (kFsCacheRefreshMissingIntermediateDir(pCache, pChild, penmError))
1963	pParent = (PKFSDIR)pChild;
1964	else
1965	return NULL;
1966	}
1967
1968	return NULL;
1969	}
1970
1971
1972	/**
1973	* This deals with paths that are relative and paths that contains '..'
1974	* elements, ANSI version.
1975	*
1976	* @returns Pointer to object corresponding to @a pszPath on success.
1977	* NULL if this isn't a path we care to cache.
1978	*
1979	* @param pCache The cache.
1980	* @param pszPath The path.
1981	* @param cchPath The length of the path.
1982	* @param penmError Where to return details as to why the lookup
1983	* failed.
1984	*/
1985	static PKFSOBJ kFsCacheLookupSlowA(PKFSCACHE pCache, const char pszPath, KU32 cchPath, KFSLOOKUPERROR penmError)
1986	{
1987	/*
1988	* We just call GetFullPathNameA here to do the job as getcwd and _getdcwd
1989	* ends up calling it anyway.
1990	*/
1991	char szFull[KFSCACHE_CFG_MAX_PATH];
1992	UINT cchFull = GetFullPathNameA(pszPath, sizeof(szFull), szFull, NULL);
1993	if ( cchFull >= 3
1994	&& cchFull < sizeof(szFull))
1995	{
1996	PKFSOBJ pFsObj;
1997	KFSCACHE_LOG(("kFsCacheLookupSlowA(%s)\n", pszPath));
1998	pFsObj = kFsCacheLookupAbsoluteA(pCache, szFull, cchFull, penmError);
1999
2000	#if 0 /* No need to do this until it's actually queried. */
2001	/* Cache the resulting path. */
2002	if ( pFsObj
2003	\|\| (pCache->fFlags & KFSCACHE_F_MISSING_PATHS)
2004	\|\| *penmError == KFSLOOKUPERROR_UNSUPPORTED)
2005	{
2006	KU32 uHashPath = kFsCacheStrHash(szFull);
2007	kFsCacheCreatePathHashTabEntryA(pCache, pFsObj, pszPath, cchPath, uHashPath,
2008	uHashPath % K_ELEMENTS(pCache->apAnsiPaths), *penmError);
2009	}
2010	#endif
2011	return pFsObj;
2012	}
2013
2014	/* The path is too long! */
2015	kHlpAssertMsgFailed(("'%s' -> cchFull=%u\n", pszPath, cchFull));
2016	*penmError = KFSLOOKUPERROR_PATH_TOO_LONG;
2017	return NULL;
2018	}
2019
2020
2021	/**
2022	* This deals with paths that are relative and paths that contains '..'
2023	* elements, UTF-16 version.
2024	*
2025	* @returns Pointer to object corresponding to @a pszPath on success.
2026	* NULL if this isn't a path we care to cache.
2027	*
2028	* @param pCache The cache.
2029	* @param pwszPath The path.
2030	* @param cwcPath The length of the path (in wchar_t's).
2031	* @param penmError Where to return details as to why the lookup
2032	* failed.
2033	*/
2034	static PKFSOBJ kFsCacheLookupSlowW(PKFSCACHE pCache, const wchar_t pwszPath, KU32 wcwPath, KFSLOOKUPERROR penmError)
2035	{
2036	/*
2037	* We just call GetFullPathNameA here to do the job as getcwd and _getdcwd
2038	* ends up calling it anyway.
2039	*/
2040	wchar_t wszFull[KFSCACHE_CFG_MAX_PATH];
2041	UINT cwcFull = GetFullPathNameW(pwszPath, KFSCACHE_CFG_MAX_PATH, wszFull, NULL);
2042	if ( cwcFull >= 3
2043	&& cwcFull < KFSCACHE_CFG_MAX_PATH)
2044	{
2045	PKFSOBJ pFsObj;
2046	KFSCACHE_LOG(("kFsCacheLookupSlowA(%ls)\n", pwszPath));
2047	pFsObj = kFsCacheLookupAbsoluteW(pCache, wszFull, cwcFull, penmError);
2048
2049	#if 0 /* No need to do this until it's actually queried. */
2050	/* Cache the resulting path. */
2051	if ( pFsObj
2052	\|\| (pCache->fFlags & KFSCACHE_F_MISSING_PATHS)
2053	\|\| *penmError == KFSLOOKUPERROR_UNSUPPORTED)
2054	{
2055	KU32 uHashPath = kFsCacheStrHash(szFull);
2056	kFsCacheCreatePathHashTabEntryA(pCache, pFsObj, pszPath, cchPath, uHashPath,
2057	uHashPath % K_ELEMENTS(pCache->apAnsiPaths), *penmError);
2058	}
2059	#endif
2060	return pFsObj;
2061	}
2062
2063	/* The path is too long! */
2064	kHlpAssertMsgFailed(("'%ls' -> cwcFull=%u\n", pwszPath, cwcFull));
2065	*penmError = KFSLOOKUPERROR_PATH_TOO_LONG;
2066	return NULL;
2067	}
2068
2069
2070	/**
2071	* Refreshes a path hash that has expired, ANSI version.
2072	*
2073	* @returns pHash on success, NULL if removed.
2074	* @param pCache The cache.
2075	* @param pHashEntry The path hash.
2076	* @param idxHashTab The hash table entry.
2077	*/
2078	static PKFSHASHA kFsCacheRefreshPathA(PKFSCACHE pCache, PKFSHASHA pHashEntry, KU32 idxHashTab)
2079	{
2080	/** @todo implement once we've start inserting uCacheGen nodes. */
2081	__debugbreak();
2082	K_NOREF(pCache);
2083	K_NOREF(idxHashTab);
2084	return pHashEntry;
2085	}
2086
2087
2088	/**
2089	* Refreshes a path hash that has expired, UTF-16 version.
2090	*
2091	* @returns pHash on success, NULL if removed.
2092	* @param pCache The cache.
2093	* @param pHashEntry The path hash.
2094	* @param idxHashTab The hash table entry.
2095	*/
2096	static PKFSHASHW kFsCacheRefreshPathW(PKFSCACHE pCache, PKFSHASHW pHashEntry, KU32 idxHashTab)
2097	{
2098	/** @todo implement once we've start inserting uCacheGen nodes. */
2099	__debugbreak();
2100	K_NOREF(pCache);
2101	K_NOREF(idxHashTab);
2102	return pHashEntry;
2103	}
2104
2105
2106	/**
2107	* Looks up a KFSOBJ for the given ANSI path.
2108	*
2109	* This will first try the hash table. If not in the hash table, the file
2110	* system cache tree is walked, missing bits filled in and finally a hash table
2111	* entry is created.
2112	*
2113	* Only drive letter paths are cachable. We don't do any UNC paths at this
2114	* point.
2115	*
2116	* @returns Reference to object corresponding to @a pszPath on success, this
2117	* must be released by kwFsCacheRelease.
2118	* NULL if not a path we care to cache.
2119	* @param pCache The cache.
2120	* @param pszPath The path to lookup.
2121	* @param penmError Where to return details as to why the lookup
2122	* failed.
2123	*/
2124	PKFSOBJ kFsCacheLookupA(PKFSCACHE pCache, const char pszPath, KFSLOOKUPERROR penmError)
2125	{
2126	/*
2127	* Do hash table lookup of the path.
2128	*/
2129	KU32 uHashPath;
2130	KU32 cchPath = (KU32)kFsCacheStrHashEx(pszPath, &uHashPath);
2131	KU32 idxHashTab = uHashPath % K_ELEMENTS(pCache->apAnsiPaths);
2132	PKFSHASHA pHashEntry = pCache->apAnsiPaths[idxHashTab];
2133	if (pHashEntry)
2134	{
2135	do
2136	{
2137	if ( pHashEntry->uHashPath == uHashPath
2138	&& pHashEntry->cchPath == cchPath
2139	&& kHlpMemComp(pHashEntry->pszPath, pszPath, cchPath) == 0)
2140	{
2141	if ( pHashEntry->uCacheGen == KFSOBJ_CACHE_GEN_IGNORE
2142	\|\| pHashEntry->uCacheGen == pCache->uGeneration
2143	\|\| (pHashEntry = kFsCacheRefreshPathA(pCache, pHashEntry, idxHashTab)) )
2144	{
2145	pCache->cLookups++;
2146	pCache->cPathHashHits++;
2147	KFSCACHE_LOG(("kFsCacheLookupA(%s) - hit %p\n", pszPath, pHashEntry->pFsObj));
2148	*penmError = pHashEntry->enmError;
2149	if (pHashEntry->pFsObj)
2150	return kFsCacheObjRetainInternal(pHashEntry->pFsObj);
2151	return NULL;
2152	}
2153	break;
2154	}
2155	pHashEntry = pHashEntry->pNext;
2156	} while (pHashEntry);
2157	}
2158
2159	/*
2160	* Create an entry for it by walking the file system cache and filling in the blanks.
2161	*/
2162	if ( cchPath > 0
2163	&& cchPath < KFSCACHE_CFG_MAX_PATH)
2164	{
2165	PKFSOBJ pFsObj;
2166
2167	/* Is absolute without any '..' bits? */
2168	if ( cchPath >= 3
2169	&& ( ( pszPath[1] == ':' /* Drive letter */
2170	&& IS_SLASH(pszPath[2])
2171	&& IS_ALPHA(pszPath[0]) )
2172	\|\| ( IS_SLASH(pszPath[0]) /* UNC */
2173	&& IS_SLASH(pszPath[1]) ) )
2174	&& !kFsCacheHasDotDotA(pszPath, cchPath) )
2175	pFsObj = kFsCacheLookupAbsoluteA(pCache, pszPath, cchPath, penmError);
2176	else
2177	pFsObj = kFsCacheLookupSlowA(pCache, pszPath, cchPath, penmError);
2178	if ( pFsObj
2179	\|\| ( (pCache->fFlags & KFSCACHE_F_MISSING_PATHS)
2180	&& *penmError != KFSLOOKUPERROR_PATH_TOO_LONG)
2181	\|\| *penmError == KFSLOOKUPERROR_UNSUPPORTED )
2182	kFsCacheCreatePathHashTabEntryA(pCache, pFsObj, pszPath, cchPath, uHashPath, idxHashTab, *penmError);
2183
2184	pCache->cLookups++;
2185	if (pFsObj)
2186	pCache->cWalkHits++;
2187	return pFsObj;
2188	}
2189
2190	*penmError = KFSLOOKUPERROR_PATH_TOO_LONG;
2191	return NULL;
2192	}
2193
2194
2195	/**
2196	* Looks up a KFSOBJ for the given UTF-16 path.
2197	*
2198	* This will first try the hash table. If not in the hash table, the file
2199	* system cache tree is walked, missing bits filled in and finally a hash table
2200	* entry is created.
2201	*
2202	* Only drive letter paths are cachable. We don't do any UNC paths at this
2203	* point.
2204	*
2205	* @returns Reference to object corresponding to @a pszPath on success, this
2206	* must be released by kwFsCacheRelease.
2207	* NULL if not a path we care to cache.
2208	* @param pCache The cache.
2209	* @param pwszPath The path to lookup.
2210	* @param penmError Where to return details as to why the lookup
2211	* failed.
2212	*/
2213	PKFSOBJ kFsCacheLookupW(PKFSCACHE pCache, const wchar_t pwszPath, KFSLOOKUPERROR penmError)
2214	{
2215	/*
2216	* Do hash table lookup of the path.
2217	*/
2218	KU32 uHashPath;
2219	KU32 cwcPath = (KU32)kFsCacheUtf16HashEx(pwszPath, &uHashPath);
2220	KU32 idxHashTab = uHashPath % K_ELEMENTS(pCache->apAnsiPaths);
2221	PKFSHASHW pHashEntry = pCache->apUtf16Paths[idxHashTab];
2222	if (pHashEntry)
2223	{
2224	do
2225	{
2226	if ( pHashEntry->uHashPath == uHashPath
2227	&& pHashEntry->cwcPath == cwcPath
2228	&& kHlpMemComp(pHashEntry->pwszPath, pwszPath, cwcPath) == 0)
2229	{
2230	if ( pHashEntry->uCacheGen == KFSOBJ_CACHE_GEN_IGNORE
2231	\|\| pHashEntry->uCacheGen == pCache->uGeneration
2232	\|\| (pHashEntry = kFsCacheRefreshPathW(pCache, pHashEntry, idxHashTab)) )
2233	{
2234	pCache->cLookups++;
2235	pCache->cPathHashHits++;
2236	KFSCACHE_LOG(("kFsCacheLookupW(%ls) - hit %p\n", pwszPath, pHashEntry->pFsObj));
2237	*penmError = pHashEntry->enmError;
2238	if (pHashEntry->pFsObj)
2239	return kFsCacheObjRetainInternal(pHashEntry->pFsObj);
2240	return NULL;
2241	}
2242	break;
2243	}
2244	pHashEntry = pHashEntry->pNext;
2245	} while (pHashEntry);
2246	}
2247
2248	/*
2249	* Create an entry for it by walking the file system cache and filling in the blanks.
2250	*/
2251	if ( cwcPath > 0
2252	&& cwcPath < KFSCACHE_CFG_MAX_PATH)
2253	{
2254	PKFSOBJ pFsObj;
2255
2256	/* Is absolute without any '..' bits? */
2257	if ( cwcPath >= 3
2258	&& ( ( pwszPath[1] == ':' /* Drive letter */
2259	&& IS_SLASH(pwszPath[2])
2260	&& IS_ALPHA(pwszPath[0]) )
2261	\|\| ( IS_SLASH(pwszPath[0]) /* UNC */
2262	&& IS_SLASH(pwszPath[1]) ) )
2263	&& !kFsCacheHasDotDotW(pwszPath, cwcPath) )
2264	pFsObj = kFsCacheLookupAbsoluteW(pCache, pwszPath, cwcPath, penmError);
2265	else
2266	pFsObj = kFsCacheLookupSlowW(pCache, pwszPath, cwcPath, penmError);
2267	if ( pFsObj
2268	\|\| ( (pCache->fFlags & KFSCACHE_F_MISSING_PATHS)
2269	&& *penmError != KFSLOOKUPERROR_PATH_TOO_LONG)
2270	\|\| *penmError == KFSLOOKUPERROR_UNSUPPORTED )
2271	kFsCacheCreatePathHashTabEntryW(pCache, pFsObj, pwszPath, cwcPath, uHashPath, idxHashTab, *penmError);
2272
2273	pCache->cLookups++;
2274	if (pFsObj)
2275	pCache->cWalkHits++;
2276	return pFsObj;
2277	}
2278
2279	*penmError = KFSLOOKUPERROR_PATH_TOO_LONG;
2280	return NULL;
2281	}
2282
2283
2284	/**
2285	* Destroys a cache object which has a zero reference count.
2286	*
2287	* @returns 0
2288	* @param pCache The cache.
2289	* @param pObj The object.
2290	*/
2291	KU32 kFsCacheObjDestroy(PKFSCACHE pCache, PKFSOBJ pObj)
2292	{
2293	kHlpAssert(pObj->cRefs == 0);
2294	kHlpAssert(pObj->pParent == NULL);
2295
2296	switch (pObj->bObjType)
2297	{
2298	case KFSOBJ_TYPE_MISSING:
2299	//case KFSOBJ_TYPE_MISSING \| KFSOBJ_TYPE_F_INVALID:
2300	/* nothing else to do here */
2301	pCache->cbObjects -= sizeof(*pObj);
2302	break;
2303
2304	case KFSOBJ_TYPE_DIR:
2305	//case KFSOBJ_TYPE_DIR \| KFSOBJ_TYPE_F_INVALID:
2306	case KFSOBJ_TYPE_FILE:
2307	//case KFSOBJ_TYPE_FILE \| KFSOBJ_TYPE_F_INVALID:
2308	kHlpAssertFailed();
2309	break;
2310	default:
2311	kHlpAssertFailed();
2312	}
2313	pCache->cObjects--;
2314	free(pObj);
2315	return 0;
2316	}
2317
2318
2319	/**
2320	* Releases a reference to a cache object.
2321	*
2322	* @returns New reference count.
2323	* @param pCache The cache.
2324	* @param pObj The object.
2325	*/
2326	KU32 kFsCacheObjRelease(PKFSCACHE pCache, PKFSOBJ pObj)
2327	{
2328	KU32 cRefs = --pObj->cRefs;
2329	if (cRefs)
2330	return cRefs;
2331	return kFsCacheObjDestroy(pCache, pObj);
2332	}
2333
2334
2335	/**
2336	* Retains a reference to a cahce object.
2337	*
2338	* @returns New reference count.
2339	* @param pObj The object.
2340	*/
2341	KU32 kFsCacheObjRetain(PKFSOBJ pObj)
2342	{
2343	KU32 cRefs = ++pObj->cRefs;
2344	kHlpAssert(cRefs < 16384);
2345	return cRefs;
2346	}
2347
2348
2349
2350	PKFSCACHE kFsCacheCreate(KU32 fFlags)
2351	{
2352	PKFSCACHE pCache;
2353	birdResolveImports();
2354
2355	pCache = (PKFSCACHE)kHlpAllocZ(sizeof(*pCache));
2356	if (pCache)
2357	{
2358	/* Dummy root dir entry. */
2359	pCache->RootDir.Obj.u32Magic = KFSOBJ_MAGIC;
2360	pCache->RootDir.Obj.cRefs = 1;
2361	pCache->RootDir.Obj.uCacheGen = KFSOBJ_CACHE_GEN_IGNORE;
2362	pCache->RootDir.Obj.bObjType = KFSOBJ_TYPE_DIR;
2363	pCache->RootDir.Obj.fHaveStats = K_FALSE;
2364	pCache->RootDir.Obj.pParent = NULL;
2365	pCache->RootDir.Obj.pszName = "";
2366	pCache->RootDir.Obj.cchName = 0;
2367	pCache->RootDir.Obj.cchParent = 0;
2368	#ifdef KFSCACHE_CFG_UTF16
2369	pCache->RootDir.Obj.cwcName = 0;
2370	pCache->RootDir.Obj.cwcParent = 0;
2371	pCache->RootDir.Obj.pwszName = L"";
2372	#endif
2373
2374	#ifdef KFSCACHE_CFG_SHORT_NAMES
2375	pCache->RootDir.Obj.pszShortName = NULL;
2376	pCache->RootDir.Obj.cchShortName = 0;
2377	pCache->RootDir.Obj.cchShortParent = 0;
2378	# ifdef KFSCACHE_CFG_UTF16
2379	pCache->RootDir.Obj.cwcShortName;
2380	pCache->RootDir.Obj.cwcShortParent;
2381	pCache->RootDir.Obj.pwszShortName;
2382	# endif
2383	#endif
2384	pCache->RootDir.cChildren = 0;
2385	pCache->RootDir.papChildren = NULL;
2386	pCache->RootDir.hDir = INVALID_HANDLE_VALUE;
2387	pCache->RootDir.cHashTab = 251;
2388	pCache->RootDir.paHashTab = (PKFSOBJHASH)kHlpAllocZ( pCache->RootDir.cHashTab
2389	* sizeof(pCache->RootDir.paHashTab[0]));
2390	if (pCache->RootDir.paHashTab)
2391	{
2392	/* The cache itself. */
2393	pCache->u32Magic = KFSCACHE_MAGIC;
2394	pCache->fFlags = fFlags;
2395	pCache->uGeneration = 1;
2396	pCache->cObjects = 1;
2397	pCache->cbObjects = sizeof(pCache->RootDir) + pCache->RootDir.cHashTab * sizeof(pCache->RootDir.paHashTab[0]);
2398	pCache->cPathHashHits = 0;
2399	pCache->cWalkHits = 0;
2400	pCache->cAnsiPaths = 0;
2401	pCache->cAnsiPathCollisions = 0;
2402	pCache->cbAnsiPaths = 0;
2403	#ifdef KFSCACHE_CFG_UTF16
2404	pCache->cUtf16Paths = 0;
2405	pCache->cUtf16PathCollisions = 0;
2406	pCache->cbUtf16Paths = 0;
2407	#endif
2408	return pCache;
2409	}
2410
2411	kHlpFree(pCache);
2412	}
2413	return NULL;
2414	}
2415

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

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

Download in other formats: