lib/pagecache.c

   1 /*
   2  *      Sherlock Library -- File Page Cache
   3  *
   4  *      (c) 1999--2002 Martin Mares <mj@ucw.cz>
   5  *
   6  *      This software may be freely distributed and used according to the terms
   7  *      of the GNU Lesser General Public License.
   8  */
   9
  10 #include "lib/lib.h"
  11 #include "lib/pagecache.h"
  12 #include "lib/lfs.h"
  13
  14 #include <stdio.h>
  15 #include <stdlib.h>
  16 #include <string.h>
  17 #include <fcntl.h>
  18 #include <unistd.h>
  19 #include <alloca.h>
  20
  21 struct page_cache {
  22   list free_pages;                      /* LRU queue of free non-dirty pages */
  23   list locked_pages;                    /* List of locked pages (starts with dirty ones) */
  24   list dirty_pages;                     /* List of free dirty pages */
  25   uns page_size;                        /* Bytes per page (must be a power of two) */
  26   uns free_count;                       /* Number of free / dirty pages */
  27   uns total_count;                      /* Total number of pages */
  28   uns max_pages;                        /* Maximum number of free pages */
  29   uns hash_size;                        /* Hash table size */
  30   uns stat_hit;                         /* Number of cache hits */
  31   uns stat_miss;                        /* Number of cache misses */
  32   uns stat_write;                       /* Number of writes */
  33   list *hash_table;                     /* List heads corresponding to hash buckets */
  34 #ifndef SHERLOCK_HAVE_PREAD
  35   sh_off_t pos;                         /* Current position in the file */
  36   int pos_fd;                           /* FD the position corresponds to */
  37 #endif
  38 };
  39
  40 #define PAGE_NUMBER(pos) ((pos) & ~(sh_off_t)(c->page_size - 1))
  41 #define PAGE_OFFSET(pos) ((pos) & (c->page_size - 1))
  42
  43 struct page_cache *
  44 pgc_open(uns page_size, uns max_pages)
  45 {
  46   struct page_cache *c = xmalloc_zero(sizeof(struct page_cache));
  47   uns i;
  48
  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   xfree(c->hash_table);
  72   xfree(c);
  73 }
  74
  75 static void
  76 pgc_debug_page(struct page *p)
  77 {
  78   printf("\tp=%08x d=%d f=%x c=%d\n", (uns) p->pos, p->fd, 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 s;
 106
 107   ASSERT(p->flags & PG_FLAG_DIRTY);
 108 #ifdef SHERLOCK_HAVE_PREAD
 109   s = sh_pwrite(p->fd, p->data, c->page_size, p->pos);
 110 #else
 111   if (c->pos != p->pos || c->pos_fd != (int) p->fd)
 112     sh_seek(p->fd, p->pos, SEEK_SET);
 113   s = write(p->fd, p->data, c->page_size);
 114   c->pos = p->pos + s;
 115   c->pos_fd = p->fd;
 116 #endif
 117   if (s < 0)
 118     die("pgc_write(%d): %m", p->fd);
 119   if (s != (int) c->page_size)
 120     die("pgc_write(%d): incomplete page (only %d of %d)", p->fd, s, c->page_size);
 121   p->flags &= ~PG_FLAG_DIRTY;
 122   c->stat_write++;
 123 }
 124
 125 static int
 126 flush_cmp(const void *X, const void *Y)
 127 {
 128   struct page *x = *((struct page **)X);
 129   struct page *y = *((struct page **)Y);
 130
 131   if (x->fd < y->fd)
 132     return -1;
 133   if (x->fd > y->fd)
 134     return 1;
 135   if (x->pos < y->pos)
 136     return -1;
 137   if (x->pos > y->pos)
 138     return 1;
 139   return 0;
 140 }
 141
 142 static void
 143 flush_pages(struct page_cache *c, uns force)
 144 {
 145   uns cnt = 0;
 146   uns max = force ? ~0U : c->free_count / 2;
 147   uns i;
 148   struct page *p, *q, **req, **rr;
 149
 150   WALK_LIST(p, c->dirty_pages)
 151     {
 152       cnt++;
 153       if (cnt >= max)
 154         break;
 155     }
 156   req = rr = alloca(cnt * sizeof(struct page *));
 157   i = cnt;
 158   p = HEAD(c->dirty_pages);
 159   while ((q = (struct page *) p->n.next) && i--)
 160     {
 161       rem_node(&p->n);
 162       add_tail(&c->free_pages, &p->n);
 163       *rr++ = p;
 164       p = q;
 165     }
 166   qsort(req, cnt, sizeof(struct page *), flush_cmp);
 167   for(i=0; i<cnt; i++)
 168     flush_page(c, req[i]);
 169 }
 170
 171 static inline uns
 172 hash_page(struct page_cache *c, sh_off_t pos, uns fd)
 173 {
 174   return (pos + fd) % c->hash_size;
 175 }
 176
 177 static struct page *
 178 get_page(struct page_cache *c, sh_off_t pos, uns fd)
 179 {
 180   node *n;
 181   struct page *p;
 182   uns hash = hash_page(c, pos, fd);
 183
 184   /*
 185    *  Return locked buffer for given page.
 186    */
 187
 188   WALK_LIST(n, c->hash_table[hash])
 189     {
 190       p = SKIP_BACK(struct page, hn, n);
 191       if (p->pos == pos && p->fd == fd)
 192         {
 193           /* Found in the cache */
 194           rem_node(&p->n);
 195           if (!p->lock_count)
 196             c->free_count--;
 197           return p;
 198         }
 199     }
 200   if (c->total_count < c->max_pages || !c->free_count)
 201     {
 202       /* Enough free space, expand the cache */
 203       p = xmalloc(sizeof(struct page) + c->page_size);
 204       c->total_count++;
 205     }
 206   else
 207     {
 208       /* Discard the oldest unlocked page */
 209       p = HEAD(c->free_pages);
 210       if (!p->n.next)
 211         {
 212           /* There are only dirty pages here */
 213           flush_pages(c, 0);
 214           p = HEAD(c->free_pages);
 215           ASSERT(p->n.next);
 216         }
 217       ASSERT(!p->lock_count);
 218       rem_node(&p->n);
 219       rem_node(&p->hn);
 220       c->free_count--;
 221     }
 222   p->pos = pos;
 223   p->fd = fd;
 224   p->flags = 0;
 225   p->lock_count = 0;
 226   add_tail(&c->hash_table[hash], &p->hn);
 227   return p;
 228 }
 229
 230 void
 231 pgc_flush(struct page_cache *c)
 232 {
 233   struct page *p;
 234
 235   flush_pages(c, 1);
 236   WALK_LIST(p, c->locked_pages)
 237     if (p->flags & PG_FLAG_DIRTY)
 238       flush_page(c, p);
 239     else
 240       break;
 241 }
 242
 243 void
 244 pgc_cleanup(struct page_cache *c)
 245 {
 246   struct page *p;
 247   node *n;
 248
 249   pgc_flush(c);
 250   WALK_LIST_DELSAFE(p, n, c->free_pages)
 251     {
 252       ASSERT(!(p->flags & PG_FLAG_DIRTY) && !p->lock_count);
 253       rem_node(&p->n);
 254       rem_node(&p->hn);
 255       c->free_count--;
 256       c->total_count--;
 257       xfree(p);
 258     }
 259   ASSERT(!c->free_count);
 260 }
 261
 262 static inline struct page *
 263 get_and_lock_page(struct page_cache *c, sh_off_t pos, uns fd)
 264 {
 265   struct page *p = get_page(c, pos, fd);
 266
 267   add_tail(&c->locked_pages, &p->n);
 268   p->lock_count++;
 269   return p;
 270 }
 271
 272 struct page *
 273 pgc_read(struct page_cache *c, int fd, sh_off_t pos)
 274 {
 275   struct page *p;
 276   int s;
 277
 278   ASSERT(!PAGE_OFFSET(pos));
 279   p = get_and_lock_page(c, pos, fd);
 280   if (p->flags & PG_FLAG_VALID)
 281     c->stat_hit++;
 282   else
 283     {
 284       c->stat_miss++;
 285 #ifdef SHERLOCK_HAVE_PREAD
 286       s = sh_pread(fd, p->data, c->page_size, pos);
 287 #else
 288       if (c->pos != pos || c->pos_fd != (int)fd)
 289         sh_seek(fd, pos, SEEK_SET);
 290       s = read(fd, p->data, c->page_size);
 291       c->pos = pos + s;
 292       c->pos_fd = fd;
 293 #endif
 294       if (s < 0)
 295         die("pgc_read(%d): %m", fd);
 296       if (s != (int) c->page_size)
 297         die("pgc_read(%d): incomplete page (only %d of %d)", p->fd, s, c->page_size);
 298       p->flags |= PG_FLAG_VALID;
 299     }
 300   return p;
 301 }
 302
 303 struct page *
 304 pgc_get(struct page_cache *c, int fd, sh_off_t pos)
 305 {
 306   struct page *p;
 307
 308   ASSERT(!PAGE_OFFSET(pos));
 309   p = get_and_lock_page(c, pos, fd);
 310   p->flags |= PG_FLAG_VALID | PG_FLAG_DIRTY;
 311   return p;
 312 }
 313
 314 struct page *
 315 pgc_get_zero(struct page_cache *c, int fd, sh_off_t pos)
 316 {
 317   struct page *p;
 318
 319   ASSERT(!PAGE_OFFSET(pos));
 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       xfree(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