sr_arpcache.h

Go to the documentation of this file.

/**
 *  \file
 *  This file defines an ARP cache (\link sr_arpcache \endlink), which is made of two structures: an ARP
 *  request queue (\link sr_arpreq \endlink), and ARP cache entries (\link sr_arpentry \endlink). 
 *
 *  Here, we present pseudocode for use of these structures.
 *  \n
 *
 *  The outline for sending a packet using the ARP cache is as follows:
 *  \code{.cpp}
 *  // When sending packet to next_hop_ip
 *  entry = arpcache_lookup(next_hop_ip)
 *  if entry:
 *      use next_hop_ip->mac mapping in entry to send the packet
 *      free entry
 *  else:
 *      req = arpcache_queuereq(next_hop_ip, packet, len)
 *      handle_arpreq(req)
 *  \endcode
 *  \n
 *
 *  The handle_arpreq() function is a function you should write, and it should
 *  handle sending ARP requests if necessary:
 *  \code{.cpp}
 *  function handle_arpreq(req):
 *      if difftime(now, req->sent) > 1.0
 *          if req->times_sent >= 5:
 *              send icmp host unreachable to source addr of all pkts waiting
 *                on this request
 *              arpreq_destroy(req)
 *          else:
 *              send arp request
 *              req->sent = now
 *              req->times_sent++
 *  \endcode
 *  \n
 *
 *  The ARP reply processing code should move entries from the ARP request
 *  queue to the ARP cache:
 *  \code{.cpp}
 *  // When servicing an arp reply that gives us an IP->MAC mapping
 *  req = arpcache_insert(ip, mac)
 *  if req:
 *      send all packets on the req->packets linked list
 *      arpreq_destroy(req)
 *  \endcode
 *  \n
 *
 *  Since handle_arpreq as defined in the comments above could destroy your
 *  current request, make sure to save the next pointer before calling
 *  handle_arpreq when traversing through the ARP requests linked list.
 */

#ifndef SR_ARPCACHE_H
#define SR_ARPCACHE_H

#include <inttypes.h>
#include <time.h>
#include <pthread.h>
#include "sr_if.h"

#define SR_ARPCACHE_SZ    100
#define SR_ARPCACHE_TO    15.0

/** 
 * A packet queued, waiting for the resolution of an \link sr_arpreq \endlink.
 */
struct sr_packet {              
    uint8_t *buf;               /**< The raw Ethernet frame of the packet, presumably with the dest MAC empty */
    unsigned int len;           /**< Length of the raw ethernet frame */
    char *iface;                /**< The outgoing interface */
    struct sr_packet *next;     /**< A pointer to the next packet waiting on the same request.
                                 * NULL if there are no more packets. */
};

/**
 * An entry in the ARP cache.
 */
struct sr_arpentry {
    unsigned char mac[6];       /**< MAC address of the MAC/IP mapping. */
    uint32_t ip;                /**< IP addr in network byte order of the MAC/IP mapping. */
    time_t added;               /**< Time that the entry was added. 
                                  * The entry invalidated after SR_ARPCACHE_TO seconds. 
                                  * This is already tracked for you.*/
    int valid;                  /**< Boolean indicating whether or not the entry is valid. 
                                  * This is already tracked for you*/
};

/**
 * An outstanding ARP request with queued packets waiting on the response.
 */
struct sr_arpreq {
    uint32_t ip;                /**< The IP trying to be resolved by the request. */
    time_t sent;                /**< Last time this ARP request was sent. 
                                  * You should update this. If the ARP request
                                  * was never sent, will be 0. */
    uint32_t times_sent;        /**< Number of times this request was sent. 
                                  * You should update this. */
    struct sr_packet *packets;  /**< List of \link sr_packet \endlink waiting
                                  on this request to finish. */
    struct sr_arpreq *next;     /**< Pointer to the next outstanding ARP request.
                                  * NULL if there are no more in the linked list. */
};

/**
 * An ARP cache which tracks IP/MAC mappings, as well as outstanding ARP requests.
 */
struct sr_arpcache {
    struct sr_arpentry entries[SR_ARPCACHE_SZ]; /**< The list of cached IP/MAC mappings. */
    struct sr_arpreq *requests; /**< The linked list of outstanding ARP requests. */
    pthread_mutex_t lock; /**< A lock to ensure that the cache isn't
                            * concurrently modified by multiple threads,
                            * you shouldn't need to use this, the starter code
                            * handles it for you. */
    pthread_mutexattr_t attr; /**< Attributes for the mutex lock, you shouldn't
                                * need to use this, the starter code handles it
                                * for you. */
};

/**
 * Checks if an IP->MAC mapping is in the cache. IP is in network byte order.
 * You must free the returned structure if it is not NULL. 
 * */
struct sr_arpentry *sr_arpcache_lookup(struct sr_arpcache *cache, uint32_t ip);

/** Adds an ARP request to the ARP request queue. If the request is already on
   * the queue, adds the packet to the linked list of packets for this sr_arpreq
   * that corresponds to this ARP request. The packet argument should not be
   * freed by the caller.

   * A pointer to the ARP request is returned; it should be freed. The caller
   * can remove the ARP request from the queue by calling sr_arpreq_destroy. 
   */
struct sr_arpreq *sr_arpcache_queuereq(struct sr_arpcache *cache,
                         uint32_t ip,
                         uint8_t *packet,               /* borrowed */
                         unsigned int packet_len,
                         char *iface);

/** 
 * Inserts an ARP cache entry.
 * This method performs two functions:
 * 1) Looks up this IP in the request queue. If it is found, returns a pointer
 *    to the sr_arpreq with this IP. Otherwise, returns NULL.
 * 2) Inserts this IP to MAC mapping in the cache, and marks it valid. 
 * */
struct sr_arpreq *sr_arpcache_insert(struct sr_arpcache *cache,
                                     unsigned char *mac,
                                     uint32_t ip);

/** Frees all memory associated with this arp request entry. If this arp request
  * entry is on the arp request queue, it is removed from the queue. 
  * */
void sr_arpreq_destroy(struct sr_arpcache *cache, struct sr_arpreq *entry);

/** Prints out the ARP table. */
void sr_arpcache_dump(struct sr_arpcache *cache);

/* You shouldn't have to call these methods--they're already called in the
   starter code for you. The init call is a constructor, the destroy call is
   a destructor, and a cleanup thread times out cache entries every 15
   seconds. */

/** 
 * \link sr_arpcache \endlink constructor, you shouldn't need to call this, the
 * starter code calls it for you.
 * */
int   sr_arpcache_init(struct sr_arpcache *cache);

/**
 * \link sr_arpcache \endlink destructor, you shouldn't need to call this, the
 * starter code calls it for you.
 * */
int   sr_arpcache_destroy(struct sr_arpcache *cache);

/**
 * A cleanup command which clears out ARP cache entries every 15 seconds,
 * you shouldn't need to call this, it is called on a separte thread by
 * the starter code for you.
 * */
void *sr_arpcache_timeout(void *cache_ptr);

#endif