2 Copyright (c) 2010 Frank Lahm <franklahm@gmail.com>
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.
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.
17 #endif /* HAVE_CONFIG_H */
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 #include <atalk/globals.h>
37 #include "directory.h"
45 * Cache files and directories in a LRU cache.
47 * The directory cache caches directories and files(!). The main reason for having the cache
48 * is avoiding recursive walks up the path, querying the CNID database each time, when
49 * we have to calculate the location of eg directory with CNID 30, which is located in a dir with
50 * CNID 25, next CNID 20 and then CNID 2 (the volume root as per AFP spec).
51 * If all these dirs where in the cache, each database look up can be avoided. Additionally there's
52 * the element "fullpath" in struct dir, which is used to avoid the recursion in any case. Wheneveer
53 * a struct dir is initialized, the fullpath to the directory is stored there.
55 * In order to speed up the CNID query for files too, which eg happens when a directory is enumerated,
56 * files are stored too in the dircache. In order to differentiate between files and dirs, we set
57 * the flag DIRF_ISFILE in struct dir.d_flags for files.
59 * The most frequent codepatch that leads to caching is directory enumeration (cf enumerate.c):
60 * - if a element is a directory:
61 * (1) the cache is searched by dircache_search_by_name()
62 * (2) if it wasn't found a new struct dir is created and cached both from within dir_add()
63 * - for files the caching happens a little bit down the call chain:
64 * (3) first getfilparams() is called, which calls
65 * (4) getmetadata() where the cache is searched with dircache_search_by_name()
66 * (5) if the element is not found
67 * (6) get_id() queries the CNID from the database
68 * (7) then a struct dir is initialized via dir_new() (note the fullpath arg is NULL)
69 * (8) finally added to the cache with dircache_add()
70 * (2) of course does contain the steps 6,7 and 8.
72 * The dircache is a LRU cache, whenever it fills up we call dircache_evict internally which removes
73 * DIRCACHE_FREE_QUANTUM elements from the cache.
75 * There is only one cache for all volumes, so of course we use the volume id in hashing calculations.
77 * In order to avoid cache poisoning, we store the cached entries st_ctime from stat in
78 * struct dir.ctime_dircache. Later when we search the cache we compare the stored
79 * value with the result of a fresh stat. If the times differ, we remove the cached
80 * entry and return "no entry found in cache".
81 * A elements ctime changes when
82 * 1) the element is renamed
83 * (we loose the cached entry here, but it will expire when the cache fills)
84 * 2) its a directory and an object has been created therein
85 * 3) the element is deleted and recreated under the same name
86 * Using ctime leads to cache eviction in case 2) where it wouldn't be necessary, because
87 * the dir itself (name, CNID, ...) hasn't changed, but there's no other way.
92 * The maximum dircache size is:
93 * max(DEFAULT_MAX_DIRCACHE_SIZE, min(size, MAX_POSSIBLE_DIRCACHE_SIZE)).
94 * It is a hashtable which we use to store "struct dir"s in. If the cache get full, oldest
95 * entries are evicted in chunks of DIRCACHE_FREE.
97 * We have/need two indexes:
98 * - a DID/name index on the main dircache, another hashtable
99 * - a queue index on the dircache, for evicting the oldest entries
104 * Sending SIGINT to a afpd child causes it to dump the dircache to a file "/tmp/dircache.PID".
107 /********************************************************
108 * Local funcs and variables
109 ********************************************************/
111 /*****************************
114 static hash_t *dircache; /* The actual cache */
115 static unsigned int dircache_maxsize; /* cache maximum size */
117 static struct dircache_stat {
118 unsigned long long lookups;
119 unsigned long long hits;
120 unsigned long long misses;
121 unsigned long long added;
122 unsigned long long removed;
123 unsigned long long expunged;
124 unsigned long long evicted;
128 static hash_val_t hash_vid_did(const void *key)
130 const struct dir *k = (const struct dir *)key;
131 hash_val_t hash = 2166136261;
133 hash ^= k->d_vid >> 8;
138 hash ^= k->d_did >> 24;
140 hash ^= (k->d_did >> 16) & 0xff;
142 hash ^= (k->d_did >> 8) & 0xff;
144 hash ^= (k->d_did >> 0) & 0xff;
150 static int hash_comp_vid_did(const void *key1, const void *key2)
152 const struct dir *k1 = key1;
153 const struct dir *k2 = key2;
155 return !(k1->d_did == k2->d_did && k1->d_vid == k2->d_vid);
158 /**************************************************
159 * DID/name index on dircache (another hashtable) */
161 static hash_t *index_didname;
164 #if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \
165 || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__)
166 #define get16bits(d) (*((const uint16_t *) (d)))
169 #if !defined (get16bits)
170 #define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8) \
171 +(uint32_t)(((const uint8_t *)(d))[0]) )
174 static hash_val_t hash_didname(const void *p)
176 const struct dir *key = (const struct dir *)p;
177 const unsigned char *data = key->d_u_name->data;
178 int len = key->d_u_name->slen;
179 hash_val_t hash = key->d_pdid + key->d_vid;
186 for (;len > 0; len--) {
187 hash += get16bits (data);
188 tmp = (get16bits (data+2) << 11) ^ hash;
189 hash = (hash << 16) ^ tmp;
190 data += 2*sizeof (uint16_t);
194 /* Handle end cases */
196 case 3: hash += get16bits (data);
198 hash ^= data[sizeof (uint16_t)] << 18;
201 case 2: hash += get16bits (data);
205 case 1: hash += *data;
210 /* Force "avalanching" of final 127 bits */
221 static int hash_comp_didname(const void *k1, const void *k2)
223 const struct dir *key1 = (const struct dir *)k1;
224 const struct dir *key2 = (const struct dir *)k2;
226 return ! (key1->d_vid == key2->d_vid
227 && key1->d_pdid == key2->d_pdid
228 && (bstrcmp(key1->d_u_name, key2->d_u_name) == 0) );
231 /***************************
232 * queue index on dircache */
234 static q_t *index_queue; /* the index itself */
235 static unsigned long queue_count;
238 * @brief Remove a fixed number of (oldest) entries from the cache and indexes
240 * The default is to remove the 256 oldest entries from the cache.
241 * 1. Get the oldest entry
242 * 2. If it's in use ie open forks reference it or it's curdir requeue it,
244 * 3. Remove the dir from the main cache and the didname index
245 * 4. Free the struct dir structure and all its members
247 static void dircache_evict(void)
249 int i = DIRCACHE_FREE_QUANTUM;
252 LOG(log_debug, logtype_afpd, "dircache: {starting cache eviction}");
255 if ((dir = (struct dir *)dequeue(index_queue)) == NULL) { /* 1 */
257 AFP_PANIC("dircache_evict");
261 if (curdir == dir) { /* 2 */
262 if ((dir->qidx_node = enqueue(index_queue, dir)) == NULL) {
264 AFP_PANIC("dircache_evict");
270 dircache_remove(NULL, dir, DIRCACHE | DIDNAME_INDEX); /* 3 */
271 dir_free(dir); /* 4 */
274 AFP_ASSERT(queue_count == dircache->hash_nodecount);
275 dircache_stat.evicted += DIRCACHE_FREE_QUANTUM;
276 LOG(log_debug, logtype_afpd, "dircache: {finished cache eviction}");
280 /********************************************************
282 ********************************************************/
285 * @brief Search the dircache via a CNID for a directory
287 * Found cache entries are expunged if both the parent directory st_ctime and the objects
288 * st_ctime are modified.
289 * This func builds on the fact, that all our code only ever needs to and does search
290 * the dircache by CNID expecting directories to be returned, but not files.
292 * (1) if we find a file for a given CNID we
293 * (1a) remove it from the cache
294 * (1b) return NULL indicating nothing found
295 * (2) we can then use d_fullpath to stat the directory
297 * @param vol (r) pointer to struct vol
298 * @param cnid (r) CNID of the directory to search
300 * @returns Pointer to struct dir if found, else NULL
302 struct dir *dircache_search_by_did(const struct vol *vol, cnid_t cnid)
304 struct dir *cdir = NULL;
310 AFP_ASSERT(ntohl(cnid) >= CNID_START);
312 dircache_stat.lookups++;
313 key.d_vid = vol->v_vid;
315 if ((hn = hash_lookup(dircache, &key)))
316 cdir = hnode_get(hn);
319 if (cdir->d_flags & DIRF_ISFILE) { /* (1) */
320 LOG(log_debug, logtype_afpd, "dircache(cnid:%u): {not a directory:\"%s\"}",
321 ntohl(cnid), cfrombstr(cdir->d_u_name));
322 (void)dir_remove(vol, cdir); /* (1a) */
323 dircache_stat.expunged++;
324 return NULL; /* (1b) */
327 if (ostat(cfrombstr(cdir->d_fullpath), &st, vol_syml_opt(vol)) != 0) {
328 LOG(log_debug, logtype_afpd, "dircache(cnid:%u): {missing:\"%s\"}",
329 ntohl(cnid), cfrombstr(cdir->d_fullpath));
330 (void)dir_remove(vol, cdir);
331 dircache_stat.expunged++;
334 if ((cdir->dcache_ctime != st.st_ctime) || (cdir->dcache_ino != st.st_ino)) {
335 LOG(log_debug, logtype_afpd, "dircache(cnid:%u): {modified:\"%s\"}",
336 ntohl(cnid), cfrombstr(cdir->d_u_name));
337 (void)dir_remove(vol, cdir);
338 dircache_stat.expunged++;
341 LOG(log_debug, logtype_afpd, "dircache(cnid:%u): {cached: path:\"%s\"}",
342 ntohl(cnid), cfrombstr(cdir->d_fullpath));
343 dircache_stat.hits++;
345 LOG(log_debug, logtype_afpd, "dircache(cnid:%u): {not in cache}", ntohl(cnid));
346 dircache_stat.misses++;
353 * @brief Search the cache via did/name hashtable
355 * Found cache entries are expunged if both the parent directory st_ctime and the objects
356 * st_ctime are modified.
358 * @param vol (r) volume
359 * @param dir (r) directory
360 * @param name (r) name (server side encoding)
361 * @parma len (r) strlen of name
363 * @returns pointer to struct dir if found in cache, else NULL
365 struct dir *dircache_search_by_name(const struct vol *vol,
366 const struct dir *dir,
370 struct dir *cdir = NULL;
375 static_bstring uname = {-1, len, (unsigned char *)name};
380 AFP_ASSERT(len == strlen(name));
381 AFP_ASSERT(len < 256);
383 dircache_stat.lookups++;
384 LOG(log_debug, logtype_afpd, "dircache_search_by_name(did:%u, \"%s\")",
385 ntohl(dir->d_did), name);
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;
392 if ((hn = hash_lookup(index_didname, &key)))
393 cdir = hnode_get(hn);
397 if (ostat(cfrombstr(cdir->d_fullpath), &st, vol_syml_opt(vol)) != 0) {
398 LOG(log_debug, logtype_afpd, "dircache(did:%u,\"%s\"): {missing:\"%s\"}",
399 ntohl(dir->d_did), name, cfrombstr(cdir->d_fullpath));
400 (void)dir_remove(vol, cdir);
401 dircache_stat.expunged++;
405 /* Remove modified directories and files */
406 if ((cdir->dcache_ctime != st.st_ctime) || (cdir->dcache_ino != st.st_ino)) {
407 LOG(log_debug, logtype_afpd, "dircache(did:%u,\"%s\"): {modified}",
408 ntohl(dir->d_did), name);
409 (void)dir_remove(vol, cdir);
410 dircache_stat.expunged++;
413 LOG(log_debug, logtype_afpd, "dircache(did:%u,\"%s\"): {found in cache}",
414 ntohl(dir->d_did), name);
415 dircache_stat.hits++;
417 LOG(log_debug, logtype_afpd, "dircache(did:%u,\"%s\"): {not in cache}",
418 ntohl(dir->d_did), name);
419 dircache_stat.misses++;
426 * @brief create struct dir from struct path
428 * Add a struct dir to the cache and its indexes.
430 * @param dir (r) pointer to parrent directory
432 * @returns 0 on success, -1 on error which should result in an abort
434 int dircache_add(const struct vol *vol,
441 AFP_ASSERT(ntohl(dir->d_pdid) >= 2);
442 AFP_ASSERT(ntohl(dir->d_did) >= CNID_START);
443 AFP_ASSERT(dir->d_u_name);
444 AFP_ASSERT(dir->d_vid);
445 AFP_ASSERT(dircache->hash_nodecount <= dircache_maxsize);
447 /* Check if cache is full */
448 if (dircache->hash_nodecount == dircache_maxsize)
452 * Make sure we don't add duplicates
455 /* Search primary cache by CNID */
456 key.d_vid = dir->d_vid;
457 key.d_did = dir->d_did;
458 if ((hn = hash_lookup(dircache, &key))) {
459 /* Found an entry with the same CNID, delete it */
460 dir_remove(vol, hnode_get(hn));
461 dircache_stat.expunged++;
463 key.d_vid = vol->v_vid;
464 key.d_pdid = dir->d_pdid;
465 key.d_u_name = dir->d_u_name;
466 if ((hn = hash_lookup(index_didname, &key))) {
467 /* Found an entry with the same DID/name, delete it */
468 dir_remove(vol, hnode_get(hn));
469 dircache_stat.expunged++;
472 /* Add it to the main dircache */
473 if (hash_alloc_insert(dircache, dir, dir) == 0) {
478 /* Add it to the did/name index */
479 if (hash_alloc_insert(index_didname, dir, dir) == 0) {
484 /* Add it to the fifo queue index */
485 if ((dir->qidx_node = enqueue(index_queue, dir)) == NULL) {
492 dircache_stat.added++;
493 LOG(log_debug, logtype_afpd, "dircache(did:%u,'%s'): {added}",
494 ntohl(dir->d_did), cfrombstr(dir->d_u_name));
496 AFP_ASSERT(queue_count == index_didname->hash_nodecount
497 && queue_count == dircache->hash_nodecount);
503 * @brief Remove an entry from the dircache
505 * Callers outside of dircache.c should call this with
506 * flags = QUEUE_INDEX | DIDNAME_INDEX | DIRCACHE.
508 void dircache_remove(const struct vol *vol _U_, struct dir *dir, int flags)
513 AFP_ASSERT((flags & ~(QUEUE_INDEX | DIDNAME_INDEX | DIRCACHE)) == 0);
515 if (flags & QUEUE_INDEX) {
516 /* remove it from the queue index */
517 dequeue(dir->qidx_node->prev); /* this effectively deletes the dequeued node */
521 if (flags & DIDNAME_INDEX) {
522 if ((hn = hash_lookup(index_didname, dir)) == NULL) {
523 LOG(log_error, logtype_afpd, "dircache_remove(%u,\"%s\"): not in didname index",
524 ntohl(dir->d_did), cfrombstr(dir->d_u_name));
526 AFP_PANIC("dircache_remove");
528 hash_delete_free(index_didname, hn);
531 if (flags & DIRCACHE) {
532 if ((hn = hash_lookup(dircache, dir)) == NULL) {
533 LOG(log_error, logtype_afpd, "dircache_remove(%u,\"%s\"): not in dircache",
534 ntohl(dir->d_did), cfrombstr(dir->d_u_name));
536 AFP_PANIC("dircache_remove");
538 hash_delete_free(dircache, hn);
541 LOG(log_debug, logtype_afpd, "dircache(did:%u,\"%s\"): {removed}",
542 ntohl(dir->d_did), cfrombstr(dir->d_u_name));
544 dircache_stat.removed++;
545 AFP_ASSERT(queue_count == index_didname->hash_nodecount
546 && queue_count == dircache->hash_nodecount);
550 * @brief Initialize the dircache and indexes
552 * This is called in child afpd initialisation. The maximum cache size will be
553 * max(DEFAULT_MAX_DIRCACHE_SIZE, min(size, MAX_POSSIBLE_DIRCACHE_SIZE)).
554 * It initializes a hashtable which we use to store a directory cache in.
555 * It also initializes two indexes:
556 * - a DID/name index on the main dircache
557 * - a queue index on the dircache
559 * @param size (r) requested maximum size from afp.conf
561 * @return 0 on success, -1 on error
563 int dircache_init(int reqsize)
565 dircache_maxsize = DEFAULT_MAX_DIRCACHE_SIZE;
567 /* Initialize the main dircache */
568 if (reqsize > DEFAULT_MAX_DIRCACHE_SIZE && reqsize < MAX_POSSIBLE_DIRCACHE_SIZE) {
569 while ((dircache_maxsize < MAX_POSSIBLE_DIRCACHE_SIZE) && (dircache_maxsize < reqsize))
570 dircache_maxsize *= 2;
572 if ((dircache = hash_create(dircache_maxsize, hash_comp_vid_did, hash_vid_did)) == NULL)
575 LOG(log_debug, logtype_afpd, "dircache_init: done. max dircache size: %u", dircache_maxsize);
577 /* Initialize did/name index hashtable */
578 if ((index_didname = hash_create(dircache_maxsize, hash_comp_didname, hash_didname)) == NULL)
581 /* Initialize index queue */
582 if ((index_queue = queue_init()) == NULL)
587 /* Initialize index queue */
588 if ((invalid_dircache_entries = queue_init()) == NULL)
591 /* As long as directory.c hasn't got its own initializer call, we do it for it */
592 rootParent.d_did = DIRDID_ROOT_PARENT;
593 rootParent.d_fullpath = bfromcstr("ROOT_PARENT");
594 rootParent.d_m_name = bfromcstr("ROOT_PARENT");
595 rootParent.d_u_name = rootParent.d_m_name;
596 rootParent.d_rights_cache = 0xffffffff;
602 * Log dircache statistics
604 void log_dircache_stat(void)
606 LOG(log_info, logtype_afpd, "dircache statistics: "
607 "entries: %lu, lookups: %llu, hits: %llu, misses: %llu, added: %llu, removed: %llu, expunged: %llu, evicted: %llu",
609 dircache_stat.lookups,
611 dircache_stat.misses,
613 dircache_stat.removed,
614 dircache_stat.expunged,
615 dircache_stat.evicted);
619 * @brief Dump dircache to /tmp/dircache.PID
621 void dircache_dump(void)
625 qnode_t *n = index_queue->next;
628 const struct dir *dir;
631 LOG(log_warning, logtype_afpd, "Dumping directory cache...");
633 sprintf(tmpnam, "/tmp/dircache.%u", getpid());
634 if ((dump = fopen(tmpnam, "w+")) == NULL) {
635 LOG(log_error, logtype_afpd, "dircache_dump: %s", strerror(errno));
640 fprintf(dump, "Number of cache entries in LRU queue: %lu\n", queue_count);
641 fprintf(dump, "Configured maximum cache size: %u\n\n", dircache_maxsize);
643 fprintf(dump, "Primary CNID index:\n");
644 fprintf(dump, " VID DID CNID STAT PATH\n");
645 fprintf(dump, "====================================================================\n");
646 hash_scan_begin(&hs, dircache);
648 while ((hn = hash_scan_next(&hs))) {
650 fprintf(dump, "%05u: %3u %6u %6u %s %s\n",
655 dir->d_flags & DIRF_ISFILE ? "f" : "d",
656 cfrombstr(dir->d_fullpath));
659 fprintf(dump, "\nSecondary DID/name index:\n");
660 fprintf(dump, " VID DID CNID STAT PATH\n");
661 fprintf(dump, "====================================================================\n");
662 hash_scan_begin(&hs, index_didname);
664 while ((hn = hash_scan_next(&hs))) {
666 fprintf(dump, "%05u: %3u %6u %6u %s %s\n",
671 dir->d_flags & DIRF_ISFILE ? "f" : "d",
672 cfrombstr(dir->d_fullpath));
675 fprintf(dump, "\nLRU Queue:\n");
676 fprintf(dump, " VID DID CNID STAT PATH\n");
677 fprintf(dump, "====================================================================\n");
679 for (i = 1; i <= queue_count; i++) {
680 if (n == index_queue)
682 dir = (struct dir *)n->data;
683 fprintf(dump, "%05u: %3u %6u %6u %s %s\n",
688 dir->d_flags & DIRF_ISFILE ? "f" : "d",
689 cfrombstr(dir->d_fullpath));