2 * Sherlock Library -- File Page Cache
4 * (c) 1999 Martin Mares <mj@atrey.karlin.mff.cuni.cz>
14 #include "pagecache.h"
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 */
32 #define PAGE_NUMBER(pos) ((pos) & ~(sh_off_t)(c->page_size - 1))
33 #define PAGE_OFFSET(pos) ((pos) & (c->page_size - 1))
35 #define KEY_PAGE(key) PAGE_NUMBER(key)
36 #define KEY_FD(key) PAGE_OFFSET(key)
39 pgc_open(uns page_size, uns max_pages)
41 struct page_cache *c = xmalloc(sizeof(struct page_cache));
45 init_list(&c->free_pages);
46 init_list(&c->locked_pages);
47 init_list(&c->dirty_pages);
48 c->page_size = page_size;
49 c->max_pages = max_pages;
50 c->hash_size = nextprime(c->max_pages);
51 c->hash_table = xmalloc(sizeof(list) * c->hash_size);
52 for(i=0; i<c->hash_size; i++)
53 init_list(&c->hash_table[i]);
58 pgc_close(struct page_cache *c)
61 ASSERT(EMPTY_LIST(c->locked_pages));
62 ASSERT(EMPTY_LIST(c->dirty_pages));
63 ASSERT(EMPTY_LIST(c->free_pages));
69 pgc_debug_page(struct page *p)
71 printf("\tk=%08x f=%x c=%d\n", (uns) p->key, p->flags, p->lock_count);
75 pgc_debug(struct page_cache *c, int mode)
79 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);
80 printf(">> stats: %d hits, %d misses, %d writes\n", c->stat_hit, c->stat_miss, c->stat_write);
84 WALK_LIST(p, c->free_pages)
87 WALK_LIST(p, c->locked_pages)
90 WALK_LIST(p, c->dirty_pages)
96 flush_page(struct page_cache *c, struct page *p)
98 int fd = KEY_FD(p->key);
99 sh_off_t pos = KEY_PAGE(p->key);
102 ASSERT(p->flags & PG_FLAG_DIRTY);
103 /* FIXME: Use pwrite() */
104 sh_seek(fd, pos, SEEK_SET);
105 s = write(fd, p->data, c->page_size);
107 die("pgc_write(%d): %m", fd);
108 if (s != (int) c->page_size)
109 die("pgc_write(%d): incomplete page (only %d of %d)", s, c->page_size);
110 p->flags &= ~PG_FLAG_DIRTY;
115 hash_page(struct page_cache *c, sh_off_t key)
117 return key % c->hash_size; /* FIXME: Use better hash function */
121 get_page(struct page_cache *c, sh_off_t key)
125 uns hash = hash_page(c, key);
128 * Return locked buffer for given page.
131 WALK_LIST(n, c->hash_table[hash])
133 p = SKIP_BACK(struct page, hn, n);
136 /* Found in the cache */
143 if (c->total_count < c->max_pages || !c->free_count)
145 /* Enough free space, expand the cache */
146 p = xmalloc(sizeof(struct page) + c->page_size);
151 /* Discard the oldest unlocked page */
152 p = HEAD(c->free_pages);
155 /* There are only dirty pages here */
156 p = HEAD(c->dirty_pages);
159 ASSERT(!p->lock_count);
167 add_tail(&c->hash_table[hash], &p->hn);
172 pgc_flush(struct page_cache *c)
177 WALK_LIST_DELSAFE(p, n, c->dirty_pages)
181 add_tail(&c->free_pages, &p->n);
183 WALK_LIST(p, c->locked_pages)
184 if (p->flags & PG_FLAG_DIRTY)
191 pgc_cleanup(struct page_cache *c)
197 WALK_LIST_DELSAFE(p, n, c->free_pages)
199 ASSERT(!(p->flags & PG_FLAG_DIRTY) && !p->lock_count);
205 ASSERT(!c->free_count);
208 static inline struct page *
209 get_and_lock_page(struct page_cache *c, sh_off_t key)
211 struct page *p = get_page(c, key);
213 add_tail(&c->locked_pages, &p->n);
219 pgc_read(struct page_cache *c, int fd, sh_off_t pos)
225 ASSERT(!PAGE_OFFSET(pos));
226 ASSERT(!PAGE_NUMBER(fd));
228 p = get_and_lock_page(c, key);
229 if (p->flags & PG_FLAG_VALID)
234 /* FIXME: Use pread() */
235 sh_seek(fd, pos, SEEK_SET);
236 s = read(fd, p->data, c->page_size);
238 die("pgc_read(%d): %m", fd);
239 if (s != (int) c->page_size)
240 die("pgc_read(%d): incomplete page (only %d of %d)", s, c->page_size);
241 p->flags |= PG_FLAG_VALID;
247 pgc_get(struct page_cache *c, int fd, sh_off_t pos)
252 ASSERT(!PAGE_OFFSET(pos));
253 ASSERT(!PAGE_NUMBER(fd));
255 p = get_and_lock_page(c, key);
256 p->flags |= PG_FLAG_VALID | PG_FLAG_DIRTY;
261 pgc_put(struct page_cache *c, struct page *p)
263 ASSERT(p->lock_count);
267 if (p->flags & PG_FLAG_DIRTY)
269 add_tail(&c->dirty_pages, &p->n);
272 else if (c->free_count < c->max_pages)
274 add_tail(&c->free_pages, &p->n);
285 pgc_mark_dirty(struct page_cache *c, struct page *p)
287 ASSERT(p->lock_count);
288 if (!(p->flags & PG_FLAG_DIRTY))
290 p->flags |= PG_FLAG_DIRTY;
292 add_head(&c->locked_pages, &p->n);
297 pgc_read_data(struct page_cache *c, int fd, sh_off_t pos, uns *len)
300 sh_off_t page = PAGE_NUMBER(pos);
301 uns offset = PAGE_OFFSET(pos);
303 p = pgc_read(c, fd, page);
305 *len = c->page_size - offset;
306 return p->data + offset;
311 int main(int argc, char **argv)
313 struct page_cache *c = pgc_open(1024, 2);
314 struct page *p, *q, *r;
315 int fd = open("test", O_RDWR | O_CREAT | O_TRUNC, 0666);
319 p = pgc_get(c, fd, 0);
321 strcpy(p->data, "one");
324 p = pgc_get(c, fd, 1024);
326 strcpy(p->data, "two");
329 p = pgc_get(c, fd, 2048);
331 strcpy(p->data, "three");
336 p = pgc_read(c, fd, 0);
338 strcpy(p->data, "odin");
339 pgc_mark_dirty(c, p);
343 q = pgc_read(c, fd, 1024);
345 r = pgc_read(c, fd, 2048);
351 p = pgc_get(c, fd, 3072);