lib/qache.c

   1 /*
   2  *      Simple and Quick Shared Memory Cache
   3  *
   4  *      (c) 2005 Martin Mares <mj@ucw.cz>
   5  */
   6
   7 #define LOCAL_DEBUG
   8
   9 #include "lib/lib.h"
  10 #include "lib/fastbuf.h"
  11 #include "lib/qache.h"
  12
  13 #include <stdlib.h>
  14 #include <unistd.h>
  15 #include <fcntl.h>
  16 #include <sys/mman.h>
  17 #include <sys/user.h>
  18
  19 /*
  20  *  The cache lives in a mmapped file of the following format:
  21  *      qache_header
  22  *      qache_entry[max_entries]        table of entries and their keys
  23  *      u32 qache_hash[hash_size]       hash table pointing to keys
  24  *      u32 block_next[num_blocks]      next block pointers
  25  *      padding                         to a multiple of block size
  26  *      blocks[]                        data blocks
  27  */
  28
  29 struct qache_header {
  30   u32 magic;                            /* QCACHE_MAGIC */
  31   u32 block_size;                       /* Parameters as in qache_params */
  32   u32 block_shift;                      /* block_size = 1 << block_shift */
  33   u32 num_blocks;
  34   u32 format_id;
  35   u32 entry_table_start;                /* Array of qache_entry's */
  36   u32 max_entries;
  37   u32 hash_table_start;                 /* Hash table containing all keys */
  38   u32 hash_size;
  39   u32 next_table_start;                 /* Array of next pointers */
  40   u32 first_data_block;
  41 };
  42
  43 #define QACHE_MAGIC 0xb79f6d12
  44
  45 struct qache_entry {
  46   u32 lru_prev, lru_next;               /* Entry #0: head of the cyclic LRU list */
  47   u32 data_len;                         /* Entry #0: number of free blocks, Free entries: ~0U */
  48   u32 first_data_block;                 /* Entry #0: first free block */
  49   qache_key_t key;
  50   u32 hash_next;                        /* Entry #0: first free entry, Free entries: next free */
  51 };
  52
  53 struct qache {
  54   struct qache_header *hdr;
  55   struct qache_entry *entry_table;
  56   u32 *hash_table;
  57   u32 *next_table;
  58   int fd;
  59   byte *mmap_data;
  60   uns file_size;
  61   byte *file_name;
  62   uns locked;
  63 };
  64
  65 #define first_free_entry entry_table[0].hash_next
  66 #define first_free_block entry_table[0].first_data_block
  67 #define num_free_blocks entry_table[0].data_len
  68
  69 static inline byte *
  70 format_key(qache_key_t *key)
  71 {
  72   static byte keybuf[2*sizeof(qache_key_t)+1];
  73   for (uns i=0; i<sizeof(qache_key_t); i++)
  74     sprintf(keybuf+2*i, "%02x", (*key)[i]);
  75   return keybuf;
  76 }
  77
  78 static int
  79 qache_open_existing(struct qache *q, struct qache_params *par)
  80 {
  81   if ((q->fd = open(q->file_name, O_RDWR, 0)) < 0)
  82     return 0;
  83
  84   struct stat st;
  85   byte *err = "stat failed";
  86   if (fstat(q->fd, &st) < 0)
  87     goto close_and_fail;
  88
  89   err = "invalid file size";
  90   if (st.st_size < (int)sizeof(struct qache_header) || (st.st_size % par->block_size))
  91     goto close_and_fail;
  92   q->file_size = st.st_size;
  93
  94   err = "requested size change";
  95   if (q->file_size != par->cache_size)
  96     goto close_and_fail;
  97
  98   err = "cannot mmap";
  99   if ((q->mmap_data = mmap(NULL, q->file_size, PROT_READ | PROT_WRITE, MAP_SHARED, q->fd, 0)) == MAP_FAILED)
 100     goto close_and_fail;
 101   struct qache_header *h = (struct qache_header *) q->mmap_data;
 102
 103   err = "incompatible format";
 104   if (h->magic != QACHE_MAGIC ||
 105       h->block_size != par->block_size ||
 106       h->max_entries != par->max_entries ||
 107       h->format_id != par->format_id)
 108     goto unmap_and_fail;
 109
 110   err = "incomplete file";
 111   if (h->num_blocks*h->block_size != q->file_size)
 112     goto unmap_and_fail;
 113
 114   /* FIXME: Audit cache file contents */
 115
 116   log(L_INFO, "Cache %s: using existing data", q->file_name);
 117   return 1;
 118
 119  unmap_and_fail:
 120   munmap(q->mmap_data, q->file_size);
 121  close_and_fail:
 122   log(L_INFO, "Cache %s: ignoring old contents (%s)", q->file_name, err);
 123   close(q->fd);
 124   return 0;
 125 }
 126
 127 static void
 128 qache_create(struct qache *q, struct qache_params *par)
 129 {
 130   q->fd = open(q->file_name, O_RDWR | O_CREAT | O_TRUNC, 0666);
 131   if (q->fd < 0)
 132     die("Cache %s: unable to create (%m)", q->file_name);
 133   struct fastbuf *fb = bfdopen_shared(q->fd, 16384);
 134
 135   struct qache_header h;
 136   bzero(&h, sizeof(h));
 137   h.magic = QACHE_MAGIC;
 138   h.block_size = par->block_size;
 139   h.block_shift = fls(h.block_size);
 140   h.num_blocks = par->cache_size >> h.block_shift;
 141   h.format_id = par->format_id;
 142   h.entry_table_start = sizeof(h);
 143   h.max_entries = par->max_entries;
 144   h.hash_table_start = h.entry_table_start + (h.max_entries+1) * sizeof(struct qache_entry);
 145   h.hash_size = 1;
 146   while (h.hash_size < h.max_entries)
 147     h.hash_size *= 2;
 148   h.next_table_start = h.hash_table_start + h.hash_size * 4;
 149   h.first_data_block = (h.next_table_start + 4*h.num_blocks + h.block_size - 1) >> h.block_shift;
 150   if (h.first_data_block >= h.num_blocks)
 151     die("Cache %s: Requested size is too small even to hold the maintenance structures", q->file_name);
 152   bwrite(fb, &h, sizeof(h));
 153
 154   /* Entry #0: heads of all lists */
 155   ASSERT(btell(fb) == h.entry_table_start);
 156   struct qache_entry ent;
 157   bzero(&ent, sizeof(ent));
 158   ent.first_data_block = h.first_data_block;
 159   ent.data_len = h.num_blocks - h.first_data_block;
 160   ent.hash_next = 1;
 161   bwrite(fb, &ent, sizeof(ent));
 162
 163   /* Other entries */
 164   bzero(&ent, sizeof(ent));
 165   ent.data_len = ~0U;
 166   for (uns i=1; i<=h.max_entries; i++)
 167     {
 168       ent.hash_next = (i == h.max_entries ? 0 : i+1);
 169       bwrite(fb, &ent, sizeof(ent));
 170     }
 171
 172   /* The hash table */
 173   ASSERT(btell(fb) == h.hash_table_start);
 174   for (uns i=0; i<h.hash_size; i++)
 175     bputl(fb, 0);
 176
 177   /* The next pointers */
 178   ASSERT(btell(fb) == h.next_table_start);
 179   for (uns i=0; i<h.num_blocks; i++)
 180     bputl(fb, (i < h.first_data_block || i == h.num_blocks-1) ? 0 : i+1);
 181
 182   /* Padding */
 183   ASSERT(btell(fb) <= h.first_data_block << h.block_shift);
 184   while (btell(fb) < h.first_data_block << h.block_shift)
 185     bputc(fb, 0);
 186
 187   /* Data blocks */
 188   for (uns i=h.first_data_block; i<h.num_blocks; i++)
 189     for (uns j=0; j<h.block_size; j+=4)
 190       bputl(fb, 0);
 191
 192   ASSERT(btell(fb) == par->cache_size);
 193   bclose(fb);
 194   log(L_INFO, "Cache %s: created (%d bytes, %d slots, %d buckets)", q->file_name, par->cache_size, h.max_entries, h.hash_size);
 195
 196   if ((q->mmap_data = mmap(NULL, par->cache_size, PROT_READ | PROT_WRITE, MAP_SHARED, q->fd, 0)) == MAP_FAILED)
 197     die("Cache %s: mmap failed (%m)", par->cache_size);
 198   q->file_size = par->cache_size;
 199 }
 200
 201 struct qache *
 202 qache_open(struct qache_params *par)
 203 {
 204   struct qache *q = xmalloc_zero(sizeof(*q));
 205   q->file_name = xstrdup(par->file_name);
 206
 207   ASSERT(par->block_size >= 8 && !(par->block_size & (par->block_size-1)));
 208   par->cache_size = ALIGN(par->cache_size, par->block_size);
 209
 210   if (par->force_reset <= 0 && qache_open_existing(q, par))
 211     ;
 212   else if (par->force_reset < 0)
 213     die("Cache %s: read-only access requested, but no data available");
 214   else
 215     qache_create(q, par);
 216
 217   /* FIXME: Remember `closed correctly' status */
 218
 219   q->hdr = (struct qache_header *) q->mmap_data;
 220   q->entry_table = (struct qache_entry *) (q->mmap_data + q->hdr->entry_table_start);
 221   q->hash_table = (u32 *) (q->mmap_data + q->hdr->hash_table_start);
 222   q->next_table = (u32 *) (q->mmap_data + q->hdr->next_table_start);
 223   return q;
 224 }
 225
 226 void
 227 qache_close(struct qache *q, uns retain_data)
 228 {
 229   munmap(q->mmap_data, q->file_size);
 230   close(q->fd);
 231   if (!retain_data && unlink(q->file_name) < 0)
 232     log(L_ERROR, "Cache %s: unlink failed (%m)", q->file_name);
 233   xfree(q->file_name);
 234   xfree(q);
 235 }
 236
 237 static void
 238 qache_msync(struct qache *q, uns start, uns len)
 239 {
 240   len += (start % PAGE_SIZE);
 241   start -= start % PAGE_SIZE;
 242   len = ALIGN(len, PAGE_SIZE);
 243   if (msync(q->mmap_data + start, len, MS_ASYNC | MS_INVALIDATE) < 0)
 244     log(L_ERROR, "Cache %s: msync failed: %m", q->file_name);
 245   /* FIXME: Do we need this on Linux? */
 246 }
 247
 248 static void
 249 qache_msync_block(struct qache *q, uns blk)
 250 {
 251   DBG("\tSyncing block %d", blk);
 252   qache_msync(q, blk << q->hdr->block_shift, q->hdr->block_size);
 253 }
 254
 255 static void
 256 qache_lock(struct qache *q)
 257 {
 258   /* We cannot use flock() since it happily permits locking a shared fd (e.g., after fork()) multiple times */
 259   ASSERT(!q->locked);
 260   struct flock fl = { .l_type = F_WRLCK, .l_whence = SEEK_SET, .l_start = 0, .l_len = sizeof(struct qache_header) };
 261   if (fcntl(q->fd, F_SETLKW, &fl) < 0)
 262     die("fcntl lock on %s: %m", q->file_name);
 263   q->locked = 1;
 264   DBG("Locked cache %s", q->file_name);
 265 }
 266
 267 static void
 268 qache_unlock(struct qache *q, uns dirty)
 269 {
 270   ASSERT(q->locked);
 271   if (dirty)                            /* Sync header, entry table and hash table */
 272     qache_msync(q, 0, q->hdr->first_data_block << q->hdr->block_shift);
 273   struct flock fl = { .l_type = F_UNLCK, .l_whence = SEEK_SET, .l_start = 0, .l_len = sizeof(struct qache_header) };
 274   if (fcntl(q->fd, F_SETLKW, &fl) < 0)
 275     die("fcntl unlock on %s: %m", q->file_name);
 276   q->locked = 0;
 277   DBG("Unlocked cache %s (dirty=%d)", q->file_name, dirty);
 278 }
 279
 280 static uns
 281 qache_hash(struct qache *q, qache_key_t *key)
 282 {
 283   uns h = ((*key)[0] << 24) | ((*key)[1] << 16) | ((*key)[2] << 8) | (*key)[3];
 284   return h % q->hdr->hash_size;
 285 }
 286
 287 static uns
 288 qache_hash_find(struct qache *q, qache_key_t *key, uns pos_hint)
 289 {
 290   ASSERT(q->locked);
 291
 292   if (pos_hint && pos_hint <= q->hdr->max_entries && !memcmp(q->entry_table[pos_hint].key, key, sizeof(*key)))
 293     return pos_hint;
 294
 295   uns h = qache_hash(q, key);
 296   for (uns e = q->hash_table[h]; e; e=q->entry_table[e].hash_next)
 297     if (!memcmp(q->entry_table[e].key, key, sizeof(*key)))
 298       return e;
 299   return 0;
 300 }
 301
 302 static void
 303 qache_hash_insert(struct qache *q, uns e)
 304 {
 305   uns h = qache_hash(q, &q->entry_table[e].key);
 306   q->entry_table[e].hash_next = q->hash_table[h];
 307   q->hash_table[h] = e;
 308 }
 309
 310 static void
 311 qache_hash_remove(struct qache *q, uns e)
 312 {
 313   struct qache_entry *entry = &q->entry_table[e];
 314   uns f, *hh;
 315   for (hh=&q->hash_table[qache_hash(q, &entry->key)]; f=*hh; hh=&(q->entry_table[f].hash_next))
 316     if (!memcmp(q->entry_table[f].key, entry->key, sizeof(qache_key_t)))
 317       {
 318         *hh = entry->hash_next;
 319         return;
 320       }
 321   ASSERT(0);
 322 }
 323
 324 static uns
 325 qache_alloc_entry(struct qache *q)
 326 {
 327   uns e = q->first_free_entry;
 328   ASSERT(q->locked && e);
 329   struct qache_entry *entry = &q->entry_table[e];
 330   ASSERT(entry->data_len == ~0U);
 331   q->first_free_entry = entry->hash_next;
 332   entry->data_len = 0;
 333   return e;
 334 }
 335
 336 static void
 337 qache_free_entry(struct qache *q, uns e)
 338 {
 339   struct qache_entry *entry = &q->entry_table[e];
 340   ASSERT(q->locked && entry->data_len != ~0U);
 341   entry->data_len = ~0U;
 342   entry->hash_next = q->first_free_entry;
 343   q->first_free_entry = e;
 344 }
 345
 346 static inline void *
 347 get_block_start(struct qache *q, uns block)
 348 {
 349   ASSERT(block && block < q->hdr->num_blocks);
 350   return q->mmap_data + (block << q->hdr->block_shift);
 351 }
 352
 353 static uns
 354 qache_alloc_block(struct qache *q)
 355 {
 356   ASSERT(q->locked && q->num_free_blocks);
 357   uns blk = q->first_free_block;
 358   q->first_free_block = q->next_table[blk];
 359   q->num_free_blocks--;
 360   DBG("\tAllocated block %d", blk);
 361   return blk;
 362 }
 363
 364 static void
 365 qache_free_block(struct qache *q, uns blk)
 366 {
 367   ASSERT(q->locked);
 368   q->next_table[blk] = q->first_free_block;
 369   q->first_free_block = blk;
 370   q->num_free_blocks++;
 371   DBG("\tFreed block %d", blk);
 372 }
 373
 374 static void
 375 qache_lru_insert(struct qache *q, uns e)
 376 {
 377   struct qache_entry *head = &q->entry_table[0];
 378   struct qache_entry *entry = &q->entry_table[e];
 379   ASSERT(q->locked && !entry->lru_prev && !entry->lru_next);
 380   uns succe = head->lru_next;
 381   struct qache_entry *succ = &q->entry_table[succe];
 382   head->lru_next = e;
 383   entry->lru_prev = 0;
 384   entry->lru_next = succe;
 385   succ->lru_prev = e;
 386 }
 387
 388 static void
 389 qache_lru_remove(struct qache *q, uns e)
 390 {
 391   ASSERT(q->locked);
 392   struct qache_entry *entry = &q->entry_table[e];
 393   q->entry_table[entry->lru_prev].lru_next = entry->lru_next;
 394   q->entry_table[entry->lru_next].lru_prev = entry->lru_prev;
 395   entry->lru_prev = entry->lru_next = 0;
 396 }
 397
 398 static uns
 399 qache_lru_get(struct qache *q)
 400 {
 401   return q->entry_table[0].lru_prev;
 402 }
 403
 404 static void
 405 qache_ll_delete(struct qache *q, uns e)
 406 {
 407   struct qache_entry *entry = &q->entry_table[e];
 408   uns blk = entry->first_data_block;
 409   while (entry->data_len)
 410     {
 411       uns next = q->next_table[blk];
 412       qache_free_block(q, blk);
 413       blk = next;
 414       if (entry->data_len >= q->hdr->block_size)
 415         entry->data_len -= q->hdr->block_size;
 416       else
 417         entry->data_len = 0;
 418     }
 419   qache_lru_remove(q, e);
 420   qache_hash_remove(q, e);
 421   qache_free_entry(q, e);
 422 }
 423
 424 uns
 425 qache_insert(struct qache *q, qache_key_t *key, uns pos_hint, void *data, uns size)
 426 {
 427   qache_lock(q);
 428
 429   uns e = qache_hash_find(q, key, pos_hint);
 430   if (e)
 431     {
 432       qache_ll_delete(q ,e);
 433       DBG("Insert <%s>: deleting old entry %d", format_key(key), e);
 434     }
 435
 436   uns blocks = (size + q->hdr->block_size - 1) >> q->hdr->block_shift;
 437   if (blocks > q->hdr->num_blocks - q->hdr->first_data_block)
 438     {
 439       qache_unlock(q, 0);
 440       return 0;
 441     }
 442   while (q->num_free_blocks < blocks || !q->first_free_entry)
 443     {
 444       e = qache_lru_get(q);
 445       DBG("Insert <%s>: evicting entry %d to make room for %d blocks", format_key(key), e, blocks);
 446       ASSERT(e);
 447       qache_ll_delete(q, e);
 448     }
 449   e = qache_alloc_entry(q);
 450   struct qache_entry *entry = &q->entry_table[e];
 451   entry->data_len = size;
 452   memcpy(entry->key, key, sizeof(*key));
 453   DBG("Insert <%s>: created entry %d with %d data blocks", format_key(key), e, blocks);
 454
 455   entry->first_data_block = 0;
 456   while (size)
 457     {
 458       uns chunk = (size & (q->hdr->block_size-1)) ? : q->hdr->block_size;
 459       uns blk = qache_alloc_block(q);
 460       q->next_table[blk] = entry->first_data_block;
 461       memcpy(get_block_start(q, blk), data+size-chunk, chunk);
 462       qache_msync_block(q, blk);
 463       entry->first_data_block = blk;
 464       size -= chunk;
 465     }
 466
 467   qache_lru_insert(q, e);
 468   qache_hash_insert(q, e);
 469   qache_unlock(q, 1);
 470   return e;
 471 }
 472
 473 uns
 474 qache_lookup(struct qache *q, qache_key_t *key, uns pos_hint, void **datap, uns *sizep, uns start)
 475 {
 476   qache_lock(q);
 477   uns e = qache_hash_find(q, key, pos_hint);
 478   if (e)
 479     {
 480       struct qache_entry *entry = &q->entry_table[e];
 481       DBG("Lookup <%s>: found entry %d", format_key(key), e);
 482       qache_lru_remove(q, e);
 483       qache_lru_insert(q, e);
 484       if (sizep)
 485         {
 486           uns size = *sizep;
 487           uns avail = (size > entry->data_len) ? 0 : entry->data_len - size;
 488           uns xfer = MIN(*sizep, avail);
 489           *sizep = avail;
 490           if (datap)
 491             {
 492               if (!*datap)
 493                 *datap = xmalloc(xfer);
 494               uns blk = entry->first_data_block;
 495               while (start >= q->hdr->block_size)
 496                 {
 497                   blk = q->next_table[blk];
 498                   start -= q->hdr->block_size;
 499                 }
 500               byte *data = *datap;
 501               while (xfer)
 502                 {
 503                   uns len = MIN(xfer, q->hdr->block_size - start);
 504                   memcpy(data, get_block_start(q, blk), len);
 505                   blk = q->next_table[blk];
 506                   data += len;
 507                   xfer -= len;
 508                   start = 0;
 509                 }
 510             }
 511         }
 512       else
 513         ASSERT(!datap);
 514       qache_unlock(q, 1);     /* Yes, modified -- we update the LRU */
 515     }
 516   else
 517     {
 518       DBG("Lookup <%s>: not found", format_key(key));
 519       qache_unlock(q, 0);
 520     }
 521   return e;
 522 }
 523
 524 uns
 525 qache_delete(struct qache *q, qache_key_t *key, uns pos_hint)
 526 {
 527   qache_lock(q);
 528   uns e = qache_hash_find(q, key, pos_hint);
 529   if (e)
 530     {
 531       DBG("Delete <%s: deleting entry %d", format_key(key), e);
 532       qache_ll_delete(q, e);
 533     }
 534   else
 535     DBG("Delete <%s>: No match", format_key(key));
 536   qache_unlock(q, 1);
 537   return e;
 538 }
 539
 540 void
 541 qache_debug(struct qache *q)
 542 {
 543   log(L_DEBUG, "Cache %s: block_size=%d (%d data), num_blocks=%d (%d first data), %d slots, %d hash buckets",
 544       q->file_name, q->hdr->block_size, q->hdr->block_size, q->hdr->num_blocks, q->hdr->first_data_block,
 545       q->hdr->max_entries, q->hdr->hash_size);
 546
 547   log(L_DEBUG, "Table of cache entries:");
 548   log(L_DEBUG, "\tEntry\tLruPrev\tLruNext\tDataLen\tDataBlk\tHashNxt\tKey");
 549   for (uns e=0; e<=q->hdr->max_entries; e++)
 550     {
 551       struct qache_entry *ent = &q->entry_table[e];
 552       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,
 553           ent->first_data_block, ent->hash_next, format_key(&ent->key));
 554     }
 555
 556   log(L_DEBUG, "Hash table:");
 557   for (uns h=0; h<q->hdr->hash_size; h++)
 558     log(L_DEBUG, "\t%04x\t%d", h, q->hash_table[h]);
 559
 560   log(L_DEBUG, "Next pointers:");
 561   for (uns blk=q->hdr->first_data_block; blk<q->hdr->num_blocks; blk++)
 562     log(L_DEBUG, "\t%d\t%d", blk, q->next_table[blk]);
 563 }
 564
 565 #ifdef TEST
 566
 567 int main(int argc UNUSED, char **argv UNUSED)
 568 {
 569   struct qache_params par = {
 570     .file_name = "tmp/test",
 571     .block_size = 256,
 572     .cache_size = 65536,
 573     .max_entries = 123,
 574     .force_reset = 0,
 575     .format_id = 0xfeedcafe
 576   };
 577   struct qache *q = qache_open(&par);
 578
 579   qache_key_t key = { 0x12, 0x34, 0x56, 0x78, 0x9a, 0xbc, 0xde, 0xf0, 0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef };
 580   byte data[1000] = { '1', '2', '3', '4', '5' };
 581   for (uns i=0; i<100; i++)
 582     {
 583       qache_insert(q, &key, 0, data, 10*i);
 584       key[15]++;
 585     }
 586   qache_debug(q);
 587
 588   qache_lookup(q, &key, 0, NULL, NULL, 0);
 589
 590   qache_close(q, 1);
 591   return 0;
 592 }
 593
 594 #endif