Directory Cache. More...

#include <assert.h>
#include <errno.h>
#include <signal.h>
#include <stdint.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/netatalk_conf.h>
#include <atalk/queue.h>
#include <atalk/server_ipc.h>
#include <atalk/util.h>
#include <atalk/volume.h>
#include "ad_cache.h"
#include "dircache.h"
#include "directory.h"
#include "pfd_cache.h"
#include "hash.h"
#include "idle_worker.h"

Data Structures
struct	deferred_cleanup
struct	dircache_stat
struct	[struct].cache_hint_stat
struct	[struct].arc_cache

Macros
#define	MAX_DEFERRED_CLEANUPS 5120
#define	get16bits(d)
#define	MAX_HINTS_PER_CYCLE 32
#define	HINT_READ_BUF_SIZE

Enumerations
enum	arc_list_t { ARC_NONE = 0 , ARC_T1 , ARC_T2 , ARC_B1 , ARC_B2 }

Functions
static hnode_t *	hash_chain_head (hash_t *hash, hashcount_t chain)
static hash_val_t	hash_vid_did (const void *key)
static int	hash_comp_vid_did (const void key1, const void key2)
static int	arc_init (size_t cache_size)
	Initialize ARC cache structures.
static void	arc_destroy (void)
	Destroy ARC cache structures.
static void	arc_verify_invariants (void)
	Verify ARC invariants (debug mode).
static void	dircache_defer_free (struct dir *dir)
	Hash-removed entry: defer its free to end-of-request.
void	dircache_purge_vol (const struct vol *vol)
	Release every cache entry belonging to a closing volume.
qnode_t *	arc_ghost_trim_candidate (q_t q, const struct dir skip)
	Pick the ghost to release from a list at capacity.
static void	arc_ensure_ghost_capacity (arc_list_t target_list)
	Ensure the ghost lists have room for one more entry.
static struct dir *	arc_find_victim (q_t *queue, size_t queue_size)
	Find an evictable victim in a cache queue, skipping curdir.
static void	arc_evict_to_ghost (struct dir victim, q_t src, q_t *dst, int dst_list, bool fallback)
	Evict a victim from a cache queue to the corresponding ghost list.
static int	arc_replace (int in_b2)
	ARC REPLACE subroutine (from paper Figure 1).
static void	arc_case_i (struct dir *dir)
	ARC Case I: Cache hit in T1 or T2.
static void	arc_case_ii_adapt_and_replace (struct dir *ghost)
	ARC Case II: Ghost hit in B1.
static void	arc_case_iii_adapt_and_replace (struct dir *ghost)
	ARC Case III: Ghost hit in B2.
static void	arc_case_iv_make_room (void)
	ARC Case IV, eviction half: make room for a complete miss.
static void	arc_case_iv_insert (struct dir *dir)
	ARC Case IV, insertion half: "Put x at MRU of T1, load into cache".
static hash_val_t	hash_didname (const void *p)
static int	hash_comp_didname (const void k1, const void k2)
static unsigned int	validation_freq (void)
	Validation frequency in effect.
static int	should_validate_cache_entry (void)
	Determine if cache entry should be validated against filesystem.
static void	dircache_evict (void)
	Remove a fixed number of (oldest) entries from the cache and indexes.
static uint8_t	gone_event_for (const struct dir *dir)
static void	validation_expunge_and_hint (const struct vol vol, struct dir cdir)
	Validation discovered the entry gone: expunge + hint siblings.
static int	validation_refresh_and_hint (const struct vol vol, struct dir cdir, struct stat *st)
	Validation saw an ino/ctime change: refresh in-place + hint.
struct dir *	dircache_lookup_parent (const struct vol *vol, cnid_t did)
	Plain index probe for pfd_cache parent resolution.
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, size_t len)
	Search the cache via did/name hashtable.
static void	dircache_expunge_duplicate (const struct vol vol, struct dir dup, int *took_curdir)
	Retire a cached entry that a pending insert is about to supersede.
int	dircache_add (const struct vol vol, struct dir dir)
	create struct dir from struct path
static void	dircache_mismatch_panic (const char index_name, const struct dir dir, const void nodenode, const struct dir found)
	A stored index node does not name its entry: unrecoverable.
void	dircache_remove (const struct vol vol, struct dir dir, int flags)
	Remove an entry from the dircache.
int	dircache_remove_children (const struct vol vol, struct dir dir)
	Remove all child entries of a directory from the dircache.
int	dircache_reindex_didname (const struct vol vol, struct dir dir)
	Re-insert entry into DID/name index after key change.
void	dircache_promote (struct dir *dir)
	Promote a cache entry to signal recency.
unsigned int	dircache_resolve_size (int reqsize)
	Resolve a requested dircache size to the effective maximum.
int	dircache_init (int reqsize)
	Initialize the dircache and indexes.
void	log_dircache_stat (void)
	Log dircache statistics.
void	dircache_rfork_shutdown (void)
	Shutdown the rfork cache — free remaining RFork LRU nodes and sentinel.
void	dircache_dump (void)
	Dump dircache to /tmp/dircache.PID.
void	dircache_reset_validation_counter (void)
	Reset validation counter for consistent testing.
void	process_cache_hints (AFPObj *obj)
	Process cross-process dircache invalidation hints.
void	dircache_report_invalid_entry (struct dir *dir)
	Report that a cache entry was invalid when actually used.
void	dircache_remove_children_defer (const struct vol vol, struct dir dir)
	Enqueue a deferred dircache_remove_children operation.
static void	deferred_job_kill (int idx)
	Free a job slot without completing it (volume gone / covered).
static void	deferred_compact_head (void)
	Advance deferred_head past dead slots, keeping count consistent.
void	dircache_flush_deferred_for_vol (uint16_t vid)
	Process deferred cleanup entries for a closing volume synchronously.
int	dircache_has_deferred_work (void)
static int	path_is_strict_child (const char path, size_t len, const char parent_path, size_t parent_len)
	Test path strictly below parent: byte-prefix at a '/' boundary.
static void	deferred_cover_set (const struct deferred_cleanup *done, unsigned int scan_seq)
	Remember a completed scan as the covering memo.
static int	deferred_cover_drops (const struct deferred_cleanup *j)
	Test whether a popped job is covered by the memoized scan.
static void	deferred_compact_tail (void)
	Compact deferred_tail backwards past dead slots.
static int	deferred_batch_cmp (const void a, const void b)
	qsort comparator for batch members: vid, then path bytes.
static int	deferred_batch_match (uint16_t vid, const char *ep, size_t elen)
	Test whether an entry path is covered by a batch member.
static int	deferred_batch_start (void)
	Start a flat batch scan over every live pending job.
static void	deferred_batch_complete (void)
	Finish the flat batch scan: retire every pre-batch member.
static int	deferred_batch_chain (void)
	Scan one hash chain for the flat batch: purge every entry whose unique candidate ancestor is a batch member.
int	dircache_process_deferred_chain (void)
	Process one unit of deferred cleanup.

Variables
static hash_t *	dircache
static unsigned int	dircache_maxsize
static uint32_t	vid_entry_count [UINT16_MAX+1]
static unsigned int	deferred_seq = 0
static unsigned int	deferred_scan_started_seq = 0
static int	deferred_active = -1
static unsigned int	deferred_depth_min = 0
static unsigned int	deferred_depth_max = 0
static char *	deferred_cover_path = NULL
static size_t	deferred_cover_len = 0
static uint16_t	deferred_cover_vid = 0
static unsigned int	deferred_cover_seq = 0
static int	deferred_batch_active = 0
static unsigned int	deferred_batch_seq = 0
static unsigned int	deferred_batch_depth = 0
static hashcount_t	deferred_batch_chain_idx = 0
static int	deferred_batch_n = 0
static struct deferred_cleanup	deferred_queue [MAX_DEFERRED_CLEANUPS]
static int	deferred_batch_idx [MAX_DEFERRED_CLEANUPS]
static int	deferred_head = 0
static int	deferred_tail = 0
static int	deferred_count = 0
static unsigned long	queue_count_max = 0
static volatile uint64_t	validation_counter = 0
static struct dircache_stat	dircache_stat
unsigned long long	rfork_stat_lookups = 0
unsigned long long	rfork_stat_hits = 0
unsigned long long	rfork_stat_misses = 0
unsigned long long	rfork_stat_added = 0
unsigned long long	rfork_stat_evicted = 0
unsigned long long	rfork_stat_invalidated = 0
size_t	rfork_stat_used_max = 0
size_t	rfork_cache_used = 0
size_t	rfork_cache_budget = 0
size_t	rfork_max_entry_size = 0
unsigned int	rfork_lru_count = 0
q_t *	rfork_lru = NULL
static struct	cache_hint_stat
static struct	arc_cache
static const struct dir *	arc_promoting_ghost = NULL
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

the element is renamed (we lose the cached entry here, but it will expire when the cache fills)
its a directory and an object has been created therein
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 resolves from the requested size: unset or below MIN_DIRCACHE_SIZE uses DEFAULT_DIRCACHE_SIZE, in-range values round up to the next power of two, larger requests clamp to MAX_DIRCACHE_SIZE. It is a hashtable which we use to store "struct dir"s in. If the cache gets full, oldest entries are evicted in chunks of DIRCACHE_FREE_QUANTUM.

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]) )

◆ HINT_READ_BUF_SIZE

#define HINT_READ_BUF_SIZE

Value:

(MAX_HINTS_PER_CYCLE * \

(IPC_HEADERLEN + sizeof(struct ipc_cache_hint_payload)))

MAX_HINTS_PER_CYCLE

#define MAX_HINTS_PER_CYCLE

Definition dircache.c:2845

IPC_HEADERLEN

#define IPC_HEADERLEN

Definition server_ipc.h:12

ipc_cache_hint_payload

Definition server_ipc.h:33

◆ MAX_DEFERRED_CLEANUPS

#define MAX_DEFERRED_CLEANUPS 5120

◆ MAX_HINTS_PER_CYCLE

#define MAX_HINTS_PER_CYCLE 32

Enumeration Type Documentation

◆ arc_list_t

enum arc_list_t

ARC list location for cache entries

Enumerator
ARC_NONE	Not in any ARC list (matches calloc() zero init)
ARC_T1	Recent entries
ARC_T2	Frequent entries
ARC_B1	Ghost entries evicted from T1
ARC_B2	Ghost entries evicted from T2

Function Documentation

◆ arc_case_i()

void arc_case_i ( struct dir * dir )

static

ARC Case I: Cache hit in T1 or T2.

From paper: "Move x to MRU of T2"

Promotes entry from T1 to T2 (frequency list) on second+ access, or moves within T2 if already frequent.

Parameters

[in] dir Directory entry in T1 or T2

◆ arc_case_ii_adapt_and_replace()

void arc_case_ii_adapt_and_replace ( struct dir * ghost )

static

ARC Case II: Ghost hit in B1.

From paper: "Adapt p = min(c, p + max(|B2|/|B1|, 1)) REPLACE(p) Move x to MRU of T2, load into cache"

B1 hit indicates we evicted this entry too soon from T1. Increase p to favor recency (grow T1 target size).

Ghost entries in this implementation are full struct dir with DIRF_ARC_GHOST flag. This function adapts p, calls REPLACE, and promotes ghost from B1 to T2 inline using queue_move_to_tail_of() for zero-allocation transition.

Parameters

[in] ghost Ghost entry (struct dir with DIRF_ARC_GHOST) in B1

◆ arc_case_iii_adapt_and_replace()

void arc_case_iii_adapt_and_replace ( struct dir * ghost )

static

ARC Case III: Ghost hit in B2.

From paper: "Adapt p = max(0, p - max(|B1|/|B2|, 1)) REPLACE(p) Move x to MRU of T2, load into cache"

B2 hit indicates we evicted this entry too soon from T2. Decrease p to favor frequency (grow T2 target size).

Ghost entries in this implementation are full struct dir with DIRF_ARC_GHOST flag. This function adapts p, calls REPLACE, and promotes ghost from B2 to T2 inline using queue_move_to_tail_of() for zero-allocation transition.

Parameters

[in] ghost Ghost entry (struct dir with DIRF_ARC_GHOST) in B2

◆ arc_case_iv_insert()

void arc_case_iv_insert ( struct dir * dir )

static

ARC Case IV, insertion half: "Put x at MRU of T1, load into cache".

Parameters

[in] dir New directory entry, already in both hash indexes

◆ arc_case_iv_make_room()

void arc_case_iv_make_room ( void )

static

ARC Case IV, eviction half: make room for a complete miss.

From paper: "case (i): |L1| = c if |T1| < c then delete LRU of B1, REPLACE(p) else delete LRU of T1, remove from cache case (ii): |L1| < c and |L1| + |L2| ≥ c if |L1| + |L2| = 2c then delete LRU of B2 REPLACE(p)"

Runs before the new entry's hash inserts: whenever the dircache holds 2c entries this deletes one from the hash, so hash_insert() never sees a full table (its nodecount < maxcount assert holds).

◆ arc_destroy()

void arc_destroy ( void )

static

Destroy ARC cache structures.

◆ arc_ensure_ghost_capacity()

void arc_ensure_ghost_capacity ( arc_list_t target_list )

static

Ensure the ghost lists have room for one more entry.

Maintains the ARC invariant: B1 + B2 ≤ c

Called before operations that will add a ghost entry to B1 or B2. If the ghost lists are at or over capacity, deletes the LRU ghost from the specified target list to make room.

This handles the edge case where entries are removed from the cache via dircache_remove() (bypassing ghost lists), causing the ghost lists to stay at capacity while the cache shrinks.

A ghost mid-promotion is skipped, leaving the ghost lists one over capacity until that promotion moves it out.

Parameters

[in] target_list Which ghost list will receive new entry (ARC_B1 or ARC_B2)

◆ arc_evict_to_ghost()

void arc_evict_to_ghost	(	struct dir *	victim,
		q_t *	src,
		q_t *	dst,
		int	dst_list,
		bool	fallback )

static

Evict a victim from a cache queue to the corresponding ghost list.

Moves victim's queue node from src to dst, sets ghost flag, and updates all ARC size counters and stats.

Parameters

[in]	victim	Directory entry to evict (must have valid qidx_node)
[in]	src	Source cache queue (T1 or T2)
[in]	dst	Destination ghost queue (B1 or B2)
[in]	dst_list	ARC_B1 or ARC_B2 (determines which counters to update)
[in]	fallback	true if this is a cross-queue fallback eviction (for logging)

◆ arc_find_victim()

struct dir * arc_find_victim	(	q_t *	queue,
		size_t	queue_size )

static

Find an evictable victim in a cache queue, skipping curdir.

Only searches T1 and T2 (the real cache queues). B1/B2 are ghost lists with full data.

Tries the LRU entry first; if it's curdir, tries the second-LRU.

Parameters

[in]	queue	The ARC queue to search (T1 or T2)
[in]	queue_size	Number of entries in the queue

Returns: evictable dir entry, or NULL if queue is empty/only contains curdir

◆ arc_ghost_trim_candidate()

qnode_t * arc_ghost_trim_candidate	(	q_t *	q,
		const struct dir *	skip )

Pick the ghost to release from a list at capacity.

LRU first, skipping the excluded entry; a single-node list is both MRU and LRU, so MRU ordering alone cannot exclude it.

Parameters

[in]	q	Ghost queue (B1 or B2)
[in]	skip	Entry that must not be selected (ghost mid-promotion), or NULL

Returns: node to release, or NULL to leave the list alone

Non-static so the unit tests can drive selection directly

◆ arc_init()

int arc_init ( size_t cache_size )

static

Initialize ARC cache structures.

Parameters

[in] cache_size Total cache size (c)

Returns: 0 on success, -1 on error

◆ arc_replace()

int arc_replace ( int in_b2 )

static

ARC REPLACE subroutine (from paper Figure 1).

Evicts one entry from T1 or T2 and moves it to the corresponding ghost list (B1 or B2). Decision based on:

Current size of T1 relative to target p
Whether the incoming request is in B2

If the preferred queue only contains curdir (which must never be evicted), falls back to the other queue. Returns -1 only when both queues are exhausted, allowing the caller to proceed with a temporarily over-capacity cache that self-heals on the next eviction cycle.

From paper: "if |T1| ≥ 1 and ((x ∈ B2 and |T1| = p) or |T1| > p): Move LRU of T1 to MRU of B1, remove from cache else: Move LRU of T2 to MRU of B2, remove from cache"

Parameters

[in] in_b2 1 if incoming request is in B2, 0 otherwise

Returns: 0 on successful eviction, -1 if no entry could be evicted

◆ arc_verify_invariants()

void arc_verify_invariants ( void )

static

Verify ARC invariants (debug mode).

Checks that ARC list sizes satisfy all constraints from the paper. Called after each operation in debug builds.

◆ deferred_batch_chain()

int deferred_batch_chain ( void )

static

Scan one hash chain for the flat batch: purge every entry whose unique candidate ancestor is a batch member.

Returns: 1 if more chains remain, 0 when the batch completed

◆ deferred_batch_cmp()

int deferred_batch_cmp	(	const void *	a,
		const void *	b )

static

qsort comparator for batch members: vid, then path bytes.

◆ deferred_batch_complete()

void deferred_batch_complete ( void )

static

Finish the flat batch scan: retire every pre-batch member.

Mid-batch enqueues (seq >= batch seq) stay pending — their entries may sit in chains the batch already passed.

◆ deferred_batch_match()

int deferred_batch_match	(	uint16_t	vid,
		const char *	ep,
		size_t	elen )

static

Test whether an entry path is covered by a batch member.

The candidate ancestor is unique at uniform depth: the entry path truncated at its (batch_depth+1)-th slash. Binary search over the sorted member index; byte comparisons only.

Returns: member index-array position, or -1

◆ deferred_batch_start()

int deferred_batch_start ( void )

static

Start a flat batch scan over every live pending job.

Precondition: deferred_depth_min == deferred_depth_max and no batch is active.

Returns: 1 if the batch was armed, 0 if no live members exist

◆ deferred_compact_head()

void deferred_compact_head ( void )

static

Advance deferred_head past dead slots, keeping count consistent.

◆ deferred_compact_tail()

void deferred_compact_tail ( void )

static

Compact deferred_tail backwards past dead slots.

LIFO consumption retires slots at the tail; head compaction still handles slots killed by the volume flush.

◆ deferred_cover_drops()

int deferred_cover_drops ( const struct deferred_cleanup * j )

static

Test whether a popped job is covered by the memoized scan.

Covered iff enqueued before that scan started (serial-number compare: the unsigned seq difference exceeds half the counter space iff the job predates the scan, fully defined across wraparound), same volume, and its byte path equals or sits strictly below the memoized path at a '/' boundary.

Returns: 1 if the job's entries were already purged, else 0

◆ deferred_cover_set()

void deferred_cover_set	(	const struct deferred_cleanup *	done,
		unsigned int	scan_seq )

static

Remember a completed scan as the covering memo.

◆ deferred_job_kill()

void deferred_job_kill ( int idx )

static

Free a job slot without completing it (volume gone / covered).

◆ 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. Supports both LRU mode (legacy) and ARC mode.

Parameters

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

Returns: 0; a failed hash insert aborts the process

◆ dircache_defer_free()

void dircache_defer_free ( struct dir * dir )

static

Hash-removed entry: defer its free to end-of-request.

Caller must have removed the entry from both hash indexes and every ARC/LRU queue. Deferring keeps pointers handed out earlier in this request valid (consumers gate on d_did != CNID_INVALID) — ARC ghost eviction can reach entries that WERE returned this request, so an inline free here could dangle a held pointer. On qnode OOM (effectively unreachable: the kernel OOM killer fires first) leak the entry instead; dir_remove makes the same choice.

◆ 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.

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

◆ dircache_expunge_duplicate()

void dircache_expunge_duplicate	(	const struct vol *	vol,
		struct dir *	dup,
		int *	took_curdir )

static

Retire a cached entry that a pending insert is about to supersede.

Not dir_remove(): its curdir recovery calls dirlookup(), which re-enters dircache_add() and re-publishes the key the caller is clearing. curdir is handed back instead, for the caller to re-point once its entry is published.

Parameters

[in]	vol	Volume the entry belongs to
[in]	dup	Entry to retire
[out]	took_curdir	set if the retired entry was curdir

◆ dircache_flush_deferred_for_vol()

void dircache_flush_deferred_for_vol ( uint16_t vid )

Process deferred cleanup entries for a closing volume synchronously.

Precondition: : Worker is dormant (called during AFP command processing). Called from afp_closevol() before volume structures are freed. Drops the preselected active-job cursor if it points at this volume.

◆ dircache_has_deferred_work()

int dircache_has_deferred_work ( void )

◆ dircache_init()

int dircache_init ( int reqsize )

Initialize the dircache and indexes.

This is called in child afpd initialization. Unset or below-minimum sizes use DEFAULT_DIRCACHE_SIZE, in-range sizes round up to the next power of two, oversize requests clamp to MAX_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 (LRU mode) or four queues (ARC mode)

Parameters

[in] reqsize requested maximum size from afp.conf

Returns: 0 on success, -1 on error

◆ dircache_lookup_parent()

struct dir * dircache_lookup_parent	(	const struct vol *	vol,
		cnid_t	did )

Plain index probe for pfd_cache parent resolution.

Never validates, never mutates, never promotes. Filters ARC ghosts (their identity fields are frozen and unvalidated — treating one as a live parent would let the pfd sync-check pass against stale identity) and file entries (a parent must be a directory).

◆ dircache_mismatch_panic()

void dircache_mismatch_panic	(	const char *	index_name,
		const struct dir *	dir,
		const void *	node,
		const struct dir *	found )

static

A stored index node does not name its entry: unrecoverable.

Every node is created with its entry as data and freed only through the entry's own removal, so a mismatch means memory corruption or a foreign delete. Freeing what a table still points at cannot be survived.

◆ dircache_process_deferred_chain()

int dircache_process_deferred_chain ( void )

Process one unit of deferred cleanup.

Called by idle worker under a validated grant. Jobs are consumed LIFO: AFP deletes bottom-up, so a tree's covering root-most job arrives last and its single scan purges the whole subtree; the covering memo then drops the tree's remaining jobs in O(1) as they pop. When every pending job sits at one depth, one merged batch scan serves all of them. Every removal re-checks iw_can_work; scans resume via their chain cursors across granted cycles.

Returns: 1 if more work remains, 0 if all deferred work is complete

◆ dircache_promote()

void dircache_promote ( struct dir * dir )

Promote a cache entry to signal recency.

Dispatches based on cache mode:

ARC mode (arc_list membership): T1/T2: arc_case_i() — move to MRU of T2 B1: arc_case_ii_adapt_and_replace() — promote ghost to T2 B2: arc_case_iii_adapt_and_replace() — promote ghost to T2

LRU mode: Move entry to MRU position of the LRU queue, so recently accessed entries are evicted last. Prevents actively-used entries from being evicted.

Parameters

[in,out] dir Cache entry to promote (required)

◆ dircache_purge_vol()

void dircache_purge_vol ( const struct vol * vol )

Release every cache entry belonging to a closing volume.

Nothing else reclaims by volume, so entries left behind are found as valid when the vid is reused. DIRCACHE_NOSHRINK keeps the scan valid: each entry deletes only its own just-returned node and the table never rehashes mid-scan.

Nothing is exempt: closevol() frees v_root next, so an entry kept back would outlive its volume under a reusable vid. A curdir still inside the volume is dropped to rootParent rather than left cached.

Parameters

[in] vol Volume being closed (required)

◆ dircache_reindex_didname()

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

Re-insert entry into DID/name index after key change.

Called by dir_modify() after updating d_pdid / d_u_name. The caller MUST have already removed the entry from the DIDNAME_INDEX via dircache_remove(vol, dir, DIDNAME_INDEX) before calling this.

Parameters

[in]	vol	Volume (required)
[in]	dir	Entry with updated d_pdid / d_u_name (required)

Returns: 0 on success, -1 on hash insert failure

◆ dircache_remove()

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

Remove an entry from the dircache.

Deletes the entry's own stored nodes, so removal can never cost another entry its node. A NULL node means the entry is not in that index and it is skipped; a node naming a different entry panics before anything is mutated or followed.

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

◆ dircache_remove_children()

int 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.

Removes as it scans: DIRCACHE_NOSHRINK deletes the entry's own just-returned node without rehashing the table, and the free is deferred, so nothing the scan is walking moves. dir_remove() cannot be used here — its curdir recovery calls dirlookup(), and an insert mid-scan can grow the table. A removed curdir is re-resolved once the scan is over instead: a rename keeps the CNID, so the lookup rebuilds the entry on the new path.

Parameters

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

Returns: 0 on success, -1 if a removed curdir could not be re-resolved

◆ dircache_remove_children_defer()

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

Enqueue a deferred dircache_remove_children operation.

O(1) enqueue — the idle worker performs the actual hash scan during poll() idle periods. Falls back to synchronous removal if the worker is not active or the queue is full.

◆ 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_resolve_size()

unsigned int dircache_resolve_size ( int reqsize )

Resolve a requested dircache size to the effective maximum.

Unset or below-minimum sizes use DEFAULT_DIRCACHE_SIZE, in-range sizes round up to the next power of two, oversize requests clamp to MAX_DIRCACHE_SIZE.

Parameters

[in] reqsize requested maximum size from afp.conf

Returns: the effective maximum cache size

◆ dircache_rfork_shutdown()

void dircache_rfork_shutdown ( void )

Shutdown the rfork cache — free remaining RFork LRU nodes and sentinel.

Called from the child shutdown path after log_dircache_stat(). Frees the qnodes (rfork data buffers are reclaimed by exit()) and the LRU sentinel.

◆ 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,
		size_t	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

◆ gone_event_for()

uint8_t gone_event_for ( const struct dir * dir )

static

◆ hash_chain_head()

hnode_t * hash_chain_head	(	hash_t *	hash,
		hashcount_t	chain )

inlinestatic

◆ hash_comp_didname()

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

inlinestatic

◆ hash_comp_vid_did()

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

inlinestatic

◆ hash_didname()

hash_val_t hash_didname ( const void * p )

inlinestatic

◆ hash_vid_did()

hash_val_t hash_vid_did ( const void * key )

inlinestatic

◆ 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).

◆ path_is_strict_child()

int path_is_strict_child	(	const char *	path,
		size_t	len,
		const char *	parent_path,
		size_t	parent_len )

static

Test path strictly below parent: byte-prefix at a '/' boundary.

The boundary byte check rejects sibling prefixes ("/A/BC" under "/A/B").

Returns: 1 if path is a strict descendant of parent_path, else 0

◆ process_cache_hints()

void process_cache_hints ( AFPObj * obj )

Process cross-process dircache invalidation hints.

Called from the DSI command loop after each AFP command completes. Uses direct hash_lookup() on the CNID hash table to support BOTH files (DIRF_ISFILE) and directories — dircache_search_by_did() is unsuitable because it actively removes file entries.

Dispatches on hint type:

CACHE_HINT_REFRESH: ostat() + dir_modify() — stat refresh, AD invalidation
CACHE_HINT_DELETE: direct dir_remove() — no ostat needed
CACHE_HINT_DELETE_CHILDREN: dircache_remove_children() + parent cleanup

◆ 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

◆ validation_expunge_and_hint()

void validation_expunge_and_hint	(	const struct vol *	vol,
		struct dir *	cdir )

static

Validation discovered the entry gone: expunge + hint siblings.

One pipe message replaces each sibling re-discovering the change by its own full-path stat. The hint reports evidence (gone); a same-named recreate is harmless — hints only invalidate, receivers rebuild.

◆ validation_freq()

unsigned int validation_freq ( void )

static

Validation frequency in effect.

Read live: the coherency defaults are applied per volume, after dircache_init(). The single reader for the validation decision and the statistics, so both always report the same frequency.

Returns: configured validation frequency, never 0 (divisor)

◆ validation_refresh_and_hint()

int validation_refresh_and_hint	(	const struct vol *	vol,
		struct dir *	cdir,
		struct stat *	st )

static

Validation saw an ino/ctime change: refresh in-place + hint.

Hints: an inode change (object replaced) broadcasts REFRESH under the entry's current DID and, when dir_modify re-keyed it, under the old DID too — siblings cache the object under the old key. A ctime-only change sends nothing: fork writes advance ctime on every flush, and broadcasting those would rebuild sibling AD/rfork caches per write; pure metadata changes propagate via each sibling's own validation.

Returns: 0 if the entry survived (refreshed in-place), -1 if dir_modify evicted it (inode change + CNID miss) — hint sent either way.

Variable Documentation

◆ arc_cache

struct [struct].arc_cache arc_cache

Initial value:

= {
    .enabled = 0,  
    .t1 = NULL, .t2 = NULL, .b1 = NULL, .b2 = NULL,
    .t1_size = 0, .t2_size = 0, .b1_size = 0, .b2_size = 0,
    .p = 0, .c = 0,
    .stats = {0}
}

◆ arc_promoting_ghost

const struct dir* arc_promoting_ghost = NULL

static

◆ cache_hint_stat

struct [struct].cache_hint_stat cache_hint_stat

◆ deferred_active

int deferred_active = -1

static

◆ deferred_batch_active

int deferred_batch_active = 0

static

◆ deferred_batch_chain_idx

hashcount_t deferred_batch_chain_idx = 0

static

◆ deferred_batch_depth

unsigned int deferred_batch_depth = 0

static

◆ deferred_batch_idx

int deferred_batch_idx[MAX_DEFERRED_CLEANUPS]

static

◆ deferred_batch_n

int deferred_batch_n = 0

static

◆ deferred_batch_seq

unsigned int deferred_batch_seq = 0

static

◆ deferred_count

int deferred_count = 0

static

◆ deferred_cover_len

size_t deferred_cover_len = 0

static

◆ deferred_cover_path

char* deferred_cover_path = NULL

static

◆ deferred_cover_seq

unsigned int deferred_cover_seq = 0

static

◆ deferred_cover_vid

uint16_t deferred_cover_vid = 0

static

◆ deferred_depth_max

unsigned int deferred_depth_max = 0

static

◆ deferred_depth_min

unsigned int deferred_depth_min = 0

static

◆ deferred_head

int deferred_head = 0

static

◆ deferred_queue

struct deferred_cleanup deferred_queue[MAX_DEFERRED_CLEANUPS]

static

◆ deferred_scan_started_seq

unsigned int deferred_scan_started_seq = 0

static

◆ deferred_seq

unsigned int deferred_seq = 0

static

◆ deferred_tail

int deferred_tail = 0

static

◆ dircache

hash_t* dircache

static

◆ dircache_maxsize

unsigned int dircache_maxsize

static

◆ dircache_stat

struct dircache_stat dircache_stat

static

◆ index_didname

hash_t* index_didname

static

◆ index_queue

q_t* index_queue

static

◆ queue_count

unsigned long queue_count

static

◆ queue_count_max

unsigned long queue_count_max = 0

static

Peak cached entries reached this session (shared by LRU and ARC)

◆ rfork_cache_budget

size_t rfork_cache_budget = 0

◆ rfork_cache_used

size_t rfork_cache_used = 0

◆ rfork_lru

q_t* rfork_lru = NULL

◆ rfork_lru_count

unsigned int rfork_lru_count = 0

◆ rfork_max_entry_size

size_t rfork_max_entry_size = 0

◆ rfork_stat_added

unsigned long long rfork_stat_added = 0

◆ rfork_stat_evicted

unsigned long long rfork_stat_evicted = 0

◆ rfork_stat_hits

unsigned long long rfork_stat_hits = 0

◆ rfork_stat_invalidated

unsigned long long rfork_stat_invalidated = 0

◆ rfork_stat_lookups

unsigned long long rfork_stat_lookups = 0

◆ rfork_stat_misses

unsigned long long rfork_stat_misses = 0

◆ rfork_stat_used_max

size_t rfork_stat_used_max = 0

◆ validation_counter

volatile uint64_t validation_counter = 0

static

◆ vid_entry_count

uint32_t vid_entry_count[UINT16_MAX+1]

static

Data Structures

Macros

Enumerations

Functions

Variables

Detailed Description

Indexes

Debugging

Macro Definition Documentation

◆ get16bits

◆ HINT_READ_BUF_SIZE

◆ MAX_DEFERRED_CLEANUPS

◆ MAX_HINTS_PER_CYCLE

Enumeration Type Documentation

◆ arc_list_t

Function Documentation

◆ arc_case_i()

◆ arc_case_ii_adapt_and_replace()

◆ arc_case_iii_adapt_and_replace()

◆ arc_case_iv_insert()

◆ arc_case_iv_make_room()

◆ arc_destroy()

◆ arc_ensure_ghost_capacity()

◆ arc_evict_to_ghost()

◆ arc_find_victim()

◆ arc_ghost_trim_candidate()

◆ arc_init()

◆ arc_replace()

◆ arc_verify_invariants()

◆ deferred_batch_chain()

◆ deferred_batch_cmp()

◆ deferred_batch_complete()

◆ deferred_batch_match()

◆ deferred_batch_start()

◆ deferred_compact_head()

◆ deferred_compact_tail()

◆ deferred_cover_drops()

◆ deferred_cover_set()

◆ deferred_job_kill()

◆ dircache_add()

◆ dircache_defer_free()

◆ dircache_dump()

◆ dircache_evict()

◆ dircache_expunge_duplicate()

◆ dircache_flush_deferred_for_vol()

◆ dircache_has_deferred_work()

◆ dircache_init()

◆ dircache_lookup_parent()

◆ dircache_mismatch_panic()

◆ dircache_process_deferred_chain()

◆ dircache_promote()

◆ dircache_purge_vol()

◆ dircache_reindex_didname()

◆ dircache_remove()

◆ dircache_remove_children()

◆ dircache_remove_children_defer()

◆ dircache_report_invalid_entry()

◆ dircache_reset_validation_counter()

◆ dircache_resolve_size()

◆ dircache_rfork_shutdown()

◆ dircache_search_by_did()

◆ dircache_search_by_name()

◆ gone_event_for()

◆ hash_chain_head()

◆ hash_comp_didname()

◆ hash_comp_vid_did()

◆ hash_didname()

◆ hash_vid_did()

◆ log_dircache_stat()

◆ path_is_strict_child()

◆ process_cache_hints()

◆ should_validate_cache_entry()

◆ validation_expunge_and_hint()

◆ validation_freq()

◆ validation_refresh_and_hint()

Variable Documentation

◆ arc_cache

◆ arc_promoting_ghost

◆ cache_hint_stat

◆ deferred_active