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