Login | Register For Free | Help
Search for: (Advanced)

Mailing List Archive: Quagga: Dev
[PATCH 02/25] bgpd: optimize bgp_nexthop_self()
 

Index | Next | Previous | View Flat


jorge at dti2

May 7, 2012, 10:52 AM


Views: 139
Permalink
[PATCH 02/25] bgpd: optimize bgp_nexthop_self()

From: "Jorge Boncompte [DTI2]" <jorge [at] dti2>

This function scores 2nd, profiling a full internet table load. It's called
for every prefix received.
Instead of looping in the interface lists comparing addresses use a hash
to mantain them.

* bgpd.c: Init the own address hash.
* bgp_nexthop.c: Introduce methods to maintain an own address hash.
(bgp_connected_add) add addresses to the hash.
(bgp_connected_delete) delete addresses from the hash.
(bgp_nexthop_self) lookup addresses in the hash. Removed the unused afi_t
parameter.
* bgp_route.c: (bgp_update_main) Micro-optimization, rearranged condition to
not lookup the hash for bogus nexthops (0.0.0.0 or a class D/E address)

Signed-off-by: Jorge Boncompte [DTI2] <jorge [at] dti2>
---
bgpd/bgp_nexthop.c | 106 ++++++++++++++++++++++++++++++++++++++++++++--------
bgpd/bgp_nexthop.h | 3 +-
bgpd/bgp_route.c | 6 +-
bgpd/bgpd.c | 1 +
lib/memtypes.c | 1 +
5 files changed, 97 insertions(+), 20 deletions(-)

diff --git a/bgpd/bgp_nexthop.c b/bgpd/bgp_nexthop.c
index fdf251b..723057b 100644
--- a/bgpd/bgp_nexthop.c
+++ b/bgpd/bgp_nexthop.c
@@ -28,6 +28,8 @@ Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
#include "network.h"
#include "log.h"
#include "memory.h"
+#include "hash.h"
+#include "jhash.h"

#include "bgpd/bgpd.h"
#include "bgpd/bgp_table.h"
@@ -524,6 +526,83 @@ bgp_scan_timer (struct thread *t)

return 0;
}
+
+/* BGP own address structure */
+struct bgp_addr
+{
+ struct in_addr addr;
+ int refcnt;
+};
+
+static struct hash *bgp_address_hash;
+
+static void *
+bgp_address_hash_alloc (void *p)
+{
+ struct in_addr *val = p;
+ struct bgp_addr *addr;
+
+ addr = XMALLOC (MTYPE_BGP_ADDR, sizeof (struct bgp_addr));
+ addr->refcnt = 0;
+ addr->addr.s_addr = val->s_addr;
+
+ return addr;
+}
+
+static unsigned int
+bgp_address_hash_key_make (void *p)
+{
+ const struct bgp_addr *addr = p;
+
+ return jhash_1word(addr->addr.s_addr, 0);
+}
+
+static int
+bgp_address_hash_cmp (const void *p1, const void *p2)
+{
+ const struct bgp_addr *addr1 = p1;
+ const struct bgp_addr *addr2 = p2;
+
+ return addr1->addr.s_addr == addr2->addr.s_addr;
+}
+
+void
+bgp_address_init (void)
+{
+ bgp_address_hash = hash_create (bgp_address_hash_key_make,
+ bgp_address_hash_cmp);
+}
+
+static void
+bgp_address_add (struct prefix *p)
+{
+ struct bgp_addr tmp;
+ struct bgp_addr *addr;
+
+ tmp.addr = p->u.prefix4;
+
+ addr = hash_get (bgp_address_hash, &tmp, bgp_address_hash_alloc);
+ addr->refcnt++;
+}
+
+static void
+bgp_address_del (struct prefix *p)
+{
+ struct bgp_addr tmp;
+ struct bgp_addr *addr;
+
+ tmp.addr = p->u.prefix4;
+
+ addr = hash_lookup (bgp_address_hash, &tmp);
+ addr->refcnt--;
+
+ if (addr->refcnt == 0)
+ {
+ hash_release (bgp_address_hash, addr);
+ XFREE (MTYPE_BGP_ADDR, addr);
+ }
+}
+

struct bgp_connected_ref
{
@@ -557,6 +636,8 @@ bgp_connected_add (struct connected *ifc)
if (prefix_ipv4_any ((struct prefix_ipv4 *) &p))
return;

+ bgp_address_add (addr);
+
rn = bgp_node_get (bgp_connected_table[AFI_IP], (struct prefix *) &p);
if (rn->info)
{
@@ -622,6 +703,8 @@ bgp_connected_delete (struct connected *ifc)
if (prefix_ipv4_any ((struct prefix_ipv4 *) &p))
return;

+ bgp_address_del (addr);
+
rn = bgp_node_lookup (bgp_connected_table[AFI_IP], &p);
if (! rn)
return;
@@ -666,25 +749,16 @@ bgp_connected_delete (struct connected *ifc)
}

int
-bgp_nexthop_self (afi_t afi, struct attr *attr)
+bgp_nexthop_self (struct attr *attr)
{
- struct listnode *node;
- struct listnode *node2;
- struct interface *ifp;
- struct connected *ifc;
- struct prefix *p;
+ struct bgp_addr tmp, *addr;

- for (ALL_LIST_ELEMENTS_RO (iflist, node, ifp))
- {
- for (ALL_LIST_ELEMENTS_RO (ifp->connected, node2, ifc))
- {
- p = ifc->address;
+ tmp.addr = attr->nexthop;
+
+ addr = hash_lookup (bgp_address_hash, &tmp);
+ if (addr)
+ return 1;

- if (p && p->family == AF_INET
- && IPV4_ADDR_SAME (&p->u.prefix4, &attr->nexthop))
- return 1;
- }
- }
return 0;
}

diff --git a/bgpd/bgp_nexthop.h b/bgpd/bgp_nexthop.h
index 874f3bb..6e5350e 100644
--- a/bgpd/bgp_nexthop.h
+++ b/bgpd/bgp_nexthop.h
@@ -55,6 +55,7 @@ extern void bgp_connected_delete (struct connected *c);
extern int bgp_multiaccess_check_v4 (struct in_addr, char *);
extern int bgp_config_write_scan_time (struct vty *);
extern int bgp_nexthop_onlink (afi_t, struct attr *);
-extern int bgp_nexthop_self (afi_t, struct attr *);
+extern int bgp_nexthop_self (struct attr *);
+extern void bgp_address_init (void);

#endif /* _QUAGGA_BGP_NEXTHOP_H */
diff --git a/bgpd/bgp_route.c b/bgpd/bgp_route.c
index d96224d..49e021a 100644
--- a/bgpd/bgp_route.c
+++ b/bgpd/bgp_route.c
@@ -2147,9 +2147,9 @@ bgp_update_main (struct peer *peer, struct prefix *p, struct attr *attr,

/* Next hop must not be 0.0.0.0 nor Class D/E address. Next hop
must not be my own address. */
- if (bgp_nexthop_self (afi, &new_attr)
- || new_attr.nexthop.s_addr == 0
- || IPV4_CLASS_DE (ntohl (new_attr.nexthop.s_addr)))
+ if (new_attr.nexthop.s_addr == 0
+ || IPV4_CLASS_DE (ntohl (new_attr.nexthop.s_addr))
+ || bgp_nexthop_self (&new_attr))
{
reason = "martian next-hop;";
goto filtered;
diff --git a/bgpd/bgpd.c b/bgpd/bgpd.c
index ab27783..30fb091 100644
--- a/bgpd/bgpd.c
+++ b/bgpd/bgpd.c
@@ -5358,6 +5358,7 @@ bgp_init (void)
bgp_dump_init ();
bgp_route_init ();
bgp_route_map_init ();
+ bgp_address_init ();
bgp_scan_init ();
bgp_mplsvpn_init ();

diff --git a/lib/memtypes.c b/lib/memtypes.c
index acbd16b..1723490 100644
--- a/lib/memtypes.c
+++ b/lib/memtypes.c
@@ -150,6 +150,7 @@ struct memory_list memory_list_bgp[] =
{ MTYPE_BGP_DAMP_ARRAY, "BGP Dampening array" },
{ MTYPE_BGP_REGEXP, "BGP regexp" },
{ MTYPE_BGP_AGGREGATE, "BGP aggregate" },
+ { MTYPE_BGP_ADDR, "BGP own address" },
{ -1, NULL }
};

--
1.7.8.3


_______________________________________________
Quagga-dev mailing list
Quagga-dev [at] lists
http://lists.quagga.net/mailman/listinfo/quagga-dev

Subject User Time
[PATCH 02/25] bgpd: optimize bgp_nexthop_self() jorge at dti2 May 7, 2012, 10:52 AM

  Index | Next | Previous | View Flat
 
 


Interested in having your list archived? Contact Gossamer Threads
 
  Web Applications & Managed Hosting Powered by Gossamer Threads Inc.