]> mj.ucw.cz Git - libucw.git/blob - lib/pagecache.c
3e1577f65503f511fcab719d88f11bbc4bc111bd
[libucw.git] / lib / pagecache.c
1 /*
2  *      Sherlock Library -- File Page Cache
3  *
4  *      (c) 1999 Martin Mares <mj@atrey.karlin.mff.cuni.cz>
5  */
6
7 #include <stdio.h>
8 #include <stdlib.h>
9 #include <string.h>
10 #include <fcntl.h>
11 #include <unistd.h>
12
13 #include "lib.h"
14 #include "pagecache.h"
15 #include "lfs.h"
16
17 struct page_cache {
18   list free_pages;                      /* LRU queue of free pages */
19   list locked_pages;                    /* List of locked pages */
20   list dirty_pages;                     /* List of 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   list *hash_table;                     /* List heads corresponding to hash buckets */
27 };
28
29 /* FIXME: Negations -> cast to sh_off_t */
30
31 struct page_cache *
32 pgc_open(uns page_size, uns max_pages)
33 {
34   struct page_cache *c = xmalloc(sizeof(struct page_cache));
35   uns i;
36
37   bzero(c, sizeof(*c));
38   init_list(&c->free_pages);
39   init_list(&c->locked_pages);
40   init_list(&c->dirty_pages);
41   c->page_size = page_size;
42   c->max_pages = max_pages;
43   c->hash_size = nextprime(c->max_pages);
44   c->hash_table = xmalloc(sizeof(list) * c->hash_size);
45   for(i=0; i<c->hash_size; i++)
46     init_list(&c->hash_table[i]);
47   return c;
48 }
49
50 void
51 pgc_close(struct page_cache *c)
52 {
53   pgc_cleanup(c);
54   ASSERT(EMPTY_LIST(c->locked_pages));
55   ASSERT(EMPTY_LIST(c->dirty_pages));
56   ASSERT(EMPTY_LIST(c->free_pages));
57   free(c->hash_table);
58   free(c);
59 }
60
61 static void
62 pgc_debug_page(struct page *p)
63 {
64   printf("\tk=%08x f=%x c=%d\n", (uns) p->key, p->flags, p->lock_count);
65 }
66
67 void
68 pgc_debug(struct page_cache *c)
69 {
70   struct page *p;
71
72   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);
73   puts("LRU list:");
74   WALK_LIST(p, c->free_pages)
75     pgc_debug_page(p);
76   puts("Locked list:");
77   WALK_LIST(p, c->locked_pages)
78     pgc_debug_page(p);
79   puts("Dirty list:");
80   WALK_LIST(p, c->dirty_pages)
81     pgc_debug_page(p);
82 }
83
84 static void
85 flush_page(struct page_cache *c, struct page *p)
86 {
87   int fd = p->key & (c->page_size - 1);
88   sh_off_t pos = p->key & ~(c->page_size - 1);
89   int s;
90
91   ASSERT((p->flags & PG_FLAG_DIRTY) && !p->lock_count);
92   /* FIXME: Use pwrite() */
93   sh_seek(fd, pos, SEEK_SET);
94   s = write(fd, p->data, c->page_size);
95   if (s < 0)
96     die("pgc_write(%d): %m", fd);
97   if (s != c->page_size)
98     die("pgc_write(%d): incomplete page (only %d of %d)", s, c->page_size);
99   p->flags &= ~PG_FLAG_DIRTY;
100 }
101
102 static inline uns
103 hash_page(struct page_cache *c, sh_off_t key)
104 {
105   return key % c->hash_size;            /* FIXME: Use better hash function */
106 }
107
108 static struct page *
109 get_page(struct page_cache *c, sh_off_t key)
110 {
111   node *n;
112   struct page *p;
113   uns hash = hash_page(c, key);
114
115   /*
116    *  Return locked buffer for given page.
117    */
118
119   WALK_LIST(n, c->hash_table[hash])
120     {
121       p = SKIP_BACK(struct page, hn, n);
122       if (p->key == key)
123         {
124           /* Found in the cache */
125           rem_node(&p->n);
126           if (!p->lock_count)
127             c->free_count--;
128           return p;
129         }
130     }
131   if (c->total_count < c->max_pages || !c->free_count)
132     {
133       /* Enough free space, expand the cache */
134       p = xmalloc(sizeof(struct page) + c->page_size);
135       c->total_count++;
136     }
137   else
138     {
139       /* Discard the oldest unlocked page */
140       p = HEAD(c->free_pages);
141       if (!p->n.next)
142         {
143           /* There are only dirty pages here */
144           p = HEAD(c->dirty_pages);
145           flush_page(c, p);
146         }
147       ASSERT(!p->lock_count);
148       rem_node(&p->n);
149       rem_node(&p->hn);
150       c->free_count--;
151     }
152   p->key = key;
153   p->flags = 0;
154   p->lock_count = 0;
155   add_tail(&c->hash_table[hash], &p->hn);
156   return p;
157 }
158
159 void
160 pgc_flush(struct page_cache *c)
161 {
162   struct page *p;
163   node *n;
164
165   WALK_LIST_DELSAFE(p, n, c->dirty_pages)
166     {
167       flush_page(c, p);
168       rem_node(&p->n);
169       add_tail(&c->free_pages, &p->n);
170     }
171 }
172
173 void
174 pgc_cleanup(struct page_cache *c)
175 {
176   struct page *p;
177   node *n;
178
179   pgc_flush(c);
180   WALK_LIST_DELSAFE(p, n, c->free_pages)
181     {
182       ASSERT(!(p->flags & PG_FLAG_DIRTY) && !p->lock_count);
183       rem_node(&p->n);
184       c->free_count--;
185       c->total_count--;
186       free(p);
187     }
188   ASSERT(!c->free_count);
189 }
190
191 static inline struct page *
192 get_and_lock_page(struct page_cache *c, sh_off_t key)
193 {
194   struct page *p = get_page(c, key);
195
196   add_tail(&c->locked_pages, &p->n);
197   p->lock_count++;
198   return p;
199 }
200
201 struct page *
202 pgc_read(struct page_cache *c, int fd, sh_off_t pos)
203 {
204   sh_off_t key;
205   struct page *p;
206   int s;
207
208   ASSERT(!(pos & (c->page_size - 1)));
209   ASSERT(!(fd & ~(c->page_size - 1)));
210   key = pos | fd;
211   p = get_and_lock_page(c, key);
212   if (!(p->flags & PG_FLAG_VALID))
213     {
214       /* FIXME: Use pread() */
215       sh_seek(fd, pos, SEEK_SET);
216       s = read(fd, p->data, c->page_size);
217       if (s < 0)
218         die("pgc_read(%d): %m", fd);
219       if (s != c->page_size)
220         die("pgc_read(%d): incomplete page (only %d of %d)", s, c->page_size);
221       p->flags |= PG_FLAG_VALID;
222     }
223   return p;
224 }
225
226 struct page *
227 pgc_get(struct page_cache *c, int fd, sh_off_t pos)
228 {
229   sh_off_t key;
230   struct page *p;
231
232   ASSERT(!(pos & (c->page_size - 1)));
233   ASSERT(!(fd & ~(c->page_size - 1)));
234   key = pos | fd;
235   p = get_and_lock_page(c, key);
236   p->flags |= PG_FLAG_VALID | PG_FLAG_DIRTY;
237   return p;
238 }
239
240 void
241 pgc_put(struct page_cache *c, struct page *p)
242 {
243   ASSERT(p->lock_count);
244   if (--p->lock_count)
245     return;
246   rem_node(&p->n);
247   if (p->flags & PG_FLAG_DIRTY)
248     {
249       add_tail(&c->dirty_pages, &p->n);
250       c->free_count++;
251     }
252   else if (c->free_count < c->max_pages)
253     {
254       add_tail(&c->free_pages, &p->n);
255       c->free_count++;
256     }
257   else
258     {
259       free(p);
260       c->total_count--;
261     }
262 }
263
264 void
265 pgc_put_dirty(struct page_cache *c, struct page *p)
266 {
267   p->flags |= PG_FLAG_DIRTY;
268   pgc_put(c, p);
269 }
270
271 byte *
272 pgc_read_data(struct page_cache *c, int fd, sh_off_t pos, uns *len)
273 {
274   struct page *p;
275   sh_off_t page = pos & ~(c->page_size - 1);
276   uns offset = pos & (c->page_size - 1);
277
278   p = pgc_read(c, fd, page);
279   pgc_put(c, p);
280   *len = c->page_size - offset;
281   return p->data + offset;
282 }
283
284 #ifdef TEST
285
286 int main(int argc, char **argv)
287 {
288   struct page_cache *c = pgc_open(1024, 2);
289   struct page *p, *q, *r;
290   int fd = open("test", O_RDWR | O_CREAT | O_TRUNC, 0666);
291   if (fd < 0)
292     die("open: %m");
293   pgc_debug(c);
294   p = pgc_get(c, fd, 0);
295   pgc_debug(c);
296   strcpy(p->data, "one");
297   pgc_put_dirty(c, p);
298   pgc_debug(c);
299   p = pgc_get(c, fd, 1024);
300   pgc_debug(c);
301   strcpy(p->data, "two");
302   pgc_put_dirty(c, p);
303   pgc_debug(c);
304   p = pgc_get(c, fd, 2048);
305   pgc_debug(c);
306   strcpy(p->data, "three");
307   pgc_put_dirty(c, p);
308   pgc_debug(c);
309   pgc_flush(c);
310   pgc_debug(c);
311   p = pgc_read(c, fd, 0);
312   pgc_debug(c);
313   q = pgc_read(c, fd, 1024);
314   pgc_debug(c);
315   r = pgc_read(c, fd, 2048);
316   pgc_debug(c);
317   pgc_put(c, p);
318   pgc_put(c, q);
319   pgc_put(c, r);
320   pgc_debug(c);
321   p = pgc_get(c, fd, 3072);
322   pgc_debug(c);
323   pgc_put(c, p);
324   pgc_debug(c);
325   pgc_cleanup(c);
326   pgc_debug(c);
327   pgc_close(c);
328   return 0;
329 }
330
331 #endif