/*
 * cache.c - block cache with red-black trees
 * Copyright (C) 2006 Thorsten Zitterell <thorsten@zitterell.de>
 */

#include <linux/module.h>
#include <linux/types.h>
#include <linux/highmem.h>
#include <linux/fs.h>
#include <linux/file.h>
/* use red-black library of kernel */
#include <linux/rbtree.h>
#include <linux/version.h>
#include <asm/uaccess.h>

#include "../common/dnbd-cliserv.h"
#include "cache.h"

/* empty node */
#define rb_entry_cn(node)	rb_entry((node), struct cache_node, rb_node)

/* dummy operations of no cache is used */
int dnbd_cache_dummy_search(dnbd_cache_t * cache, struct request *req)
{
	return 0;
}

int dnbd_cache_dummy_insert(dnbd_cache_t * cache, sector_t block,
			    void *buf)
{
	return 0;
}

void dnbd_cache_dummy_clean(dnbd_cache_t * cache)
{
	return;
}

int dnbd_cache_search(dnbd_cache_t * cache, struct request *req)
{
	/* hold segment as we copy from user space */
	mm_segment_t old_fs = get_fs();
	size_t blksize;
	void *kaddr;

	#if (LINUX_VERSION_CODE < KERNEL_VERSION(2,6,24))
		int i;
		struct bio *bio;
	#else
		struct req_iterator iter;
	#endif
	struct bio_vec *bvec;

	int result = 0, rbytes;
	struct rb_node *n;
	struct cache_node *cn;
	loff_t offset;
	char *buf;

	down(&cache->sema);
	n = cache->root.rb_node;
	blksize = cache->blksize;

	/* search for block */
	while (n) {
		cn = rb_entry_cn(n);

		if (req->sector < cn->rb_key)
			n = n->rb_left;
		else if (req->sector > cn->rb_key)
			n = n->rb_right;
		else
			goto found;
	}
	/* block is not cached */
	cache->miss++;
	goto out;

	/* cached block was found */
      found:
	cache->hits++;
	offset = cn->rb_data * blksize;
	#if (LINUX_VERSION_CODE < KERNEL_VERSION(2,6,24))
	rq_for_each_bio(bio, req) {
		bio_for_each_segment(bvec, bio, i) {
	#else
	rq_for_each_segment(bvec, req, iter) {
	#endif
			if (bvec->bv_len > blksize) {
				printk(KERN_WARNING
				       "bvec->bv_len greater than cache block size\n");
				goto out;
			}
			/* copy cached block from cache file */
			set_fs(get_ds());
			buf = req->buffer;
			kaddr = kmap(bvec->bv_page);
			rbytes =
			    vfs_read(cache->filp, kaddr + bvec->bv_offset,
				     bvec->bv_len, &offset);
			kunmap(bvec->bv_page);
			set_fs(old_fs);

			/* error on reading? */
			if (rbytes != bio_iovec(req->bio)->bv_len) {
				printk
				    ("dnbd: ERROR reading from cache!\n");
				result = 0;
				goto out;
			}

			result += rbytes;
			if (result == blksize)
				goto out;
	#if (LINUX_VERSION_CODE < KERNEL_VERSION(2,6,24))
		}
	#endif
	}

      out:
	up(&cache->sema);

	/* return number of copied sectors */
	return result >> 9;
}

int dnbd_cache_insert(dnbd_cache_t * cache, sector_t sector, void *buf)
{
	mm_segment_t old_fs = get_fs();
	int result = 0;
	struct rb_node **p;
	struct rb_node *parent = NULL;
	cache_node_t *__cn, *cn;
	sector_t act_block;

	loff_t offset;

	down(&cache->sema);
	p = &cache->root.rb_node;

	/* red-black tree search and replacement in O(log n) */
	
	/* check if node was already inserted to cache and,
	   if necessary, do LRU replacement */
	
	while (*p) {
		parent = *p;
		__cn = rb_entry_cn(parent);
		if (sector < __cn->rb_key)
			p = &(*p)->rb_left;
		else if (sector > __cn->rb_key)
			p = &(*p)->rb_right;
		else {
			/* the sector was already added to cache */

			/* LRU replacement policy */
			if (__cn->prev)
				__cn->prev->next = __cn->next;
			else
				/* __cn is head - do nothing */
				goto no_lru;

			if (__cn->next)
				__cn->next->prev = __cn->prev;
			else
				/* __cn is tail - so set new one */
				cache->tail =
				    (__cn->prev ? __cn->prev : __cn);

			/* insert new node to head:
			   head of list has no predecessor, 
			   set previous node to NULL and next 
			   node to old head and set new head */

			__cn->prev = NULL;
			__cn->next = cache->head;

			if (cache->head)
				cache->head->prev = __cn;

			cache->head = __cn;

			cache->lru++;
		      no_lru:
			result = 1;
			goto out;
		}
	}

	/* check if cache is full */
	if (cache->used_blocks == cache->max_blocks) {
		/* 
		   remove LRU node (cn), but keep reserved 
		   data structure in memory 
		*/
		cn = cache->tail;
		cache->tail->prev->next = NULL;
		cache->tail = cache->tail->prev;

		/*
		   Node (which is tail of LRU list) will be erased from tree 
		   which is then rebalanced. 
		   Re-finding a parent for the a node is mandatory.
		 */
		act_block = cn->rb_data;
		rb_erase(&cn->rb_node, &cache->root);
		p = &cache->root.rb_node;
		while (*p) {
			parent = *p;
			__cn = rb_entry_cn(parent);
			if (sector < __cn->rb_key)
				p = &(*p)->rb_left;
			else
				p = &(*p)->rb_right;
		}
	} else {
		/* cache is not full, so reserve memory for red-black tree node */
		if (!
		    (cn =
		     (cache_node_t *) kmalloc(sizeof(cache_node_t),
					      GFP_KERNEL))) {
			result = -ENOMEM;
			goto out;
		}
		act_block = cache->used_blocks;
		/* cn = &cache->nodes[act_block]; */
		cache->used_blocks++;
	}
	
	/* write block to cache file */	
	offset = act_block * cache->blksize;
	set_fs(get_ds());
	result = vfs_write(cache->filp, buf, cache->blksize, &offset);
	set_fs(old_fs);

	if (result != cache->blksize) {
		printk("dnbd: ERROR writing to cache!\n");
		cache->used_blocks--;
		kfree(cn);
		goto out;
	}
	
	/* cn (current node) points to an empty node, now */
	cn->rb_key = sector;
	cn->rb_data = act_block;

	/* current node (which will become the new head) has no predecessor */
	cn->prev = NULL;
	cn->next = cache->head;

	/* adapt head element - if it exists */
	if (cache->head)
		cache->head->prev = cn;

	/* set new head */
	cache->head = cn;

	/* set new tail */
	if (!cache->tail)
		cache->tail = cn;

	/* call kernel helpers for red-black trees */
	rb_link_node(&cn->rb_node, parent, p);
	rb_insert_color(&cn->rb_node, &cache->root);

      out:
	up(&cache->sema);
	return result;
}

int dnbd_cache_init(dnbd_cache_t * cache)
{
	int result = -EINVAL;

	/* initialize cache */
	cache->active = 0;
	
	/* set dummy function, if no cache is used */
	cache->insert = &dnbd_cache_dummy_insert;
	cache->search = &dnbd_cache_dummy_search;
	cache->clean = &dnbd_cache_dummy_clean;

	cache->root.rb_node = NULL;

	cache->max_blocks = 0;
	cache->used_blocks = 0;
	cache->blksize = 0;

	cache->hits = 0;
	cache->miss = 0;
	cache->lru = 0;

	cache->filp = NULL;
	cache->fname = NULL;

	cache->head = NULL;
	cache->tail = NULL;
	spin_lock_init(&cache->lock);
	init_MUTEX(&cache->sema);

	result = 0;
	return result;
}

void dnbd_cache_clean(dnbd_cache_t * cache)
{
	cache_node_t *node;
	cache_node_t *tmp;
	int cnt = 0;

	spin_lock(&cache->lock);
	node = cache->head;

	cache->head = NULL;
	cache->tail = NULL;

	if (cache->fname)
		kfree(cache->fname);

	/* free memory of all nodes; start with head */
	while (node) {
		tmp = node;
		node = node->next;
		kfree(tmp);
		cnt++;
	}
	printk(KERN_INFO "dnbd: freed %i cache nodes\n", cnt);

	cache->active = 0;
	spin_unlock(&cache->lock);

}

int dnbd_cache_set(dnbd_cache_t * cache, struct dnbd_file __user * arg,
		   size_t blksize)
{
	int result = -EINVAL;
	struct dnbd_file cfile;
	struct kstat stat;
	loff_t div1;
	size_t div2;

	if (cache->active) {
		printk(KERN_ERR "dnbd: cachefile is already set!\n");
		return -EFAULT;
	}

	/* open, verify and set cache file */
	if (copy_from_user(&cfile, arg, sizeof(cfile)))
		return -EFAULT;

	if (!(cache->fname = (char *) kmalloc(cfile.len + 1, GFP_KERNEL)))
		return -ENOMEM;

	if (copy_from_user
	    (cache->fname, (void __user *) cfile.name, cfile.len)) {
		result = -EFAULT;
		goto out_free;
	}
	*(cache->fname + cfile.len) = 0;

	printk(KERN_INFO "dnbd: setting cachefile to %s\n", cache->fname);

	cache->filp = filp_open(cache->fname, O_RDWR | O_LARGEFILE, 0);

	if (cache->filp == NULL || IS_ERR(cache->filp)) {
		printk(KERN_ERR "dnbd: ERROR opening cache file!\n");
		result = -EINVAL;
		goto out_free;
	}

	generic_fillattr(cache->filp->f_dentry->d_inode, &stat);

	div1 = stat.size;
	div2 = blksize;
	do_div(div1, div2);

	printk(KERN_INFO
	       "dnbd: cachefile size %llu KB using %llu blocks a %i bytes for caching.\n",
	       stat.size >> 10, div1, blksize);

	cache->max_blocks = div1;
	cache->blksize = blksize;

	/* activate cache and adapt function for insert, search and clean up */
	cache->active = 1;
	cache->insert = &dnbd_cache_insert;
	cache->search = &dnbd_cache_search;
	cache->clean = &dnbd_cache_clean;

	result = 0;
	goto out;

      out_free:
	kfree(cache->fname);
      out:
	if (result < 0 && cache->filp)
		fput(cache->filp);
	return result;
}