X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=lib%2Fpagecache.c;h=13ad36603fc7f69ea64c0aa9e527e74c88d8a7f5;hb=39d5e9acc6d93c07cbb408fe27144c8a485499ac;hp=2d8c1dbb379f787ef35471cbcb9d09b157e128f4;hpb=17b25548f7426be302e3ef36cf4b7ea4a2bf3edc;p=libucw.git

diff --git a/lib/pagecache.c b/lib/pagecache.c
index 2d8c1dbb..13ad3660 100644
--- a/lib/pagecache.c
+++ b/lib/pagecache.c
@@ -1,40 +1,51 @@
 /*
- *	Sherlock Library -- File Page Cache
+ *	UCW Library -- File Page Cache
  *
- *	(c) 1999 Martin Mares <mj@atrey.karlin.mff.cuni.cz>
+ *	(c) 1999--2002 Martin Mares <mj@ucw.cz>
+ *
+ *	This software may be freely distributed and used according to the terms
+ *	of the GNU Lesser General Public License.
  */
 
+#include "lib/lib.h"
+#include "lib/pagecache.h"
+#include "lib/lfs.h"
+
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 #include <fcntl.h>
 #include <unistd.h>
-
-#include "lib.h"
-#include "pagecache.h"
-#include "lfs.h"
+#include <alloca.h>
 
 struct page_cache {
-  list free_pages;			/* LRU queue of free pages */
-  list locked_pages;			/* List of locked pages */
-  list dirty_pages;			/* List of dirty pages */
+  list free_pages;			/* LRU queue of free non-dirty pages */
+  list locked_pages;			/* List of locked pages (starts with dirty ones) */
+  list dirty_pages;			/* List of free dirty pages */
   uns page_size;			/* Bytes per page (must be a power of two) */
   uns free_count;			/* Number of free / dirty pages */
   uns total_count;			/* Total number of pages */
   uns max_pages;			/* Maximum number of free pages */
   uns hash_size;			/* Hash table size */
+  uns stat_hit;				/* Number of cache hits */
+  uns stat_miss;			/* Number of cache misses */
+  uns stat_write;			/* Number of writes */
   list *hash_table;			/* List heads corresponding to hash buckets */
+#ifndef HAVE_PREAD
+  sh_off_t pos;				/* Current position in the file */
+  int pos_fd;				/* FD the position corresponds to */
+#endif
 };
 
-/* FIXME: Negations -> cast to sh_off_t */
+#define PAGE_NUMBER(pos) ((pos) & ~(sh_off_t)(c->page_size - 1))
+#define PAGE_OFFSET(pos) ((pos) & (c->page_size - 1))
 
 struct page_cache *
 pgc_open(uns page_size, uns max_pages)
 {
-  struct page_cache *c = xmalloc(sizeof(struct page_cache));
+  struct page_cache *c = xmalloc_zero(sizeof(struct page_cache));
   uns i;
 
-  bzero(c, sizeof(*c));
   init_list(&c->free_pages);
   init_list(&c->locked_pages);
   init_list(&c->dirty_pages);
@@ -44,6 +55,9 @@ pgc_open(uns page_size, uns max_pages)
   c->hash_table = xmalloc(sizeof(list) * c->hash_size);
   for(i=0; i<c->hash_size; i++)
     init_list(&c->hash_table[i]);
+#ifndef HAVE_PREAD
+  c->pos_fd = -1;
+#endif
   return c;
 }
 
@@ -54,63 +68,118 @@ pgc_close(struct page_cache *c)
   ASSERT(EMPTY_LIST(c->locked_pages));
   ASSERT(EMPTY_LIST(c->dirty_pages));
   ASSERT(EMPTY_LIST(c->free_pages));
-  free(c->hash_table);
-  free(c);
+  xfree(c->hash_table);
+  xfree(c);
 }
 
 static void
 pgc_debug_page(struct page *p)
 {
-  printf("\tk=%08x f=%x c=%d\n", (uns) p->key, p->flags, p->lock_count);
+  printf("\tp=%08x d=%d f=%x c=%d\n", (uns) p->pos, p->fd, p->flags, p->lock_count);
 }
 
 void
-pgc_debug(struct page_cache *c)
+pgc_debug(struct page_cache *c, int mode)
 {
   struct page *p;
 
   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);
-  puts("LRU list:");
-  WALK_LIST(p, c->free_pages)
-    pgc_debug_page(p);
-  puts("Locked list:");
-  WALK_LIST(p, c->locked_pages)
-    pgc_debug_page(p);
-  puts("Dirty list:");
-  WALK_LIST(p, c->dirty_pages)
-    pgc_debug_page(p);
+  printf(">> stats: %d hits, %d misses, %d writes\n", c->stat_hit, c->stat_miss, c->stat_write);
+  if (mode)
+    {
+      puts("LRU list:");
+      WALK_LIST(p, c->free_pages)
+	pgc_debug_page(p);
+      puts("Locked list:");
+      WALK_LIST(p, c->locked_pages)
+	pgc_debug_page(p);
+      puts("Dirty list:");
+      WALK_LIST(p, c->dirty_pages)
+	pgc_debug_page(p);
+    }
 }
 
 static void
 flush_page(struct page_cache *c, struct page *p)
 {
-  int fd = p->key & (c->page_size - 1);
-  sh_off_t pos = p->key & ~(c->page_size - 1);
   int s;
 
-  ASSERT((p->flags & PG_FLAG_DIRTY) && !p->lock_count);
-  /* FIXME: Use pwrite() */
-  sh_seek(fd, pos, SEEK_SET);
-  s = write(fd, p->data, c->page_size);
+  ASSERT(p->flags & PG_FLAG_DIRTY);
+#ifdef HAVE_PREAD
+  s = sh_pwrite(p->fd, p->data, c->page_size, p->pos);
+#else
+  if (c->pos != p->pos || c->pos_fd != (int) p->fd)
+    sh_seek(p->fd, p->pos, SEEK_SET);
+  s = write(p->fd, p->data, c->page_size);
+  c->pos = p->pos + s;
+  c->pos_fd = p->fd;
+#endif
   if (s < 0)
-    die("pgc_write(%d): %m", fd);
+    die("pgc_write(%d): %m", p->fd);
   if (s != (int) c->page_size)
-    die("pgc_write(%d): incomplete page (only %d of %d)", s, c->page_size);
+    die("pgc_write(%d): incomplete page (only %d of %d)", p->fd, s, c->page_size);
   p->flags &= ~PG_FLAG_DIRTY;
+  c->stat_write++;
+}
+
+static int
+flush_cmp(const void *X, const void *Y)
+{
+  struct page *x = *((struct page **)X);
+  struct page *y = *((struct page **)Y);
+
+  if (x->fd < y->fd)
+    return -1;
+  if (x->fd > y->fd)
+    return 1;
+  if (x->pos < y->pos)
+    return -1;
+  if (x->pos > y->pos)
+    return 1;
+  return 0;
+}
+
+static void
+flush_pages(struct page_cache *c, uns force)
+{
+  uns cnt = 0;
+  uns max = force ? ~0U : c->free_count / 2;
+  uns i;
+  struct page *p, *q, **req, **rr;
+
+  WALK_LIST(p, c->dirty_pages)
+    {
+      cnt++;
+      if (cnt >= max)
+	break;
+    }
+  req = rr = alloca(cnt * sizeof(struct page *));
+  i = cnt;
+  p = HEAD(c->dirty_pages);
+  while ((q = (struct page *) p->n.next) && i--)
+    {
+      rem_node(&p->n);
+      add_tail(&c->free_pages, &p->n);
+      *rr++ = p;
+      p = q;
+    }
+  qsort(req, cnt, sizeof(struct page *), flush_cmp);
+  for(i=0; i<cnt; i++)
+    flush_page(c, req[i]);
 }
 
 static inline uns
-hash_page(struct page_cache *c, sh_off_t key)
+hash_page(struct page_cache *c, sh_off_t pos, uns fd)
 {
-  return key % c->hash_size;		/* FIXME: Use better hash function */
+  return (pos + fd) % c->hash_size;
 }
 
 static struct page *
-get_page(struct page_cache *c, sh_off_t key)
+get_page(struct page_cache *c, sh_off_t pos, uns fd)
 {
   node *n;
   struct page *p;
-  uns hash = hash_page(c, key);
+  uns hash = hash_page(c, pos, fd);
 
   /*
    *  Return locked buffer for given page.
@@ -119,7 +188,7 @@ get_page(struct page_cache *c, sh_off_t key)
   WALK_LIST(n, c->hash_table[hash])
     {
       p = SKIP_BACK(struct page, hn, n);
-      if (p->key == key)
+      if (p->pos == pos && p->fd == fd)
 	{
 	  /* Found in the cache */
 	  rem_node(&p->n);
@@ -141,15 +210,17 @@ get_page(struct page_cache *c, sh_off_t key)
       if (!p->n.next)
 	{
 	  /* There are only dirty pages here */
-	  p = HEAD(c->dirty_pages);
-	  flush_page(c, p);
+	  flush_pages(c, 0);
+	  p = HEAD(c->free_pages);
+	  ASSERT(p->n.next);
 	}
       ASSERT(!p->lock_count);
       rem_node(&p->n);
       rem_node(&p->hn);
       c->free_count--;
     }
-  p->key = key;
+  p->pos = pos;
+  p->fd = fd;
   p->flags = 0;
   p->lock_count = 0;
   add_tail(&c->hash_table[hash], &p->hn);
@@ -160,14 +231,13 @@ void
 pgc_flush(struct page_cache *c)
 {
   struct page *p;
-  node *n;
 
-  WALK_LIST_DELSAFE(p, n, c->dirty_pages)
-    {
+  flush_pages(c, 1);
+  WALK_LIST(p, c->locked_pages)
+    if (p->flags & PG_FLAG_DIRTY)
       flush_page(c, p);
-      rem_node(&p->n);
-      add_tail(&c->free_pages, &p->n);
-    }
+    else
+      break;
 }
 
 void
@@ -181,17 +251,18 @@ pgc_cleanup(struct page_cache *c)
     {
       ASSERT(!(p->flags & PG_FLAG_DIRTY) && !p->lock_count);
       rem_node(&p->n);
+      rem_node(&p->hn);
       c->free_count--;
       c->total_count--;
-      free(p);
+      xfree(p);
     }
   ASSERT(!c->free_count);
 }
 
 static inline struct page *
-get_and_lock_page(struct page_cache *c, sh_off_t key)
+get_and_lock_page(struct page_cache *c, sh_off_t pos, uns fd)
 {
-  struct page *p = get_page(c, key);
+  struct page *p = get_page(c, pos, fd);
 
   add_tail(&c->locked_pages, &p->n);
   p->lock_count++;
@@ -201,23 +272,29 @@ get_and_lock_page(struct page_cache *c, sh_off_t key)
 struct page *
 pgc_read(struct page_cache *c, int fd, sh_off_t pos)
 {
-  sh_off_t key;
   struct page *p;
   int s;
 
-  ASSERT(!(pos & (c->page_size - 1)));
-  ASSERT(!(fd & ~(c->page_size - 1)));
-  key = pos | fd;
-  p = get_and_lock_page(c, key);
-  if (!(p->flags & PG_FLAG_VALID))
+  ASSERT(!PAGE_OFFSET(pos));
+  p = get_and_lock_page(c, pos, fd);
+  if (p->flags & PG_FLAG_VALID)
+    c->stat_hit++;
+  else
     {
-      /* FIXME: Use pread() */
-      sh_seek(fd, pos, SEEK_SET);
+      c->stat_miss++;
+#ifdef HAVE_PREAD
+      s = sh_pread(fd, p->data, c->page_size, pos);
+#else
+      if (c->pos != pos || c->pos_fd != (int)fd)
+	sh_seek(fd, pos, SEEK_SET);
       s = read(fd, p->data, c->page_size);
+      c->pos = pos + s;
+      c->pos_fd = fd;
+#endif
       if (s < 0)
 	die("pgc_read(%d): %m", fd);
       if (s != (int) c->page_size)
-	die("pgc_read(%d): incomplete page (only %d of %d)", s, c->page_size);
+	die("pgc_read(%d): incomplete page (only %d of %d)", p->fd, s, c->page_size);
       p->flags |= PG_FLAG_VALID;
     }
   return p;
@@ -226,13 +303,22 @@ pgc_read(struct page_cache *c, int fd, sh_off_t pos)
 struct page *
 pgc_get(struct page_cache *c, int fd, sh_off_t pos)
 {
-  sh_off_t key;
   struct page *p;
 
-  ASSERT(!(pos & (c->page_size - 1)));
-  ASSERT(!(fd & ~(c->page_size - 1)));
-  key = pos | fd;
-  p = get_and_lock_page(c, key);
+  ASSERT(!PAGE_OFFSET(pos));
+  p = get_and_lock_page(c, pos, fd);
+  p->flags |= PG_FLAG_VALID | PG_FLAG_DIRTY;
+  return p;
+}
+
+struct page *
+pgc_get_zero(struct page_cache *c, int fd, sh_off_t pos)
+{
+  struct page *p;
+
+  ASSERT(!PAGE_OFFSET(pos));
+  p = get_and_lock_page(c, pos, fd);
+  bzero(p->data, c->page_size);
   p->flags |= PG_FLAG_VALID | PG_FLAG_DIRTY;
   return p;
 }
@@ -256,24 +342,30 @@ pgc_put(struct page_cache *c, struct page *p)
     }
   else
     {
-      free(p);
+      rem_node(&p->hn);
+      xfree(p);
       c->total_count--;
     }
 }
 
 void
-pgc_put_dirty(struct page_cache *c, struct page *p)
+pgc_mark_dirty(struct page_cache *c, struct page *p)
 {
-  p->flags |= PG_FLAG_DIRTY;
-  pgc_put(c, p);
+  ASSERT(p->lock_count);
+  if (!(p->flags & PG_FLAG_DIRTY))
+    {
+      p->flags |= PG_FLAG_DIRTY;
+      rem_node(&p->n);
+      add_head(&c->locked_pages, &p->n);
+    }
 }
 
 byte *
 pgc_read_data(struct page_cache *c, int fd, sh_off_t pos, uns *len)
 {
   struct page *p;
-  sh_off_t page = pos & ~(c->page_size - 1);
-  uns offset = pos & (c->page_size - 1);
+  sh_off_t page = PAGE_NUMBER(pos);
+  uns offset = PAGE_OFFSET(pos);
 
   p = pgc_read(c, fd, page);
   pgc_put(c, p);
@@ -290,40 +382,46 @@ int main(int argc, char **argv)
   int fd = open("test", O_RDWR | O_CREAT | O_TRUNC, 0666);
   if (fd < 0)
     die("open: %m");
-  pgc_debug(c);
+  pgc_debug(c, 1);
   p = pgc_get(c, fd, 0);
-  pgc_debug(c);
+  pgc_debug(c, 1);
   strcpy(p->data, "one");
-  pgc_put_dirty(c, p);
-  pgc_debug(c);
+  pgc_put(c, p);
+  pgc_debug(c, 1);
   p = pgc_get(c, fd, 1024);
-  pgc_debug(c);
+  pgc_debug(c, 1);
   strcpy(p->data, "two");
-  pgc_put_dirty(c, p);
-  pgc_debug(c);
+  pgc_put(c, p);
+  pgc_debug(c, 1);
   p = pgc_get(c, fd, 2048);
-  pgc_debug(c);
+  pgc_debug(c, 1);
   strcpy(p->data, "three");
-  pgc_put_dirty(c, p);
-  pgc_debug(c);
+  pgc_put(c, p);
+  pgc_debug(c, 1);
   pgc_flush(c);
-  pgc_debug(c);
+  pgc_debug(c, 1);
   p = pgc_read(c, fd, 0);
-  pgc_debug(c);
+  pgc_debug(c, 1);
+  strcpy(p->data, "odin");
+  pgc_mark_dirty(c, p);
+  pgc_debug(c, 1);
+  pgc_flush(c);
+  pgc_debug(c, 1);
   q = pgc_read(c, fd, 1024);
-  pgc_debug(c);
+  pgc_debug(c, 1);
   r = pgc_read(c, fd, 2048);
-  pgc_debug(c);
+  pgc_debug(c, 1);
   pgc_put(c, p);
   pgc_put(c, q);
   pgc_put(c, r);
-  pgc_debug(c);
+  pgc_debug(c, 1);
   p = pgc_get(c, fd, 3072);
-  pgc_debug(c);
+  pgc_debug(c, 1);
+  strcpy(p->data, "four");
   pgc_put(c, p);
-  pgc_debug(c);
+  pgc_debug(c, 1);
   pgc_cleanup(c);
-  pgc_debug(c);
+  pgc_debug(c, 1);
   pgc_close(c);
   return 0;
 }