Implementing an ARP Cache with Queuing and Timeout Logic in C

Purpose

The MAC Address Chicken-and-Egg Dilemma

You’re building a network router. A packet arrives destined for 192.168.2.2. Your routing table says “forward it out interface eth1.” Simple, right?

Wrong. Ethernet requires a MAC address to actually send the frame. You have an IP address but no MAC address. You need to:

1. Ask “Who has 192.168.2.2?” via ARP broadcast
2. Wait for the reply (which might take milliseconds… or never arrive)
3. Meanwhile, 10 more packets arrive for the same destination

Do you:

• Drop all packets until ARP resolves? (Terrible performance)
• Send 10 duplicate ARP requests? (Wasteful)
• Queue packets and risk memory exhaustion? (Crash hazard)

A Stateful ARP Cache with Request Queue Management

The sr_arpcache.c module solves this with a request queue data structure that:

• Deduplicates ARP requests (one request per destination IP)
• Queues packets waiting for resolution
• Retries failed requests with exponential backoff
• Sends ICMP errors when resolution fails after timeout

The Constraint Triangle

This isn’t just “store IP→MAC mappings.” We’re handling:

1. Concurrency: A background thread sweeps the cache every second while packet handlers query it
2. Memory Safety: Manual allocation/deallocation in C without leaking
3. Network Protocol Semantics: RFC-compliant retry logic and failure modes

Prerequisites & Tooling

Knowledge Base

• Required:

  • C fundamentals (pointers, structs, malloc/free)
  • Basic networking (what an IP/MAC address is)
  • Linked list data structures

• Helpful:

  • Mutex/pthread basics
  • Understanding of time-based state machines

Environment

From the project’s Makefile:

# Compiler: GCC with pthread support
gcc --version  # 9.4.0+ recommended

# Build the router
cd router
make clean && make

# Dependencies (from Dockerfile)
sudo apt-get install build-essential

Key Headers Used:

#include <pthread.h>      // Mutexes for thread safety
#include <time.h>         // Timestamps for timeout logic
#include <netinet/in.h>   // Network byte order (htonl, etc.)

High-Level Architecture

State Machine Diagram

stateDiagram-v2
    [*] --> CacheMiss: Packet arrives
    CacheMiss --> QueuePacket: No MAC found
    QueuePacket --> SendARPRequest: First packet for this IP
    QueuePacket --> AppendToQueue: Subsequent packets
    SendARPRequest --> WaitingForReply: Set sent_time
    WaitingForReply --> Resolved: ARP Reply arrives
    WaitingForReply --> RetryRequest: 1s timeout (< 5 retries)
    WaitingForReply --> SendICMPError: 5s total timeout
    Resolved --> ForwardAllQueued: Dequeue packets
    ForwardAllQueued --> [*]
    SendICMPError --> DestroyRequest: Cleanup
    DestroyRequest --> [*]

The Restaurant

Imagine a busy restaurant kitchen:

• Cache entries = Regular customers with known table numbers
• ARP requests = New walk-ins waiting for a table assignment
• Packet queue = Orders taken while waiting (you don’t throw away their appetizer order just because they don’t have a table yet!)
• Sweep thread = The host checking every minute: “Has table 5 been assigned yet? Did guest X give up and leave?”

When table 5 is finally assigned (ARP reply arrives), the host rushes all queued orders for that guest to the kitchen.

Implementation

Data Structures

Goal: Understand how we represent cache state in memory.

// From sr_arpcache.h

/* Cached ARP entry: Resolved IP→MAC mapping */
struct sr_arpentry {
    unsigned char mac[6];       // Ethernet hardware address
    uint32_t ip;                // IP address (network byte order)
    time_t added;               // Timestamp when entry was added
    int valid;                  // 1 if entry is valid, 0 if expired
};

/* Packet waiting in queue */
struct sr_packet {
    uint8_t *buf;               // Full Ethernet frame (malloc'd)
    unsigned int len;           // Frame length in bytes
    char *iface;                // Output interface name (e.g., "eth1")
    struct sr_packet *next;     // Linked list pointer
};

/* ARP request waiting for reply */
struct sr_arpreq {
    uint32_t ip;                // Destination IP we're asking about
    time_t sent;                // Time of last ARP request sent
    uint32_t times_sent;        // Retry counter
    struct sr_packet *packets;  // Linked list of queued packets
    struct sr_arpreq *next;     // Linked list pointer
};

/* The cache itself */
struct sr_arpcache {
    struct sr_arpentry entries[SR_ARPCACHE_SZ];  // Fixed-size array (100 entries)
    struct sr_arpreq *requests;                   // Linked list of pending requests
    pthread_mutex_t lock;                         // Protects concurrent access
    pthread_t thread;                             // Background sweep thread
};

🔵 Deep Dive: Why Array for Entries, Linked List for Requests?

Entries (resolved mappings):

• Bounded size (max 100 neighbors in this simple topology)
• Frequent random access (“do I have MAC for 10.0.1.2?”)
• Array provides O(1) lookup vs. O(n) for linked lists

Requests (unresolved pending):

• Unbounded (attacker could send packets to 1000 nonexistent IPs)
• Mostly sequential access (sweep thread walks all requests)
• Linked list allows dynamic growth without reallocation

Looking Up an Entry

Goal: Check if we have a cached MAC for a given IP.

struct sr_arpentry *sr_arpcache_lookup(struct sr_arpcache *cache, uint32_t ip) {
    pthread_mutex_lock(&(cache->lock));  // CRITICAL SECTION START
    
    struct sr_arpentry *entry = NULL;
    
    for (int i = 0; i < SR_ARPCACHE_SZ; i++) {
        // Check if entry is valid AND matches target IP
        if ((cache->entries[i].valid) && 
            (cache->entries[i].ip == ip)) {
            
            // Allocate a COPY (caller must free!)
            entry = (struct sr_arpentry *) malloc(sizeof(struct sr_arpentry));
            memcpy(entry, &(cache->entries[i]), sizeof(struct sr_arpentry));
            break;
        }
    }
    
    pthread_mutex_unlock(&(cache->lock));  // CRITICAL SECTION END
    return entry;  // NULL if not found
}

🔴 Danger: Memory Ownership Transfer

Notice we return a heap-allocated copy, not a pointer to the cache entry itself. Why?

Bad (Race Condition):

// WRONG: Caller holds pointer to cache entry
struct sr_arpentry *entry = &cache->entries[i];
pthread_mutex_unlock(&lock);
// Another thread could invalidate entry here!
send_packet(entry->mac);  // Use-after-free bug!

Good (Current Implementation):

// Caller owns a private copy
struct sr_arpentry *entry = malloc(...);
pthread_mutex_unlock(&lock);
send_packet(entry->mac);  // Safe: our data
free(entry);  // Caller's responsibility

Queueing a Packet

Goal: Add packet to waiting queue, creating request if needed.

struct sr_arpreq *sr_arpcache_queuereq(struct sr_arpcache *cache,
                                        uint32_t ip,
                                        uint8_t *packet,
                                        unsigned int packet_len,
                                        char *iface)
{
    pthread_mutex_lock(&(cache->lock));
    
    // Search for existing request for this IP
    struct sr_arpreq *req = cache->requests;
    for (; req != NULL; req = req->next) {
        if (req->ip == ip) {
            break;  // Found existing request!
        }
    }
    
    // No existing request? Create a new one
    if (req == NULL) {
        req = (struct sr_arpreq *) calloc(1, sizeof(struct sr_arpreq));
        req->ip = ip;
        req->times_sent = 0;
        req->sent = time(NULL);  // Current timestamp
        req->packets = NULL;
        
        // Prepend to linked list
        req->next = cache->requests;
        cache->requests = req;
    }
    
    // Append this packet to the request's queue
    struct sr_packet *new_pkt = (struct sr_packet *) malloc(sizeof(struct sr_packet));
    new_pkt->buf = (uint8_t *) malloc(packet_len);
    memcpy(new_pkt->buf, packet, packet_len);  // Deep copy of packet data
    new_pkt->len = packet_len;
    new_pkt->iface = (char *) malloc(strlen(iface) + 1);
    strcpy(new_pkt->iface, iface);
    new_pkt->next = req->packets;  // Prepend to list
    req->packets = new_pkt;
    
    pthread_mutex_unlock(&(cache->lock));
    return req;
}

The Key Insight: Before creating a new ARP request, we search for an existing one with the same IP. This deduplication means:

• 100 packets to 192.168.2.2 → 1 ARP request
• Reduces broadcast storm risk
• Simplifies timeout logic (one timer per IP, not per packet)

Inserting a MAC Mapping

Naive Approach (Missing Functionality):

// INCOMPLETE: Just store the MAC
void add_to_cache(struct sr_arpcache *cache, uint32_t ip, unsigned char *mac) {
    cache->entries[0].ip = ip;
    memcpy(cache->entries[0].mac, mac, 6);
    cache->entries[0].valid = 1;
    // BUG: What about the queued packets waiting for this IP?!
}

Refined Solution (From Repo):

struct sr_arpreq *sr_arpcache_insert(struct sr_arpcache *cache,
                                      unsigned char *mac,
                                      uint32_t ip)
{
    pthread_mutex_lock(&(cache->lock));
    
    // Find empty slot in cache array
    int i = 0;
    for (; i < SR_ARPCACHE_SZ; i++) {
        if (!(cache->entries[i].valid)) {
            break;
        }
    }
    
    // Cache full? Evict oldest entry (LRU approximation)
    if (i == SR_ARPCACHE_SZ) {
        time_t oldest = cache->entries[0].added;
        int oldest_idx = 0;
        for (int j = 1; j < SR_ARPCACHE_SZ; j++) {
            if (cache->entries[j].added < oldest) {
                oldest = cache->entries[j].added;
                oldest_idx = j;
            }
        }
        i = oldest_idx;
    }
    
    // Insert the new entry
    memcpy(cache->entries[i].mac, mac, 6);
    cache->entries[i].ip = ip;
    cache->entries[i].added = time(NULL);
    cache->entries[i].valid = 1;
    
    // CRITICAL: Find and return the corresponding request (if it exists)
    struct sr_arpreq *req = cache->requests, *prev = NULL;
    for (; req != NULL; prev = req, req = req->next) {
        if (req->ip == ip) {
            // Remove from requests list
            if (prev) {
                prev->next = req->next;
            } else {
                cache->requests = req->next;
            }
            break;
        }
    }
    
    pthread_mutex_unlock(&(cache->lock));
    return req;  // Caller must forward queued packets and free this!
}

Why Return the Request?

The caller needs to:

1. Iterate through req->packets
2. Rewrite each packet’s destination MAC (now known!)
3. Send all queued packets
4. Free the request structure

This separation of concerns keeps the cache module focused on state management, while the router module handles packet forwarding logic.

The Sweep Thread

Goal: Every second, check all pending requests for timeouts.

void handle_arpreq(struct sr_instance *sr, struct sr_arpreq* req) {
    time_t now = time(NULL);
    
    // Has it been >= 1 second since last ARP request?
    if (difftime(now, req->sent) >= 1.0) {
        
        if (req->times_sent >= 5) {
            // TIMEOUT: Send ICMP Host Unreachable for all queued packets
            struct sr_packet *pkt = req->packets;
            while (pkt) {
                // Extract original packet's source IP
                sr_ip_hdr_t *ip_hdr = (sr_ip_hdr_t *)(pkt->buf + sizeof(sr_ethernet_hdr_t));
                
                // Send ICMP type 3 (Destination Unreachable), code 1 (Host Unreachable)
                send_icmp_error_message(sr, pkt->iface, ip_hdr->ip_id, 
                                        (uint8_t*)ip_hdr, 
                                        ip_hdr->ip_src, 
                                        ICMP_DEST_UNREACHABLE);
                pkt = pkt->next;
            }
            
            // Destroy the request (frees all queued packets)
            sr_arpreq_destroy(&(sr->cache), req);
            
        } else {
            // RETRY: Send another ARP request
            send_arp_request(sr, req->ip);
            req->sent = now;
            req->times_sent++;
        }
    }
}

void sr_arpcache_sweepreqs(struct sr_instance *sr) {
    struct sr_arpreq *req = sr->cache.requests;
    
    while (req) {
        struct sr_arpreq *next = req->next;  // Save next before possible destruction
        handle_arpreq(sr, req);
        req = next;
    }
}

The State Machine in Action:

This implements exponential backoff (conceptually—each retry waits 1s) while capping total wait time.

Under the Hood

Memory Layout: Cache vs. Heap Allocations

Cache Entries (Stack-ish):

struct sr_arpcache cache;
cache.entries[0...99]  →  Allocated once at init, fixed 6.4KB
                          (100 entries × 64 bytes each)

• Lives in the router’s data segment (global)
• No fragmentation risk
• Cache-friendly (contiguous memory)

Pending Requests (Heap):

cache.requests → [req1] → [req2] → [req3] → NULL
                    ↓        ↓        ↓
                  pkts     pkts     pkts
                    ↓        ↓        ↓
                  [p1]→[p2] [p1]    [p1]→[p2]→[p3]

• Each malloc() call fragments heap slightly
• Worst case: 1000 fake IPs × 100 queued packets = 100K allocations
• Defense: Limit queue depth (production systems cap at 5-10 packets per request)

Thread Safety: The Lock Granularity Question

Current Implementation (Coarse-Grained):

pthread_mutex_lock(&cache->lock);
// Entire cache locked
for (int i = 0; i < 100; i++) { ... }
pthread_mutex_unlock(&cache->lock);

Alternative (Fine-Grained):

// Lock per cache entry?
for (int i = 0; i < 100; i++) {
    pthread_mutex_lock(&cache->entries[i].lock);
    if (cache->entries[i].ip == target_ip) { ... }
    pthread_mutex_unlock(&cache->entries[i].lock);
}

Why Coarse Wins Here:

1. Cache operations are fast (~100 array comparisons takes < 1μs)
2. Fine-grained locking adds overhead (100 lock/unlock pairs)
3. Contention is low (one sweep thread + occasional packet lookups)

Rule of thumb: Use fine-grained locks when critical sections are long (>10ms) or contentious (100+ threads).

Big-O Analysis

Optimization Opportunity: Replace the requests linked list with a hash table keyed by IP for O(1) queueing.

Edge Cases & Pitfalls

ARP Spoofing Attack

Scenario: Attacker sends fake ARP reply: “192.168.2.2 is at DE:AD:BE:EF:00:00”

Current Code Vulnerability:

// No validation of ARP sender!
sr_arpcache_insert(cache, arp_reply->ar_sha, arp_reply->ar_sip);

Defense (Not Implemented):

// Only accept replies for IPs we actually requested
if (arp_reply->ar_sip != req->ip) {
    return;  // Ignore unsolicited replies
}

Memory Leak on Cache Overflow

Scenario:

1. Cache fills with 100 entries
2. New ARP reply arrives for IP 10.0.1.2
3. LRU eviction runs
4. But what if queued packets referenced the old MAC?

Not a Problem Here Because: The code evicts cache entries (resolved mappings), not requests (pending). By the time we’re inserting a new MAC, the old request has already been destroyed (its packets were forwarded or timed out).

But Watch For: If you add negative caching (remembering “IP X doesn’t exist”), ensure you expire those too.

The Thundering Herd

Scenario:

1. 1000 packets arrive for 192.168.2.99 (nonexistent host)
2. All get queued
3. After 5s timeout, we send 1000 ICMP errors simultaneously
4. Outbound link gets flooded

Defense (Production Routers):

// Rate-limit ICMP generation
if (icmp_sent_this_second > 100) {
    drop_silently();
}

RFC 1812 Section 4.3.2.8 requires rate-limiting ICMP to prevent amplification attacks.

Conclusion

Skills Acquired

You’ve learned:

1. Data Structure Design: When to use arrays vs. linked lists based on access patterns
2. Thread Safety: Coarse vs. fine-grained locking tradeoffs
3. State Machine Implementation: Time-based retries with timeout handling
4. Memory Management: Deep copies, ownership transfer, preventing leaks
5. Protocol Correctness: Implementing RFC-compliant ARP behavior

The Proficiency Marker: Most networking tutorials show “send ARP request, get reply, done.” You’ve implemented production-grade queuing logic that handles failures, retries, and resource limits—the same patterns used in Linux’s ARP stack, BSD’s routing code, and Cisco IOS.

Next Challenge: Implement ARP announcement on interface up (gratuitous ARP) or proxy ARP for transparent NAT scenarios.