dircache.c File Reference

Directory Cache. More...

#include <assert.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <bstrlib.h>
#include <atalk/cnid.h>
#include <atalk/directory.h>
#include <atalk/globals.h>
#include <atalk/logger.h>
#include <atalk/queue.h>
#include <atalk/util.h>
#include <atalk/volume.h>
#include "dircache.h"
#include "directory.h"
#include "hash.h"

Data Structures
struct	dircache_stat

Macros
#define	get16bits(d)

Functions
static hash_val_t	hash_vid_did (const void *key)
static int	hash_comp_vid_did (const void *key1, const void *key2)
static hash_val_t	hash_didname (const void *p)
static int	hash_comp_didname (const void *k1, const void *k2)
static int	should_validate_cache_entry (void)
	Determine if cache entry should be validated against filesystem.
static int	cache_entry_externally_modified (struct dir *cdir, const struct stat *st)
	Smart validation for directory cache entries.
static void	dircache_evict (void)
	Remove a fixed number of (oldest) entries from the cache and indexes.
struct dir *	dircache_search_by_did (const struct vol *vol, cnid_t cnid)
	Search the dircache via a CNID for a directory.
struct dir *	dircache_search_by_name (const struct vol *vol, const struct dir *dir, char *name, int len)
	Search the cache via did/name hashtable.
int	dircache_add (const struct vol *vol, struct dir *dir)
	create struct dir from struct path
void	dircache_remove (const struct vol *vol, struct dir *dir, int flags)
	Remove an entry from the dircache.
void	dircache_remove_children (const struct vol *vol, struct dir *dir)
	Remove all child entries of a directory from the dircache.
int	dircache_init (int reqsize)
	Initialize the dircache and indexes.
void	log_dircache_stat (void)
	Log dircache statistics.
void	dircache_dump (void)
	Dump dircache to /tmp/dircache.PID.
int	dircache_set_validation_params (unsigned int freq, unsigned int meta_win, unsigned int meta_thresh)
	Set directory cache validation parameters.
void	dircache_reset_validation_counter (void)
	Reset validation counter for consistent testing.
void	dircache_report_invalid_entry (struct dir *dir)
	Report that a cache entry was invalid when actually used.

Variables
static hash_t *	dircache
static unsigned int	dircache_maxsize
static unsigned int	dircache_validation_freq = DEFAULT_DIRCACHE_VALIDATION_FREQ
static unsigned int	dircache_metadata_window = DEFAULT_DIRCACHE_METADATA_WINDOW
static unsigned int	dircache_metadata_threshold
static volatile uint64_t	validation_counter = 0
static struct dircache_stat	dircache_stat
static hash_t *	index_didname
static q_t *	index_queue
static unsigned long	queue_count

Detailed Description

Directory Cache.

Cache files and directories in a LRU cache.

The directory cache caches directories and files(!). The main reason for having the cache is avoiding recursive walks up the path, querying the CNID database each time, when we have to calculate the location of e.g. directory with CNID 30, which is located in a dir with CNID 25, next CNID 20 and then CNID 2 (the volume root as per AFP spec). If all these dirs where in the cache, each database look up can be avoided. Additionally there's the element "fullpath" in struct dir, which is used to avoid the recursion in any case. Wheneveer a struct dir is initialized, the fullpath to the directory is stored there.

In order to speed up the CNID query for files too, which e.g. happens when a directory is enumerated, files are stored too in the dircache. In order to differentiate between files and dirs, we set the flag DIRF_ISFILE in struct dir.d_flags for files.

The most frequent codepatch that leads to caching is directory enumeration (cf enumerate.c):

• if a element is a directory:
  1. the cache is searched by dircache_search_by_name()
  2. if it wasn't found a new struct dir is created and cached both from within dir_add()
• for files the caching happens a little bit down the call chain:
  1. first getfilparams() is called, which calls
  2. getmetadata() where the cache is searched with dircache_search_by_name()
  3. if the element is not found
  4. get_id() queries the CNID from the database
  5. then a struct dir is initialized via dir_new() (note the fullpath arg is NULL)
  6. finally added to the cache with dircache_add() (2) of course does contain the steps 6,7 and 8.

The dircache is a LRU cache, whenever it fills up we call dircache_evict internally which removes DIRCACHE_FREE_QUANTUM elements from the cache.

There is only one cache for all volumes, so of course we use the volume id in hashing calculations.

In order to avoid cache poisoning, we store the cached entries st_ctime from stat in struct dir.ctime_dircache. Later when we search the cache we compare the stored value with the result of a fresh stat. If the times differ, we remove the cached entry and return "no entry found in cache". A elements ctime changes when

1. the element is renamed (we lose the cached entry here, but it will expire when the cache fills)
2. its a directory and an object has been created therein
3. the element is deleted and recreated under the same name Using ctime leads to cache eviction in case 2) where it wouldn't be necessary, because the dir itself (name, CNID, ...) hasn't changed, but there's no other way.

Indexes

The maximum dircache size is: max(DEFAULT_MAX_DIRCACHE_SIZE, min(size, MAX_POSSIBLE_DIRCACHE_SIZE)). It is a hashtable which we use to store "struct dir"s in. If the cache get full, oldest entries are evicted in chunks of DIRCACHE_FREE.

We have/need two indexes:

• a DID/name index on the main dircache, another hashtable
• a queue index on the dircache, for evicting the oldest entries

Debugging

Sending SIGINT to a afpd child causes it to dump the dircache to a file "/tmp/dircache.PID".

Macro Definition Documentation

get16bits

#define get16bits

(

d

)

Value:

                      ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)    \
                      +(uint32_t)(((const uint8_t *)(d))[0]) )

Function Documentation

cache_entry_externally_modified()

int cache_entry_externally_modified ( struct dir * cdir, const struct stat * st )

static

Smart validation for directory cache entries.

Distinguishes between metadata-only changes (permissions, xattrs) and content changes (files added/removed) to avoid unnecessary cache invalidation. This is critical for AFP performance as directory ctime changes frequently for reasons that don't affect cached directory information.

Parameters

[in]	cdir	cached directory entry
[in]	st	fresh stat information from filesystem

Returns

1 if entry should be invalidated, 0 if still valid

dircache_add()

int dircache_add	(	const struct vol *	vol,
		struct dir *	dir )

create struct dir from struct path

Add a struct dir to the cache and its indexes.

Parameters

[in]	vol	pointer to volume
[in]	dir	pointer to parent directory

Returns

0 on success, -1 on error which should result in an abort

dircache_dump()

void dircache_dump

(

void

)

Dump dircache to /tmp/dircache.PID.

dircache_evict()

void dircache_evict ( void )

static

Remove a fixed number of (oldest) entries from the cache and indexes.

The default is to remove the 256 oldest entries from the cache.

1. Get the oldest entry
2. If it's in use i.e. open forks reference it or it's curdir requeue it, don't remove it
3. Remove the dir from the main cache and the didname index
4. Free the struct dir structure and all its members

dircache_init()

int dircache_init

(

int

reqsize

)

Initialize the dircache and indexes.

This is called in child afpd initialization. The maximum cache size will be max(DEFAULT_MAX_DIRCACHE_SIZE, min(size, MAX_POSSIBLE_DIRCACHE_SIZE)). It initializes a hashtable which we use to store a directory cache in. It also initializes two indexes:

• a DID/name index on the main dircache
• a queue index on the dircache

Parameters

[in]

reqsize

requested maximum size from afp.conf

Returns

0 on success, -1 on error

dircache_remove()

void dircache_remove	(	const struct vol *	vol,
		struct dir *	dir,
		int	flags )

Remove an entry from the dircache.

Callers outside of dircache.c should call this with flags = QUEUE_INDEX | DIDNAME_INDEX | DIRCACHE.

dircache_remove_children()

void dircache_remove_children	(	const struct vol *	vol,
		struct dir *	dir )

Remove all child entries of a directory from the dircache.

When a directory is renamed or moved, the full paths stored in the dircache become invalid for all child entries of the renamed dir. This function prunes orphaned child dircache entries of given dir. CNID entries use parent DIDs and name, and requre recursion to get the full path, therefore parent changes do not invalidate the CNIDs.

Parameters

[in]	vol	volume
[in]	dir	parent directory whose children should be removed

dircache_report_invalid_entry()

void dircache_report_invalid_entry

(

struct dir *

dir

)

Report that a cache entry was invalid when actually used.

This function should be called when a cached directory entry that was returned without validation (for performance) turns out to be invalid when actually accessed (e.g., file doesn't exist, has been modified, etc). This helps track the effectiveness of the validation frequency setting.

Parameters

[in]

dir

The directory entry that was found to be invalid

dircache_reset_validation_counter()

void dircache_reset_validation_counter

(

void

)

Reset validation counter for consistent testing.

Resets the global validation counter to ensure predictable validation patterns between test runs or configuration changes.

dircache_search_by_did()

struct dir * dircache_search_by_did	(	const struct vol *	vol,
		cnid_t	cnid )

Search the dircache via a CNID for a directory.

Found cache entries are expunged if both the parent directory st_ctime and the objects st_ctime are modified. This func builds on the fact, that all our code only ever needs to and does search the dircache by CNID expecting directories to be returned, but not files. Thus (1) if we find a file for a given CNID we (1a) remove it from the cache (1b) return NULL indicating nothing found (2) we can then use d_fullpath to stat the directory

Parameters

[in]	vol	pointer to struct vol
[in]	cnid	CNID of the directory to search

Returns

Pointer to struct dir if found, else NULL

dircache_search_by_name()

struct dir * dircache_search_by_name	(	const struct vol *	vol,
		const struct dir *	dir,
		char *	name,
		int	len )

Search the cache via did/name hashtable.

Found cache entries are expunged if both the parent directory st_ctime and the objects st_ctime are modified.

Parameters

[in]	vol	volume
[in]	dir	directory
[in]	name	name (server side encoding)
[in]	len	strlen of name

Returns

pointer to struct dir if found in cache, else NULL

dircache_set_validation_params()

int dircache_set_validation_params	(	unsigned int	freq,
		unsigned int	meta_win,
		unsigned int	meta_thresh )

Set directory cache validation parameters.

Allows runtime configuration of cache validation behavior for performance tuning. Lower validation frequency improves performance but may delay detection of external filesystem changes.

Parameters

[in]	freq	validation frequency (1 = validate every access, 5 = every 5th access)
[in]	meta_win	metadata change time window in seconds
[in]	meta_thresh	metadata change threshold in seconds

Returns

0 on success, -1 on invalid parameters

hash_comp_didname()

int hash_comp_didname ( const void * k1, const void * k2 )

static

hash_comp_vid_did()

int hash_comp_vid_did ( const void * key1, const void * key2 )

static

hash_didname()

hash_val_t hash_didname ( const void * p )

static

hash_vid_did()

hash_val_t hash_vid_did ( const void * key )

static

log_dircache_stat()

void log_dircache_stat

(

void

)

Log dircache statistics.

Includes hit ratio percentage for monitoring cache effectiveness, validation-specific metrics to monitor performance impact of the optimization changes, and username for tracking per-user stats. Shows both expunged (caught by validation) and invalid_on_use (missed by validation).

should_validate_cache_entry()

int should_validate_cache_entry ( void )

static

Determine if cache entry should be validated against filesystem.

Uses probabilistic validation to reduce filesystem calls while still detecting external changes. Internal netatalk operations use explicit cache invalidation via dir_remove() calls, so frequent validation is only needed to detect external filesystem changes.

Returns

1 if validation should be performed, 0 otherwise

Variable Documentation

dircache

hash_t* dircache

static

dircache_maxsize

unsigned int dircache_maxsize

static

dircache_metadata_threshold

unsigned int dircache_metadata_threshold

static

Initial value:

=
    DEFAULT_DIRCACHE_METADATA_THRESHOLD

dircache_metadata_window

unsigned int dircache_metadata_window = DEFAULT_DIRCACHE_METADATA_WINDOW

static

dircache_stat

struct dircache_stat dircache_stat

static

dircache_validation_freq

unsigned int dircache_validation_freq = DEFAULT_DIRCACHE_VALIDATION_FREQ

static

index_didname

hash_t* index_didname

static

index_queue

q_t* index_queue

static

queue_count

unsigned long queue_count

static

validation_counter

volatile uint64_t validation_counter = 0

static