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