router.c

#include "protocols.h"
#include "queue.h"
#include "lib.h"
#include <arpa/inet.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ETHERTYPE_ARP 0x0806
#define ETHERTYPE_IP  0x0800

uint8_t BROADCAST_MAC[6] = {0xff, 0xff, 0xff, 0xff, 0xff, 0xff};

// Tabela de rutare
#define MAX_ROUTE_ENTRIES 100000
struct route_table_entry rtable[MAX_ROUTE_ENTRIES];
int rtable_size = 0;

// ARP Cache Dinamic 
#define MAX_DYNAMIC_ARP_ENTRIES 100
struct arp_table_entry dynamic_arp_cache[MAX_DYNAMIC_ARP_ENTRIES];
int dynamic_arp_cache_size = 0;

//Structuri pentru coada de așteptare ARP
struct waiting_packet {
    char *packet;     // copie a pachetului original
    size_t len;       
    int out_iface;    // interfața de ieșire
};

struct arp_pending_entry {
    uint32_t ip;      // urmatorul hop IP pentru care așteptăm rezoluția ARP
    queue waiting_packets;
};

#define MAX_PENDING_ENTRIES 100
struct arp_pending_entry pending_entries[MAX_PENDING_ENTRIES];
int pending_entries_size = 0;

// Trie pentru LPM
struct trie_node {
    struct route_table_entry *route;  // Pointer la intrarea de rutare validă
    struct trie_node *left;           // Pentru bit 0
    struct trie_node *right;          // Pentru bit 1
};

struct trie_node *create_trie_node() {
    struct trie_node *node = malloc(sizeof(struct trie_node));
    if (!node) {
        perror("malloc");
        exit(1);
    }
    node->route = NULL;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Calculează lungimea prefixului din mască
int prefix_length(uint32_t mask) {
    return __builtin_popcount(ntohl(mask));
}

// Inserează o intrare în trie pe baza prefixului
void trie_insert(struct trie_node *root, struct route_table_entry *route) {
    int plen = prefix_length(route->mask);
    uint32_t prefix_host = ntohl(route->prefix);
    struct trie_node *current = root;
    for (int i = 31; i >= 32 - plen; i--) {
        int bit = (prefix_host >> i) & 1;
        if (bit == 0) {
            if (current->left == NULL)
                current->left = create_trie_node();
            current = current->left;
        } else {
            if (current->right == NULL)
                current->right = create_trie_node();
            current = current->right;
        }
    }
    current->route = route;
}

// Căutare în trie pentru cel mai lung prefix care se potrivește cu dest_ip
struct route_table_entry *trie_search(struct trie_node *root, uint32_t dest_ip) {
    uint32_t ip_host = ntohl(dest_ip);
    struct trie_node *current = root;
    struct route_table_entry *best = NULL;
    for (int i = 31; i >= 0; i--) {
        if (current->route != NULL)
            best = current->route;
        int bit = (ip_host >> i) & 1;
        if (bit == 0) {
            if (current->left == NULL)
                break;
            current = current->left;
        } else {
            if (current->right == NULL)
                break;
            current = current->right;
        }
    }
    return best;
}

void free_trie(struct trie_node *root) {
    if (!root) return;
    free_trie(root->left);
    free_trie(root->right);
    free(root);
}

struct trie_node *trie_root = NULL;

// Construește și trimite un mesaj ICMP de eroare (Time Exceeded sau Destination Unreachable)
void send_icmp_error(uint8_t icmp_type, uint8_t icmp_code, char *orig_buf, size_t orig_len) {
    if (orig_len < sizeof(struct ether_hdr) + sizeof(struct ip_hdr))
        return;
    struct ip_hdr *orig_ip = (struct ip_hdr *)(orig_buf + sizeof(struct ether_hdr));
    int orig_ihl = orig_ip->ihl * 4;
    size_t appended_data_len = orig_ihl + 8;
    if (orig_len < sizeof(struct ether_hdr) + appended_data_len)
        appended_data_len = orig_len - sizeof(struct ether_hdr);
    size_t icmp_total_len = 8 + appended_data_len;
    size_t new_ip_total_len = sizeof(struct ip_hdr) + icmp_total_len;

    char err_buf[MAX_PACKET_LEN];
    memset(err_buf, 0, MAX_PACKET_LEN);

    struct ether_hdr *eth_err = (struct ether_hdr *)err_buf;
    struct ip_hdr *ip_err = (struct ip_hdr *)(err_buf + sizeof(struct ether_hdr));
    struct icmp_hdr *icmp_err = (struct icmp_hdr *)(err_buf + sizeof(struct ether_hdr) + sizeof(struct ip_hdr));

    ip_err->ver = 4;
    ip_err->ihl = 5;
    ip_err->tos = 0;
    ip_err->tot_len = htons(new_ip_total_len);
    ip_err->id = htons(0);
    ip_err->frag = 0;
    ip_err->ttl = 64;
    ip_err->proto = IPPROTO_ICMP;
    ip_err->dest_addr = orig_ip->source_addr;
    ip_err->checksum = 0;
    ip_err->checksum = htons(checksum((uint16_t *)ip_err, sizeof(struct ip_hdr)));

    icmp_err->mtype = icmp_type;
    icmp_err->mcode = icmp_code;
    icmp_err->check = 0;
    memset(&icmp_err->un_t, 0, 4);
    memcpy((char *)icmp_err + 8, orig_buf + sizeof(struct ether_hdr), appended_data_len);
    icmp_err->check = htons(checksum((uint16_t *)icmp_err, icmp_total_len));

    // Folosim trie-ul pentru a determina interfața de ieșire
    struct route_table_entry *route = trie_search(trie_root, ip_err->dest_addr);
    if (route == NULL)
        return;
    int out_iface = route->interface;
    char *iface_ip_str = get_interface_ip(out_iface);
    struct in_addr iface_in;
    inet_aton(iface_ip_str, &iface_in);
    ip_err->source_addr = iface_in.s_addr;
    ip_err->checksum = 0;
    ip_err->checksum = htons(checksum((uint16_t *)ip_err, sizeof(struct ip_hdr)));

    get_interface_mac(out_iface, eth_err->ethr_shost);
    uint32_t next_hop_ip = route->next_hop;
    if (next_hop_ip == 0)
        next_hop_ip = ip_err->dest_addr;
    uint8_t next_hop_mac[6];
    int found = 0;
    for (int i = 0; i < dynamic_arp_cache_size; i++) {
        if (dynamic_arp_cache[i].ip == next_hop_ip) {
            memcpy(next_hop_mac, dynamic_arp_cache[i].mac, 6);
            found = 1;
            break;
        }
    }
    if (!found)
        return;
    memcpy(eth_err->ethr_dhost, next_hop_mac, 6);
    eth_err->ethr_type = htons(ETHERTYPE_IP);

    size_t total_packet_len = sizeof(struct ether_hdr) + new_ip_total_len;
    send_to_link(total_packet_len, err_buf, out_iface);
}

// Procesează un ICMP Echo Request destinat routerului și trimite un Echo Reply
void process_icmp_echo_request(char *buf, size_t len, size_t recv_iface) {
    if (len < sizeof(struct ether_hdr) + sizeof(struct ip_hdr) + sizeof(struct icmp_hdr))
        return;
    struct ether_hdr *eth_hdr = (struct ether_hdr *)buf;
    struct ip_hdr *ip_hdr = (struct ip_hdr *)(buf + sizeof(struct ether_hdr));
    int ip_hdr_len = ip_hdr->ihl * 4;
    struct icmp_hdr *icmp_hdr = (struct icmp_hdr *)((char *)ip_hdr + ip_hdr_len);
    if (icmp_hdr->mtype != 8 || icmp_hdr->mcode != 0)
        return;

    char reply_buf[MAX_PACKET_LEN];
    memset(reply_buf, 0, MAX_PACKET_LEN);
    struct ether_hdr *eth_reply = (struct ether_hdr *)reply_buf;
    memcpy(eth_reply->ethr_dhost, eth_hdr->ethr_shost, 6);
    struct ip_hdr *ip_reply = (struct ip_hdr *)(reply_buf + sizeof(struct ether_hdr));
    ip_reply->ver = 4;
    ip_reply->ihl = 5;
    ip_reply->tos = 0;
    size_t payload_len = len - sizeof(struct ether_hdr) - ip_hdr_len;
    ip_reply->tot_len = htons(sizeof(struct ip_hdr) + payload_len);
    ip_reply->id = htons(0);
    ip_reply->frag = 0;
    ip_reply->ttl = 64;
    ip_reply->proto = IPPROTO_ICMP;
    ip_reply->source_addr = ip_hdr->dest_addr;
    ip_reply->dest_addr = ip_hdr->source_addr;
    ip_reply->checksum = 0;
    ip_reply->checksum = htons(checksum((uint16_t *)ip_reply, sizeof(struct ip_hdr)));

    struct icmp_hdr *icmp_reply = (struct icmp_hdr *)(reply_buf + sizeof(struct ether_hdr) + sizeof(struct ip_hdr));
    size_t icmp_data_len = payload_len;
    memcpy((char *)icmp_reply, (char *)icmp_hdr, icmp_data_len);
    icmp_reply->mtype = 0;
    icmp_reply->check = 0;
    icmp_reply->check = htons(checksum((uint16_t *)icmp_reply, icmp_data_len));

    struct route_table_entry *route = trie_search(trie_root, ip_reply->dest_addr);
    if (route == NULL)
        return;
    int out_iface = route->interface;
    get_interface_mac(out_iface, eth_reply->ethr_shost);
    uint32_t next_hop_ip = route->next_hop;
    if (next_hop_ip == 0)
        next_hop_ip = ip_reply->dest_addr;
    uint8_t next_hop_mac[6];
    int found = 0;
    for (int i = 0; i < dynamic_arp_cache_size; i++) {
        if (dynamic_arp_cache[i].ip == next_hop_ip) {
            memcpy(next_hop_mac, dynamic_arp_cache[i].mac, 6);
            found = 1;
            break;
        }
    }
    if (!found)
        return;
    memcpy(eth_reply->ethr_dhost, next_hop_mac, 6);
    eth_reply->ethr_type = htons(ETHERTYPE_IP);
    size_t total_packet_len = sizeof(struct ether_hdr) + ntohs(ip_reply->tot_len);
    send_to_link(total_packet_len, reply_buf, out_iface);
}

// La primirea unui ARP Reply, actualizează cache-ul dinamic și trimite pachetele din coadă
void process_arp_reply(char *buf, size_t len, size_t recv_iface) {
    if (len < sizeof(struct ether_hdr) + sizeof(struct arp_hdr))
        return;
    struct arp_hdr *arp_hdr = (struct arp_hdr *)(buf + sizeof(struct ether_hdr));
    uint16_t opcode = ntohs(arp_hdr->opcode);
    if (opcode != 2)
        return;
    uint32_t sender_ip = arp_hdr->sprotoa;
    int exists = 0;
    for (int i = 0; i < dynamic_arp_cache_size; i++) {
        if (dynamic_arp_cache[i].ip == sender_ip) {
            exists = 1;
            break;
        }
    }
    if (!exists && dynamic_arp_cache_size < MAX_DYNAMIC_ARP_ENTRIES) {
        dynamic_arp_cache[dynamic_arp_cache_size].ip = sender_ip;
        memcpy(dynamic_arp_cache[dynamic_arp_cache_size].mac, arp_hdr->shwa, 6);
        dynamic_arp_cache_size++;
    }
    for (int i = 0; i < pending_entries_size; i++) {
        if (pending_entries[i].ip == sender_ip) {
            while (!queue_empty(pending_entries[i].waiting_packets)) {
                struct waiting_packet *wp = queue_deq(pending_entries[i].waiting_packets);
                struct ether_hdr *eth_wait = (struct ether_hdr *)wp->packet;
                memcpy(eth_wait->ethr_dhost, arp_hdr->shwa, 6);
                get_interface_mac(wp->out_iface, eth_wait->ethr_shost);
                send_to_link(wp->len, wp->packet, wp->out_iface);
                free(wp->packet);
                free(wp);
            }
            pending_entries[i] = pending_entries[pending_entries_size - 1];
            pending_entries_size--;
            break;
        }
    }
}

int main(int argc, char *argv[])
{
    char buf[MAX_PACKET_LEN];
    init(argv + 2, argc - 2);

    // Încărcăm tabela de rutare
    rtable_size = read_rtable(argv[1], rtable);
    DIE(rtable_size < 0, "read_rtable");

    // Construim trie-ul pentru LPM
    trie_root = create_trie_node();
    for (int i = 0; i < rtable_size; i++) {
        trie_insert(trie_root, &rtable[i]);
    }

    // Inițializăm ARP cache dinamic și pending entries
    dynamic_arp_cache_size = 0;
    pending_entries_size = 0;

    while (1) {
        size_t interface;
        size_t len;
        interface = recv_from_any_link(buf, &len);
        DIE(interface < 0, "recv_from_any_link");

        if (len < sizeof(struct ether_hdr))
            continue;
        struct ether_hdr *eth_hdr = (struct ether_hdr *)buf;
        uint16_t ethertype = ntohs(eth_hdr->ethr_type);

        // Procesare ARP
        if (ethertype == ETHERTYPE_ARP) {
            struct arp_hdr *arp_hdr = (struct arp_hdr *)(buf + sizeof(struct ether_hdr));
            uint16_t opcode = ntohs(arp_hdr->opcode);
            if (opcode == 1) { // ARP Request
                char *iface_ip_str = get_interface_ip(interface);
                struct in_addr iface_ip;
                inet_aton(iface_ip_str, &iface_ip);
                if (iface_ip.s_addr == arp_hdr->tprotoa) {
                    char reply_buf[MAX_PACKET_LEN];
                    memset(reply_buf, 0, MAX_PACKET_LEN);
                    struct ether_hdr *eth_reply = (struct ether_hdr *)reply_buf;
                    memcpy(eth_reply->ethr_dhost, arp_hdr->shwa, 6);
                    get_interface_mac(interface, eth_reply->ethr_shost);
                    eth_reply->ethr_type = htons(ETHERTYPE_ARP);
                    struct arp_hdr *arp_reply = (struct arp_hdr *)(reply_buf + sizeof(struct ether_hdr));
                    arp_reply->hw_type = htons(1);
                    arp_reply->proto_type = htons(ETHERTYPE_IP);
                    arp_reply->hw_len = 6;
                    arp_reply->proto_len = 4;
                    arp_reply->opcode = htons(2);
                    get_interface_mac(interface, arp_reply->shwa);
                    inet_pton(AF_INET, iface_ip_str, &arp_reply->sprotoa);
                    memcpy(arp_reply->thwa, arp_hdr->shwa, 6);
                    arp_reply->tprotoa = arp_hdr->sprotoa;
                    send_to_link(sizeof(struct ether_hdr) + sizeof(struct arp_hdr), reply_buf, interface);
                }
            } else if (opcode == 2) { // ARP Reply
                process_arp_reply(buf, len, interface);
            }
            continue;
        }

        if (ethertype != ETHERTYPE_IP)
            continue;

        // Validare L2: pachetul trebuie să fie adresat routerului (sau broadcast)
        uint8_t iface_mac[6];
        get_interface_mac(interface, iface_mac);
        if (memcmp(eth_hdr->ethr_dhost, BROADCAST_MAC, 6) != 0 &&
            memcmp(eth_hdr->ethr_dhost, iface_mac, 6) != 0)
            continue;

        if (len < sizeof(struct ether_hdr) + sizeof(struct ip_hdr))
            continue;
        struct ip_hdr *ip_hdr = (struct ip_hdr *)(buf + sizeof(struct ether_hdr));
        
        // Verificare checksum IP: dacă header-ul IP nu este valid, ignorăm pachetul
        if (checksum((uint16_t *)ip_hdr, ip_hdr->ihl * 4) != 0)
            continue;

        // Verificăm dacă pachetul este destinat routerului
        int is_for_router = 0;
        for (int i = 0; i < ROUTER_NUM_INTERFACES; i++) {
            char *ip_str = get_interface_ip(i);
            struct in_addr intf_addr;
            inet_aton(ip_str, &intf_addr);
            if (intf_addr.s_addr == ip_hdr->dest_addr)
                is_for_router = 1;
        }
        if (is_for_router) {
            if (ip_hdr->proto == IPPROTO_ICMP)
                process_icmp_echo_request(buf, len, interface);
            continue;
        }

        // Forwarding
        struct route_table_entry *route = trie_search(trie_root, ip_hdr->dest_addr);
        if (route == NULL) {
            send_icmp_error(3, 0, buf, len);
            continue;
        }
        if (ip_hdr->ttl <= 1) {
            send_icmp_error(11, 0, buf, len);
            continue;
        }
        ip_hdr->ttl--;
        ip_hdr->checksum = 0;
        ip_hdr->checksum = htons(checksum((uint16_t *)ip_hdr, ip_hdr->ihl * 4));

        uint32_t next_hop_ip = route->next_hop;
        if (next_hop_ip == 0)
            next_hop_ip = ip_hdr->dest_addr;

        int found = 0;
        uint8_t next_hop_mac[6];
        for (int i = 0; i < dynamic_arp_cache_size; i++) {
            if (dynamic_arp_cache[i].ip == next_hop_ip) {
                memcpy(next_hop_mac, dynamic_arp_cache[i].mac, 6);
                found = 1;
                break;
            }
        }
        if (!found) {
            // Nu s-a găsit intrare în ARP cache, punem pachetul în coadă
            struct waiting_packet *wp = malloc(sizeof(struct waiting_packet));
            if (!wp) { perror("malloc"); exit(1); }
            wp->packet = malloc(len);
            if (!wp->packet) { perror("malloc"); exit(1); }
            memcpy(wp->packet, buf, len);
            wp->len = len;
            wp->out_iface = route->interface;

            int pending_found = 0;
            for (int i = 0; i < pending_entries_size; i++) {
                if (pending_entries[i].ip == next_hop_ip) {
                    queue_enq(pending_entries[i].waiting_packets, wp);
                    pending_found = 1;
                    break;
                }
            }
            if (!pending_found) {
                if (pending_entries_size < MAX_PENDING_ENTRIES) {
                    pending_entries[pending_entries_size].ip = next_hop_ip;
                    pending_entries[pending_entries_size].waiting_packets = create_queue();
                    queue_enq(pending_entries[pending_entries_size].waiting_packets, wp);
                    pending_entries_size++;
                } else {
                    free(wp->packet);
                    free(wp);
                }
                // Generăm ARP request
                char arp_req_buf[MAX_PACKET_LEN];
                memset(arp_req_buf, 0, MAX_PACKET_LEN);
                struct ether_hdr *eth_req = (struct ether_hdr *)arp_req_buf;
                memcpy(eth_req->ethr_dhost, BROADCAST_MAC, 6);
                get_interface_mac(route->interface, eth_req->ethr_shost);
                eth_req->ethr_type = htons(ETHERTYPE_ARP);
                struct arp_hdr *arp_req = (struct arp_hdr *)(arp_req_buf + sizeof(struct ether_hdr));
                arp_req->hw_type = htons(1);
                arp_req->proto_type = htons(ETHERTYPE_IP);
                arp_req->hw_len = 6;
                arp_req->proto_len = 4;
                arp_req->opcode = htons(1); // ARP request
                get_interface_mac(route->interface, arp_req->shwa);
                char *iface_ip_str = get_interface_ip(route->interface);
                inet_pton(AF_INET, iface_ip_str, &arp_req->sprotoa);
                memset(arp_req->thwa, 0, 6);
                arp_req->tprotoa = next_hop_ip;
                send_to_link(sizeof(struct ether_hdr) + sizeof(struct arp_hdr), arp_req_buf, route->interface);
            }
            continue;
        }
        get_interface_mac(route->interface, eth_hdr->ethr_shost);
        memcpy(eth_hdr->ethr_dhost, next_hop_mac, 6);
        send_to_link(len, buf, route->interface);
    }

    free_trie(trie_root);
    return 0;
}