VirtualBox

source: kBuild/trunk/src/lib/nt/kFsCache.h@ 2912

Last change on this file since 2912 was 2912, checked in by bird, 9 years ago

rewrote kmk_redirect to skip the separate process. Added chache invalidation after directory deletion for addressing kmk rebuild and fetching.
  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 18.4 KB
Line 
1/* $Id: kFsCache.h 2912 2016-09-14 13:36:15Z bird $ */
2/** @file
3 * kFsCache.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#ifndef ___lib_nt_kFsCache_h___
32#define ___lib_nt_kFsCache_h___
33
34
35#include <k/kHlp.h>
36#include "ntstat.h"
37#ifndef NDEBUG
38# include <stdarg.h>
39#endif
40
41
42/** @def KFSCACHE_CFG_UTF16
43 * Whether to compile in the UTF-16 names support. */
44#define KFSCACHE_CFG_UTF16 1
45/** @def KFSCACHE_CFG_SHORT_NAMES
46 * Whether to compile in the short name support. */
47#define KFSCACHE_CFG_SHORT_NAMES 1
48/** @def KFSCACHE_CFG_PATH_HASH_TAB_SIZE
49 * Size of the path hash table. */
50#define KFSCACHE_CFG_PATH_HASH_TAB_SIZE 16381
51/** The max length paths we consider. */
52#define KFSCACHE_CFG_MAX_PATH 1024
53/** The max ANSI name length. */
54#define KFSCACHE_CFG_MAX_ANSI_NAME (256*3 + 16)
55/** The max UTF-16 name length. */
56#define KFSCACHE_CFG_MAX_UTF16_NAME (256*2 + 16)
57
58
59
60/** Special KFSOBJ::uCacheGen number indicating that it does not apply. */
61#define KFSOBJ_CACHE_GEN_IGNORE KU32_MAX
62
63
64/** @name KFSOBJ_TYPE_XXX - KFSOBJ::bObjType
65 * @{ */
66/** Directory, type KFSDIR. */
67#define KFSOBJ_TYPE_DIR KU8_C(0x01)
68/** Regular file - type KFSOBJ. */
69#define KFSOBJ_TYPE_FILE KU8_C(0x02)
70/** Other file - type KFSOBJ. */
71#define KFSOBJ_TYPE_OTHER KU8_C(0x03)
72/** Caching of a negative result - type KFSOBJ.
73 * @remarks We will allocate enough space for the largest cache node, so this
74 * can metamorph into any other object should it actually turn up. */
75#define KFSOBJ_TYPE_MISSING KU8_C(0x04)
76///** Invalidated entry flag. */
77//#define KFSOBJ_TYPE_F_INVALID KU8_C(0x20)
78/** @} */
79
80/** @name KFSOBJ_F_XXX - KFSOBJ::fFlags
81 * @{ */
82 /** Use custom generation.
83 * @remarks This is given the value 1, as we use it as an index into
84 * KFSCACHE::auGenerations, 0 being the default. */
85#define KFSOBJ_F_USE_CUSTOM_GEN KU32_C(0x00000001)
86
87/** Whether the file system update the modified timestamp of directories
88 * when something is removed from it or added to it.
89 * @remarks They say NTFS is the only windows filesystem doing this. */
90#define KFSOBJ_F_WORKING_DIR_MTIME KU32_C(0x00000002)
91/** NTFS file system volume. */
92#define KFSOBJ_F_NTFS KU32_C(0x80000000)
93/** Flags that are automatically inherited. */
94#define KFSOBJ_F_INHERITED_MASK KU32_C(0xffffffff)
95/** @} */
96
97
98#define IS_ALPHA(ch) ( ((ch) >= 'A' && (ch) <= 'Z') || ((ch) >= 'a' && (ch) <= 'z') )
99#define IS_SLASH(ch) ((ch) == '\\' || (ch) == '/')
100
101
102
103
104/** Pointer to a cache. */
105typedef struct KFSCACHE *PKFSCACHE;
106/** Pointer to a core object. */
107typedef struct KFSOBJ *PKFSOBJ;
108/** Pointer to a directory object. */
109typedef struct KFSDIR *PKFSDIR;
110/** Pointer to a directory hash table entry. */
111typedef struct KFSOBJHASH *PKFSOBJHASH;
112
113
114/**
115 * Directory hash table entry.
116 *
117 * There can be two of these per directory entry when the short name differs
118 * from the long name.
119 */
120typedef struct KFSOBJHASH
121{
122 /** Pointer to the next entry with the same hash. */
123 PKFSOBJHASH pNext;
124 /** Pointer to the object. */
125 PKFSOBJ pObj;
126} KFSOBJHASH;
127
128
129/** Pointer to a user data item. */
130typedef struct KFSUSERDATA *PKFSUSERDATA;
131/**
132 * User data item associated with a cache node.
133 */
134typedef struct KFSUSERDATA
135{
136 /** Pointer to the next piece of user data. */
137 PKFSUSERDATA pNext;
138 /** The key identifying this user. */
139 KUPTR uKey;
140 /** The destructor. */
141 void (*pfnDestructor)(PKFSCACHE pCache, PKFSOBJ pObj, PKFSUSERDATA pData);
142} KFSUSERDATA;
143
144
145/**
146 * Base cache node.
147 */
148typedef struct KFSOBJ
149{
150 /** Magic value (KFSOBJ_MAGIC). */
151 KU32 u32Magic;
152 /** Number of references. */
153 KU32 volatile cRefs;
154 /** The cache generation, see KFSOBJ_CACHE_GEN_IGNORE. */
155 KU32 uCacheGen;
156 /** The object type, KFSOBJ_TYPE_XXX. */
157 KU8 bObjType;
158 /** Set if the Stats member is valid, clear if not. */
159 KBOOL fHaveStats;
160 /** Unused flags. */
161 KBOOL abUnused[2];
162 /** Flags, KFSOBJ_F_XXX. */
163 KU32 fFlags;
164
165 /** Pointer to the parent (directory).
166 * This is only NULL for a root. */
167 PKFSDIR pParent;
168
169 /** The directory name. (Allocated after the structure.) */
170 const char *pszName;
171 /** The length of pszName. */
172 KU16 cchName;
173 /** The length of the parent path (up to where pszName starts).
174 * @note This is valuable when constructing an absolute path to this node by
175 * means of the parent pointer (no need for recursion). */
176 KU16 cchParent;
177#ifdef KFSCACHE_CFG_UTF16
178 /** The length of pwszName (in wchar_t's). */
179 KU16 cwcName;
180 /** The length of the parent UTF-16 path (in wchar_t's).
181 * @note This is valuable when constructing an absolute path to this node by
182 * means of the parent pointer (no need for recursion). */
183 KU16 cwcParent;
184 /** The UTF-16 object name. (Allocated after the structure.) */
185 const wchar_t *pwszName;
186#endif
187
188#ifdef KFSCACHE_CFG_SHORT_NAMES
189 /** The short object name. (Allocated after the structure, could be same
190 * as pszName.) */
191 const char *pszShortName;
192 /** The length of pszShortName. */
193 KU16 cchShortName;
194 /** The length of the short parent path (up to where pszShortName starts). */
195 KU16 cchShortParent;
196# ifdef KFSCACHE_CFG_UTF16
197 /** The length of pwszShortName (in wchar_t's). */
198 KU16 cwcShortName;
199 /** The length of the short parent UTF-16 path (in wchar_t's). */
200 KU16 cwcShortParent;
201 /** The UTF-16 short object name. (Allocated after the structure, possibly
202 * same as pwszName.) */
203 const wchar_t *pwszShortName;
204# endif
205#endif
206
207 /** Pointer to the first user data item */
208 PKFSUSERDATA pUserDataHead;
209
210 /** Stats - only valid when fHaveStats is set. */
211 BirdStat_T Stats;
212} KFSOBJ;
213
214/** The magic for a KFSOBJ structure (Thelonious Sphere Monk). */
215#define KFSOBJ_MAGIC KU32_C(0x19171010)
216
217
218/**
219 * Directory node in the cache.
220 */
221typedef struct KFSDIR
222{
223 /** The core object information. */
224 KFSOBJ Obj;
225
226 /** Child objects. */
227 PKFSOBJ *papChildren;
228 /** The number of child objects. */
229 KU32 cChildren;
230 /** The allocated size of papChildren. */
231 KU32 cChildrenAllocated;
232
233 /** Pointer to the hash table.
234 * @todo this isn't quite there yet, structure wise. sigh. */
235 PKFSOBJHASH paHashTab;
236 /** The size of the hash table.
237 * @remarks The hash table is optional and only used when there are a lot of
238 * entries in the directory. */
239 KU32 cHashTab;
240
241 /** Handle to the directory (we generally keep it open). */
242#ifndef DECLARE_HANDLE
243 KUPTR hDir;
244#else
245 HANDLE hDir;
246#endif
247 /** The device number we queried/inherited when opening it. */
248 KU64 uDevNo;
249
250 /** The last write time sampled the last time the directory was refreshed.
251 * @remarks May differ from st_mtim because it will be updated when the
252 * parent directory is refreshed. */
253 KI64 iLastWrite;
254
255 /** Set if populated. */
256 KBOOL fPopulated;
257 /** Set if it needs re-populated. */
258 KBOOL fNeedRePopulating;
259} KFSDIR;
260
261
262/**
263 * Lookup errors.
264 */
265typedef enum KFSLOOKUPERROR
266{
267 /** Lookup was a success. */
268 KFSLOOKUPERROR_SUCCESS = 0,
269 /** A path component was not found. */
270 KFSLOOKUPERROR_PATH_COMP_NOT_FOUND,
271 /** A path component is not a directory. */
272 KFSLOOKUPERROR_PATH_COMP_NOT_DIR,
273 /** The final path entry is not a directory (trailing slash). */
274 KFSLOOKUPERROR_NOT_DIR,
275 /** Not found. */
276 KFSLOOKUPERROR_NOT_FOUND,
277 /** The path is too long. */
278 KFSLOOKUPERROR_PATH_TOO_LONG,
279 /** Unsupported path type. */
280 KFSLOOKUPERROR_UNSUPPORTED,
281 /** We're out of memory. */
282 KFSLOOKUPERROR_OUT_OF_MEMORY,
283
284 /** Error opening directory. */
285 KFSLOOKUPERROR_DIR_OPEN_ERROR,
286 /** Error reading directory. */
287 KFSLOOKUPERROR_DIR_READ_ERROR,
288 /** UTF-16 to ANSI conversion error. */
289 KFSLOOKUPERROR_ANSI_CONVERSION_ERROR,
290 /** ANSI to UTF-16 conversion error. */
291 KFSLOOKUPERROR_UTF16_CONVERSION_ERROR,
292 /** Internal error. */
293 KFSLOOKUPERROR_INTERNAL_ERROR
294} KFSLOOKUPERROR;
295
296
297/** Pointer to an ANSI path hash table entry. */
298typedef struct KFSHASHA *PKFSHASHA;
299/**
300 * ANSI file system path hash table entry.
301 * The path hash table allows us to skip parsing and walking a path.
302 */
303typedef struct KFSHASHA
304{
305 /** Next entry with the same hash table slot. */
306 PKFSHASHA pNext;
307 /** Path hash value. */
308 KU32 uHashPath;
309 /** The path length. */
310 KU16 cchPath;
311 /** Set if aboslute path. */
312 KBOOL fAbsolute;
313 /** Index into KFSCACHE:auGenerationsMissing when pFsObj is NULL. */
314 KU8 idxMissingGen;
315 /** The cache generation ID. */
316 KU32 uCacheGen;
317 /** The lookup error (when pFsObj is NULL). */
318 KFSLOOKUPERROR enmError;
319 /** The path. (Allocated after the structure.) */
320 const char *pszPath;
321 /** Pointer to the matching FS object.
322 * This is NULL for negative path entries? */
323 PKFSOBJ pFsObj;
324} KFSHASHA;
325
326
327#ifdef KFSCACHE_CFG_UTF16
328/** Pointer to an UTF-16 path hash table entry. */
329typedef struct KFSHASHW *PKFSHASHW;
330/**
331 * UTF-16 file system path hash table entry. The path hash table allows us
332 * to skip parsing and walking a path.
333 */
334typedef struct KFSHASHW
335{
336 /** Next entry with the same hash table slot. */
337 PKFSHASHW pNext;
338 /** Path hash value. */
339 KU32 uHashPath;
340 /** The path length (in wchar_t units). */
341 KU16 cwcPath;
342 /** Set if aboslute path. */
343 KBOOL fAbsolute;
344 /** Index into KFSCACHE:auGenerationsMissing when pFsObj is NULL. */
345 KU8 idxMissingGen;
346 /** The cache generation ID. */
347 KU32 uCacheGen;
348 /** The lookup error (when pFsObj is NULL). */
349 KFSLOOKUPERROR enmError;
350 /** The path. (Allocated after the structure.) */
351 const wchar_t *pwszPath;
352 /** Pointer to the matching FS object.
353 * This is NULL for negative path entries? */
354 PKFSOBJ pFsObj;
355} KFSHASHW;
356#endif
357
358
359/** @name KFSCACHE_F_XXX
360 * @{ */
361/** Whether to cache missing directory entries (KFSOBJ_TYPE_MISSING). */
362#define KFSCACHE_F_MISSING_OBJECTS KU32_C(0x00000001)
363/** Whether to cache missing paths. */
364#define KFSCACHE_F_MISSING_PATHS KU32_C(0x00000002)
365/** @} */
366
367
368/**
369 * Directory cache instance.
370 */
371typedef struct KFSCACHE
372{
373 /** Magic value (KFSCACHE_MAGIC). */
374 KU32 u32Magic;
375 /** Cache flags. */
376 KU32 fFlags;
377
378 /** The default and custom cache generations for stuff that exists, indexed by
379 * KFSOBJ_F_USE_CUSTOM_GEN.
380 *
381 * The custom generation can be used to invalidate parts of the file system that
382 * are known to be volatile without triggering refreshing of the more static
383 * parts. Like the 'out' directory in a kBuild setup or a 'TEMP' directory are
384 * expected to change and you need to invalidate the caching of these frequently
385 * to stay on top of things. Whereas the sources, headers, compilers, sdk,
386 * ddks, windows directory and such generally doesn't change all that often.
387 */
388 KU32 auGenerations[2];
389 /** The current cache generation for missing objects, negative results, ++.
390 * This comes with a custom variant too. Indexed by KFSOBJ_F_USE_CUSTOM_GEN. */
391 KU32 auGenerationsMissing[2];
392
393 /** Number of cache objects. */
394 KSIZE cObjects;
395 /** Memory occupied by the cache object structures. */
396 KSIZE cbObjects;
397 /** Number of lookups. */
398 KSIZE cLookups;
399 /** Number of hits in the path hash tables. */
400 KSIZE cPathHashHits;
401 /** Number of hits walking the file system hierarchy. */
402 KSIZE cWalkHits;
403
404 /** The root directory. */
405 KFSDIR RootDir;
406
407 /** File system hash table for ANSI filename strings. */
408 PKFSHASHA apAnsiPaths[KFSCACHE_CFG_PATH_HASH_TAB_SIZE];
409 /** Number of paths in the apAnsiPaths hash table. */
410 KSIZE cAnsiPaths;
411 /** Number of collisions in the apAnsiPaths hash table. */
412 KSIZE cAnsiPathCollisions;
413 /** Amount of memory used by the path entries. */
414 KSIZE cbAnsiPaths;
415
416#ifdef KFSCACHE_CFG_UTF16
417 /** Number of paths in the apUtf16Paths hash table. */
418 KSIZE cUtf16Paths;
419 /** Number of collisions in the apUtf16Paths hash table. */
420 KSIZE cUtf16PathCollisions;
421 /** Amount of memory used by the UTF-16 path entries. */
422 KSIZE cbUtf16Paths;
423 /** File system hash table for UTF-16 filename strings. */
424 PKFSHASHW apUtf16Paths[KFSCACHE_CFG_PATH_HASH_TAB_SIZE];
425#endif
426} KFSCACHE;
427
428/** Magic value for KFSCACHE::u32Magic (Jon Batiste). */
429#define KFSCACHE_MAGIC KU32_C(0x19861111)
430
431
432/** @def KW_LOG
433 * Generic logging.
434 * @param a Argument list for kFsCacheDbgPrintf */
435#ifdef NDEBUG
436# define KFSCACHE_LOG(a) do { } while (0)
437#else
438# define KFSCACHE_LOG(a) kFsCacheDbgPrintf a
439void kFsCacheDbgPrintfV(const char *pszFormat, va_list va);
440void kFsCacheDbgPrintf(const char *pszFormat, ...);
441#endif
442
443
444KBOOL kFsCacheDirEnsurePopuplated(PKFSCACHE pCache, PKFSDIR pDir, KFSLOOKUPERROR *penmError);
445KBOOL kFsCacheDirAddChild(PKFSCACHE pCache, PKFSDIR pParent, PKFSOBJ pChild, KFSLOOKUPERROR *penmError);
446PKFSOBJ kFsCacheCreateObject(PKFSCACHE pCache, PKFSDIR pParent,
447 char const *pszName, KU16 cchName, wchar_t const *pwszName, KU16 cwcName,
448#ifdef KFSCACHE_CFG_SHORT_NAMES
449 char const *pszShortName, KU16 cchShortName, wchar_t const *pwszShortName, KU16 cwcShortName,
450#endif
451 KU8 bObjType, KFSLOOKUPERROR *penmError);
452PKFSOBJ kFsCacheCreateObjectW(PKFSCACHE pCache, PKFSDIR pParent, wchar_t const *pwszName, KU32 cwcName,
453#ifdef KFSCACHE_CFG_SHORT_NAMES
454 wchar_t const *pwszShortName, KU32 cwcShortName,
455#endif
456 KU8 bObjType, KFSLOOKUPERROR *penmError);
457PKFSOBJ kFsCacheLookupA(PKFSCACHE pCache, const char *pszPath, KFSLOOKUPERROR *penmError);
458PKFSOBJ kFsCacheLookupW(PKFSCACHE pCache, const wchar_t *pwszPath, KFSLOOKUPERROR *penmError);
459PKFSOBJ kFsCacheLookupRelativeToDirA(PKFSCACHE pCache, PKFSDIR pParent, const char *pszPath, KU32 cchPath, KU32 fFlags,
460 KFSLOOKUPERROR *penmError, PKFSOBJ *ppLastAncestor);
461PKFSOBJ kFsCacheLookupRelativeToDirW(PKFSCACHE pCache, PKFSDIR pParent, const wchar_t *pwszPath, KU32 cwcPath, KU32 fFlags,
462 KFSLOOKUPERROR *penmError, PKFSOBJ *ppLastAncestor);
463PKFSOBJ kFsCacheLookupWithLengthA(PKFSCACHE pCache, const char *pchPath, KSIZE cchPath, KFSLOOKUPERROR *penmError);
464PKFSOBJ kFsCacheLookupWithLengthW(PKFSCACHE pCache, const wchar_t *pwcPath, KSIZE cwcPath, KFSLOOKUPERROR *penmError);
465PKFSOBJ kFsCacheLookupNoMissingA(PKFSCACHE pCache, const char *pszPath, KFSLOOKUPERROR *penmError);
466PKFSOBJ kFsCacheLookupNoMissingW(PKFSCACHE pCache, const wchar_t *pwszPath, KFSLOOKUPERROR *penmError);
467
468/** @name KFSCACHE_LOOKUP_F_XXX - lookup flags
469 * @{ */
470/** No inserting new cache entries.
471 * This effectively prevent directories from being repopulated too. */
472#define KFSCACHE_LOOKUP_F_NO_INSERT KU32_C(1)
473/** No refreshing cache entries. */
474#define KFSCACHE_LOOKUP_F_NO_REFRESH KU32_C(2)
475/** @} */
476
477KU32 kFsCacheObjRelease(PKFSCACHE pCache, PKFSOBJ pObj);
478KU32 kFsCacheObjRetain(PKFSOBJ pObj);
479PKFSUSERDATA kFsCacheObjAddUserData(PKFSCACHE pCache, PKFSOBJ pObj, KUPTR uKey, KSIZE cbUserData);
480PKFSUSERDATA kFsCacheObjGetUserData(PKFSCACHE pCache, PKFSOBJ pObj, KUPTR uKey);
481KBOOL kFsCacheObjGetFullPathA(PKFSOBJ pObj, char *pszPath, KSIZE cbPath, char chSlash);
482KBOOL kFsCacheObjGetFullPathW(PKFSOBJ pObj, wchar_t *pwszPath, KSIZE cwcPath, wchar_t wcSlash);
483KBOOL kFsCacheObjGetFullShortPathA(PKFSOBJ pObj, char *pszPath, KSIZE cbPath, char chSlash);
484KBOOL kFsCacheObjGetFullShortPathW(PKFSOBJ pObj, wchar_t *pwszPath, KSIZE cwcPath, wchar_t wcSlash);
485
486KBOOL kFsCacheFileSimpleOpenReadClose(PKFSCACHE pCache, PKFSOBJ pFileObj, KU64 offStart, void *pvBuf, KSIZE cbToRead);
487
488PKFSCACHE kFsCacheCreate(KU32 fFlags);
489void kFsCacheDestroy(PKFSCACHE);
490void kFsCacheInvalidateMissing(PKFSCACHE pCache);
491void kFsCacheInvalidateAll(PKFSCACHE pCache);
492void kFsCacheInvalidateCustomMissing(PKFSCACHE pCache);
493void kFsCacheInvalidateCustomBoth(PKFSCACHE pCache);
494KBOOL kFsCacheSetupCustomRevisionForTree(PKFSCACHE pCache, PKFSOBJ pRoot);
495KBOOL kFsCacheInvalidateDeletedDirectoryA(PKFSCACHE pCache, const char *pszDir);
496
497#endif
Note: See TracBrowser for help on using the repository browser.

© 2025 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette