2 * Simple and Quick Shared Memory Cache
4 * (c) 2005 Martin Mares <mj@ucw.cz>
10 #include "lib/bitops.h"
11 #include "lib/fastbuf.h"
12 #include "lib/qache.h"
21 * The cache lives in a mmapped file of the following format:
23 * qache_entry[max_entries] table of entries and their keys
24 * u32 qache_hash[hash_size] hash table pointing to keys
25 * u32 block_next[num_blocks] next block pointers
26 * padding to a multiple of block size
27 * blocks[] data blocks
31 u32 magic; /* QCACHE_MAGIC */
32 u32 block_size; /* Parameters as in qache_params */
33 u32 block_shift; /* block_size = 1 << block_shift */
36 u32 entry_table_start; /* Array of qache_entry's */
38 u32 hash_table_start; /* Hash table containing all keys */
40 u32 next_table_start; /* Array of next pointers */
44 #define QACHE_MAGIC 0xb79f6d12
47 u32 lru_prev, lru_next; /* Entry #0: head of the cyclic LRU list */
48 u32 data_len; /* Entry #0: number of free blocks, Free entries: ~0U */
49 u32 first_data_block; /* Entry #0: first free block */
51 u32 hash_next; /* Entry #0: first free entry, Free entries: next free */
55 struct qache_header *hdr;
56 struct qache_entry *entry_table;
66 #define first_free_entry entry_table[0].hash_next
67 #define first_free_block entry_table[0].first_data_block
68 #define num_free_blocks entry_table[0].data_len
71 format_key(qache_key_t *key)
73 static byte keybuf[2*sizeof(qache_key_t)+1];
74 for (uns i=0; i<sizeof(qache_key_t); i++)
75 sprintf(keybuf+2*i, "%02x", (*key)[i]);
80 qache_msync(struct qache *q UNUSED, uns start UNUSED, uns len UNUSED)
83 /* We don't need msyncing on Linux, since the mappings are guaranteed to be coherent */
84 len += (start % PAGE_SIZE);
85 start -= start % PAGE_SIZE;
86 len = ALIGN(len, PAGE_SIZE);
87 if (msync(q->mmap_data + start, len, MS_ASYNC | MS_INVALIDATE) < 0)
88 log(L_ERROR, "Cache %s: msync failed: %m", q->file_name);
93 qache_msync_block(struct qache *q, uns blk)
95 DBG("\tSyncing block %d", blk);
96 qache_msync(q, blk << q->hdr->block_shift, q->hdr->block_size);
100 qache_lock(struct qache *q)
102 /* We cannot use flock() since it happily permits locking a shared fd (e.g., after fork()) multiple times */
104 struct flock fl = { .l_type = F_WRLCK, .l_whence = SEEK_SET, .l_start = 0, .l_len = sizeof(struct qache_header) };
105 if (fcntl(q->fd, F_SETLKW, &fl) < 0)
106 die("fcntl lock on %s: %m", q->file_name);
108 DBG("Locked cache %s", q->file_name);
112 qache_unlock(struct qache *q, uns dirty)
115 if (dirty) /* Sync header, entry table and hash table */
116 qache_msync(q, 0, q->hdr->first_data_block << q->hdr->block_shift);
117 struct flock fl = { .l_type = F_UNLCK, .l_whence = SEEK_SET, .l_start = 0, .l_len = sizeof(struct qache_header) };
118 if (fcntl(q->fd, F_SETLKW, &fl) < 0)
119 die("fcntl unlock on %s: %m", q->file_name);
121 DBG("Unlocked cache %s (dirty=%d)", q->file_name, dirty);
124 enum entry_audit_flags {
131 audit_entries(struct qache *q, byte *entrymap)
135 DBG("Auditing entries");
137 /* Check the free list */
138 i = q->first_free_entry;
141 if (i >= q->hdr->max_entries || (entrymap[i] & ET_FREE_LIST) || q->entry_table[i].data_len != ~0U)
142 return "inconsistent free entry list";
143 entrymap[i] |= ET_FREE_LIST;
144 i = q->entry_table[i].hash_next;
147 /* Check the hash table */
148 for (i=0; i<q->hdr->hash_size; i++)
150 j = q->hash_table[i];
153 if (j >= q->hdr->max_entries || (entrymap[j] & (ET_HASH | ET_FREE_LIST)))
154 return "inconsistent hash chains";
155 entrymap[j] |= ET_HASH;
156 j = q->entry_table[j].hash_next;
164 j = q->entry_table[i].lru_next;
165 if ((entrymap[i] & (ET_LRU | ET_FREE_LIST)) || j >= q->hdr->max_entries || q->entry_table[j].lru_prev != i)
166 return "inconsistent LRU list";
167 entrymap[i] |= ET_LRU;
172 /* Check if all non-free items are in all lists */
173 for (i=1; i<q->hdr->max_entries; i++)
175 if (entrymap[i] != ((q->entry_table[i].data_len == ~0U) ? ET_FREE_LIST : (ET_LRU | ET_HASH)))
176 return "inconsistent lists";
181 enum block_audit_flags {
187 audit_blocks(struct qache *q, byte *entrymap, byte *blockmap)
191 DBG("Auditing blocks");
193 /* Check the free list */
194 for (i=q->first_free_block; i; i=q->next_table[i])
196 if (i < q->hdr->first_data_block || i >= q->hdr->num_blocks || (blockmap[i] & BT_FREE_LIST))
197 return "inconsistent free block list";
198 blockmap[i] |= BT_FREE_LIST;
201 /* Check allocation lists of entries */
202 for (i=1; i<q->hdr->max_entries; i++)
203 if (!(entrymap[i] & ET_FREE_LIST))
206 for (j=q->entry_table[i].first_data_block; j; j=q->next_table[j])
209 return "inconsistent entry block list";
210 blockmap[j] |= BT_ALLOC;
213 if (((q->entry_table[i].data_len + q->hdr->block_size - 1) >> q->hdr->block_shift) != blocks)
214 return "inconsistent entry data length";
217 /* Check if all blocks belong somewhere */
218 for (i=q->hdr->first_data_block; i < q->hdr->num_blocks; i++)
221 DBG("Block %d unreferenced", i);
222 return "unreferenced blocks found";
229 do_audit(struct qache *q)
231 byte *entry_map = xmalloc_zero(q->hdr->max_entries);
232 byte *block_map = xmalloc_zero(q->hdr->num_blocks);
233 byte *err = audit_entries(q, entry_map);
235 err = audit_blocks(q, entry_map, block_map);
242 qache_setup_pointers(struct qache *q)
244 q->hdr = (struct qache_header *) q->mmap_data;
245 q->entry_table = (struct qache_entry *) (q->mmap_data + q->hdr->entry_table_start);
246 q->hash_table = (u32 *) (q->mmap_data + q->hdr->hash_table_start);
247 q->next_table = (u32 *) (q->mmap_data + q->hdr->next_table_start);
251 qache_open_existing(struct qache *q, struct qache_params *par)
253 if ((q->fd = open(q->file_name, O_RDWR, 0)) < 0)
257 byte *err = "stat failed";
258 if (fstat(q->fd, &st) < 0)
261 err = "invalid file size";
262 if (st.st_size < (int)sizeof(struct qache_header) || (st.st_size % par->block_size))
264 q->file_size = st.st_size;
266 err = "requested size change";
267 if (q->file_size != par->cache_size)
271 if ((q->mmap_data = mmap(NULL, q->file_size, PROT_READ | PROT_WRITE, MAP_SHARED, q->fd, 0)) == MAP_FAILED)
273 struct qache_header *h = (struct qache_header *) q->mmap_data;
275 qache_setup_pointers(q);
278 err = "incompatible format";
279 if (h->magic != QACHE_MAGIC ||
280 h->block_size != par->block_size ||
281 h->max_entries != par->max_entries ||
282 h->format_id != par->format_id)
283 goto unlock_and_fail;
285 err = "incomplete file";
286 if (h->num_blocks*h->block_size != q->file_size)
287 goto unlock_and_fail;
289 if (err = do_audit(q))
290 goto unlock_and_fail;
293 log(L_INFO, "Cache %s: using existing data", q->file_name);
298 munmap(q->mmap_data, q->file_size);
300 log(L_INFO, "Cache %s: ignoring old contents (%s)", q->file_name, err);
306 qache_create(struct qache *q, struct qache_params *par)
308 q->fd = open(q->file_name, O_RDWR | O_CREAT | O_TRUNC, 0666);
310 die("Cache %s: unable to create (%m)", q->file_name);
311 struct fastbuf *fb = bfdopen_shared(q->fd, 16384);
313 struct qache_header h;
314 bzero(&h, sizeof(h));
315 h.magic = QACHE_MAGIC;
316 h.block_size = par->block_size;
317 h.block_shift = bit_fls(h.block_size);
318 h.num_blocks = par->cache_size >> h.block_shift;
319 h.format_id = par->format_id;
320 h.entry_table_start = sizeof(h);
321 h.max_entries = par->max_entries;
322 h.hash_table_start = h.entry_table_start + h.max_entries * sizeof(struct qache_entry);
324 while (h.hash_size < h.max_entries)
326 h.next_table_start = h.hash_table_start + h.hash_size * 4;
327 h.first_data_block = (h.next_table_start + 4*h.num_blocks + h.block_size - 1) >> h.block_shift;
328 if (h.first_data_block >= h.num_blocks)
329 die("Cache %s: Requested size is too small even to hold the maintenance structures", q->file_name);
330 bwrite(fb, &h, sizeof(h));
332 /* Entry #0: heads of all lists */
333 ASSERT(btell(fb) == h.entry_table_start);
334 struct qache_entry ent;
335 bzero(&ent, sizeof(ent));
336 ent.first_data_block = h.first_data_block;
337 ent.data_len = h.num_blocks - h.first_data_block;
339 bwrite(fb, &ent, sizeof(ent));
342 bzero(&ent, sizeof(ent));
344 for (uns i=1; i<h.max_entries; i++)
346 ent.hash_next = (i == h.max_entries-1 ? 0 : i+1);
347 bwrite(fb, &ent, sizeof(ent));
351 ASSERT(btell(fb) == h.hash_table_start);
352 for (uns i=0; i<h.hash_size; i++)
355 /* The next pointers */
356 ASSERT(btell(fb) == h.next_table_start);
357 for (uns i=0; i<h.num_blocks; i++)
358 bputl(fb, (i < h.first_data_block || i == h.num_blocks-1) ? 0 : i+1);
361 ASSERT(btell(fb) <= h.first_data_block << h.block_shift);
362 while (btell(fb) < h.first_data_block << h.block_shift)
366 for (uns i=h.first_data_block; i<h.num_blocks; i++)
367 for (uns j=0; j<h.block_size; j+=4)
370 ASSERT(btell(fb) == par->cache_size);
372 log(L_INFO, "Cache %s: created (%d bytes, %d slots, %d buckets)", q->file_name, par->cache_size, h.max_entries, h.hash_size);
374 if ((q->mmap_data = mmap(NULL, par->cache_size, PROT_READ | PROT_WRITE, MAP_SHARED, q->fd, 0)) == MAP_FAILED)
375 die("Cache %s: mmap failed (%m)", par->file_name);
376 q->file_size = par->cache_size;
377 qache_setup_pointers(q);
381 qache_open(struct qache_params *par)
383 struct qache *q = xmalloc_zero(sizeof(*q));
384 q->file_name = xstrdup(par->file_name);
386 ASSERT(par->block_size >= 8 && !(par->block_size & (par->block_size-1)));
387 par->cache_size = ALIGN(par->cache_size, par->block_size);
389 if (par->force_reset <= 0 && qache_open_existing(q, par))
391 else if (par->force_reset < 0)
392 die("Cache %s: read-only access requested, but no data available", q->file_name);
394 qache_create(q, par);
399 qache_close(struct qache *q, uns retain_data)
401 munmap(q->mmap_data, q->file_size);
403 if (!retain_data && unlink(q->file_name) < 0)
404 log(L_ERROR, "Cache %s: unlink failed (%m)", q->file_name);
410 qache_hash(struct qache *q, qache_key_t *key)
412 uns h = ((*key)[0] << 24) | ((*key)[1] << 16) | ((*key)[2] << 8) | (*key)[3];
413 return h % q->hdr->hash_size;
417 qache_hash_find(struct qache *q, qache_key_t *key, uns pos_hint)
421 if (pos_hint && pos_hint < q->hdr->max_entries && q->entry_table[pos_hint].data_len != ~0U && !memcmp(q->entry_table[pos_hint].key, key, sizeof(*key)))
424 uns h = qache_hash(q, key);
425 for (uns e = q->hash_table[h]; e; e=q->entry_table[e].hash_next)
426 if (!memcmp(q->entry_table[e].key, key, sizeof(*key)))
432 qache_hash_insert(struct qache *q, uns e)
434 uns h = qache_hash(q, &q->entry_table[e].key);
435 q->entry_table[e].hash_next = q->hash_table[h];
436 q->hash_table[h] = e;
440 qache_hash_remove(struct qache *q, uns e)
442 struct qache_entry *entry = &q->entry_table[e];
444 for (hh=&q->hash_table[qache_hash(q, &entry->key)]; f=*hh; hh=&(q->entry_table[f].hash_next))
445 if (!memcmp(q->entry_table[f].key, entry->key, sizeof(qache_key_t)))
447 *hh = entry->hash_next;
454 qache_alloc_entry(struct qache *q)
456 uns e = q->first_free_entry;
457 ASSERT(q->locked && e);
458 struct qache_entry *entry = &q->entry_table[e];
459 ASSERT(entry->data_len == ~0U);
460 q->first_free_entry = entry->hash_next;
466 qache_free_entry(struct qache *q, uns e)
468 struct qache_entry *entry = &q->entry_table[e];
469 ASSERT(q->locked && entry->data_len != ~0U);
470 entry->data_len = ~0U;
471 entry->hash_next = q->first_free_entry;
472 q->first_free_entry = e;
476 get_block_start(struct qache *q, uns block)
478 ASSERT(block && block < q->hdr->num_blocks);
479 return q->mmap_data + (block << q->hdr->block_shift);
483 qache_alloc_block(struct qache *q)
485 ASSERT(q->locked && q->num_free_blocks);
486 uns blk = q->first_free_block;
487 q->first_free_block = q->next_table[blk];
488 q->num_free_blocks--;
489 DBG("\tAllocated block %d", blk);
494 qache_free_block(struct qache *q, uns blk)
497 q->next_table[blk] = q->first_free_block;
498 q->first_free_block = blk;
499 q->num_free_blocks++;
500 DBG("\tFreed block %d", blk);
504 qache_lru_insert(struct qache *q, uns e)
506 struct qache_entry *head = &q->entry_table[0];
507 struct qache_entry *entry = &q->entry_table[e];
508 ASSERT(q->locked && !entry->lru_prev && !entry->lru_next);
509 uns succe = head->lru_next;
510 struct qache_entry *succ = &q->entry_table[succe];
513 entry->lru_next = succe;
518 qache_lru_remove(struct qache *q, uns e)
521 struct qache_entry *entry = &q->entry_table[e];
522 q->entry_table[entry->lru_prev].lru_next = entry->lru_next;
523 q->entry_table[entry->lru_next].lru_prev = entry->lru_prev;
524 entry->lru_prev = entry->lru_next = 0;
528 qache_lru_get(struct qache *q)
530 return q->entry_table[0].lru_prev;
534 qache_ll_delete(struct qache *q, uns e)
536 struct qache_entry *entry = &q->entry_table[e];
537 uns blk = entry->first_data_block;
538 while (entry->data_len)
540 uns next = q->next_table[blk];
541 qache_free_block(q, blk);
543 if (entry->data_len >= q->hdr->block_size)
544 entry->data_len -= q->hdr->block_size;
548 qache_lru_remove(q, e);
549 qache_hash_remove(q, e);
550 qache_free_entry(q, e);
554 qache_insert(struct qache *q, qache_key_t *key, uns pos_hint, void *data, uns size)
558 uns e = qache_hash_find(q, key, pos_hint);
561 qache_ll_delete(q ,e);
562 DBG("Insert <%s>: deleting old entry %d", format_key(key), e);
565 uns blocks = (size + q->hdr->block_size - 1) >> q->hdr->block_shift;
566 if (blocks > q->hdr->num_blocks - q->hdr->first_data_block)
571 while (q->num_free_blocks < blocks || !q->first_free_entry)
573 e = qache_lru_get(q);
574 DBG("Insert <%s>: evicting entry %d to make room for %d blocks", format_key(key), e, blocks);
576 qache_ll_delete(q, e);
578 e = qache_alloc_entry(q);
579 struct qache_entry *entry = &q->entry_table[e];
580 entry->data_len = size;
581 memcpy(entry->key, key, sizeof(*key));
582 DBG("Insert <%s>: created entry %d with %d data blocks", format_key(key), e, blocks);
584 entry->first_data_block = 0;
587 uns chunk = (size & (q->hdr->block_size-1)) ? : q->hdr->block_size;
588 uns blk = qache_alloc_block(q);
589 q->next_table[blk] = entry->first_data_block;
590 memcpy(get_block_start(q, blk), data+size-chunk, chunk);
591 qache_msync_block(q, blk);
592 entry->first_data_block = blk;
596 qache_lru_insert(q, e);
597 qache_hash_insert(q, e);
603 copy_out(struct qache *q, struct qache_entry *entry, byte **datap, uns *sizep, uns start)
608 uns avail = (start > entry->data_len) ? 0 : entry->data_len - start;
609 uns xfer = MIN(size, avail);
614 *datap = xmalloc(xfer);
615 uns blk = entry->first_data_block;
616 while (start >= q->hdr->block_size)
618 blk = q->next_table[blk];
619 start -= q->hdr->block_size;
624 uns len = MIN(xfer, q->hdr->block_size - start);
625 memcpy(data, get_block_start(q, blk), len);
626 blk = q->next_table[blk];
638 qache_lookup(struct qache *q, qache_key_t *key, uns pos_hint, byte **datap, uns *sizep, uns start)
641 uns e = qache_hash_find(q, key, pos_hint);
644 struct qache_entry *entry = &q->entry_table[e];
645 DBG("Lookup <%s>: found entry %d", format_key(key), e);
646 qache_lru_remove(q, e);
647 qache_lru_insert(q, e);
648 copy_out(q, entry, datap, sizep, start);
649 qache_unlock(q, 1); /* Yes, modified -- we update the LRU */
653 DBG("Lookup <%s>: not found", format_key(key));
660 qache_probe(struct qache *q, qache_key_t *key, uns pos, byte **datap, uns *sizep, uns start)
662 if (!pos || pos >= q->hdr->max_entries)
664 DBG("Probe %d: Out of range", pos);
670 struct qache_entry *entry = &q->entry_table[pos];
671 if (entry->data_len != ~0U)
673 DBG("Probe %d: Found key <%s>", format_key(entry->key));
675 memcpy(key, entry->key, sizeof(qache_key_t));
676 copy_out(q, entry, datap, sizep, start);
680 DBG("Probe %d: Empty", pos);
686 qache_delete(struct qache *q, qache_key_t *key, uns pos_hint)
689 uns e = qache_hash_find(q, key, pos_hint);
692 DBG("Delete <%s: deleting entry %d", format_key(key), e);
693 qache_ll_delete(q, e);
696 DBG("Delete <%s>: No match", format_key(key));
702 qache_debug(struct qache *q)
704 log(L_DEBUG, "Cache %s: block_size=%d (%d data), num_blocks=%d (%d first data), %d slots, %d hash buckets",
705 q->file_name, q->hdr->block_size, q->hdr->block_size, q->hdr->num_blocks, q->hdr->first_data_block,
706 q->hdr->max_entries, q->hdr->hash_size);
708 log(L_DEBUG, "Table of cache entries:");
709 log(L_DEBUG, "\tEntry\tLruPrev\tLruNext\tDataLen\tDataBlk\tHashNxt\tKey");
710 for (uns e=0; e<q->hdr->max_entries; e++)
712 struct qache_entry *ent = &q->entry_table[e];
713 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,
714 ent->first_data_block, ent->hash_next, format_key(&ent->key));
717 log(L_DEBUG, "Hash table:");
718 for (uns h=0; h<q->hdr->hash_size; h++)
719 log(L_DEBUG, "\t%04x\t%d", h, q->hash_table[h]);
721 log(L_DEBUG, "Next pointers:");
722 for (uns blk=q->hdr->first_data_block; blk<q->hdr->num_blocks; blk++)
723 log(L_DEBUG, "\t%d\t%d", blk, q->next_table[blk]);
727 qache_audit(struct qache *q)
731 if (err = do_audit(q))
732 die("Cache %s: %s", q->file_name, err);
738 int main(int argc UNUSED, char **argv UNUSED)
740 struct qache_params par = {
741 .file_name = "tmp/test",
746 .format_id = 0xfeedcafe
748 struct qache *q = qache_open(&par);
750 qache_key_t key = { 0x12, 0x34, 0x56, 0x78, 0x9a, 0xbc, 0xde, 0xf0, 0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef };
756 key[3] = i / 16; key[15] = i % 16;
757 for (j=0; j<11*i; j++)
758 data[j] = 0x33 + i*j;
759 qache_insert(q, &key, 0, data, 11*i);
765 for (i=0; i<100; i++)
767 key[3] = i / 16; key[15] = i % 16;
769 uns sz = sizeof(data);
770 uns e = qache_lookup(q, &key, 0, &dptr, &sz, 0);
775 ASSERT(data[j] == (byte)(0x33 + i*j));
779 log(L_INFO, "Found %d of %d entries", found, N);