Subversion Repositories shark

/*

 * Project: HARTIK (HA-rd R-eal TI-me K-ernel)

 *

 * Coordinators: Giorgio Buttazzo <giorgio@sssup.it>

 *               Gerardo Lamastra <gerardo@sssup.it>

 *

 * Authors     : Massimiliano Giorgi <massy@hartik.sssup.it>

 * (see authors.txt for full list of hartik's authors)

 *

 * ReTiS Lab (Scuola Superiore S.Anna - Pisa - Italy)

 *

 * http://www.sssup.it

 * http://retis.sssup.it

 * http://hartik.sssup.it

 */

/*

 * Copyright (C) 1999 Massimiliano Giorgi

 *

 * 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

 *

 */

/*

 * CVS :        $Id: dcache.c,v 1.1.1.1 2002-03-29 14:12:50 pj Exp $

 *

 * File:        $File$

 * Revision:    $Revision: 1.1.1.1 $

 * Last update: $Date: 2002-03-29 14:12:50 $

 */

#include <fs/util.h>

#include <fs/assert.h>

#include <fs/bdev.h>

#include <fs/magic.h>

#include <fs/major.h>

#include <fs/sysmacro.h>

#include "dcache.h"

#include "mutex.h"

#include "semaph.h"

#include "rwlock.h"

#include "debug.h"

/*

 * To do:

 * - separate the "buffer" field of a cache entry by the entry itself

 *   allowing a better memory management and a variable cache block size

 *   without wasting space.

 * - improve the purging algorithm (the algorithm that remove entries from

 *   the cache).

 * - implement a server to mantains an x% of cache buffers free and to write

 *   dirty cache entries to disk during idle periods.

 */

/*

 * How the cache is implemented:

 * copy-back algorithm or write-throught

 * (define only one of this)

 */

#define COPYBACK

//#define WRITETHROUGHT

/*

 * if a write throught policy is chosen for the cache if this

 * is defined the 'skipwt' bits into the dcache_t structure is honoured

 * (ie. if 'skipwt' is set the cache entry use a copyback policy and

 * not a write throught policy).

 */

//#define HONOURSKIPWTFLAG

/*

 * Data structures:

 *

 * We have two table:

 * "dcache" contains cache entries

 * "dhash" contains the index of the first entry of the hash list.

 * Every cache entries has two fields used to concatenates the entries

 * into lists.

 * There is the list of free entries: "freeindex" is an index into "dcache"

 * of the first free entries, every entry has a "next" field that points

 * to the next free entry.

 * Every entry into "dhash" is a pointer to the first cache entry that is

 * into a hash bucket; every hash bucket is organized like a double linked

 * list using the "next" and "prev" fields of the cache entry.

 *

 * DANGER:

 * - to prevent dead-lock locking of "freemutex" MUST be done always

 *   after a lock of "hashmutex".

 * - the functions that begins with "__????" do not lock/unlock

 *   the mutex.

 */

/*+ number of hash buckets +*/

#define MAXHASH     64

/*+ and-mask to obtain a number between 0 and MAXHASH-1 +*/

#define MAXHASHMASK 0x3f

/*+ hash buckets +*/

static int       dhash[MAXHASH];

/*+ mutex to operate on "dhash" +*/

static __fs_mutex_t hashmutex;

/*+ number of cache entries +*/

#define MAXCACHESIZE (8192*4)

/*+ cache entries table +*/

static dcache_t  dcache[MAXCACHESIZE];

/*+ mutex to operate with the "free list" +*/

static __fs_mutex_t freemutex;

/*+ index of first free cache entry +*/

static int       freeindex=0;

static __dev_t blocked_device=makedev(MAJOR_B_NULL,0);

/*++++++++++++++++++++++++++++++++++++++

  Hash function.

  int hash_fun

    return a number between 0 and MAXHASH-1.

  __dev_t ldisk

    block device.

  __blkcnt_t lsector

    block number.

  ++++++++++++++++++++++++++++++++++++++*/

static int hash_fun(__dev_t dev, __blkcnt_t lsector)

{

  static __uint32_t table[8]={3,5,7,11,13,17,19,23};

  return (table[dev&0x07]*(lsector+1))&MAXHASHMASK;

}

/*

 *

 * INITIALIZATION/TERMINATION FUNCTIONS

 *

 */

/*++++++++++++++++++++++++++++++++++++++

  Dump into the system logs the cache status.

  ++++++++++++++++++++++++++++++++++++++*/

#include <drivers/keyb.h>

void dcache_stats(void)

{

  int i,c,d,l,j,r,lc;

  long x,f;

  /* acquire all mutex */

  __fs_mutex_lock(&hashmutex);

  __fs_mutex_lock(&freemutex);

  /* count free entries */

  c=0;

  i=freeindex;

  while (i!=NIL) {

    c++;

    i=dcache[i].next;

  }

  /* dump informations */

  printk(KERN_INFO "max dcache entries: %4i",MAXCACHESIZE);

  printk(KERN_INFO "  free entries:     %4i",c);

  /* count used entries */

  for (i=0,c=0,d=0,l=0,r=0;i<MAXHASH;i++) {

    j=dhash[i];

    while (j!=NIL) {

      c++;

      if (dcache[j].used!=0) l++;

      if (dcache[j].dirty) d++;

      if (!dcache[j].ready) r++;

      j=dcache[j].next;      

    }

  }

  /* dump informations */

  printk(KERN_INFO "  cached entries:      %4i",c);

  printk(KERN_INFO "    used entries:      %4i",l);

  printk(KERN_INFO "    dirty entries:     %4i",d);

  printk(KERN_INFO "    not ready entries: %4i",r);

  /* compute hash function quality factor */

  for (i=0,x=0;i<MAXHASH;i++) {

    j=dhash[i];

    lc=0;

    while (j!=NIL) {

      lc++;

      j=dcache[j].next;      

    }

    f=((long)lc*MAXHASH-c);

    x+=f*f/(MAXHASH*2);

  }

  /* dump informations */

  printk(KERN_INFO "hash quality:     %6li",x);

  /* release all mutex */

  __fs_mutex_unlock(&freemutex);

  __fs_mutex_unlock(&hashmutex);

}

/*++++++++++++++++++++++++++++++++++++++

  Module initialization; must be called prior to other functions.

  int dcache_init

    return 0 on success, other values on failure.

  ++++++++++++++++++++++++++++++++++++++*/

int dcache_init(void)

{

  int i;

  /* mutex initialization */

  __fs_mutex_init(&freemutex);

  __fs_mutex_init(&hashmutex);

  /* free list and cache table initialization */

  freeindex=0;

  for (i=0;i<MAXCACHESIZE;i++) {

    magic_set(dcache[i].magic,DCACHE_MAGIC);

    dcache[i].next=i+1;

    dcache[i].prev=NIL;

    dcache[i].device=NULLDEV;

    dcache[i].lsector=0;

    dcache[i].used=-1;

    dcache[i].dirty=0;

    dcache[i].ready=0;

    dcache[i].numblocked=0;

    dcache[i].esyncreq=0;

    dcache[i].skipwt=0;

    __fs_sem_init(&dcache[i].sync,0);

    __fs_sem_init(&dcache[i].esync,0);

    __rwlock_init(&dcache[i].rwlock);

  }

  dcache[MAXCACHESIZE-1].next=NIL;

  /* hash buckets initialization */

  for (i=0;i<MAXHASH;i++)

    dhash[i]=NIL;

  return 0;

}

/*++++++++++++++++++++++++++++++++++++++

  Terminate the cache flushing all dirty blocks and prevent

  other request to be made to the cache module; the only function

  that can be called after this is __dcache_flush().

  int dcache_end

    return 0 on success other values on failure

  int flag

    if set aquire exclusive use of all cache entries

    before ending

  ++++++++++++++++++++++++++++++++++++++*/

int dcache_end(int flag)

{

  int __dcache_flush(int flag);

  /* if a lock on all cache entries is required... */

  if (flag) {

    int i,k;

    __fs_mutex_lock(&hashmutex);

    /* lock every request of other cache entries*/

    __fs_mutex_lock(&freemutex);

    /* scan all hash bucket locking all cache entries */

    for (k=0;k<MAXHASH;k++) {

      i=dhash[k];

      while (i!=NIL) {

        /* so cache entry can not be removed! */

        dcache[i].used++;

        __fs_mutex_unlock(&hashmutex);

        /* exclusive lock */

        __rwlock_wrlock(&dcache[i].rwlock);

        __fs_mutex_lock(&hashmutex);

        dcache[i].used=1;

        i=dcache[i].next;

      }

    }

    __fs_mutex_unlock(&hashmutex);

  }

  /* this mutex is not released to prevent other modules use of this module */

  __fs_mutex_lock(&hashmutex);

  /* flush the cache */

  return __dcache_flush(flag);

}

/*

 *

 * GET/FREE cache entries FUNCTIONS

 *

 */

/*++++++++++++++++++++++++++++++++++++++

  Get a cache entry from the free list.

  int get_dcache

    return NIL on failure, an index into "dcache" on success.

  ++++++++++++++++++++++++++++++++++++++*/

static int get_dcache(void)

{

  int ret;

  /* remove the head of a list (if present) */

  __fs_mutex_lock(&freemutex);

  ret=freeindex;

  if (ret!=NIL) {

    freeindex=dcache[ret].next;

    _assert(dcache[ret].used==-1);

    dcache[ret].used=0;

    dcache[ret].skipwt=0;

    magic_assert(dcache[ret].magic,DCACHE_MAGIC,

                 "dcache: get_dcache(): cache_entry[%i] overwritten",

                 ret);    

  }

  __fs_mutex_unlock(&freemutex);

  return ret;

}

/*++++++++++++++++++++++++++++++++++++++

  Insert a free cache entry into the free list.

  int index

    Index of the "dcache" entry to free.

  ++++++++++++++++++++++++++++++++++++++*/

static void free_dcache(int index)

{

  /* insert an element into a list */

  _assert(index>=0&&index<MAXCACHESIZE);

  _assert(dcache[index].used==0);

  dcache[index].used=-1;

  magic_assert(dcache[index].magic,DCACHE_MAGIC,

               "dcache: free_dcache(): cache_entry[%i] overwritten",

               index);    

  __fs_mutex_lock(&freemutex);

  dcache[index].next=freeindex;

  freeindex=index;

  __fs_mutex_unlock(&freemutex);

}

/*

 *

 * HASH BUCKETS MANAGEMENT FUNCTIONS

 *

 */

/*++++++++++++++++++++++++++++++++++++++

  Insert a cache entry into an hash bucket.

  int index

    Entry to insert.

  ++++++++++++++++++++++++++++++++++++++*/

static void __insert_dcache(int index)

{

  int h;

  /* insert an element into a double linked list */

  _assert(index>=0&&index<MAXCACHESIZE);

  _assert(dcache[index].used==1);

  magic_assert(dcache[index].magic,DCACHE_MAGIC,

               "dcache: insert_dcache(): cache_entry[%i] overwritten",

               index);    

  h=hash_fun(dcache[index].device,dcache[index].lsector);

  dcache[index].prev=NIL;

  dcache[index].hash=h;

  dcache[index].next=dhash[h];

  if (dhash[h]!=NIL) dcache[dhash[h]].prev=index;

  dhash[h]=index;

}

/*++++++++++++++++++++++++++++++++++++++

  Remove a cache entry from an hash bucket.

  int index

    Entry to remove.

  ++++++++++++++++++++++++++++++++++++++*/

static void __remove_dcache(int index)

{

  /* remove an element from a double linked list */

  _assert(index>=0&&index<MAXCACHESIZE);

  _assert(dcache[index].used==0);

  magic_assert(dcache[index].magic,DCACHE_MAGIC,

               "dcache: remove_dcache(): cache_entry[%i] overwritten",

               index);

  if (dcache[index].prev!=NIL)

    dcache[dcache[index].prev].next=dcache[index].next;

  else {

    dhash[dcache[index].hash]=dcache[index].next;

  }

  if (dcache[index].next!=NIL)

    dcache[dcache[index].next].prev=dcache[index].prev;

}

/*++++++++++++++++++++++++++++++++++++++

  Find an entry into an hash bucket to free.

  int __purge_dcache

    NIL on failure, an index of a free cache entry on success

  ++++++++++++++++++++++++++++++++++++++*/

static int __purge_dcache(void)

{

  int i,k;

  int flag;

  int ind;

  int res;

  __time_t t;

  /* TO IMPROVE!!! */

  /* algoritmo brutale ed inefficiente per rimuovere un'entry

   * in cache:

   * -- si scorrono sempre (sigh) tutte le entry

   * -- viene trovata la entry non in uso, non sporca, piu' vecchia

   * -- altrimenti quella non in uso, piu' vecchia

   * -- altrimenti NIL (non rimuove niente)

   */

  /*

   * search an entry to purge

   */

  flag=1;

  ind=NIL;

  t=0xffffffff;  

  for (k=0;k<MAXHASH;k++) {        

    i=dhash[k];

    while (i!=NIL) {

      if (dcache[i].used==0) {

        if (dcache[i].dirty==0) {

          flag=0;

          if (dcache[i].time<t||(ind!=NIL&&dcache[ind].dirty==1)) {

            ind=i;

            t=dcache[i].time;

          }

        } else if (flag) {

          if (dcache[i].time<t) {

            ind=i;

            t=dcache[i].time;

          }      

        }

      }      

      i=dcache[i].next;

    }

  }

  /*

   * purging the entry

   */

  /* if an entry is found... */

  if (ind!=NIL) {

    /* if it is dirty... */

    if (dcache[ind].dirty) {

      /* the entry is dirty... try to write to disk!*/

      /* update reference count */

      dcache[ind].used++;

      /* set not ready flags */

      dcache[ind].ready=0;

      /* safety stuff */

      _assert(dcache[ind].used==1);

      /* release mutex */

      __fs_mutex_unlock(&hashmutex);

      /* try to write... */

      /* there is no need to acquire the entry for writing... it is not used */

      res=bdev_write(dcache[ind].device,dcache[ind].lsector,

                     dcache[ind].buffer);

      /* aquire the mutex */

      __fs_mutex_lock(&hashmutex);

      /* if error while writing... */

      if (res!=0) {

        /* restore old fields value */

        dcache[ind].used--;

        dcache[ind].ready=1;

      }

      /* set flag if some thread has been blocked waiting for "ready" field */

      flag=(dcache[ind].numblocked>0);

      /* wake up all thread waiting for synchronization */

      while (dcache[ind].numblocked>0) {

        __fs_sem_signal(&dcache[ind].sync);

        dcache[ind].numblocked--;      

      }

      /* if error while writing... return NIL*/

      if (res!=0) return NIL;

      /* to be ensure that no other treads can be blocked on this entry */

      dcache[ind].device=NULLDEV;

      /* if some thread have been waked up... */

      if (flag) {

        /* we must wait that all waked up thread had made the error test... */

        /* request error synchronization */

        dcache[ind].esyncreq=1;

        /* release mutex */

        __fs_mutex_unlock(&hashmutex);

        /* wait for synchronization */

        __fs_sem_wait(&dcache[ind].esync);

        /* reacquire mutex */

        __fs_mutex_lock(&hashmutex);

        /* safety stuff */

        /*_assert(dcache[ind].used==1);*/

      }

      /* restore old value */

      dcache[ind].used--;      

      /* safety stuff */

      _assert(dcache[ind].used==0);      

    }

    /* remove the entry from the hasb bucket*/

    __remove_dcache(ind);

  }

  return ind;

}

/*++++++++++++++++++++++++++++++++++++++

  Called when a cache entry has been modificated (AFTER has been

  modified not before).

  WARNING: this function CAN be called only by the task what has

  aquired (for exclusive use) the cache entry.

  void dcache_dirty

    nothing to return

  dcache_t *d

    entry that must be marked dirty

  ++++++++++++++++++++++++++++++++++++++*/

#ifdef COPYBACK

void dcache_dirty(dcache_t *d)

{

  /* safety stuff */

  _assert(d->used==1);

  /* we use copy back so only set the flag */

  d->dirty=1;

}

/* used internally when we want flush a cache entry during

 * generic unlock functions

 */

static __inline__ void __flush_cache(dcache_t *d)

{

  /* nothing to do */

  return;

}

#endif

#ifdef WRITETHROUGHT

void dcache_dirty(dcache_t *d)

{

  /* safety stuff */

  _assert(d->used==1);

  /* we only set the flag */

  d->dirty=1;

}

/* used internally when we want flush a cache entry during

 * generic unlock functions

 */

static __inline__ void __flush_cache(dcache_t *d)

{

  int res;

  #ifdef HONOURSKIPWTFLAG

  if (d->skipwt) return;

  #endif

  if (d->dirty) {

    /* safety stuff */

    _assert(d->used==1);

    _assert(d-dcache>=0&&d-dcache<MAXCACHESIZE);

    /* try to write... */

    /* there is no need to modify/lock the entry (see the warning!) */

    res=bdev_write(d->device,d->lsector,d->buffer);

    /* if write OK... */

    if (res==0) d->dirty=0;

  }  

}

#endif

/*++++++++++++++++++++++++++++++++++++++

  Find a free cache entry to use.

  int __catch_dcache

    NIL on failure, a index of a free cache entry on success.

  ++++++++++++++++++++++++++++++++++++++*/

static __inline__ int __catch_dcache(void)

{

  int ind;

  ind=get_dcache();

  if (ind==NIL) ind=__purge_dcache();

  return ind;

}

/*

 *

 * FLUSHING FUNCTIONS

 *

 */

/*++++++++++++++++++++++++++++++++++++++

  Flush all cache entries to disk; this function does not acquire the

  "hashmutex" mutex so it can be called only during system shut down (with

  no runnig thread) or after a call to dcache_end().

  The function dcache_end() call this function before ending.

  int __dcache_flush

    return 0 on success, other values on failure

  inf flag

    if set mean that we do have exclusive access to cache memory; if

    we have exclusive access the "used" field must be 1 else must be 0.

  ++++++++++++++++++++++++++++++++++++++*/

int __dcache_flush(int flag)

{

  int i,k,ret,res;

  ret=0;

  /* for every hash buckets... */

  for (k=0;k<MAXHASH;k++) {

    i=dhash[k];

    /* scan all entries... */

    while (i!=NIL) {    

      _assert(dcache[i].used==(flag?1:0));

      /* for every dirty entry... */

      if (dcache[i].dirty) {

        res=bdev_write(dcache[i].device,dcache[i].lsector,dcache[i].buffer);

        if (res==0)

          dcache[i].dirty=0;

        else

          ret=-1;        

      }

      /* go to next entry */

      i=dcache[i].next;

    }

  }

  return ret;

}

/*++++++++++++++++++++++++++++++++++++++

  Purge a device from the cache; remove every reference to the device

  from the cache.

  int dcache_purgedevice

  __dev_t dev

    device to purge

  int cont

    if setted continue on disk write error

  ++++++++++++++++++++++++++++++++++++++*/

int dcache_purgedevice(__dev_t dev, int cont)

{

  int retvalue=0;

  int i,k,inext;

  int res;

  printka("dcache_purgedevice() START for device(%08lx)",(long)dev);

  __fs_mutex_lock(&hashmutex);

  /* prevent other thread to cache this device*/

  blocked_device=dev;

  for (k=0;k<MAXHASH;k++) {

    i=dhash[k];

    /* scan all entries... */

    while (i!=NIL) {

      /* remember next entry */

      inext=dcache[i].next;

      if (dcache[i].device==dev) {

        /* an entry to purge is found... */

        //printka("  found %li",dcache[i].lsector);

        _assert(dcache[i].used!=-1);

        while (dcache[i].used!=0) {

          /* someone is using this entry... we must wait! */

          dcache[i].used++;

          __fs_mutex_unlock(&hashmutex);

          __rwlock_wrlock(&dcache[i].rwlock);

          __rwlock_wrunlock(&dcache[i].rwlock);

          __fs_mutex_lock(&hashmutex);

          dcache[i].used--;

          /* we must loop because, in general, we do not know how */

          /* the __rwlock queues are managed; the loop must quit because */

          /* we prevent other threads to be inserted into this queues */

          /* we must update 'inext' */

          inext=dcache[i].next;

        }

        if (dcache[i].dirty!=0) {

          /* the cache entry is dirty... we must write to disk */

          printka("  dirty %li",dcache[i].lsector);

          dcache[i].used++;

          __fs_mutex_unlock(&hashmutex);

          res=bdev_write(dcache[i].device,dcache[i].lsector,dcache[i].buffer);

          __fs_mutex_lock(&hashmutex);

          dcache[i].used--;

          /* we must update 'inext' */

          inext=dcache[i].next;

          if (res!=0) {

            /* an error! */

            retvalue=-1;

            if (!cont) {

              /* ...we can not continue! */

              blocked_device=makedev(MAJOR_B_NULL,0);

              __fs_mutex_unlock(&hashmutex);

              return -1;

            }

          }

        }

        /* now we can purge the entry */

        __remove_dcache(i);

      }

      /* go to next entry */

      i=inext;

    }

  }

  blocked_device=makedev(MAJOR_B_NULL,0);  

  __fs_mutex_unlock(&hashmutex);

  printka("dcache_purgedevice() END");

  return retvalue;

}

/*++++++++++++++++++++++++++++++++++++++

  Flush all the cache to disk; it can be called always but it does not

  assure that there are no more dirty cache entries when it return.

  int dcache_flush

    return 0 on success, other value on failure.

  ++++++++++++++++++++++++++++++++++++++*/

int dcache_flush(void)

{

  int i,k,ret,res;

  __fs_mutex_lock(&hashmutex);

  ret=0;

  for (k=0;k<MAXHASH;k++) {

    i=dhash[k];

    /* for every dirty cache entries...*/

    while (i!=NIL) {

      magic_assert(dcache[i].magic,DCACHE_MAGIC,

                   "dcache: dcache_flush(): cache_entry[%i] overwritten",

                   i);    

      if (dcache[i].dirty) {

        /* to prevent purging the cache entry */

        dcache[i].used++;

        __fs_mutex_unlock(&hashmutex);

        /* aquire a "read lock" (we do not modify cache) to write to disk */