source: trunk/src/lib/nt/kFsCache.h@ 2854

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

updates
  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 13.7 KB
Line 
1/* $Id: kFsCache.h 2853 2016-08-31 20:56:48Z 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/** Whether the file system update the modified timestamp of directories
83 * when something is removed from it or added to it.
84 * @remarks They say NTFS is the only windows filesystem doing this. */
85#define KFSOBJ_F_WORKING_DIR_MTIME KU32_C(0x00000001)
86/** NTFS file system volume. */
87#define KFSOBJ_F_NTFS KU32_C(0x80000000)
88/** @} */
89
90
91#define IS_ALPHA(ch) ( ((ch) >= 'A' && (ch) <= 'Z') || ((ch) >= 'a' && (ch) <= 'z') )
92#define IS_SLASH(ch) ((ch) == '\\' || (ch) == '/')
93
94
95
96
97/** Pointer to a core object. */
98typedef struct KFSOBJ *PKFSOBJ;
99/** Pointer to a directory object. */
100typedef struct KFSDIR *PKFSDIR;
101/** Pointer to a directory hash table entry. */
102typedef struct KFSOBJHASH *PKFSOBJHASH;
103
104
105/**
106 * Directory hash table entry.
107 *
108 * There can be two of these per directory entry when the short name differs
109 * from the long name.
110 */
111typedef struct KFSOBJHASH
112{
113 /** Pointer to the next entry with the same hash. */
114 PKFSOBJHASH pNext;
115 /** Pointer to the object. */
116 PKFSOBJ pObj;
117} KFSOBJHASH;
118
119
120/**
121 * Base cache node.
122 */
123typedef struct KFSOBJ
124{
125 /** Magic value (KFSOBJ_MAGIC). */
126 KU32 u32Magic;
127 /** Number of references. */
128 KU32 volatile cRefs;
129 /** The cache generation, see KFSOBJ_CACHE_GEN_IGNORE. */
130 KU32 uCacheGen;
131 /** The object type, KFSOBJ_TYPE_XXX. */
132 KU8 bObjType;
133 /** Set if the Stats member is valid, clear if not. */
134 KBOOL fHaveStats;
135 /** Unused flags. */
136 KBOOL abUnused[2];
137 /** Flags, KFSOBJ_F_XXX. */
138 KU32 fFlags;
139
140 /** Pointer to the parent (directory).
141 * This is only NULL for a root. */
142 PKFSDIR pParent;
143
144 /** The directory name. (Allocated after the structure.) */
145 const char *pszName;
146 /** The length of pszName. */
147 KU16 cchName;
148 /** The length of the parent path (up to where pszName starts).
149 * @note This is valuable when constructing an absolute path to this node by
150 * means of the parent pointer (no need for recursion). */
151 KU16 cchParent;
152#ifdef KFSCACHE_CFG_UTF16
153 /** The length of pwszName (in wchar_t's). */
154 KU16 cwcName;
155 /** The length of the parent UTF-16 path (in wchar_t's).
156 * @note This is valuable when constructing an absolute path to this node by
157 * means of the parent pointer (no need for recursion). */
158 KU16 cwcParent;
159 /** The UTF-16 object name. (Allocated after the structure.) */
160 const wchar_t *pwszName;
161#endif
162
163#ifdef KFSCACHE_CFG_SHORT_NAMES
164 /** The short object name. (Allocated after the structure, could be same
165 * as pszName.) */
166 const char *pszShortName;
167 /** The length of pszShortName. */
168 KU16 cchShortName;
169 /** The length of the short parent path (up to where pszShortName starts). */
170 KU16 cchShortParent;
171# ifdef KFSCACHE_CFG_UTF16
172 /** The length of pwszShortName (in wchar_t's). */
173 KU16 cwcShortName;
174 /** The length of the short parent UTF-16 path (in wchar_t's). */
175 KU16 cwcShortParent;
176 /** The UTF-16 short object name. (Allocated after the structure, possibly
177 * same as pwszName.) */
178 const wchar_t *pwszShortName;
179# endif
180#endif
181
182 /** Stats - only valid when fHaveStats is set. */
183 BirdStat_T Stats;
184} KFSOBJ;
185
186/** The magic for a KFSOBJ structure (Thelonious Sphere Monk). */
187#define KFSOBJ_MAGIC KU32_C(0x19171010)
188
189
190/**
191 * Directory node in the cache.
192 */
193typedef struct KFSDIR
194{
195 /** The core object information. */
196 KFSOBJ Obj;
197
198 /** Child objects. */
199 PKFSOBJ *papChildren;
200 /** The number of child objects. */
201 KU32 cChildren;
202
203 /** The size of the hash table.
204 * @remarks The hash table is optional and only used when there are a lot of
205 * entries in the directory. */
206 KU32 cHashTab;
207 /** Pointer to the hash table.
208 * @todo this isn't quite there yet, structure wise. sigh. */
209 PKFSOBJHASH paHashTab;
210
211 /** Handle to the directory (we generally keep it open). */
212 HANDLE hDir;
213 /** The device number we queried/inherited when opening it. */
214 KU64 uDevNo;
215
216 /** Set if populated. */
217 KBOOL fPopulated;
218} KFSDIR;
219
220
221/**
222 * Lookup errors.
223 */
224typedef enum KFSLOOKUPERROR
225{
226 /** Lookup was a success. */
227 KFSLOOKUPERROR_SUCCESS = 0,
228 /** A path component was not found. */
229 KFSLOOKUPERROR_PATH_COMP_NOT_FOUND,
230 /** A path component is not a directory. */
231 KFSLOOKUPERROR_PATH_COMP_NOT_DIR,
232 /** The final path entry is not a directory (trailing slash). */
233 KFSLOOKUPERROR_NOT_DIR,
234 /** Not found. */
235 KFSLOOKUPERROR_NOT_FOUND,
236 /** The path is too long. */
237 KFSLOOKUPERROR_PATH_TOO_LONG,
238 /** Unsupported path type. */
239 KFSLOOKUPERROR_UNSUPPORTED,
240 /** We're out of memory. */
241 KFSLOOKUPERROR_OUT_OF_MEMORY,
242
243 /** Error opening directory. */
244 KFSLOOKUPERROR_DIR_OPEN_ERROR,
245 /** Error reading directory. */
246 KFSLOOKUPERROR_DIR_READ_ERROR,
247 /** UTF-16 to ANSI conversion error. */
248 KFSLOOKUPERROR_ANSI_CONVERSION_ERROR,
249 /** ANSI to UTF-16 conversion error. */
250 KFSLOOKUPERROR_UTF16_CONVERSION_ERROR,
251 /** Internal error. */
252 KFSLOOKUPERROR_INTERNAL_ERROR
253} KFSLOOKUPERROR;
254
255
256/** Pointer to an ANSI path hash table entry. */
257typedef struct KFSHASHA *PKFSHASHA;
258/**
259 * ANSI file system path hash table entry.
260 * The path hash table allows us to skip parsing and walking a path.
261 */
262typedef struct KFSHASHA
263{
264 /** Next entry with the same hash table slot. */
265 PKFSHASHA pNext;
266 /** Path hash value. */
267 KU32 uHashPath;
268 /** The path length. */
269 KU32 cchPath;
270 /** The cache generation ID. */
271 KU32 uCacheGen;
272 /** The lookup error (when pFsObj is NULL). */
273 KFSLOOKUPERROR enmError;
274 /** The path. (Allocated after the structure.) */
275 const char *pszPath;
276 /** Pointer to the matching FS object.
277 * This is NULL for negative path entries? */
278 PKFSOBJ pFsObj;
279} KFSHASHA;
280
281
282#ifdef KFSCACHE_CFG_UTF16
283/** Pointer to an UTF-16 path hash table entry. */
284typedef struct KFSHASHW *PKFSHASHW;
285/**
286 * UTF-16 file system path hash table entry. The path hash table allows us
287 * to skip parsing and walking a path.
288 */
289typedef struct KFSHASHW
290{
291 /** Next entry with the same hash table slot. */
292 PKFSHASHW pNext;
293 /** Path hash value. */
294 KU32 uHashPath;
295 /** The path length (in wchar_t units). */
296 KU32 cwcPath;
297 /** The cache generation ID. */
298 KU32 uCacheGen;
299 /** The lookup error (when pFsObj is NULL). */
300 KFSLOOKUPERROR enmError;
301 /** The path. (Allocated after the structure.) */
302 const wchar_t *pwszPath;
303 /** Pointer to the matching FS object.
304 * This is NULL for negative path entries? */
305 PKFSOBJ pFsObj;
306} KFSHASHW;
307#endif
308
309
310/** @name KFSCACHE_F_XXX
311 * @{ */
312/** Whether to cache missing directory entries (KFSOBJ_TYPE_MISSING). */
313#define KFSCACHE_F_MISSING_OBJECTS KU32_C(0x00000001)
314/** Whether to cache missing paths. */
315#define KFSCACHE_F_MISSING_PATHS KU32_C(0x00000002)
316/** @} */
317
318
319/** Pointer to a cache. */
320typedef struct KFSCACHE *PKFSCACHE;
321/**
322 * Directory cache instance.
323 */
324typedef struct KFSCACHE
325{
326 /** Magic value (KFSCACHE_MAGIC). */
327 KU32 u32Magic;
328 /** Cache flags. */
329 KU32 fFlags;
330
331 /** The current cache generation for objects that already exists. */
332 KU32 uGeneration;
333 /** The current cache generation for missing objects, negative results, ++. */
334 KU32 uGenerationMissing;
335
336 /** Number of cache objects. */
337 KSIZE cObjects;
338 /** Memory occupied by the cache object structures. */
339 KSIZE cbObjects;
340 /** Number of lookups. */
341 KSIZE cLookups;
342 /** Number of hits in the path hash tables. */
343 KSIZE cPathHashHits;
344 /** Number of hits walking the file system hierarchy. */
345 KSIZE cWalkHits;
346
347 /** The root directory. */
348 KFSDIR RootDir;
349
350 /** File system hash table for ANSI filename strings. */
351 PKFSHASHA apAnsiPaths[KFSCACHE_CFG_PATH_HASH_TAB_SIZE];
352 /** Number of paths in the apAnsiPaths hash table. */
353 KSIZE cAnsiPaths;
354 /** Number of collisions in the apAnsiPaths hash table. */
355 KSIZE cAnsiPathCollisions;
356 /** Amount of memory used by the path entries. */
357 KSIZE cbAnsiPaths;
358
359#ifdef KFSCACHE_CFG_UTF16
360 /** Number of paths in the apUtf16Paths hash table. */
361 KSIZE cUtf16Paths;
362 /** Number of collisions in the apUtf16Paths hash table. */
363 KSIZE cUtf16PathCollisions;
364 /** Amount of memory used by the UTF-16 path entries. */
365 KSIZE cbUtf16Paths;
366 /** File system hash table for UTF-16 filename strings. */
367 PKFSHASHW apUtf16Paths[KFSCACHE_CFG_PATH_HASH_TAB_SIZE];
368#endif
369} KFSCACHE;
370
371/** Magic value for KFSCACHE::u32Magic (Jon Batiste). */
372#define KFSCACHE_MAGIC KU32_C(0x19861111)
373
374
375/** @def KW_LOG
376 * Generic logging.
377 * @param a Argument list for kFsCacheDbgPrintf */
378#ifdef NDEBUG
379# define KFSCACHE_LOG(a) do { } while (0)
380#else
381# define KFSCACHE_LOG(a) kFsCacheDbgPrintf a
382void kFsCacheDbgPrintfV(const char *pszFormat, va_list va);
383void kFsCacheDbgPrintf(const char *pszFormat, ...);
384#endif
385
386
387KBOOL kFsCacheDirAddChild(PKFSCACHE pCache, PKFSDIR pParent, PKFSOBJ pChild, KFSLOOKUPERROR *penmError);
388PKFSOBJ kFsCacheCreateObject(PKFSCACHE pCache, PKFSDIR pParent,
389 char const *pszName, KU16 cchName, wchar_t const *pwszName, KU16 cwcName,
390#ifdef KFSCACHE_CFG_SHORT_NAMES
391 char const *pszShortName, KU16 cchShortName, wchar_t const *pwszShortName, KU16 cwcShortName,
392#endif
393 KU8 bObjType, KFSLOOKUPERROR *penmError);
394PKFSOBJ kFsCacheCreateObjectW(PKFSCACHE pCache, PKFSDIR pParent, wchar_t const *pwszName, KU32 cwcName,
395#ifdef KFSCACHE_CFG_SHORT_NAMES
396 wchar_t const *pwszShortName, KU32 cwcShortName,
397#endif
398 KU8 bObjType, KFSLOOKUPERROR *penmError);
399PKFSOBJ kFsCacheLookupA(PKFSCACHE pCache, const char *pszPath, KFSLOOKUPERROR *penmError);
400PKFSOBJ kFsCacheLookupW(PKFSCACHE pCache, const wchar_t *pwszPath, KFSLOOKUPERROR *penmError);
401
402KU32 kFsCacheObjRelease(PKFSCACHE pCache, PKFSOBJ pObj);
403KU32 kFsCacheObjRetain(PKFSOBJ pObj);
404
405PKFSCACHE kFsCacheCreate(KU32 fFlags);
406void kFsCacheDestroy(PKFSCACHE);
407
408#endif
Note: See TracBrowser for help on using the repository browser.