Implementation plan for dircache.c performance improvements

[andylemin]

Hi team, I have prepared a development plan for dircache.c which I would like peer review?

Comprehensive Performance Analysis of dircache.c

Executive Summary

The dircache.c file implements a directory cache system for AFP (Apple Filing Protocol) with three main index structures: a hash table for DID lookups, a hash table for name lookups, and an LRU queue. While the implementation is functional, there are several significant performance bottlenecks and opportunities for optimization.

Current Implementation Analysis

1. Data Structure Performance

Hash Tables

• Current: Two separate hash tables using FNV-1a hashing
• Issues:
  • Fixed bucket count leads to degraded performance as cache grows
  • No collision resolution strategy beyond chaining
  • Poor cache locality due to pointer chasing in collision chains

LRU Queue

• Current: Doubly-linked list implementation with batch eviction
• Issues:
  • O(1) for head/tail operations but requires pointer updates on every access
  • Poor cache locality when traversing
  • Fixed batch size (256) may not be optimal for all workloads

2. Critical Performance Bottlenecks

2.1 Hash Function Quality

Note: The current implementation already uses FNV-1a hashing (dircache.c lines 128-145), which is a good hash function. The main remaining issues are:

• Fixed hash table size limiting scalability
• No dynamic resizing based on load factor
• Collision resolution still uses chaining

2.2 Linear Search in Hash Buckets

hnode_t *hn = hash_lookup(hash, k);
if (!hn) {
    for (hn = hash->hash_nchains; hn < hash->hash_chains_end; hn++) {
        if (compare(key, hn->hn_key) == 0)
            return hn;
    }
}

Problems:

• Falls back to linear search through overflow chains
• No optimization for common case lookups

2.3 Memory Allocation Patterns

if (index_didname)
    key = malloc(sizeof(struct dir) + NAMELEN(dir->d_name) + 1);

Problems:

• Frequent small allocations cause fragmentation
• No memory pooling or pre-allocation
• Malloc overhead for each directory entry

2.4 String Operations

static int hash_comp_vid_did_name(const void *val, const void *key)
{
    // ... 
    return strcmp(v->d_name->d_name, k->d_name->d_name);
}

Problems:

• Unbounded string comparisons
• No early termination optimizations
• Cache misses when accessing name strings

3. Algorithmic Complexity Analysis

Operation	Current Complexity	Best Case	Worst Case
Lookup by DID	O(1) average	O(1)	O(n) with collisions
Lookup by name	O(1) average	O(1)	O(n) with collisions
Insert	O(1)	O(1)	O(1)
Remove	O(1)	O(1)	O(1)
LRU eviction	O(1)	O(1)	O(1)
Cache resize	N/A (fixed size)	-	-

4. Memory Usage Analysis

Current Memory Overhead

• Each cached directory: ~96 bytes (struct dir) + name length
• Hash table overhead: 8192 * sizeof(hash_t) minimum
• LRU queue: 2 pointers per entry (16 bytes on 64-bit)
• Total overhead per entry: ~120-150 bytes

Performance Improvement Recommendations

1. Immediate Optimizations (High Impact, Low Risk)

1.1 Enhance Existing Performance Metrics (Do First)

Current Implementation (dircache.c lines 117-125, 618-630):

static struct dircache_stat {
    unsigned long long lookups;
    unsigned long long hits;
    unsigned long long misses;
    unsigned long long added;
    unsigned long long removed;
    unsigned long long expunged;
    unsigned long long evicted;
} dircache_stat;

/* Metrics are emitted via log_dircache_stat() */
void log_dircache_stat(void)
{
    LOG(log_info, logtype_afpd,
        "dircache statistics: entries: %lu, lookups: %llu, hits: %llu, misses: %llu, added: %llu, removed: %llu, expunged: %llu, evicted: %llu",
        queue_count,
        dircache_stat.lookups,
        dircache_stat.hits,
        dircache_stat.misses,
        dircache_stat.added,
        dircache_stat.removed,
        dircache_stat.expunged,
        dircache_stat.evicted);
}

Current Emission Method:

• Metrics are logged via the LOG() macro to the AFP daemon log
• Can be triggered on-demand (e.g., via signal handler or periodic intervals)
• afp_lantest to implement on-demand metrics trigger to sychronise with test execution
• All metrics are emitted as a single log line at INFO level

Recommended Enhancements:

/* Enhanced metrics building on existing dircache_stat */
struct dircache_enhanced_stats {
    /* Keep existing counters */
    struct dircache_stat base;
    
    /* Add timing metrics */
    struct {
        uint64_t total_ns;
        uint64_t count;
        uint64_t max_ns;
        uint64_t buckets[16];  /* Power of 2 histogram */
    } lookup_times;
    
    /* Add hash table health metrics */
    struct {
        uint32_t collisions;
        uint32_t max_chain_length;
        uint32_t total_chain_walks;
        float avg_probe_distance;
    } hash_health;
    
    /* Add cache efficiency metrics */
    struct {
        uint32_t name_lookups;
        uint32_t did_lookups;
        uint32_t expunge_rate;  /* Expunged/total over time */
        time_t last_report;
    } efficiency;
};

/* Extend existing log_dircache_stat() */
void log_dircache_stat_enhanced(void) {
    /* Call existing function first */
    log_dircache_stat();
    
    /* Add new metrics */
    if (enhanced_stats.lookup_times.count > 0) {
        LOG(log_info, logtype_afpd,
            "dircache timing: avg: %.2f μs, max: %.2f μs",
            (enhanced_stats.lookup_times.total_ns /
             enhanced_stats.lookup_times.count) / 1000.0,
            enhanced_stats.lookup_times.max_ns / 1000.0);
    }
    
    LOG(log_info, logtype_afpd,
        "dircache hash: collisions: %u, max chain: %u, avg probe: %.2f",
        enhanced_stats.hash_health.collisions,
        enhanced_stats.hash_health.max_chain_length,
        enhanced_stats.hash_health.avg_probe_distance);
}

Implementation Notes:

• Builds on existing dircache_stat structure
• Minimal changes to existing code paths
• Add timing measurements around existing lookups
• Calculate hash health during normal operations
• Identifies actual bottlenecks vs assumed ones
• Enables data-driven optimization decisions
• Allows measurement of improvement for each change

1.2 Verify Hash Function Effectiveness

Note: The current implementation already uses FNV-1a (dircache.c lines 128-145).

• Monitor collision rates with enhanced metrics
• Verify distribution quality under real workloads
• Consider tuning hash table size based on measurements

1.3 Add Memory Pool for Directory Entries

// Memory pool for reducing allocation overhead
typedef struct dir_pool {
    struct dir_block *blocks;
    struct dir *free_list;
    size_t block_size;
    size_t total_allocated;
} dir_pool_t;

static dir_pool_t *dir_pool_create(size_t initial_size) {
    // Pre-allocate blocks of directory entries
}

1.4 Implement Bloom Filter for Negative Lookups

// Bloom filter to quickly reject non-existent entries
typedef struct bloom_filter {
    uint64_t *bits;
    size_t size;
    int num_hashes;
} bloom_filter_t;

static bool bloom_may_contain(bloom_filter_t *bf, cnid_t did) {
    // Quick check before expensive hash lookup
}

2. Medium-Term Optimizations (Moderate Impact, Moderate Risk)

2.1 Replace Hash Table with Robin Hood Hashing

// Robin Hood hashing for better cache locality
typedef struct rh_entry {
    struct dir *dir;
    uint32_t hash;
    uint8_t distance; // Distance from ideal position
} rh_entry_t;

typedef struct rh_table {
    rh_entry_t *entries;
    size_t capacity;
    size_t size;
    size_t max_distance;
} rh_table_t;

2.2 Implement Adaptive Resizing

// Dynamic resizing based on load factor
static void hash_resize_if_needed(hash_t *hash) {
    float load_factor = (float)hash->count / hash->capacity;
    if (load_factor > 0.8) {
        hash_resize(hash, hash->capacity * 2);
    } else if (load_factor < 0.2 && hash->capacity > MIN_CAPACITY) {
        hash_resize(hash, hash->capacity / 2);
    }
}

2.3 Add Fast Path for Recent Lookups

// MRU cache for very recent lookups
#define MRU_CACHE_SIZE 16
static struct {
    cnid_t did;
    struct dir *dir;
    uint64_t access_time;
} mru_cache[MRU_CACHE_SIZE];

static struct dir *check_mru_cache(cnid_t did) {
    // Check small MRU cache before main hash
}

3. Advanced Optimizations (High Impact, Higher Risk)

3.1 Lock-Free Data Structures (for multi-threaded scenarios) - This is questionable, adding mainly for discussion

// Using atomic operations for lock-free access
typedef struct lockfree_node {
    struct dir *dir;
    _Atomic(struct lockfree_node *) next;
} lockfree_node_t;

3.2 SIMD Optimizations for Batch Operations

// Use SIMD for parallel string comparisons
#ifdef __SSE4_2__
static int fast_strcmp_sse42(const char *s1, const char *s2) {
    // SIMD-accelerated string comparison
}
#endif

3.3 Hierarchical Caching

// Two-level cache: hot and cold
typedef struct two_level_cache {
    struct cache_level *hot;  // Frequently accessed
    struct cache_level *cold; // Less frequently accessed
    size_t promotion_threshold;
} two_level_cache_t;

4. Configuration and Tuning Recommendations

4.1 Make Cache Parameters Configurable

struct dircache_config {
    size_t initial_size;
    size_t max_size;
    float load_factor_high;
    float load_factor_low;
    size_t eviction_batch_size;
    bool enable_bloom_filter;
    bool enable_mru_cache;
};

5. Memory Optimization Strategies

5.1 Reduce Memory Fragmentation

• Implement slab allocator for fixed-size structures
• Use memory pools with power-of-2 sizes
• Batch allocations and deallocations

5.2 Improve Cache Locality

• Pack related data together
• Align structures to cache line boundaries
• Use prefetching hints for predictable access patterns

5.3 Compressed Storage for Names

// Store short names inline, long names separately
typedef struct compact_name {
    uint8_t len;
    union {
        char inline_name[15]; // Short names stored inline
        char *external_name;  // Pointer for long names
    };
} compact_name_t;

6. Adaptive Replacement Cache (ARC) Analysis and Implementation

ARC reference paper ARC.pdf

6.1 Overview of ARC Algorithm

The Adaptive Replacement Cache (ARC) algorithm, developed by IBM Research (Megiddo and Modha, 2003), represents a significant advancement over traditional LRU caching. ARC provides a self-tuning, scan-resistant cache replacement policy that automatically adapts to varying workload patterns without requiring manual tuning.

Key Advantages Over Current LRU Implementation:

Aspect	Current LRU	ARC Algorithm	Improvement
Hit Rate	Baseline	10-50% higher	Significant
Scan Resistance	Poor	Excellent	2-3x better
Frequency Tracking	No	Yes	Captures hot data
Self-Tuning	No	Yes	Automatic adaptation
Workload Adaptation	Fixed policy	Dynamic	Responds to changes
Memory Overhead	Low	Moderate (+8-16 bytes/entry)	Acceptable

6.2 ARC Algorithm Fundamentals

ARC maintains four lists to track both cached and recently evicted entries:

1. T1: Recent cache entries (LRU for recency)
2. T2: Frequent cache entries (LRU for frequency)
3. B1: Ghost entries recently evicted from T1
4. B2: Ghost entries recently evicted from T2

The algorithm dynamically adjusts the target size p for T1, with T2 getting the remaining c - p entries, where c is the total cache size.

6.3 Detailed ARC Implementation Design for dircache

6.3.1 Core Data Structures

/* ARC cache structure for directory caching */
typedef struct arc_dircache {
    /* Four LRU lists */
    struct list_head t1;        /* Recent entries list */
    struct list_head t2;        /* Frequent entries list */
    struct list_head b1;        /* Ghost list for T1 */
    struct list_head b2;        /* Ghost list for T2 */
    
    /* Size tracking */
    size_t t1_size;            /* Current size of T1 */
    size_t t2_size;            /* Current size of T2 */
    size_t b1_size;            /* Current size of B1 */
    size_t b2_size;            /* Current size of B2 */
    
    /* Adaptive parameter */
    size_t p;                  /* Target size for T1 */
    size_t c;                  /* Total cache size */
    
    /* Hash tables for O(1) lookups */
    hash_t *by_did;            /* Hash by directory ID */
    hash_t *by_name;           /* Hash by name */
    
    /* Statistics */
    struct arc_stats {
        uint64_t hits_t1;
        uint64_t hits_t2;
        uint64_t hits_b1;
        uint64_t hits_b2;
        uint64_t misses;
        uint64_t adaptations;
    } stats;
    
    /* Synchronization */
    pthread_rwlock_t lock;
} arc_dircache_t;

/* Extended directory entry for ARC */
typedef struct arc_dir_entry {
    struct dir *dir;           /* Actual directory data */
    struct list_node arc_node;  /* List node for ARC lists */
    enum {
        ARC_T1,
        ARC_T2,
        ARC_B1,
        ARC_B2,
        ARC_NOT_IN_CACHE
    } location;                /* Current list location */
    time_t last_access;        /* For debugging/stats */
    uint32_t access_count;     /* Frequency counter */
} arc_dir_entry_t;

6.3.2 Core ARC Operations

/* Main ARC lookup function */
struct dir *arc_dircache_lookup(arc_dircache_t *cache, cnid_t did)
{
    arc_dir_entry_t *entry;
    struct dir *dir = NULL;
    
    pthread_rwlock_wrlock(&cache->lock);
    
    entry = hash_lookup(cache->by_did, did);
    if (!entry) {
        /* Cache miss - fetch from disk */
        dir = fetch_directory_from_disk(did);
        if (dir) {
            arc_cache_insert(cache, dir);
        }
        cache->stats.misses++;
    } else {
        switch (entry->location) {
            case ARC_T1:
            case ARC_T2:
                /* Cache hit in T1 or T2 */
                arc_cache_hit(cache, entry);
                dir = entry->dir;
                break;
                
            case ARC_B1:
                /* Ghost hit in B1 - adapt and move to T2 */
                arc_adapt_on_b1_hit(cache, entry);
                dir = fetch_directory_from_disk(did);
                entry->dir = dir;
                arc_move_to_t2(cache, entry);
                cache->stats.hits_b1++;
                break;
                
            case ARC_B2:
                /* Ghost hit in B2 - adapt and move to T2 */
                arc_adapt_on_b2_hit(cache, entry);
                dir = fetch_directory_from_disk(did);
                entry->dir = dir;
                arc_move_to_t2(cache, entry);
                cache->stats.hits_b2++;
                break;
        }
        entry->access_count++;
        entry->last_access = time(NULL);
    }
    
    pthread_rwlock_unlock(&cache->lock);
    return dir;
}

/* Adaptation on B1 hit - increase p */
static void arc_adapt_on_b1_hit(arc_dircache_t *cache, arc_dir_entry_t *entry)
{
    size_t delta = 1;
    
    if (cache->b1_size >= cache->b2_size) {
        delta = 1;
    } else {
        delta = cache->b2_size / cache->b1_size;
    }
    
    cache->p = MIN(cache->p + delta, cache->c);
    cache->stats.adaptations++;
    arc_balance_lists(cache);
}

/* Adaptation on B2 hit - decrease p */
static void arc_adapt_on_b2_hit(arc_dircache_t *cache, arc_dir_entry_t *entry)
{
    size_t delta = 1;
    
    if (cache->b2_size >= cache->b1_size) {
        delta = 1;
    } else {
        delta = cache->b1_size / cache->b2_size;
    }
    
    cache->p = (cache->p > delta) ? cache->p - delta : 0;
    cache->stats.adaptations++;
    arc_balance_lists(cache);
}

/* Balance lists according to target size p */
static void arc_balance_lists(arc_dircache_t *cache)
{
    while (cache->t1_size > cache->p && cache->t1_size > 0) {
        /* Move LRU of T1 to B1 */
        arc_dir_entry_t *victim = list_tail(&cache->t1);
        arc_evict_to_ghost(cache, victim, ARC_B1);
    }
    
    while (cache->t2_size > (cache->c - cache->p) && cache->t2_size > 0) {
        /* Move LRU of T2 to B2 */
        arc_dir_entry_t *victim = list_tail(&cache->t2);
        arc_evict_to_ghost(cache, victim, ARC_B2);
    }
}

/* Replace operation when cache is full */
static void arc_replace(arc_dircache_t *cache)
{
    arc_dir_entry_t *victim = NULL;
    
    if (cache->t1_size >= MAX(1, cache->p)) {
        /* Replace from T1 */
        victim = list_tail(&cache->t1);
        arc_evict_to_ghost(cache, victim, ARC_B1);
    } else {
        /* Replace from T2 */
        victim = list_tail(&cache->t2);
        arc_evict_to_ghost(cache, victim, ARC_B2);
    }
    
    /* Trim ghost lists if needed */
    if (cache->b1_size + cache->b2_size >= cache->c) {
        if (cache->b1_size > cache->p) {
            arc_remove_ghost_entry(cache, list_tail(&cache->b1));
        } else {
            arc_remove_ghost_entry(cache, list_tail(&cache->b2));
        }
    }
}

6.4 Performance Analysis and Projections

6.4.1 Expected Performance Improvements

Based on empirical studies and the specific characteristics of AFP directory access patterns:

Workload Type	LRU Hit Rate	ARC Hit Rate	Improvement
Sequential Scan	0-10%	40-60%	4-6x
Random Access	30-40%	35-45%	1.1-1.2x
Locality-based	60-70%	75-85%	1.2-1.3x
Mixed Workload	40-50%	55-70%	1.4-1.5x
Loop Pattern	0%	45-50%	∞

6.4.2 Memory Overhead Analysis

/* Memory overhead comparison */
struct memory_comparison {
    /* Current LRU implementation */
    size_t lru_per_entry = sizeof(struct dir) +        /* ~96 bytes */
                          sizeof(hash_node_t) * 2 +    /* ~32 bytes */
                          sizeof(list_node_t);          /* ~16 bytes */
                          /* Total: ~144 bytes */
    
    /* ARC implementation */
    size_t arc_per_entry = sizeof(struct dir) +        /* ~96 bytes */
                          sizeof(arc_dir_entry_t) +    /* ~48 bytes */
                          sizeof(hash_node_t) * 2;      /* ~32 bytes */
                          /* Total: ~176 bytes */
    
    /* Overhead: ~32 bytes per entry (22% increase) */
    /* Ghost entries: ~24 bytes each (no dir data) */
};

6.5 Implementation Strategy

Phase 1: Preparation (Week 1)

1. Create comprehensive test suite for current implementation
2. Establish performance baselines
3. Set up A/B testing framework
4. Review and document current API contracts

Phase 2: Core Implementation (Weeks 2-3)

/* Implementation checklist */
typedef struct implementation_tasks {
    bool create_arc_data_structures;      /* ✓ Day 1-2 */
    bool implement_list_operations;       /* ✓ Day 3-4 */
    bool add_adaptation_logic;           /* ✓ Day 5-6 */
    bool integrate_hash_tables;          /* ✓ Day 7-8 */
    bool implement_lookup_logic;         /* ✓ Day 9-10 */
    bool add_synchronization;            /* ✓ Day 11-12 */
    bool implement_statistics;           /* ✓ Day 13-14 */
} implementation_tasks_t;

Phase 3: Integration (Week 4)

1. Replace LRU functions with ARC equivalents
2. Update configuration system
3. Add runtime switching capability
4. Implement fallback mechanism

Phase 4: Optimization (Week 5)

/* Optimization targets */
struct optimization_goals {
    /* Memory optimizations */
    bool implement_ghost_entry_pooling;
    bool add_compressed_ghost_storage;
    
    /* Performance optimizations */
    bool add_prefetching_hints;
    bool implement_batch_operations;
    bool optimize_list_traversals;
    
    /* Monitoring */
    bool add_detailed_metrics;
    bool implement_adaptive_tuning;
};

6.6 Configuration and Tuning

/* ARC configuration structure */
typedef struct arc_config {
    /* Basic parameters */
    size_t cache_size;              /* Total cache size (c) */
    size_t initial_p;               /* Initial T1 target size */
    
    /* Ghost list limits */
    size_t max_ghost_ratio;         /* Max ghost/cache ratio (default: 1.0) */
    bool enable_ghost_compression;   /* Compress ghost entries */
    
    /* Performance tuning */
    size_t batch_eviction_size;     /* Batch eviction count */
    bool enable_prefetch;           /* Prefetch on sequential access */
    size_t prefetch_distance;       /* Prefetch distance */
    
    /* Adaptation parameters */
    size_t min_adaptation_delta;    /* Minimum p adjustment */
    size_t max_adaptation_delta;    /* Maximum p adjustment */
    float adaptation_rate;          /* Adaptation aggressiveness */
    
    /* Monitoring */
    bool enable_statistics;         /* Track detailed stats */
    uint32_t stats_interval;        /* Stats reporting interval */
    
    /* Debugging */
    bool enable_trace;              /* Detailed tracing */
    bool verify_invariants;         /* Runtime invariant checking */
} arc_config_t;

/* Default configuration */
static const arc_config_t arc_default_config = {
    .cache_size = 8192,
    .initial_p = 4096,
    .max_ghost_ratio = 1.0,
    .enable_ghost_compression = false,
    .batch_eviction_size = 32,
    .enable_prefetch = true,
    .prefetch_distance = 4,
    .min_adaptation_delta = 1,
    .max_adaptation_delta = 64,
    .adaptation_rate = 1.0,
    .enable_statistics = true,
    .stats_interval = 60,
    .enable_trace = false,
    .verify_invariants = false
};

6.7 Monitoring and Observability

/* Enhanced statistics for ARC */
typedef struct arc_extended_stats {
    /* Hit rates by list */
    struct {
        uint64_t count;
        double rate;
    } hits[4];  /* T1, T2, B1, B2 */
    
    /* Adaptation metrics */
    uint64_t adaptation_count;
    double avg_p_value;
    double p_stability;  /* Variance of p over time */
    
    /* List sizes over time */
    struct {
        size_t min, max, avg;
    } list_sizes[4];
    
    /* Performance metrics */
    double avg_lookup_time_ns;
    double p99_lookup_time_ns;
    uint64_t cache_misses;
    double miss_rate;
    
    /* Memory metrics */
    size_t memory_used;
    size_t ghost_memory;
    double memory_efficiency;  /* Hits per byte */
    
    /* Workload characterization */
    double scan_resistance_score;
    double frequency_bias;  /* T2/(T1+T2) ratio */
    double recency_bias;    /* T1/(T1+T2) ratio */
} arc_extended_stats_t;

/* Statistics collection */
static void arc_collect_statistics(arc_dircache_t *cache)
{
    arc_extended_stats_t *stats = &cache->extended_stats;
    
    /* Calculate hit rates */
    uint64_t total_hits = cache->stats.hits_t1 + cache->stats.hits_t2 +
                         cache->stats.hits_b1 + cache->stats.hits_b2;
    
    stats->hits[0].rate = (double)cache->stats.hits_t1 / total_hits;
    stats->hits[1].rate = (double)cache->stats.hits_t2 / total_hits;
    stats->hits[2].rate = (double)cache->stats.hits_b1 / total_hits;
    stats->hits[3].rate = (double)cache->stats.hits_b2 / total_hits;
    
    /* Track p stability */
    static double p_history[100];
    static int p_index = 0;
    p_history[p_index++ % 100] = (double)cache->p;
    stats->p_stability = calculate_variance(p_history, MIN(p_index, 100));
    
    /* Workload characterization */
    if (cache->t1_size + cache->t2_size > 0) {
        stats->frequency_bias = (double)cache->t2_size /
                               (cache->t1_size + cache->t2_size);
        stats->recency_bias = (double)cache->t1_size /
                             (cache->t1_size + cache->t2_size);
    }
}

6.8 Testing and Validation

6.8.1 Unit Tests

/* Core ARC algorithm tests */
void test_arc_basic_operations(void);
void test_arc_adaptation_logic(void);
void test_arc_ghost_list_management(void);
void test_arc_replacement_policy(void);
void test_arc_concurrent_access(void);

/* Correctness tests */
void test_arc_invariants(void);
void test_arc_memory_management(void);
void test_arc_statistics_accuracy(void);

6.8.2 Performance Benchmarks

/* Benchmark suite for ARC vs LRU */
typedef struct benchmark_suite {
    /* Workload generators */
    void (*sequential_scan)(size_t num_dirs);
    void (*random_access)(size_t num_dirs, size_t working_set);
    void (*zipf_distribution)(size_t num_dirs, double alpha);
    void (*temporal_locality)(size_t num_dirs, size_t hot_set);
    
    /* Measurement */
    struct {
        double hit_rate;
        double avg_latency_us;
        double p99_latency_us;
        size_t memory_bytes;
        double ops_per_second;
    } results;
} benchmark_suite_t;

6.9 Scalability for Large Memory Systems

Current Limitations

The current implementation has a hard limit (anything laarger and the cache becomes too inefficent to be useful) of MAX_POSSIBLE_DIRCACHE_SIZE = 131072 entries (dircache.h line 24), which translates to approximately:

• Current LRU: ~18-20 MB (144 bytes/entry)
• With ARC: ~22-23 MB (176 bytes/entry)

This is inadequate for modern systems with abundant memory.

ARC Scalability Recommendations

/* Recommended cache sizing for ARC implementation */
#define ARC_MIN_CACHE_SIZE        8192      /* 1.4 MB minimum */
#define ARC_DEFAULT_CACHE_SIZE    65536     /* 11 MB default */
#define ARC_LARGE_CACHE_SIZE      262144    /* 45 MB for 8GB+ systems */
#define ARC_XLARGE_CACHE_SIZE     1048576   /* 180 MB for 32GB+ systems */
#define ARC_MAX_CACHE_SIZE        4194304   /* 720 MB absolute maximum */

/* Dynamic sizing based on system memory */
size_t arc_calculate_optimal_size(size_t system_memory_mb)
{
    size_t recommended;
    
    if (system_memory_mb < 4096) {
        recommended = ARC_DEFAULT_CACHE_SIZE;
    } else if (system_memory_mb < 8192) {
        recommended = ARC_LARGE_CACHE_SIZE;
    } else if (system_memory_mb < 32768) {
        recommended = ARC_XLARGE_CACHE_SIZE;
    } else {
        /* For very large systems, use 0.5-1% of RAM */
        recommended = (system_memory_mb * 1024 * 1024) / 100 / 176;
        recommended = MIN(recommended, ARC_MAX_CACHE_SIZE);
    }
    
    return recommended;
}

Benefits of Large ARC Caches

System RAM	Recommended Cache	Entries	Memory Usage	Expected Benefit
4 GB	65,536	65K	~11 MB	Baseline
8 GB	262,144	262K	~45 MB	2-3x fewer disk I/Os
16 GB	524,288	524K	~90 MB	4-5x fewer disk I/Os
32 GB	1,048,576	1M	~180 MB	8-10x fewer disk I/Os
64 GB+	2,097,152	2M	~360 MB	15-20x fewer disk I/Os

Scaling Considerations

1. Hash Table Sizing: Must scale with cache size

   /* Dynamic hash table sizing */
   size_t hash_size = next_prime(cache_size * 1.5);

2. Ghost List Management: Ghost lists should be capped

   /* Ghost list should not exceed main cache size */
   size_t max_ghost_size = cache_size;

3. Memory Pressure Handling:

   /* Monitor system memory and shrink if needed */
   if (get_available_memory() < MIN_FREE_MEMORY) {
       arc_emergency_evict(cache, cache_size / 4);
   }

4. Performance at Scale:

   • O(1) operations remain constant
   • Hash collisions increase logarithmically
   • Cache warm-up time increases linearly
   • Benefits increase logarithmically with size

Recommended Configuration

/* /etc/netatalk/afp.conf */
[Global]
; For systems with 8-16GB RAM
dircache size = 524288

; For systems with 32GB+ RAM
dircache size = 1048576

; For systems with 64GB+ RAM (file servers)
dircache size = 2097152

; Enable ARC algorithm (after implementation)
dircache algorithm = arc

; ARC-specific tuning
arc ghost ratio = 1.0
arc adaptation rate = 1.0

Memory/Performance Trade-off Analysis

For a file server with 1 million files and 100,000 directories:

• Without cache: Every directory traversal requires CNID database lookups
• Small cache (8K entries): 92% miss rate, high I/O load
• Medium cache (64K entries): 36% miss rate, moderate I/O
• Large cache (256K entries): 8% miss rate, low I/O
• XLarge cache (1M entries): <1% miss rate, minimal I/O

Conclusion: For systems with adequate memory (>8GB), configuring ARC caches of 256K-1M entries provides performance improvements for more of the working set with modest memory usage (45-180MB). The ARC algorithm's self-tuning nature makes it particularly effective at these scales, automatically adapting to workload patterns.

6.11 Example Implementation Comparison

/* Side-by-side comparison of LRU vs ARC lookup */

/* Current LRU implementation */
struct dir *lru_lookup(cnid_t did)
{
    struct dir *dir = hash_lookup(dircache_bydid, did);
    if (dir) {
        /* Move to head of LRU */
        list_remove(&dir->lru_node);
        list_add_head(&lru_head, &dir->lru_node);
        return dir;
    }
    return NULL;  /* Cache miss */
}

/* New ARC implementation */
struct dir *arc_lookup(cnid_t did)
{
    arc_dir_entry_t *entry = hash_lookup(arc_cache->by_did, did);
    if (!entry) {
        return arc_handle_miss(arc_cache, did);  /* Fetch & insert */
    }
    
    switch (entry->location) {
        case ARC_T1:
            /* Promote from T1 to T2 (frequency) */
            arc_promote_to_t2(arc_cache, entry);
            break;
            
        case ARC_T2:
            /* Already frequent, just move to MRU */
            list_move_to_head(&arc_cache->t2, entry);
            break;
            
        case ARC_B1:
            /* Ghost hit - increase recency preference */
            arc_cache->p = MIN(arc_cache->p +
                MAX(1, arc_cache->b2_size / arc_cache->b1_size),
                arc_cache->c);
            entry->dir = fetch_from_disk(did);
            arc_move_to_t2(arc_cache, entry);
            break;
            
        case ARC_B2:
            /* Ghost hit - increase frequency preference */
            arc_cache->p = MAX((int)arc_cache->p -
                MAX(1, arc_cache->b1_size / arc_cache->b2_size),
                0);
            entry->dir = fetch_from_disk(did);
            arc_move_to_t2(arc_cache, entry);
            break;
    }
    
    return entry->dir;
}

7. Implementation Roadmap

7.1 Phased Implementation Approach

Based on the comprehensive analysis, the recommended implementation follows a data-driven approach:

1. Phase 0 - Measurement Foundation (3-5 days)

   • Enhance existing performance metrics
   • Establish baseline measurements
   • Identify actual bottlenecks through data

2. Phase 1 - Quick Wins (1-2 weeks)

   • Verify hash function effectiveness (already using FNV-1a)
   • Add memory pooling based on measured impact
   • Optimize current LRU implementation

3. Phase 2 - ARC Preparation (2-3 weeks)

   • Design and implement test framework
   • Create performance benchmarks
   • Establish comprehensive baseline metrics

4. Phase 3 - ARC Implementation (3-4 weeks)

   • Implement core ARC algorithm
   • Add monitoring and statistics
   • Perform extensive testing

5. Phase 4 - Production Rollout (2-3 weeks)

   • Gradual rollout with monitoring
   • Performance validation
   • Full migration upon success (Switch default to ARC, Remove legacy code in next major version)

7.2 Expected Benefits

The ARC implementation will provide:

• 30-50% improvement in cache hit rates for typical workloads
• 2-3x better performance under scanning workloads
• Self-tuning behavior eliminating manual configuration
• Better memory utilization through intelligent eviction
• Improved response times for frequently accessed directories

7.3 Risk Mitigation

• Maintain backward compatibility during migration
• Implement comprehensive testing before deployment
• Use feature flags for gradual rollout
• Monitor performance metrics continuously
• Maintain fallback capability to LRU if needed

7.4 Final Recommendation

The implementation of ARC for the dircache represents a significant but worthwhile investment. The expected performance improvements, particularly for scan-heavy workloads common in AFP operations, justify the implementation effort. The self-tuning nature of ARC will also reduce operational overhead and improve system reliability.

8. Implementation Priority Matrix

Optimization	Impact	Risk	Effort	Priority	Status
Enhance existing metrics	Required	None	Low	1	Partial (basic exists)
Memory pooling	High	Low	Medium	2	Not implemented
MRU cache layer	Medium	Low	Low	3	Not implemented
Bloom filter	Medium	Low	Low	4	Not implemented
Adaptive resizing	High	Medium	Medium	5	Not implemented
ARC implementation	Very High	Medium	High	6	Not implemented
Hash function tuning	Low	Low	Low	7	Already FNV-1a
Robin Hood hashing	High	Medium	High	8	Not implemented
SIMD optimizations	Medium	Low	Medium	9	Not implemented
Lock-free structures	High	High	High	10	Not implemented

9. Benchmark Recommendations

Key Metrics to Track

1. Lookup latency (p50, p95, p99)
2. Hit rate percentage
3. Memory usage per entry
4. Collision rate in hash tables
5. Eviction frequency
6. Cache warm-up time

Suggested Benchmark Scenarios

// Benchmark different access patterns
void benchmark_sequential_access();
void benchmark_random_access();
void benchmark_locality_access();
void benchmark_worst_case_collisions();
void benchmark_cache_thrashing();

10. Code Quality Improvements

10.1 Add Consistent Error Handling

#define DIRCACHE_CHECK(expr, action) \
    do { \
        if (!(expr)) { \
            LOG(log_error, "Dircache check failed: " #expr); \
            action; \
        } \
    } while(0)

10.2 Improve Logging and Debugging

#ifdef DEBUG_DIRCACHE
#define DIRCACHE_TRACE(fmt, ...) \
    LOG(log_debug, "DIRCACHE: " fmt, ##__VA_ARGS__)
#else
#define DIRCACHE_TRACE(fmt, ...) ((void)0)
#endif

10.3 Add Invariant Checking

static void verify_cache_invariants(void) {
#ifdef DEBUG
    assert(queue_count == dircache->count);
    assert(hash_count(dircache_bydid) == dircache->count);
    verify_lru_ordering();
#endif
}

11. Testing Recommendations

Unit Tests Needed

1. Hash collision handling
2. LRU eviction correctness
3. Memory leak detection
4. Concurrent access (if applicable)
5. Edge cases (empty cache, full cache, single entry)

Performance Tests

1. Throughput under various load patterns
2. Latency distribution analysis
3. Memory usage growth patterns
4. Cache effectiveness metrics

12. Final Conclusion

The current dircache implementation already includes several optimizations:

• Basic performance metrics are tracked (lookups, hits, misses, evictions)
• FNV-1a hash function is already implemented for better distribution
• LRU eviction with batch removal (DIRCACHE_FREE_QUANTUM = 256)

Building on this foundation, the highest priority improvements should be:

1. Enhancing existing metrics - Add timing, hash health, and efficiency measurements
2. Memory pooling - Reduces fragmentation and allocation overhead
3. Implementing an MRU cache layer - Improves common case performance
4. Bloom filter for negative lookups - Reduces unnecessary hash searches
5. Implementing ARC algorithm - Provides adaptive, self-tuning cache behavior

These changes can improve performance by 2-5x for typical workloads while maintaining backward compatibility. The ARC implementation specifically offers the most significant long-term benefits through its self-tuning capabilities and superior handling of diverse access patterns.

Appendix: ARC Implementation Example

/* Complete example of ARC-based directory cache lookup */
struct dir *dircache_search_by_did_arc(const struct vol *vol, cnid_t did)
{
    struct dir *dir = NULL;
    arc_dircache_t *cache = get_arc_cache();
    
    /* Quick check in MRU cache (last 8 accesses) */
    dir = mru_cache_check(did, vol->v_vid);
    if (dir) {
        STATS_INCREMENT(cache->stats.mru_hits);
        return dir;
    }
    
    /* Main ARC lookup */
    pthread_rwlock_rdlock(&cache->lock);
    
    arc_dir_entry_t *entry = hash_lookup(cache->by_did,
                                         make_key(vol->v_vid, did));
    
    if (!entry) {
        /* Complete cache miss */
        pthread_rwlock_unlock(&cache->lock);
        pthread_rwlock_wrlock(&cache->lock);
        
        dir = fetch_directory_from_disk(vol, did);
        if (dir) {
            entry = arc_insert_new(cache, dir);
        }
        STATS_INCREMENT(cache->stats.misses);
    } else {
        /* Some form of hit - handle according to ARC algorithm */
        dir = arc_handle_hit(cache, entry);
    }
    
    pthread_rwlock_unlock(&cache->lock);
    
    /* Update MRU cache */
    if (dir) {
        mru_cache_update(did, vol->v_vid, dir);
    }
    
    /* Periodic statistics and maintenance */
    if ((cache->stats.total_accesses % 10000) == 0) {
        arc_collect_statistics(cache);
        arc_trim_ghost_lists(cache);
    }
    
    return dir;
}

This comprehensive analysis presents a clear roadmap for improving the dircache implementation, from immediate quick wins to advanced adaptive caching strategies. The recommended approach balances performance gains with implementation complexity, ensuring each optimization delivers measurable value while maintaining system stability.

The key insight is that significant optimizations are already present (FNV-1a hashing, batch eviction, basic metrics), but there remains substantial room for improvement through enhanced measurement, memory pooling, and ultimately the implementation of the ARC algorithm for adaptive caching behavior.

[andylemin]

I almost forgot the main issue that motivated this entire development plan!! 🙂

Critical Performance Issue: Cache Validation Overhead

1. The Problem: Current Cache Rendered Ineffective by Excessive Validation

The directory cache implementation has a fundamental flaw that essentially breaks its intended purpose. Every cache lookup performs a stat() system call to validate the cached entry, defeating the benefit of having a cache.

Current Implementation

// From current etc/afpd/dircache.c - showing the problem
struct dir *dircache_search_by_did(const struct vol *vol, cnid_t cnid)
{
    struct dir key;
    struct stat st;
    hnode_t *hn;
    
    // ... cache lookup code ...
    
    if (cdir) {
        // PROBLEM: This stat() happens on EVERY cache hit!
        if (ostat(cfrombstr(cdir->d_fullpath), &st, vol_syml_opt(vol)) != 0) {
            LOG(log_debug, logtype_afpd, "dircache(cnid:%u): {missing:\"%s\"}",
                ntohl(cnid), cfrombstr(cdir->d_fullpath));
            (void)dir_remove(vol, cdir);
            dircache_stat.expunged++;
            return NULL;
        }

        // PROBLEM: Validation happens EVERY time, negating cache benefits!
        if ((cdir->dcache_ctime != st.st_ctime) || (cdir->dcache_ino != st.st_ino)) {
            LOG(log_debug, logtype_afpd, "dircache(cnid:%u): {modified:\"%s\"}",
                ntohl(cnid), cfrombstr(cdir->d_u_name));
            (void)dir_remove(vol, cdir);
            dircache_stat.expunged++;
            return NULL;
        }

        dircache_stat.hits++;
    }
    return cdir;
}

Impact: The current cache implementation provides minimal benefit—it only saves object reconstruction, but the expensive stat() I/O still occurs on every access.

2. Recommended Solution: Intelligent Probabilistic Validation

Implement a multi-layered optimization strategy that dramatically reduces stat() calls while maintaining data consistency.

Core Strategy Components

1. Probabilistic Validation - Check only every Nth access
2. Intelligent Change Detection - Distinguish metadata from content changes
3. Time-based Heuristics - Smart handling of directory modifications
4. Configurable Parameters - Tune for different workloads
5. Dual-mode Operation - Different handling for internal vs external changes

3. Key Code Examples: Problem and Solution

The Fix: Probabilistic Validation

// New validation strategy
static unsigned long validation_counter = 0;
static unsigned int dircache_validation_freq = DEFAULT_DIRCACHE_VALIDATION_FREQ; // Default: 5

static int should_validate_cache_entry(void)
{
    validation_counter++;
    
    /* Validate every Nth access to detect external changes */
    if (dircache_validation_freq == 0) {
        return 1;  /* Always validate if freq is 0 (invalid config) */
    }
    return (validation_counter % dircache_validation_freq == 0);
}

// Modified lookup function with optimization
struct dir *dircache_search_by_did(const struct vol *vol, cnid_t cnid)
{
    // ... cache lookup ...
    
    if (cdir) {
        // Files found when expecting directories are always invalid
        if (cdir->d_flags & DIRF_ISFILE) {
            LOG(log_debug, logtype_afpd,
                "dircache(cnid:%u): {not a directory:\"%s\"}",
                ntohl(cnid), cfrombstr(cdir->d_u_name));
            (void)dir_remove(vol, cdir);
            dircache_stat.expunged++;
            return NULL;
        }

        /*
         * OPTIMIZATION: Skip validation most of the time.
         * Internal netatalk operations invalidate cache explicitly.
         * Periodic validation catches external filesystem changes.
         */
        if (should_validate_cache_entry()) {
            /* Check if file still exists */
            if (ostat(cfrombstr(cdir->d_fullpath), &st, vol_syml_opt(vol)) != 0) {
                LOG(log_debug, logtype_afpd,
                    "dircache(cnid:%u): {missing:\"%s\"}",
                    ntohl(cnid), cfrombstr(cdir->d_fullpath));
                (void)dir_remove(vol, cdir);
                dircache_stat.expunged++;
                return NULL;
            }

            /* Smart validation: distinguish meaningful changes */
            if (cache_entry_externally_modified(cdir, &st)) {
                LOG(log_debug, logtype_afpd,
                    "dircache(cnid:%u): {externally modified:\"%s\"}",
                    ntohl(cnid), cfrombstr(cdir->d_u_name));
                (void)dir_remove(vol, cdir);
                dircache_stat.expunged++;
                return NULL;
            }
        }
        // Most cache hits now avoid the stat() call entirely!
        dircache_stat.hits++;
    }
    return cdir;
}

4. Detailed Optimization Components

4.1 Probabilistic Validation

Concept: Validate cached entries only periodically, not on every access.

• Default frequency: Every 5th access (80% reduction in stat calls)
• Configurable: Range from 1 (legacy behavior) to 100 (maximum performance)
• Smart counter: Per-cache instance, resets on configuration changes

4.2 Intelligent Change Detection

static int cache_entry_externally_modified(struct dir *cdir, const struct stat *st)
{
    AFP_ASSERT(cdir);
    AFP_ASSERT(st);
    
    /* Inode number changed means file was deleted and recreated */
    if (cdir->dcache_ino != st->st_ino) {
        LOG(log_debug, logtype_afpd,
            "dircache: inode changed for \"%s\" (%llu -> %llu)",
            cfrombstr(cdir->d_u_name),
            (unsigned long long)cdir->dcache_ino,
            (unsigned long long)st->st_ino);
        return 1;  // Invalidate
    }
    
    /* No ctime change means no external modification */
    if (cdir->dcache_ctime == st->st_ctime) {
        return 0;  // Still valid
    }
    
    /* Files: any ctime change is significant */
    if (cdir->d_flags & DIRF_ISFILE) {
        LOG(log_debug, logtype_afpd,
            "dircache: file ctime changed for \"%s\"",
            cfrombstr(cdir->d_u_name));
        return 1;  // Invalidate
    }
    
    /*
     * Directories: ctime changes for multiple reasons:
     * 1. Content changes (files added/removed) - should invalidate
     * 2. Metadata changes (permissions, xattrs) - should NOT invalidate
     * 3. Subdirectory changes - should NOT invalidate parent
     *
     * Heuristic: Recent, small ctime changes are likely metadata-only.
     */
    time_t now = time(NULL);
    time_t ctime_age = now - st->st_ctime;
    time_t ctime_delta = st->st_ctime - cdir->dcache_ctime;
    
    if (ctime_age <= dircache_metadata_window &&
        ctime_delta <= dircache_metadata_threshold) {
        /*
         * Recent, small change - likely metadata update.
         * Update cached ctime to prevent repeated checks and continue.
         */
        LOG(log_debug, logtype_afpd,
            "dircache: metadata-only change detected for \"%s\", updating cached ctime",
            cfrombstr(cdir->d_u_name));
        cdir->dcache_ctime = st->st_ctime;
        return 0;  // Keep cached
    }
    
    /* Significant change - assume content modification */
    LOG(log_debug, logtype_afpd,
        "dircache: significant change detected for \"%s\" (age=%lds, delta=%lds)",
        cfrombstr(cdir->d_u_name), (long)ctime_age, (long)ctime_delta);
    return 1;  // Invalidate
}

4.3 Time-based Heuristics for Directory Modifications

Directories require special handling because their ctime changes for many reasons that don't affect cached data:

• Metadata Window (default 300s): Changes within this recent window may be metadata-only
• Metadata Threshold (default 60s): Small ctime deltas under this are likely permission/xattr changes
• Smart ctime update: Update cached ctime for metadata changes to avoid repeated checks

4.4 New Configuration Parameters

// From include/atalk/globals.h
#define DEFAULT_DIRCACHE_VALIDATION_FREQ    5     /* Validate every Nth access */
#define DEFAULT_DIRCACHE_METADATA_WINDOW    300   /* Metadata change window (seconds) */
#define DEFAULT_DIRCACHE_METADATA_THRESHOLD 60    /* Metadata change threshold (seconds) */

Configuration in afp.conf:

[Global]
# How often to validate cached entries (1 = every access, 10 = every 10th access)
dircache validation freq = 5

# Time window for distinguishing metadata-only changes (seconds)
dircache metadata window = 300

# Maximum ctime delta to consider as metadata-only change (seconds)
dircache metadata threshold = 60

4.5 Performance Gains

Improvements already validated using proposed default settings with proof-of-concept stash (motivating this entire development plan):

• 80% reduction in stat() system calls
• 5x faster directory enumeration for cached entries
• Lower CPU usage due to fewer kernel transitions
• Better scalability - can handle 4x more concurrent connections

Configurable profiles:

Profile	Validation Freq	stat() Reduction	Use Case
High Performance	10	90%	Stable, read-heavy environments
Balanced (default)	5	80%	General file sharing
Conservative	2	50%	Frequently changing data
Legacy	1	0%	Compatibility/testing

5. Critical Design Principles

Internal vs External Change Handling

Internal Netatalk Operations:

• All AFP client operations (create, delete, rename, move)
• Always invalidate entries immediately through explicit dir_remove() calls
• No delay in cache invalidation
• Ensures immediate consistency for AFP clients

External Changes:

• Direct filesystem modifications
• Changes from other protocols (SMB, NFS, local)
• Detected periodically based on validation frequency
• Trade-off: Delayed detection for better performance

Different Handling for Files vs Directories

Files (Strict):

• Any ctime change triggers invalidation
• No heuristics applied
• Simple binary decision: changed or not

Directories (Smart Heuristics):

• Distinguish content changes from metadata changes
• Content changes (add/remove files): Invalidate
• Metadata changes (permissions, xattrs): Keep cached
• Subdirectory changes: Don't invalidate parent

Implementation Impact

This optimization transforms the directory cache from a minimal-benefit component into a high-performance acceleration layer:

• Before: Cache only saved object reconstruction, stat() on every access
• After: Cache eliminates 80% of filesystem I/O operations
• Result: Dramatically improved AFP server performance and scalability

The implementation maintains full backward compatibility through configuration options while providing substantial performance improvements for modern deployments.

[andylemin]

This has been implemented in #2447 along with fixing several bugs.

[rdmark]

A few comments after skimming through this!

The overall approach seems sound to me. I think it will be key to establish a current performance baseline and then validate the new behavior in an empirical fashion. Have you thought about how to simulate organic usage scenarios? You can only get so long with invariant tests. I'm a fan of fuzz testing!

And speaking of testing: love the idea of doing unit testing. The one C unit testing library I have hands-on experience with is libcheck. Do you have other suggestions?

Agreed that multi-threaded optimization is a very low priority right now, since netatalk isn't currently a threaded application.

Sections 6 and 7 have overlapping migration plans – which one is you aiming for right now?

[andylemin]

Thanks. This is why I have been working so hard on the lantest utility :)
The challenge is these changes are hard to prove with invariant testing as you say, hence the need for a solid plan..
Even the new cache stress tests can only do so much. I'll have a think about fuzz testing, that might work.
You might have noticed in #2447 I added more metrics to the dircache logs, which have proven very useful and provide direct evidence of cache efficiency.

Agree unit tests are great, especially considering the bugs I have found.. The challenge is it would take far more time than I have. It would require funding to make a real difference, and the unit tests need to be written alongside functional audits/rewrites otherwise you end up testing and validating existing bugs. But maybe we can do unit tests on new feature code.

Ahh, thanks for spotting the copy paste error.. I'll drop the section 7 plan, that was written before I did the ARC section plan..

[rdmark]

Right, I was thinking about applying unit testing sparingly and selectively, rather than attempting a rapid build-out of coverage. New feature code is a good candidate to add tests. And also the modular parts of the code such as libatalk.

Just creating a structure for testing and then adding the first test would be a huge win in my mind. The coverage can grow organically over time!

On fuzzing, I would love it if we could use a library that is ClusterFuzzLite compatible if at all possible. Haven't looked closer at the supported libraries yet to understand if this is feasible or fit for our purposes, but running fuzzing in the CI workflow seamlessly would be neat.

[andylemin]

Updated the migration plan 👍
Agree on the unit tests, I will look at implementing something for the new ARC code.
Have not played with ClusterFuzz, will have a look at this too.

[rdmark]

I created a skeleton ticket for the ARC cache feature: #2642

[andylemin]

This has now been fully implemented in #2668