bgpd: Add a hash for quick lookup in community_list_lookup

The community_list_lookup function in a situation where you have
a large number of communities and route-maps that reference them
becomes a very expensive operation( effectively a linked list walk
per route per route-map you apply per peer that has a routemap that
refereces a community, ecommunity or lcommunity.  This is a very
expensive operation.

In my testbed, I have a full bgp feed that feeds into 14 namespace
view based bgp processes and finally those 14 feed into a final
namespace FRR instance that has route-maps applied to each
incoming peer for in and out:

!
router bgp 65033
 bgp bestpath as-path multipath-relax
 neighbor 192.168.41.1 remote-as external
 neighbor 192.168.42.2 remote-as external
 neighbor 192.168.43.3 remote-as external
 neighbor 192.168.44.4 remote-as external
 neighbor 192.168.45.5 remote-as external
 neighbor 192.168.46.6 remote-as external
 neighbor 192.168.47.7 remote-as external
 neighbor 192.168.48.8 remote-as external
 neighbor 192.168.49.9 remote-as external
 neighbor 192.168.50.10 remote-as external
 neighbor 192.168.51.11 remote-as external
 neighbor 192.168.52.12 remote-as external
 neighbor 192.168.53.13 remote-as external
 neighbor 192.168.54.14 remote-as external
 !
 address-family ipv4 unicast
  neighbor 192.168.42.2 prefix-list two-in in
  neighbor 192.168.42.2 route-map two-in in
  neighbor 192.168.42.2 route-map two-out out
  neighbor 192.168.43.3 prefix-list three-in in
  neighbor 192.168.43.3 route-map three-in in
  neighbor 192.168.43.3 route-map three-out out
  neighbor 192.168.44.4 prefix-list four-in in
  neighbor 192.168.44.4 route-map four-in in
  neighbor 192.168.44.4 route-map four-out out
  neighbor 192.168.45.5 prefix-list five-in in
  neighbor 192.168.45.5 route-map five-in in
  neighbor 192.168.45.5 route-map five-out out
  neighbor 192.168.46.6 prefix-list six-in in
  neighbor 192.168.46.6 route-map six-in in
  neighbor 192.168.46.6 route-map six-out out
  neighbor 192.168.47.7 prefix-list seven-in in
  neighbor 192.168.47.7 route-map seven-in in
  neighbor 192.168.47.7 route-map seven-out out
  neighbor 192.168.48.8 prefix-list eight-in in
  neighbor 192.168.48.8 route-map eight-in in
  neighbor 192.168.48.8 route-map eight-out out
  neighbor 192.168.49.9 prefix-list nine-in in
  neighbor 192.168.49.9 route-map nine-in in
  neighbor 192.168.49.9 route-map nine-out out
  neighbor 192.168.50.10 prefix-list ten-in in
  neighbor 192.168.50.10 route-map ten-in in
  neighbor 192.168.50.10 route-map ten-out out
  neighbor 192.168.51.11 prefix-list eleven-in in
  neighbor 192.168.51.11 route-map eleven-in in
  neighbor 192.168.51.11 route-map eleven-out out
  neighbor 192.168.52.12 prefix-list twelve-in in
  neighbor 192.168.52.12 route-map twelve-in in
  neighbor 192.168.52.12 route-map twelve-out out
  neighbor 192.168.53.13 prefix-list thirteen-in in
  neighbor 192.168.53.13 route-map thirteen-in in
  neighbor 192.168.53.13 route-map thirteen-out out
  neighbor 192.168.54.14 prefix-list fourteen-in in
  neighbor 192.168.54.14 route-map fourteen-in in
  neighbor 192.168.54.14 route-map fourteen-out out
 exit-address-family
!

This configuration on my machine before this change takes about 2:45 to converge
and bgp takes:

Total thread statistics
   16     151715.050    493440      307   3464919      335   7376696 RWTEX TOTAL

CPU time as reported by 'show thread cpu'.

After this change BGP takes 58 seconds to converge and uses:
Total thread statistics
-------------------------
   16      42954.284    350319      122    295743      157   1194820 RWTEX TOTAL

almost 43 seconds of CPU time.

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

0 files changed, 0 insertions, 0 deletions