VirtualBox

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

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

kFsCache: Finally tracked down the heap corruption bug in the directory refreshing code. Added kFsCacheObjReleaseTagged for debugging.

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 19.7 KB
Line 
1/* $Id: kFsCache.h 2945 2016-09-20 01:46:23Z 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 99991
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/** Pointer to a user data item. */
116typedef struct KFSUSERDATA *PKFSUSERDATA;
117/**
118 * User data item associated with a cache node.
119 */
120typedef struct KFSUSERDATA
121{
122 /** Pointer to the next piece of user data. */
123 PKFSUSERDATA pNext;
124 /** The key identifying this user. */
125 KUPTR uKey;
126 /** The destructor. */
127 void (*pfnDestructor)(PKFSCACHE pCache, PKFSOBJ pObj, PKFSUSERDATA pData);
128} KFSUSERDATA;
129
130
131/**
132 * Base cache node.
133 */
134typedef struct KFSOBJ
135{
136 /** Magic value (KFSOBJ_MAGIC). */
137 KU32 u32Magic;
138 /** Number of references. */
139 KU32 volatile cRefs;
140 /** The cache generation, see KFSOBJ_CACHE_GEN_IGNORE. */
141 KU32 uCacheGen;
142 /** The object type, KFSOBJ_TYPE_XXX. */
143 KU8 bObjType;
144 /** Set if the Stats member is valid, clear if not. */
145 KBOOL fHaveStats;
146 /** Unused flags. */
147 KBOOL abUnused[2];
148 /** Flags, KFSOBJ_F_XXX. */
149 KU32 fFlags;
150
151 /** Hash value of the name inserted into the parent hash table.
152 * This is 0 if not inserted. Names are only hashed and inserted as they are
153 * first found thru linear searching of its siblings, and which name it is
154 * dependens on the lookup function (W or A) and whether the normal name or
155 * short name seems to have matched.
156 *
157 * @note It was ruled out as too much work to hash and track all four names,
158 * so instead this minimalist approach was choosen in stead. */
159 KU32 uNameHash;
160 /** Pointer to the next child with the same name hash value. */
161 PKFSOBJ pNextNameHash;
162 /** Pointer to the parent (directory).
163 * This is only NULL for a root. */
164 PKFSDIR pParent;
165
166 /** The directory name. (Allocated after the structure.) */
167 const char *pszName;
168 /** The length of pszName. */
169 KU16 cchName;
170 /** The length of the parent path (up to where pszName starts).
171 * @note This is valuable when constructing an absolute path to this node by
172 * means of the parent pointer (no need for recursion). */
173 KU16 cchParent;
174#ifdef KFSCACHE_CFG_UTF16
175 /** The length of pwszName (in wchar_t's). */
176 KU16 cwcName;
177 /** The length of the parent UTF-16 path (in wchar_t's).
178 * @note This is valuable when constructing an absolute path to this node by
179 * means of the parent pointer (no need for recursion). */
180 KU16 cwcParent;
181 /** The UTF-16 object name. (Allocated after the structure.) */
182 const wchar_t *pwszName;
183#endif
184
185#ifdef KFSCACHE_CFG_SHORT_NAMES
186 /** The short object name. (Allocated after the structure, could be same
187 * as pszName.) */
188 const char *pszShortName;
189 /** The length of pszShortName. */
190 KU16 cchShortName;
191 /** The length of the short parent path (up to where pszShortName starts). */
192 KU16 cchShortParent;
193# ifdef KFSCACHE_CFG_UTF16
194 /** The length of pwszShortName (in wchar_t's). */
195 KU16 cwcShortName;
196 /** The length of the short parent UTF-16 path (in wchar_t's). */
197 KU16 cwcShortParent;
198 /** The UTF-16 short object name. (Allocated after the structure, possibly
199 * same as pwszName.) */
200 const wchar_t *pwszShortName;
201# endif
202#endif
203
204 /** Pointer to the first user data item */
205 PKFSUSERDATA pUserDataHead;
206
207 /** Stats - only valid when fHaveStats is set. */
208 BirdStat_T Stats;
209} KFSOBJ;
210
211/** The magic for a KFSOBJ structure (Thelonious Sphere Monk). */
212#define KFSOBJ_MAGIC KU32_C(0x19171010)
213
214
215/**
216 * Directory node in the cache.
217 */
218typedef struct KFSDIR
219{
220 /** The core object information. */
221 KFSOBJ Obj;
222
223 /** Child objects. */
224 PKFSOBJ *papChildren;
225 /** The number of child objects. */
226 KU32 cChildren;
227 /** The allocated size of papChildren. */
228 KU32 cChildrenAllocated;
229
230 /** Pointer to the child hash table. */
231 PKFSOBJ *papHashTab;
232 /** The mask shift of the hash table.
233 * Hash table size is a power of two, this is the size minus one.
234 *
235 * @remarks The hash table is optional and populated by lookup hits. The
236 * assumption being that a lookup is repeated and will choose a good
237 * name to hash on. We've got up to 4 different hashes, so this
238 * was the easy way out. */
239 KU32 fHashTabMask;
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 /** Number of child searches. */
404 KSIZE cChildSearches;
405 /** Number of cChildLookups resolved thru hash table hits. */
406 KSIZE cChildHashHits;
407 /** The number of child hash tables. */
408 KSIZE cChildHashTabs;
409 /** The sum of all child hash table sizes. */
410 KSIZE cChildHashEntriesTotal;
411 /** Number of children inserted into the hash tables. */
412 KSIZE cChildHashed;
413 /** Number of collisions in the child hash tables */
414 KSIZE cChildHashCollisions;
415
416 /** The root directory. */
417 KFSDIR RootDir;
418
419 /** File system hash table for ANSI filename strings. */
420 PKFSHASHA apAnsiPaths[KFSCACHE_CFG_PATH_HASH_TAB_SIZE];
421 /** Number of paths in the apAnsiPaths hash table. */
422 KSIZE cAnsiPaths;
423 /** Number of collisions in the apAnsiPaths hash table. */
424 KSIZE cAnsiPathCollisions;
425 /** Amount of memory used by the path entries. */
426 KSIZE cbAnsiPaths;
427
428#ifdef KFSCACHE_CFG_UTF16
429 /** Number of paths in the apUtf16Paths hash table. */
430 KSIZE cUtf16Paths;
431 /** Number of collisions in the apUtf16Paths hash table. */
432 KSIZE cUtf16PathCollisions;
433 /** Amount of memory used by the UTF-16 path entries. */
434 KSIZE cbUtf16Paths;
435 /** File system hash table for UTF-16 filename strings. */
436 PKFSHASHW apUtf16Paths[KFSCACHE_CFG_PATH_HASH_TAB_SIZE];
437#endif
438} KFSCACHE;
439
440/** Magic value for KFSCACHE::u32Magic (Jon Batiste). */
441#define KFSCACHE_MAGIC KU32_C(0x19861111)
442
443
444/** @def KW_LOG
445 * Generic logging.
446 * @param a Argument list for kFsCacheDbgPrintf */
447#ifdef NDEBUG
448# define KFSCACHE_LOG(a) do { } while (0)
449#else
450# define KFSCACHE_LOG(a) kFsCacheDbgPrintf a
451void kFsCacheDbgPrintfV(const char *pszFormat, va_list va);
452void kFsCacheDbgPrintf(const char *pszFormat, ...);
453#endif
454
455
456KBOOL kFsCacheDirEnsurePopuplated(PKFSCACHE pCache, PKFSDIR pDir, KFSLOOKUPERROR *penmError);
457KBOOL kFsCacheDirAddChild(PKFSCACHE pCache, PKFSDIR pParent, PKFSOBJ pChild, KFSLOOKUPERROR *penmError);
458PKFSOBJ kFsCacheCreateObject(PKFSCACHE pCache, PKFSDIR pParent,
459 char const *pszName, KU16 cchName, wchar_t const *pwszName, KU16 cwcName,
460#ifdef KFSCACHE_CFG_SHORT_NAMES
461 char const *pszShortName, KU16 cchShortName, wchar_t const *pwszShortName, KU16 cwcShortName,
462#endif
463 KU8 bObjType, KFSLOOKUPERROR *penmError);
464PKFSOBJ kFsCacheCreateObjectW(PKFSCACHE pCache, PKFSDIR pParent, wchar_t const *pwszName, KU32 cwcName,
465#ifdef KFSCACHE_CFG_SHORT_NAMES
466 wchar_t const *pwszShortName, KU32 cwcShortName,
467#endif
468 KU8 bObjType, KFSLOOKUPERROR *penmError);
469PKFSOBJ kFsCacheLookupA(PKFSCACHE pCache, const char *pszPath, KFSLOOKUPERROR *penmError);
470PKFSOBJ kFsCacheLookupW(PKFSCACHE pCache, const wchar_t *pwszPath, KFSLOOKUPERROR *penmError);
471PKFSOBJ kFsCacheLookupRelativeToDirA(PKFSCACHE pCache, PKFSDIR pParent, const char *pszPath, KU32 cchPath, KU32 fFlags,
472 KFSLOOKUPERROR *penmError, PKFSOBJ *ppLastAncestor);
473PKFSOBJ kFsCacheLookupRelativeToDirW(PKFSCACHE pCache, PKFSDIR pParent, const wchar_t *pwszPath, KU32 cwcPath, KU32 fFlags,
474 KFSLOOKUPERROR *penmError, PKFSOBJ *ppLastAncestor);
475PKFSOBJ kFsCacheLookupWithLengthA(PKFSCACHE pCache, const char *pchPath, KSIZE cchPath, KFSLOOKUPERROR *penmError);
476PKFSOBJ kFsCacheLookupWithLengthW(PKFSCACHE pCache, const wchar_t *pwcPath, KSIZE cwcPath, KFSLOOKUPERROR *penmError);
477PKFSOBJ kFsCacheLookupNoMissingA(PKFSCACHE pCache, const char *pszPath, KFSLOOKUPERROR *penmError);
478PKFSOBJ kFsCacheLookupNoMissingW(PKFSCACHE pCache, const wchar_t *pwszPath, KFSLOOKUPERROR *penmError);
479
480/** @name KFSCACHE_LOOKUP_F_XXX - lookup flags
481 * @{ */
482/** No inserting new cache entries.
483 * This effectively prevent directories from being repopulated too. */
484#define KFSCACHE_LOOKUP_F_NO_INSERT KU32_C(1)
485/** No refreshing cache entries. */
486#define KFSCACHE_LOOKUP_F_NO_REFRESH KU32_C(2)
487/** @} */
488
489KU32 kFsCacheObjRelease(PKFSCACHE pCache, PKFSOBJ pObj);
490KU32 kFsCacheObjReleaseTagged(PKFSCACHE pCache, PKFSOBJ pObj, const char *pszWhere);
491#ifndef NDEBUG /* enable to debug object release. */
492# define kFsCacheObjRelease(a_pCache, a_pObj) kFsCacheObjReleaseTagged(a_pCache, a_pObj, __FUNCTION__)
493#endif
494KU32 kFsCacheObjRetain(PKFSOBJ pObj);
495PKFSUSERDATA kFsCacheObjAddUserData(PKFSCACHE pCache, PKFSOBJ pObj, KUPTR uKey, KSIZE cbUserData);
496PKFSUSERDATA kFsCacheObjGetUserData(PKFSCACHE pCache, PKFSOBJ pObj, KUPTR uKey);
497KBOOL kFsCacheObjGetFullPathA(PKFSOBJ pObj, char *pszPath, KSIZE cbPath, char chSlash);
498KBOOL kFsCacheObjGetFullPathW(PKFSOBJ pObj, wchar_t *pwszPath, KSIZE cwcPath, wchar_t wcSlash);
499KBOOL kFsCacheObjGetFullShortPathA(PKFSOBJ pObj, char *pszPath, KSIZE cbPath, char chSlash);
500KBOOL kFsCacheObjGetFullShortPathW(PKFSOBJ pObj, wchar_t *pwszPath, KSIZE cwcPath, wchar_t wcSlash);
501
502KBOOL kFsCacheFileSimpleOpenReadClose(PKFSCACHE pCache, PKFSOBJ pFileObj, KU64 offStart, void *pvBuf, KSIZE cbToRead);
503
504PKFSCACHE kFsCacheCreate(KU32 fFlags);
505void kFsCacheDestroy(PKFSCACHE);
506void kFsCacheInvalidateMissing(PKFSCACHE pCache);
507void kFsCacheInvalidateAll(PKFSCACHE pCache);
508void kFsCacheInvalidateCustomMissing(PKFSCACHE pCache);
509void kFsCacheInvalidateCustomBoth(PKFSCACHE pCache);
510KBOOL kFsCacheSetupCustomRevisionForTree(PKFSCACHE pCache, PKFSOBJ pRoot);
511KBOOL kFsCacheInvalidateDeletedDirectoryA(PKFSCACHE pCache, const char *pszDir);
512
513#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