lib/pagecache.c

   1 /*
   2  *      Sherlock Library -- File Page Cache
   3  *
   4  *      (c) 1999 Martin Mares <mj@atrey.karlin.mff.cuni.cz>
   5  */
   6
   7 #include <stdio.h>
   8 #include <stdlib.h>
   9 #include <string.h>
  10 #include <fcntl.h>
  11 #include <unistd.h>
  12
  13 #include "lib.h"
  14 #include "pagecache.h"
  15 #include "lfs.h"
  16
  17 struct page_cache {
  18   list free_pages;                      /* LRU queue of free pages */
  19   list locked_pages;                    /* List of locked pages */
  20   list dirty_pages;                     /* List of dirty pages */
  21   uns page_size;                        /* Bytes per page (must be a power of two) */
  22   uns free_count;                       /* Number of free / dirty pages */
  23   uns total_count;                      /* Total number of pages */
  24   uns max_pages;                        /* Maximum number of free pages */
  25   uns hash_size;                        /* Hash table size */
  26   list *hash_table;                     /* List heads corresponding to hash buckets */
  27 };
  28
  29 /* FIXME: Negations -> cast to sh_off_t */
  30
  31 struct page_cache *
  32 pgc_open(uns page_size, uns max_pages)
  33 {
  34   struct page_cache *c = xmalloc(sizeof(struct page_cache));
  35   uns i;
  36
  37   bzero(c, sizeof(*c));
  38   init_list(&c->free_pages);
  39   init_list(&c->locked_pages);
  40   init_list(&c->dirty_pages);
  41   c->page_size = page_size;
  42   c->max_pages = max_pages;
  43   c->hash_size = nextprime(c->max_pages);
  44   c->hash_table = xmalloc(sizeof(list) * c->hash_size);
  45   for(i=0; i<c->hash_size; i++)
  46     init_list(&c->hash_table[i]);
  47   return c;
  48 }
  49
  50 void
  51 pgc_close(struct page_cache *c)
  52 {
  53   pgc_cleanup(c);
  54   ASSERT(EMPTY_LIST(c->locked_pages));
  55   ASSERT(EMPTY_LIST(c->dirty_pages));
  56   ASSERT(EMPTY_LIST(c->free_pages));
  57   free(c->hash_table);
  58   free(c);
  59 }
  60
  61 static void
  62 pgc_debug_page(struct page *p)
  63 {
  64   printf("\tk=%08x f=%x c=%d\n", (uns) p->key, p->flags, p->lock_count);
  65 }
  66
  67 void
  68 pgc_debug(struct page_cache *c)
  69 {
  70   struct page *p;
  71
  72   printf(">> Page cache dump: pgsize=%d, pages=%d, freepages=%d of %d, hash=%d\n", c->page_size, c->total_count, c->free_count, c->max_pages, c->hash_size);
  73   puts("LRU list:");
  74   WALK_LIST(p, c->free_pages)
  75     pgc_debug_page(p);
  76   puts("Locked list:");
  77   WALK_LIST(p, c->locked_pages)
  78     pgc_debug_page(p);
  79   puts("Dirty list:");
  80   WALK_LIST(p, c->dirty_pages)
  81     pgc_debug_page(p);
  82 }
  83
  84 static void
  85 flush_page(struct page_cache *c, struct page *p)
  86 {
  87   int fd = p->key & (c->page_size - 1);
  88   sh_off_t pos = p->key & ~(c->page_size - 1);
  89   int s;
  90
  91   ASSERT((p->flags & PG_FLAG_DIRTY) && !p->lock_count);
  92   /* FIXME: Use pwrite() */
  93   sh_seek(fd, pos, SEEK_SET);
  94   s = write(fd, p->data, c->page_size);
  95   if (s < 0)
  96     die("pgc_write(%d): %m", fd);
  97   if (s != (int) c->page_size)
  98     die("pgc_write(%d): incomplete page (only %d of %d)", s, c->page_size);
  99   p->flags &= ~PG_FLAG_DIRTY;
 100 }
 101
 102 static inline uns
 103 hash_page(struct page_cache *c, sh_off_t key)
 104 {
 105   return key % c->hash_size;            /* FIXME: Use better hash function */
 106 }
 107
 108 static struct page *
 109 get_page(struct page_cache *c, sh_off_t key)
 110 {
 111   node *n;
 112   struct page *p;
 113   uns hash = hash_page(c, key);
 114
 115   /*
 116    *  Return locked buffer for given page.
 117    */
 118
 119   WALK_LIST(n, c->hash_table[hash])
 120     {
 121       p = SKIP_BACK(struct page, hn, n);
 122       if (p->key == key)
 123         {
 124           /* Found in the cache */
 125           rem_node(&p->n);
 126           if (!p->lock_count)
 127             c->free_count--;
 128           return p;
 129         }
 130     }
 131   if (c->total_count < c->max_pages || !c->free_count)
 132     {
 133       /* Enough free space, expand the cache */
 134       p = xmalloc(sizeof(struct page) + c->page_size);
 135       c->total_count++;
 136     }
 137   else
 138     {
 139       /* Discard the oldest unlocked page */
 140       p = HEAD(c->free_pages);
 141       if (!p->n.next)
 142         {
 143           /* There are only dirty pages here */
 144           p = HEAD(c->dirty_pages);
 145           flush_page(c, p);
 146         }
 147       ASSERT(!p->lock_count);
 148       rem_node(&p->n);
 149       rem_node(&p->hn);
 150       c->free_count--;
 151     }
 152   p->key = key;
 153   p->flags = 0;
 154   p->lock_count = 0;
 155   add_tail(&c->hash_table[hash], &p->hn);
 156   return p;
 157 }
 158
 159 void
 160 pgc_flush(struct page_cache *c)
 161 {
 162   struct page *p;
 163   node *n;
 164
 165   WALK_LIST_DELSAFE(p, n, c->dirty_pages)
 166     {
 167       flush_page(c, p);
 168       rem_node(&p->n);
 169       add_tail(&c->free_pages, &p->n);
 170     }
 171 }
 172
 173 void
 174 pgc_cleanup(struct page_cache *c)
 175 {
 176   struct page *p;
 177   node *n;
 178
 179   pgc_flush(c);
 180   WALK_LIST_DELSAFE(p, n, c->free_pages)
 181     {
 182       ASSERT(!(p->flags & PG_FLAG_DIRTY) && !p->lock_count);
 183       rem_node(&p->n);
 184       c->free_count--;
 185       c->total_count--;
 186       free(p);
 187     }
 188   ASSERT(!c->free_count);
 189 }
 190
 191 static inline struct page *
 192 get_and_lock_page(struct page_cache *c, sh_off_t key)
 193 {
 194   struct page *p = get_page(c, key);
 195
 196   add_tail(&c->locked_pages, &p->n);
 197   p->lock_count++;
 198   return p;
 199 }
 200
 201 struct page *
 202 pgc_read(struct page_cache *c, int fd, sh_off_t pos)
 203 {
 204   sh_off_t key;
 205   struct page *p;
 206   int s;
 207
 208   ASSERT(!(pos & (c->page_size - 1)));
 209   ASSERT(!(fd & ~(c->page_size - 1)));
 210   key = pos | fd;
 211   p = get_and_lock_page(c, key);
 212   if (!(p->flags & PG_FLAG_VALID))
 213     {
 214       /* FIXME: Use pread() */
 215       sh_seek(fd, pos, SEEK_SET);
 216       s = read(fd, p->data, c->page_size);
 217       if (s < 0)
 218         die("pgc_read(%d): %m", fd);
 219       if (s != (int) c->page_size)
 220         die("pgc_read(%d): incomplete page (only %d of %d)", s, c->page_size);
 221       p->flags |= PG_FLAG_VALID;
 222     }
 223   return p;
 224 }
 225
 226 struct page *
 227 pgc_get(struct page_cache *c, int fd, sh_off_t pos)
 228 {
 229   sh_off_t key;
 230   struct page *p;
 231
 232   ASSERT(!(pos & (c->page_size - 1)));
 233   ASSERT(!(fd & ~(c->page_size - 1)));
 234   key = pos | fd;
 235   p = get_and_lock_page(c, key);
 236   p->flags |= PG_FLAG_VALID | PG_FLAG_DIRTY;
 237   return p;
 238 }
 239
 240 void
 241 pgc_put(struct page_cache *c, struct page *p)
 242 {
 243   ASSERT(p->lock_count);
 244   if (--p->lock_count)
 245     return;
 246   rem_node(&p->n);
 247   if (p->flags & PG_FLAG_DIRTY)
 248     {
 249       add_tail(&c->dirty_pages, &p->n);
 250       c->free_count++;
 251     }
 252   else if (c->free_count < c->max_pages)
 253     {
 254       add_tail(&c->free_pages, &p->n);
 255       c->free_count++;
 256     }
 257   else
 258     {
 259       free(p);
 260       c->total_count--;
 261     }
 262 }
 263
 264 void
 265 pgc_put_dirty(struct page_cache *c, struct page *p)
 266 {
 267   p->flags |= PG_FLAG_DIRTY;
 268   pgc_put(c, p);
 269 }
 270
 271 byte *
 272 pgc_read_data(struct page_cache *c, int fd, sh_off_t pos, uns *len)
 273 {
 274   struct page *p;
 275   sh_off_t page = pos & ~(c->page_size - 1);
 276   uns offset = pos & (c->page_size - 1);
 277
 278   p = pgc_read(c, fd, page);
 279   pgc_put(c, p);
 280   *len = c->page_size - offset;
 281   return p->data + offset;
 282 }
 283
 284 #ifdef TEST
 285
 286 int main(int argc, char **argv)
 287 {
 288   struct page_cache *c = pgc_open(1024, 2);
 289   struct page *p, *q, *r;
 290   int fd = open("test", O_RDWR | O_CREAT | O_TRUNC, 0666);
 291   if (fd < 0)
 292     die("open: %m");
 293   pgc_debug(c);
 294   p = pgc_get(c, fd, 0);
 295   pgc_debug(c);
 296   strcpy(p->data, "one");
 297   pgc_put_dirty(c, p);
 298   pgc_debug(c);
 299   p = pgc_get(c, fd, 1024);
 300   pgc_debug(c);
 301   strcpy(p->data, "two");
 302   pgc_put_dirty(c, p);
 303   pgc_debug(c);
 304   p = pgc_get(c, fd, 2048);
 305   pgc_debug(c);
 306   strcpy(p->data, "three");
 307   pgc_put_dirty(c, p);
 308   pgc_debug(c);
 309   pgc_flush(c);
 310   pgc_debug(c);
 311   p = pgc_read(c, fd, 0);
 312   pgc_debug(c);
 313   q = pgc_read(c, fd, 1024);
 314   pgc_debug(c);
 315   r = pgc_read(c, fd, 2048);
 316   pgc_debug(c);
 317   pgc_put(c, p);
 318   pgc_put(c, q);
 319   pgc_put(c, r);
 320   pgc_debug(c);
 321   p = pgc_get(c, fd, 3072);
 322   pgc_debug(c);
 323   pgc_put(c, p);
 324   pgc_debug(c);
 325   pgc_cleanup(c);
 326   pgc_debug(c);
 327   pgc_close(c);
 328   return 0;
 329 }
 330
 331 #endif