2 * Simple and Quick Shared Memory Cache
4 * (c) 2005 Martin Mares <mj@ucw.cz>
8 #include "lib/fastbuf.h"
20 * qache_entry[max_entries] table of entries and their keys
21 * u32 qache_hash[hash_size] hash table pointing to keys
22 * padding to a multiple of block size
23 * blocks[] data blocks, each block starts with u32 next_ptr
27 u32 magic; /* QCACHE_MAGIC */
28 u32 block_size; /* Parameters as in qache_params */
29 u32 block_shift; /* block_size = 1 << block_shift */
32 u32 entry_table_start; /* Array of qache_entry's */
34 u32 hash_table_start; /* Hash table containing all keys */
39 #define QACHE_MAGIC 0xb79f6d12
42 u32 lru_prev, lru_next; /* Entry #0: head of the cyclic LRU list */
43 u32 data_len; /* Entry #0: number of free blocks, Free entries: ~0U */
44 u32 first_data_block; /* Entry #0: first free block */
46 u32 hash_next; /* Entry #0: first free entry, Free entries: next free */
50 struct qache_header *hdr;
51 struct qache_entry *entry_table;
61 #define first_free_entry entry_table[0].hash_next
62 #define first_free_block entry_table[0].first_data_block
63 #define num_free_blocks entry_table[0].data_len
66 qache_open_existing(struct qache *q, struct qache_params *par)
68 if ((q->fd = open(q->file_name, O_RDWR, 0)) < 0)
72 byte *err = "stat failed";
73 if (fstat(q->fd, &st) < 0)
76 err = "invalid file size";
77 if (st.st_size < (int)sizeof(struct qache_header) || (st.st_size % par->block_size))
79 q->file_size = st.st_size;
81 err = "requested size change";
82 if (q->file_size != par->cache_size)
86 if ((q->mmap_data = mmap(NULL, q->file_size, PROT_READ | PROT_WRITE, MAP_SHARED, q->fd, 0)) == MAP_FAILED)
88 struct qache_header *h = (struct qache_header *) q->mmap_data;
90 err = "incompatible format";
91 if (h->magic != QACHE_MAGIC ||
92 h->block_size != par->block_size ||
93 h->format_id != par->format_id)
96 err = "incomplete file";
97 if (h->num_blocks*h->block_size != q->file_size)
100 /* FIXME: Audit cache file contents */
102 log(L_INFO, "Cache %s: using existing data", q->file_name);
106 munmap(q->mmap_data, q->file_size);
108 log(L_INFO, "Cache %s: ignoring old contents (%s)", q->file_name, err);
114 qache_create(struct qache *q, struct qache_params *par)
116 q->fd = open(q->file_name, O_RDWR | O_CREAT | O_TRUNC, 0666);
118 die("Cache %s: unable to create (%m)", q->file_name);
119 struct fastbuf *fb = bfdopen_shared(q->fd, 16384);
121 struct qache_header h;
122 bzero(&h, sizeof(h));
123 h.magic = QACHE_MAGIC;
124 h.block_size = par->block_size;
125 h.block_shift = fls(h.block_size);
126 h.num_blocks = par->cache_size / par->block_size;
127 h.format_id = par->format_id;
128 h.entry_table_start = sizeof(h);
129 h.max_entries = h.num_blocks;
130 h.hash_table_start = h.entry_table_start + (h.max_entries+1) * sizeof(struct qache_entry);
132 while (h.hash_size < h.max_entries)
134 h.first_data_block = (h.hash_table_start + h.hash_size * 4 + h.block_size - 1) >> h.block_shift;
135 if (h.first_data_block >= h.num_blocks)
136 die("Cache %s: Requested size is too small even to hold the maintenance structures", q->file_name);
137 bwrite(fb, &h, sizeof(h));
139 /* Entry #0: heads of all lists */
140 ASSERT(btell(fb) == h.entry_table_start);
141 struct qache_entry ent;
142 bzero(&ent, sizeof(ent));
143 ent.first_data_block = h.first_data_block;
144 ent.data_len = h.num_blocks - h.first_data_block;
146 bwrite(fb, &ent, sizeof(ent));
149 bzero(&ent, sizeof(ent));
151 for (uns i=1; i<=h.max_entries; i++)
153 ent.hash_next = (i == h.max_entries ? 0 : i+1);
154 bwrite(fb, &ent, sizeof(ent));
158 ASSERT(btell(fb) == h.hash_table_start);
159 for (uns i=0; i<h.hash_size; i++)
163 ASSERT(btell(fb) <= h.first_data_block << h.block_shift);
164 while (btell(fb) < h.first_data_block << h.block_shift)
168 for (uns i=h.first_data_block; i<h.num_blocks; i++)
170 bputl(fb, (i == h.num_blocks-1 ? 0 : i+1));
171 for (uns i=4; i<h.block_size; i+=4)
175 ASSERT(btell(fb) == par->cache_size);
177 log(L_INFO, "Cache %s: created (%d bytes, %d slots, %d buckets)", q->file_name, par->cache_size, h.max_entries, h.hash_size);
179 if ((q->mmap_data = mmap(NULL, par->cache_size, PROT_READ | PROT_WRITE, MAP_SHARED, q->fd, 0)) == MAP_FAILED)
180 die("Cache %s: mmap failed (%m)", par->cache_size);
181 q->file_size = par->cache_size;
185 qache_open(struct qache_params *par)
187 struct qache *q = xmalloc_zero(sizeof(*q));
188 q->file_name = xstrdup(par->file_name);
190 ASSERT(par->block_size >= 8 && !(par->block_size & (par->block_size-1)));
191 par->cache_size = ALIGN(par->cache_size, par->block_size);
193 if (par->force_reset <= 0 && qache_open_existing(q, par))
195 else if (par->force_reset < 0)
196 die("Cache %s: read-only access requested, but no data available");
198 qache_create(q, par);
200 /* FIXME: Remember `closed correctly' status */
202 q->hdr = (struct qache_header *) q->mmap_data;
203 q->entry_table = (struct qache_entry *) (q->mmap_data + q->hdr->entry_table_start);
204 q->hash_table = (u32 *) (q->mmap_data + q->hdr->hash_table_start);
205 q->data_block_size = q->hdr->block_size - 4;
210 qache_close(struct qache *q, uns retain_data)
212 munmap(q->mmap_data, q->file_size);
214 if (!retain_data && unlink(q->file_name) < 0)
215 log(L_ERROR, "Cache %s: unlink failed (%m)", q->file_name);
221 qache_msync(struct qache *q, uns start, uns len)
223 len += (start % PAGE_SIZE);
224 start -= start % PAGE_SIZE;
225 len = ALIGN(len, PAGE_SIZE);
226 if (msync(q->mmap_data + start, len, MS_ASYNC | MS_INVALIDATE) < 0)
227 log(L_ERROR, "Cache %s: msync failed: %m", q->file_name);
228 /* FIXME: Do we need this on Linux? */
232 qache_msync_block(struct qache *q, uns blk)
234 qache_msync(q, blk << q->hdr->block_shift, q->hdr->block_size);
238 qache_lock(struct qache *q)
240 /* We cannot use flock() since it happily permits locking a shared fd (e.g., after fork()) multiple times */
242 struct flock fl = { .l_type = F_WRLCK, .l_whence = SEEK_SET, .l_start = 0, .l_len = sizeof(struct qache_header) };
243 if (fcntl(q->fd, F_SETLKW, &fl) < 0)
244 die("fcntl lock on %s: %m", q->file_name);
249 qache_unlock(struct qache *q, uns dirty)
252 if (dirty) /* Sync header, entry table and hash table */
253 qache_msync(q, 0, q->hdr->first_data_block << q->hdr->block_shift);
254 struct flock fl = { .l_type = F_UNLCK, .l_whence = SEEK_SET, .l_start = 0, .l_len = sizeof(struct qache_header) };
255 if (fcntl(q->fd, F_SETLKW, &fl) < 0)
256 die("fcntl unlock on %s: %m", q->file_name);
261 qache_hash(struct qache *q, qache_key_t *key)
263 uns h = ((*key)[0] << 24) | ((*key)[1] << 16) | ((*key)[2] << 8) | (*key)[3];
264 return h % q->hdr->hash_size;
268 qache_hash_find(struct qache *q, qache_key_t *key, uns pos_hint)
272 if (pos_hint && pos_hint <= q->hdr->max_entries && !memcmp(q->entry_table[pos_hint].key, key, sizeof(*key)))
275 uns h = qache_hash(q, key);
276 for (uns e = q->hash_table[h]; e; e=q->entry_table[e].hash_next)
277 if (!memcmp(q->entry_table[e].key, key, sizeof(*key)))
283 qache_hash_insert(struct qache *q, uns e)
285 uns h = qache_hash(q, &q->entry_table[e].key);
286 q->entry_table[e].hash_next = q->hash_table[h];
287 q->hash_table[h] = e;
291 qache_hash_remove(struct qache *q, uns e)
293 struct qache_entry *entry = &q->entry_table[e];
294 uns *hh = &q->hash_table[qache_hash(q, &entry->key)];
295 for (uns f = *hh; f; hh=&(q->entry_table[f].hash_next))
296 if (!memcmp(q->entry_table[f].key, entry->key, sizeof(qache_key_t)))
298 *hh = entry->hash_next;
305 qache_alloc_entry(struct qache *q)
307 uns e = q->first_free_entry;
308 ASSERT(q->locked && e);
309 struct qache_entry *entry = &q->entry_table[e];
310 ASSERT(entry->data_len == ~0U);
311 q->first_free_entry = entry->hash_next;
317 qache_free_entry(struct qache *q, uns e)
319 struct qache_entry *entry = &q->entry_table[e];
320 ASSERT(q->locked && entry->data_len != ~0U);
321 entry->data_len = ~0U;
322 entry->hash_next = q->first_free_entry;
323 q->first_free_entry = e;
327 get_block_start(struct qache *q, uns block)
329 ASSERT(block && block < q->hdr->num_blocks);
330 return q->mmap_data + (block << q->hdr->block_shift);
334 get_block_data(struct qache *q, uns block)
336 return (byte*)get_block_start(q, block) + 4;
340 get_block_next(struct qache *q, uns block)
342 return *(u32*)get_block_start(q, block);
346 set_block_next(struct qache *q, uns block, uns next)
348 *(u32*)get_block_start(q, block) = next;
352 qache_alloc_block(struct qache *q)
354 ASSERT(q->locked && q->num_free_blocks);
355 uns blk = q->first_free_block;
356 q->first_free_block = get_block_next(q, blk);
357 q->num_free_blocks--;
362 qache_free_block(struct qache *q, uns blk)
365 set_block_next(q, blk, q->first_free_block);
366 qache_msync_block(q, blk);
367 q->first_free_block = blk;
368 q->num_free_blocks++;
372 qache_lru_insert(struct qache *q, uns e)
374 struct qache_entry *head = &q->entry_table[0];
375 struct qache_entry *entry = &q->entry_table[e];
376 ASSERT(q->locked && !entry->lru_prev && !entry->lru_next);
377 uns succe = head->lru_next;
378 struct qache_entry *succ = &q->entry_table[succe];
381 entry->lru_next = succe;
386 qache_lru_remove(struct qache *q, uns e)
389 struct qache_entry *entry = &q->entry_table[e];
390 q->entry_table[entry->lru_prev].lru_next = entry->lru_next;
391 q->entry_table[entry->lru_next].lru_prev = entry->lru_prev;
392 entry->lru_prev = entry->lru_next = 0;
396 qache_lru_get(struct qache *q)
398 return q->entry_table[0].lru_prev;
402 qache_ll_delete(struct qache *q, uns e)
404 struct qache_entry *entry = &q->entry_table[e];
405 uns blk = entry->first_data_block;
406 while (entry->data_len)
408 uns next = get_block_next(q, blk);
409 qache_free_block(q, blk);
411 if (entry->data_len >= q->data_block_size)
412 entry->data_len -= q->data_block_size;
416 qache_lru_remove(q, e);
417 qache_hash_remove(q, e);
418 qache_free_entry(q, e);
422 qache_insert(struct qache *q, qache_key_t *key, uns pos_hint, void *data, uns size)
426 uns e = qache_hash_find(q, key, pos_hint);
428 qache_ll_delete(q ,e);
430 uns blocks = (size + q->data_block_size - 1) / q->data_block_size;
431 if (blocks > q->hdr->num_blocks - q->hdr->first_data_block)
436 while (q->num_free_blocks < blocks)
438 e = qache_lru_get(q);
440 qache_ll_delete(q, e);
442 e = qache_alloc_entry(q);
443 struct qache_entry *entry = &q->entry_table[e];
444 entry->data_len = size;
445 memcpy(entry->key, key, sizeof(*key));
447 entry->first_data_block = 0;
450 uns chunk = (size % q->data_block_size ) ? : q->data_block_size;
451 uns blk = qache_alloc_block(q);
452 set_block_next(q, blk, entry->first_data_block);
453 memcpy(get_block_data(q, blk), data+size-chunk, chunk);
454 qache_msync_block(q, blk);
455 entry->first_data_block = blk;
459 qache_lru_insert(q, e);
460 qache_hash_insert(q, e);
466 qache_lookup(struct qache *q, qache_key_t *key, uns pos_hint, void **datap, uns *sizep, uns start)
469 uns e = qache_hash_find(q, key, pos_hint);
472 struct qache_entry *entry = &q->entry_table[e];
473 qache_lru_remove(q, e);
474 qache_lru_insert(q, e);
478 uns avail = (size > entry->data_len) ? 0 : entry->data_len - size;
479 uns xfer = MIN(*sizep, avail);
484 *datap = xmalloc(xfer);
485 uns blk = entry->first_data_block;
486 while (start >= q->data_block_size)
488 blk = get_block_next(q, blk);
489 start -= q->data_block_size;
494 uns len = MIN(xfer, q->data_block_size - start);
495 memcpy(data, get_block_data(q, blk), len);
496 blk = get_block_next(q, blk);
506 qache_unlock(q, 1); /* Yes, modified -- we update the LRU */
511 qache_delete(struct qache *q, qache_key_t *key, uns pos_hint)
514 uns e = qache_hash_find(q, key, pos_hint);
516 qache_ll_delete(q, e);
522 qache_debug(struct qache *q)
524 log(L_DEBUG, "Cache %s: block_size=%d (%d data), num_blocks=%d (%d first data), %d entries, %d hash slots",
525 q->file_name, q->hdr->block_size, q->data_block_size, q->hdr->num_blocks, q->hdr->first_data_block,
526 q->hdr->max_entries, q->hdr->hash_size);
528 log(L_DEBUG, "Table of cache entries:");
529 log(L_DEBUG, "\tEntry\tLruPrev\tLruNext\tDataLen\tDataBlk\tHashNxt\tKey");
530 for (uns e=0; e<=q->hdr->max_entries; e++)
532 struct qache_entry *ent = &q->entry_table[e];
533 byte ky[2*sizeof(qache_key_t)+1];
534 for (uns i=0; i<sizeof(qache_key_t); i++)
535 sprintf(ky+2*i, "%02x", ent->key[i]);
536 log(L_DEBUG, "\t%d\t%d\t%d\t%d\t%d\t%d\t%s", e, ent->lru_prev, ent->lru_next, ent->data_len,
537 ent->first_data_block, ent->hash_next, ky);
540 log(L_DEBUG, "Hash table:");
541 for (uns h=0; h<q->hdr->hash_size; h++)
542 log(L_DEBUG, "\t%04x\t%d", h, q->hash_table[h]);
544 log(L_DEBUG, "Next pointers:");
545 for (uns blk=q->hdr->first_data_block; blk<q->hdr->num_blocks; blk++)
546 log(L_DEBUG, "\t%d\t%d", blk, get_block_next(q, blk));
551 int main(int argc UNUSED, char **argv UNUSED)
553 struct qache_params par = {
554 .file_name = "tmp/test",
558 .format_id = 0xfeedcafe
560 struct qache *q = qache_open(&par);
562 qache_key_t key = { 0x12, 0x34, 0x56, 0x78, 0x9a, 0xbc, 0xde, 0xf0, 0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef };
563 byte data[1000] = { '1', '2', '3', '4', '5' };
564 qache_insert(q, &key, 0, data, 1000);
567 qache_lookup(q, &key, 0, NULL, NULL, 0);