lib/pagecache.c

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