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