libntfs-3g/cache.c

/**
 * cache.c : deal with LRU caches
 *
 * Copyright (c) 2008-2010 Jean-Pierre Andre
 *
 * This program/include file is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as published
 * by the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program/include file is distributed in the hope that it will be
 * useful, but WITHOUT ANY WARRANTY; without even the implied warranty
 * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program (in the main directory of the NTFS-3G
 * distribution in the file COPYING); if not, write to the Free Software
 * Foundation,Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#ifdef HAVE_STDLIB_H
#include <stdlib.h>
#endif
#ifdef HAVE_STRING_H
#include <string.h>
#endif

#include "types.h"
#include "security.h"
#include "cache.h"
#include "misc.h"
#include "logging.h"

/*
 *		General functions to deal with LRU caches
 *
 *	The cached data have to be organized in a structure in which
 *	the first fields must follow a mandatory pattern and further
 *	fields may contain any fixed size data. They are stored in an
 *	LRU list.
 *
 *	A compare function must be provided for finding a wanted entry
 *	in the cache. Another function may be provided for invalidating
 *	an entry to facilitate multiple invalidation.
 *
 *	These functions never return error codes. When there is a
 *	shortage of memory, data is simply not cached.
 *	When there is a hashing bug, hashing is dropped, and sequential
 *	searches are used.
 */

/*
 *		Enter a new hash index, after a new record has been inserted
 *
 *	Do not call when a record has been modified (with no key change)
 */

static void inserthashindex(struct CACHE_HEADER *cache,
			struct CACHED_GENERIC *current)
{
	int h;
	struct HASH_ENTRY *link;
	struct HASH_ENTRY *first;

	if (cache->dohash) {
		h = cache->dohash(current);
		if ((h >= 0) && (h < cache->max_hash)) {
			/* get a free link and insert at top of hash list */
			link = cache->free_hash;
			if (link) {
				cache->free_hash = link->next;
				first = cache->first_hash[h];
				if (first)
					link->next = first;
				else
					link->next = NULL;
				link->entry = current;
				cache->first_hash[h] = link;
			} else {
				ntfs_log_error("No more hash entries,"
						" cache %s hashing dropped\n",
						cache->name);
				cache->dohash = (cache_hash)NULL;
			}
		} else {
			ntfs_log_error("Illegal hash value,"
						" cache %s hashing dropped\n",
						cache->name);
			cache->dohash = (cache_hash)NULL;
		}
	}
}

/*
 *		Drop a hash index when a record is about to be deleted
 */

static void drophashindex(struct CACHE_HEADER *cache,
			const struct CACHED_GENERIC *current, int hash)
{
	struct HASH_ENTRY *link;
	struct HASH_ENTRY *previous;

	if (cache->dohash) {
		if ((hash >= 0) && (hash < cache->max_hash)) {
			/* find the link and unlink */
			link = cache->first_hash[hash];
			previous = (struct HASH_ENTRY*)NULL;
			while (link && (link->entry != current)) {
				previous = link;
				link = link->next;
			}
			if (link) {
				if (previous)
					previous->next = link->next;
				else
					cache->first_hash[hash] = link->next;
				link->next = cache->free_hash;
				cache->free_hash = link;
			} else {
				ntfs_log_error("Bad hash list,"
						" cache %s hashing dropped\n",
						cache->name);
				cache->dohash = (cache_hash)NULL;
			}
		} else {
			ntfs_log_error("Illegal hash value,"
					" cache %s hashing dropped\n",
					cache->name);
			cache->dohash = (cache_hash)NULL;
		}
	}
}

/*
 *		Fetch an entry from cache
 *
 *	returns the cache entry, or NULL if not available
 *	The returned entry may be modified, but not freed
 */

struct CACHED_GENERIC *ntfs_fetch_cache(struct CACHE_HEADER *cache,
		const struct CACHED_GENERIC *wanted, cache_compare compare)
{
	struct CACHED_GENERIC *current;
	struct CACHED_GENERIC *previous;
	struct HASH_ENTRY *link;
	int h;

	current = (struct CACHED_GENERIC*)NULL;
	if (cache) {
		if (cache->dohash) {
			/*
			 * When possible, use the hash table to
			 * locate the entry if present
			 */
			h = cache->dohash(wanted);
		        link = cache->first_hash[h];
			while (link && compare(link->entry, wanted))
				link = link->next;
			if (link)
				current = link->entry;
		}
		if (!cache->dohash) {
			/*
			 * Search sequentially in LRU list if no hash table
			 * or if hashing has just failed
			 */
			current = cache->most_recent_entry;
			while (current
				   && compare(current, wanted)) {
				current = current->next;
				}
		}
		if (current) {
			previous = current->previous;
			cache->hits++;
			if (previous) {
			/*
			 * found and not at head of list, unlink from current
			 * position and relink as head of list
			 */
				previous->next = current->next;
				if (current->next)
					current->next->previous
						= current->previous;
				else
					cache->oldest_entry
						= current->previous;
				current->next = cache->most_recent_entry;
				current->previous
						= (struct CACHED_GENERIC*)NULL;
				cache->most_recent_entry->previous = current;
				cache->most_recent_entry = current;
			}
		}
		cache->reads++;
	}
	return (current);
}

/*
 *		Enter an inode number into cache
 *	returns the cache entry or NULL if not possible
 */

struct CACHED_GENERIC *ntfs_enter_cache(struct CACHE_HEADER *cache,
			const struct CACHED_GENERIC *item,
			cache_compare compare)
{
	struct CACHED_GENERIC *current;
	struct CACHED_GENERIC *before;
	struct HASH_ENTRY *link;
	int h;

	current = (struct CACHED_GENERIC*)NULL;
	if (cache) {
		if (cache->dohash) {
			/*
			 * When possible, use the hash table to
			 * find out whether the entry if present
			 */
			h = cache->dohash(item);
		        link = cache->first_hash[h];
			while (link && compare(link->entry, item))
				link = link->next;
			if (link) {
				current = link->entry;
			}
		}
		if (!cache->dohash) {
			/*
			 * Search sequentially in LRU list to locate the end,
			 * and find out whether the entry is already in list
			 * As we normally go to the end, no statistics is
			 * kept.
		 	 */
			current = cache->most_recent_entry;
			while (current
			   && compare(current, item)) {
				current = current->next;
				}
		}

		if (!current) {
			/*
			 * Not in list, get a free entry or reuse the
			 * last entry, and relink as head of list
			 * Note : we assume at least three entries, so
			 * before, previous and first are different when
			 * an entry is reused.
			 */

			if (cache->free_entry) {
				current = cache->free_entry;
				cache->free_entry = cache->free_entry->next;
				if (item->varsize) {
					current->variable = ntfs_malloc(
						item->varsize);
				} else
					current->variable = (void*)NULL;
				current->varsize = item->varsize;
				if (!cache->oldest_entry)
					cache->oldest_entry = current;
			} else {
				/* reusing the oldest entry */
				current = cache->oldest_entry;
				before = current->previous;
				before->next = (struct CACHED_GENERIC*)NULL;
				if (cache->dohash)
					drophashindex(cache,current,
						cache->dohash(current));
				if (cache->dofree)
					cache->dofree(current);
				cache->oldest_entry = current->previous;
				if (item->varsize) {
					if (current->varsize)
						current->variable = realloc(
							current->variable,
							item->varsize);
					else
						current->variable = ntfs_malloc(
							item->varsize);
				} else {
					if (current->varsize)
						free(current->variable);
					current->variable = (void*)NULL;
				}
				current->varsize = item->varsize;
			}
			current->next = cache->most_recent_entry;
			current->previous = (struct CACHED_GENERIC*)NULL;
			if (cache->most_recent_entry)
				cache->most_recent_entry->previous = current;
			cache->most_recent_entry = current;
			memcpy(current->payload, item->payload, cache->fixed_size);
			if (item->varsize) {
				if (current->variable) {
					memcpy(current->variable,
						item->variable, item->varsize);
				} else {
					/*
					 * no more memory for variable part
					 * recycle entry in free list
					 * not an error, just uncacheable
					 */
					cache->most_recent_entry = current->next;
					current->next = cache->free_entry;
					cache->free_entry = current;
					current = (struct CACHED_GENERIC*)NULL;
				}
			} else {
				current->variable = (void*)NULL;
				current->varsize = 0;
			}
			if (cache->dohash && current)
				inserthashindex(cache,current);
		}
		cache->writes++;
	}
	return (current);
}

/*
 *		Invalidate a cache entry
 *	The entry is moved to the free entry list
 *	A specific function may be called for entry deletion
 */

static void do_invalidate(struct CACHE_HEADER *cache,
		struct CACHED_GENERIC *current, int flags)
{
	struct CACHED_GENERIC *previous;

	previous = current->previous;
	if ((flags & CACHE_FREE) && cache->dofree)
		cache->dofree(current);
	/*
	 * Relink into free list
	 */
	if (current->next)
		current->next->previous = current->previous;
	else
		cache->oldest_entry = current->previous;
	if (previous)
		previous->next = current->next;
	else
		cache->most_recent_entry = current->next;
	current->next = cache->free_entry;
	cache->free_entry = current;
	if (current->variable)
		free(current->variable);
	current->varsize = 0;
   }


/*
 *		Invalidate entries in cache
 *
 *	Several entries may have to be invalidated (at least for inodes
 *	associated to directories which have been renamed), a different
 *	compare function may be provided to select entries to invalidate
 *
 *	Returns the number of deleted entries, this can be used by
 *	the caller to signal a cache corruption if the entry was
 *	supposed to be found.
 */

int ntfs_invalidate_cache(struct CACHE_HEADER *cache,
		const struct CACHED_GENERIC *item, cache_compare compare,
		int flags)
{
	struct CACHED_GENERIC *current;
	struct CACHED_GENERIC *next;
	struct HASH_ENTRY *link;
	int count;
	int h;

	current = (struct CACHED_GENERIC*)NULL;
	count = 0;
	if (cache) {
		if (!(flags & CACHE_NOHASH) && cache->dohash) {
			/*
			 * When possible, use the hash table to
			 * find out whether the entry if present
			 */
			h = cache->dohash(item);
		        link = cache->first_hash[h];
			while (link) {
				if (compare(link->entry, item))
					link = link->next;
				else {
					current = link->entry;
					link = link->next;
					if (current) {
						drophashindex(cache,current,h);
						do_invalidate(cache,
							current,flags);
						count++;
					}
				}
			}
		}
		if ((flags & CACHE_NOHASH) || !cache->dohash) {
				/*
				 * Search sequentially in LRU list
				 */
			current = cache->most_recent_entry;
			while (current) {
				if (!compare(current, item)) {
					next = current->next;
					if (cache->dohash)
						drophashindex(cache,current,
						    cache->dohash(current));
					do_invalidate(cache,current,flags);
					current = next;
					count++;
				} else {
					current = current->next;
				}
			}
		}
	}
	return (count);
}

int ntfs_remove_cache(struct CACHE_HEADER *cache,
		struct CACHED_GENERIC *item, int flags)
{
	int count;

	count = 0;
	if (cache) {
		if (cache->dohash)
			drophashindex(cache,item,cache->dohash(item));
		do_invalidate(cache,item,flags);
		count++;
	}
	return (count);
}

/*
 *		Free memory allocated to a cache
 */

static void ntfs_free_cache(struct CACHE_HEADER *cache)
{
	struct CACHED_GENERIC *entry;

	if (cache) {
		for (entry=cache->most_recent_entry; entry; entry=entry->next) {
			if (cache->dofree)
				cache->dofree(entry);
			if (entry->variable)
				free(entry->variable);
		}
		free(cache);
	}
}

/*
 *		Create a cache
 *
 *	Returns the cache header, or NULL if the cache could not be created
 */

static struct CACHE_HEADER *ntfs_create_cache(const char *name,
			cache_free dofree, cache_hash dohash,
			int full_item_size,
			int item_count, int max_hash)
{
	struct CACHE_HEADER *cache;
	struct CACHED_GENERIC *pc;
	struct CACHED_GENERIC *qc;
	struct HASH_ENTRY *ph;
	struct HASH_ENTRY *qh;
	struct HASH_ENTRY **px;
	size_t size;
	int i;

	size = sizeof(struct CACHE_HEADER) + item_count*full_item_size;
	if (max_hash)
		size += item_count*sizeof(struct HASH_ENTRY)
			 + max_hash*sizeof(struct HASH_ENTRY*);
	cache = (struct CACHE_HEADER*)ntfs_malloc(size);
	if (cache) {
				/* header */
		cache->name = name;
		cache->dofree = dofree;
		if (dohash && max_hash) {
			cache->dohash = dohash;
			cache->max_hash = max_hash;
		} else {
			cache->dohash = (cache_hash)NULL;
			cache->max_hash = 0;
		}
		cache->fixed_size = full_item_size - sizeof(struct CACHED_GENERIC);
		cache->reads = 0;
		cache->writes = 0;
		cache->hits = 0;
		/* chain the data entries, and mark an invalid entry */
		cache->most_recent_entry = (struct CACHED_GENERIC*)NULL;
		cache->oldest_entry = (struct CACHED_GENERIC*)NULL;
		cache->free_entry = &cache->entry[0];
		pc = &cache->entry[0];
		for (i=0; i<(item_count - 1); i++) {
			qc = (struct CACHED_GENERIC*)((char*)pc
							 + full_item_size);
			pc->next = qc;
			pc->variable = (void*)NULL;
			pc->varsize = 0;
			pc = qc;
		}
			/* special for the last entry */
		pc->next =  (struct CACHED_GENERIC*)NULL;
		pc->variable = (void*)NULL;
		pc->varsize = 0;

		if (max_hash) {
				/* chain the hash entries */
			ph = (struct HASH_ENTRY*)(((char*)pc) + full_item_size);
			cache->free_hash = ph;
			for (i=0; i<(item_count - 1); i++) {
				qh = &ph[1];
				ph->next = qh;
				ph = qh;
			}
				/* special for the last entry */
			if (item_count) {
				ph->next =  (struct HASH_ENTRY*)NULL;
			}
				/* create and initialize the hash indexes */
			px = (struct HASH_ENTRY**)&ph[1];
			cache->first_hash = px;
			for (i=0; i<max_hash; i++)
				px[i] = (struct HASH_ENTRY*)NULL;
		} else {
			cache->free_hash = (struct HASH_ENTRY*)NULL;
			cache->first_hash = (struct HASH_ENTRY**)NULL;
		}
	}
	return (cache);
}

/*
 *		Create all LRU caches
 *
 *	No error return, if creation is not possible, cacheing will
 *	just be not available
 */

void ntfs_create_lru_caches(ntfs_volume *vol)
{
#if CACHE_INODE_SIZE
		 /* inode cache */
	vol->xinode_cache = ntfs_create_cache("inode",(cache_free)NULL,
		ntfs_dir_inode_hash, sizeof(struct CACHED_INODE),
		CACHE_INODE_SIZE, 2*CACHE_INODE_SIZE);
#endif
#if CACHE_NIDATA_SIZE
		 /* idata cache */
	vol->nidata_cache = ntfs_create_cache("nidata",
		ntfs_inode_nidata_free, ntfs_inode_nidata_hash,
		sizeof(struct CACHED_NIDATA),
		CACHE_NIDATA_SIZE, 2*CACHE_NIDATA_SIZE);
#endif
#if CACHE_LOOKUP_SIZE
		 /* lookup cache */
	vol->lookup_cache = ntfs_create_cache("lookup",
		(cache_free)NULL, ntfs_dir_lookup_hash,
		sizeof(struct CACHED_LOOKUP),
		CACHE_LOOKUP_SIZE, 2*CACHE_LOOKUP_SIZE);
#endif
	vol->securid_cache = ntfs_create_cache("securid",(cache_free)NULL,
		(cache_hash)NULL,sizeof(struct CACHED_SECURID), CACHE_SECURID_SIZE, 0);
#if CACHE_LEGACY_SIZE
	vol->legacy_cache = ntfs_create_cache("legacy",(cache_free)NULL,
		(cache_hash)NULL, sizeof(struct CACHED_PERMISSIONS_LEGACY), CACHE_LEGACY_SIZE, 0);
#endif
}

/*
 *		Free all LRU caches
 */

void ntfs_free_lru_caches(ntfs_volume *vol)
{
#if CACHE_INODE_SIZE
	ntfs_free_cache(vol->xinode_cache);
#endif
#if CACHE_NIDATA_SIZE
	ntfs_free_cache(vol->nidata_cache);
#endif
#if CACHE_LOOKUP_SIZE
	ntfs_free_cache(vol->lookup_cache);
#endif
	ntfs_free_cache(vol->securid_cache);
#if CACHE_LEGACY_SIZE
	ntfs_free_cache(vol->legacy_cache);
#endif
}