2 $Id: dircache.c,v 1.1.2.3 2010-02-04 14:34:31 franklahm Exp $
3 Copyright (c) 2010 Frank Lahm <franklahm@gmail.com>
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.
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.
18 #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>
36 #include "directory.h"
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
52 /********************************************************
53 * Local funcs and variables
54 ********************************************************/
56 /*****************************
59 /* Maximum size of the dircache hashtable */
60 #define DEFAULT_MAX_DIRCACHE_SIZE 8192 /* FIXME: make it a afpd.conf option */
61 #define MAX_POSSIBLE_DIRCACHE_SIZE 131072
63 static hash_t *dircache; /* The actual cache */
64 static unsigned int dircache_maxsize; /* cache maximum size */
67 static hash_val_t hash_vid_did(const void *key)
69 const struct dir *k = (const struct dir *)key;
70 hash_val_t hash = 2166136261;
72 hash ^= k->d_vid >> 8;
77 hash ^= k->d_did >> 24;
79 hash ^= (k->d_did >> 16) & 0xff;
81 hash ^= (k->d_did >> 8) & 0xff;
83 hash ^= (k->d_did >> 0) & 0xff;
89 static int hash_comp_vid_did(const void *key1, const void *key2)
91 const struct dir *k1 = key1;
92 const struct dir *k2 = key2;
94 return !(k1->d_did == k2->d_did && k1->d_vid == k2->d_vid);
97 /**************************************************
98 * DID/name index on dircache (another hashtable) */
100 static hash_t *index_didname;
103 #if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \
104 || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__)
105 #define get16bits(d) (*((const uint16_t *) (d)))
108 #if !defined (get16bits)
109 #define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8) \
110 +(uint32_t)(((const uint8_t *)(d))[0]) )
113 static hash_val_t hash_didname(const void *p)
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;
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);
133 /* Handle end cases */
135 case 3: hash += get16bits (data);
137 hash ^= data[sizeof (uint16_t)] << 18;
140 case 2: hash += get16bits (data);
144 case 1: hash += *data;
149 /* Force "avalanching" of final 127 bits */
160 static int hash_comp_didname(const void *k1, const void *k2)
162 const struct dir *key1 = (const struct dir *)k1;
163 const struct dir *key2 = (const struct dir *)k2;
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) );
170 /***************************
171 * queue index on dircache */
173 static queue_t *index_queue; /* the index itself */
174 static unsigned int queue_count;
175 static const int dircache_free_quantum = 256; /* number of entries to free */
178 * @brief Remove a fixed number of (oldest) entries from the cache and indexes
180 * The default is to remove the 256 oldest entries from the cache.
181 * 1. Get the oldest entry
182 * 2. If it's in use ie open forks reference it or it's curdir requeue it, 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
186 static void dircache_evict(void)
188 int i = dircache_free_quantum;
191 LOG(log_debug, logtype_afpd, "dircache: {starting cache eviction}");
194 if ((dir = (struct dir *)dequeue(index_queue)) == NULL) { /* 1 */
200 if (curdir == dir || dir->d_ofork) { /* 2 */
201 if ((dir->qidx_node = enqueue(index_queue, dir)) == NULL) {
209 dircache_remove(NULL, dir, DIRCACHE | DIDNAME_INDEX); /* 3 */
210 dir_free(dir); /* 4 */
213 assert(queue_count == dircache->hash_nodecount);
214 assert(queue_count + dircache_free_quantum <= dircache_maxsize);
216 LOG(log_debug, logtype_afpd, "dircache: {finished cache eviction}");
220 /********************************************************
222 ********************************************************/
225 * @brief Search the dircache via a DID
227 * @param vol (r) pointer to struct vol
228 * @param did (r) CNID of the directory
230 * @returns Pointer to struct dir if found, else NULL
232 struct dir *dircache_search_by_did(const struct vol *vol, cnid_t did)
234 struct dir *cdir = NULL;
239 assert(ntohl(did) >= CNID_START);
241 key.d_vid = vol->v_vid;
243 if ((hn = hash_lookup(dircache, &key)))
244 cdir = hnode_get(hn);
247 LOG(log_debug, logtype_afpd, "dircache(did:%u): {cached: path:'%s'}", ntohl(did), cfrombstring(cdir->d_fullpath));
249 LOG(log_debug, logtype_afpd, "dircache(did:%u): {not in cache}", ntohl(did));
255 * @brief Search the cache via did/name hashtable
257 * @param vol (r) volume
258 * @param dir (r) directory
259 * @param name (r) name (server side encoding)
260 * @parma len (r) strlen of name
262 * @returns pointer to struct dir if found in cache, else NULL
264 struct dir *dircache_search_by_name(const struct vol *vol, const struct dir *dir, char *name, int len)
266 struct dir *cdir = NULL;
269 static_bstring uname = {-1, len, (unsigned char *)name};
274 assert(len == strlen(name));
277 if (dir->d_did != DIRDID_ROOT_PARENT) {
278 key.d_vid = vol->v_vid;
279 key.d_pdid = dir->d_did;
280 key.d_u_name = &uname;
282 if ((hn = hash_lookup(index_didname, &key)))
283 cdir = hnode_get(hn);
287 LOG(log_debug, logtype_afpd, "dircache(pdid:%u, did:%u, '%s'): {found in cache}",
288 ntohl(dir->d_did), ntohl(cdir->d_did), cfrombstring(cdir->d_fullpath));
290 LOG(log_debug, logtype_afpd, "dircache(pdid:%u,'%s/%s'): {not in cache}",
291 ntohl(dir->d_did), cfrombstring(dir->d_fullpath), name);
297 * @brief create struct dir from struct path
299 * Add a struct dir to the cache and its indexes.
301 * @param dir (r) pointer to parrent directory
303 * @returns 0 on success, -1 on error which should result in an abort
305 int dircache_add(struct dir *dir)
308 assert(ntohl(dir->d_pdid) >= 2);
309 assert(ntohl(dir->d_did) >= CNID_START);
310 assert(dir->d_fullpath);
311 assert(dir->d_u_name);
313 assert(dircache->hash_nodecount <= dircache_maxsize);
315 /* Check if cache is full */
316 if (dircache->hash_nodecount == dircache_maxsize)
319 /* Add it to the main dircache */
320 if (hash_alloc_insert(dircache, dir, dir) == 0) {
325 /* Add it to the did/name index */
326 if (hash_alloc_insert(index_didname, dir, dir) == 0) {
331 /* Add it to the fifo queue index */
332 if ((dir->qidx_node = enqueue(index_queue, dir)) == NULL) {
339 LOG(log_debug, logtype_afpd, "dircache(did:%u,'%s'): {added}", ntohl(dir->d_did), cfrombstring(dir->d_fullpath));
341 assert(queue_count == index_didname->hash_nodecount
342 && queue_count == dircache->hash_nodecount);
348 * @brief Remove an entry from the dircache
350 * FIXME what about opened forks with refs to it?
351 * it's an afp specs violation because you can't delete
352 * an opened forks. Now afpd doesn't care about forks opened by other
353 * process. It's fixable within afpd if fnctl_lock, doable with smb and
354 * next to impossible for nfs and local filesystem access.
356 void dircache_remove(const struct vol *vol _U_, struct dir *dir, int flags)
361 assert((flags & ~(QUEUE_INDEX | DIDNAME_INDEX | DIRCACHE)) == 0);
363 if (flags & QUEUE_INDEX) {
364 /* remove it from the queue index */
365 dequeue(dir->qidx_node->prev); /* this effectively deletes the dequeued node */
369 if (flags & DIDNAME_INDEX) {
370 if ((hn = hash_lookup(index_didname, dir)) == NULL) {
371 LOG(log_error, logtype_default, "dircache_remove(%u,%s): not in didname index",
372 ntohl(dir->d_did), cfrombstring(dir->d_fullpath));
376 hash_delete(index_didname, hn);
379 if (flags & DIRCACHE) {
380 if ((hn = hash_lookup(dircache, dir)) == NULL) {
381 LOG(log_error, logtype_default, "dircache_remove(%u,%s): not in dircache",
382 ntohl(dir->d_did), cfrombstring(dir->d_fullpath));
386 hash_delete(dircache, hn);
389 LOG(log_debug, logtype_afpd, "dircache(did:%u,'%s'): {removed}", ntohl(dir->d_did), cfrombstring(dir->d_fullpath));
391 assert(queue_count == index_didname->hash_nodecount
392 && queue_count == dircache->hash_nodecount);
396 * @brief Initialize the dircache and indexes
398 * This is called in child afpd initialisation. The maximum cache size will be
399 * max(DEFAULT_MAX_DIRCACHE_SIZE, min(size, MAX_POSSIBLE_DIRCACHE_SIZE)).
400 * It initializes a hashtable which we use to store a directory cache in.
401 * It also initializes two indexes:
402 * - a DID/name index on the main dircache
403 * - a queue index on the dircache
405 * @param size (r) requested maximum size from afpd.conf
407 * @return 0 on success, -1 on error
409 int dircache_init(int reqsize)
411 dircache_maxsize = DEFAULT_MAX_DIRCACHE_SIZE;
413 /* Initialize the main dircache */
414 if (reqsize > DEFAULT_MAX_DIRCACHE_SIZE && reqsize < MAX_POSSIBLE_DIRCACHE_SIZE) {
415 while ((dircache_maxsize < MAX_POSSIBLE_DIRCACHE_SIZE) && (dircache_maxsize < reqsize))
416 dircache_maxsize *= 2;
418 if ((dircache = hash_create(dircache_maxsize, hash_comp_vid_did, hash_vid_did)) == NULL)
421 LOG(log_debug, logtype_afpd, "dircache_init: done. max dircache size: %u", dircache_maxsize);
423 /* Initialize did/name index hashtable */
424 if ((index_didname = hash_create(dircache_maxsize, hash_comp_didname, hash_didname)) == NULL)
427 /* Initialize index queue */
428 if ((index_queue = queue_init()) == NULL)
433 /* As long as directory.c hasn't got its own initializer call, we do it for it */
434 rootParent.d_did = DIRDID_ROOT_PARENT;
435 rootParent.d_fullpath = bfromcstr("");
436 rootParent.d_u_name = bfromcstr("");
437 rootParent.d_m_name = bfromcstr("");
446 * @brief Dump dircache to /tmp/dircache.PID
449 void dircache_dump(void)
453 qnode_t *n = index_queue->next;
454 const struct dir *dir;
456 LOG(log_warning, logtype_afpd, "Dumping directory cache...");
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));
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");
469 for (int i = 1; i <= queue_count; i++) {
470 if (n == index_queue)
472 dir = (struct dir *)n->data;
473 fprintf(dump, "%05u: vid:%u, pdid:%u, did:%u, path:%s\n",
474 i, ntohs(dir->d_vid), ntohl(dir->d_pdid), ntohl(dir->d_did), cfrombstring(dir->d_fullpath));