etc/afpd/dircache.c

   1 /*
   2   Copyright (c) 2010 Frank Lahm <franklahm@gmail.com>
   3
   4   This program is free software; you can redistribute it and/or modify
   5   it under the terms of the GNU General Public License as published by
   6   the Free Software Foundation; either version 2 of the License, or
   7   (at your option) any later version.
   8
   9   This program is distributed in the hope that it will be useful,
  10   but WITHOUT ANY WARRANTY; without even the implied warranty of
  11   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12   GNU General Public License for more details.
  13 */
  14
  15 #ifdef HAVE_CONFIG_H
  16 #include "config.h"
  17 #endif /* HAVE_CONFIG_H */
  18
  19 #include <string.h>
  20 #include <stdio.h>
  21 #include <stdlib.h>
  22 #include <errno.h>
  23 #include <assert.h>
  24 #include <time.h>
  25
  26 #include <atalk/util.h>
  27 #include <atalk/cnid.h>
  28 #include <atalk/logger.h>
  29 #include <atalk/volume.h>
  30 #include <atalk/directory.h>
  31 #include <atalk/queue.h>
  32 #include <atalk/bstrlib.h>
  33 #include <atalk/bstradd.h>
  34
  35 #include "dircache.h"
  36 #include "directory.h"
  37 #include "hash.h"
  38 #include "globals.h"
  39
  40 /*
  41  * Directory Cache
  42  * ===============
  43  *
  44  * Cache files and directories in a LRU cache.
  45  *
  46  * The directory cache caches directories and files(!). The main reason for having the cache
  47  * is avoiding recursive walks up the path, querying the CNID database each time, when
  48  * we have to calculate the location of eg directory with CNID 30, which is located in a dir with
  49  * CNID 25, next CNID 20 and then CNID 2 (the volume root as per AFP spec).
  50  * If all these dirs where in the cache, each database look up can be avoided. Additionally there's
  51  * the element "fullpath" in struct dir, which is used to avoid the recursion in any case. Wheneveer
  52  * a struct dir is initialized, the fullpath to the directory is stored there.
  53  *
  54  * In order to speed up the CNID query for files too, which eg happens when a directory is enumerated,
  55  * files are stored too in the dircache. In order to differentiate between files and dirs, we re-use
  56  * the element fullpath, which for files is always NULL.
  57  *
  58  * The most frequent codepatch that leads to caching is directory enumeration (cf enumerate.c):
  59  * - if a element is a directory:
  60  *   (1) the cache is searched by dircache_search_by_name()
  61  *   (2) if it wasn't found a new struct dir is created and cached both from within dir_add()
  62  * - for files the caching happens a little bit down the call chain:
  63  *   (3) first getfilparams() is called, which calls
  64  *   (4) getmetadata() where the cache is searched with dircache_search_by_name()
  65  *   (5) if the element is not found
  66  *   (6) get_id() queries the CNID from the database
  67  *   (7) then a struct dir is initialized via dir_new() (note the fullpath arg is NULL)
  68  *   (8) finally added to the cache with dircache_add()
  69  * (2) of course does contain the steps 6,7 and 8.
  70  *
  71  * The dircache is a LRU cache, whenever it fills up we call dircache_evict internally which removes
  72  * DIRCACHE_FREE_QUANTUM elements from the cache.
  73  *
  74  * There is only one cache for all volumes, so of course we use the volume id in hashing calculations.
  75  *
  76  * In order to avoid cache poisoning, we store the cached entries st_ctime from stat in
  77  * struct dir.ctime_dircache. Later when we search the cache we compare the stored
  78  * value with the result of a fresh stat. If the times differ, we remove the cached
  79  * entry and return "no entry found in cache".
  80  * A elements ctime changes when
  81  *   1) the element is renamed
  82  *      (we loose the cached entry here, but it will expire when the cache fills)
  83  *   2) its a directory and an object has been created therein
  84  *   3) the element is deleted and recreated under the same name
  85  * Using ctime leads to cache eviction in case 2) where it wouldn't be necessary, because
  86  * the dir itself (name, CNID, ...) hasn't changed, but there's no other way.
  87  *
  88  * Indexes
  89  * =======
  90  *
  91  * The maximum dircache size is:
  92  * max(DEFAULT_MAX_DIRCACHE_SIZE, min(size, MAX_POSSIBLE_DIRCACHE_SIZE)).
  93  * It is a hashtable which we use to store "struct dir"s in. If the cache get full, oldest
  94  * entries are evicted in chunks of DIRCACHE_FREE.
  95  *
  96  * We have/need two indexes:
  97  * - a DID/name index on the main dircache, another hashtable
  98  * - a queue index on the dircache, for evicting the oldest entries
  99  * The cache supports locking of struct dir elements through the DIRF_CACHELOCK flag. A dir
 100  * locked this way wont ever be removed from the cache, so be careful.
 101  *
 102  * Debugging
 103  * =========
 104  *
 105  * Sending SIGHUP to a afpd child causes it to dump the dircache to a file "/tmp/dircache.PID".
 106  */
 107
 108 /********************************************************
 109  * Local funcs and variables
 110  ********************************************************/
 111
 112 /*****************************
 113  *       the dircache        */
 114
 115 static hash_t       *dircache;        /* The actual cache */
 116 static unsigned int dircache_maxsize; /* cache maximum size */
 117
 118 static struct dircache_stat {
 119     unsigned long long lookups;
 120     unsigned long long hits;
 121     unsigned long long misses;
 122     unsigned long long added;
 123     unsigned long long removed;
 124     unsigned long long expunged;
 125     unsigned long long evicted;
 126 } dircache_stat;
 127
 128 /* FNV 1a */
 129 static hash_val_t hash_vid_did(const void *key)
 130 {
 131     const struct dir *k = (const struct dir *)key;
 132     hash_val_t hash = 2166136261;
 133
 134     hash ^= k->d_vid >> 8;
 135     hash *= 16777619;
 136     hash ^= k->d_vid;
 137     hash *= 16777619;
 138
 139     hash ^= k->d_did >> 24;
 140     hash *= 16777619;
 141     hash ^= (k->d_did >> 16) & 0xff;
 142     hash *= 16777619;
 143     hash ^= (k->d_did >> 8) & 0xff;
 144     hash *= 16777619;
 145     hash ^= (k->d_did >> 0) & 0xff;
 146     hash *= 16777619;
 147
 148     return hash;
 149 }
 150
 151 static int hash_comp_vid_did(const void *key1, const void *key2)
 152 {
 153     const struct dir *k1 = key1;
 154     const struct dir *k2 = key2;
 155
 156     return !(k1->d_did == k2->d_did && k1->d_vid == k2->d_vid);
 157 }
 158
 159 /**************************************************
 160  * DID/name index on dircache (another hashtable) */
 161
 162 static hash_t *index_didname;
 163
 164 #undef get16bits
 165 #if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__)    \
 166     || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__)
 167 #define get16bits(d) (*((const uint16_t *) (d)))
 168 #endif
 169
 170 #if !defined (get16bits)
 171 #define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)    \
 172                       +(uint32_t)(((const uint8_t *)(d))[0]) )
 173 #endif
 174
 175 static hash_val_t hash_didname(const void *p)
 176 {
 177     const struct dir *key = (const struct dir *)p;
 178     const unsigned char *data = key->d_u_name->data;
 179     int len = key->d_u_name->slen;
 180     hash_val_t hash = key->d_pdid + key->d_vid;
 181     hash_val_t tmp;
 182
 183     int rem = len & 3;
 184     len >>= 2;
 185
 186     /* Main loop */
 187     for (;len > 0; len--) {
 188         hash  += get16bits (data);
 189         tmp    = (get16bits (data+2) << 11) ^ hash;
 190         hash   = (hash << 16) ^ tmp;
 191         data  += 2*sizeof (uint16_t);
 192         hash  += hash >> 11;
 193     }
 194
 195     /* Handle end cases */
 196     switch (rem) {
 197     case 3: hash += get16bits (data);
 198         hash ^= hash << 16;
 199         hash ^= data[sizeof (uint16_t)] << 18;
 200         hash += hash >> 11;
 201         break;
 202     case 2: hash += get16bits (data);
 203         hash ^= hash << 11;
 204         hash += hash >> 17;
 205         break;
 206     case 1: hash += *data;
 207         hash ^= hash << 10;
 208         hash += hash >> 1;
 209     }
 210
 211     /* Force "avalanching" of final 127 bits */
 212     hash ^= hash << 3;
 213     hash += hash >> 5;
 214     hash ^= hash << 4;
 215     hash += hash >> 17;
 216     hash ^= hash << 25;
 217     hash += hash >> 6;
 218
 219     return hash;
 220 }
 221
 222 static int hash_comp_didname(const void *k1, const void *k2)
 223 {
 224     const struct dir *key1 = (const struct dir *)k1;
 225     const struct dir *key2 = (const struct dir *)k2;
 226
 227     return ! (key1->d_vid == key2->d_vid
 228               && key1->d_pdid == key2->d_pdid
 229               && (bstrcmp(key1->d_u_name, key2->d_u_name) == 0) );
 230 }
 231
 232 /***************************
 233  * queue index on dircache */
 234
 235 static q_t *index_queue;    /* the index itself */
 236 static unsigned long queue_count;
 237
 238 /*!
 239  * @brief Remove a fixed number of (oldest) entries from the cache and indexes
 240  *
 241  * The default is to remove the 256 oldest entries from the cache.
 242  * 1. Get the oldest entry
 243  * 2. If it's in use ie open forks reference it or it's curdir requeue it,
 244  *    or it's locked (from catsearch) dont remove it
 245  * 3. Remove the dir from the main cache and the didname index
 246  * 4. Free the struct dir structure and all its members
 247  */
 248 static void dircache_evict(void)
 249 {
 250     int i = DIRCACHE_FREE_QUANTUM;
 251     struct dir *dir;
 252
 253     LOG(log_debug, logtype_afpd, "dircache: {starting cache eviction}");
 254
 255     while (i--) {
 256         if ((dir = (struct dir *)dequeue(index_queue)) == NULL) { /* 1 */
 257             dircache_dump();
 258             AFP_PANIC("dircache_evict");
 259         }
 260         queue_count--;
 261
 262         if (curdir == dir
 263             || dir->d_ofork
 264             || (dir->d_flags & DIRF_CACHELOCK)) {     /* 2 */
 265             if ((dir->qidx_node = enqueue(index_queue, dir)) == NULL) {
 266                 dircache_dump();
 267                 AFP_PANIC("dircache_evict");
 268             }
 269             queue_count++;
 270             continue;
 271         }
 272
 273         dircache_remove(NULL, dir, DIRCACHE | DIDNAME_INDEX); /* 3 */
 274         dir_free(dir);                                        /* 4 */
 275     }
 276
 277     AFP_ASSERT(queue_count == dircache->hash_nodecount);
 278     dircache_stat.evicted += DIRCACHE_FREE_QUANTUM;
 279     LOG(log_debug, logtype_afpd, "dircache: {finished cache eviction}");
 280 }
 281
 282
 283 /********************************************************
 284  * Interface
 285  ********************************************************/
 286
 287 /*!
 288  * @brief Search the dircache via a CNID for a directory
 289  *
 290  * Found cache entries are expunged if both the parent directory st_ctime and the objects
 291  * st_ctime are modified.
 292  * This func builds on the fact, that all our code only ever needs to and does search
 293  * the dircache by CNID expecting directories to be returned, but not files.
 294  * Thus
 295  * (1) if we find a file (d_fullpath == NULL) for a given CNID we
 296  *     (1a) remove it from the cache
 297  *     (1b) return NULL indicating nothing found
 298  * (2) we can then use d_fullpath to stat the directory
 299  *
 300  * @param vol      (r) pointer to struct vol
 301  * @param cnid     (r) CNID of the directory to search
 302  *
 303  * @returns            Pointer to struct dir if found, else NULL
 304  */
 305 struct dir *dircache_search_by_did(const struct vol *vol, cnid_t cnid)
 306 {
 307     struct dir *cdir = NULL;
 308     struct dir key;
 309     struct stat st;
 310     hnode_t *hn;
 311
 312     AFP_ASSERT(vol);
 313     AFP_ASSERT(ntohl(cnid) >= CNID_START);
 314
 315     dircache_stat.lookups++;
 316     key.d_vid = vol->v_vid;
 317     key.d_did = cnid;
 318     if ((hn = hash_lookup(dircache, &key)))
 319         cdir = hnode_get(hn);
 320
 321     if (cdir) {
 322         if (cdir->d_fullpath == NULL) { /* (1) */
 323             LOG(log_debug, logtype_afpd, "dircache(cnid:%u): {not a directory:\"%s\"}",
 324                 ntohl(cnid), cfrombstr(cdir->d_u_name));
 325             (void)dir_remove(vol, cdir); /* (1a) */
 326             dircache_stat.expunged++;
 327             return NULL;        /* (1b) */
 328
 329         }
 330         if (lstat(cfrombstr(cdir->d_fullpath), &st) != 0) {
 331             LOG(log_debug, logtype_afpd, "dircache(cnid:%u): {missing:\"%s\"}",
 332                 ntohl(cnid), cfrombstr(cdir->d_fullpath));
 333             (void)dir_remove(vol, cdir);
 334             dircache_stat.expunged++;
 335             return NULL;
 336         }
 337         if (cdir->ctime_dircache != st.st_ctime) {
 338             LOG(log_debug, logtype_afpd, "dircache(cnid:%u): {modified:\"%s\"}",
 339                 ntohl(cnid), cfrombstr(cdir->d_u_name));
 340             (void)dir_remove(vol, cdir);
 341             dircache_stat.expunged++;
 342             return NULL;
 343         }
 344         LOG(log_debug, logtype_afpd, "dircache(cnid:%u): {cached: path:\"%s\"}",
 345             ntohl(cnid), cfrombstr(cdir->d_fullpath));
 346         dircache_stat.hits++;
 347     } else {
 348         LOG(log_debug, logtype_afpd, "dircache(cnid:%u): {not in cache}", ntohl(cnid));
 349         dircache_stat.hits++;
 350     }
 351
 352     return cdir;
 353 }
 354
 355 /*!
 356  * @brief Search the cache via did/name hashtable
 357  *
 358  * Found cache entries are expunged if both the parent directory st_ctime and the objects
 359  * st_ctime are modified.
 360  *
 361  * @param vol      (r) volume
 362  * @param dir      (r) directory
 363  * @param name     (r) name (server side encoding)
 364  * @parma len      (r) strlen of name
 365  * @param ctime    (r) current st_ctime from stat
 366  *
 367  * @returns pointer to struct dir if found in cache, else NULL
 368  */
 369 struct dir *dircache_search_by_name(const struct vol *vol, const struct dir *dir, char *name, int len, time_t ctime)
 370 {
 371     struct dir *cdir = NULL;
 372     struct dir key;
 373
 374     hnode_t *hn;
 375     static_bstring uname = {-1, len, (unsigned char *)name};
 376
 377     AFP_ASSERT(vol);
 378     AFP_ASSERT(dir);
 379     AFP_ASSERT(name);
 380     AFP_ASSERT(len == strlen(name));
 381     AFP_ASSERT(len < 256);
 382
 383     dircache_stat.lookups++;
 384     LOG(log_debug, logtype_afpd, "dircache_search_by_name(did:%u, \"%s\")",
 385         ntohl(dir->d_did), name);
 386
 387     if (dir->d_did != DIRDID_ROOT_PARENT) {
 388         key.d_vid = vol->v_vid;
 389         key.d_pdid = dir->d_did;
 390         key.d_u_name = &uname;
 391
 392         if ((hn = hash_lookup(index_didname, &key)))
 393             cdir = hnode_get(hn);
 394     }
 395
 396     if (cdir) {
 397         if (cdir->ctime_dircache != ctime) {
 398             LOG(log_debug, logtype_afpd, "dircache(did:%u,\"%s\"): {modified}",
 399                 ntohl(dir->d_did), name);
 400             (void)dir_remove(vol, cdir);
 401             dircache_stat.expunged++;
 402             return NULL;
 403         }
 404         LOG(log_debug, logtype_afpd, "dircache(did:%u,\"%s\"): {found in cache}",
 405             ntohl(dir->d_did), name);
 406         dircache_stat.hits++;
 407     } else {
 408         LOG(log_debug, logtype_afpd, "dircache(did:%u,\"%s\"): {not in cache}",
 409             ntohl(dir->d_did), name);
 410         dircache_stat.misses++;
 411     }
 412
 413     return cdir;
 414 }
 415
 416 /*!
 417  * @brief create struct dir from struct path
 418  *
 419  * Add a struct dir to the cache and its indexes.
 420  *
 421  * @param dir   (r) pointer to parrent directory
 422  *
 423  * @returns 0 on success, -1 on error which should result in an abort
 424  */
 425 int dircache_add(struct dir *dir)
 426 {
 427    AFP_ASSERT(dir);
 428    AFP_ASSERT(ntohl(dir->d_pdid) >= 2);
 429    AFP_ASSERT(ntohl(dir->d_did) >= CNID_START);
 430    AFP_ASSERT(dir->d_u_name);
 431    AFP_ASSERT(dir->d_vid);
 432    AFP_ASSERT(dircache->hash_nodecount <= dircache_maxsize);
 433
 434     /* Check if cache is full */
 435     if (dircache->hash_nodecount == dircache_maxsize)
 436         dircache_evict();
 437
 438     /* Add it to the main dircache */
 439     if (hash_alloc_insert(dircache, dir, dir) == 0) {
 440         dircache_dump();
 441         exit(EXITERR_SYS);
 442     }
 443
 444     /* Add it to the did/name index */
 445     if (hash_alloc_insert(index_didname, dir, dir) == 0) {
 446         dircache_dump();
 447         exit(EXITERR_SYS);
 448     }
 449
 450     /* Add it to the fifo queue index */
 451     if ((dir->qidx_node = enqueue(index_queue, dir)) == NULL) {
 452         dircache_dump();
 453         exit(EXITERR_SYS);
 454     } else {
 455         queue_count++;
 456     }
 457
 458     dircache_stat.added++;
 459     LOG(log_debug, logtype_afpd, "dircache(did:%u,'%s'): {added}",
 460         ntohl(dir->d_did), cfrombstr(dir->d_u_name));
 461
 462    AFP_ASSERT(queue_count == index_didname->hash_nodecount
 463            && queue_count == dircache->hash_nodecount);
 464
 465     return 0;
 466 }
 467
 468 /*!
 469   * @brief Remove an entry from the dircache
 470   *
 471   * Callers outside of dircache.c should call this with
 472   * flags = QUEUE_INDEX | DIDNAME_INDEX | DIRCACHE.
 473   */
 474 void dircache_remove(const struct vol *vol _U_, struct dir *dir, int flags)
 475 {
 476     hnode_t *hn;
 477
 478    AFP_ASSERT(dir);
 479    AFP_ASSERT((flags & ~(QUEUE_INDEX | DIDNAME_INDEX | DIRCACHE)) == 0);
 480
 481     if (dir->d_flags & DIRF_CACHELOCK)
 482         return;
 483
 484     if (flags & QUEUE_INDEX) {
 485         /* remove it from the queue index */
 486         dequeue(dir->qidx_node->prev); /* this effectively deletes the dequeued node */
 487         queue_count--;
 488     }
 489
 490     if (flags & DIDNAME_INDEX) {
 491         if ((hn = hash_lookup(index_didname, dir)) == NULL) {
 492             LOG(log_error, logtype_default, "dircache_remove(%u,\"%s\"): not in didname index",
 493                 ntohl(dir->d_did), cfrombstr(dir->d_u_name));
 494             dircache_dump();
 495             AFP_PANIC("dircache_remove");
 496         }
 497         hash_delete_free(index_didname, hn);
 498     }
 499
 500     if (flags & DIRCACHE) {
 501         if ((hn = hash_lookup(dircache, dir)) == NULL) {
 502             LOG(log_error, logtype_default, "dircache_remove(%u,\"%s\"): not in dircache",
 503                 ntohl(dir->d_did), cfrombstr(dir->d_u_name));
 504             dircache_dump();
 505             AFP_PANIC("dircache_remove");
 506         }
 507         hash_delete_free(dircache, hn);
 508     }
 509
 510     LOG(log_debug, logtype_afpd, "dircache(did:%u,\"%s\"): {removed}",
 511         ntohl(dir->d_did), cfrombstr(dir->d_u_name));
 512
 513     dircache_stat.removed++;
 514     AFP_ASSERT(queue_count == index_didname->hash_nodecount
 515                && queue_count == dircache->hash_nodecount);
 516 }
 517
 518 /*!
 519  * @brief Initialize the dircache and indexes
 520  *
 521  * This is called in child afpd initialisation. The maximum cache size will be
 522  * max(DEFAULT_MAX_DIRCACHE_SIZE, min(size, MAX_POSSIBLE_DIRCACHE_SIZE)).
 523  * It initializes a hashtable which we use to store a directory cache in.
 524  * It also initializes two indexes:
 525  * - a DID/name index on the main dircache
 526  * - a queue index on the dircache
 527  *
 528  * @param size   (r) requested maximum size from afpd.conf
 529  *
 530  * @return 0 on success, -1 on error
 531  */
 532 int dircache_init(int reqsize)
 533 {
 534     dircache_maxsize = DEFAULT_MAX_DIRCACHE_SIZE;
 535
 536     /* Initialize the main dircache */
 537     if (reqsize > DEFAULT_MAX_DIRCACHE_SIZE && reqsize < MAX_POSSIBLE_DIRCACHE_SIZE) {
 538         while ((dircache_maxsize < MAX_POSSIBLE_DIRCACHE_SIZE) && (dircache_maxsize < reqsize))
 539                dircache_maxsize *= 2;
 540     }
 541     if ((dircache = hash_create(dircache_maxsize, hash_comp_vid_did, hash_vid_did)) == NULL)
 542         return -1;
 543
 544     LOG(log_debug, logtype_afpd, "dircache_init: done. max dircache size: %u", dircache_maxsize);
 545
 546     /* Initialize did/name index hashtable */
 547     if ((index_didname = hash_create(dircache_maxsize, hash_comp_didname, hash_didname)) == NULL)
 548         return -1;
 549
 550     /* Initialize index queue */
 551     if ((index_queue = queue_init()) == NULL)
 552         return -1;
 553     else
 554         queue_count = 0;
 555
 556     /* As long as directory.c hasn't got its own initializer call, we do it for it */
 557     rootParent.d_did = DIRDID_ROOT_PARENT;
 558     rootParent.d_fullpath = bfromcstr("ROOT_PARENT");
 559     rootParent.d_m_name = bfromcstr("ROOT_PARENT");
 560     rootParent.d_u_name = rootParent.d_m_name;
 561
 562     return 0;
 563 }
 564
 565 /*!
 566  * Log dircache statistics
 567  */
 568 void log_dircache_stat(void)
 569 {
 570     LOG(log_debug, logtype_afpd, "dircache_stat: "
 571         "entries: %lu, lookups: %llu, hits: %llu, misses: %llu, added: %llu, removed: %llu, expunged: %llu, evicted: %llu",
 572         queue_count,
 573         dircache_stat.lookups,
 574         dircache_stat.hits,
 575         dircache_stat.misses,
 576         dircache_stat.added,
 577         dircache_stat.removed,
 578         dircache_stat.expunged,
 579         dircache_stat.evicted);
 580 }
 581
 582 /*!
 583  * @brief Dump dircache to /tmp/dircache.PID
 584  */
 585 void dircache_dump(void)
 586 {
 587     char tmpnam[64];
 588     FILE *dump;
 589     qnode_t *n = index_queue->next;
 590     hnode_t *hn;
 591     hscan_t hs;
 592     const struct dir *dir;
 593     int i;
 594
 595     LOG(log_warning, logtype_afpd, "Dumping directory cache...");
 596
 597     sprintf(tmpnam, "/tmp/dircache.%u", getpid());
 598     if ((dump = fopen(tmpnam, "w+")) == NULL) {
 599         LOG(log_error, logtype_afpd, "dircache_dump: %s", strerror(errno));
 600         return;
 601     }
 602     setbuf(dump, NULL);
 603
 604     fprintf(dump, "Number of cache entries in LRU queue: %lu\n", queue_count);
 605     fprintf(dump, "Configured maximum cache size: %u\n\n", dircache_maxsize);
 606
 607     fprintf(dump, "Primary CNID index:\n");
 608     fprintf(dump, "       VID     DID    CNID STAT  PATH\n");
 609     fprintf(dump, "====================================================================\n");
 610     hash_scan_begin(&hs, dircache);
 611     i = 1;
 612     while ((hn = hash_scan_next(&hs))) {
 613         dir = hnode_get(hn);
 614         fprintf(dump, "%05u: %3u  %6u  %6u  %s%s%s  %s\n",
 615                 i++,
 616                 ntohs(dir->d_vid),
 617                 ntohl(dir->d_pdid),
 618                 ntohl(dir->d_did),
 619                 dir->d_fullpath ? "d" : "f",
 620                 (dir->d_flags & DIRF_CACHELOCK) ? "l" : "-",
 621                 dir->d_ofork ? "o" : "-",
 622                 cfrombstr(dir->d_u_name));
 623     }
 624
 625     fprintf(dump, "\nSecondary DID/name index:\n");
 626     fprintf(dump, "       VID     DID    CNID STAT  PATH\n");
 627     fprintf(dump, "====================================================================\n");
 628     hash_scan_begin(&hs, index_didname);
 629     i = 1;
 630     while ((hn = hash_scan_next(&hs))) {
 631         dir = hnode_get(hn);
 632         fprintf(dump, "%05u: %3u  %6u  %6u  %s%s%s  %s\n",
 633                 i++,
 634                 ntohs(dir->d_vid),
 635                 ntohl(dir->d_pdid),
 636                 ntohl(dir->d_did),
 637                 dir->d_fullpath ? "d" : "f",
 638                 (dir->d_flags & DIRF_CACHELOCK) ? "l" : "-",
 639                 dir->d_ofork ? "o" : "-",
 640                 cfrombstr(dir->d_u_name));
 641     }
 642
 643     fprintf(dump, "\nLRU Queue:\n");
 644     fprintf(dump, "       VID     DID    CNID STAT  PATH\n");
 645     fprintf(dump, "====================================================================\n");
 646
 647     for (i = 1; i <= queue_count; i++) {
 648         if (n == index_queue)
 649             break;
 650         dir = (struct dir *)n->data;
 651         fprintf(dump, "%05u: %3u  %6u  %6u  %s%s%s  %s\n",
 652                 i,
 653                 ntohs(dir->d_vid),
 654                 ntohl(dir->d_pdid),
 655                 ntohl(dir->d_did),
 656                 dir->d_fullpath ? "d" : "f",
 657                 (dir->d_flags & DIRF_CACHELOCK) ? "l" : "-",
 658                 dir->d_ofork ? "o" : "-",
 659                 cfrombstr(dir->d_u_name));
 660         n = n->next;
 661     }
 662
 663     fprintf(dump, "\n");
 664     return;
 665 }