]> mj.ucw.cz Git - libucw.git/blob - lib/pagecache.c
Added bit_array_assign(), replaced BIT_ARRAY_ALLOC by functions.
[libucw.git] / lib / pagecache.c
1 /*
2  *      UCW Library -- File Page Cache
3  *
4  *      (c) 1999--2002 Martin Mares <mj@ucw.cz>
5  *
6  *      This software may be freely distributed and used according to the terms
7  *      of the GNU Lesser General Public License.
8  */
9
10 #include "lib/lib.h"
11 #include "lib/pagecache.h"
12 #include "lib/lfs.h"
13
14 #include <stdio.h>
15 #include <stdlib.h>
16 #include <string.h>
17 #include <fcntl.h>
18 #include <unistd.h>
19 #include <alloca.h>
20
21 struct page_cache {
22   list free_pages;                      /* LRU queue of free non-dirty pages */
23   list locked_pages;                    /* List of locked pages (starts with dirty ones) */
24   list dirty_pages;                     /* List of free dirty pages */
25   uns page_size;                        /* Bytes per page (must be a power of two) */
26   uns free_count;                       /* Number of free / dirty pages */
27   uns total_count;                      /* Total number of pages */
28   uns max_pages;                        /* Maximum number of free pages */
29   uns hash_size;                        /* Hash table size */
30   uns stat_hit;                         /* Number of cache hits */
31   uns stat_miss;                        /* Number of cache misses */
32   uns stat_write;                       /* Number of writes */
33   list *hash_table;                     /* List heads corresponding to hash buckets */
34 #ifndef HAVE_PREAD
35   sh_off_t pos;                         /* Current position in the file */
36   int pos_fd;                           /* FD the position corresponds to */
37 #endif
38 };
39
40 #define PAGE_NUMBER(pos) ((pos) & ~(sh_off_t)(c->page_size - 1))
41 #define PAGE_OFFSET(pos) ((pos) & (c->page_size - 1))
42
43 struct page_cache *
44 pgc_open(uns page_size, uns max_pages)
45 {
46   struct page_cache *c = xmalloc_zero(sizeof(struct page_cache));
47   uns i;
48
49   init_list(&c->free_pages);
50   init_list(&c->locked_pages);
51   init_list(&c->dirty_pages);
52   c->page_size = page_size;
53   c->max_pages = max_pages;
54   c->hash_size = nextprime(c->max_pages);
55   c->hash_table = xmalloc(sizeof(list) * c->hash_size);
56   for(i=0; i<c->hash_size; i++)
57     init_list(&c->hash_table[i]);
58 #ifndef HAVE_PREAD
59   c->pos_fd = -1;
60 #endif
61   return c;
62 }
63
64 void
65 pgc_close(struct page_cache *c)
66 {
67   pgc_cleanup(c);
68   ASSERT(EMPTY_LIST(c->locked_pages));
69   ASSERT(EMPTY_LIST(c->dirty_pages));
70   ASSERT(EMPTY_LIST(c->free_pages));
71   xfree(c->hash_table);
72   xfree(c);
73 }
74
75 static void
76 pgc_debug_page(struct page *p)
77 {
78   printf("\tp=%08x d=%d f=%x c=%d\n", (uns) p->pos, p->fd, p->flags, p->lock_count);
79 }
80
81 void
82 pgc_debug(struct page_cache *c, int mode)
83 {
84   struct page *p;
85
86   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);
87   printf(">> stats: %d hits, %d misses, %d writes\n", c->stat_hit, c->stat_miss, c->stat_write);
88   if (mode)
89     {
90       puts("LRU list:");
91       WALK_LIST(p, c->free_pages)
92         pgc_debug_page(p);
93       puts("Locked list:");
94       WALK_LIST(p, c->locked_pages)
95         pgc_debug_page(p);
96       puts("Dirty list:");
97       WALK_LIST(p, c->dirty_pages)
98         pgc_debug_page(p);
99     }
100 }
101
102 static void
103 flush_page(struct page_cache *c, struct page *p)
104 {
105   int s;
106
107   ASSERT(p->flags & PG_FLAG_DIRTY);
108 #ifdef HAVE_PREAD
109   s = sh_pwrite(p->fd, p->data, c->page_size, p->pos);
110 #else
111   if (c->pos != p->pos || c->pos_fd != (int) p->fd)
112     sh_seek(p->fd, p->pos, SEEK_SET);
113   s = write(p->fd, p->data, c->page_size);
114   c->pos = p->pos + s;
115   c->pos_fd = p->fd;
116 #endif
117   if (s < 0)
118     die("pgc_write(%d): %m", p->fd);
119   if (s != (int) c->page_size)
120     die("pgc_write(%d): incomplete page (only %d of %d)", p->fd, s, c->page_size);
121   p->flags &= ~PG_FLAG_DIRTY;
122   c->stat_write++;
123 }
124
125 static int
126 flush_cmp(const void *X, const void *Y)
127 {
128   struct page *x = *((struct page **)X);
129   struct page *y = *((struct page **)Y);
130
131   if (x->fd < y->fd)
132     return -1;
133   if (x->fd > y->fd)
134     return 1;
135   if (x->pos < y->pos)
136     return -1;
137   if (x->pos > y->pos)
138     return 1;
139   return 0;
140 }
141
142 static void
143 flush_pages(struct page_cache *c, uns force)
144 {
145   uns cnt = 0;
146   uns max = force ? ~0U : c->free_count / 2;
147   uns i;
148   struct page *p, *q, **req, **rr;
149
150   WALK_LIST(p, c->dirty_pages)
151     {
152       cnt++;
153       if (cnt >= max)
154         break;
155     }
156   req = rr = alloca(cnt * sizeof(struct page *));
157   i = cnt;
158   p = HEAD(c->dirty_pages);
159   while ((q = (struct page *) p->n.next) && i--)
160     {
161       rem_node(&p->n);
162       add_tail(&c->free_pages, &p->n);
163       *rr++ = p;
164       p = q;
165     }
166   qsort(req, cnt, sizeof(struct page *), flush_cmp);
167   for(i=0; i<cnt; i++)
168     flush_page(c, req[i]);
169 }
170
171 static inline uns
172 hash_page(struct page_cache *c, sh_off_t pos, uns fd)
173 {
174   return (pos + fd) % c->hash_size;
175 }
176
177 static struct page *
178 get_page(struct page_cache *c, sh_off_t pos, uns fd)
179 {
180   node *n;
181   struct page *p;
182   uns hash = hash_page(c, pos, fd);
183
184   /*
185    *  Return locked buffer for given page.
186    */
187
188   WALK_LIST(n, c->hash_table[hash])
189     {
190       p = SKIP_BACK(struct page, hn, n);
191       if (p->pos == pos && p->fd == fd)
192         {
193           /* Found in the cache */
194           rem_node(&p->n);
195           if (!p->lock_count)
196             c->free_count--;
197           return p;
198         }
199     }
200   if (c->total_count < c->max_pages || !c->free_count)
201     {
202       /* Enough free space, expand the cache */
203       p = xmalloc(sizeof(struct page) + c->page_size);
204       c->total_count++;
205     }
206   else
207     {
208       /* Discard the oldest unlocked page */
209       p = HEAD(c->free_pages);
210       if (!p->n.next)
211         {
212           /* There are only dirty pages here */
213           flush_pages(c, 0);
214           p = HEAD(c->free_pages);
215           ASSERT(p->n.next);
216         }
217       ASSERT(!p->lock_count);
218       rem_node(&p->n);
219       rem_node(&p->hn);
220       c->free_count--;
221     }
222   p->pos = pos;
223   p->fd = fd;
224   p->flags = 0;
225   p->lock_count = 0;
226   add_tail(&c->hash_table[hash], &p->hn);
227   return p;
228 }
229
230 void
231 pgc_flush(struct page_cache *c)
232 {
233   struct page *p;
234
235   flush_pages(c, 1);
236   WALK_LIST(p, c->locked_pages)
237     if (p->flags & PG_FLAG_DIRTY)
238       flush_page(c, p);
239     else
240       break;
241 }
242
243 void
244 pgc_cleanup(struct page_cache *c)
245 {
246   struct page *p;
247   node *n;
248
249   pgc_flush(c);
250   WALK_LIST_DELSAFE(p, n, c->free_pages)
251     {
252       ASSERT(!(p->flags & PG_FLAG_DIRTY) && !p->lock_count);
253       rem_node(&p->n);
254       rem_node(&p->hn);
255       c->free_count--;
256       c->total_count--;
257       xfree(p);
258     }
259   ASSERT(!c->free_count);
260 }
261
262 static inline struct page *
263 get_and_lock_page(struct page_cache *c, sh_off_t pos, uns fd)
264 {
265   struct page *p = get_page(c, pos, fd);
266
267   add_tail(&c->locked_pages, &p->n);
268   p->lock_count++;
269   return p;
270 }
271
272 struct page *
273 pgc_read(struct page_cache *c, int fd, sh_off_t pos)
274 {
275   struct page *p;
276   int s;
277
278   ASSERT(!PAGE_OFFSET(pos));
279   p = get_and_lock_page(c, pos, fd);
280   if (p->flags & PG_FLAG_VALID)
281     c->stat_hit++;
282   else
283     {
284       c->stat_miss++;
285 #ifdef HAVE_PREAD
286       s = sh_pread(fd, p->data, c->page_size, pos);
287 #else
288       if (c->pos != pos || c->pos_fd != (int)fd)
289         sh_seek(fd, pos, SEEK_SET);
290       s = read(fd, p->data, c->page_size);
291       c->pos = pos + s;
292       c->pos_fd = fd;
293 #endif
294       if (s < 0)
295         die("pgc_read(%d): %m", fd);
296       if (s != (int) c->page_size)
297         die("pgc_read(%d): incomplete page (only %d of %d)", p->fd, s, c->page_size);
298       p->flags |= PG_FLAG_VALID;
299     }
300   return p;
301 }
302
303 struct page *
304 pgc_get(struct page_cache *c, int fd, sh_off_t pos)
305 {
306   struct page *p;
307
308   ASSERT(!PAGE_OFFSET(pos));
309   p = get_and_lock_page(c, pos, fd);
310   p->flags |= PG_FLAG_VALID | PG_FLAG_DIRTY;
311   return p;
312 }
313
314 struct page *
315 pgc_get_zero(struct page_cache *c, int fd, sh_off_t pos)
316 {
317   struct page *p;
318
319   ASSERT(!PAGE_OFFSET(pos));
320   p = get_and_lock_page(c, pos, fd);
321   bzero(p->data, c->page_size);
322   p->flags |= PG_FLAG_VALID | PG_FLAG_DIRTY;
323   return p;
324 }
325
326 void
327 pgc_put(struct page_cache *c, struct page *p)
328 {
329   ASSERT(p->lock_count);
330   if (--p->lock_count)
331     return;
332   rem_node(&p->n);
333   if (p->flags & PG_FLAG_DIRTY)
334     {
335       add_tail(&c->dirty_pages, &p->n);
336       c->free_count++;
337     }
338   else if (c->free_count < c->max_pages)
339     {
340       add_tail(&c->free_pages, &p->n);
341       c->free_count++;
342     }
343   else
344     {
345       rem_node(&p->hn);
346       xfree(p);
347       c->total_count--;
348     }
349 }
350
351 void
352 pgc_mark_dirty(struct page_cache *c, struct page *p)
353 {
354   ASSERT(p->lock_count);
355   if (!(p->flags & PG_FLAG_DIRTY))
356     {
357       p->flags |= PG_FLAG_DIRTY;
358       rem_node(&p->n);
359       add_head(&c->locked_pages, &p->n);
360     }
361 }
362
363 byte *
364 pgc_read_data(struct page_cache *c, int fd, sh_off_t pos, uns *len)
365 {
366   struct page *p;
367   sh_off_t page = PAGE_NUMBER(pos);
368   uns offset = PAGE_OFFSET(pos);
369
370   p = pgc_read(c, fd, page);
371   pgc_put(c, p);
372   *len = c->page_size - offset;
373   return p->data + offset;
374 }
375
376 #ifdef TEST
377
378 int main(int argc, char **argv)
379 {
380   struct page_cache *c = pgc_open(1024, 2);
381   struct page *p, *q, *r;
382   int fd = open("test", O_RDWR | O_CREAT | O_TRUNC, 0666);
383   if (fd < 0)
384     die("open: %m");
385   pgc_debug(c, 1);
386   p = pgc_get(c, fd, 0);
387   pgc_debug(c, 1);
388   strcpy(p->data, "one");
389   pgc_put(c, p);
390   pgc_debug(c, 1);
391   p = pgc_get(c, fd, 1024);
392   pgc_debug(c, 1);
393   strcpy(p->data, "two");
394   pgc_put(c, p);
395   pgc_debug(c, 1);
396   p = pgc_get(c, fd, 2048);
397   pgc_debug(c, 1);
398   strcpy(p->data, "three");
399   pgc_put(c, p);
400   pgc_debug(c, 1);
401   pgc_flush(c);
402   pgc_debug(c, 1);
403   p = pgc_read(c, fd, 0);
404   pgc_debug(c, 1);
405   strcpy(p->data, "odin");
406   pgc_mark_dirty(c, p);
407   pgc_debug(c, 1);
408   pgc_flush(c);
409   pgc_debug(c, 1);
410   q = pgc_read(c, fd, 1024);
411   pgc_debug(c, 1);
412   r = pgc_read(c, fd, 2048);
413   pgc_debug(c, 1);
414   pgc_put(c, p);
415   pgc_put(c, q);
416   pgc_put(c, r);
417   pgc_debug(c, 1);
418   p = pgc_get(c, fd, 3072);
419   pgc_debug(c, 1);
420   strcpy(p->data, "four");
421   pgc_put(c, p);
422   pgc_debug(c, 1);
423   pgc_cleanup(c);
424   pgc_debug(c, 1);
425   pgc_close(c);
426   return 0;
427 }
428
429 #endif