summaryrefslogtreecommitdiff
path: root/libntfs-3g/cache.c (plain)
blob: 2ad8d359e101f341bada80836b858f8ea3885b16
1/**
2 * cache.c : deal with LRU caches
3 *
4 * Copyright (c) 2008-2010 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->payload, item->payload, 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 *next;
380 struct HASH_ENTRY *link;
381 int count;
382 int h;
383
384 current = (struct CACHED_GENERIC*)NULL;
385 count = 0;
386 if (cache) {
387 if (!(flags & CACHE_NOHASH) && cache->dohash) {
388 /*
389 * When possible, use the hash table to
390 * find out whether the entry if present
391 */
392 h = cache->dohash(item);
393 link = cache->first_hash[h];
394 while (link) {
395 if (compare(link->entry, item))
396 link = link->next;
397 else {
398 current = link->entry;
399 link = link->next;
400 if (current) {
401 drophashindex(cache,current,h);
402 do_invalidate(cache,
403 current,flags);
404 count++;
405 }
406 }
407 }
408 }
409 if ((flags & CACHE_NOHASH) || !cache->dohash) {
410 /*
411 * Search sequentially in LRU list
412 */
413 current = cache->most_recent_entry;
414 while (current) {
415 if (!compare(current, item)) {
416 next = current->next;
417 if (cache->dohash)
418 drophashindex(cache,current,
419 cache->dohash(current));
420 do_invalidate(cache,current,flags);
421 current = next;
422 count++;
423 } else {
424 current = current->next;
425 }
426 }
427 }
428 }
429 return (count);
430}
431
432int ntfs_remove_cache(struct CACHE_HEADER *cache,
433 struct CACHED_GENERIC *item, int flags)
434{
435 int count;
436
437 count = 0;
438 if (cache) {
439 if (cache->dohash)
440 drophashindex(cache,item,cache->dohash(item));
441 do_invalidate(cache,item,flags);
442 count++;
443 }
444 return (count);
445}
446
447/*
448 * Free memory allocated to a cache
449 */
450
451static void ntfs_free_cache(struct CACHE_HEADER *cache)
452{
453 struct CACHED_GENERIC *entry;
454
455 if (cache) {
456 for (entry=cache->most_recent_entry; entry; entry=entry->next) {
457 if (cache->dofree)
458 cache->dofree(entry);
459 if (entry->variable)
460 free(entry->variable);
461 }
462 free(cache);
463 }
464}
465
466/*
467 * Create a cache
468 *
469 * Returns the cache header, or NULL if the cache could not be created
470 */
471
472static struct CACHE_HEADER *ntfs_create_cache(const char *name,
473 cache_free dofree, cache_hash dohash,
474 int full_item_size,
475 int item_count, int max_hash)
476{
477 struct CACHE_HEADER *cache;
478 struct CACHED_GENERIC *pc;
479 struct CACHED_GENERIC *qc;
480 struct HASH_ENTRY *ph;
481 struct HASH_ENTRY *qh;
482 struct HASH_ENTRY **px;
483 size_t size;
484 int i;
485
486 size = sizeof(struct CACHE_HEADER) + item_count*full_item_size;
487 if (max_hash)
488 size += item_count*sizeof(struct HASH_ENTRY)
489 + max_hash*sizeof(struct HASH_ENTRY*);
490 cache = (struct CACHE_HEADER*)ntfs_malloc(size);
491 if (cache) {
492 /* header */
493 cache->name = name;
494 cache->dofree = dofree;
495 if (dohash && max_hash) {
496 cache->dohash = dohash;
497 cache->max_hash = max_hash;
498 } else {
499 cache->dohash = (cache_hash)NULL;
500 cache->max_hash = 0;
501 }
502 cache->fixed_size = full_item_size - sizeof(struct CACHED_GENERIC);
503 cache->reads = 0;
504 cache->writes = 0;
505 cache->hits = 0;
506 /* chain the data entries, and mark an invalid entry */
507 cache->most_recent_entry = (struct CACHED_GENERIC*)NULL;
508 cache->oldest_entry = (struct CACHED_GENERIC*)NULL;
509 cache->free_entry = &cache->entry[0];
510 pc = &cache->entry[0];
511 for (i=0; i<(item_count - 1); i++) {
512 qc = (struct CACHED_GENERIC*)((char*)pc
513 + full_item_size);
514 pc->next = qc;
515 pc->variable = (void*)NULL;
516 pc->varsize = 0;
517 pc = qc;
518 }
519 /* special for the last entry */
520 pc->next = (struct CACHED_GENERIC*)NULL;
521 pc->variable = (void*)NULL;
522 pc->varsize = 0;
523
524 if (max_hash) {
525 /* chain the hash entries */
526 ph = (struct HASH_ENTRY*)(((char*)pc) + full_item_size);
527 cache->free_hash = ph;
528 for (i=0; i<(item_count - 1); i++) {
529 qh = &ph[1];
530 ph->next = qh;
531 ph = qh;
532 }
533 /* special for the last entry */
534 if (item_count) {
535 ph->next = (struct HASH_ENTRY*)NULL;
536 }
537 /* create and initialize the hash indexes */
538 px = (struct HASH_ENTRY**)&ph[1];
539 cache->first_hash = px;
540 for (i=0; i<max_hash; i++)
541 px[i] = (struct HASH_ENTRY*)NULL;
542 } else {
543 cache->free_hash = (struct HASH_ENTRY*)NULL;
544 cache->first_hash = (struct HASH_ENTRY**)NULL;
545 }
546 }
547 return (cache);
548}
549
550/*
551 * Create all LRU caches
552 *
553 * No error return, if creation is not possible, cacheing will
554 * just be not available
555 */
556
557void ntfs_create_lru_caches(ntfs_volume *vol)
558{
559#if CACHE_INODE_SIZE
560 /* inode cache */
561 vol->xinode_cache = ntfs_create_cache("inode",(cache_free)NULL,
562 ntfs_dir_inode_hash, sizeof(struct CACHED_INODE),
563 CACHE_INODE_SIZE, 2*CACHE_INODE_SIZE);
564#endif
565#if CACHE_NIDATA_SIZE
566 /* idata cache */
567 vol->nidata_cache = ntfs_create_cache("nidata",
568 ntfs_inode_nidata_free, ntfs_inode_nidata_hash,
569 sizeof(struct CACHED_NIDATA),
570 CACHE_NIDATA_SIZE, 2*CACHE_NIDATA_SIZE);
571#endif
572#if CACHE_LOOKUP_SIZE
573 /* lookup cache */
574 vol->lookup_cache = ntfs_create_cache("lookup",
575 (cache_free)NULL, ntfs_dir_lookup_hash,
576 sizeof(struct CACHED_LOOKUP),
577 CACHE_LOOKUP_SIZE, 2*CACHE_LOOKUP_SIZE);
578#endif
579 vol->securid_cache = ntfs_create_cache("securid",(cache_free)NULL,
580 (cache_hash)NULL,sizeof(struct CACHED_SECURID), CACHE_SECURID_SIZE, 0);
581#if CACHE_LEGACY_SIZE
582 vol->legacy_cache = ntfs_create_cache("legacy",(cache_free)NULL,
583 (cache_hash)NULL, sizeof(struct CACHED_PERMISSIONS_LEGACY), CACHE_LEGACY_SIZE, 0);
584#endif
585}
586
587/*
588 * Free all LRU caches
589 */
590
591void ntfs_free_lru_caches(ntfs_volume *vol)
592{
593#if CACHE_INODE_SIZE
594 ntfs_free_cache(vol->xinode_cache);
595#endif
596#if CACHE_NIDATA_SIZE
597 ntfs_free_cache(vol->nidata_cache);
598#endif
599#if CACHE_LOOKUP_SIZE
600 ntfs_free_cache(vol->lookup_cache);
601#endif
602 ntfs_free_cache(vol->securid_cache);
603#if CACHE_LEGACY_SIZE
604 ntfs_free_cache(vol->legacy_cache);
605#endif
606}
607
generated by cgit at 2024-05-19 07:31:02 (GMT)