Lines Matching +full:file +full:- +full:entry +full:- +full:cache
2 * cache.c : deal with LRU caches
4 * Copyright (c) 2008-2010 Jean-Pierre Andre
6 * This program/include file is free software; you can redistribute it and/or
11 * This program/include file is distributed in the hope that it will be
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
35 #include "cache.h"
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.
63 static void inserthashindex(struct CACHE_HEADER *cache, in inserthashindex() argument
70 if (cache->dohash) { in inserthashindex()
71 h = cache->dohash(current); in inserthashindex()
72 if ((h >= 0) && (h < cache->max_hash)) { in inserthashindex()
74 link = cache->free_hash; in inserthashindex()
76 cache->free_hash = link->next; in inserthashindex()
77 first = cache->first_hash[h]; in inserthashindex()
79 link->next = first; in inserthashindex()
81 link->next = NULL; in inserthashindex()
82 link->entry = current; in inserthashindex()
83 cache->first_hash[h] = link; in inserthashindex()
86 " cache %s hashing dropped\n", in inserthashindex()
87 cache->name); in inserthashindex()
88 cache->dohash = (cache_hash)NULL; in inserthashindex()
92 " cache %s hashing dropped\n", in inserthashindex()
93 cache->name); in inserthashindex()
94 cache->dohash = (cache_hash)NULL; in inserthashindex()
103 static void drophashindex(struct CACHE_HEADER *cache, in drophashindex() argument
109 if (cache->dohash) { in drophashindex()
110 if ((hash >= 0) && (hash < cache->max_hash)) { in drophashindex()
112 link = cache->first_hash[hash]; in drophashindex()
114 while (link && (link->entry != current)) { in drophashindex()
116 link = link->next; in drophashindex()
120 previous->next = link->next; in drophashindex()
122 cache->first_hash[hash] = link->next; in drophashindex()
123 link->next = cache->free_hash; in drophashindex()
124 cache->free_hash = link; in drophashindex()
127 " cache %s hashing dropped\n", in drophashindex()
128 cache->name); in drophashindex()
129 cache->dohash = (cache_hash)NULL; in drophashindex()
133 " cache %s hashing dropped\n", in drophashindex()
134 cache->name); in drophashindex()
135 cache->dohash = (cache_hash)NULL; in drophashindex()
141 * Fetch an entry from cache
143 * returns the cache entry, or NULL if not available
144 * The returned entry may be modified, but not freed
147 struct CACHED_GENERIC *ntfs_fetch_cache(struct CACHE_HEADER *cache, in ntfs_fetch_cache() argument
156 if (cache) { in ntfs_fetch_cache()
157 if (cache->dohash) { in ntfs_fetch_cache()
160 * locate the entry if present in ntfs_fetch_cache()
162 h = cache->dohash(wanted); in ntfs_fetch_cache()
163 link = cache->first_hash[h]; in ntfs_fetch_cache()
164 while (link && compare(link->entry, wanted)) in ntfs_fetch_cache()
165 link = link->next; in ntfs_fetch_cache()
167 current = link->entry; in ntfs_fetch_cache()
169 if (!cache->dohash) { in ntfs_fetch_cache()
174 current = cache->most_recent_entry; in ntfs_fetch_cache()
177 current = current->next; in ntfs_fetch_cache()
181 previous = current->previous; in ntfs_fetch_cache()
182 cache->hits++; in ntfs_fetch_cache()
188 previous->next = current->next; in ntfs_fetch_cache()
189 if (current->next) in ntfs_fetch_cache()
190 current->next->previous in ntfs_fetch_cache()
191 = current->previous; in ntfs_fetch_cache()
193 cache->oldest_entry in ntfs_fetch_cache()
194 = current->previous; in ntfs_fetch_cache()
195 current->next = cache->most_recent_entry; in ntfs_fetch_cache()
196 current->previous in ntfs_fetch_cache()
198 cache->most_recent_entry->previous = current; in ntfs_fetch_cache()
199 cache->most_recent_entry = current; in ntfs_fetch_cache()
202 cache->reads++; in ntfs_fetch_cache()
208 * Enter an inode number into cache
209 * returns the cache entry or NULL if not possible
212 struct CACHED_GENERIC *ntfs_enter_cache(struct CACHE_HEADER *cache, in ntfs_enter_cache() argument
222 if (cache) { in ntfs_enter_cache()
223 if (cache->dohash) { in ntfs_enter_cache()
226 * find out whether the entry if present in ntfs_enter_cache()
228 h = cache->dohash(item); in ntfs_enter_cache()
229 link = cache->first_hash[h]; in ntfs_enter_cache()
230 while (link && compare(link->entry, item)) in ntfs_enter_cache()
231 link = link->next; in ntfs_enter_cache()
233 current = link->entry; in ntfs_enter_cache()
236 if (!cache->dohash) { in ntfs_enter_cache()
239 * and find out whether the entry is already in list in ntfs_enter_cache()
243 current = cache->most_recent_entry; in ntfs_enter_cache()
246 current = current->next; in ntfs_enter_cache()
252 * Not in list, get a free entry or reuse the in ntfs_enter_cache()
253 * last entry, and relink as head of list in ntfs_enter_cache()
256 * an entry is reused. in ntfs_enter_cache()
259 if (cache->free_entry) { in ntfs_enter_cache()
260 current = cache->free_entry; in ntfs_enter_cache()
261 cache->free_entry = cache->free_entry->next; in ntfs_enter_cache()
262 if (item->varsize) { in ntfs_enter_cache()
263 current->variable = ntfs_malloc( in ntfs_enter_cache()
264 item->varsize); in ntfs_enter_cache()
266 current->variable = (void*)NULL; in ntfs_enter_cache()
267 current->varsize = item->varsize; in ntfs_enter_cache()
268 if (!cache->oldest_entry) in ntfs_enter_cache()
269 cache->oldest_entry = current; in ntfs_enter_cache()
271 /* reusing the oldest entry */ in ntfs_enter_cache()
272 current = cache->oldest_entry; in ntfs_enter_cache()
273 before = current->previous; in ntfs_enter_cache()
274 before->next = (struct CACHED_GENERIC*)NULL; in ntfs_enter_cache()
275 if (cache->dohash) in ntfs_enter_cache()
276 drophashindex(cache,current, in ntfs_enter_cache()
277 cache->dohash(current)); in ntfs_enter_cache()
278 if (cache->dofree) in ntfs_enter_cache()
279 cache->dofree(current); in ntfs_enter_cache()
280 cache->oldest_entry = current->previous; in ntfs_enter_cache()
281 if (item->varsize) { in ntfs_enter_cache()
282 if (current->varsize) in ntfs_enter_cache()
283 current->variable = realloc( in ntfs_enter_cache()
284 current->variable, in ntfs_enter_cache()
285 item->varsize); in ntfs_enter_cache()
287 current->variable = ntfs_malloc( in ntfs_enter_cache()
288 item->varsize); in ntfs_enter_cache()
290 if (current->varsize) in ntfs_enter_cache()
291 free(current->variable); in ntfs_enter_cache()
292 current->variable = (void*)NULL; in ntfs_enter_cache()
294 current->varsize = item->varsize; in ntfs_enter_cache()
296 current->next = cache->most_recent_entry; in ntfs_enter_cache()
297 current->previous = (struct CACHED_GENERIC*)NULL; in ntfs_enter_cache()
298 if (cache->most_recent_entry) in ntfs_enter_cache()
299 cache->most_recent_entry->previous = current; in ntfs_enter_cache()
300 cache->most_recent_entry = current; in ntfs_enter_cache()
301 memcpy(current->payload, item->payload, cache->fixed_size); in ntfs_enter_cache()
302 if (item->varsize) { in ntfs_enter_cache()
303 if (current->variable) { in ntfs_enter_cache()
304 memcpy(current->variable, in ntfs_enter_cache()
305 item->variable, item->varsize); in ntfs_enter_cache()
309 * recycle entry in free list in ntfs_enter_cache()
312 cache->most_recent_entry = current->next; in ntfs_enter_cache()
313 current->next = cache->free_entry; in ntfs_enter_cache()
314 cache->free_entry = current; in ntfs_enter_cache()
318 current->variable = (void*)NULL; in ntfs_enter_cache()
319 current->varsize = 0; in ntfs_enter_cache()
321 if (cache->dohash && current) in ntfs_enter_cache()
322 inserthashindex(cache,current); in ntfs_enter_cache()
324 cache->writes++; in ntfs_enter_cache()
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
335 static void do_invalidate(struct CACHE_HEADER *cache, in do_invalidate() argument
340 previous = current->previous; in do_invalidate()
341 if ((flags & CACHE_FREE) && cache->dofree) in do_invalidate()
342 cache->dofree(current); in do_invalidate()
346 if (current->next) in do_invalidate()
347 current->next->previous = current->previous; in do_invalidate()
349 cache->oldest_entry = current->previous; in do_invalidate()
351 previous->next = current->next; in do_invalidate()
353 cache->most_recent_entry = current->next; in do_invalidate()
354 current->next = cache->free_entry; in do_invalidate()
355 cache->free_entry = current; in do_invalidate()
356 if (current->variable) in do_invalidate()
357 free(current->variable); in do_invalidate()
358 current->varsize = 0; in do_invalidate()
363 * Invalidate entries in cache
370 * the caller to signal a cache corruption if the entry was
374 int ntfs_invalidate_cache(struct CACHE_HEADER *cache, in ntfs_invalidate_cache() argument
386 if (cache) { in ntfs_invalidate_cache()
387 if (!(flags & CACHE_NOHASH) && cache->dohash) { in ntfs_invalidate_cache()
390 * find out whether the entry if present in ntfs_invalidate_cache()
392 h = cache->dohash(item); in ntfs_invalidate_cache()
393 link = cache->first_hash[h]; in ntfs_invalidate_cache()
395 if (compare(link->entry, item)) in ntfs_invalidate_cache()
396 link = link->next; in ntfs_invalidate_cache()
398 current = link->entry; in ntfs_invalidate_cache()
399 link = link->next; in ntfs_invalidate_cache()
401 drophashindex(cache,current,h); in ntfs_invalidate_cache()
402 do_invalidate(cache, in ntfs_invalidate_cache()
409 if ((flags & CACHE_NOHASH) || !cache->dohash) { in ntfs_invalidate_cache()
413 current = cache->most_recent_entry; in ntfs_invalidate_cache()
416 next = current->next; in ntfs_invalidate_cache()
417 if (cache->dohash) in ntfs_invalidate_cache()
418 drophashindex(cache,current, in ntfs_invalidate_cache()
419 cache->dohash(current)); in ntfs_invalidate_cache()
420 do_invalidate(cache,current,flags); in ntfs_invalidate_cache()
424 current = current->next; in ntfs_invalidate_cache()
432 int ntfs_remove_cache(struct CACHE_HEADER *cache, in ntfs_remove_cache() argument
438 if (cache) { in ntfs_remove_cache()
439 if (cache->dohash) in ntfs_remove_cache()
440 drophashindex(cache,item,cache->dohash(item)); in ntfs_remove_cache()
441 do_invalidate(cache,item,flags); in ntfs_remove_cache()
448 * Free memory allocated to a cache
451 static void ntfs_free_cache(struct CACHE_HEADER *cache) in ntfs_free_cache() argument
453 struct CACHED_GENERIC *entry; in ntfs_free_cache() local
455 if (cache) { in ntfs_free_cache()
456 for (entry=cache->most_recent_entry; entry; entry=entry->next) { in ntfs_free_cache()
457 if (cache->dofree) in ntfs_free_cache()
458 cache->dofree(entry); in ntfs_free_cache()
459 if (entry->variable) in ntfs_free_cache()
460 free(entry->variable); in ntfs_free_cache()
462 free(cache); in ntfs_free_cache()
467 * Create a cache
469 * Returns the cache header, or NULL if the cache could not be created
477 struct CACHE_HEADER *cache; in ntfs_create_cache() local
490 cache = (struct CACHE_HEADER*)ntfs_malloc(size); in ntfs_create_cache()
491 if (cache) { in ntfs_create_cache()
493 cache->name = name; in ntfs_create_cache()
494 cache->dofree = dofree; in ntfs_create_cache()
496 cache->dohash = dohash; in ntfs_create_cache()
497 cache->max_hash = max_hash; in ntfs_create_cache()
499 cache->dohash = (cache_hash)NULL; in ntfs_create_cache()
500 cache->max_hash = 0; in ntfs_create_cache()
502 cache->fixed_size = full_item_size - sizeof(struct CACHED_GENERIC); in ntfs_create_cache()
503 cache->reads = 0; in ntfs_create_cache()
504 cache->writes = 0; in ntfs_create_cache()
505 cache->hits = 0; in ntfs_create_cache()
506 /* chain the data entries, and mark an invalid entry */ in ntfs_create_cache()
507 cache->most_recent_entry = (struct CACHED_GENERIC*)NULL; in ntfs_create_cache()
508 cache->oldest_entry = (struct CACHED_GENERIC*)NULL; in ntfs_create_cache()
509 cache->free_entry = &cache->entry[0]; in ntfs_create_cache()
510 pc = &cache->entry[0]; in ntfs_create_cache()
511 for (i=0; i<(item_count - 1); i++) { in ntfs_create_cache()
514 pc->next = qc; in ntfs_create_cache()
515 pc->variable = (void*)NULL; in ntfs_create_cache()
516 pc->varsize = 0; in ntfs_create_cache()
519 /* special for the last entry */ in ntfs_create_cache()
520 pc->next = (struct CACHED_GENERIC*)NULL; in ntfs_create_cache()
521 pc->variable = (void*)NULL; in ntfs_create_cache()
522 pc->varsize = 0; in ntfs_create_cache()
527 cache->free_hash = ph; in ntfs_create_cache()
528 for (i=0; i<(item_count - 1); i++) { in ntfs_create_cache()
530 ph->next = qh; in ntfs_create_cache()
533 /* special for the last entry */ in ntfs_create_cache()
535 ph->next = (struct HASH_ENTRY*)NULL; in ntfs_create_cache()
539 cache->first_hash = px; in ntfs_create_cache()
543 cache->free_hash = (struct HASH_ENTRY*)NULL; in ntfs_create_cache()
544 cache->first_hash = (struct HASH_ENTRY**)NULL; in ntfs_create_cache()
547 return (cache); in ntfs_create_cache()
560 /* inode cache */ in ntfs_create_lru_caches()
561 vol->xinode_cache = ntfs_create_cache("inode",(cache_free)NULL, in ntfs_create_lru_caches()
566 /* idata cache */ in ntfs_create_lru_caches()
567 vol->nidata_cache = ntfs_create_cache("nidata", in ntfs_create_lru_caches()
573 /* lookup cache */ in ntfs_create_lru_caches()
574 vol->lookup_cache = ntfs_create_cache("lookup", in ntfs_create_lru_caches()
579 vol->securid_cache = ntfs_create_cache("securid",(cache_free)NULL, in ntfs_create_lru_caches()
582 vol->legacy_cache = ntfs_create_cache("legacy",(cache_free)NULL, in ntfs_create_lru_caches()
594 ntfs_free_cache(vol->xinode_cache); in ntfs_free_lru_caches()
597 ntfs_free_cache(vol->nidata_cache); in ntfs_free_lru_caches()
600 ntfs_free_cache(vol->lookup_cache); in ntfs_free_lru_caches()
602 ntfs_free_cache(vol->securid_cache); in ntfs_free_lru_caches()
604 ntfs_free_cache(vol->legacy_cache); in ntfs_free_lru_caches()