/*   This file contains the global device cache for the BeOS.  All   file system I/O comes through here.  The cache can handle blocks   of different sizes for multiple different underlying physical   devices.   The cache is organized as a hash table (for lookups by device   and block number) and two doubly-linked lists.  The normal   list is for "normal" blocks which are either clean or dirty.   The locked list is for blocks that are locked in the cache by   BFS.  The lists are LRU ordered.   Most of the work happens in the function cache_block_io() which   is quite lengthy.  The other functions of interest are get_ents()   which picks victims to be kicked out of the cache; flush_ents()   which does the work of flushing them; and set_blocks_info() which   handles cloning blocks and setting callbacks so that the BFS   journal will work properly.  If you want to modify this code it   will take some study but it's not too bad.  Do not think about   separating the list of clean and dirty blocks into two lists as   I did that already and it's slower.   Originally this cache code was written while listening to the album   "Ride the Lightning" by Metallica.  The current version was written   while listening to "Welcome to SkyValley" by Kyuss as well as an   ambient collection on the German label FAX.  Music helps a lot when   writing code.     THIS CODE COPYRIGHT DOMINIC GIAMPAOLO.  NO WARRANTY IS EXPRESSED    OR IMPLIED.  YOU MAY USE THIS CODE AND FREELY DISTRIBUTE IT FOR   NON-COMMERCIAL USE AS LONG AS THIS NOTICE REMAINS ATTACHED.   FOR COMMERCIAL USE, CONTACT DOMINIC GIAMPAOLO (dbg@be.com).   Dominic Giampaolo   dbg@be.com*/   #include <stdio.h>#include <stdlib.h>#include <memory.h>#include <string.h>#include <errno.h>#include <fcntl.h>#include <sys/types.h>#include <unistd.h>#ifdef __BEOS__#include <OS.h>#include <KernelExport.h>#endif#include "compat.h"#include "lock.h"#include "cache.h"#ifndef USER#define printf dprintf#endif#ifdef USER#define kprintf printf#endif/* forward prototypes */static int   flush_ents(cache_ent **ents, int n_ents);static int   do_dump(int argc, char **argv);static int   do_find_block(int argc, char **argv);static int   do_find_data(int argc, char **argv);static void  cache_flusher(void *arg, int phase);int chatty_io = 0;#define CHUNK (512 * 1024)   /* a hack to work around scsi driver bugs */size_tread_phys_blocks(int fd, fs_off_t bnum, void *data, uint num_blocks, int bsize){    size_t ret = 0;    size_t sum;        if (chatty_io)        printf("R: %8ld : %3d\n", bnum, num_blocks);    if (num_blocks * bsize < CHUNK)        ret = read_pos(fd, bnum * bsize, data, num_blocks * bsize);    else {        for(sum=0; (sum + CHUNK) <= (num_blocks * bsize); sum += CHUNK) {            ret = read_pos(fd, (bnum * bsize) + sum, data, CHUNK);            if (ret != CHUNK)                break;                    data = (void *)((char *)data + CHUNK);        }        if (ret == CHUNK && ((num_blocks * bsize) - sum) > 0) {            ret = read_pos(fd, (bnum * bsize) + sum, data,                           (num_blocks * bsize) - sum);            if (ret == (num_blocks * bsize) - sum)                ret = num_blocks * bsize;        } else if (ret == CHUNK) {            ret = num_blocks * bsize;        }    }    if (ret == num_blocks * bsize)        return 0;    else        return EBADF;}size_twrite_phys_blocks(int fd, fs_off_t bnum, void *data, uint num_blocks, int bsize){    size_t ret = 0;    size_t sum;    if (chatty_io)        printf("W: %8ld : %3d\n", bnum, num_blocks);    if (num_blocks * bsize < CHUNK)        ret = write_pos(fd, bnum * bsize, data, num_blocks * bsize);    else {        for(sum=0; (sum + CHUNK) <= (num_blocks * bsize); sum += CHUNK) {            ret = write_pos(fd, (bnum * bsize) + sum, data, CHUNK);            if (ret != CHUNK)                break;                    data = (void *)((char *)data + CHUNK);        }        if (ret == CHUNK && ((num_blocks * bsize) - sum) > 0) {            ret = write_pos(fd, (bnum * bsize) + sum, data,                            (num_blocks * bsize) - sum);            if (ret == (num_blocks * bsize) - sum)                ret = num_blocks * bsize;        } else if (ret == CHUNK) {            ret = num_blocks * bsize;        }    }    if (ret == num_blocks * bsize)        return 0;    else        return EBADF;}static intinit_hash_table(hash_table *ht){    ht->max   = HT_DEFAULT_MAX;    ht->mask  = ht->max - 1;    ht->num_elements = 0;    ht->table = (hash_ent **)calloc(ht->max, sizeof(hash_ent *));    if (ht->table == NULL)        return ENOMEM;    return 0;}static voidshutdown_hash_table(hash_table *ht){    int       i, hash_len;    hash_ent *he, *next;    for(i=0; i < ht->max; i++) {        he = ht->table[i];        for(hash_len=0; he; hash_len++, he=next) {            next = he->next;            free(he);        }    }    if (ht->table)        free(ht->table);    ht->table = NULL;}static voidprint_hash_stats(hash_table *ht){    int       i, hash_len, max = -1, sum = 0;    hash_ent *he, *next;    for(i=0; i < ht->max; i++) {        he = ht->table[i];        for(hash_len=0; he; hash_len++, he=next) {            next = he->next;        }        if (hash_len)            printf("bucket %3d : %3d\n", i, hash_len);        sum += hash_len;        if (hash_len > max)            max = hash_len;    }    printf("max # of chains: %d,  average chain length %d\n", max,sum/ht->max);}#define HASH(d, b)   ((((fs_off_t)d) << (sizeof(fs_off_t)*8 - 6)) | (b))static hash_ent *new_hash_ent(int dev, fs_off_t bnum, void *data){    hash_ent *he;    he = (hash_ent *)malloc(sizeof(*he));    if (he == NULL)        return NULL;    he->hash_val = HASH(dev, bnum);    he->dev      = dev;    he->bnum     = bnum;    he->data     = data;    he->next     = NULL;    return he;}static intgrow_hash_table(hash_table *ht){    int        i, omax, newsize, newmask;    fs_off_t      hash;    hash_ent **new_table, *he, *next;        if (ht->max & ht->mask) {        printf("*** hashtable size %d or mask %d looks weird!\n", ht->max,               ht->mask);    }    omax    = ht->max;    newsize = omax * 2;        /* have to grow in powers of two */    newmask = newsize - 1;    new_table = (hash_ent **)calloc(newsize, sizeof(hash_ent *));    if (new_table == NULL)        return ENOMEM;    for(i=0; i < omax; i++) {        for(he=ht->table[i]; he; he=next) {            hash = he->hash_val & newmask;            next = he->next;                        he->next        = new_table[hash];            new_table[hash] = he;        }    }        free(ht->table);    ht->table = new_table;    ht->max   = newsize;    ht->mask  = newmask;            return 0;}static inthash_insert(hash_table *ht, int dev, fs_off_t bnum, void *data){    fs_off_t    hash;    hash_ent *he, *curr;    hash = HASH(dev, bnum) & ht->mask;    curr = ht->table[hash];    for(; curr != NULL; curr=curr->next)        if (curr->dev == dev && curr->bnum == bnum)            break;    if (curr && curr->dev == dev && curr->bnum == bnum) {        printf("entry %d:%ld already in the hash table!\n", dev, bnum);        return EEXIST;    }    he = new_hash_ent(dev, bnum, data);    if (he == NULL)        return ENOMEM;        he->next        = ht->table[hash];    ht->table[hash] = he;    ht->num_elements++;    if (ht->num_elements >= ((ht->max * 3) / 4)) {        if (grow_hash_table(ht) != 0)            return ENOMEM;    }    return 0;}static void *hash_lookup(hash_table *ht, int dev, fs_off_t bnum){    hash_ent *he;    he = ht->table[HASH(dev, bnum) & ht->mask];    for(; he != NULL; he=he->next) {        if (he->dev == dev && he->bnum == bnum)            break;    }    if (he)        return he->data;    else        return NULL;}static void *hash_delete(hash_table *ht, int dev, fs_off_t bnum){    void     *data;    fs_off_t     hash;    hash_ent *he, *prev = NULL;    hash = HASH(dev, bnum) & ht->mask;    he = ht->table[hash];    for(; he != NULL; prev=he,he=he->next) {        if (he->dev == dev && he->bnum == bnum)            break;    }    if (he == NULL) {        printf("*** hash_delete: tried to delete non-existent block %d:%ld\n",               dev, bnum);        return NULL;    }    data = he->data;    if (ht->table[hash] == he)        ht->table[hash] = he->next;    else if (prev)        prev->next = he->next;    else        panic("hash table is inconsistent\n");    free(he);    ht->num_elements--;    return data;}/*  These are the global variables for the cache.*/  static block_cache  bc;#define       MAX_IOVECS  64           /* # of iovecs for use by cache code */static lock   iovec_lock;static struct iovec *iovec_pool[MAX_IOVECS];  /* each ptr is to an array of iovecs */static int    iovec_used[MAX_IOVECS];  /* non-zero == iovec is in use */#define NUM_FLUSH_BLOCKS 64    /* size of the iovec array pointed by each ptr */#define DEFAULT_READ_AHEAD_SIZE  (32 * 1024)static int read_ahead_size = DEFAULT_READ_AHEAD_SIZE;/* this array stores the size of each device so we can error check requests */#define MAX_DEVICES  256fs_off_t max_device_blocks[MAX_DEVICES];/* has the time of the last cache access so cache flushing doesn't interfere */static bigtime_t last_cache_access = 0;intinit_block_cache(int max_blocks, int flags){    memset(&bc, 0, sizeof(bc));    memset(iovec_pool, 0, sizeof(iovec_pool));    memset(iovec_used, 0, sizeof(iovec_used));    memset(&max_device_blocks, 0, sizeof(max_device_blocks));    if (init_hash_table(&bc.ht) != 0)        return ENOMEM;    bc.lock.s = iovec_lock.s = -1;    bc.max_blocks = max_blocks;    bc.flags      = flags;    if (new_lock(&bc.lock, "bollockcache") != 0)        goto err;    if (new_lock(&iovec_lock, "iovec_lock") != 0)        goto err;        /* allocate two of these up front so vm won't accidently re-enter itself */    iovec_pool[0] = (struct iovec *)malloc(sizeof(struct iovec)*NUM_FLUSH_BLOCKS);    iovec_pool[1] = (struct iovec *)malloc(sizeof(struct iovec)*NUM_FLUSH_BLOCKS);#ifdef DEBUG    add_debugger_command("bcache", do_dump, "dump the block cache list");    add_debugger_command("fblock", do_find_block, "find a block in the cache");    add_debugger_command("fdata",  do_find_data, "find a data block ptr in the cache");#endif#ifndef USER    register_kernel_daemon(cache_flusher, NULL, 3);#endif    return 0; err:    if (bc.lock.s >= 0)        free_lock(&bc.lock);    if (iovec_lock.s >= 0)        free_lock(&iovec_lock);    shutdown_hash_table(&bc.ht);    memset((void *)&bc, 0, sizeof(bc));    return ENOMEM;}static struct iovec *get_iovec_array(void){    int i;    struct iovec *iov;    LOCK(iovec_lock);    for(i=0; i < MAX_IOVECS; i++) {        if (iovec_used[i] == 0)            break;    }    if (i >= MAX_IOVECS)       /* uh-oh */        panic("cache: ran out of iovecs (pool 0x%x, used 0x%x)!\n",              &iovec_pool[0], &iovec_used[0]);        if (iovec_pool[i] == NULL) {        iovec_pool[i] = (struct iovec *)malloc(sizeof(struct iovec)*NUM_FLUSH_BLOCKS);        if (iovec_pool == NULL)            panic("can't allocate an iovec!\n");    }    iov = iovec_pool[i];    iovec_used[i] = 1;    UNLOCK(iovec_lock);    return iov;}