router.c

#include <arpa/inet.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>

#include "lib.h"
#include "protocols.h"
#include "queue.h"

struct route_table_entry *rtable;
int rtable_len;

queue packet_queue;
struct arp_entry {
  uint32_t ip;
  uint8_t mac[6];
};
struct pending_packet {
  char packet[MAX_PACKET_LEN];
  size_t len;
  int interface;
  uint32_t next_hop_ip;
};

struct arp_entry arp_table[80000];
int arp_table_len = 0;

void add_arp_entry(uint32_t ip, uint8_t *mac) {
  arp_table[arp_table_len].ip = ip;
  memcpy(arp_table[arp_table_len].mac, mac, 6);
  arp_table_len++;
}

uint8_t *get_arp_mac(uint32_t ip) {
  int index = 0;
  for (index = 0; index < arp_table_len; index++) {
    if (arp_table[index].ip == ip) {
      return arp_table[index].mac;
    }
    index++;
  }
  return NULL;
}

// ARP request
void send_arp_request(uint32_t target_ip, int interface) {
  char arp_request[MAX_PACKET_LEN];
  struct ether_hdr *eth_hdr = (struct ether_hdr *)arp_request;
  struct arp_hdr *arp_hdr =
      (struct arp_hdr *)(arp_request + sizeof(struct ether_hdr));

  memset(eth_hdr->ethr_dhost, 0xFF, 6);
  get_interface_mac(interface, eth_hdr->ethr_shost);
  eth_hdr->ethr_type = htons(0x0806);

  arp_hdr->hw_type = htons(1);
  arp_hdr->proto_type = htons(0x0800);
  arp_hdr->hw_len = 6;
  arp_hdr->proto_len = 4;
  arp_hdr->opcode = htons(1);

  get_interface_mac(interface, arp_hdr->shwa);
  struct in_addr sender_ip;
  inet_aton(get_interface_ip(interface), &sender_ip);
  arp_hdr->sprotoa = sender_ip.s_addr;

  memset(arp_hdr->thwa, 0, 6);
  arp_hdr->tprotoa = target_ip;

  send_to_link(sizeof(struct ether_hdr) + sizeof(struct arp_hdr), arp_request,
               interface);
}

// ICMP Echo Reply
void send_icmp_echo_reply(struct icmp_hdr *icmp_hdr, struct ip_hdr *ip_hdr,
                          struct ether_hdr *eth_hdr, int interface,
                          char *packet, size_t len) {
  size_t optional_data_len = len - sizeof(struct ether_hdr) -
                             sizeof(struct ip_hdr) - sizeof(struct icmp_hdr);

  memcpy(eth_hdr->ethr_dhost, eth_hdr->ethr_shost, 6);
  get_interface_mac(interface, eth_hdr->ethr_shost);

  uint32_t ip_dst = ip_hdr->source_addr;
  ip_hdr->dest_addr = ip_dst;

  struct in_addr ip_addr;
  inet_aton(get_interface_ip(interface), &ip_addr);
  ip_hdr->source_addr = ip_addr.s_addr;

  ip_hdr->proto = IPPROTO_ICMP;
  ip_hdr->ttl = 64;
  ip_hdr->tot_len = htons(sizeof(struct ip_hdr) + sizeof(struct icmp_hdr) +
                          optional_data_len);

  ip_hdr->tos = 0;
  ip_hdr->frag = 0;
  ip_hdr->ver = 4;
  ip_hdr->ihl = 5;
  ip_hdr->id = 4;

  ip_hdr->checksum = 0;
  ip_hdr->checksum = htons(checksum((uint16_t *)ip_hdr, sizeof(struct ip_hdr)));

  icmp_hdr->mtype = 0;
  icmp_hdr->mcode = 0;
  icmp_hdr->check = 0;
  icmp_hdr->check = htons(checksum(
      (uint16_t *)icmp_hdr, sizeof(struct icmp_hdr) + optional_data_len));

  send_to_link(len, packet, interface);
}

// ICMP Time Exceeded
void send_icmp_time_exceeded(struct icmp_hdr *icmp_hdr, struct ip_hdr *ip_hdr,
                             struct ether_hdr *eth_hdr, int interface,
                             char *packet) {
  struct ip_hdr original_ip;
  memcpy(&original_ip, ip_hdr, sizeof(struct ip_hdr));

  memcpy(eth_hdr->ethr_dhost, eth_hdr->ethr_shost, 6);
  get_interface_mac(interface, eth_hdr->ethr_shost);

  struct in_addr ip_addr;
  inet_aton(get_interface_ip(interface), &ip_addr);
  ip_hdr->source_addr = ip_addr.s_addr;
  ip_hdr->dest_addr = original_ip.source_addr;
  ip_hdr->proto = IPPROTO_ICMP;
  ip_hdr->ttl = 64;
  ip_hdr->tot_len = htons(sizeof(struct ip_hdr) + sizeof(struct icmp_hdr) +
                          sizeof(struct ip_hdr) + 8);

  ip_hdr->tos = 0;
  ip_hdr->frag = 0;
  ip_hdr->ver = 4;
  ip_hdr->ihl = 5;
  ip_hdr->id = 4;
  ip_hdr->checksum = 0;
  ip_hdr->checksum = htons(checksum((uint16_t *)ip_hdr, ip_hdr->ihl * 4));

  icmp_hdr->mtype = 11;
  icmp_hdr->mcode = 0;
  icmp_hdr->un_t.frag_t.__unused = htons(0);
  icmp_hdr->un_t.frag_t.mtu = htons(0);
  icmp_hdr->check = 0;

  memcpy(packet + sizeof(struct ether_hdr) + sizeof(struct ip_hdr) +
             sizeof(struct icmp_hdr),
         &original_ip, sizeof(struct ip_hdr) + 8);

  icmp_hdr->check =
      htons(checksum((uint16_t *)icmp_hdr,
                     sizeof(struct icmp_hdr) + sizeof(struct ip_hdr) + 8));

  size_t packet_len = sizeof(struct ether_hdr) + sizeof(struct ip_hdr) +
                      sizeof(struct icmp_hdr) + sizeof(struct ip_hdr) + 8;

  send_to_link(packet_len, packet, interface);
}

// ICMP Destination Unreachable
void send_icmp_dest_unreach(struct icmp_hdr *icmp_hdr, struct ip_hdr *ip_hdr,
                            struct ether_hdr *eth_hdr, int interface,
                            char *packet) {
  struct ip_hdr original_ip;
  memcpy(&original_ip, ip_hdr, sizeof(struct ip_hdr));

  memcpy(eth_hdr->ethr_dhost, eth_hdr->ethr_shost, 6);
  get_interface_mac(interface, eth_hdr->ethr_shost);

  struct in_addr ip_addr;
  inet_aton(get_interface_ip(interface), &ip_addr);
  ip_hdr->source_addr = ip_addr.s_addr;
  ip_hdr->dest_addr = original_ip.source_addr;
  ip_hdr->proto = IPPROTO_ICMP;
  ip_hdr->ttl = 64;
  ip_hdr->tot_len = htons(sizeof(struct ip_hdr) + sizeof(struct icmp_hdr) +
                          sizeof(struct ip_hdr) + 8);

  ip_hdr->tos = 0;
  ip_hdr->frag = 0;
  ip_hdr->ver = 4;
  ip_hdr->ihl = 5;
  ip_hdr->id = 4;
  ip_hdr->checksum = 0;
  ip_hdr->checksum = htons(checksum((uint16_t *)ip_hdr, sizeof(struct ip_hdr)));

  icmp_hdr->mtype = 3;
  icmp_hdr->mcode = 0;
  icmp_hdr->un_t.frag_t.__unused = htons(0);
  icmp_hdr->un_t.frag_t.mtu = htons(0);
  icmp_hdr->check = 0;

  memcpy(packet + sizeof(struct ether_hdr) + sizeof(struct ip_hdr) +
             sizeof(struct icmp_hdr),
         &original_ip, sizeof(struct ip_hdr) + 8);

  icmp_hdr->check =
      htons(checksum((uint16_t *)icmp_hdr,
                     sizeof(struct icmp_hdr) + sizeof(struct ip_hdr) + 8));

  size_t packet_len = sizeof(struct ether_hdr) + sizeof(struct ip_hdr) +
                      sizeof(struct icmp_hdr) + sizeof(struct ip_hdr) + 8;

  send_to_link(packet_len, packet, interface);
}

struct trie_node {
  struct route_table_entry *route;
  struct trie_node *children[2];  // 0 si 1 pentru cei doi biti posibili
};

struct trie_node *create_node() {
  struct trie_node *node = calloc(1, sizeof(struct trie_node));
  return node;
}

void insert_route(struct trie_node *root, struct route_table_entry *route) {
  struct trie_node *current = root;
  uint32_t prefix = ntohl(route->prefix);
  uint32_t mask = ntohl(route->mask);
  int mask_bits = 0;
  uint32_t temp = mask;

  // Calculeaza numarul de biti in masca
  while (temp != 0) {
    if ((temp & 1) == 1) {
      mask_bits++;
    }
    temp = temp >> 1;
  }

  // Traverseaza trie-ul urmand bitii din prefix
  for (int i = 31; i > 31 - mask_bits; i--) {
    int bit = (prefix >> i) & 1;
    if (!current->children[bit]) {
      current->children[bit] = create_node();
    }
    current = current->children[bit];
  }

  current->route = route;
}

struct route_table_entry *get_best_route(struct trie_node *root, uint32_t ip) {
  struct trie_node *current = root;
  struct route_table_entry *best_route = NULL;
  uint32_t normalized_ip = ntohl(ip);

  // Traverseaza trie-ul urmand bitii din adresa IP
  for (int i = 31; i >= 0 && current; i--) {
    uint32_t mask = 1 << i;
    int bit = (normalized_ip & mask)
                  ? 1
                  : 0;  // luam bitul i pentru a gasi ruta din trie

    // Daca gasim o ruta, o salvam ca fiind cea mai buna pana acm
    if (current->route) {
      best_route = current->route;
    }

    current = current->children[bit];
  }

  // Verificam si ultimul nod
  if (current && current->route) {
    best_route = current->route;
  }

  return best_route;
}

// IP packet forwarding
void forward_ip_packet(char *buf, size_t len, int interface,
                       struct trie_node *root) {
  struct ether_hdr *ethhdr = (struct ether_hdr *)buf;
  struct ip_hdr *iphdr = (struct ip_hdr *)(buf + sizeof(struct ether_hdr));
  struct icmp_hdr *icmphdr =
      (struct icmp_hdr *)(buf + sizeof(struct ether_hdr) +
                          sizeof(struct ip_hdr));

  if (iphdr->ttl <= 1) {
    send_icmp_time_exceeded(icmphdr, iphdr, ethhdr, interface, buf);
    return;
  }
  if (iphdr->dest_addr == inet_addr(get_interface_ip(interface))) {
    if (iphdr->proto == IPPROTO_ICMP && icmphdr->mtype == 8) {
      send_icmp_echo_reply(icmphdr, iphdr, ethhdr, interface, buf, len);
      return;
    }
  }

  uint16_t original_checksum = ntohs(iphdr->checksum);
  iphdr->checksum = 0;
  if (checksum((uint16_t *)iphdr, sizeof(struct ip_hdr)) != original_checksum) {
    return;
  }

  struct route_table_entry *best_route = get_best_route(root, iphdr->dest_addr);
  if (best_route == NULL) {
    send_icmp_dest_unreach(icmphdr, iphdr, ethhdr, interface, buf);
    return;
  }
  iphdr->ttl--;
  iphdr->checksum = 0;
  iphdr->checksum = htons(checksum((uint16_t *)iphdr, sizeof(struct ip_hdr)));

  uint8_t *mac_dest = get_arp_mac(best_route->next_hop);

  if (mac_dest == NULL) {
    send_arp_request(best_route->next_hop, best_route->interface);
    //  Creeaza structura de pachet în asteptare
    struct pending_packet *pp = malloc(sizeof(struct pending_packet));
    memcpy(pp->packet, buf, len);
    pp->len = len;
    pp->interface = best_route->interface;
    pp->next_hop_ip = best_route->next_hop;

    queue_enq(packet_queue, pp);
    return;
  }

  memcpy(ethhdr->ethr_dhost, mac_dest, 6);
  get_interface_mac(best_route->interface, ethhdr->ethr_shost);

  send_to_link(len, buf, best_route->interface);
}

// ARP packet
void process_arp_packet(char *buf, size_t len, int interface) {
  struct ether_hdr *ethhdr = (struct ether_hdr *)buf;
  struct arp_hdr *arphdr = (struct arp_hdr *)(buf + sizeof(struct ether_hdr));

  if (ntohs(arphdr->opcode) == 1) {  // ARP Request
    struct in_addr target_ip;
    target_ip.s_addr = arphdr->tprotoa;

    for (int i = 0; i < ROUTER_NUM_INTERFACES; i++) {
      struct in_addr if_ip;
      inet_aton(get_interface_ip(i), &if_ip);

      if (if_ip.s_addr == target_ip.s_addr) {
        arphdr->opcode = htons(2);

        memcpy(arphdr->thwa, arphdr->shwa, 6);
        arphdr->tprotoa = arphdr->sprotoa;

        get_interface_mac(interface, arphdr->shwa);
        arphdr->sprotoa = if_ip.s_addr;

        memcpy(ethhdr->ethr_dhost, ethhdr->ethr_shost, 6);
        get_interface_mac(interface, ethhdr->ethr_shost);

        send_to_link(sizeof(struct ether_hdr) + sizeof(struct arp_hdr), buf,
                     interface);
        break;
      }
    }
  }
  if (ntohs(arphdr->opcode) == 2) {  // ARP reply
    add_arp_entry(arphdr->sprotoa, arphdr->shwa);

    // Trimite toate pachetele din coada care asteptau acest IP
    queue new_queue = create_queue();  // coada temporara

    while (!queue_empty(packet_queue)) {
      struct pending_packet *pp = queue_deq(packet_queue);
      if (pp->next_hop_ip == arphdr->sprotoa) {
        struct ether_hdr *ethhdr2 = (struct ether_hdr *)pp->packet;
        memcpy(ethhdr2->ethr_dhost, arphdr->shwa, 6);
        get_interface_mac(pp->interface, ethhdr2->ethr_shost);
        send_to_link(pp->len, pp->packet, pp->interface);

        free(pp);
      } else {
        queue_enq(new_queue, pp);
      }
    }
    while (!queue_empty(new_queue)) {
      struct pending_packet *aux = queue_deq(new_queue);
      queue_enq(packet_queue, aux);
    }
  }
}

int main(int argc, char *argv[]) {
  char buf[MAX_PACKET_LEN];
  // Do not modify this line
  init(argv + 2, argc - 2);

  rtable = malloc(sizeof(struct route_table_entry) * 100000);
  rtable_len = read_rtable(argv[1], rtable);

  struct trie_node *route_trie = create_node();
  packet_queue = create_queue();
  memset(arp_table, 0, sizeof(arp_table));
  // Popularea trie-ului cu datele din tabela de rutare
  for (int i = 0; i < rtable_len; i++) {
    insert_route(route_trie, &rtable[i]);
  }
  while (1) {
    size_t interface;
    size_t len;

    interface = recv_from_any_link(buf, &len);
    DIE(interface < 0, "recv_from_any_links");
    if (len < sizeof(struct ether_hdr)) {
      continue;
    }

    struct ether_hdr *ethhdr = (struct ether_hdr *)buf;
    uint8_t int_mac[6];
    get_interface_mac(interface, int_mac);

    if (memcmp(ethhdr->ethr_dhost, int_mac, 6) != 0 &&
        memcmp(ethhdr->ethr_dhost, "\xFF\xFF\xFF\xFF\xFF\xFF", 6) != 0) {
      continue;
    }

    if (ntohs(ethhdr->ethr_type) == 0x0800) {  // IPv4
      forward_ip_packet(buf, len, interface, route_trie);
    } else if (ntohs(ethhdr->ethr_type) == 0x0806) {  // ARP
      process_arp_packet(buf, len, interface);
    }
  }
  free(route_trie);
  free(rtable);
  return 0;
}