/*
 *   (C) Copyright IBM Corp. 2002, 2003
 *
 *   This program 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 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;  if not, write to the Free Software
 *   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 *
 * Device-Manager cache
 *
 * This file implements a very simple read cache for the Local Disk Manager.
 * It does not do fancy block alignment and read ahead. It just stores the
 * sectors read from disk into a hash table using the sector number as a
 * hash key. There is no effort done to manage updates to sectors that
 * could span multiple cache entries. Anyone is welcome to beef up the
 * sophitication of the caching. Right now, all that is needed is a place
 * to store sectors that were read during discovery so that they don't get
 * read from the disk multiple times.
 */

#define _GNU_SOURCE

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <fcntl.h>
#include <unistd.h>
#include <errno.h>

#include <plugin.h>
#include "localdskmgr.h"
#include "cache.h"

static u_int64_t cache_hit_count = 0;
static u_int64_t cache_miss_count = 0;

/**
 * struct cache_entry
 *
 * Structure to hold information about a cache
 ***/
typedef struct cache_entry_s {
	storage_object_t	* disk;
	lsn_t			sector;
	sector_count_t		count;
	void			* buffer;
	struct cache_entry_s	* prev;
	struct cache_entry_s	* next;
} cache_entry_t;

/* Macros for list manipulation */

/* Insert item1 before item2. */
#define list_insert_before(item1, item2)	\
{						\
	(item1)->prev = (item2)->prev;		\
	(item2)->prev->next = (item1);		\
	(item2)->prev = (item1);		\
	(item1)->next = (item2);		\
}

/* Insert item1 after item2. */
#define list_insert_after(item1, item2)		\
{						\
	(item1)->next = (item2)->next;		\
	(item2)->next->prev = (item1);		\
	(item2)->next = (item1);		\
	(item1)->prev = (item2);		\
}

/* Delete item from the list. */
#define list_delete(item)			\
{						\
	(item)->next->prev = (item)->prev;	\
	(item)->prev->next = (item)->next;	\
	(item)->prev = NULL;			\
	(item)->next = NULL;			\
}

/*
 * The hash table size should be prime number.  A prime number promotes
 * a more even distribution of entries in the hash table.
 * Other "prime" candidates that are near a power of 10 or power of 2:
 * 127, 257, 499, 503, 509, 521, 997, 1009, 1021, 1031
 */
#define HASH_TABLE_SIZE 521   
#define HASH_INDEX_BITS 9
#define HASH_INDEX_MASK ((1 << HASH_INDEX_BITS) - 1)
#define HASH_INDEX(sector) (hash_value(sector) & HASH_INDEX_MASK)

static cache_entry_t * hash_table = NULL;

/**
 * initialize_cache
 *
 * Initialize the cache if it hasn't been started already.
 **/
int initialize_cache(void)
{
	int i, rc = 0;

	LOG_ENTRY();

	if (hash_table) {
		/* Cache is already initialized. */
		goto out;
	}

	hash_table = calloc(HASH_TABLE_SIZE, sizeof(cache_entry_t));
        if (!hash_table) {
		rc = ENOMEM;
		goto out;
        }

	for (i = 0; i < HASH_TABLE_SIZE; i++) {
		hash_table[i].prev = &hash_table[i];
		hash_table[i].next = &hash_table[i];
	}

out:
	LOG_EXIT_INT(rc);
	return rc;
}

/**
 * hash_value
 *
 * Hash value computer. Modeled after ElfHash().
 **/
static u_int32_t hash_value(lsn_t sector)
{
	u_int32_t h = 0;
	u_int32_t g;
	int i;
	u_char * pByte = (u_char *)&sector;

	for (i = 0; i < sizeof(sector); i++) {
		h = (h << 4) + pByte[i];
		g = h & 0xF0000000;

		if (g != 0) {
			h ^= g >> 24;
		}

		h &= ~g;
	}

	return h;
}

/**
 * read_from_cache
 *
 * Read sectors from the cache, if they exist in the cache.
 * Else, return ENOENT.
 **/
int read_from_cache(storage_object_t * disk,
                    lsn_t sector,
                    sector_count_t count,
                    void * buffer)
{
	int rc = ENOENT;
	cache_entry_t * hash_entry = &hash_table[HASH_INDEX(sector)];
	cache_entry_t * cache_entry;

	LOG_ENTRY();

	if (hash_table == NULL) {
		goto out;
	}

	cache_entry = hash_entry->next;
	while (cache_entry != hash_entry &&
	       (cache_entry->disk != disk ||
	        cache_entry->sector != sector ||
	        cache_entry->count < count)) {
		cache_entry = cache_entry->next;
	}

	if (cache_entry == hash_entry) {
		cache_miss_count++;
		goto out;
	}

	LOG_DEBUG("Read from cache.  disk %s, sector %"PRIu64", count %"PRIu64".\n",
		  disk->name, sector, count);
	memcpy(buffer, cache_entry->buffer, count << EVMS_VSECTOR_SIZE_SHIFT);
	cache_hit_count++;
	rc = 0;

out:
	LOG_EXIT_INT(rc);
	return rc;
}

/**
 * write_to_cache
 *
 * Put an entry in the cache.
 * Return:
 *   ENOENT if the cache is disabled
 *   EXIST  if the entry is already in the cache
 *   ENOMEM if there is an error allocating memory for the cache entry
 **/
int write_to_cache(storage_object_t * disk,
		   lsn_t sector,
		   sector_count_t count,
		   void * buffer)
{
	cache_entry_t * cache_entry;
	cache_entry_t * hash_entry = &hash_table[HASH_INDEX(sector)];
	int rc = ENOENT;

	LOG_ENTRY();

	if (hash_table == NULL) {
		goto out;
	}

	cache_entry = hash_entry->next;
	while (cache_entry != hash_entry &&
	       (cache_entry->disk != disk ||
	        cache_entry->sector != sector)) {
		cache_entry = cache_entry->next;
	}

	if (cache_entry != hash_entry) {
		/* Found a cache entry. */
		if (cache_entry->count >= count) {
			LOG_DEBUG("Cache entry already exists for disk %s, sector %"PRIu64".\n",
				  disk->name, sector);
			rc = EEXIST;
			goto out;
		}

		LOG_DEBUG("Cache entry for disk %s, sector %"PRIu64" is too small.\n",
			  disk->name, sector);
		LOG_DEBUG("   Has %"PRIu64" sectors; need %"PRIu64" sectors.\n",
			  cache_entry->count, count);
		free(cache_entry->buffer);
		cache_entry->buffer = NULL;
		cache_entry->count = 0;
	} else {
		/* Need a new cache entry. */
		LOG_DEBUG("Create a new cache entry for disk %s, sector %"PRIu64", count %"PRIu64".\n",
			  disk->name, sector, count);
		cache_entry = calloc(1, sizeof(cache_entry_t));
		if (!cache_entry) {
			LOG_SERIOUS("Could not allocate memory for a new cache entry.\n");
			rc = ENOMEM;	
			goto out;
		}

		cache_entry->disk = disk;
		cache_entry->sector = sector;
	}

	if (cache_entry->buffer == NULL) {
		LOG_DEBUG("Allocate a new buffer for the cache entry for disk %s, sector %"PRIu64", count %"PRIu64".\n",
			  disk->name, sector, count);
		cache_entry->buffer = malloc(count << EVMS_VSECTOR_SIZE_SHIFT);
		if (!cache_entry->buffer) {
			LOG_SERIOUS("Could not allocate memory for a buffer for a cache entry for disk %s, sector %"PRIu64", count %"PRIu64".\n",
				    disk->name, sector, count);
			if (cache_entry->prev) {
				list_delete(cache_entry);
			}
			free(cache_entry);
			rc = ENOMEM;
			goto out;
		}

		cache_entry->count = count;
	}

	memcpy(cache_entry->buffer, buffer, count << EVMS_VSECTOR_SIZE_SHIFT);

	if (cache_entry->prev == NULL) {
		list_insert_before(cache_entry, hash_entry);
	}
	rc = 0;

out:
	LOG_EXIT_INT(rc);
	return rc;
}


/**
 * purge_cache
 *
 * Delete all entries in the cache, but leave the cache active.
 **/
void purge_cache(void)
{
	int i;
	cache_entry_t * cache_entry;

	LOG_ENTRY();

	LOG_DEBUG("Purge cache.\n");
	if (hash_table) {
		for (i = 0; i < HASH_TABLE_SIZE; i++) {
			while (hash_table[i].next != &hash_table[i]) {
				cache_entry = hash_table[i].next;
				free(cache_entry->buffer);
				list_delete(cache_entry);
				free(cache_entry);
			}
		}

		LOG_DEBUG("Cache hit count:   %"PRIu64"\n", cache_hit_count);
		LOG_DEBUG("Cache miss count:  %"PRIu64"\n", cache_miss_count);
		cache_hit_count = 0;
		cache_miss_count = 0;
	}

	LOG_EXIT_VOID();
}


/**
 * destroy_cache
 *
 * Delete all entries in the cache and disable the cache.
 **/
void destroy_cache(void)
{
	LOG_ENTRY();

	LOG_DEBUG("Destroy cache.\n");
	if (hash_table) {
		purge_cache();
		free(hash_table);
		hash_table = NULL;
	}

	LOG_EXIT_VOID();
}