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(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 = sh_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)", p->fd, 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   p = get_and_lock_page(c, pos, fd);
 277   if (p->flags & PG_FLAG_VALID)
 278     c->stat_hit++;
 279   else
 280     {
 281       c->stat_miss++;
 282 #ifdef SHERLOCK_HAVE_PREAD
 283       s = sh_pread(fd, p->data, c->page_size, pos);
 284 #else
 285       if (c->pos != pos || c->pos_fd != fd)
 286         sh_seek(fd, pos, SEEK_SET);
 287       s = read(fd, p->data, c->page_size);
 288       c->pos = pos + s;
 289       c->pos_fd = fd;
 290 #endif
 291       if (s < 0)
 292         die("pgc_read(%d): %m", fd);
 293       if (s != (int) c->page_size)
 294         die("pgc_read(%d): incomplete page (only %d of %d)", p->fd, s, c->page_size);
 295       p->flags |= PG_FLAG_VALID;
 296     }
 297   return p;
 298 }
 299
 300 struct page *
 301 pgc_get(struct page_cache *c, int fd, sh_off_t pos)
 302 {
 303   struct page *p;
 304
 305   ASSERT(!PAGE_OFFSET(pos));
 306   p = get_and_lock_page(c, pos, fd);
 307   p->flags |= PG_FLAG_VALID | PG_FLAG_DIRTY;
 308   return p;
 309 }
 310
 311 struct page *
 312 pgc_get_zero(struct page_cache *c, int fd, sh_off_t pos)
 313 {
 314   struct page *p;
 315
 316   ASSERT(!PAGE_OFFSET(pos));
 317   p = get_and_lock_page(c, pos, fd);
 318   bzero(p->data, c->page_size);
 319   p->flags |= PG_FLAG_VALID | PG_FLAG_DIRTY;
 320   return p;
 321 }
 322
 323 void
 324 pgc_put(struct page_cache *c, struct page *p)
 325 {
 326   ASSERT(p->lock_count);
 327   if (--p->lock_count)
 328     return;
 329   rem_node(&p->n);
 330   if (p->flags & PG_FLAG_DIRTY)
 331     {
 332       add_tail(&c->dirty_pages, &p->n);
 333       c->free_count++;
 334     }
 335   else if (c->free_count < c->max_pages)
 336     {
 337       add_tail(&c->free_pages, &p->n);
 338       c->free_count++;
 339     }
 340   else
 341     {
 342       rem_node(&p->hn);
 343       free(p);
 344       c->total_count--;
 345     }
 346 }
 347
 348 void
 349 pgc_mark_dirty(struct page_cache *c, struct page *p)
 350 {
 351   ASSERT(p->lock_count);
 352   if (!(p->flags & PG_FLAG_DIRTY))
 353     {
 354       p->flags |= PG_FLAG_DIRTY;
 355       rem_node(&p->n);
 356       add_head(&c->locked_pages, &p->n);
 357     }
 358 }
 359
 360 byte *
 361 pgc_read_data(struct page_cache *c, int fd, sh_off_t pos, uns *len)
 362 {
 363   struct page *p;
 364   sh_off_t page = PAGE_NUMBER(pos);
 365   uns offset = PAGE_OFFSET(pos);
 366
 367   p = pgc_read(c, fd, page);
 368   pgc_put(c, p);
 369   *len = c->page_size - offset;
 370   return p->data + offset;
 371 }
 372
 373 #ifdef TEST
 374
 375 int main(int argc, char **argv)
 376 {
 377   struct page_cache *c = pgc_open(1024, 2);
 378   struct page *p, *q, *r;
 379   int fd = open("test", O_RDWR | O_CREAT | O_TRUNC, 0666);
 380   if (fd < 0)
 381     die("open: %m");
 382   pgc_debug(c, 1);
 383   p = pgc_get(c, fd, 0);
 384   pgc_debug(c, 1);
 385   strcpy(p->data, "one");
 386   pgc_put(c, p);
 387   pgc_debug(c, 1);
 388   p = pgc_get(c, fd, 1024);
 389   pgc_debug(c, 1);
 390   strcpy(p->data, "two");
 391   pgc_put(c, p);
 392   pgc_debug(c, 1);
 393   p = pgc_get(c, fd, 2048);
 394   pgc_debug(c, 1);
 395   strcpy(p->data, "three");
 396   pgc_put(c, p);
 397   pgc_debug(c, 1);
 398   pgc_flush(c);
 399   pgc_debug(c, 1);
 400   p = pgc_read(c, fd, 0);
 401   pgc_debug(c, 1);
 402   strcpy(p->data, "odin");
 403   pgc_mark_dirty(c, p);
 404   pgc_debug(c, 1);
 405   pgc_flush(c);
 406   pgc_debug(c, 1);
 407   q = pgc_read(c, fd, 1024);
 408   pgc_debug(c, 1);
 409   r = pgc_read(c, fd, 2048);
 410   pgc_debug(c, 1);
 411   pgc_put(c, p);
 412   pgc_put(c, q);
 413   pgc_put(c, r);
 414   pgc_debug(c, 1);
 415   p = pgc_get(c, fd, 3072);
 416   pgc_debug(c, 1);
 417   strcpy(p->data, "four");
 418   pgc_put(c, p);
 419   pgc_debug(c, 1);
 420   pgc_cleanup(c);
 421   pgc_debug(c, 1);
 422   pgc_close(c);
 423   return 0;
 424 }
 425
 426 #endif