From 10f9bf3f2021f874e574e4ebae9413bee982ed2b Mon Sep 17 00:00:00 2001 From: "Jorge Boncompte [DTI2]" Date: Mon, 7 May 2012 16:52:52 +0000 Subject: bgpd: optimize bgp_nexthop_self() 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] Signed-off-by: David Lamparter --- 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 fdf251b2..723057b6 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 874f3bba..6e5350ea 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 589c0738..12cb693a 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 ab27783f..30fb091f 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 acbd16b9..1723490f 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 } }; -- cgit v1.2.1