lib/qache.c

   1 /*
   2  *      Simple and Quick Shared Memory Cache
   3  *
   4  *      (c) 2005 Martin Mares <mj@ucw.cz>
   5  */
   6
   7 #include "lib/lib.h"
   8 #include "lib/fastbuf.h"
   9 #include "lib/qache.h"
  10
  11 #include <stdlib.h>
  12 #include <unistd.h>
  13 #include <fcntl.h>
  14 #include <sys/mman.h>
  15 #include <sys/user.h>
  16
  17 /*
  18  *  On-disk format:
  19  *      qache_header
  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
  24  */
  25
  26 struct qache_header {
  27   u32 magic;                            /* QCACHE_MAGIC */
  28   u32 block_size;                       /* Parameters as in qache_params */
  29   u32 block_shift;                      /* block_size = 1 << block_shift */
  30   u32 num_blocks;
  31   u32 format_id;
  32   u32 entry_table_start;                /* Array of qache_entry's */
  33   u32 max_entries;
  34   u32 hash_table_start;                 /* Hash table containing all keys */
  35   u32 hash_size;
  36   u32 first_data_block;
  37 };
  38
  39 #define QACHE_MAGIC 0xb79f6d12
  40
  41 struct qache_entry {
  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 */
  45   qache_key_t key;
  46   u32 hash_next;                        /* Entry #0: first free entry, Free entries: next free */
  47 };
  48
  49 struct qache {
  50   struct qache_header *hdr;
  51   struct qache_entry *entry_table;
  52   u32 *hash_table;
  53   int fd;
  54   byte *mmap_data;
  55   uns file_size;
  56   byte *file_name;
  57   uns locked;
  58   uns data_block_size;
  59 };
  60
  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
  64
  65 static int
  66 qache_open_existing(struct qache *q, struct qache_params *par)
  67 {
  68   if ((q->fd = open(q->file_name, O_RDWR, 0)) < 0)
  69     return 0;
  70
  71   struct stat st;
  72   byte *err = "stat failed";
  73   if (fstat(q->fd, &st) < 0)
  74     goto close_and_fail;
  75
  76   err = "invalid file size";
  77   if (st.st_size < (int)sizeof(struct qache_header) || (st.st_size % par->block_size))
  78     goto close_and_fail;
  79   q->file_size = st.st_size;
  80
  81   err = "requested size change";
  82   if (q->file_size != par->cache_size)
  83     goto close_and_fail;
  84
  85   err = "cannot mmap";
  86   if ((q->mmap_data = mmap(NULL, q->file_size, PROT_READ | PROT_WRITE, MAP_SHARED, q->fd, 0)) == MAP_FAILED)
  87     goto close_and_fail;
  88   struct qache_header *h = (struct qache_header *) q->mmap_data;
  89
  90   err = "incompatible format";
  91   if (h->magic != QACHE_MAGIC ||
  92       h->block_size != par->block_size ||
  93       h->format_id != par->format_id)
  94     goto unmap_and_fail;
  95
  96   err = "incomplete file";
  97   if (h->num_blocks*h->block_size != q->file_size)
  98     goto unmap_and_fail;
  99
 100   /* FIXME: Audit cache file contents */
 101
 102   log(L_INFO, "Cache %s: using existing data", q->file_name);
 103   return 1;
 104
 105  unmap_and_fail:
 106   munmap(q->mmap_data, q->file_size);
 107  close_and_fail:
 108   log(L_INFO, "Cache %s: ignoring old contents (%s)", q->file_name, err);
 109   close(q->fd);
 110   return 0;
 111 }
 112
 113 static void
 114 qache_create(struct qache *q, struct qache_params *par)
 115 {
 116   q->fd = open(q->file_name, O_RDWR | O_CREAT | O_TRUNC, 0666);
 117   if (q->fd < 0)
 118     die("Cache %s: unable to create (%m)", q->file_name);
 119   struct fastbuf *fb = bfdopen_shared(q->fd, 16384);
 120
 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);
 131   h.hash_size = 1;
 132   while (h.hash_size < h.max_entries)
 133     h.hash_size *= 2;
 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));
 138
 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;
 145   ent.hash_next = 1;
 146   bwrite(fb, &ent, sizeof(ent));
 147
 148   /* Other entries */
 149   bzero(&ent, sizeof(ent));
 150   ent.data_len = ~0U;
 151   for (uns i=1; i<=h.max_entries; i++)
 152     {
 153       ent.hash_next = (i == h.max_entries ? 0 : i+1);
 154       bwrite(fb, &ent, sizeof(ent));
 155     }
 156
 157   /* The hash table */
 158   ASSERT(btell(fb) == h.hash_table_start);
 159   for (uns i=0; i<h.hash_size; i++)
 160     bputl(fb, 0);
 161
 162   /* Padding */
 163   ASSERT(btell(fb) <= h.first_data_block << h.block_shift);
 164   while (btell(fb) < h.first_data_block << h.block_shift)
 165     bputc(fb, 0);
 166
 167   /* Data blocks */
 168   for (uns i=h.first_data_block; i<h.num_blocks; i++)
 169     {
 170       bputl(fb, (i == h.num_blocks-1 ? 0 : i+1));
 171       for (uns i=4; i<h.block_size; i+=4)
 172         bputl(fb, 0);
 173     }
 174
 175   ASSERT(btell(fb) == par->cache_size);
 176   bclose(fb);
 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);
 178
 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;
 182 }
 183
 184 struct qache *
 185 qache_open(struct qache_params *par)
 186 {
 187   struct qache *q = xmalloc_zero(sizeof(*q));
 188   q->file_name = xstrdup(par->file_name);
 189
 190   ASSERT(par->block_size >= 8 && !(par->block_size & (par->block_size-1)));
 191   par->cache_size = ALIGN(par->cache_size, par->block_size);
 192
 193   if (par->force_reset <= 0 && qache_open_existing(q, par))
 194     ;
 195   else if (par->force_reset < 0)
 196     die("Cache %s: read-only access requested, but no data available");
 197   else
 198     qache_create(q, par);
 199
 200   /* FIXME: Remember `closed correctly' status */
 201
 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;
 206   return q;
 207 }
 208
 209 void
 210 qache_close(struct qache *q, uns retain_data)
 211 {
 212   munmap(q->mmap_data, q->file_size);
 213   close(q->fd);
 214   if (!retain_data && unlink(q->file_name) < 0)
 215     log(L_ERROR, "Cache %s: unlink failed (%m)", q->file_name);
 216   xfree(q->file_name);
 217   xfree(q);
 218 }
 219
 220 static void
 221 qache_msync(struct qache *q, uns start, uns len)
 222 {
 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? */
 229 }
 230
 231 static void
 232 qache_msync_block(struct qache *q, uns blk)
 233 {
 234   qache_msync(q, blk << q->hdr->block_shift, q->hdr->block_size);
 235 }
 236
 237 static void
 238 qache_lock(struct qache *q)
 239 {
 240   /* We cannot use flock() since it happily permits locking a shared fd (e.g., after fork()) multiple times */
 241   ASSERT(!q->locked);
 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);
 245   q->locked = 1;
 246 }
 247
 248 static void
 249 qache_unlock(struct qache *q, uns dirty)
 250 {
 251   ASSERT(q->locked);
 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);
 257   q->locked = 0;
 258 }
 259
 260 static uns
 261 qache_hash(struct qache *q, qache_key_t *key)
 262 {
 263   uns h = ((*key)[0] << 24) | ((*key)[1] << 16) | ((*key)[2] << 8) | (*key)[3];
 264   return h % q->hdr->hash_size;
 265 }
 266
 267 static uns
 268 qache_hash_find(struct qache *q, qache_key_t *key, uns pos_hint)
 269 {
 270   ASSERT(q->locked);
 271
 272   if (pos_hint && pos_hint <= q->hdr->max_entries && !memcmp(q->entry_table[pos_hint].key, key, sizeof(*key)))
 273     return pos_hint;
 274
 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)))
 278       return e;
 279   return 0;
 280 }
 281
 282 static void
 283 qache_hash_insert(struct qache *q, uns e)
 284 {
 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;
 288 }
 289
 290 static void
 291 qache_hash_remove(struct qache *q, uns e)
 292 {
 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)))
 297       {
 298         *hh = entry->hash_next;
 299         return;
 300       }
 301   ASSERT(0);
 302 }
 303
 304 static uns
 305 qache_alloc_entry(struct qache *q)
 306 {
 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;
 312   entry->data_len = 0;
 313   return e;
 314 }
 315
 316 static void
 317 qache_free_entry(struct qache *q, uns e)
 318 {
 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;
 324 }
 325
 326 static inline void *
 327 get_block_start(struct qache *q, uns block)
 328 {
 329   ASSERT(block && block < q->hdr->num_blocks);
 330   return q->mmap_data + (block << q->hdr->block_shift);
 331 }
 332
 333 static inline void *
 334 get_block_data(struct qache *q, uns block)
 335 {
 336   return (byte*)get_block_start(q, block) + 4;
 337 }
 338
 339 static inline u32
 340 get_block_next(struct qache *q, uns block)
 341 {
 342   return *(u32*)get_block_start(q, block);
 343 }
 344
 345 static inline void
 346 set_block_next(struct qache *q, uns block, uns next)
 347 {
 348   *(u32*)get_block_start(q, block) = next;
 349 }
 350
 351 static uns
 352 qache_alloc_block(struct qache *q)
 353 {
 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--;
 358   return blk;
 359 }
 360
 361 static void
 362 qache_free_block(struct qache *q, uns blk)
 363 {
 364   ASSERT(q->locked);
 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++;
 369 }
 370
 371 static void
 372 qache_lru_insert(struct qache *q, uns e)
 373 {
 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];
 379   head->lru_next = e;
 380   entry->lru_prev = 0;
 381   entry->lru_next = succe;
 382   succ->lru_prev = e;
 383 }
 384
 385 static void
 386 qache_lru_remove(struct qache *q, uns e)
 387 {
 388   ASSERT(q->locked);
 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;
 393 }
 394
 395 static uns
 396 qache_lru_get(struct qache *q)
 397 {
 398   return q->entry_table[0].lru_prev;
 399 }
 400
 401 static void
 402 qache_ll_delete(struct qache *q, uns e)
 403 {
 404   struct qache_entry *entry = &q->entry_table[e];
 405   uns blk = entry->first_data_block;
 406   while (entry->data_len)
 407     {
 408       uns next = get_block_next(q, blk);
 409       qache_free_block(q, blk);
 410       blk = next;
 411       if (entry->data_len >= q->data_block_size)
 412         entry->data_len -= q->data_block_size;
 413       else
 414         entry->data_len = 0;
 415     }
 416   qache_lru_remove(q, e);
 417   qache_hash_remove(q, e);
 418   qache_free_entry(q, e);
 419 }
 420
 421 uns
 422 qache_insert(struct qache *q, qache_key_t *key, uns pos_hint, void *data, uns size)
 423 {
 424   qache_lock(q);
 425
 426   uns e = qache_hash_find(q, key, pos_hint);
 427   if (e)
 428     qache_ll_delete(q ,e);
 429
 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)
 432     {
 433       qache_unlock(q, 0);
 434       return 0;
 435     }
 436   while (q->num_free_blocks < blocks)
 437     {
 438       e = qache_lru_get(q);
 439       ASSERT(e);
 440       qache_ll_delete(q, e);
 441     }
 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));
 446
 447   entry->first_data_block = 0;
 448   while (size)
 449     {
 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;
 456       size -= chunk;
 457     }
 458
 459   qache_lru_insert(q, e);
 460   qache_hash_insert(q, e);
 461   qache_unlock(q, 1);
 462   return e;
 463 }
 464
 465 uns
 466 qache_lookup(struct qache *q, qache_key_t *key, uns pos_hint, void **datap, uns *sizep, uns start)
 467 {
 468   qache_lock(q);
 469   uns e = qache_hash_find(q, key, pos_hint);
 470   if (e)
 471     {
 472       struct qache_entry *entry = &q->entry_table[e];
 473       qache_lru_remove(q, e);
 474       qache_lru_insert(q, e);
 475       if (sizep)
 476         {
 477           uns size = *sizep;
 478           uns avail = (size > entry->data_len) ? 0 : entry->data_len - size;
 479           uns xfer = MIN(*sizep, avail);
 480           *sizep = avail;
 481           if (datap)
 482             {
 483               if (!*datap)
 484                 *datap = xmalloc(xfer);
 485               uns blk = entry->first_data_block;
 486               while (start >= q->data_block_size)
 487                 {
 488                   blk = get_block_next(q, blk);
 489                   start -= q->data_block_size;
 490                 }
 491               byte *data = *datap;
 492               while (xfer)
 493                 {
 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);
 497                   data += len;
 498                   xfer -= len;
 499                   start = 0;
 500                 }
 501             }
 502         }
 503       else
 504         ASSERT(!datap);
 505     }
 506   qache_unlock(q, 1);                   /* Yes, modified -- we update the LRU */
 507   return e;
 508 }
 509
 510 uns
 511 qache_delete(struct qache *q, qache_key_t *key, uns pos_hint)
 512 {
 513   qache_lock(q);
 514   uns e = qache_hash_find(q, key, pos_hint);
 515   if (e)
 516     qache_ll_delete(q, e);
 517   qache_unlock(q, 1);
 518   return e;
 519 }
 520
 521 void
 522 qache_debug(struct qache *q)
 523 {
 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);
 527
 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++)
 531     {
 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);
 538     }
 539
 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]);
 543
 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));
 547 }
 548
 549 #ifdef TEST
 550
 551 int main(int argc UNUSED, char **argv UNUSED)
 552 {
 553   struct qache_params par = {
 554     .file_name = "tmp/test",
 555     .block_size = 256,
 556     .cache_size = 65536,
 557     .force_reset = 0,
 558     .format_id = 0xfeedcafe
 559   };
 560   struct qache *q = qache_open(&par);
 561
 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);
 565   qache_debug(q);
 566
 567   qache_lookup(q, &key, 0, NULL, NULL, 0);
 568
 569   qache_close(q, 1);
 570   return 0;
 571 }
 572
 573 #endif