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 */
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>
35 #include "directory.h"
43 * Cache files and directories in a LRU cache.
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.
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.
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.
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.
73 * There is only one cache for all volumes, so of course we use the volume is in hashing calculations.
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.
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.
92 * Sending SIGHUP to a afpd child causes it to dump the dircache to a file "/tmp/dircache.PID".
95 /********************************************************
96 * Local funcs and variables
97 ********************************************************/
99 /*****************************
102 static hash_t *dircache; /* The actual cache */
103 static unsigned int dircache_maxsize; /* cache maximum size */
106 static hash_val_t hash_vid_did(const void *key)
108 const struct dir *k = (const struct dir *)key;
109 hash_val_t hash = 2166136261;
111 hash ^= k->d_vid >> 8;
116 hash ^= k->d_did >> 24;
118 hash ^= (k->d_did >> 16) & 0xff;
120 hash ^= (k->d_did >> 8) & 0xff;
122 hash ^= (k->d_did >> 0) & 0xff;
128 static int hash_comp_vid_did(const void *key1, const void *key2)
130 const struct dir *k1 = key1;
131 const struct dir *k2 = key2;
133 return !(k1->d_did == k2->d_did && k1->d_vid == k2->d_vid);
136 /**************************************************
137 * DID/name index on dircache (another hashtable) */
139 static hash_t *index_didname;
142 #if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \
143 || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__)
144 #define get16bits(d) (*((const uint16_t *) (d)))
147 #if !defined (get16bits)
148 #define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8) \
149 +(uint32_t)(((const uint8_t *)(d))[0]) )
152 static hash_val_t hash_didname(const void *p)
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;
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);
172 /* Handle end cases */
174 case 3: hash += get16bits (data);
176 hash ^= data[sizeof (uint16_t)] << 18;
179 case 2: hash += get16bits (data);
183 case 1: hash += *data;
188 /* Force "avalanching" of final 127 bits */
199 static int hash_comp_didname(const void *k1, const void *k2)
201 const struct dir *key1 = (const struct dir *)k1;
202 const struct dir *key2 = (const struct dir *)k2;
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) );
209 /***************************
210 * queue index on dircache */
212 static q_t *index_queue; /* the index itself */
213 static unsigned int queue_count;
216 * @brief Remove a fixed number of (oldest) entries from the cache and indexes
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
225 static void dircache_evict(void)
227 int i = DIRCACHE_FREE_QUANTUM;
230 LOG(log_debug, logtype_afpd, "dircache: {starting cache eviction}");
233 if ((dir = (struct dir *)dequeue(index_queue)) == NULL) { /* 1 */
235 AFP_PANIC("dircache_evict");
241 || (dir->d_flags & DIRF_CACHELOCK)) { /* 2 */
242 if ((dir->qidx_node = enqueue(index_queue, dir)) == NULL) {
244 AFP_PANIC("dircache_evict");
250 dircache_remove(NULL, dir, DIRCACHE | DIDNAME_INDEX); /* 3 */
251 dir_free(dir); /* 4 */
254 AFP_ASSERT(queue_count == dircache->hash_nodecount);
256 LOG(log_debug, logtype_afpd, "dircache: {finished cache eviction}");
260 /********************************************************
262 ********************************************************/
265 * @brief Search the dircache via a CNID
267 * @param vol (r) pointer to struct vol
268 * @param cnid (r) CNID of the file or directory
270 * @returns Pointer to struct dir if found, else NULL
272 struct dir *dircache_search_by_did(const struct vol *vol, cnid_t cnid)
274 struct dir *cdir = NULL;
279 AFP_ASSERT(ntohl(cnid) >= CNID_START);
281 key.d_vid = vol->v_vid;
283 if ((hn = hash_lookup(dircache, &key)))
284 cdir = hnode_get(hn);
287 LOG(log_debug, logtype_afpd, "dircache(cnid:%u): {cached: path:'%s'}",
288 ntohl(cnid), cfrombstr(cdir->d_u_name));
290 LOG(log_debug, logtype_afpd, "dircache(cnid:%u): {not in cache}", ntohl(cnid));
296 * @brief Search the cache via did/name hashtable
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
303 * @returns pointer to struct dir if found in cache, else NULL
305 struct dir *dircache_search_by_name(const struct vol *vol, const struct dir *dir, char *name, int len)
307 struct dir *cdir = NULL;
310 static_bstring uname = {-1, len, (unsigned char *)name};
315 AFP_ASSERT(len == strlen(name));
316 AFP_ASSERT(len < 256);
318 LOG(log_debug, logtype_afpd, "dircache_search_by_name(did:%u, \"%s\")",
319 ntohl(dir->d_did), name);
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;
326 if ((hn = hash_lookup(index_didname, &key)))
327 cdir = hnode_get(hn);
331 LOG(log_debug, logtype_afpd, "dircache(did:%u, '%s'): {found in cache}",
332 ntohl(dir->d_did), name);
334 LOG(log_debug, logtype_afpd, "dircache(did:%u,'%s'): {not in cache}",
335 ntohl(dir->d_did), name);
341 * @brief create struct dir from struct path
343 * Add a struct dir to the cache and its indexes.
345 * @param dir (r) pointer to parrent directory
347 * @returns 0 on success, -1 on error which should result in an abort
349 int dircache_add(struct dir *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);
358 /* Check if cache is full */
359 if (dircache->hash_nodecount == dircache_maxsize)
362 /* Add it to the main dircache */
363 if (hash_alloc_insert(dircache, dir, dir) == 0) {
368 /* Add it to the did/name index */
369 if (hash_alloc_insert(index_didname, dir, dir) == 0) {
374 /* Add it to the fifo queue index */
375 if ((dir->qidx_node = enqueue(index_queue, dir)) == NULL) {
382 LOG(log_debug, logtype_afpd, "dircache(did:%u,'%s'): {added}",
383 ntohl(dir->d_did), cfrombstr(dir->d_u_name));
385 AFP_ASSERT(queue_count == index_didname->hash_nodecount
386 && queue_count == dircache->hash_nodecount);
392 * @brief Remove an entry from the dircache
394 * Callers outside of dircache.c should call this with
395 * flags = QUEUE_INDEX | DIDNAME_INDEX | DIRCACHE.
397 void dircache_remove(const struct vol *vol _U_, struct dir *dir, int flags)
402 AFP_ASSERT((flags & ~(QUEUE_INDEX | DIDNAME_INDEX | DIRCACHE)) == 0);
404 if (dir->d_flags & DIRF_CACHELOCK)
407 if (flags & QUEUE_INDEX) {
408 /* remove it from the queue index */
409 dequeue(dir->qidx_node->prev); /* this effectively deletes the dequeued node */
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), cfrombstr(dir->d_u_name));
418 AFP_PANIC("dircache_remove");
420 hash_delete_free(index_didname, hn);
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), cfrombstr(dir->d_u_name));
428 AFP_PANIC("dircache_remove");
430 hash_delete_free(dircache, hn);
433 LOG(log_debug, logtype_afpd, "dircache(did:%u,\"%s\"): {removed}",
434 ntohl(dir->d_did), cfrombstr(dir->d_u_name));
436 AFP_ASSERT(queue_count == index_didname->hash_nodecount
437 && queue_count == dircache->hash_nodecount);
441 * @brief Initialize the dircache and indexes
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
450 * @param size (r) requested maximum size from afpd.conf
452 * @return 0 on success, -1 on error
454 int dircache_init(int reqsize)
456 dircache_maxsize = DEFAULT_MAX_DIRCACHE_SIZE;
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;
463 if ((dircache = hash_create(dircache_maxsize, hash_comp_vid_did, hash_vid_did)) == NULL)
466 LOG(log_debug, logtype_afpd, "dircache_init: done. max dircache size: %u", dircache_maxsize);
468 /* Initialize did/name index hashtable */
469 if ((index_didname = hash_create(dircache_maxsize, hash_comp_didname, hash_didname)) == NULL)
472 /* Initialize index queue */
473 if ((index_queue = queue_init()) == NULL)
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;
488 * @brief Dump dircache to /tmp/dircache.PID
490 void dircache_dump(void)
494 qnode_t *n = index_queue->next;
497 const struct dir *dir;
500 LOG(log_warning, logtype_afpd, "Dumping directory cache...");
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));
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);
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);
517 while ((hn = hash_scan_next(&hs))) {
519 fprintf(dump, "%05u: %3u %6u %6u %s%s%s %s\n",
524 dir->d_fullpath ? "d" : "f",
525 (dir->d_flags & DIRF_CACHELOCK) ? "l" : "-",
526 dir->d_ofork ? "o" : "-",
527 cfrombstr(dir->d_u_name));
530 fprintf(dump, "\nSecondary DID/name index:\n");
531 fprintf(dump, " VID DID CNID STAT PATH\n");
532 fprintf(dump, "====================================================================\n");
533 hash_scan_begin(&hs, index_didname);
535 while ((hn = hash_scan_next(&hs))) {
537 fprintf(dump, "%05u: %3u %6u %6u %s%s%s %s\n",
542 dir->d_fullpath ? "d" : "f",
543 (dir->d_flags & DIRF_CACHELOCK) ? "l" : "-",
544 dir->d_ofork ? "o" : "-",
545 cfrombstr(dir->d_u_name));
548 fprintf(dump, "\nLRU Queue:\n");
549 fprintf(dump, " VID DID CNID STAT PATH\n");
550 fprintf(dump, "====================================================================\n");
552 for (i = 1; i <= queue_count; i++) {
553 if (n == index_queue)
555 dir = (struct dir *)n->data;
556 fprintf(dump, "%05u: %3u %6u %6u %s%s%s %s\n",
561 dir->d_fullpath ? "d" : "f",
562 (dir->d_flags & DIRF_CACHELOCK) ? "l" : "-",
563 dir->d_ofork ? "o" : "-",
564 cfrombstr(dir->d_u_name));