From 868fec1f8eca7c344fc9ac057b7418331299d9ce Mon Sep 17 00:00:00 2001 From: Lars Müller Date: Sat, 1 Mar 2008 18:30:38 +0000 Subject: Import dnbd* from the former openslx-contrib repo as of revision 92. openslx-contrib is currently read only and will get removed in some days. git-svn-id: http://svn.openslx.org/svn/openslx/contrib/dnbd/trunk@1592 95ad53e4-c205-0410-b2fa-d234c58c8868 --- kernel/cache.c | 389 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 389 insertions(+) create mode 100644 kernel/cache.c (limited to 'kernel/cache.c') diff --git a/kernel/cache.c b/kernel/cache.c new file mode 100644 index 0000000..e72b2ff --- /dev/null +++ b/kernel/cache.c @@ -0,0 +1,389 @@ +/* + * cache.c - block cache with red-black trees + * Copyright (C) 2006 Thorsten Zitterell + */ + +#include +#include +#include +#include +#include +/* use red-black library of kernel */ +#include +#include + +#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; + + int i; + struct bio *bio; + 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; + rq_for_each_bio(bio, req) { + bio_for_each_segment(bvec, bio, i) { + 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; + } + } + + 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; +} -- cgit v1.2.3-55-g7522