etc/afpd/dircache.c

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