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