lib/qache.c

   1 /*
   2  *      Simple and Quick Shared Memory Cache
   3  *
   4  *      (c) 2005 Martin Mares <mj@ucw.cz>
   5  */
   6
   7 #undef LOCAL_DEBUG
   8
   9 #include "lib/lib.h"
  10 #include "lib/bitops.h"
  11 #include "lib/fastbuf.h"
  12 #include "lib/qache.h"
  13
  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 void
  79 qache_msync(struct qache *q UNUSED, uns start UNUSED, uns len UNUSED)
  80 {
  81 #ifndef CONFIG_LINUX
  82   /* We don't need msyncing on Linux, since the mappings are guaranteed to be coherent */
  83   len += (start % PAGE_SIZE);
  84   start -= start % PAGE_SIZE;
  85   len = ALIGN(len, PAGE_SIZE);
  86   if (msync(q->mmap_data + start, len, MS_ASYNC | MS_INVALIDATE) < 0)
  87     log(L_ERROR, "Cache %s: msync failed: %m", q->file_name);
  88 #endif
  89 }
  90
  91 static void
  92 qache_msync_block(struct qache *q, uns blk)
  93 {
  94   DBG("\tSyncing block %d", blk);
  95   qache_msync(q, blk << q->hdr->block_shift, q->hdr->block_size);
  96 }
  97
  98 static void
  99 qache_lock(struct qache *q)
 100 {
 101   /* We cannot use flock() since it happily permits locking a shared fd (e.g., after fork()) multiple times */
 102   ASSERT(!q->locked);
 103   struct flock fl = { .l_type = F_WRLCK, .l_whence = SEEK_SET, .l_start = 0, .l_len = sizeof(struct qache_header) };
 104   if (fcntl(q->fd, F_SETLKW, &fl) < 0)
 105     die("fcntl lock on %s: %m", q->file_name);
 106   q->locked = 1;
 107   DBG("Locked cache %s", q->file_name);
 108 }
 109
 110 static void
 111 qache_unlock(struct qache *q, uns dirty)
 112 {
 113   ASSERT(q->locked);
 114   if (dirty)                            /* Sync header, entry table and hash table */
 115     qache_msync(q, 0, q->hdr->first_data_block << q->hdr->block_shift);
 116   struct flock fl = { .l_type = F_UNLCK, .l_whence = SEEK_SET, .l_start = 0, .l_len = sizeof(struct qache_header) };
 117   if (fcntl(q->fd, F_SETLKW, &fl) < 0)
 118     die("fcntl unlock on %s: %m", q->file_name);
 119   q->locked = 0;
 120   DBG("Unlocked cache %s (dirty=%d)", q->file_name, dirty);
 121 }
 122
 123 enum entry_audit_flags {
 124   ET_FREE_LIST = 1,
 125   ET_LRU = 2,
 126   ET_HASH = 4
 127 };
 128
 129 static byte *
 130 audit_entries(struct qache *q, byte *entrymap)
 131 {
 132   uns i, j;
 133
 134   DBG("Auditing entries");
 135
 136   /* Check the free list */
 137   i = q->first_free_entry;
 138   while (i)
 139     {
 140       if (i >= q->hdr->max_entries || (entrymap[i] & ET_FREE_LIST) || q->entry_table[i].data_len != ~0U)
 141         return "inconsistent free entry list";
 142       entrymap[i] |= ET_FREE_LIST;
 143       i = q->entry_table[i].hash_next;
 144     }
 145
 146   /* Check the hash table */
 147   for (i=0; i<q->hdr->hash_size; i++)
 148     {
 149       j = q->hash_table[i];
 150       while (j)
 151         {
 152           if (j >= q->hdr->max_entries || (entrymap[j] & (ET_HASH | ET_FREE_LIST)))
 153             return "inconsistent hash chains";
 154           entrymap[j] |= ET_HASH;
 155           j = q->entry_table[j].hash_next;
 156         }
 157     }
 158
 159   /* Check the LRU */
 160   i = 0;
 161   do
 162     {
 163       j = q->entry_table[i].lru_next;
 164       if ((entrymap[i] & (ET_LRU | ET_FREE_LIST)) || j >= q->hdr->max_entries || q->entry_table[j].lru_prev != i)
 165         return "inconsistent LRU list";
 166       entrymap[i] |= ET_LRU;
 167       i = j;
 168     }
 169   while (i);
 170
 171   /* Check if all non-free items are in all lists */
 172   for (i=1; i<q->hdr->max_entries; i++)
 173     {
 174       if (entrymap[i] != ((q->entry_table[i].data_len == ~0U) ? ET_FREE_LIST : (ET_LRU | ET_HASH)))
 175         return "inconsistent lists";
 176     }
 177   return NULL;
 178 }
 179
 180 enum block_audit_flags {
 181   BT_FREE_LIST = 1,
 182   BT_ALLOC = 2
 183 };
 184
 185 static byte *
 186 audit_blocks(struct qache *q, byte *entrymap, byte *blockmap)
 187 {
 188   uns i, j;
 189
 190   DBG("Auditing blocks");
 191
 192   /* Check the free list */
 193   for (i=q->first_free_block; i; i=q->next_table[i])
 194     {
 195       if (i < q->hdr->first_data_block || i >= q->hdr->num_blocks || (blockmap[i] & BT_FREE_LIST))
 196         return "inconsistent free block list";
 197       blockmap[i] |= BT_FREE_LIST;
 198     }
 199
 200   /* Check allocation lists of entries */
 201   for (i=1; i<q->hdr->max_entries; i++)
 202     if (!(entrymap[i] & ET_FREE_LIST))
 203       {
 204         uns blocks = 0;
 205         for (j=q->entry_table[i].first_data_block; j; j=q->next_table[j])
 206           {
 207             if (blockmap[j])
 208               return "inconsistent entry block list";
 209             blockmap[j] |= BT_ALLOC;
 210             blocks++;
 211           }
 212         if (((q->entry_table[i].data_len + q->hdr->block_size - 1) >> q->hdr->block_shift) != blocks)
 213           return "inconsistent entry data length";
 214       }
 215
 216   /* Check if all blocks belong somewhere */
 217   for (i=q->hdr->first_data_block; i < q->hdr->num_blocks; i++)
 218     if (!blockmap[i])
 219       {
 220         DBG("Block %d unreferenced", i);
 221         return "unreferenced blocks found";
 222       }
 223
 224   return NULL;
 225 }
 226
 227 static byte *
 228 do_audit(struct qache *q)
 229 {
 230   byte *entry_map = xmalloc_zero(q->hdr->max_entries);
 231   byte *block_map = xmalloc_zero(q->hdr->num_blocks);
 232   byte *err = audit_entries(q, entry_map);
 233   if (!err)
 234     err = audit_blocks(q, entry_map, block_map);
 235   xfree(block_map);
 236   xfree(entry_map);
 237   return err;
 238 }
 239
 240 static void
 241 qache_setup_pointers(struct qache *q)
 242 {
 243   q->hdr = (struct qache_header *) q->mmap_data;
 244   q->entry_table = (struct qache_entry *) (q->mmap_data + q->hdr->entry_table_start);
 245   q->hash_table = (u32 *) (q->mmap_data + q->hdr->hash_table_start);
 246   q->next_table = (u32 *) (q->mmap_data + q->hdr->next_table_start);
 247 }
 248
 249 static int
 250 qache_open_existing(struct qache *q, struct qache_params *par)
 251 {
 252   if ((q->fd = open(q->file_name, O_RDWR, 0)) < 0)
 253     return 0;
 254
 255   struct stat st;
 256   byte *err = "stat failed";
 257   if (fstat(q->fd, &st) < 0)
 258     goto close_and_fail;
 259
 260   err = "invalid file size";
 261   if (st.st_size < (int)sizeof(struct qache_header) || (st.st_size % par->block_size))
 262     goto close_and_fail;
 263   q->file_size = st.st_size;
 264
 265   err = "requested size change";
 266   if (q->file_size != par->cache_size)
 267     goto close_and_fail;
 268
 269   err = "cannot mmap";
 270   if ((q->mmap_data = mmap(NULL, q->file_size, PROT_READ | PROT_WRITE, MAP_SHARED, q->fd, 0)) == MAP_FAILED)
 271     goto close_and_fail;
 272   struct qache_header *h = (struct qache_header *) q->mmap_data;
 273
 274   qache_setup_pointers(q);
 275   qache_lock(q);
 276
 277   err = "incompatible format";
 278   if (h->magic != QACHE_MAGIC ||
 279       h->block_size != par->block_size ||
 280       h->max_entries != par->max_entries ||
 281       h->format_id != par->format_id)
 282     goto unlock_and_fail;
 283
 284   err = "incomplete file";
 285   if (h->num_blocks*h->block_size != q->file_size)
 286     goto unlock_and_fail;
 287
 288   if (err = do_audit(q))
 289     goto unlock_and_fail;
 290
 291   qache_unlock(q, 0);
 292   log(L_INFO, "Cache %s: using existing data", q->file_name);
 293   return 1;
 294
 295  unlock_and_fail:
 296   qache_unlock(q, 0);
 297   munmap(q->mmap_data, q->file_size);
 298  close_and_fail:
 299   log(L_INFO, "Cache %s: ignoring old contents (%s)", q->file_name, err);
 300   close(q->fd);
 301   return 0;
 302 }
 303
 304 static void
 305 qache_create(struct qache *q, struct qache_params *par)
 306 {
 307   q->fd = open(q->file_name, O_RDWR | O_CREAT | O_TRUNC, 0666);
 308   if (q->fd < 0)
 309     die("Cache %s: unable to create (%m)", q->file_name);
 310   struct fastbuf *fb = bfdopen_shared(q->fd, 16384);
 311
 312   struct qache_header h;
 313   bzero(&h, sizeof(h));
 314   h.magic = QACHE_MAGIC;
 315   h.block_size = par->block_size;
 316   h.block_shift = bit_fls(h.block_size);
 317   h.num_blocks = par->cache_size >> h.block_shift;
 318   h.format_id = par->format_id;
 319   h.entry_table_start = sizeof(h);
 320   h.max_entries = par->max_entries;
 321   h.hash_table_start = h.entry_table_start + h.max_entries * sizeof(struct qache_entry);
 322   h.hash_size = 1;
 323   while (h.hash_size < h.max_entries)
 324     h.hash_size *= 2;
 325   h.next_table_start = h.hash_table_start + h.hash_size * 4;
 326   h.first_data_block = (h.next_table_start + 4*h.num_blocks + h.block_size - 1) >> h.block_shift;
 327   if (h.first_data_block >= h.num_blocks)
 328     die("Cache %s: Requested size is too small even to hold the maintenance structures", q->file_name);
 329   bwrite(fb, &h, sizeof(h));
 330
 331   /* Entry #0: heads of all lists */
 332   ASSERT(btell(fb) == h.entry_table_start);
 333   struct qache_entry ent;
 334   bzero(&ent, sizeof(ent));
 335   ent.first_data_block = h.first_data_block;
 336   ent.data_len = h.num_blocks - h.first_data_block;
 337   ent.hash_next = 1;
 338   bwrite(fb, &ent, sizeof(ent));
 339
 340   /* Other entries */
 341   bzero(&ent, sizeof(ent));
 342   ent.data_len = ~0U;
 343   for (uns i=1; i<h.max_entries; i++)
 344     {
 345       ent.hash_next = (i == h.max_entries-1 ? 0 : i+1);
 346       bwrite(fb, &ent, sizeof(ent));
 347     }
 348
 349   /* The hash table */
 350   ASSERT(btell(fb) == h.hash_table_start);
 351   for (uns i=0; i<h.hash_size; i++)
 352     bputl(fb, 0);
 353
 354   /* The next pointers */
 355   ASSERT(btell(fb) == h.next_table_start);
 356   for (uns i=0; i<h.num_blocks; i++)
 357     bputl(fb, (i < h.first_data_block || i == h.num_blocks-1) ? 0 : i+1);
 358
 359   /* Padding */
 360   ASSERT(btell(fb) <= h.first_data_block << h.block_shift);
 361   while (btell(fb) < h.first_data_block << h.block_shift)
 362     bputc(fb, 0);
 363
 364   /* Data blocks */
 365   for (uns i=h.first_data_block; i<h.num_blocks; i++)
 366     for (uns j=0; j<h.block_size; j+=4)
 367       bputl(fb, 0);
 368
 369   ASSERT(btell(fb) == par->cache_size);
 370   bclose(fb);
 371   log(L_INFO, "Cache %s: created (%d bytes, %d slots, %d buckets)", q->file_name, par->cache_size, h.max_entries, h.hash_size);
 372
 373   if ((q->mmap_data = mmap(NULL, par->cache_size, PROT_READ | PROT_WRITE, MAP_SHARED, q->fd, 0)) == MAP_FAILED)
 374     die("Cache %s: mmap failed (%m)", par->file_name);
 375   q->file_size = par->cache_size;
 376   qache_setup_pointers(q);
 377 }
 378
 379 struct qache *
 380 qache_open(struct qache_params *par)
 381 {
 382   struct qache *q = xmalloc_zero(sizeof(*q));
 383   q->file_name = xstrdup(par->file_name);
 384
 385   ASSERT(par->block_size >= 8 && !(par->block_size & (par->block_size-1)));
 386   par->cache_size = ALIGN(par->cache_size, par->block_size);
 387
 388   if (par->force_reset <= 0 && qache_open_existing(q, par))
 389     ;
 390   else if (par->force_reset < 0)
 391     die("Cache %s: read-only access requested, but no data available", q->file_name);
 392   else
 393     qache_create(q, par);
 394   return q;
 395 }
 396
 397 void
 398 qache_close(struct qache *q, uns retain_data)
 399 {
 400   munmap(q->mmap_data, q->file_size);
 401   close(q->fd);
 402   if (!retain_data && unlink(q->file_name) < 0)
 403     log(L_ERROR, "Cache %s: unlink failed (%m)", q->file_name);
 404   xfree(q->file_name);
 405   xfree(q);
 406 }
 407
 408 static uns
 409 qache_hash(struct qache *q, qache_key_t *key)
 410 {
 411   uns h = ((*key)[0] << 24) | ((*key)[1] << 16) | ((*key)[2] << 8) | (*key)[3];
 412   return h % q->hdr->hash_size;
 413 }
 414
 415 static uns
 416 qache_hash_find(struct qache *q, qache_key_t *key, uns pos_hint)
 417 {
 418   ASSERT(q->locked);
 419
 420   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)))
 421     return pos_hint;
 422
 423   uns h = qache_hash(q, key);
 424   for (uns e = q->hash_table[h]; e; e=q->entry_table[e].hash_next)
 425     if (!memcmp(q->entry_table[e].key, key, sizeof(*key)))
 426       return e;
 427   return 0;
 428 }
 429
 430 static void
 431 qache_hash_insert(struct qache *q, uns e)
 432 {
 433   uns h = qache_hash(q, &q->entry_table[e].key);
 434   q->entry_table[e].hash_next = q->hash_table[h];
 435   q->hash_table[h] = e;
 436 }
 437
 438 static void
 439 qache_hash_remove(struct qache *q, uns e)
 440 {
 441   struct qache_entry *entry = &q->entry_table[e];
 442   uns f, *hh;
 443   for (hh=&q->hash_table[qache_hash(q, &entry->key)]; f=*hh; hh=&(q->entry_table[f].hash_next))
 444     if (!memcmp(q->entry_table[f].key, entry->key, sizeof(qache_key_t)))
 445       {
 446         *hh = entry->hash_next;
 447         return;
 448       }
 449   ASSERT(0);
 450 }
 451
 452 static uns
 453 qache_alloc_entry(struct qache *q)
 454 {
 455   uns e = q->first_free_entry;
 456   ASSERT(q->locked && e);
 457   struct qache_entry *entry = &q->entry_table[e];
 458   ASSERT(entry->data_len == ~0U);
 459   q->first_free_entry = entry->hash_next;
 460   entry->data_len = 0;
 461   return e;
 462 }
 463
 464 static void
 465 qache_free_entry(struct qache *q, uns e)
 466 {
 467   struct qache_entry *entry = &q->entry_table[e];
 468   ASSERT(q->locked && entry->data_len != ~0U);
 469   entry->data_len = ~0U;
 470   entry->hash_next = q->first_free_entry;
 471   q->first_free_entry = e;
 472 }
 473
 474 static inline void *
 475 get_block_start(struct qache *q, uns block)
 476 {
 477   ASSERT(block && block < q->hdr->num_blocks);
 478   return q->mmap_data + (block << q->hdr->block_shift);
 479 }
 480
 481 static uns
 482 qache_alloc_block(struct qache *q)
 483 {
 484   ASSERT(q->locked && q->num_free_blocks);
 485   uns blk = q->first_free_block;
 486   q->first_free_block = q->next_table[blk];
 487   q->num_free_blocks--;
 488   DBG("\tAllocated block %d", blk);
 489   return blk;
 490 }
 491
 492 static void
 493 qache_free_block(struct qache *q, uns blk)
 494 {
 495   ASSERT(q->locked);
 496   q->next_table[blk] = q->first_free_block;
 497   q->first_free_block = blk;
 498   q->num_free_blocks++;
 499   DBG("\tFreed block %d", blk);
 500 }
 501
 502 static void
 503 qache_lru_insert(struct qache *q, uns e)
 504 {
 505   struct qache_entry *head = &q->entry_table[0];
 506   struct qache_entry *entry = &q->entry_table[e];
 507   ASSERT(q->locked && !entry->lru_prev && !entry->lru_next);
 508   uns succe = head->lru_next;
 509   struct qache_entry *succ = &q->entry_table[succe];
 510   head->lru_next = e;
 511   entry->lru_prev = 0;
 512   entry->lru_next = succe;
 513   succ->lru_prev = e;
 514 }
 515
 516 static void
 517 qache_lru_remove(struct qache *q, uns e)
 518 {
 519   ASSERT(q->locked);
 520   struct qache_entry *entry = &q->entry_table[e];
 521   q->entry_table[entry->lru_prev].lru_next = entry->lru_next;
 522   q->entry_table[entry->lru_next].lru_prev = entry->lru_prev;
 523   entry->lru_prev = entry->lru_next = 0;
 524 }
 525
 526 static uns
 527 qache_lru_get(struct qache *q)
 528 {
 529   return q->entry_table[0].lru_prev;
 530 }
 531
 532 static void
 533 qache_ll_delete(struct qache *q, uns e)
 534 {
 535   struct qache_entry *entry = &q->entry_table[e];
 536   uns blk = entry->first_data_block;
 537   while (entry->data_len)
 538     {
 539       uns next = q->next_table[blk];
 540       qache_free_block(q, blk);
 541       blk = next;
 542       if (entry->data_len >= q->hdr->block_size)
 543         entry->data_len -= q->hdr->block_size;
 544       else
 545         entry->data_len = 0;
 546     }
 547   qache_lru_remove(q, e);
 548   qache_hash_remove(q, e);
 549   qache_free_entry(q, e);
 550 }
 551
 552 uns
 553 qache_insert(struct qache *q, qache_key_t *key, uns pos_hint, void *data, uns size)
 554 {
 555   qache_lock(q);
 556
 557   uns e = qache_hash_find(q, key, pos_hint);
 558   if (e)
 559     {
 560       qache_ll_delete(q ,e);
 561       DBG("Insert <%s>: deleting old entry %d", format_key(key), e);
 562     }
 563
 564   uns blocks = (size + q->hdr->block_size - 1) >> q->hdr->block_shift;
 565   if (blocks > q->hdr->num_blocks - q->hdr->first_data_block)
 566     {
 567       qache_unlock(q, 0);
 568       return 0;
 569     }
 570   while (q->num_free_blocks < blocks || !q->first_free_entry)
 571     {
 572       e = qache_lru_get(q);
 573       DBG("Insert <%s>: evicting entry %d to make room for %d blocks", format_key(key), e, blocks);
 574       ASSERT(e);
 575       qache_ll_delete(q, e);
 576     }
 577   e = qache_alloc_entry(q);
 578   struct qache_entry *entry = &q->entry_table[e];
 579   entry->data_len = size;
 580   memcpy(entry->key, key, sizeof(*key));
 581   DBG("Insert <%s>: created entry %d with %d data blocks", format_key(key), e, blocks);
 582
 583   entry->first_data_block = 0;
 584   while (size)
 585     {
 586       uns chunk = (size & (q->hdr->block_size-1)) ? : q->hdr->block_size;
 587       uns blk = qache_alloc_block(q);
 588       q->next_table[blk] = entry->first_data_block;
 589       memcpy(get_block_start(q, blk), data+size-chunk, chunk);
 590       qache_msync_block(q, blk);
 591       entry->first_data_block = blk;
 592       size -= chunk;
 593     }
 594
 595   qache_lru_insert(q, e);
 596   qache_hash_insert(q, e);
 597   qache_unlock(q, 1);
 598   return e;
 599 }
 600
 601 static void
 602 copy_out(struct qache *q, struct qache_entry *entry, byte **datap, uns *sizep, uns start)
 603 {
 604   if (sizep)
 605     {
 606       uns size = *sizep;
 607       uns avail = (start > entry->data_len) ? 0 : entry->data_len - start;
 608       uns xfer = MIN(size, avail);
 609       *sizep = avail;
 610       if (datap)
 611         {
 612           if (!*datap)
 613             *datap = xmalloc(xfer);
 614           uns blk = entry->first_data_block;
 615           while (start >= q->hdr->block_size)
 616             {
 617               blk = q->next_table[blk];
 618               start -= q->hdr->block_size;
 619             }
 620           byte *data = *datap;
 621           while (xfer)
 622             {
 623               uns len = MIN(xfer, q->hdr->block_size - start);
 624               memcpy(data, get_block_start(q, blk), len);
 625               blk = q->next_table[blk];
 626               data += len;
 627               xfer -= len;
 628               start = 0;
 629             }
 630         }
 631     }
 632   else
 633     ASSERT(!datap);
 634 }
 635
 636 uns
 637 qache_lookup(struct qache *q, qache_key_t *key, uns pos_hint, byte **datap, uns *sizep, uns start)
 638 {
 639   qache_lock(q);
 640   uns e = qache_hash_find(q, key, pos_hint);
 641   if (e)
 642     {
 643       struct qache_entry *entry = &q->entry_table[e];
 644       DBG("Lookup <%s>: found entry %d", format_key(key), e);
 645       qache_lru_remove(q, e);
 646       qache_lru_insert(q, e);
 647       copy_out(q, entry, datap, sizep, start);
 648       qache_unlock(q, 1);     /* Yes, modified -- we update the LRU */
 649     }
 650   else
 651     {
 652       DBG("Lookup <%s>: not found", format_key(key));
 653       qache_unlock(q, 0);
 654     }
 655   return e;
 656 }
 657
 658 uns
 659 qache_probe(struct qache *q, qache_key_t *key, uns pos, byte **datap, uns *sizep, uns start)
 660 {
 661   if (!pos || pos >= q->hdr->max_entries)
 662     {
 663       DBG("Probe %d: Out of range", pos);
 664       return ~0U;
 665     }
 666
 667   qache_lock(q);
 668   uns ret = 0;
 669   struct qache_entry *entry = &q->entry_table[pos];
 670   if (entry->data_len != ~0U)
 671     {
 672       DBG("Probe %d: Found key <%s>", format_key(entry->key));
 673       if (key)
 674         memcpy(key, entry->key, sizeof(qache_key_t));
 675       copy_out(q, entry, datap, sizep, start);
 676       ret = pos;
 677     }
 678   else
 679     DBG("Probe %d: Empty", pos);
 680   qache_unlock(q, 0);
 681   return ret;
 682 }
 683
 684 uns
 685 qache_delete(struct qache *q, qache_key_t *key, uns pos_hint)
 686 {
 687   qache_lock(q);
 688   uns e = qache_hash_find(q, key, pos_hint);
 689   if (e)
 690     {
 691       DBG("Delete <%s: deleting entry %d", format_key(key), e);
 692       qache_ll_delete(q, e);
 693     }
 694   else
 695     DBG("Delete <%s>: No match", format_key(key));
 696   qache_unlock(q, 1);
 697   return e;
 698 }
 699
 700 void
 701 qache_debug(struct qache *q)
 702 {
 703   log(L_DEBUG, "Cache %s: block_size=%d (%d data), num_blocks=%d (%d first data), %d slots, %d hash buckets",
 704       q->file_name, q->hdr->block_size, q->hdr->block_size, q->hdr->num_blocks, q->hdr->first_data_block,
 705       q->hdr->max_entries, q->hdr->hash_size);
 706
 707   log(L_DEBUG, "Table of cache entries:");
 708   log(L_DEBUG, "\tEntry\tLruPrev\tLruNext\tDataLen\tDataBlk\tHashNxt\tKey");
 709   for (uns e=0; e<q->hdr->max_entries; e++)
 710     {
 711       struct qache_entry *ent = &q->entry_table[e];
 712       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,
 713           ent->first_data_block, ent->hash_next, format_key(&ent->key));
 714     }
 715
 716   log(L_DEBUG, "Hash table:");
 717   for (uns h=0; h<q->hdr->hash_size; h++)
 718     log(L_DEBUG, "\t%04x\t%d", h, q->hash_table[h]);
 719
 720   log(L_DEBUG, "Next pointers:");
 721   for (uns blk=q->hdr->first_data_block; blk<q->hdr->num_blocks; blk++)
 722     log(L_DEBUG, "\t%d\t%d", blk, q->next_table[blk]);
 723 }
 724
 725 void
 726 qache_audit(struct qache *q)
 727 {
 728   byte *err;
 729   qache_lock(q);
 730   if (err = do_audit(q))
 731     die("Cache %s: %s", q->file_name, err);
 732   qache_unlock(q, 0);
 733 }
 734
 735 #ifdef TEST
 736
 737 int main(int argc UNUSED, char **argv UNUSED)
 738 {
 739   struct qache_params par = {
 740     .file_name = "tmp/test",
 741     .block_size = 256,
 742     .cache_size = 65536,
 743     .max_entries = 123,
 744     .force_reset = 0,
 745     .format_id = 0xfeedcafe
 746   };
 747   struct qache *q = qache_open(&par);
 748
 749   qache_key_t key = { 0x12, 0x34, 0x56, 0x78, 0x9a, 0xbc, 0xde, 0xf0, 0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef };
 750 #define N 100
 751   uns i, j;
 752   byte data[11*N];
 753   for (i=0; i<N; i++)
 754     {
 755       key[3] = i / 16; key[15] = i % 16;
 756       for (j=0; j<11*i; j++)
 757         data[j] = 0x33 + i*j;
 758       qache_insert(q, &key, 0, data, 11*i);
 759     }
 760   qache_debug(q);
 761   qache_audit(q);
 762
 763   uns found = 0;
 764   for (i=0; i<100; i++)
 765     {
 766       key[3] = i / 16; key[15] = i % 16;
 767       byte *dptr = data;
 768       uns sz = sizeof(data);
 769       uns e = qache_lookup(q, &key, 0, &dptr, &sz, 0);
 770       if (e)
 771         {
 772           ASSERT(sz == 11*i);
 773           for (j=0; j<sz; j++)
 774             ASSERT(data[j] == (byte)(0x33 + i*j));
 775           found++;
 776         }
 777     }
 778   log(L_INFO, "Found %d of %d entries", found, N);
 779
 780   qache_close(q, 1);
 781   return 0;
 782 }
 783
 784 #endif