Router working finally

10 files changed, 295 insertions, 86 deletions

diff --git a/Semestr 4/sieci/pracownia2/router/config.h b/Semestr 4/sieci/pracownia2/router/config.h
index 3537c03..ef8bf47 100644
--- a/Semestr 4/sieci/pracownia2/router/config.h
+++ b/Semestr 4/sieci/pracownia2/router/config.h
@@ -3,6 +3,12 @@
 
 #define SERVER_PORT 54321
 #define TURN_LEN_S 5
+
+#define INFINITY_DIST 16
+#define REACHABILITY_WAIT_TIME 5
+
+#define DV_DATAGRAM_LEN 9
+
 #define TURN_LEN_MS (1000 * TURN_LEN_S)
 #define TURN_LEN_US (1000000 * TURN_LEN_S)
 
diff --git a/Semestr 4/sieci/pracownia2/router/dist_vector.c b/Semestr 4/sieci/pracownia2/router/dist_vector.c
index 1e09bff..f1c8c67 100644
--- a/Semestr 4/sieci/pracownia2/router/dist_vector.c
+++ b/Semestr 4/sieci/pracownia2/router/dist_vector.c
@@ -1,8 +1,101 @@
 #include "dist_vector.h"
+#include <stdio.h>
 
 bool is_connected_directly(struct vector_item item) {
-  return (get_network_address(item.network).s_addr == 
-    get_network_address(item.via_ip).s_addr);
+  return item.is_connected_directly;
 }
 
-void update_distance_vector(list_t *distance_vector, struct vector_item new_item) {}
\ No newline at end of file
+bool is_reachable(struct vector_item item) {
+  return (item.distance < INFINITY_DIST);
+}
+
+void init_dv(list_t *dv, int n_cnt, struct network_addr *neighbours) {
+  for (int i = 0; i < n_cnt; i++) {
+    struct vector_item new_item;
+    new_item.network = neighbours[i];
+    new_item.distance = INFINITY_DIST;
+    new_item.is_connected_directly = true;
+    insert(dv, &new_item, sizeof(new_item));
+  }
+}
+
+void update_dv_reachability(list_t *distance_vector) {
+  reset(distance_vector);
+  while (distance_vector->it != NULL) {
+    struct vector_item *current = (struct vector_item *)distance_vector->it->data;
+    if(++current->reachable > REACHABILITY_WAIT_TIME) {
+      if (current->distance >= INFINITY_DIST) {
+        if (!is_connected_directly(*current)) {
+          erase_it(distance_vector);
+        }
+      } else {
+        current->distance = INFINITY_DIST;
+        current->reachable = 0;
+      }
+    }
+    iterate(distance_vector);
+  }
+}
+
+void update_dv_new_item(list_t *distance_vector, struct vector_item new_item) {
+  bool new_entry = true;
+  reset(distance_vector);
+  while (distance_vector->it != NULL) {
+    struct vector_item *current = (struct vector_item *)distance_vector->it->data;
+
+    /* If the network is already in the distance vector, then we possibly want to change it:
+     *  - if the new item has better distance than the previous one, then we just want to change it no matter what,
+     *  - if the new item has the same via ip, then we want to check two things:
+     *     - if new item has infinity dist, then we want to set infinity (if it wasn't set, then we want to change reachable to 0)
+     *     - if new item has < inf dist, then we want to change reachable to 0 and set our dist accordingly.
+     *  - else we ignore the entry.
+     */
+    if (get_network_address(current->network).s_addr == get_network_address(new_item.network).s_addr) {
+      if (current->distance > new_item.distance) {
+        *current = new_item;
+        current->reachable = 0;
+      } else if(current->via_ip.s_addr == new_item.via_ip.s_addr) {
+        if (new_item.distance >= INFINITY_DIST) {
+          if (current->distance < INFINITY_DIST) {
+            current->distance = INFINITY_DIST;
+            current->reachable = 0;
+          }
+        } else if (new_item.distance < INFINITY_DIST) {
+          if (current->distance >= INFINITY_DIST) {
+            current->distance = new_item.distance;
+          }
+          current->reachable = 0;
+        }
+      }
+      new_entry = false;
+    }
+
+    iterate(distance_vector);
+  }
+
+  if (new_entry) {
+    insert(distance_vector, &new_item, sizeof(new_item));
+  }
+}
+
+void print_dv(list_t *distance_vector) {
+  printf("Distance vector:\n");
+  reset(distance_vector);
+  while (distance_vector->it != NULL) {
+    char addr[20], via_addr[20];
+    struct vector_item current  = *(struct vector_item *)distance_vector->it->data;
+    struct in_addr net_addr     = get_network_address(current.network);
+    inet_ntop(AF_INET, &net_addr, addr, sizeof(addr));
+    printf("%s/%d ", addr, current.network.netmask);
+    
+    if (is_reachable(current))          printf("distance %d ", current.distance);
+    else                                printf("unreachable ");
+
+    inet_ntop(AF_INET, &current.via_ip, via_addr, sizeof(via_addr));
+    if (is_connected_directly(current)) printf("connected directly\n");
+    else                                printf("via %s\n", via_addr);
+
+    iterate(distance_vector);
+  }
+  printf("\n");
+}
\ No newline at end of file
diff --git a/Semestr 4/sieci/pracownia2/router/dist_vector.h b/Semestr 4/sieci/pracownia2/router/dist_vector.h
index cd1a995..14159b4 100644
--- a/Semestr 4/sieci/pracownia2/router/dist_vector.h
+++ b/Semestr 4/sieci/pracownia2/router/dist_vector.h
@@ -3,6 +3,7 @@
 
 #include "linked_list.h"
 #include "network_addr.h"
+#include "config.h"
 
 /* Item of the distance vector. 
  * If <<reachable>> is set to 0, then it means that the network is reachable.
@@ -11,14 +12,25 @@
  */
 struct vector_item {
   struct network_addr network;
-  router_addr         via_ip;
+  struct in_addr      via_ip;
+  uint16_t            distance;
   uint8_t             reachable;
+  bool                is_connected_directly;
 };
 
-/* Returns true if given distance vector item is connected directly, false otherwise */
+/* Initis distance vector with given neighbours array. */
+void init_dv(list_t *dv, int n_cnt, struct network_addr *neighbours);
+
+/* Returns true if given distance vector item is connected directly, false otherwise. */
 bool is_connected_directly(struct vector_item item);
 
 /* Updates the distance vector. */
-void update_distance_vector(list_t *distance_vector, struct vector_item new_item);
+void update_dv_new_item(list_t *distance_vector, struct vector_item new_item);
+
+/* Updates reachabilities. */
+void update_dv_reachability(list_t *distance_vector);
+
+/* Print distance vector. */
+void print_dv(list_t *distance_vector);
 
 #endif
\ No newline at end of file
diff --git a/Semestr 4/sieci/pracownia2/router/linked_list.c b/Semestr 4/sieci/pracownia2/router/linked_list.c
index f3bccc9..09f6025 100644
--- a/Semestr 4/sieci/pracownia2/router/linked_list.c
+++ b/Semestr 4/sieci/pracownia2/router/linked_list.c
@@ -8,10 +8,7 @@ node_t *_next(node_t *node) {
 
 void _insert(node_t **head, void *data, size_t data_size) {
   node_t *new_node = (node_t *)malloc(sizeof(node_t));
-  new_node->data = malloc(data_size);
-  for (int i = 0; i < data_size; i++)
-    *(uint8_t *)(new_node->data + i) = *(uint8_t *)(data + i);
-  
+  new_node->data = malloc(data_size);  
   new_node->next = *head;
   *head = new_node;
 }
diff --git a/Semestr 4/sieci/pracownia2/router/linked_list.h b/Semestr 4/sieci/pracownia2/router/linked_list.h
index 28e8ef7..1574b2f 100644
--- a/Semestr 4/sieci/pracownia2/router/linked_list.h
+++ b/Semestr 4/sieci/pracownia2/router/linked_list.h
@@ -15,7 +15,7 @@ typedef struct list_t {
   node_t *prev_it;
 } list_t;
 
-/* Creates an empty list */
+/* Creates an empty list. */
 list_t create_list();
 
 /* Insert a new node in the begining of a list. */
diff --git a/Semestr 4/sieci/pracownia2/router/network_addr.c b/Semestr 4/sieci/pracownia2/router/network_addr.c
index a65f48c..d1982c2 100644
--- a/Semestr 4/sieci/pracownia2/router/network_addr.c
+++ b/Semestr 4/sieci/pracownia2/router/network_addr.c
@@ -5,21 +5,31 @@
 
 struct in_addr _get_broadcast_address(struct in_addr addr, uint16_t netmask) {
   struct in_addr result = addr;
+  result.s_addr = ntohl(result.s_addr);
   /* bitshift by more than 31 is UB */
-  if (netmask < 32) {
-    result.s_addr |= ~((1<<netmask) - 1);
+  if (netmask == 0) {
+    result.s_addr = -1;
+  }
+  else {
+    result.s_addr |= ((1 << (32 - netmask)) - 1);
   }
+  result.s_addr = htonl(result.s_addr);
+
   return result;
 }
 
 struct in_addr _get_network_address(struct in_addr addr, uint16_t netmask) {
   struct in_addr result = addr;
+  result.s_addr = ntohl(result.s_addr);
+
   if (netmask == 0) {
-    addr.s_addr = 0;
+    result.s_addr = 0;
   }
   else {
     result.s_addr &= ~((1 << (32 - netmask)) - 1);
   }
+  result.s_addr = htonl(result.s_addr);
+
   return result;
 }
 
@@ -31,13 +41,13 @@ struct in_addr get_network_address(struct network_addr na) {
   return _get_network_address(na.addr, na.netmask);
 }
 
-void pretty_print(struct network_addr na) {
+void pretty_print_network(struct network_addr na) {
   char ip_addr[20];
   inet_ntop(AF_INET, &na.addr, ip_addr, sizeof(ip_addr));
-  printf("%s/%d distance %d\n", ip_addr, na.netmask, na.distance);
+  printf("%s/%d\n", ip_addr, na.netmask);
 }
 
-struct network_addr stora(char *str) {
+struct network_addr stona(char *str) {
   struct network_addr  result;
   char                addr[20];
   size_t              ip_preffix = strcspn(str, "/");
diff --git a/Semestr 4/sieci/pracownia2/router/network_addr.h b/Semestr 4/sieci/pracownia2/router/network_addr.h
index 2067e05..616c64f 100644
--- a/Semestr 4/sieci/pracownia2/router/network_addr.h
+++ b/Semestr 4/sieci/pracownia2/router/network_addr.h
@@ -5,12 +5,9 @@
 #include <stdint.h>
 #include <stdbool.h>
 
-#define INFINITY_DIST 128
-
-/* Network address and sitance */
+/* Network address with netmask. */
 struct network_addr {
   struct in_addr  addr;
-  uint16_t        distance;
   uint8_t         netmask;
 };
 
@@ -23,10 +20,9 @@ struct in_addr get_broadcast_address(struct network_addr na);
 struct in_addr get_network_address(struct network_addr na);
 
 /* Prints network_addr via stdio. */
-void pretty_print(struct network_addr na);
+void pretty_print_network(struct network_addr na);
 
 /* Converts string of ip in CIDR notation with a netmask to network_addr. */
-struct network_addr stora(char *str);
-
+struct network_addr stona(char *str);
 
 #endif
\ No newline at end of file
diff --git a/Semestr 4/sieci/pracownia2/router/router.c b/Semestr 4/sieci/pracownia2/router/router.c
index 031ead8..7262ee6 100644
--- a/Semestr 4/sieci/pracownia2/router/router.c
+++ b/Semestr 4/sieci/pracownia2/router/router.c
@@ -7,74 +7,78 @@
 #include <stdint.h>
 #include <stdlib.h>
 #include <unistd.h>
+#include <limits.h>
 #include "network_addr.h"
 #include "utils.h"
+#include "dist_vector.h"
 
-uint16_t read_configuration(struct network_addr** networks) {
+uint16_t read_configuration(struct network_addr** networks, uint16_t **dists) {
   uint16_t n;
   scanf("%hd", &n);
   *networks = malloc(n * sizeof(struct network_addr));
+  *dists    = malloc(n * sizeof(uint16_t));
   for (int i = 0; i < n; i++) {
     char addr[20];
     char _dist[10];
     uint16_t dist;
     scanf(" %s %s %hd", addr, _dist, &dist);
-    (*networks)[i] = stora(addr);
-    (*networks)[i].distance = dist;
+    (*networks)[i] = stona(addr);
+    (*dists)[i] = dist;
   }
   return n;
 }
 
-void listen_for_routers(int sockfd, int timeout, int networks_number, struct network_addr *netowrks) {
-  printf("Listening for %dms.\n", timeout);
+void listen_for_routers(int sockfd, int timeout, int networks_number, struct network_addr *networks, uint16_t *dists, list_t *dv) {
+  // printf("Listening for %dms.\n", timeout);
+  char buffer[IP_MAXPACKET + 1];
+  struct sockaddr_in sender;
+
   while (poll_socket_modify_timeout(sockfd, &timeout)) {
-    printf("Poll returned, remaining timeout: %dms.\n", timeout);
-    recv_and_print(sockfd, networks_number, netowrks);
-  }
-  printf("Finished listening\n\n");
-}
+    size_t buf_len = recv_message(sockfd, buffer, &sender);
+    struct vector_item new_item = parse_message(buffer, &sender);
+    // char addr[20];
+    // inet_ntop(AF_INET, &sender.sin_addr, addr, sizeof(addr));
+    // printf("Via ip: %s\n", addr);
 
-int send_distance_vector(int sockfd, struct in_addr network) {
-  char* message = "Hello server! My name is S1\n";
-  ssize_t message_len = strlen(message);
-  int result;
+    if (!is_from_network(sender.sin_addr, new_item.network)) {
+      for (int i = 0; i < networks_number; i++) {
+          if (is_from_network(sender.sin_addr, networks[i])) {
+          new_item.distance += dists[i];
+          break;
+        }
+      }
+      new_item.is_connected_directly = false;
+    } 
 
-  char addr[20];
-  inet_ntop(AF_INET, &network, addr, sizeof(addr));
-  printf("Sending datagram to %s\n", addr);
-  if ((result = send_message(sockfd, message, message_len, network)) != message_len) {
-    fprintf(stderr, "sendto error: %s\n", strerror(errno));
+    update_dv_new_item(dv, new_item);
   }
+  update_dv_reachability(dv);
+  // printf("Finished listening\n\n");
 }
 
-void propagate_distance_vector(int sockfd, int networks_number, struct network_addr *networks) {
-  printf("Propagating distance vector\n");
-  for (int i = 0; i < networks_number; i++) {
-    struct in_addr broadcast_address = get_broadcast_address(networks[i]);
-    send_distance_vector(sockfd, broadcast_address);
-  }
-  printf("Distance vector propagated.\n\n");
-}
+void router_loop(int sockfd, int networks_number, struct network_addr *networks, uint16_t *dists) {
+  list_t dv = create_list();
+  init_dv(&dv, networks_number, networks);
 
-void router_loop(int sockfd, int networks_number, struct network_addr *networks) {
   printf("Starting the router loop...\n");
   for (;;) {
-    listen_for_routers(sockfd, TURN_LEN_MS, networks_number, networks);
-    propagate_distance_vector(sockfd, networks_number, networks);
+    print_dv(&dv);
+    propagate_distance_vector(sockfd, networks_number, networks, dists, &dv);
+    listen_for_routers(sockfd, TURN_LEN_MS, networks_number, networks, dists, &dv);
   }
 }
 
 int main() {
   struct network_addr* networks;
-  int n = read_configuration(&networks);
-  for (int i = 0; i < n; i++) {
-    pretty_print(networks[i]);
-  }
+  uint16_t *dists;
+  int n = read_configuration(&networks, &dists);
 
   int sockfd = get_socket();
   bind_to_port(sockfd, SERVER_PORT);
-  router_loop(sockfd, n, networks);
+
+  router_loop(sockfd, n, networks, dists);
 
   close(sockfd);
   free(networks);
+  free(dists);
 }
\ No newline at end of file
diff --git a/Semestr 4/sieci/pracownia2/router/utils.c b/Semestr 4/sieci/pracownia2/router/utils.c
index 2872a35..3f9078e 100644
--- a/Semestr 4/sieci/pracownia2/router/utils.c
+++ b/Semestr 4/sieci/pracownia2/router/utils.c
@@ -5,6 +5,7 @@
 #include <errno.h>
 #include <stdio.h>
 #include <string.h>
+#include <limits.h>
 
 int get_socket() {
   int sockfd = socket(AF_INET, SOCK_DGRAM, 0);
@@ -37,7 +38,7 @@ long get_time_interval(struct timespec start, struct timespec finish) {
 
 int poll_socket_modify_timeout(int sockfd, int *timeout) {
   if (*timeout < 0) {
-    fprintf(stderr, "poll_modify_timeout: timeout is negative.\n");
+    fprintf(stderr, "poll_socket_modify_timeout: timeout is negative.\n");
     exit(EXIT_FAILURE);
   }
 
@@ -62,35 +63,9 @@ int poll_socket_modify_timeout(int sockfd, int *timeout) {
 
   clock_gettime(CLOCK_REALTIME, &finish);
   *timeout -= get_time_interval(start, finish);
-  printf("Timeout: %dms, time waiting: %ldms.\n", *timeout, get_time_interval(start, finish));
   return result;
 }   
 
-void recv_and_print(int sockfd, int networks_number, struct network_addr *networks) {
-  struct sockaddr_in  sender;
-  socklen_t           sender_len = sizeof(sender);
-  uint8_t             buffer[IP_MAXPACKET + 1];
-  ssize_t datagram_len = recvfrom(sockfd, buffer, IP_MAXPACKET, 0,
-    (struct sockaddr*)&sender, &sender_len);
-  if (datagram_len < 0) {
-    fprintf(stderr, "recvfrom error: %s\n", strerror(errno));
-    exit(EXIT_FAILURE);
-  }
-  for (int i = 0; i < networks_number; i++) {
-    if (networks[i].addr.s_addr == sender.sin_addr.s_addr) {
-      return;
-    }
-  }
- 
-  char sender_ip_str[20];
-  inet_ntop(AF_INET, &(sender.sin_addr), sender_ip_str, sizeof(sender_ip_str));
-  printf("Received UDP packet from IP address: %s, port %d\n", 
-    sender_ip_str, ntohs(sender.sin_port));
-
-  buffer[datagram_len] = 0;
-  printf("%ld-byte message: +%s+\n", datagram_len, buffer);
-}
-
 size_t send_message(int sockfd, char *buffer, int buffer_len, struct in_addr network) {
   struct sockaddr_in network_address;
   bzero (&network_address, sizeof(network_address));
@@ -100,3 +75,106 @@ size_t send_message(int sockfd, char *buffer, int buffer_len, struct in_addr net
   
   return sendto(sockfd, buffer, buffer_len, 0, (struct sockaddr*) &network_address, sizeof(network_address));
 }
+
+size_t recv_message(int sockfd, char *buffer, struct sockaddr_in *sender) {
+  socklen_t sender_len = sizeof(*sender);
+  for (int i = 0; i < DV_DATAGRAM_LEN; i++) buffer[i] = 0;
+  size_t datagram_len = recvfrom(sockfd, buffer, IP_MAXPACKET, 0,
+    (struct sockaddr*)sender, &sender_len);
+  if (datagram_len < 0) {
+    fprintf(stderr, "recvfrom error: %s\n", strerror(errno));
+    exit(EXIT_FAILURE);
+  }
+  // printf("Received a message: ");
+  // for (int i = 0 ; i < 9; i++) {
+  //   printf("%u ", (uint8_t)buffer[i]);
+  // }
+  // printf("\n");
+  return datagram_len;
+}
+
+struct vector_item parse_message(char *buffer, struct sockaddr_in *sender) {
+  // printf("Parsing a message: ");
+  // for (int i = 0 ; i < 9; i++) {
+  //   printf("%u ", (uint8_t)buffer[i]);
+  // }
+  // printf("\n");
+  struct vector_item res;
+  uint32_t ip_addr  = *(uint32_t *)buffer;
+  // ip_addr           = ip_addr;
+  uint32_t dist     = *(uint32_t *)(buffer + 5);
+  dist              = ntohl(dist);
+
+  res.network.addr.s_addr   = ip_addr;
+  res.network.netmask       = buffer[4];
+  res.is_connected_directly = true;
+  res.via_ip                = sender->sin_addr;
+  res.distance              = (dist < INFINITY_DIST ? dist : INFINITY_DIST);
+  res.reachable             = 0;
+
+  char addr[20];
+  inet_ntop(AF_INET, &res.network.addr, addr, sizeof(addr));
+  char via[20];
+  inet_ntop(AF_INET, &sender->sin_addr, via, sizeof(via));
+  
+  // printf("Po ludzku: %s/%d, distance %d, via %s\n", addr,  res.network.netmask, res.distance, via);
+
+  return res;
+}
+
+void _get_message(struct vector_item item, char *message) {
+  *(uint32_t *)message  = item.network.addr.s_addr;
+  message[4]            = item.network.netmask;
+  uint32_t distance     = htonl(item.distance >= INFINITY_DIST ? INT_MAX : item.distance);
+  for (int i = 0; i < 4; i++) {
+    *(message + 5 + i) = *((char *)(&distance) + i); 
+  }
+}
+
+int _send_item(int sockfd, struct network_addr network, struct vector_item item) {
+  char message[DV_DATAGRAM_LEN + 1];
+  _get_message(item, message);
+  message[DV_DATAGRAM_LEN] = 0;
+  ssize_t message_len = DV_DATAGRAM_LEN;
+
+  struct in_addr na = get_broadcast_address(network);
+  
+  char addr[20];
+  inet_ntop(AF_INET, &na, addr, sizeof(addr));
+  // printf("Sending datagram to %s: ", addr);
+  // for (int i = 0 ; i < DV_DATAGRAM_LEN; i++) {
+  //   printf("%u ", (uint8_t)message[i]);
+  // }
+  // printf("\nmessage_len: %ld\n", message_len);
+  int result;
+  if ((result = send_message(sockfd, message, message_len, na)) != message_len) {
+    // fprintf(stderr, "sendto error: %s\n", strerror(errno));
+  }
+  return result;
+}
+
+void propagate_distance_vector(int sockfd, int networks_number, struct network_addr *networks, uint16_t *dists, list_t *dv) {
+  for (int i = 0; i < networks_number; i++) {
+    reset(dv);
+    while (dv->it != NULL) {
+      struct vector_item data = *(struct vector_item *)dv->it->data;
+      if (!(get_network_address(data.network).s_addr == get_network_address(networks[i]).s_addr)) {
+        _send_item(sockfd, networks[i], data);
+      }
+      iterate(dv);
+    }
+
+    struct vector_item self_item;
+    self_item.distance = dists[i];
+    self_item.network = networks[i];    
+    // printf("Sending self message: %d\n", dists[i]);
+    _send_item(sockfd, networks[i], self_item);
+  }
+}
+
+bool is_from_network(struct in_addr ip_addr, struct network_addr network) {
+  struct network_addr temp;
+  temp.addr= ip_addr;
+  temp.netmask = network.netmask;
+  return (get_network_address(temp).s_addr == get_network_address(network).s_addr);
+}
\ No newline at end of file
diff --git a/Semestr 4/sieci/pracownia2/router/utils.h b/Semestr 4/sieci/pracownia2/router/utils.h
index 63ad6fb..3642779 100644
--- a/Semestr 4/sieci/pracownia2/router/utils.h
+++ b/Semestr 4/sieci/pracownia2/router/utils.h
@@ -7,6 +7,7 @@
 #include <time.h>
 #include <poll.h>
 #include "network_addr.h"
+#include "dist_vector.h"
 
 #define NS_TO_MS(X) ((long)(X) / (long)1000000)
 #define S_TO_MS(X) ((long)(X) * (long)1000)
@@ -32,5 +33,17 @@ void recv_and_print(int sockfd, int networks_number, struct network_addr *networ
  */  
 size_t send_message(int sockfd, char *buffer, int buffer_len, struct in_addr addr);
 
+/* Receive message and write it to buffer. */
+size_t recv_message(int sockfd, char *buffer, struct sockaddr_in *sender);
+
+/* Parse datagram into a vector item. */
+struct vector_item parse_message(char *buffer, struct sockaddr_in *sender);
+
+/* Propagates dv to all connected networks. */
+void propagate_distance_vector(int sockfd, int networks_number, struct network_addr *networks, uint16_t *dists, list_t *dv);
+
+/* Checks if given address is in network range. */
+bool is_from_network(struct in_addr ip_addr, struct network_addr network);
+ 
 
 #endif
\ No newline at end of file