pimd: Create channel_oil hash for quicker lookup

When looking up the channel_oil use a hash
to find it.  Keep the list around for quick
walks of the channel oils.

Signed-off-by: Donald Sharp <sharpd@cumulusnetworks.com>

7 files changed, 99 insertions, 48 deletions

diff --git a/pimd/pim_cmd.c b/pimd/pim_cmd.c
index a12a7a230e..5ea8887faf 100644
--- a/pimd/pim_cmd.c
+++ b/pimd/pim_cmd.c
@@ -1311,7 +1311,7 @@ pim_show_state(struct vty *vty, const char *src_or_group, const char *group, u_c
     vty_out(vty, "%sSource           Group            IIF    OIL%s", VTY_NEWLINE, VTY_NEWLINE);
   }
 
-  for (ALL_LIST_ELEMENTS_RO(qpim_channel_oil_list, node, c_oil)) {
+  for (ALL_LIST_ELEMENTS_RO(pim_channel_oil_list, node, c_oil)) {
     char grp_str[100];
     char src_str[100];
     char in_ifname[16];
@@ -2232,7 +2232,7 @@ static void mroute_add_all()
   struct listnode    *node;
   struct channel_oil *c_oil;
 
-  for (ALL_LIST_ELEMENTS_RO(qpim_channel_oil_list, node, c_oil)) {
+  for (ALL_LIST_ELEMENTS_RO(pim_channel_oil_list, node, c_oil)) {
     if (pim_mroute_add(c_oil)) {
       /* just log warning */
       char source_str[100];
@@ -2251,7 +2251,7 @@ static void mroute_del_all()
   struct listnode    *node;
   struct channel_oil *c_oil;
 
-  for (ALL_LIST_ELEMENTS_RO(qpim_channel_oil_list, node, c_oil)) {
+  for (ALL_LIST_ELEMENTS_RO(pim_channel_oil_list, node, c_oil)) {
     if (pim_mroute_del(c_oil)) {
       /* just log warning */
       char source_str[100];
@@ -2829,7 +2829,7 @@ static void show_mroute(struct vty *vty, u_char uj)
   now = pim_time_monotonic_sec();
 
   /* print list of PIM and IGMP routes */
-  for (ALL_LIST_ELEMENTS_RO(qpim_channel_oil_list, node, c_oil)) {
+  for (ALL_LIST_ELEMENTS_RO(pim_channel_oil_list, node, c_oil)) {
     char grp_str[100];
     char src_str[100];
     char in_ifname[16];
@@ -3110,7 +3110,7 @@ static void show_mroute_count(struct vty *vty)
 	  VTY_NEWLINE);
 
   /* Print PIM and IGMP route counts */
-  for (ALL_LIST_ELEMENTS_RO(qpim_channel_oil_list, node, c_oil)) {
+  for (ALL_LIST_ELEMENTS_RO(pim_channel_oil_list, node, c_oil)) {
     char group_str[100]; 
     char source_str[100];
 
diff --git a/pimd/pim_oil.c b/pimd/pim_oil.c
index 9728d6304f..7fe4d8af32 100644
--- a/pimd/pim_oil.c
+++ b/pimd/pim_oil.c
@@ -25,6 +25,8 @@
 #include "memory.h"
 #include "linklist.h"
 #include "if.h"
+#include "hash.h"
+#include "jhash.h"
 
 #include "pimd.h"
 #include "pim_oil.h"
@@ -32,6 +34,75 @@
 #include "pim_iface.h"
 #include "pim_time.h"
 
+struct list *pim_channel_oil_list = NULL;
+struct hash *pim_channel_oil_hash = NULL;
+
+static int
+pim_channel_oil_compare (struct channel_oil *c1, struct channel_oil *c2)
+{
+  if (ntohl(c1->oil.mfcc_mcastgrp.s_addr) < ntohl(c2->oil.mfcc_mcastgrp.s_addr))
+     return -1;
+
+   if (ntohl(c1->oil.mfcc_mcastgrp.s_addr) > ntohl(c2->oil.mfcc_mcastgrp.s_addr))
+     return 1;
+
+   if (ntohl(c1->oil.mfcc_origin.s_addr) < ntohl(c2->oil.mfcc_origin.s_addr))
+     return -1;
+
+   if (ntohl(c1->oil.mfcc_origin.s_addr) > ntohl(c2->oil.mfcc_origin.s_addr))
+     return 1;
+
+   return 0;
+}
+
+static int
+pim_oil_equal (const void *arg1, const void *arg2)
+{
+  const struct channel_oil *c1 = (const struct channel_oil *)arg1;
+  const struct channel_oil *c2 = (const struct channel_oil *)arg2;
+
+  if ((c1->oil.mfcc_mcastgrp.s_addr == c2->oil.mfcc_mcastgrp.s_addr) &&
+      (c2->oil.mfcc_origin.s_addr == c2->oil.mfcc_origin.s_addr))
+    return 1;
+
+  return 0;
+}
+
+static unsigned int
+pim_oil_hash_key (void *arg)
+{
+  struct channel_oil *oil = (struct channel_oil *)arg;
+
+  return jhash_2words (oil->oil.mfcc_mcastgrp.s_addr, oil->oil.mfcc_origin.s_addr, 0);
+}
+
+void
+pim_oil_init (void)
+{
+  pim_channel_oil_hash = hash_create_size (8192, pim_oil_hash_key,
+					   pim_oil_equal);
+
+  pim_channel_oil_list = list_new();
+  if (!pim_channel_oil_list) {
+    zlog_err("%s %s: failure: channel_oil_list=list_new()",
+	     __FILE__, __PRETTY_FUNCTION__);
+    return;
+  }
+  pim_channel_oil_list->del = (void (*)(void *)) pim_channel_oil_free;
+  pim_channel_oil_list->cmp = (int (*)(void *, void *)) pim_channel_oil_compare;
+}
+
+void
+pim_oil_terminate (void)
+{
+  if (pim_channel_oil_list)
+    list_free(pim_channel_oil_list);
+  pim_channel_oil_list = NULL;
+
+  if (pim_channel_oil_hash)
+    hash_free (pim_upstream_hash);
+}
+
 void pim_channel_oil_free(struct channel_oil *c_oil)
 {
   XFREE(MTYPE_PIM_CHANNEL_OIL, c_oil);
@@ -45,7 +116,8 @@ pim_del_channel_oil (struct channel_oil *c_oil)
     into pim_channel_oil_free() because the later is
     called by list_delete_all_node()
   */
-  listnode_delete(qpim_channel_oil_list, c_oil);
+  listnode_delete(pim_channel_oil_list, c_oil);
+  hash_release (pim_channel_oil_hash, c_oil);
 
   pim_channel_oil_free(c_oil);
 }
@@ -73,27 +145,28 @@ pim_add_channel_oil (struct prefix_sg *sg,
 
   c_oil->oil.mfcc_mcastgrp = sg->grp;
   c_oil->oil.mfcc_origin   = sg->src;
+  c_oil = hash_get (pim_channel_oil_hash, c_oil, hash_alloc_intern);
+
   c_oil->oil.mfcc_parent   = input_vif_index;
   c_oil->oil_ref_count     = 1;
   c_oil->installed         = 0;
 
-  listnode_add_sort(qpim_channel_oil_list, c_oil);
+  listnode_add_sort(pim_channel_oil_list, c_oil);
 
   return c_oil;
 }
 
 static struct channel_oil *pim_find_channel_oil(struct prefix_sg *sg)
 {
-  struct listnode    *node;
-  struct channel_oil *c_oil;
+  struct channel_oil *c_oil = NULL;
+  struct channel_oil lookup;
 
-  for (ALL_LIST_ELEMENTS_RO(qpim_channel_oil_list, node, c_oil)) {
-    if ((sg->grp.s_addr == c_oil->oil.mfcc_mcastgrp.s_addr) &&
-	(sg->src.s_addr == c_oil->oil.mfcc_origin.s_addr))
-      return c_oil;
-  }
-  
-  return 0;
+  lookup.oil.mfcc_mcastgrp = sg->grp;
+  lookup.oil.mfcc_origin   = sg->src;
+
+  c_oil = hash_lookup (pim_channel_oil_hash, &lookup);
+
+  return c_oil;
 }
 
 struct channel_oil *pim_channel_oil_add(struct prefix_sg *sg,
diff --git a/pimd/pim_oil.h b/pimd/pim_oil.h
index 4b23b211a9..0c99afb625 100644
--- a/pimd/pim_oil.h
+++ b/pimd/pim_oil.h
@@ -78,6 +78,11 @@ struct channel_oil {
   struct channel_counts cc;
 };
 
+extern struct list *pim_channel_oil_list;
+
+void pim_oil_init (void);
+void pim_oil_terminate (void);
+
 void pim_channel_oil_free(struct channel_oil *c_oil);
 struct channel_oil *pim_channel_oil_add(struct prefix_sg *sg,
 					int input_vif_index);
diff --git a/pimd/pim_upstream.c b/pimd/pim_upstream.c
index 88755ec9fd..a7e40da948 100644
--- a/pimd/pim_upstream.c
+++ b/pimd/pim_upstream.c
@@ -1184,7 +1184,8 @@ pim_upstream_equal (const void *arg1, const void *arg2)
   return 0;
 }
 
-void pim_upstream_init (void)
+void
+pim_upstream_init (void)
 {
   pim_upstream_hash = hash_create_size (8192, pim_upstream_hash_key,
 					pim_upstream_equal);
diff --git a/pimd/pim_zebra.c b/pimd/pim_zebra.c
index 6115bcbf6e..cd0dd5c452 100644
--- a/pimd/pim_zebra.c
+++ b/pimd/pim_zebra.c
@@ -519,7 +519,7 @@ void pim_scan_oil()
   qpim_scan_oil_last = pim_time_monotonic_sec();
   ++qpim_scan_oil_events;
 
-  for (ALL_LIST_ELEMENTS(qpim_channel_oil_list, node, nextnode, c_oil))
+  for (ALL_LIST_ELEMENTS(pim_channel_oil_list, node, nextnode, c_oil))
     pim_scan_individual_oil (c_oil);
 }
 
diff --git a/pimd/pimd.c b/pimd/pimd.c
index 82ecdc9fc5..1608f2d07e 100644
--- a/pimd/pimd.c
+++ b/pimd/pimd.c
@@ -52,7 +52,6 @@ int                       qpim_mroute_socket_fd = -1;
 int64_t                   qpim_mroute_socket_creation = 0; /* timestamp of creation */
 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 zclient           *qpim_zclient_update = NULL;
 struct pim_assert_metric  qpim_infinite_assert_metric;
@@ -82,8 +81,7 @@ static void pim_free()
 {
   pim_ssmpingd_destroy();
 
-  if (qpim_channel_oil_list)
-    list_free(qpim_channel_oil_list);
+  pim_oil_terminate ();
 
   pim_upstream_terminate ();
 
@@ -96,24 +94,6 @@ static void pim_free()
   pim_route_map_terminate();
 }
 
-static int
-pim_channel_oil_compare (struct channel_oil *c1, struct channel_oil *c2)
-{
-   if (ntohl(c1->oil.mfcc_mcastgrp.s_addr) < ntohl(c2->oil.mfcc_mcastgrp.s_addr))
-     return -1;
-
-   if (ntohl(c1->oil.mfcc_mcastgrp.s_addr) > ntohl(c2->oil.mfcc_mcastgrp.s_addr))
-     return 1;
-
-   if (ntohl(c1->oil.mfcc_origin.s_addr) < ntohl(c2->oil.mfcc_origin.s_addr))
-     return -1;
-
-   if (ntohl(c1->oil.mfcc_origin.s_addr) > ntohl(c2->oil.mfcc_origin.s_addr))
-     return 1;
-
-   return 0;
-}
-
 void pim_init()
 {
   srandom(time(NULL));
@@ -130,14 +110,7 @@ void pim_init()
     return;
   }
 
-  qpim_channel_oil_list = list_new();
-  if (!qpim_channel_oil_list) {
-    zlog_err("%s %s: failure: channel_oil_list=list_new()",
-	     __FILE__, __PRETTY_FUNCTION__);
-    return;
-  }
-  qpim_channel_oil_list->del = (void (*)(void *)) pim_channel_oil_free;
-  qpim_channel_oil_list->cmp = (int (*)(void *, void *)) pim_channel_oil_compare;
+  pim_oil_init ();
 
   pim_upstream_init ();
 
diff --git a/pimd/pimd.h b/pimd/pimd.h
index f435072325..fb9cb14ca1 100644
--- a/pimd/pimd.h
+++ b/pimd/pimd.h
@@ -94,7 +94,6 @@ int                       qpim_mroute_socket_fd;
 int64_t                   qpim_mroute_socket_creation; /* timestamp of creation */
 struct thread            *qpim_mroute_socket_reader;
 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 zclient           *qpim_zclient_update;