pimd: Add hash lookups for upstream

8 files changed, 108 insertions, 89 deletions

diff --git a/pimd/pim_cmd.c b/pimd/pim_cmd.c
index 4f685eca3..a12a7a230 100644
--- a/pimd/pim_cmd.c
+++ b/pimd/pim_cmd.c
@@ -823,8 +823,8 @@ static void pim_show_interfaces_single(struct vty *vty, const char *ifname, u_ch
       json_object_int_add(json_row, "drChanges", pim_ifp->pim_dr_election_changes);
 
       // FHR
-      for (ALL_LIST_ELEMENTS_RO(qpim_upstream_list, upnode, up)) {
-        if (strcmp(ifp->name, up->rpf.source_nexthop.interface->name) == 0) {
+      for (ALL_LIST_ELEMENTS_RO(pim_upstream_list, upnode, up)) {
+        if (ifp ==  up->rpf.source_nexthop.interface) {
           if (up->flags & PIM_UPSTREAM_FLAG_MASK_FHR) {
             if (!json_fhr_sources) {
               json_fhr_sources = json_object_new_object();
@@ -915,7 +915,7 @@ static void pim_show_interfaces_single(struct vty *vty, const char *ifname, u_ch
 
       // FHR
       print_header = 1;
-      for (ALL_LIST_ELEMENTS_RO(qpim_upstream_list, upnode, up)) {
+      for (ALL_LIST_ELEMENTS_RO(pim_upstream_list, upnode, up)) {
         if (strcmp(ifp->name, up->rpf.source_nexthop.interface->name) == 0) {
           if (up->flags & PIM_UPSTREAM_FLAG_MASK_FHR) {
 
@@ -982,12 +982,11 @@ static void pim_show_interfaces_single(struct vty *vty, const char *ifname, u_ch
   }
 }
 
-
 static void pim_show_interfaces(struct vty *vty, u_char uj)
 {
   struct in_addr ifaddr;
   struct interface *ifp;
-  struct listnode  *node;
+  struct listnode *node;
   struct listnode *upnode;
   struct pim_interface *pim_ifp;
   struct pim_upstream *up;
@@ -998,7 +997,7 @@ static void pim_show_interfaces(struct vty *vty, u_char uj)
   json_object *json_row = NULL;
   char local_ip[INET_ADDRSTRLEN];
   char dr_ip[INET_ADDRSTRLEN];
-  
+
   if (uj) {
     json = json_object_new_object();
   } else {
@@ -1022,8 +1021,8 @@ static void pim_show_interfaces(struct vty *vty, u_char uj)
     if (pim_ifp->pim_dr_addr.s_addr == pim_ifp->primary_address.s_addr)
       pim_dr_local = 1;
 
-    for (ALL_LIST_ELEMENTS_RO(qpim_upstream_list, upnode, up))
-      if (strcmp(ifp->name, up->rpf.source_nexthop.interface->name) == 0)
+    for (ALL_LIST_ELEMENTS_RO(pim_upstream_list, upnode, up))
+      if (ifp ==  up->rpf.source_nexthop.interface)
         if (up->flags & PIM_UPSTREAM_FLAG_MASK_FHR)
           fhr++;
 
@@ -1589,7 +1588,7 @@ static void pim_show_upstream(struct vty *vty, u_char uj)
   else
     vty_out(vty, "Iif       Source          Group           State       Uptime   JoinTimer RSTimer   KATimer   RefCnt%s", VTY_NEWLINE);
 
-  for (ALL_LIST_ELEMENTS_RO(qpim_upstream_list, upnode, up)) {
+  for (ALL_LIST_ELEMENTS_RO(pim_upstream_list, upnode, up)) {
     char src_str[100];
     char grp_str[100];
     char uptime[10];
@@ -1742,7 +1741,7 @@ static void pim_show_upstream_rpf(struct vty *vty, u_char uj)
             "Source          Group           RpfIface RibNextHop      RpfAddress     %s",
             VTY_NEWLINE);
 
-  for (ALL_LIST_ELEMENTS_RO(qpim_upstream_list, upnode, up)) {
+  for (ALL_LIST_ELEMENTS_RO(pim_upstream_list, upnode, up)) {
     char src_str[100];
     char grp_str[100];
     char rpf_nexthop_str[100];
@@ -1861,7 +1860,7 @@ static void pim_show_rpf(struct vty *vty, u_char uj)
             VTY_NEWLINE);
   }
 
-  for (ALL_LIST_ELEMENTS_RO(qpim_upstream_list, up_node, up)) {
+  for (ALL_LIST_ELEMENTS_RO(pim_upstream_list, up_node, up)) {
     char src_str[100];
     char grp_str[100];
     char rpf_addr_str[100];
diff --git a/pimd/pim_ifchannel.c b/pimd/pim_ifchannel.c
index eb127338e..2f9e9b598 100644
--- a/pimd/pim_ifchannel.c
+++ b/pimd/pim_ifchannel.c
@@ -790,7 +790,7 @@ void pim_ifchannel_local_membership_add(struct interface *ifp,
       struct pim_upstream *child;
       struct listnode *up_node;
 
-      for (ALL_LIST_ELEMENTS_RO (qpim_upstream_list, up_node, child))
+      for (ALL_LIST_ELEMENTS_RO (pim_upstream_list, up_node, child))
         {
           if (child->parent == up)
             {
@@ -839,7 +839,7 @@ void pim_ifchannel_local_membership_del(struct interface *ifp,
       struct pim_upstream *child;
       struct listnode *up_node;
 
-      for (ALL_LIST_ELEMENTS_RO (qpim_upstream_list, up_node, child))
+      for (ALL_LIST_ELEMENTS_RO (pim_upstream_list, up_node, child))
         {
           if (child->parent == up)
             {
diff --git a/pimd/pim_join.c b/pimd/pim_join.c
index 08c1c7b93..0a00be9e6 100644
--- a/pimd/pim_join.c
+++ b/pimd/pim_join.c
@@ -117,7 +117,7 @@ static void recv_join(struct interface *ifp,
       if (!up)
 	return;
 
-      for (ALL_LIST_ELEMENTS_RO (qpim_upstream_list, up_node, child))
+      for (ALL_LIST_ELEMENTS_RO (pim_upstream_list, up_node, child))
         {
           if (child->parent == up)
             {
@@ -194,7 +194,7 @@ static void recv_prune(struct interface *ifp,
       if (!up)
 	return;
 
-      for (ALL_LIST_ELEMENTS_RO (qpim_upstream_list, up_node, child))
+      for (ALL_LIST_ELEMENTS_RO (pim_upstream_list, up_node, child))
         {
           if (child->parent == up)
             {
diff --git a/pimd/pim_upstream.c b/pimd/pim_upstream.c
index cbc8e5050..88755ec9f 100644
--- a/pimd/pim_upstream.c
+++ b/pimd/pim_upstream.c
@@ -30,6 +30,8 @@
 #include "linklist.h"
 #include "vty.h"
 #include "plist.h"
+#include "hash.h"
+#include "jhash.h"
 
 #include "pimd.h"
 #include "pim_pim.h"
@@ -49,6 +51,9 @@
 #include "pim_br.h"
 #include "pim_register.h"
 
+struct hash *pim_upstream_hash = NULL;
+struct list *pim_upstream_list = NULL;
+
 static void join_timer_start(struct pim_upstream *up);
 static void pim_upstream_update_assert_tracking_desired(struct pim_upstream *up);
 
@@ -73,7 +78,7 @@ pim_upstream_remove_children (struct pim_upstream *up)
       (up->sg.grp.s_addr != INADDR_ANY))
     return;
 
-  for (ALL_LIST_ELEMENTS_RO (qpim_upstream_list, ch_node, child))
+  for (ALL_LIST_ELEMENTS_RO (pim_upstream_list, ch_node, child))
     {
       if (child->parent == up)
         child->parent = NULL;
@@ -99,10 +104,10 @@ pim_upstream_find_new_children (struct pim_upstream *up)
       (up->sg.grp.s_addr == INADDR_ANY))
     return;
 
-  for (ALL_LIST_ELEMENTS_RO (qpim_upstream_list, ch_node, child))
+  for (ALL_LIST_ELEMENTS_RO (pim_upstream_list, ch_node, child))
     {
       if ((up->sg.grp.s_addr != INADDR_ANY) &&
-          (child->sg.grp.s_addr == up->sg.grp.s_addr) &&
+	  (child->sg.grp.s_addr == up->sg.grp.s_addr) &&
 	  (child != up))
         child->parent = up;
     }
@@ -166,7 +171,8 @@ void pim_upstream_delete(struct pim_upstream *up)
     into pim_upstream_free() because the later is
     called by list_delete_all_node()
   */
-  listnode_delete(qpim_upstream_list, up);
+  listnode_delete (pim_upstream_list, up);
+  hash_release (pim_upstream_hash, up);
 
   pim_upstream_free(up);
 }
@@ -482,6 +488,7 @@ static struct pim_upstream *pim_upstream_new(struct prefix_sg *sg,
   }
   
   up->sg                          = *sg;
+  up = hash_get (pim_upstream_hash, up, hash_alloc_intern);
   if (!pim_rp_set_upstream_addr (&up->upstream_addr, sg->src, sg->grp))
     {
       if (PIM_DEBUG_PIM_TRACE)
@@ -520,44 +527,19 @@ static struct pim_upstream *pim_upstream_new(struct prefix_sg *sg,
     return NULL;
   }
 
-  listnode_add_sort(qpim_upstream_list, up);
+  listnode_add_sort(pim_upstream_list, up);
 
   return up;
 }
 
-/*
- * For a given sg, find any non * source
- */
-struct pim_upstream *pim_upstream_find_non_any (struct prefix_sg *sg)
-{
-  struct listnode *up_node;
-  struct prefix_sg any = *sg;
-  struct pim_upstream *up;
-
-  any.src.s_addr = INADDR_ANY;
-
-  for (ALL_LIST_ELEMENTS_RO (qpim_upstream_list, up_node, up))
-    {
-      if ((any.grp.s_addr == up->sg.grp.s_addr) &&
-          (up->sg.src.s_addr != any.src.s_addr))
-        return up;
-    }
-
-  return NULL;
-}
-
 struct pim_upstream *pim_upstream_find(struct prefix_sg *sg)
 {
-  struct listnode     *up_node;
-  struct pim_upstream *up;
-
-  for (ALL_LIST_ELEMENTS_RO(qpim_upstream_list, up_node, up)) {
-    if ((sg->grp.s_addr == up->sg.grp.s_addr) &&
-	(sg->src.s_addr == up->sg.src.s_addr))
-      return up;
-  }
+  struct pim_upstream lookup;
+  struct pim_upstream *up = NULL;
 
-  return NULL;
+  lookup.sg = *sg;
+  up = hash_lookup (pim_upstream_hash, &lookup);
+  return up;
 }
 
 struct pim_upstream *pim_upstream_add(struct prefix_sg *sg,
@@ -705,9 +687,9 @@ void pim_upstream_rpf_genid_changed(struct in_addr neigh_addr)
   struct pim_upstream *up;
 
   /*
-    Scan all (S,G) upstreams searching for RPF'(S,G)=neigh_addr
-  */
-  for (ALL_LIST_ELEMENTS(qpim_upstream_list, up_node, up_nextnode, up)) {
+   * Scan all (S,G) upstreams searching for RPF'(S,G)=neigh_addr
+   */
+  for (ALL_LIST_ELEMENTS(pim_upstream_list, up_node, up_nextnode, up)) {
 
     if (PIM_DEBUG_PIM_TRACE) {
       char neigh_str[100];
@@ -1136,9 +1118,9 @@ pim_upstream_find_new_rpf (void)
   struct pim_upstream *up;
 
   /*
-    Scan all (S,G) upstreams searching for RPF'(S,G)=neigh_addr
-  */
-  for (ALL_LIST_ELEMENTS(qpim_upstream_list, up_node, up_nextnode, up))
+   * Scan all (S,G) upstreams searching for RPF'(S,G)=neigh_addr
+   */
+  for (ALL_LIST_ELEMENTS(pim_upstream_list, up_node, up_nextnode, up))
     {
       if (pim_rpf_addr_is_inaddr_any(&up->rpf))
 	{
@@ -1149,3 +1131,66 @@ pim_upstream_find_new_rpf (void)
 	}
     }
 }
+
+static int
+pim_upstream_compare (const void *arg1, const void *arg2)
+{
+  const struct pim_upstream *up1 = (const struct pim_upstream *)arg1;
+  const struct pim_upstream *up2 = (const struct pim_upstream *)arg2;
+
+  if (ntohl(up1->sg.grp.s_addr) < ntohl(up2->sg.grp.s_addr))
+    return -1;
+
+  if (ntohl(up1->sg.grp.s_addr) > ntohl(up2->sg.grp.s_addr))
+    return 1;
+
+  if (ntohl(up1->sg.src.s_addr) < ntohl(up2->sg.src.s_addr))
+    return -1;
+
+  if (ntohl(up1->sg.src.s_addr) > ntohl(up2->sg.src.s_addr))
+    return 1;
+
+  return 0;
+}
+
+static unsigned int
+pim_upstream_hash_key (void *arg)
+{
+  struct pim_upstream *up = (struct pim_upstream *)arg;
+
+  return jhash_2words (up->sg.src.s_addr, up->sg.grp.s_addr, 0);
+}
+
+void pim_upstream_terminate (void)
+{
+  if (pim_upstream_list)
+    list_free (pim_upstream_list);
+  pim_upstream_list = NULL;
+
+  if (pim_upstream_hash)
+    hash_free (pim_upstream_hash);
+}
+
+static int
+pim_upstream_equal (const void *arg1, const void *arg2)
+{
+  const struct pim_upstream *up1 = (const struct pim_upstream *)arg1;
+  const struct pim_upstream *up2 = (const struct pim_upstream *)arg2;
+
+  if ((up1->sg.grp.s_addr == up2->sg.grp.s_addr) &&
+      (up1->sg.src.s_addr == up2->sg.src.s_addr))
+    return 1;
+
+  return 0;
+}
+
+void pim_upstream_init (void)
+{
+  pim_upstream_hash = hash_create_size (8192, pim_upstream_hash_key,
+					pim_upstream_equal);
+
+  pim_upstream_list = list_new ();
+  pim_upstream_list->del = (void (*)(void *)) pim_upstream_free;
+  pim_upstream_list->cmp = (int (*)(void *, void *)) pim_upstream_compare;
+
+}
diff --git a/pimd/pim_upstream.h b/pimd/pim_upstream.h
index 61f9d3226..70b5b0106 100644
--- a/pimd/pim_upstream.h
+++ b/pimd/pim_upstream.h
@@ -112,10 +112,12 @@ struct pim_upstream {
   int64_t                  state_transition; /* Record current state uptime */
 };
 
+struct list *pim_upstream_list;
+struct hash *pim_upstream_hash;
+
 void pim_upstream_free(struct pim_upstream *up);
 void pim_upstream_delete(struct pim_upstream *up);
 struct pim_upstream *pim_upstream_find (struct prefix_sg *sg);
-struct pim_upstream *pim_upstream_find_non_any (struct prefix_sg *sg);
 struct pim_upstream *pim_upstream_add (struct prefix_sg *sg,
 				      struct interface *ifp, int);
 void pim_upstream_del(struct pim_upstream *up);
@@ -154,4 +156,6 @@ int pim_upstream_inherited_olist (struct pim_upstream *up);
 
 void pim_upstream_find_new_rpf (void);
 
+void pim_upstream_init (void);
+void pim_upstream_terminate (void);
 #endif /* PIM_UPSTREAM_H */
diff --git a/pimd/pim_zebra.c b/pimd/pim_zebra.c
index 1738c5f6f..6115bcbf6 100644
--- a/pimd/pim_zebra.c
+++ b/pimd/pim_zebra.c
@@ -362,7 +362,7 @@ static void scan_upstream_rpf_cache()
   struct listnode     *up_nextnode;
   struct pim_upstream *up;
 
-  for (ALL_LIST_ELEMENTS(qpim_upstream_list, up_node, up_nextnode, up)) {
+  for (ALL_LIST_ELEMENTS(pim_upstream_list, up_node, up_nextnode, up)) {
     struct in_addr      old_rpf_addr;
     struct interface    *old_interface;
     enum pim_rpf_result rpf_result;
diff --git a/pimd/pimd.c b/pimd/pimd.c
index 3a010e81a..82ecdc9fc 100644
--- a/pimd/pimd.c
+++ b/pimd/pimd.c
@@ -54,7 +54,6 @@ struct thread            *qpim_mroute_socket_reader = NULL;
 int                       qpim_mroute_oif_highest_vif_index = -1;
 struct list              *qpim_channel_oil_list = NULL;
 int                       qpim_t_periodic = PIM_DEFAULT_T_PERIODIC; /* Period between Join/Prune Messages */
-struct list              *qpim_upstream_list = NULL;
 struct zclient           *qpim_zclient_update = NULL;
 struct pim_assert_metric  qpim_infinite_assert_metric;
 long                      qpim_rpf_cache_refresh_delay_msec = 2000;
@@ -86,8 +85,7 @@ static void pim_free()
   if (qpim_channel_oil_list)
     list_free(qpim_channel_oil_list);
 
-  if (qpim_upstream_list)
-    list_free(qpim_upstream_list);
+  pim_upstream_terminate ();
 
   if (qpim_static_route_list)
      list_free(qpim_static_route_list);
@@ -116,24 +114,6 @@ pim_channel_oil_compare (struct channel_oil *c1, struct channel_oil *c2)
    return 0;
 }
 
-static int
-pim_upstream_compare (struct pim_upstream *up1, struct pim_upstream *up2)
-{
-   if (ntohl(up1->sg.grp.s_addr) < ntohl(up2->sg.grp.s_addr))
-     return -1;
-
-   if (ntohl(up1->sg.grp.s_addr) > ntohl(up2->sg.grp.s_addr))
-     return 1;
-
-   if (ntohl(up1->sg.src.s_addr) < ntohl(up2->sg.src.s_addr))
-     return -1;
-
-   if (ntohl(up1->sg.src.s_addr) > ntohl(up2->sg.src.s_addr))
-     return 1;
-
-   return 0;
-}
-
 void pim_init()
 {
   srandom(time(NULL));
@@ -159,15 +139,7 @@ void pim_init()
   qpim_channel_oil_list->del = (void (*)(void *)) pim_channel_oil_free;
   qpim_channel_oil_list->cmp = (int (*)(void *, void *)) pim_channel_oil_compare;
 
-  qpim_upstream_list = list_new();
-  if (!qpim_upstream_list) {
-    zlog_err("%s %s: failure: upstream_list=list_new()",
-	     __FILE__, __PRETTY_FUNCTION__);
-    pim_free();
-    return;
-  }
-  qpim_upstream_list->del = (void (*)(void *)) pim_upstream_free;
-  qpim_upstream_list->cmp = (int (*)(void *, void *)) pim_upstream_compare;
+  pim_upstream_init ();
 
   qpim_static_route_list = list_new();
   if (!qpim_static_route_list) {
diff --git a/pimd/pimd.h b/pimd/pimd.h
index 46b3e5ce7..f43507232 100644
--- a/pimd/pimd.h
+++ b/pimd/pimd.h
@@ -97,7 +97,6 @@ int                       qpim_mroute_oif_highest_vif_index;
 struct list              *qpim_channel_oil_list; /* list of struct channel_oil */
 struct in_addr            qpim_all_pim_routers_addr;
 int                       qpim_t_periodic; /* Period between Join/Prune Messages */
-struct list              *qpim_upstream_list; /* list of struct pim_upstream */
 struct zclient           *qpim_zclient_update;
 struct pim_assert_metric  qpim_infinite_assert_metric;
 long                      qpim_rpf_cache_refresh_delay_msec;