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