2 $Id: dircache.c,v 1.1.2.1 2010-02-01 10:56:08 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, 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;
192 if ((dir = (struct dir *)dequeue(index_queue)) == NULL) { /* 1 */
198 if (dir->d_ofork) { /* 2 */
199 if ((dir->qidx_node = enqueue(index_queue, dir)) == NULL) {
207 dircache_remove(NULL, dir, DIRCACHE | DIDNAME_INDEX); /* 3 */
208 dir_free(dir); /* 4 */
211 assert(queue_count == dircache->hash_nodecount);
212 assert(queue_count + dircache_free_quantum <= dircache_maxsize);
216 /********************************************************
218 ********************************************************/
221 * @brief Search the dircache via a DID
223 * @param vol (r) pointer to struct vol
224 * @param did (r) CNID of the directory
226 * @returns Pointer to struct dir if found, else NULL
228 struct dir *dircache_search_by_did(const struct vol *vol, cnid_t did)
230 struct dir *cdir = NULL;
235 assert(ntohl(did) >= CNID_START);
237 key.d_vid = vol->v_vid;
239 if ((hn = hash_lookup(dircache, &key)))
240 cdir = hnode_get(hn);
243 LOG(log_debug, logtype_afpd, "dircache(did:%u): {cached: path:'%s'}", ntohl(did), cfrombstring(cdir->d_fullpath));
245 LOG(log_debug, logtype_afpd, "dircache(did:%u): {not in cache}", ntohl(did));
251 * @brief Search the cache via did/name hashtable
253 * @param vol (r) volume
254 * @param did (r) directory CNID
255 * @param name (r) name (server side encoding)
256 * @parma len (r) strlen of name
258 * @returns pointer to struct dir if found in cache, else NULL
260 struct dir *dircache_search_by_name(const struct vol *vol, cnid_t did, char *name, int len)
262 struct dir *cdir = NULL;
265 static_bstring uname = {-1, len, (unsigned char *)name};
267 assert(vol != NULL && name != NULL && len && len < 256);
269 if ((did && did != DIRDID_ROOT_PARENT)) {
270 key.d_vid = vol->v_vid;
272 key.d_u_name = &uname;
274 if ((hn = hash_lookup(index_didname, &key)))
275 cdir = hnode_get(hn);
279 LOG(log_debug, logtype_afpd, "dircache(did:%u,'%s'): {cached: path:'%s'}", ntohl(did), name, cfrombstring(cdir->d_fullpath));
281 LOG(log_debug, logtype_afpd, "dircache(did:%u,'%s'): {not in cache}", ntohl(did), name);
287 * @brief create struct dir from struct path
289 * Add a struct dir to the cache and its indexes.
291 * @param dir (r) pointer to parrent directory
293 * @returns 0 on success, -1 on error which should result in an abort
295 int dircache_add(struct dir *dir)
298 && ntohl(dir->d_pdid) >= 2
299 && ntohl(dir->d_did) >= CNID_START
300 && dir->d_fullpath != NULL
301 && dir->d_u_name != NULL
303 && dircache->hash_nodecount <= dircache_maxsize);
305 /* Check if cache is full */
306 if (dircache->hash_nodecount == dircache_maxsize)
309 /* Add it to the main dircache */
310 if (hash_alloc_insert(dircache, dir, dir) == 0) {
315 /* Add it to the did/name index */
316 if (hash_alloc_insert(index_didname, dir, dir) == 0) {
321 /* Add it to the fifo queue index */
322 if ((dir->qidx_node = enqueue(index_queue, dir)) == NULL) {
329 assert(queue_count == index_didname->hash_nodecount
330 && queue_count == dircache->hash_nodecount);
336 * @brief Remove an entry from the dircache
338 * FIXME what about opened forks with refs to it?
339 * it's an afp specs violation because you can't delete
340 * an opened forks. Now afpd doesn't care about forks opened by other
341 * process. It's fixable within afpd if fnctl_lock, doable with smb and
342 * next to impossible for nfs and local filesystem access.
344 void dircache_remove(const struct vol *vol _U_, struct dir *dir, int flags)
349 assert((flags & ~(QUEUE_INDEX | DIDNAME_INDEX | DIRCACHE)) == 0);
351 if (flags & QUEUE_INDEX) {
352 /* remove it from the queue index */
353 dequeue(dir->qidx_node->prev); /* this effectively deletes the dequeued node */
357 if (flags & DIDNAME_INDEX) {
358 if ((hn = hash_lookup(index_didname, dir)) == NULL) {
359 LOG(log_error, logtype_default, "dircache_remove(%u,%s): not in didname index",
360 ntohl(dir->d_did), cfrombstring(dir->d_fullpath));
364 hash_delete(index_didname, hn);
367 if (flags & DIRCACHE) {
368 if ((hn = hash_lookup(dircache, dir)) == NULL) {
369 LOG(log_error, logtype_default, "dircache_remove(%u,%s): not in dircache",
370 ntohl(dir->d_did), cfrombstring(dir->d_fullpath));
374 hash_delete(dircache, hn);
377 assert(queue_count == index_didname->hash_nodecount
378 && queue_count == dircache->hash_nodecount);
382 * @brief Initialize the dircache and indexes
384 * This is called in child afpd initialisation. The maximum cache size will be
385 * max(DEFAULT_MAX_DIRCACHE_SIZE, min(size, MAX_POSSIBLE_DIRCACHE_SIZE)).
386 * It initializes a hashtable which we use to store a directory cache in.
387 * It also initializes two indexes:
388 * - a DID/name index on the main dircache
389 * - a queue index on the dircache
391 * @param size (r) requested maximum size from afpd.conf
393 * @return 0 on success, -1 on error
395 int dircache_init(int reqsize)
397 dircache_maxsize = DEFAULT_MAX_DIRCACHE_SIZE;
399 /* Initialize the main dircache */
400 if (reqsize > DEFAULT_MAX_DIRCACHE_SIZE && reqsize < MAX_POSSIBLE_DIRCACHE_SIZE) {
401 while ((dircache_maxsize < MAX_POSSIBLE_DIRCACHE_SIZE) && (dircache_maxsize < reqsize))
402 dircache_maxsize *= 2;
404 if ((dircache = hash_create(dircache_maxsize, hash_comp_vid_did, hash_vid_did)) == NULL)
407 LOG(log_debug, logtype_afpd, "dircache_init: done. max dircache size: %u", dircache_maxsize);
409 /* Initialize did/name index hashtable */
410 if ((index_didname = hash_create(dircache_maxsize, hash_comp_didname, hash_didname)) == NULL)
413 /* Initialize index queue */
414 if ((index_queue = queue_init()) == NULL)
419 /* As long as directory.c hasn't got its own initializer call, we do it for it */
420 rootParent.d_did = DIRDID_ROOT_PARENT;
421 rootParent.d_fullpath = bfromcstr("");
422 rootParent.d_u_name = bfromcstr("");
423 rootParent.d_m_name = bfromcstr("");
432 * @brief Dump dircache to /tmp/dircache.PID
435 void dircache_dump(void)
437 LOG(log_error, logtype_afpd, "Fatal directory cache corruption. Dumping...\n");