summaryrefslogtreecommitdiff
path: root/libntfs-3g/cache.c (plain)
blob: dd147672c047a82bcb7588889e7e4f453ac9ceca
1/**
2 * cache.c : deal with LRU caches
3 *
4 * Copyright (c) 2008-2009 Jean-Pierre Andre
5 *
6 * This program/include file is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License as published
8 * by the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 *
11 * This program/include file is distributed in the hope that it will be
12 * useful, but WITHOUT ANY WARRANTY; without even the implied warranty
13 * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program (in the main directory of the NTFS-3G
18 * distribution in the file COPYING); if not, write to the Free Software
19 * Foundation,Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20 */
21
22#ifdef HAVE_CONFIG_H
23#include "config.h"
24#endif
25
26#ifdef HAVE_STDLIB_H
27#include <stdlib.h>
28#endif
29#ifdef HAVE_STRING_H
30#include <string.h>
31#endif
32
33#include "types.h"
34#include "security.h"
35#include "cache.h"
36#include "misc.h"
37#include "logging.h"
38
39/*
40 * General functions to deal with LRU caches
41 *
42 * The cached data have to be organized in a structure in which
43 * the first fields must follow a mandatory pattern and further
44 * fields may contain any fixed size data. They are stored in an
45 * LRU list.
46 *
47 * A compare function must be provided for finding a wanted entry
48 * in the cache. Another function may be provided for invalidating
49 * an entry to facilitate multiple invalidation.
50 *
51 * These functions never return error codes. When there is a
52 * shortage of memory, data is simply not cached.
53 * When there is a hashing bug, hashing is dropped, and sequential
54 * searches are used.
55 */
56
57/*
58 * Enter a new hash index, after a new record has been inserted
59 *
60 * Do not call when a record has been modified (with no key change)
61 */
62
63static void inserthashindex(struct CACHE_HEADER *cache,
64 struct CACHED_GENERIC *current)
65{
66 int h;
67 struct HASH_ENTRY *link;
68 struct HASH_ENTRY *first;
69
70 if (cache->dohash) {
71 h = cache->dohash(current);
72 if ((h >= 0) && (h < cache->max_hash)) {
73 /* get a free link and insert at top of hash list */
74 link = cache->free_hash;
75 if (link) {
76 cache->free_hash = link->next;
77 first = cache->first_hash[h];
78 if (first)
79 link->next = first;
80 else
81 link->next = NULL;
82 link->entry = current;
83 cache->first_hash[h] = link;
84 } else {
85 ntfs_log_error("No more hash entries,"
86 " cache %s hashing dropped\n",
87 cache->name);
88 cache->dohash = (cache_hash)NULL;
89 }
90 } else {
91 ntfs_log_error("Illegal hash value,"
92 " cache %s hashing dropped\n",
93 cache->name);
94 cache->dohash = (cache_hash)NULL;
95 }
96 }
97}
98
99/*
100 * Drop a hash index when a record is about to be deleted
101 */
102
103static void drophashindex(struct CACHE_HEADER *cache,
104 const struct CACHED_GENERIC *current, int hash)
105{
106 struct HASH_ENTRY *link;
107 struct HASH_ENTRY *previous;
108
109 if (cache->dohash) {
110 if ((hash >= 0) && (hash < cache->max_hash)) {
111 /* find the link and unlink */
112 link = cache->first_hash[hash];
113 previous = (struct HASH_ENTRY*)NULL;
114 while (link && (link->entry != current)) {
115 previous = link;
116 link = link->next;
117 }
118 if (link) {
119 if (previous)
120 previous->next = link->next;
121 else
122 cache->first_hash[hash] = link->next;
123 link->next = cache->free_hash;
124 cache->free_hash = link;
125 } else {
126 ntfs_log_error("Bad hash list,"
127 " cache %s hashing dropped\n",
128 cache->name);
129 cache->dohash = (cache_hash)NULL;
130 }
131 } else {
132 ntfs_log_error("Illegal hash value,"
133 " cache %s hashing dropped\n",
134 cache->name);
135 cache->dohash = (cache_hash)NULL;
136 }
137 }
138}
139
140/*
141 * Fetch an entry from cache
142 *
143 * returns the cache entry, or NULL if not available
144 * The returned entry may be modified, but not freed
145 */
146
147struct CACHED_GENERIC *ntfs_fetch_cache(struct CACHE_HEADER *cache,
148 const struct CACHED_GENERIC *wanted, cache_compare compare)
149{
150 struct CACHED_GENERIC *current;
151 struct CACHED_GENERIC *previous;
152 struct HASH_ENTRY *link;
153 int h;
154
155 current = (struct CACHED_GENERIC*)NULL;
156 if (cache) {
157 if (cache->dohash) {
158 /*
159 * When possible, use the hash table to
160 * locate the entry if present
161 */
162 h = cache->dohash(wanted);
163 link = cache->first_hash[h];
164 while (link && compare(link->entry, wanted))
165 link = link->next;
166 if (link)
167 current = link->entry;
168 }
169 if (!cache->dohash) {
170 /*
171 * Search sequentially in LRU list if no hash table
172 * or if hashing has just failed
173 */
174 current = cache->most_recent_entry;
175 while (current
176 && compare(current, wanted)) {
177 current = current->next;
178 }
179 }
180 if (current) {
181 previous = current->previous;
182 cache->hits++;
183 if (previous) {
184 /*
185 * found and not at head of list, unlink from current
186 * position and relink as head of list
187 */
188 previous->next = current->next;
189 if (current->next)
190 current->next->previous
191 = current->previous;
192 else
193 cache->oldest_entry
194 = current->previous;
195 current->next = cache->most_recent_entry;
196 current->previous
197 = (struct CACHED_GENERIC*)NULL;
198 cache->most_recent_entry->previous = current;
199 cache->most_recent_entry = current;
200 }
201 }
202 cache->reads++;
203 }
204 return (current);
205}
206
207/*
208 * Enter an inode number into cache
209 * returns the cache entry or NULL if not possible
210 */
211
212struct CACHED_GENERIC *ntfs_enter_cache(struct CACHE_HEADER *cache,
213 const struct CACHED_GENERIC *item,
214 cache_compare compare)
215{
216 struct CACHED_GENERIC *current;
217 struct CACHED_GENERIC *before;
218 struct HASH_ENTRY *link;
219 int h;
220
221 current = (struct CACHED_GENERIC*)NULL;
222 if (cache) {
223 if (cache->dohash) {
224 /*
225 * When possible, use the hash table to
226 * find out whether the entry if present
227 */
228 h = cache->dohash(item);
229 link = cache->first_hash[h];
230 while (link && compare(link->entry, item))
231 link = link->next;
232 if (link) {
233 current = link->entry;
234 }
235 }
236 if (!cache->dohash) {
237 /*
238 * Search sequentially in LRU list to locate the end,
239 * and find out whether the entry is already in list
240 * As we normally go to the end, no statistics is
241 * kept.
242 */
243 current = cache->most_recent_entry;
244 while (current
245 && compare(current, item)) {
246 current = current->next;
247 }
248 }
249
250 if (!current) {
251 /*
252 * Not in list, get a free entry or reuse the
253 * last entry, and relink as head of list
254 * Note : we assume at least three entries, so
255 * before, previous and first are different when
256 * an entry is reused.
257 */
258
259 if (cache->free_entry) {
260 current = cache->free_entry;
261 cache->free_entry = cache->free_entry->next;
262 if (item->varsize) {
263 current->variable = ntfs_malloc(
264 item->varsize);
265 } else
266 current->variable = (void*)NULL;
267 current->varsize = item->varsize;
268 if (!cache->oldest_entry)
269 cache->oldest_entry = current;
270 } else {
271 /* reusing the oldest entry */
272 current = cache->oldest_entry;
273 before = current->previous;
274 before->next = (struct CACHED_GENERIC*)NULL;
275 if (cache->dohash)
276 drophashindex(cache,current,
277 cache->dohash(current));
278 if (cache->dofree)
279 cache->dofree(current);
280 cache->oldest_entry = current->previous;
281 if (item->varsize) {
282 if (current->varsize)
283 current->variable = realloc(
284 current->variable,
285 item->varsize);
286 else
287 current->variable = ntfs_malloc(
288 item->varsize);
289 } else {
290 if (current->varsize)
291 free(current->variable);
292 current->variable = (void*)NULL;
293 }
294 current->varsize = item->varsize;
295 }
296 current->next = cache->most_recent_entry;
297 current->previous = (struct CACHED_GENERIC*)NULL;
298 if (cache->most_recent_entry)
299 cache->most_recent_entry->previous = current;
300 cache->most_recent_entry = current;
301 memcpy(current->fixed, item->fixed, cache->fixed_size);
302 if (item->varsize) {
303 if (current->variable) {
304 memcpy(current->variable,
305 item->variable, item->varsize);
306 } else {
307 /*
308 * no more memory for variable part
309 * recycle entry in free list
310 * not an error, just uncacheable
311 */
312 cache->most_recent_entry = current->next;
313 current->next = cache->free_entry;
314 cache->free_entry = current;
315 current = (struct CACHED_GENERIC*)NULL;
316 }
317 } else {
318 current->variable = (void*)NULL;
319 current->varsize = 0;
320 }
321 if (cache->dohash && current)
322 inserthashindex(cache,current);
323 }
324 cache->writes++;
325 }
326 return (current);
327}
328
329/*
330 * Invalidate a cache entry
331 * The entry is moved to the free entry list
332 * A specific function may be called for entry deletion
333 */
334
335static void do_invalidate(struct CACHE_HEADER *cache,
336 struct CACHED_GENERIC *current, int flags)
337{
338 struct CACHED_GENERIC *previous;
339
340 previous = current->previous;
341 if ((flags & CACHE_FREE) && cache->dofree)
342 cache->dofree(current);
343 /*
344 * Relink into free list
345 */
346 if (current->next)
347 current->next->previous = current->previous;
348 else
349 cache->oldest_entry = current->previous;
350 if (previous)
351 previous->next = current->next;
352 else
353 cache->most_recent_entry = current->next;
354 current->next = cache->free_entry;
355 cache->free_entry = current;
356 if (current->variable)
357 free(current->variable);
358 current->varsize = 0;
359 }
360
361
362/*
363 * Invalidate entries in cache
364 *
365 * Several entries may have to be invalidated (at least for inodes
366 * associated to directories which have been renamed), a different
367 * compare function may be provided to select entries to invalidate
368 *
369 * Returns the number of deleted entries, this can be used by
370 * the caller to signal a cache corruption if the entry was
371 * supposed to be found.
372 */
373
374int ntfs_invalidate_cache(struct CACHE_HEADER *cache,
375 const struct CACHED_GENERIC *item, cache_compare compare,
376 int flags)
377{
378 struct CACHED_GENERIC *current;
379 struct CACHED_GENERIC *previous;
380 struct CACHED_GENERIC *next;
381 struct HASH_ENTRY *link;
382 int count;
383 int h;
384
385 current = (struct CACHED_GENERIC*)NULL;
386 count = 0;
387 if (cache) {
388 if (!(flags & CACHE_NOHASH) && cache->dohash) {
389 /*
390 * When possible, use the hash table to
391 * find out whether the entry if present
392 */
393 h = cache->dohash(item);
394 link = cache->first_hash[h];
395 while (link) {
396 if (compare(link->entry, item))
397 link = link->next;
398 else {
399 current = link->entry;
400 link = link->next;
401 if (current) {
402 drophashindex(cache,current,h);
403 do_invalidate(cache,
404 current,flags);
405 count++;
406 }
407 }
408 }
409 }
410 if ((flags & CACHE_NOHASH) || !cache->dohash) {
411 /*
412 * Search sequentially in LRU list
413 */
414 current = cache->most_recent_entry;
415 previous = (struct CACHED_GENERIC*)NULL;
416 while (current) {
417 if (!compare(current, item)) {
418 next = current->next;
419 if (cache->dohash)
420 drophashindex(cache,current,
421 cache->dohash(current));
422 do_invalidate(cache,current,flags);
423 current = next;
424 count++;
425 } else {
426 previous = current;
427 current = current->next;
428 }
429 }
430 }
431 }
432 return (count);
433}
434
435int ntfs_remove_cache(struct CACHE_HEADER *cache,
436 struct CACHED_GENERIC *item, int flags)
437{
438 int count;
439
440 count = 0;
441 if (cache) {
442 if (cache->dohash)
443 drophashindex(cache,item,cache->dohash(item));
444 do_invalidate(cache,item,flags);
445 count++;
446 }
447 return (count);
448}
449
450/*
451 * Free memory allocated to a cache
452 */
453
454static void ntfs_free_cache(struct CACHE_HEADER *cache)
455{
456 struct CACHED_GENERIC *entry;
457
458 if (cache) {
459 for (entry=cache->most_recent_entry; entry; entry=entry->next) {
460 if (cache->dofree)
461 cache->dofree(entry);
462 if (entry->variable)
463 free(entry->variable);
464 }
465 free(cache);
466 }
467}
468
469/*
470 * Create a cache
471 *
472 * Returns the cache header, or NULL if the cache could not be created
473 */
474
475static struct CACHE_HEADER *ntfs_create_cache(const char *name,
476 cache_free dofree, cache_hash dohash,
477 int full_item_size,
478 int item_count, int max_hash)
479{
480 struct CACHE_HEADER *cache;
481 struct CACHED_GENERIC *pc;
482 struct CACHED_GENERIC *qc;
483 struct HASH_ENTRY *ph;
484 struct HASH_ENTRY *qh;
485 struct HASH_ENTRY **px;
486 size_t size;
487 int i;
488
489 size = sizeof(struct CACHE_HEADER) + item_count*full_item_size;
490 if (max_hash)
491 size += item_count*sizeof(struct HASH_ENTRY)
492 + max_hash*sizeof(struct HASH_ENTRY*);
493 cache = (struct CACHE_HEADER*)ntfs_malloc(size);
494 if (cache) {
495 /* header */
496 cache->name = name;
497 cache->dofree = dofree;
498 if (dohash && max_hash) {
499 cache->dohash = dohash;
500 cache->max_hash = max_hash;
501 } else {
502 cache->dohash = (cache_hash)NULL;
503 cache->max_hash = 0;
504 }
505 cache->fixed_size = full_item_size - sizeof(struct CACHED_GENERIC);
506 cache->reads = 0;
507 cache->writes = 0;
508 cache->hits = 0;
509 /* chain the data entries, and mark an invalid entry */
510 cache->most_recent_entry = (struct CACHED_GENERIC*)NULL;
511 cache->oldest_entry = (struct CACHED_GENERIC*)NULL;
512 cache->free_entry = &cache->entry[0];
513 pc = &cache->entry[0];
514 for (i=0; i<(item_count - 1); i++) {
515 qc = (struct CACHED_GENERIC*)((char*)pc
516 + full_item_size);
517 pc->next = qc;
518 pc->variable = (void*)NULL;
519 pc->varsize = 0;
520 pc = qc;
521 }
522 /* special for the last entry */
523 pc->next = (struct CACHED_GENERIC*)NULL;
524 pc->variable = (void*)NULL;
525 pc->varsize = 0;
526
527 if (max_hash) {
528 /* chain the hash entries */
529 ph = (struct HASH_ENTRY*)(((char*)pc) + full_item_size);
530 cache->free_hash = ph;
531 for (i=0; i<(item_count - 1); i++) {
532 qh = &ph[1];
533 ph->next = qh;
534 ph = qh;
535 }
536 /* special for the last entry */
537 if (item_count) {
538 ph->next = (struct HASH_ENTRY*)NULL;
539 }
540 /* create and initialize the hash indexes */
541 px = (struct HASH_ENTRY**)&ph[1];
542 cache->first_hash = px;
543 for (i=0; i<max_hash; i++)
544 px[i] = (struct HASH_ENTRY*)NULL;
545 } else {
546 cache->free_hash = (struct HASH_ENTRY*)NULL;
547 cache->first_hash = (struct HASH_ENTRY**)NULL;
548 }
549 }
550 return (cache);
551}
552
553/*
554 * Create all LRU caches
555 *
556 * No error return, if creation is not possible, cacheing will
557 * just be not available
558 */
559
560void ntfs_create_lru_caches(ntfs_volume *vol)
561{
562#if CACHE_INODE_SIZE
563 /* inode cache */
564 vol->xinode_cache = ntfs_create_cache("inode",(cache_free)NULL,
565 ntfs_dir_inode_hash, sizeof(struct CACHED_INODE),
566 CACHE_INODE_SIZE, 2*CACHE_INODE_SIZE);
567#endif
568#if CACHE_NIDATA_SIZE
569 /* idata cache */
570 vol->nidata_cache = ntfs_create_cache("nidata",
571 ntfs_inode_nidata_free, ntfs_inode_nidata_hash,
572 sizeof(struct CACHED_NIDATA),
573 CACHE_NIDATA_SIZE, 2*CACHE_NIDATA_SIZE);
574#endif
575#if CACHE_LOOKUP_SIZE
576 /* lookup cache */
577 vol->lookup_cache = ntfs_create_cache("lookup",
578 (cache_free)NULL, ntfs_dir_lookup_hash,
579 sizeof(struct CACHED_LOOKUP),
580 CACHE_LOOKUP_SIZE, 2*CACHE_LOOKUP_SIZE);
581#endif
582 vol->securid_cache = ntfs_create_cache("securid",(cache_free)NULL,
583 (cache_hash)NULL,sizeof(struct CACHED_SECURID), CACHE_SECURID_SIZE, 0);
584#if CACHE_LEGACY_SIZE
585 vol->legacy_cache = ntfs_create_cache("legacy",(cache_free)NULL,
586 (cache_hash)NULL, sizeof(struct CACHED_PERMISSIONS_LEGACY), CACHE_LEGACY_SIZE, 0);
587#endif
588}
589
590/*
591 * Free all LRU caches
592 */
593
594void ntfs_free_lru_caches(ntfs_volume *vol)
595{
596#if CACHE_INODE_SIZE
597 ntfs_free_cache(vol->xinode_cache);
598#endif
599#if CACHE_NIDATA_SIZE
600 ntfs_free_cache(vol->nidata_cache);
601#endif
602#if CACHE_LOOKUP_SIZE
603 ntfs_free_cache(vol->lookup_cache);
604#endif
605 ntfs_free_cache(vol->securid_cache);
606#if CACHE_LEGACY_SIZE
607 ntfs_free_cache(vol->legacy_cache);
608#endif
609}
610
generated by cgit at 2024-05-19 02:50:54 (GMT)