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