2 * Sherlock Library -- File Page Cache
4 * (c) 1999--2000 Martin Mares <mj@ucw.cz>
8 #include "lib/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 */
30 #ifndef SHERLOCK_HAVE_PREAD
31 sh_off_t pos; /* Current position in the file */
32 int pos_fd; /* FD the position corresponds to */
36 #define PAGE_NUMBER(pos) ((pos) & ~(sh_off_t)(c->page_size - 1))
37 #define PAGE_OFFSET(pos) ((pos) & (c->page_size - 1))
40 pgc_open(uns page_size, uns max_pages)
42 struct page_cache *c = xmalloc_zero(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]);
54 #ifndef SHERLOCK_HAVE_PREAD
61 pgc_close(struct page_cache *c)
64 ASSERT(EMPTY_LIST(c->locked_pages));
65 ASSERT(EMPTY_LIST(c->dirty_pages));
66 ASSERT(EMPTY_LIST(c->free_pages));
72 pgc_debug_page(struct page *p)
74 printf("\tp=%08x d=%d f=%x c=%d\n", (uns) p->pos, p->fd, p->flags, p->lock_count);
78 pgc_debug(struct page_cache *c, int mode)
82 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);
83 printf(">> stats: %d hits, %d misses, %d writes\n", c->stat_hit, c->stat_miss, c->stat_write);
87 WALK_LIST(p, c->free_pages)
90 WALK_LIST(p, c->locked_pages)
93 WALK_LIST(p, c->dirty_pages)
99 flush_page(struct page_cache *c, struct page *p)
103 ASSERT(p->flags & PG_FLAG_DIRTY);
104 #ifdef SHERLOCK_HAVE_PREAD
105 s = sh_pwrite(p->fd, p->data, c->page_size, p->pos);
107 if (c->pos != p->pos || c->pos_fd != p->fd)
108 sh_seek(p->fd, p->pos, SEEK_SET);
109 s = write(p->fd, p->data, c->page_size);
114 die("pgc_write(%d): %m", p->fd);
115 if (s != (int) c->page_size)
116 die("pgc_write(%d): incomplete page (only %d of %d)", p->fd, s, c->page_size);
117 p->flags &= ~PG_FLAG_DIRTY;
122 flush_cmp(const void *X, const void *Y)
124 struct page *x = *((struct page **)X);
125 struct page *y = *((struct page **)Y);
139 flush_pages(struct page_cache *c, uns force)
142 uns max = force ? ~0 : c->free_count / 2; /* FIXME: Needs tuning */
144 struct page *p, *q, **req, **rr;
146 WALK_LIST(p, c->dirty_pages)
152 req = rr = alloca(cnt * sizeof(struct page *));
154 p = HEAD(c->dirty_pages);
155 while ((q = (struct page *) p->n.next) && i--)
158 add_tail(&c->free_pages, &p->n);
162 qsort(req, cnt, sizeof(struct page *), flush_cmp);
164 flush_page(c, req[i]);
168 hash_page(struct page_cache *c, sh_off_t pos, uns fd)
170 return (pos + fd) % c->hash_size;
174 get_page(struct page_cache *c, sh_off_t pos, uns fd)
178 uns hash = hash_page(c, pos, fd);
181 * Return locked buffer for given page.
184 WALK_LIST(n, c->hash_table[hash])
186 p = SKIP_BACK(struct page, hn, n);
187 if (p->pos == pos && p->fd == fd)
189 /* Found in the cache */
196 if (c->total_count < c->max_pages || !c->free_count)
198 /* Enough free space, expand the cache */
199 p = xmalloc(sizeof(struct page) + c->page_size);
204 /* Discard the oldest unlocked page */
205 p = HEAD(c->free_pages);
208 /* There are only dirty pages here */
210 p = HEAD(c->free_pages);
213 ASSERT(!p->lock_count);
222 add_tail(&c->hash_table[hash], &p->hn);
227 pgc_flush(struct page_cache *c)
232 WALK_LIST(p, c->locked_pages)
233 if (p->flags & PG_FLAG_DIRTY)
240 pgc_cleanup(struct page_cache *c)
246 WALK_LIST_DELSAFE(p, n, c->free_pages)
248 ASSERT(!(p->flags & PG_FLAG_DIRTY) && !p->lock_count);
255 ASSERT(!c->free_count);
258 static inline struct page *
259 get_and_lock_page(struct page_cache *c, sh_off_t pos, uns fd)
261 struct page *p = get_page(c, pos, fd);
263 add_tail(&c->locked_pages, &p->n);
269 pgc_read(struct page_cache *c, int fd, sh_off_t pos)
274 ASSERT(!PAGE_OFFSET(pos));
275 p = get_and_lock_page(c, pos, fd);
276 if (p->flags & PG_FLAG_VALID)
281 #ifdef SHERLOCK_HAVE_PREAD
282 s = sh_pread(fd, p->data, c->page_size, pos);
284 if (c->pos != pos || c->pos_fd != fd)
285 sh_seek(fd, pos, SEEK_SET);
286 s = read(fd, p->data, c->page_size);
291 die("pgc_read(%d): %m", fd);
292 if (s != (int) c->page_size)
293 die("pgc_read(%d): incomplete page (only %d of %d)", p->fd, s, c->page_size);
294 p->flags |= PG_FLAG_VALID;
300 pgc_get(struct page_cache *c, int fd, sh_off_t pos)
304 ASSERT(!PAGE_OFFSET(pos));
305 p = get_and_lock_page(c, pos, fd);
306 p->flags |= PG_FLAG_VALID | PG_FLAG_DIRTY;
311 pgc_get_zero(struct page_cache *c, int fd, sh_off_t pos)
315 ASSERT(!PAGE_OFFSET(pos));
316 p = get_and_lock_page(c, pos, fd);
317 bzero(p->data, c->page_size);
318 p->flags |= PG_FLAG_VALID | PG_FLAG_DIRTY;
323 pgc_put(struct page_cache *c, struct page *p)
325 ASSERT(p->lock_count);
329 if (p->flags & PG_FLAG_DIRTY)
331 add_tail(&c->dirty_pages, &p->n);
334 else if (c->free_count < c->max_pages)
336 add_tail(&c->free_pages, &p->n);
348 pgc_mark_dirty(struct page_cache *c, struct page *p)
350 ASSERT(p->lock_count);
351 if (!(p->flags & PG_FLAG_DIRTY))
353 p->flags |= PG_FLAG_DIRTY;
355 add_head(&c->locked_pages, &p->n);
360 pgc_read_data(struct page_cache *c, int fd, sh_off_t pos, uns *len)
363 sh_off_t page = PAGE_NUMBER(pos);
364 uns offset = PAGE_OFFSET(pos);
366 p = pgc_read(c, fd, page);
368 *len = c->page_size - offset;
369 return p->data + offset;
374 int main(int argc, char **argv)
376 struct page_cache *c = pgc_open(1024, 2);
377 struct page *p, *q, *r;
378 int fd = open("test", O_RDWR | O_CREAT | O_TRUNC, 0666);
382 p = pgc_get(c, fd, 0);
384 strcpy(p->data, "one");
387 p = pgc_get(c, fd, 1024);
389 strcpy(p->data, "two");
392 p = pgc_get(c, fd, 2048);
394 strcpy(p->data, "three");
399 p = pgc_read(c, fd, 0);
401 strcpy(p->data, "odin");
402 pgc_mark_dirty(c, p);
406 q = pgc_read(c, fd, 1024);
408 r = pgc_read(c, fd, 2048);
414 p = pgc_get(c, fd, 3072);
416 strcpy(p->data, "four");