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