home *** CD-ROM | disk | FTP | other *** search
/ Big Green CD 8 / BGCD_8_Dev.iso / NEXTSTEP / UNIX / Utilities / vmount-0.6a-I / src / cache.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-04-30  |  7.6 KB  |  288 lines
  1. /*
  2.  * Name: cache.c
  3.  * Description: This module contains a simple disk cache.
  4.  * Author: Christian Starkjohann <cs@hal.kph.tuwien.ac.at>
  5.  * Date: 1996-12-16
  6.  * Copyright: GNU-GPL
  7.  * Tabsize: 4
  8.  */
  9.  
  10. #include <errno.h>
  11. #include <libc.h>
  12. #include "my_defines.h"
  13. #include "cache.h"
  14.  
  15. extern int    errno;
  16.  
  17. /* ------------------------------------------------------------------------- */
  18.  
  19. #define    DPRINTF(arg)    if(debug_mode & DEBUG_CACHE)    dprintf arg
  20.  
  21. /* ------------------------------------------------------------------------- */
  22.  
  23. #define    BIG_BUFSZ    65536    /* size of one cache block */
  24. #define    SMALL_BUFSZ    4096    /* size of one cache block */
  25. #define    CACHE_SIZE    10        /* number of cache blocks */
  26.  
  27. /* ------------------------------------------------------------------------- */
  28.  
  29. typedef struct cacheline{
  30.     struct cacheline    *next;
  31.     struct cacheline    **prevnext;        /* doubly linked LRU chain */
  32.     char                valid;            /* all data in buffer is valid */
  33.     char                any_dirty;        /* there is dirty data in the buffer */
  34.     unsigned char        *dirty;            /* bitmap with dirty flags/unit */
  35.     int                    dirty_size;        /* number of bytes in dirty buffer */
  36.     unsigned long        base;            /* base of buffer on disk */
  37.     char                *buffer;        /* longword aligned block */
  38. }cacheline_t;
  39.  
  40. typedef struct list{
  41.     cacheline_t    *head;            /* first element in list */
  42.     cacheline_t    **tail;            /* pointer to 'next' entry of last element */
  43. }list_t;
  44.  
  45. /* ------------------------------------------------------------------------- */
  46.  
  47. static int                buffer_size = BIG_BUFSZ;
  48. static int                base_mask = (~(BIG_BUFSZ - 1));
  49. static cacheline_t        cache[CACHE_SIZE];
  50. static list_t            cache_lru;
  51. static int                unit_size;        /* allocation unit */
  52. static int                unit_count;        /* allocation units */
  53.  
  54. /* ------------------------------------------------------------------------- */
  55.  
  56. #define    SET_BIT(arr, i)        ((arr)[(i)>>3] |= (1 << ((i)&7)))
  57. #define    BIT_IS_SET(arr, i)    (((arr)[(i)>>3] & (1 << ((i)&7))) != 0)
  58.  
  59. /* ------------------------------------------------------------------------- */
  60.  
  61. static inline void    list_init(list_t *list)
  62. {
  63.     list->head = NULL;
  64.     list->tail = &list->head;
  65. }
  66.  
  67. static inline void    list_append(list_t *list, cacheline_t *entry)
  68. {
  69.     entry->prevnext = list->tail;
  70.     *list->tail = entry;
  71.     list->tail = &entry->next;
  72.     entry->next = NULL;
  73. }
  74.  
  75. static inline void    list_move_to_end(list_t *list, cacheline_t *entry)
  76. {
  77.     if(entry->next == NULL)    /* we are already the last! */
  78.         return;
  79.     *entry->prevnext = entry->next;        /* take us out of the list */
  80.     entry->next->prevnext = entry->prevnext;
  81.  
  82.     entry->prevnext = list->tail;        /* put us at the end */
  83.     *list->tail = entry;
  84.     list->tail = &entry->next;
  85.     entry->next = NULL;
  86. }
  87.  
  88. /* ------------------------------------------------------------------------- */
  89.  
  90. static unsigned long    file_position = -3;    /* force lseek for first time */
  91.  
  92. static void    cacheline_rw(int do_wr, cacheline_t *p, char *buffer)
  93. {
  94. int        size;
  95.  
  96.     DPRINTF(("cacheline_rw: %sing from base 0x%08lx\n", do_wr ? "writ":"read",
  97.                                                                     p->base));
  98.     if(do_wr && !wr_enable){
  99.         fatal_error("*** Attempt to write on read only filesystem: 0x%lx\n",
  100.                                                                     p->base);
  101.         return;
  102.     }
  103.     if(file_position != p->base){
  104.         if(lseek(my_fd, p->base, 0) == -1){
  105.             fatal_error("** cacheline_rw: error in lseek to 0x%08lx: %s\n",
  106.                                                     p->base, strerror(errno));
  107.             return;
  108.         }
  109.         file_position = p->base;
  110.     }
  111.     if(do_wr)
  112.         size = write(my_fd, buffer, buffer_size);
  113.     else
  114.         size = read(my_fd, buffer, buffer_size);
  115.     if(size != buffer_size){
  116.         fatal_error("** cacheline_rw: error %sing at base 0x%08lx: %s\n",
  117.                             do_wr ? "writ":"read", p->base, strerror(errno));
  118.     }
  119.     file_position += buffer_size;
  120. }
  121.  
  122. /* ------------------------------------------------------------------------- */
  123.  
  124. static void    cache_make_valid(cacheline_t *p)
  125. {
  126. int        i, pos;
  127. char    merge_buffer[buffer_size];
  128.  
  129.     if(!p->any_dirty){
  130.         DPRINTF(("cache_make_valid: full read\n"));
  131.         cacheline_rw(0, p, p->buffer);
  132.     }else{
  133.         for(i=0;i<unit_count;i++){
  134.             if(!BIT_IS_SET(p->dirty, i))
  135.                 break;
  136.         }
  137.         if(i < unit_count){        /* loop had break: not all blocks dirty */
  138.             DPRINTF(("cache_make_valid: merging with dirty\n"));
  139.             cacheline_rw(0, p, merge_buffer);
  140.             for(;i<unit_count;i++){    /* i is still on first non-dirty */
  141.                 if(!BIT_IS_SET(p->dirty, i)){
  142.                     pos = i * unit_size;
  143.                     memcpy(&p->buffer[pos], &merge_buffer[pos], unit_size);
  144.                 }
  145.             }
  146.         }else{
  147.             DPRINTF(("cache_make_valid: all dirty\n"));
  148.         }
  149.     }
  150.     p->valid = 1;
  151. }
  152.  
  153. static void    cache_writeback(cacheline_t *p)
  154. {
  155.     if(!p->valid){
  156.         cache_make_valid(p);
  157.     }
  158.     cacheline_rw(1, p, p->buffer);
  159.     p->any_dirty = 0;
  160.     bzero(p->dirty, p->dirty_size);
  161. }
  162.  
  163. /* ------------------------------------------------------------------------- */
  164.  
  165. static inline cacheline_t    *cache_find(unsigned long base)
  166. {
  167. int            i;
  168. cacheline_t    *p = NULL;
  169.  
  170.     for(i=0;i<CACHE_SIZE;i++){
  171.         if(cache[i].base <= base && (cache[i].base + buffer_size) > base){
  172.             DPRINTF(("cache_find: found for base 0x%08lx\n", base));
  173.             return &cache[i];    /* found cache line for our region */
  174.         }
  175.     }
  176.     p = cache_lru.head;
  177.     DPRINTF(("cache_find: freeing 0x%08lx for 0x%08lx\n", p->base, base));
  178.     if(p->any_dirty)
  179.         cache_writeback(p);
  180.     p->valid = 0;
  181.     p->any_dirty = 0;
  182.     bzero(p->dirty, p->dirty_size);
  183.     p->base = base & base_mask;
  184.     return p;
  185. }
  186.  
  187. /* ------------------------------------------------------------------------- */
  188.  
  189. void    cached_read(unsigned long base, char *dest)
  190. {
  191. cacheline_t    *p;
  192.  
  193.     DPRINTF(("cached_read: 0x%08lx\n", base));
  194.     p = cache_find(base);
  195.     if(!p->valid)
  196.         cache_make_valid(p);
  197.     list_move_to_end(&cache_lru, p);
  198.     memcpy(dest, &p->buffer[base - p->base], unit_size);
  199. }
  200.  
  201. void    cached_write(unsigned long base, char *data)
  202. {
  203. int            i;
  204. cacheline_t    *p;
  205.  
  206.     DPRINTF(("cached_write: 0x%08lx\n", base));
  207.     p = cache_find(base);
  208.     i = base - p->base;
  209.     memcpy(&p->buffer[i], data, unit_size);
  210.     p->any_dirty = 1;
  211.     i /= unit_size;
  212.     SET_BIT(p->dirty, i);
  213.     list_move_to_end(&cache_lru, p);
  214. }
  215.  
  216. /* ------------------------------------------------------------------------- */
  217.  
  218. void    cache_sync(void)
  219. {
  220. int            i;
  221. cacheline_t    *p;
  222.  
  223.     DPRINTF(("cache_sync()\n"));
  224.     if(debug_mode & DEBUG_CACHE){
  225.         for(p=cache_lru.head;p!=NULL;p=p->next){
  226.             dprintf("%02d base 0x%08lx valid=%d any_dirty=%d\n",
  227.                     (int)(p - cache), p->base, p->valid, p->any_dirty);
  228.         }
  229.     }
  230.     for(i=0;i<CACHE_SIZE;i++){
  231.         if(cache[i].any_dirty){
  232.             cache_writeback(&cache[i]);
  233.         }
  234.     }
  235. }
  236.  
  237. /* ------------------------------------------------------------------------- */
  238.  
  239. void    cache_set_bsize(int bsize)
  240. {
  241.     DPRINTF(("cache_set_bsize(%d)\n", bsize));
  242.     if((bsize & (bsize - 1)) != 0){
  243.         eprintf("cache_set_bsize(): %d is not power of 2\n", bsize);
  244.         terminate(1);
  245.     }
  246.     if(bsize > buffer_size){
  247.         eprintf("cache_set_bsize(): %d too big\n", bsize);
  248.         terminate(1);
  249.     }
  250.     if(bsize < 512){
  251.         eprintf("cache_set_bsize(): %d too small\n", bsize);
  252.         terminate(1);
  253.     }
  254.     cache_sync();        /* make allocation unit size irrelevant */
  255.     unit_size = bsize;
  256.     unit_count = buffer_size/unit_size;
  257. }
  258.  
  259. /* ------------------------------------------------------------------------- */
  260.  
  261. void    cache_init_buffers(int use_small_buffer)
  262. {
  263. int        i;
  264.  
  265.     DPRINTF(("cache_init_buffers()\n"));
  266.     buffer_size = use_small_buffer ? SMALL_BUFSZ : BIG_BUFSZ;
  267.     unit_size = 512;
  268.     unit_count = buffer_size/unit_size;
  269.     base_mask = (~(buffer_size - 1));
  270.     list_init(&cache_lru);
  271.     for(i=0;i<CACHE_SIZE;i++){
  272.         cache[i].valid = 0;
  273.         cache[i].any_dirty = 0;
  274.         if(cache[i].dirty != NULL)
  275.             free(cache[i].dirty);
  276.         cache[i].dirty_size = buffer_size >> 12;
  277.         cache[i].dirty = malloc(cache[i].dirty_size);
  278.         bzero(cache[i].dirty, cache[i].dirty_size);
  279.         if(cache[i].buffer != NULL)
  280.             free(cache[i].buffer);
  281.         cache[i].buffer = malloc(buffer_size);
  282.         cache[i].base = i * buffer_size;
  283.         list_append(&cache_lru, &cache[i]);
  284.     }
  285. }
  286.  
  287. /* ------------------------------------------------------------------------- */
  288.