/*
- * 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);
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;
}
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.
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);
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);
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
{
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++;
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;
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;
}
}
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);
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;
}