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/stat.h>
  17 #include <sys/mman.h>
  18 #include <sys/user.h>
  19
  20 /*
  21  *  The cache lives in a mmapped file of the following format:
  22  *      qache_header
  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
  28  */
  29
  30 struct qache_header {
  31   u32 magic;                            /* QCACHE_MAGIC */
  32   u32 block_size;                       /* Parameters as in qache_params */
  33   u32 block_shift;                      /* block_size = 1 << block_shift */
  34   u32 num_blocks;
  35   u32 format_id;
  36   u32 entry_table_start;                /* Array of qache_entry's */
  37   u32 max_entries;
  38   u32 hash_table_start;                 /* Hash table containing all keys */
  39   u32 hash_size;
  40   u32 next_table_start;                 /* Array of next pointers */
  41   u32 first_data_block;
  42 };
  43
  44 #define QACHE_MAGIC 0xb79f6d12
  45
  46 struct qache_entry {
  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 */
  50   qache_key_t key;
  51   u32 hash_next;                        /* Entry #0: first free entry, Free entries: next free */
  52 };
  53
  54 struct qache {
  55   struct qache_header *hdr;
  56   struct qache_entry *entry_table;
  57   u32 *hash_table;
  58   u32 *next_table;
  59   int fd;
  60   byte *mmap_data;
  61   uns file_size;
  62   byte *file_name;
  63   uns locked;
  64 };
  65
  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
  69
  70 static inline byte *
  71 format_key(qache_key_t *key)
  72 {
  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]);
  76   return keybuf;
  77 }
  78
  79 static void
  80 qache_msync(struct qache *q UNUSED, uns start UNUSED, uns len UNUSED)
  81 {
  82 #ifndef CONFIG_LINUX
  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_TO(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);
  89 #endif
  90 }
  91
  92 static void
  93 qache_msync_block(struct qache *q, uns blk)
  94 {
  95   DBG("\tSyncing block %d", blk);
  96   qache_msync(q, blk << q->hdr->block_shift, q->hdr->block_size);
  97 }
  98
  99 static void
 100 qache_lock(struct qache *q)
 101 {
 102   /* We cannot use flock() since it happily permits locking a shared fd (e.g., after fork()) multiple times */
 103   ASSERT(!q->locked);
 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);
 107   q->locked = 1;
 108   DBG("Locked cache %s", q->file_name);
 109 }
 110
 111 static void
 112 qache_unlock(struct qache *q, uns dirty)
 113 {
 114   ASSERT(q->locked);
 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);
 120   q->locked = 0;
 121   DBG("Unlocked cache %s (dirty=%d)", q->file_name, dirty);
 122 }
 123
 124 enum entry_audit_flags {
 125   ET_FREE_LIST = 1,
 126   ET_LRU = 2,
 127   ET_HASH = 4
 128 };
 129
 130 static byte *
 131 audit_entries(struct qache *q, byte *entrymap)
 132 {
 133   uns i, j;
 134
 135   DBG("Auditing entries");
 136
 137   /* Check the free list */
 138   i = q->first_free_entry;
 139   while (i)
 140     {
 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;
 145     }
 146
 147   /* Check the hash table */
 148   for (i=0; i<q->hdr->hash_size; i++)
 149     {
 150       j = q->hash_table[i];
 151       while (j)
 152         {
 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;
 157         }
 158     }
 159
 160   /* Check the LRU */
 161   i = 0;
 162   do
 163     {
 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;
 168       i = j;
 169     }
 170   while (i);
 171
 172   /* Check if all non-free items are in all lists */
 173   for (i=1; i<q->hdr->max_entries; i++)
 174     {
 175       if (entrymap[i] != ((q->entry_table[i].data_len == ~0U) ? ET_FREE_LIST : (ET_LRU | ET_HASH)))
 176         return "inconsistent lists";
 177     }
 178   return NULL;
 179 }
 180
 181 enum block_audit_flags {
 182   BT_FREE_LIST = 1,
 183   BT_ALLOC = 2
 184 };
 185
 186 static byte *
 187 audit_blocks(struct qache *q, byte *entrymap, byte *blockmap)
 188 {
 189   uns i, j;
 190
 191   DBG("Auditing blocks");
 192
 193   /* Check the free list */
 194   for (i=q->first_free_block; i; i=q->next_table[i])
 195     {
 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;
 199     }
 200
 201   /* Check allocation lists of entries */
 202   for (i=1; i<q->hdr->max_entries; i++)
 203     if (!(entrymap[i] & ET_FREE_LIST))
 204       {
 205         uns blocks = 0;
 206         for (j=q->entry_table[i].first_data_block; j; j=q->next_table[j])
 207           {
 208             if (blockmap[j])
 209               return "inconsistent entry block list";
 210             blockmap[j] |= BT_ALLOC;
 211             blocks++;
 212           }
 213         if (((q->entry_table[i].data_len + q->hdr->block_size - 1) >> q->hdr->block_shift) != blocks)
 214           return "inconsistent entry data length";
 215       }
 216
 217   /* Check if all blocks belong somewhere */
 218   for (i=q->hdr->first_data_block; i < q->hdr->num_blocks; i++)
 219     if (!blockmap[i])
 220       {
 221         DBG("Block %d unreferenced", i);
 222         return "unreferenced blocks found";
 223       }
 224
 225   return NULL;
 226 }
 227
 228 static byte *
 229 do_audit(struct qache *q)
 230 {
 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);
 234   if (!err)
 235     err = audit_blocks(q, entry_map, block_map);
 236   xfree(block_map);
 237   xfree(entry_map);
 238   return err;
 239 }
 240
 241 static void
 242 qache_setup_pointers(struct qache *q)
 243 {
 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);
 248 }
 249
 250 static int
 251 qache_open_existing(struct qache *q, struct qache_params *par)
 252 {
 253   if ((q->fd = open(q->file_name, O_RDWR, 0)) < 0)
 254     return 0;
 255
 256   struct stat st;
 257   byte *err = "stat failed";
 258   if (fstat(q->fd, &st) < 0)
 259     goto close_and_fail;
 260
 261   err = "invalid file size";
 262   if (st.st_size < (int)sizeof(struct qache_header) || (st.st_size % par->block_size))
 263     goto close_and_fail;
 264   q->file_size = st.st_size;
 265
 266   err = "requested size change";
 267   if (q->file_size != par->cache_size)
 268     goto close_and_fail;
 269
 270   err = "cannot mmap";
 271   if ((q->mmap_data = mmap(NULL, q->file_size, PROT_READ | PROT_WRITE, MAP_SHARED, q->fd, 0)) == MAP_FAILED)
 272     goto close_and_fail;
 273   struct qache_header *h = (struct qache_header *) q->mmap_data;
 274
 275   qache_setup_pointers(q);
 276   qache_lock(q);
 277
 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;
 284
 285   err = "incomplete file";
 286   if (h->num_blocks*h->block_size != q->file_size)
 287     goto unlock_and_fail;
 288
 289   if (err = do_audit(q))
 290     goto unlock_and_fail;
 291
 292   qache_unlock(q, 0);
 293   log(L_INFO, "Cache %s: using existing data", q->file_name);
 294   return 1;
 295
 296  unlock_and_fail:
 297   qache_unlock(q, 0);
 298   munmap(q->mmap_data, q->file_size);
 299  close_and_fail:
 300   log(L_INFO, "Cache %s: ignoring old contents (%s)", q->file_name, err);
 301   close(q->fd);
 302   return 0;
 303 }
 304
 305 static void
 306 qache_create(struct qache *q, struct qache_params *par)
 307 {
 308   q->fd = open(q->file_name, O_RDWR | O_CREAT | O_TRUNC, 0666);
 309   if (q->fd < 0)
 310     die("Cache %s: unable to create (%m)", q->file_name);
 311   struct fastbuf *fb = bfdopen_shared(q->fd, 16384);
 312
 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);
 323   h.hash_size = 1;
 324   while (h.hash_size < h.max_entries)
 325     h.hash_size *= 2;
 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));
 331
 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;
 338   ent.hash_next = 1;
 339   bwrite(fb, &ent, sizeof(ent));
 340
 341   /* Other entries */
 342   bzero(&ent, sizeof(ent));
 343   ent.data_len = ~0U;
 344   for (uns i=1; i<h.max_entries; i++)
 345     {
 346       ent.hash_next = (i == h.max_entries-1 ? 0 : i+1);
 347       bwrite(fb, &ent, sizeof(ent));
 348     }
 349
 350   /* The hash table */
 351   ASSERT(btell(fb) == h.hash_table_start);
 352   for (uns i=0; i<h.hash_size; i++)
 353     bputl(fb, 0);
 354
 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);
 359
 360   /* Padding */
 361   ASSERT(btell(fb) <= h.first_data_block << h.block_shift);
 362   while (btell(fb) < h.first_data_block << h.block_shift)
 363     bputc(fb, 0);
 364
 365   /* Data blocks */
 366   for (uns i=h.first_data_block; i<h.num_blocks; i++)
 367     for (uns j=0; j<h.block_size; j+=4)
 368       bputl(fb, 0);
 369
 370   ASSERT(btell(fb) == par->cache_size);
 371   bclose(fb);
 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);
 373
 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);
 378 }
 379
 380 struct qache *
 381 qache_open(struct qache_params *par)
 382 {
 383   struct qache *q = xmalloc_zero(sizeof(*q));
 384   q->file_name = xstrdup(par->file_name);
 385
 386   ASSERT(par->block_size >= 8 && !(par->block_size & (par->block_size-1)));
 387   par->cache_size = ALIGN_TO(par->cache_size, par->block_size);
 388
 389   if (par->force_reset <= 0 && qache_open_existing(q, par))
 390     ;
 391   else if (par->force_reset < 0)
 392     die("Cache %s: read-only access requested, but no data available", q->file_name);
 393   else
 394     qache_create(q, par);
 395   return q;
 396 }
 397
 398 void
 399 qache_close(struct qache *q, uns retain_data)
 400 {
 401   munmap(q->mmap_data, q->file_size);
 402   close(q->fd);
 403   if (!retain_data && unlink(q->file_name) < 0)
 404     log(L_ERROR, "Cache %s: unlink failed (%m)", q->file_name);
 405   xfree(q->file_name);
 406   xfree(q);
 407 }
 408
 409 static uns
 410 qache_hash(struct qache *q, qache_key_t *key)
 411 {
 412   uns h = ((*key)[0] << 24) | ((*key)[1] << 16) | ((*key)[2] << 8) | (*key)[3];
 413   return h % q->hdr->hash_size;
 414 }
 415
 416 static uns
 417 qache_hash_find(struct qache *q, qache_key_t *key, uns pos_hint)
 418 {
 419   ASSERT(q->locked);
 420
 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)))
 422     return pos_hint;
 423
 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)))
 427       return e;
 428   return 0;
 429 }
 430
 431 static void
 432 qache_hash_insert(struct qache *q, uns e)
 433 {
 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;
 437 }
 438
 439 static void
 440 qache_hash_remove(struct qache *q, uns e)
 441 {
 442   struct qache_entry *entry = &q->entry_table[e];
 443   uns f, *hh;
 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)))
 446       {
 447         *hh = entry->hash_next;
 448         return;
 449       }
 450   ASSERT(0);
 451 }
 452
 453 static uns
 454 qache_alloc_entry(struct qache *q)
 455 {
 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;
 461   entry->data_len = 0;
 462   return e;
 463 }
 464
 465 static void
 466 qache_free_entry(struct qache *q, uns e)
 467 {
 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;
 473 }
 474
 475 static inline void *
 476 get_block_start(struct qache *q, uns block)
 477 {
 478   ASSERT(block && block < q->hdr->num_blocks);
 479   return q->mmap_data + (block << q->hdr->block_shift);
 480 }
 481
 482 static uns
 483 qache_alloc_block(struct qache *q)
 484 {
 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);
 490   return blk;
 491 }
 492
 493 static void
 494 qache_free_block(struct qache *q, uns blk)
 495 {
 496   ASSERT(q->locked);
 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);
 501 }
 502
 503 static void
 504 qache_lru_insert(struct qache *q, uns e)
 505 {
 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];
 511   head->lru_next = e;
 512   entry->lru_prev = 0;
 513   entry->lru_next = succe;
 514   succ->lru_prev = e;
 515 }
 516
 517 static void
 518 qache_lru_remove(struct qache *q, uns e)
 519 {
 520   ASSERT(q->locked);
 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;
 525 }
 526
 527 static uns
 528 qache_lru_get(struct qache *q)
 529 {
 530   return q->entry_table[0].lru_prev;
 531 }
 532
 533 static void
 534 qache_ll_delete(struct qache *q, uns e)
 535 {
 536   struct qache_entry *entry = &q->entry_table[e];
 537   uns blk = entry->first_data_block;
 538   while (entry->data_len)
 539     {
 540       uns next = q->next_table[blk];
 541       qache_free_block(q, blk);
 542       blk = next;
 543       if (entry->data_len >= q->hdr->block_size)
 544         entry->data_len -= q->hdr->block_size;
 545       else
 546         entry->data_len = 0;
 547     }
 548   qache_lru_remove(q, e);
 549   qache_hash_remove(q, e);
 550   qache_free_entry(q, e);
 551 }
 552
 553 uns
 554 qache_insert(struct qache *q, qache_key_t *key, uns pos_hint, void *data, uns size)
 555 {
 556   qache_lock(q);
 557
 558   uns e = qache_hash_find(q, key, pos_hint);
 559   if (e)
 560     {
 561       qache_ll_delete(q ,e);
 562       DBG("Insert <%s>: deleting old entry %d", format_key(key), e);
 563     }
 564
 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)
 567     {
 568       qache_unlock(q, 0);
 569       return 0;
 570     }
 571   while (q->num_free_blocks < blocks || !q->first_free_entry)
 572     {
 573       e = qache_lru_get(q);
 574       DBG("Insert <%s>: evicting entry %d to make room for %d blocks", format_key(key), e, blocks);
 575       ASSERT(e);
 576       qache_ll_delete(q, e);
 577     }
 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);
 583
 584   entry->first_data_block = 0;
 585   while (size)
 586     {
 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;
 593       size -= chunk;
 594     }
 595
 596   qache_lru_insert(q, e);
 597   qache_hash_insert(q, e);
 598   qache_unlock(q, 1);
 599   return e;
 600 }
 601
 602 static void
 603 copy_out(struct qache *q, struct qache_entry *entry, byte **datap, uns *sizep, uns start)
 604 {
 605   if (sizep)
 606     {
 607       uns size = *sizep;
 608       uns avail = (start > entry->data_len) ? 0 : entry->data_len - start;
 609       uns xfer = MIN(size, avail);
 610       *sizep = avail;
 611       if (datap)
 612         {
 613           if (!*datap)
 614             *datap = xmalloc(xfer);
 615           uns blk = entry->first_data_block;
 616           while (start >= q->hdr->block_size)
 617             {
 618               blk = q->next_table[blk];
 619               start -= q->hdr->block_size;
 620             }
 621           byte *data = *datap;
 622           while (xfer)
 623             {
 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];
 627               data += len;
 628               xfer -= len;
 629               start = 0;
 630             }
 631         }
 632     }
 633   else
 634     ASSERT(!datap);
 635 }
 636
 637 uns
 638 qache_lookup(struct qache *q, qache_key_t *key, uns pos_hint, byte **datap, uns *sizep, uns start)
 639 {
 640   qache_lock(q);
 641   uns e = qache_hash_find(q, key, pos_hint);
 642   if (e)
 643     {
 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 */
 650     }
 651   else
 652     {
 653       DBG("Lookup <%s>: not found", format_key(key));
 654       qache_unlock(q, 0);
 655     }
 656   return e;
 657 }
 658
 659 uns
 660 qache_probe(struct qache *q, qache_key_t *key, uns pos, byte **datap, uns *sizep, uns start)
 661 {
 662   if (!pos || pos >= q->hdr->max_entries)
 663     {
 664       DBG("Probe %d: Out of range", pos);
 665       return ~0U;
 666     }
 667
 668   qache_lock(q);
 669   uns ret = 0;
 670   struct qache_entry *entry = &q->entry_table[pos];
 671   if (entry->data_len != ~0U)
 672     {
 673       DBG("Probe %d: Found key <%s>", format_key(entry->key));
 674       if (key)
 675         memcpy(key, entry->key, sizeof(qache_key_t));
 676       copy_out(q, entry, datap, sizep, start);
 677       ret = pos;
 678     }
 679   else
 680     DBG("Probe %d: Empty", pos);
 681   qache_unlock(q, 0);
 682   return ret;
 683 }
 684
 685 uns
 686 qache_delete(struct qache *q, qache_key_t *key, uns pos_hint)
 687 {
 688   qache_lock(q);
 689   uns e = qache_hash_find(q, key, pos_hint);
 690   if (e)
 691     {
 692       DBG("Delete <%s: deleting entry %d", format_key(key), e);
 693       qache_ll_delete(q, e);
 694     }
 695   else
 696     DBG("Delete <%s>: No match", format_key(key));
 697   qache_unlock(q, 1);
 698   return e;
 699 }
 700
 701 void
 702 qache_debug(struct qache *q)
 703 {
 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);
 707
 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++)
 711     {
 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));
 715     }
 716
 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]);
 720
 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]);
 724 }
 725
 726 void
 727 qache_audit(struct qache *q)
 728 {
 729   byte *err;
 730   qache_lock(q);
 731   if (err = do_audit(q))
 732     die("Cache %s: %s", q->file_name, err);
 733   qache_unlock(q, 0);
 734 }
 735
 736 #ifdef TEST
 737
 738 int main(int argc UNUSED, char **argv UNUSED)
 739 {
 740   struct qache_params par = {
 741     .file_name = "tmp/test",
 742     .block_size = 256,
 743     .cache_size = 65536,
 744     .max_entries = 123,
 745     .force_reset = 0,
 746     .format_id = 0xfeedcafe
 747   };
 748   struct qache *q = qache_open(&par);
 749
 750   qache_key_t key = { 0x12, 0x34, 0x56, 0x78, 0x9a, 0xbc, 0xde, 0xf0, 0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef };
 751 #define N 100
 752   uns i, j;
 753   byte data[11*N];
 754   for (i=0; i<N; i++)
 755     {
 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);
 760     }
 761   qache_debug(q);
 762   qache_audit(q);
 763
 764   uns found = 0;
 765   for (i=0; i<100; i++)
 766     {
 767       key[3] = i / 16; key[15] = i % 16;
 768       byte *dptr = data;
 769       uns sz = sizeof(data);
 770       uns e = qache_lookup(q, &key, 0, &dptr, &sz, 0);
 771       if (e)
 772         {
 773           ASSERT(sz == 11*i);
 774           for (j=0; j<sz; j++)
 775             ASSERT(data[j] == (byte)(0x33 + i*j));
 776           found++;
 777         }
 778     }
 779   log(L_INFO, "Found %d of %d entries", found, N);
 780
 781   qache_close(q, 1);
 782   return 0;
 783 }
 784
 785 #endif