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  * Dircache and indexes
  41  * ====================
  42  * The maximum dircache size is:
  43  * max(DEFAULT_MAX_DIRCACHE_SIZE, min(size, MAX_POSSIBLE_DIRCACHE_SIZE)).
  44  * It is a hashtable which we use to store "struct dir"s in. If the cache get full, oldest
  45  * entries are evicted in chunks of DIRCACHE_FREE.
  46  * We have/need two indexes:
  47  * - a DID/name index on the main dircache, another hashtable
  48  * - a queue index on the dircache, for evicting the oldest entries
  49  * The cache supports locking of struct dir elements through the DIRF_CACHELOCK flag. A dir
  50  * locked this way wont ever be removed from the cache, so be careful.
  51  *
  52  * Sending SIGHUP to a afpd child causes it to dump the dircache to a file
  53  * "/tmp/dircache.PID".
  54  */
  55
  56 /********************************************************
  57  * Local funcs and variables
  58  ********************************************************/
  59
  60 /*****************************
  61  *       THE dircache        */
  62
  63 static hash_t       *dircache;        /* The actual cache */
  64 static unsigned int dircache_maxsize; /* cache maximum size */
  65
  66 /* FNV 1a */
  67 static hash_val_t hash_vid_did(const void *key)
  68 {
  69     const struct dir *k = (const struct dir *)key;
  70     hash_val_t hash = 2166136261;
  71
  72     hash ^= k->d_vid >> 8;
  73     hash *= 16777619;
  74     hash ^= k->d_vid;
  75     hash *= 16777619;
  76
  77     hash ^= k->d_did >> 24;
  78     hash *= 16777619;
  79     hash ^= (k->d_did >> 16) & 0xff;
  80     hash *= 16777619;
  81     hash ^= (k->d_did >> 8) & 0xff;
  82     hash *= 16777619;
  83     hash ^= (k->d_did >> 0) & 0xff;
  84     hash *= 16777619;
  85
  86     return hash;
  87 }
  88
  89 static int hash_comp_vid_did(const void *key1, const void *key2)
  90 {
  91     const struct dir *k1 = key1;
  92     const struct dir *k2 = key2;
  93
  94     return !(k1->d_did == k2->d_did && k1->d_vid == k2->d_vid);
  95 }
  96
  97 /**************************************************
  98  * DID/name index on dircache (another hashtable) */
  99
 100 static hash_t *index_didname;
 101
 102 #undef get16bits
 103 #if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__)    \
 104     || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__)
 105 #define get16bits(d) (*((const uint16_t *) (d)))
 106 #endif
 107
 108 #if !defined (get16bits)
 109 #define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)    \
 110                       +(uint32_t)(((const uint8_t *)(d))[0]) )
 111 #endif
 112
 113 static hash_val_t hash_didname(const void *p)
 114 {
 115     const struct dir *key = (const struct dir *)p;
 116     const unsigned char *data = key->d_u_name->data;
 117     int len = key->d_u_name->slen;
 118     hash_val_t hash = key->d_pdid + key->d_vid;
 119     hash_val_t tmp;
 120
 121     int rem = len & 3;
 122     len >>= 2;
 123
 124     /* Main loop */
 125     for (;len > 0; len--) {
 126         hash  += get16bits (data);
 127         tmp    = (get16bits (data+2) << 11) ^ hash;
 128         hash   = (hash << 16) ^ tmp;
 129         data  += 2*sizeof (uint16_t);
 130         hash  += hash >> 11;
 131     }
 132
 133     /* Handle end cases */
 134     switch (rem) {
 135     case 3: hash += get16bits (data);
 136         hash ^= hash << 16;
 137         hash ^= data[sizeof (uint16_t)] << 18;
 138         hash += hash >> 11;
 139         break;
 140     case 2: hash += get16bits (data);
 141         hash ^= hash << 11;
 142         hash += hash >> 17;
 143         break;
 144     case 1: hash += *data;
 145         hash ^= hash << 10;
 146         hash += hash >> 1;
 147     }
 148
 149     /* Force "avalanching" of final 127 bits */
 150     hash ^= hash << 3;
 151     hash += hash >> 5;
 152     hash ^= hash << 4;
 153     hash += hash >> 17;
 154     hash ^= hash << 25;
 155     hash += hash >> 6;
 156
 157     return hash;
 158 }
 159
 160 static int hash_comp_didname(const void *k1, const void *k2)
 161 {
 162     const struct dir *key1 = (const struct dir *)k1;
 163     const struct dir *key2 = (const struct dir *)k2;
 164
 165     return ! (key1->d_vid == key2->d_vid
 166               && key1->d_pdid == key2->d_pdid
 167               && (bstrcmp(key1->d_u_name, key2->d_u_name) == 0) );
 168 }
 169
 170 /***************************
 171  * queue index on dircache */
 172
 173 static q_t *index_queue;    /* the index itself */
 174 static unsigned int queue_count;
 175
 176 /*!
 177  * @brief Remove a fixed number of (oldest) entries from the cache and indexes
 178  *
 179  * The default is to remove the 256 oldest entries from the cache.
 180  * 1. Get the oldest entry
 181  * 2. If it's in use ie open forks reference it or it's curdir requeue it,
 182  *    or it's locked (from catsearch) dont remove it
 183  * 3. Remove the dir from the main cache and the didname index
 184  * 4. Free the struct dir structure and all its members
 185  */
 186 static void dircache_evict(void)
 187 {
 188     int i = DIRCACHE_FREE_QUANTUM;
 189     struct dir *dir;
 190
 191     LOG(log_debug, logtype_afpd, "dircache: {starting cache eviction}");
 192
 193     while (i--) {
 194         if ((dir = (struct dir *)dequeue(index_queue)) == NULL) { /* 1 */
 195             dircache_dump();
 196             AFP_PANIC("dircache_evict");
 197         }
 198         queue_count--;
 199
 200         if (curdir == dir
 201             || dir->d_ofork
 202             || (dir->d_flags & DIRF_CACHELOCK)) {     /* 2 */
 203             if ((dir->qidx_node = enqueue(index_queue, dir)) == NULL) {
 204                 dircache_dump();
 205                 AFP_PANIC("dircache_evict");
 206             }
 207             queue_count++;
 208             continue;
 209         }
 210
 211         dircache_remove(NULL, dir, DIRCACHE | DIDNAME_INDEX); /* 3 */
 212         dir_free(dir);                                        /* 4 */
 213     }
 214
 215    AFP_ASSERT(queue_count == dircache->hash_nodecount);
 216
 217     LOG(log_debug, logtype_afpd, "dircache: {finished cache eviction}");
 218 }
 219
 220
 221 /********************************************************
 222  * Interface
 223  ********************************************************/
 224
 225 /*!
 226  * @brief Search the dircache via a DID
 227  *
 228  * @param vol    (r) pointer to struct vol
 229  * @param did    (r) CNID of the directory
 230  *
 231  * @returns Pointer to struct dir if found, else NULL
 232  */
 233 struct dir *dircache_search_by_did(const struct vol *vol, cnid_t did)
 234 {
 235     struct dir *cdir = NULL;
 236     struct dir key;
 237     hnode_t *hn;
 238
 239    AFP_ASSERT(vol);
 240    AFP_ASSERT(ntohl(did) >= CNID_START);
 241
 242     key.d_vid = vol->v_vid;
 243     key.d_did = did;
 244     if ((hn = hash_lookup(dircache, &key)))
 245         cdir = hnode_get(hn);
 246
 247     if (cdir)
 248         LOG(log_debug, logtype_afpd, "dircache(did:%u): {cached: path:'%s'}",
 249             ntohl(did), cfrombstring(cdir->d_u_name));
 250     else
 251         LOG(log_debug, logtype_afpd, "dircache(did:%u): {not in cache}", ntohl(did));
 252
 253     return cdir;
 254 }
 255
 256 /*!
 257  * @brief Search the cache via did/name hashtable
 258  *
 259  * @param vol    (r) volume
 260  * @param dir    (r) directory
 261  * @param name   (r) name (server side encoding)
 262  * @parma len    (r) strlen of name
 263  *
 264  * @returns pointer to struct dir if found in cache, else NULL
 265  */
 266 struct dir *dircache_search_by_name(const struct vol *vol, const struct dir *dir, char *name, int len)
 267 {
 268     struct dir *cdir = NULL;
 269     struct dir key;
 270     hnode_t *hn;
 271     static_bstring uname = {-1, len, (unsigned char *)name};
 272
 273     AFP_ASSERT(vol);
 274     AFP_ASSERT(dir);
 275     AFP_ASSERT(name);
 276     AFP_ASSERT(len == strlen(name));
 277     AFP_ASSERT(len < 256);
 278
 279     LOG(log_debug, logtype_afpd, "dircache_search_by_name(did:%u, \"%s\")",
 280         ntohl(dir->d_did), name);
 281
 282     if (dir->d_did != DIRDID_ROOT_PARENT) {
 283         key.d_vid = vol->v_vid;
 284         key.d_pdid = dir->d_did;
 285         key.d_u_name = &uname;
 286
 287         if ((hn = hash_lookup(index_didname, &key)))
 288             cdir = hnode_get(hn);
 289     }
 290
 291     if (cdir)
 292         LOG(log_debug, logtype_afpd, "dircache(did:%u, '%s'): {found in cache}",
 293             ntohl(dir->d_did), name);
 294     else
 295         LOG(log_debug, logtype_afpd, "dircache(did:%u,'%s'): {not in cache}",
 296             ntohl(dir->d_did), name);
 297
 298     return cdir;
 299 }
 300
 301 /*!
 302  * @brief create struct dir from struct path
 303  *
 304  * Add a struct dir to the cache and its indexes.
 305  *
 306  * @param dir   (r) pointer to parrent directory
 307  *
 308  * @returns 0 on success, -1 on error which should result in an abort
 309  */
 310 int dircache_add(struct dir *dir)
 311 {
 312    AFP_ASSERT(dir);
 313    AFP_ASSERT(ntohl(dir->d_pdid) >= 2);
 314    AFP_ASSERT(ntohl(dir->d_did) >= CNID_START);
 315    AFP_ASSERT(dir->d_u_name);
 316    AFP_ASSERT(dir->d_vid);
 317    AFP_ASSERT(dircache->hash_nodecount <= dircache_maxsize);
 318
 319     /* Check if cache is full */
 320     if (dircache->hash_nodecount == dircache_maxsize)
 321         dircache_evict();
 322
 323     /* Add it to the main dircache */
 324     if (hash_alloc_insert(dircache, dir, dir) == 0) {
 325         dircache_dump();
 326         exit(EXITERR_SYS);
 327     }
 328
 329     /* Add it to the did/name index */
 330     if (hash_alloc_insert(index_didname, dir, dir) == 0) {
 331         dircache_dump();
 332         exit(EXITERR_SYS);
 333     }
 334
 335     /* Add it to the fifo queue index */
 336     if ((dir->qidx_node = enqueue(index_queue, dir)) == NULL) {
 337         dircache_dump();
 338         exit(EXITERR_SYS);
 339     } else {
 340         queue_count++;
 341     }
 342
 343     LOG(log_debug, logtype_afpd, "dircache(did:%u,'%s'): {added}", ntohl(dir->d_did), cfrombstring(dir->d_u_name));
 344
 345    AFP_ASSERT(queue_count == index_didname->hash_nodecount
 346            && queue_count == dircache->hash_nodecount);
 347
 348     return 0;
 349 }
 350
 351 /*!
 352   * @brief Remove an entry from the dircache
 353   *
 354   * Callers outside of dircache.c should call this with
 355   * flags = QUEUE_INDEX | DIDNAME_INDEX | DIRCACHE.
 356   */
 357 void dircache_remove(const struct vol *vol _U_, struct dir *dir, int flags)
 358 {
 359     hnode_t *hn;
 360
 361    AFP_ASSERT(dir);
 362    AFP_ASSERT((flags & ~(QUEUE_INDEX | DIDNAME_INDEX | DIRCACHE)) == 0);
 363
 364     if (dir->d_flags & DIRF_CACHELOCK)
 365         return;
 366
 367     if (flags & QUEUE_INDEX) {
 368         /* remove it from the queue index */
 369         dequeue(dir->qidx_node->prev); /* this effectively deletes the dequeued node */
 370         queue_count--;
 371     }
 372
 373     if (flags & DIDNAME_INDEX) {
 374         if ((hn = hash_lookup(index_didname, dir)) == NULL) {
 375             LOG(log_error, logtype_default, "dircache_remove(%u,%s): not in didname index",
 376                 ntohl(dir->d_did), dir->d_u_name);
 377             dircache_dump();
 378             AFP_PANIC("dircache_remove");
 379         }
 380         hash_delete_free(index_didname, hn);
 381     }
 382
 383     if (flags & DIRCACHE) {
 384         if ((hn = hash_lookup(dircache, dir)) == NULL) {
 385             LOG(log_error, logtype_default, "dircache_remove(%u,%s): not in dircache",
 386                 ntohl(dir->d_did), dir->d_u_name);
 387             dircache_dump();
 388             AFP_PANIC("dircache_remove");
 389         }
 390         hash_delete_free(dircache, hn);
 391     }
 392
 393     LOG(log_debug, logtype_afpd, "dircache(did:%u,'%s'): {removed}", ntohl(dir->d_did), dir->d_u_name);
 394
 395    AFP_ASSERT(queue_count == index_didname->hash_nodecount
 396            && queue_count == dircache->hash_nodecount);
 397 }
 398
 399 /*!
 400  * @brief Initialize the dircache and indexes
 401  *
 402  * This is called in child afpd initialisation. The maximum cache size will be
 403  * max(DEFAULT_MAX_DIRCACHE_SIZE, min(size, MAX_POSSIBLE_DIRCACHE_SIZE)).
 404  * It initializes a hashtable which we use to store a directory cache in.
 405  * It also initializes two indexes:
 406  * - a DID/name index on the main dircache
 407  * - a queue index on the dircache
 408  *
 409  * @param size   (r) requested maximum size from afpd.conf
 410  *
 411  * @return 0 on success, -1 on error
 412  */
 413 int dircache_init(int reqsize)
 414 {
 415     dircache_maxsize = DEFAULT_MAX_DIRCACHE_SIZE;
 416
 417     /* Initialize the main dircache */
 418     if (reqsize > DEFAULT_MAX_DIRCACHE_SIZE && reqsize < MAX_POSSIBLE_DIRCACHE_SIZE) {
 419         while ((dircache_maxsize < MAX_POSSIBLE_DIRCACHE_SIZE) && (dircache_maxsize < reqsize))
 420                dircache_maxsize *= 2;
 421     }
 422     if ((dircache = hash_create(dircache_maxsize, hash_comp_vid_did, hash_vid_did)) == NULL)
 423         return -1;
 424
 425     LOG(log_debug, logtype_afpd, "dircache_init: done. max dircache size: %u", dircache_maxsize);
 426
 427     /* Initialize did/name index hashtable */
 428     if ((index_didname = hash_create(dircache_maxsize, hash_comp_didname, hash_didname)) == NULL)
 429         return -1;
 430
 431     /* Initialize index queue */
 432     if ((index_queue = queue_init()) == NULL)
 433         return -1;
 434     else
 435         queue_count = 0;
 436
 437     /* As long as directory.c hasn't got its own initializer call, we do it for it */
 438     rootParent.d_did = DIRDID_ROOT_PARENT;
 439     rootParent.d_fullpath = bfromcstr("ROOT_PARENT");
 440     rootParent.d_m_name = bfromcstr("ROOT_PARENT");
 441     rootParent.d_u_name = rootParent.d_m_name;
 442
 443     return 0;
 444 }
 445
 446 /*!
 447  * @brief Dump dircache to /tmp/dircache.PID
 448  */
 449 void dircache_dump(void)
 450 {
 451     char tmpnam[64];
 452     FILE *dump;
 453     qnode_t *n = index_queue->next;
 454     const struct dir *dir;
 455
 456     LOG(log_warning, logtype_afpd, "Dumping directory cache...");
 457
 458     sprintf(tmpnam, "/tmp/dircache.%u", getpid());
 459     if ((dump = fopen(tmpnam, "w+")) == NULL) {
 460         LOG(log_error, logtype_afpd, "dircache_dump: %s", strerror(errno));
 461         return;
 462     }
 463     setbuf(dump, NULL);
 464
 465     fprintf(dump, "Number of cache entries: %u\n", queue_count);
 466     fprintf(dump, "Configured maximum cache size: %u\n", dircache_maxsize);
 467     fprintf(dump, "==================================================\n\n");
 468
 469     for (int i = 1; i <= queue_count; i++) {
 470         if (n == index_queue)
 471             break;
 472         dir = (struct dir *)n->data;
 473         fprintf(dump, "%05u: vid:%u, pdid:%6u, did:%6u, path:%s, locked:%3s, oforks:%s\n",
 474                 i, ntohs(dir->d_vid), ntohl(dir->d_pdid), ntohl(dir->d_did),
 475                 cfrombstring(dir->d_u_name),
 476                 (dir->d_flags & DIRF_CACHELOCK) ? "yes" : "no",
 477                 dir->d_ofork ? "yes" : "no");
 478         n = n->next;
 479     }
 480
 481     fprintf(dump, "\n");
 482     return;
 483 }