HNA refactoring phase #1
authorHannes Gredler <hannes@gredler.at>
Mon, 15 Sep 2008 13:56:38 +0000 (15:56 +0200)
committerHannes Gredler <hannes@gredler.at>
Mon, 15 Sep 2008 13:56:38 +0000 (15:56 +0200)
lib/dot_draw/src/olsrd_dot_draw.c
lib/tas/src/plugin.c
lib/txtinfo/src/olsrd_txtinfo.c
src/hna_set.c
src/hna_set.h
src/tc_set.c
src/tc_set.h

index 7b97ebc..5b6adc0 100644 (file)
@@ -299,7 +299,6 @@ pcf_event(int chgs_neighborhood,
   struct neighbor_entry *neighbor_table_tmp;
   struct tc_entry *tc;
   struct tc_edge_entry *tc_edge;
-  struct hna_entry *tmp_hna;
   struct hna_net *tmp_net;
   struct ip_prefix_list *hna;
   int res = 0;
@@ -324,17 +323,15 @@ pcf_event(int chgs_neighborhood,
     } OLSR_FOR_ALL_TC_ENTRIES_END(tc);
 
     /* HNA entries */
-    OLSR_FOR_ALL_HNA_ENTRIES(tmp_hna) {
-
+    OLSR_FOR_ALL_TC_ENTRIES(tc) {
       /* Check all networks */
-      for (tmp_net = tmp_hna->networks.next;
-           tmp_net != &tmp_hna->networks;
-           tmp_net = tmp_net->next) {
-        ipc_print_net(&tmp_hna->A_gateway_addr, 
-                      &tmp_net->A_network_addr, 
-                      tmp_net->prefixlen);
-      }
-    } OLSR_FOR_ALL_HNA_ENTRIES_END(tmp_hna);
+      OLSR_FOR_ALL_TC_HNA_ENTRIES(tc, tmp_net) {
+          ipc_print_net(&tc->addr, 
+                        &tmp_net->hna_prefix.prefix, 
+                        tmp_net->hna_prefix.prefix_len);
+        }
+      } OLSR_FOR_ALL_TC_HNA_ENTRIES_END(tc, tmp_hna);
+    OLSR_FOR_ALL_TC_ENTRIES_END(tc);
 
     /* Local HNA entries */
     for (hna = olsr_cnf->hna_entries; hna != NULL; hna = hna->next) {
index 2606e81..82a8988 100644 (file)
@@ -81,7 +81,6 @@ static union olsr_ip_addr *mainAddr;
 
 static struct interface *intTab = NULL;
 static struct neighbor_entry *neighTab = NULL;
-static struct hna_entry *hnaTab = NULL;
 static struct olsrd_config *config = NULL;
 
 static int iterIndex;
@@ -460,7 +459,6 @@ int olsrd_plugin_init(void)
 
   intTab = ifnet;
   neighTab = neighbortable;
-  hnaTab = hna_set;
   config = olsr_cnf;
 
   httpInit();
index d556c5c..05238ac 100644 (file)
@@ -419,7 +419,7 @@ static void ipc_print_hna(void)
 {
     int size;
     struct ip_prefix_list *hna;
-    struct hna_entry *tmp_hna;
+    struct tc_entry *tc;
     struct hna_net *tmp_net;
     struct ipaddr_str addrbuf, mainaddrbuf;
 
@@ -445,19 +445,17 @@ static void ipc_print_hna(void)
     }
 
     /* HNA entries */
-    OLSR_FOR_ALL_HNA_ENTRIES(tmp_hna) {
-
+    OLSR_FOR_ALL_TC_ENTRIES(tc) {
         /* Check all networks */
-        for (tmp_net = tmp_hna->networks.next;
-             tmp_net != &tmp_hna->networks;
-             tmp_net = tmp_net->next) {
+        OLSR_FOR_ALL_TC_HNA_ENTRIES(tc, tmp_net) {
 
             ipc_sendf("%s/%d\t%s\n",
-                      olsr_ip_to_string(&addrbuf, &tmp_net->A_network_addr),
-                      tmp_net->prefixlen,
-                      olsr_ip_to_string(&mainaddrbuf, &tmp_hna->A_gateway_addr));
-        }
-    } OLSR_FOR_ALL_HNA_ENTRIES_END(tmp_hna);
+                      olsr_ip_to_string(&addrbuf, &tmp_net->hna_prefix.prefix),
+                      tmp_net->hna_prefix.prefix_len,
+                      olsr_ip_to_string(&mainaddrbuf, &tc->addr));
+
+        } OLSR_FOR_ALL_TC_HNA_ENTRIES_END(tc, tmp_net);
+    } OLSR_FOR_ALL_TC_ENTRIES_END(tc);
 
     ipc_sendf("\n");
 }
index a29f9d3..5ef8c46 100644 (file)
 #include "net_olsr.h"
 #include "tc_set.h"
 
-
-struct hna_entry hna_set[HASHSIZE];
+/* Some cookies for stats keeping */
 struct olsr_cookie_info *hna_net_timer_cookie = NULL;
-struct olsr_cookie_info *hna_entry_mem_cookie = NULL;
 struct olsr_cookie_info *hna_net_mem_cookie = NULL;
 
 /**
  * Initialize the HNA set
  */
-int
+void
 olsr_init_hna_set(void)
 {
-  int idx;
-
-  for(idx=0;idx<HASHSIZE;idx++) {
-    hna_set[idx].next = &hna_set[idx];
-    hna_set[idx].prev = &hna_set[idx];
-  }
+  OLSR_PRINTF(5, "HNA: init\n");
 
   hna_net_timer_cookie =
     olsr_alloc_cookie("HNA Network", OLSR_COOKIE_TYPE_TIMER);
@@ -70,136 +63,82 @@ olsr_init_hna_set(void)
   hna_net_mem_cookie =
     olsr_alloc_cookie("hna_net", OLSR_COOKIE_TYPE_MEMORY);
   olsr_cookie_set_memory_size(hna_net_mem_cookie, sizeof(struct hna_net));
-
-  hna_entry_mem_cookie =
-    olsr_alloc_cookie("hna_entry", OLSR_COOKIE_TYPE_MEMORY);
-  olsr_cookie_set_memory_size(hna_entry_mem_cookie, sizeof(struct hna_entry));
-
-  return 1;
 }
 
 /**
- * Lookup a network entry in a networkentry list.
+ * Lookup a network entry in the HNA subtree.
  *
- * @param nets the network list to look in
- * @param net the network to look for
- * @param mask the netmask to look for
+ * @param tc the HNA hookup point
+ * @param prefic the prefix to look for
  *
  * @return the localized entry or NULL of not found
  */
-struct hna_net *
-olsr_lookup_hna_net(const struct hna_net *nets, const union olsr_ip_addr *net,
-                    olsr_u8_t prefixlen)
+static struct hna_net *
+olsr_lookup_hna_net(struct tc_entry *tc, struct olsr_ip_prefix *prefix)
 {
-  struct hna_net *tmp;
-
-  /* Loop trough entrys */
-  for (tmp = nets->next; tmp != nets; tmp = tmp->next) { 
-    if (tmp->prefixlen == prefixlen && ipequal(&tmp->A_network_addr, net)) {
-      return tmp;
-    }
-  }
-
-  /* Not found */
-  return NULL;
+  return (hna_tc_tree2hna(avl_find(&tc->hna_tree, prefix)));
 }
 
-
 /**
- * Lookup a gateway entry
- *
- * @param gw the address of the gateway
- * @return the located entry or NULL if not found
- */
-struct hna_entry *
-olsr_lookup_hna_gw(const union olsr_ip_addr *gw)
-{
-  struct hna_entry *tmp_hna;
-  olsr_u32_t hash = olsr_ip_hashing(gw);
-
-#if 0
-  OLSR_PRINTF(5, "HNA: lookup entry\n");
-#endif
-    /* Check for registered entry */
-
-  for(tmp_hna = hna_set[hash].next;
-      tmp_hna != &hna_set[hash];
-      tmp_hna = tmp_hna->next) {
-    if(ipequal(&tmp_hna->A_gateway_addr, gw)) {
-      return tmp_hna;
-    }
-  }
-  
-  /* Not found */
-  return NULL;
-}
-
-
-
-/**
- *Add a gatewayentry to the HNA set
+ * Adds a network entry to a HNA gateway.
  *
- *@param addr the address of the gateway
+ * @param tc the gateway entry to add the network to
+ * @param net the nework prefix to add
+ * @param prefixlen the prefix length
  *
- *@return the created entry
+ * @return the newly created entry
  */
-struct hna_entry *
-olsr_add_hna_entry(const union olsr_ip_addr *addr)
+static struct hna_net *
+olsr_add_hna_net(struct tc_entry *tc, struct olsr_ip_prefix *prefix)
 {
-  struct hna_entry *new_entry;
-  olsr_u32_t hash;
-
-  new_entry = olsr_cookie_malloc(hna_entry_mem_cookie);
-
+  /* Add the net */
+  struct hna_net *new_net = olsr_cookie_malloc(hna_net_mem_cookie);
+  
   /* Fill struct */
-  new_entry->A_gateway_addr = *addr;
+  new_net->hna_prefix = *prefix;
 
-  /* Link nets */
-  new_entry->networks.next = &new_entry->networks;
-  new_entry->networks.prev = &new_entry->networks;
+  /* Set backpointer */
+  new_net->hna_tc = tc;
+  olsr_lock_tc_entry(tc);
 
-  /* queue */
-  hash = olsr_ip_hashing(addr);
-  
-  hna_set[hash].next->prev = new_entry;
-  new_entry->next = hna_set[hash].next;
-  hna_set[hash].next = new_entry;
-  new_entry->prev = &hna_set[hash];
+  /*
+   * Insert into the per-tc hna subtree.
+   */
+  new_net->hna_tc_node.key = &new_net->hna_prefix;
+  avl_insert(&tc->hna_tree, &new_net->hna_tc_node, AVL_DUP_NO);
 
-  return new_entry;
+  return new_net;
 }
 
 /**
- * Adds a network entry to a HNA gateway.
- *
- * @param hna_gw the gateway entry to add the network to
- * @param net the networkaddress to add
- * @param mask the netmask
- *
- * @return the newly created entry
+ * Delete a single HNA network.
+ * 
+ * @param hna_net the hna_net to delete.
  */
-struct hna_net *
-olsr_add_hna_net(struct hna_entry *hna_gw, const union olsr_ip_addr *net,
-                 olsr_u8_t prefixlen)
+static void
+olsr_delete_hna_net(struct hna_net *hna_net)
 {
-  /* Add the net */
-  struct hna_net *new_net = olsr_cookie_malloc(hna_net_mem_cookie);
-  
-  /* Fill struct */
-  memset(new_net, 0, sizeof(struct hna_net));
-  new_net->A_network_addr = *net;
-  new_net->prefixlen = prefixlen;
+  struct tc_entry *tc;
 
-  /* Set backpointer */
-  new_net->hna_gw = hna_gw;
+  tc = hna_net->hna_tc;
 
-  /* Queue */
-  hna_gw->networks.next->prev = new_net;
-  new_net->next = hna_gw->networks.next;
-  hna_gw->networks.next = new_net;
-  new_net->prev = &hna_gw->networks;
+  /*
+   * Delete the rt_path for the hna_net.
+   */
+  olsr_delete_routing_table(&hna_net->hna_prefix.prefix,
+                            hna_net->hna_prefix.prefix_len,
+                            &tc->addr);
 
-  return new_net;
+  /*
+   * Remove from the per-tc tree.
+   */
+  avl_delete(&tc->hna_tree, &hna_net->hna_tc_node);
+
+  /*
+   * Unlock and free.
+   */
+  olsr_unlock_tc_entry(tc);
+  olsr_cookie_free(hna_net_mem_cookie, hna_net);
 }
 
 /**
@@ -211,36 +150,19 @@ olsr_expire_hna_net_entry(void *context)
 #ifdef DEBUG
   struct ipaddr_str buf1, buf2;
 #endif
-  struct hna_net *net_to_delete;
-  struct hna_entry *hna_gw;
+  struct hna_net *hna_net;
 
-  net_to_delete = (struct hna_net *)context;
-  net_to_delete->hna_net_timer = NULL; /* be pedandic */
-  hna_gw = net_to_delete->hna_gw;
+  hna_net = (struct hna_net *)context;
+  hna_net->hna_net_timer = NULL; /* be pedandic */
 
 #ifdef DEBUG
   OLSR_PRINTF(5, "HNA: timeout %s/%u via hna-gw %s\n", 
-              olsr_ip_to_string(&buf1, &net_to_delete->A_network_addr),
-              net_to_delete->prefixlen,
-              olsr_ip_to_string(&buf2, &hna_gw->A_gateway_addr));
+              olsr_ip_to_string(&buf1, &hna_net->A_network_addr),
+              hna_net->prefixlen,
+              olsr_ip_to_string(&buf2, &hna_net->hna_tc->addr));
 #endif
 
-  /*
-   * Delete the rt_path for the entry.
-   */
-  olsr_delete_routing_table(&net_to_delete->A_network_addr,
-                            net_to_delete->prefixlen,
-                            &hna_gw->A_gateway_addr);
-
-
-  /* Delete hna_gw if empty */
-  if (hna_gw->networks.next == &hna_gw->networks) {
-    DEQUEUE_ELEM(hna_gw);
-    olsr_cookie_free(hna_entry_mem_cookie, hna_gw);
-  }
-
-  DEQUEUE_ELEM(net_to_delete);
-  olsr_cookie_free(hna_net_mem_cookie, net_to_delete);
+  olsr_delete_hna_net(hna_net);
 }
 
 /**
@@ -260,30 +182,28 @@ void
 olsr_update_hna_entry(const union olsr_ip_addr *gw, const union olsr_ip_addr *net,
                       olsr_u8_t prefixlen, olsr_reltime vtime)
 {
-  struct hna_entry *gw_entry;
+  struct tc_entry *tc;
   struct hna_net *net_entry;
+  struct olsr_ip_prefix prefix;
 
-  gw_entry = olsr_lookup_hna_gw(gw);
-  if (!gw_entry) {
-
-    /* Need to add the entry */
-    gw_entry = olsr_add_hna_entry(gw);
-  }
+  tc = olsr_locate_tc_entry(gw);
 
-  net_entry = olsr_lookup_hna_net(&gw_entry->networks, net, prefixlen);
-  if (net_entry == NULL)  {
+  prefix.prefix = *net;
+  prefix.prefix_len = prefixlen;
+  net_entry = olsr_lookup_hna_net(tc, &prefix);
+  if (net_entry == NULL) {
 
     /* Need to add the net */
-    net_entry = olsr_add_hna_net(gw_entry, net, prefixlen);
+    net_entry = olsr_add_hna_net(tc, &prefix);
     changes_hna = OLSR_TRUE;
   }
 
   /*
    * Add the rt_path for the entry.
    */
-  olsr_insert_routing_table(&net_entry->A_network_addr,
-                            net_entry->prefixlen,
-                            &gw_entry->A_gateway_addr,
+  olsr_insert_routing_table(&net_entry->hna_prefix.prefix,
+                            net_entry->hna_prefix.prefix_len,
+                            &tc->addr,
                             OLSR_RT_ORIGIN_HNA);
 
   /*
@@ -295,7 +215,6 @@ olsr_update_hna_entry(const union olsr_ip_addr *gw, const union olsr_ip_addr *ne
                  hna_net_timer_cookie->ci_id);
 }
 
-
 /**
  * Print all HNA entries.
  *
@@ -305,52 +224,24 @@ void
 olsr_print_hna_set(void)
 {
 #ifdef NODEBUG
-  /* The whole function doesn't do anything else. */
-  int idx;
-
-  OLSR_PRINTF(1, "\n--- %02d:%02d:%02d.%02d ------------------------------------------------- HNA SET\n\n",
-              nowtm->tm_hour,
-              nowtm->tm_min,
-              nowtm->tm_sec,
-             (int)now.tv_usec/10000);
-  
-  if(olsr_cnf->ip_version == AF_INET)
-    OLSR_PRINTF(1, "IP net          netmask         GW IP\n");
-  else
-    OLSR_PRINTF(1, "IP net/prefixlen               GW IP\n");
+  struct tc_entry *tc;
+  struct hna_net *hna_net;
 
-  for(idx=0;idx<HASHSIZE;idx++)
-    {
-      struct hna_entry *tmp_hna = hna_set[idx].next;
-      /* Check all entrys */
-      while(tmp_hna != &hna_set[idx])
-       {
-         /* Check all networks */
-         struct hna_net *tmp_net = tmp_hna->networks.next;
-
-         while(tmp_net != &tmp_hna->networks)
-           {
-             if(olsr_cnf->ip_version == AF_INET)
-               {
-                  struct ipaddr_str buf;
-                 OLSR_PRINTF(1, "%-15s ", olsr_ip_to_string(&buf, &tmp_net->A_network_addr));
-                 OLSR_PRINTF(1, "%-15d ", tmp_net->prefix_len);
-                 OLSR_PRINTF(1, "%-15s\n", olsr_ip_to_string(&buf, &tmp_hna->A_gateway_addr));
-               }
-             else
-               {
-                  struct ipaddr_str buf;
-                 OLSR_PRINTF(1, "%-27s/%d", olsr_ip_to_string(&buf, &tmp_net->A_network_addr), tmp_net->A_netmask.v6);
-                 OLSR_PRINTF(1, "%s\n", olsr_ip_to_string(&buf, &tmp_hna->A_gateway_addr));
-               }
+  /* The whole function doesn't do anything else. */
 
-             tmp_net = tmp_net->next;
-           }
-         tmp_hna = tmp_hna->next;
-       }
-    }
+  OLSR_PRINTF(1,
+             "\n--- %s ------------------------------------------------- HNA\n\n",
+             olsr_wallclock_string());
+
+  OLSR_FOR_ALL_TC_ENTRIES(tc) {
+    OLSR_PRINTF(1, "HNA-gw %s: ", olsr_ip_to_string(&buf, &tc->addr));
+    OLSR_FOR_ALL_TC_HNA_ENTRIES(tc, hna_net) {
+      OLSR_PRINTF(1, "%-27s", olsr_ip_prefix_to_string(hna_net->hna_prefix);
+                  } OLSR_FOR_ALL_TC_HNA_ENTRIES_END(tc, hna_net);
+      OLSR_PRINTF(1, "\n");
+    } OLSR_FOR_ALL_TC_ENTRIES_END(tc);
 #endif
-}
+  }
 
 /*
  * Local Variables:
index 776dc77..717df14 100644 (file)
 #ifndef _OLSR_HNA
 #define _OLSR_HNA
 
-#include "hashing.h"
+#include "common/avl.h"
 #include "olsr_types.h"
 #include "mantissa.h"
 
 #include <time.h>
 
-/* hna_netmask declared in packet.h */
-
 struct hna_net
 {
-  union olsr_ip_addr A_network_addr;
-  olsr_u8_t          prefixlen;
-  struct timer_entry *hna_net_timer;
-  struct hna_entry   *hna_gw; /* backpointer to the owning HNA entry */
-  struct hna_net     *next;
-  struct hna_net     *prev;
+  struct avl_node hna_tc_node;          /* node in the per-tc hna tree */
+  struct olsr_ip_prefix hna_prefix;     /* the prefix, key */
+  struct timer_entry *hna_net_timer;    /* expiration timer */
+  struct tc_entry    *hna_tc;           /* backpointer to the owning tc entry */
 };
 
-#define OLSR_HNA_NET_JITTER 5 /* percent */
+AVLNODE2STRUCT(hna_tc_tree2hna, struct hna_net, hna_tc_node);
 
-struct hna_entry
-{
-  union olsr_ip_addr A_gateway_addr;
-  struct hna_net     networks;
-  struct hna_entry   *next;
-  struct hna_entry   *prev;
-};
+#define OLSR_HNA_NET_JITTER 5 /* percent */
 
-#define OLSR_FOR_ALL_HNA_ENTRIES(hna) \
+#define OLSR_FOR_ALL_TC_HNA_ENTRIES(tc, hna_net) \
 { \
-  int _idx; \
-  for (_idx = 0; _idx < HASHSIZE; _idx++) { \
-    for(hna = hna_set[_idx].next; \
-        hna != &hna_set[_idx]; \
-        hna = hna->next)
-#define OLSR_FOR_ALL_HNA_ENTRIES_END(hna) }}
-
-extern struct hna_entry hna_set[HASHSIZE];
-
-
-int
-olsr_init_hna_set(void);
-
-struct hna_net *
-olsr_lookup_hna_net(const struct hna_net *, const union olsr_ip_addr *, olsr_u8_t);
-
-struct hna_entry *
-olsr_lookup_hna_gw(const union olsr_ip_addr *);
-
-struct hna_entry *
-olsr_add_hna_entry(const union olsr_ip_addr *);
-
-struct hna_net *
-olsr_add_hna_net(struct hna_entry *, const union olsr_ip_addr *, olsr_u8_t);
-
-void
-olsr_update_hna_entry(const union olsr_ip_addr *, const union olsr_ip_addr *, olsr_u8_t, olsr_reltime);
-
-void
-olsr_print_hna_set(void);
+  struct avl_node *hna_net_node, *next_hna_net_node; \
+  for (hna_net_node = avl_walk_first(&tc->hna_tree); \
+    hna_net_node; hna_net_node = next_hna_net_node) { \
+    next_hna_net_node = avl_walk_next(hna_net_node); \
+    hna_net = hna_tc_tree2hna(hna_net_node);
+#define OLSR_FOR_ALL_TC_HNA_ENTRIES_END(tc, hna_net) }}
+
+void olsr_init_hna_set(void);
+void olsr_update_hna_entry(const union olsr_ip_addr *,
+                           const union olsr_ip_addr *,
+                           olsr_u8_t, olsr_reltime);
+void olsr_print_hna_set(void);
 
 #endif
 
index 54778ff..f8db244 100644 (file)
@@ -164,11 +164,12 @@ olsr_add_tc_entry(const union olsr_ip_addr *adr)
   olsr_lock_tc_entry(tc);
 
   /*
-   * Initialize subtrees for edges, prefixes and MIDs.
+   * Initialize subtrees for edges, prefixes, HNAs and MIDs.
    */
   avl_init(&tc->edge_tree, avl_comp_default);
   avl_init(&tc->prefix_tree, avl_comp_prefix_default);
   avl_init(&tc->mid_tree, avl_comp_default);
+  avl_init(&tc->hna_tree, avl_comp_prefix_default);
 
   /*
    * Add a rt_path for ourselves.
index eb6b1aa..efdac87 100644 (file)
@@ -77,6 +77,7 @@ struct tc_entry {
   struct avl_tree edge_tree;          /* subtree for edges */
   struct avl_tree prefix_tree;        /* subtree for prefixes */
   struct avl_tree mid_tree;            /* subtree for MID entries */
+  struct avl_tree hna_tree;            /* subtree for HNA entries */
   struct timer_entry *mid_timer;       /* aging timer for MID advertisements */
   struct link_entry *next_hop;        /* SPF calculated link to the 1st hop neighbor */
   struct timer_entry *edge_gc_timer;   /* used for edge garbage collection */