2 * bgp_updgrp.c: BGP update group structures
4 * @copyright Copyright (C) 2014 Cumulus Networks, Inc.
6 * @author Avneesh Sachdev <avneesh@sproute.net>
7 * @author Rajesh Varadarajan <rajesh@sproute.net>
8 * @author Pradosh Mohapatra <pradosh@sproute.net>
10 * This file is part of GNU Zebra.
12 * GNU Zebra is free software; you can redistribute it and/or modify it
13 * under the terms of the GNU General Public License as published by the
14 * Free Software Foundation; either version 2, or (at your option) any
17 * GNU Zebra is distributed in the hope that it will be useful, but
18 * WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
20 * General Public License for more details.
22 * You should have received a copy of the GNU General Public License along
23 * with this program; see the file COPYING; if not, write to the Free Software
24 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
27 #ifndef _QUAGGA_BGP_UPDGRP_H
28 #define _QUAGGA_BGP_UPDGRP_H
30 #include "bgp_advertise.h"
33 * The following three heuristic constants determine how long advertisement to
34 * a subgroup will be delayed after it is created. The intent is to allow
35 * transient changes in peer state (primarily session establishment) to settle,
36 * so that more peers can be grouped together and benefit from sharing
37 * advertisement computations with the subgroup.
39 * These values have a very large impact on initial convergence time; any
40 * changes should be accompanied by careful performance testing at all scales.
42 * The coalesce time 'C' for a new subgroup within a particular BGP instance
43 * 'B' with total number of known peers 'P', established or not, is computed as
46 * C = MIN(BGP_MAX_SUBGROUP_COALESCE_TIME,
47 * BGP_DEFAULT_SUBGROUP_COALESCE_TIME +
48 * (P*BGP_PEER_ADJUST_SUBGROUP_COALESCE_TIME))
50 #define BGP_DEFAULT_SUBGROUP_COALESCE_TIME 1000
51 #define BGP_MAX_SUBGROUP_COALESCE_TIME 10000
52 #define BGP_PEER_ADJUST_SUBGROUP_COALESCE_TIME 50
54 #define PEER_UPDGRP_FLAGS \
55 (PEER_FLAG_LOCAL_AS_NO_PREPEND | PEER_FLAG_LOCAL_AS_REPLACE_AS)
57 #define PEER_UPDGRP_AF_FLAGS \
58 (PEER_FLAG_SEND_COMMUNITY | PEER_FLAG_SEND_EXT_COMMUNITY \
59 | PEER_FLAG_SEND_LARGE_COMMUNITY \
60 | PEER_FLAG_DEFAULT_ORIGINATE | PEER_FLAG_REFLECTOR_CLIENT \
61 | PEER_FLAG_RSERVER_CLIENT | PEER_FLAG_NEXTHOP_SELF \
62 | PEER_FLAG_NEXTHOP_UNCHANGED | PEER_FLAG_FORCE_NEXTHOP_SELF \
63 | PEER_FLAG_AS_PATH_UNCHANGED | PEER_FLAG_MED_UNCHANGED \
64 | PEER_FLAG_NEXTHOP_LOCAL_UNCHANGED | PEER_FLAG_REMOVE_PRIVATE_AS \
65 | PEER_FLAG_REMOVE_PRIVATE_AS_ALL \
66 | PEER_FLAG_REMOVE_PRIVATE_AS_REPLACE \
67 | PEER_FLAG_REMOVE_PRIVATE_AS_ALL_REPLACE \
68 | PEER_FLAG_AS_OVERRIDE)
70 #define PEER_UPDGRP_CAP_FLAGS (PEER_CAP_AS4_RCV)
72 #define PEER_UPDGRP_AF_CAP_FLAGS \
73 (PEER_CAP_ORF_PREFIX_SM_RCV | PEER_CAP_ORF_PREFIX_SM_OLD_RCV \
74 | PEER_CAP_ADDPATH_AF_TX_ADV | PEER_CAP_ADDPATH_AF_RX_RCV \
75 | PEER_CAP_ENHE_AF_NEGO)
77 enum bpacket_attr_vec_type
{ BGP_ATTR_VEC_NH
= 0, BGP_ATTR_VEC_MAX
};
84 #define BPKT_ATTRVEC_FLAGS_UPDATED (1 << 0)
85 #define BPKT_ATTRVEC_FLAGS_RMAP_NH_PEER_ADDRESS (1 << 1)
86 #define BPKT_ATTRVEC_FLAGS_REFLECTED (1 << 2)
87 #define BPKT_ATTRVEC_FLAGS_RMAP_NH_UNCHANGED (1 << 3)
88 #define BPKT_ATTRVEC_FLAGS_RMAP_IPV4_NH_CHANGED (1 << 4)
89 #define BPKT_ATTRVEC_FLAGS_RMAP_IPV6_GNH_CHANGED (1 << 5)
90 #define BPKT_ATTRVEC_FLAGS_RMAP_IPV6_LNH_CHANGED (1 << 6)
91 #define BPKT_ATTRVEC_FLAGS_RMAP_VPNV4_NH_CHANGED (1 << 7)
92 #define BPKT_ATTRVEC_FLAGS_RMAP_VPNV6_GNH_CHANGED (1 << 8)
94 typedef struct bpacket_attr_vec_arr
{
95 bpacket_attr_vec entries
[BGP_ATTR_VEC_MAX
];
96 } bpacket_attr_vec_arr
;
99 /* for being part of an update subgroup's message list */
100 TAILQ_ENTRY(bpacket
) pkt_train
;
102 /* list of peers (well, peer_afs) that the packet needs to be sent to */
103 LIST_HEAD(pkt_peer_list
, peer_af
) peers
;
105 struct stream
*buffer
;
106 bpacket_attr_vec_arr arr
;
111 struct bpacket_queue
{
112 TAILQ_HEAD(pkt_queue
, bpacket
) pkts
;
114 unsigned int conf_max_count
;
115 unsigned int curr_count
;
116 unsigned int hwm_count
;
117 unsigned int max_count_reached_count
;
120 struct update_group
{
121 /* back pointer to the BGP instance */
124 /* list of subgroups that belong to the update group */
125 LIST_HEAD(subgrp_list
, update_subgroup
) subgrps
;
127 /* lazy way to store configuration common to all peers
128 hash function will compute from this data */
138 uint32_t join_events
;
139 uint32_t prune_events
;
140 uint32_t merge_events
;
141 uint32_t updgrp_switch_events
;
142 uint32_t peer_refreshes_combined
;
144 uint32_t split_events
;
145 uint32_t merge_checks_triggered
;
147 uint32_t subgrps_created
;
148 uint32_t subgrps_deleted
;
150 uint32_t num_dbg_en_peers
;
154 * Shorthand for a global statistics counter.
156 #define UPDGRP_GLOBAL_STAT(updgrp, stat) \
157 ((updgrp)->bgp->update_group_stats.stat)
160 * Add the given value to a counter on an update group and the bgp
163 #define UPDGRP_INCR_STAT_BY(updgrp, stat, value) \
165 (updgrp)->stat += (value); \
166 UPDGRP_GLOBAL_STAT(updgrp, stat) += (value); \
170 * Increment a counter on a update group and its parent structures.
172 #define UPDGRP_INCR_STAT(subgrp, stat) UPDGRP_INCR_STAT_BY(subgrp, stat, 1)
174 struct update_subgroup
{
175 /* back pointer to the parent update group */
176 struct update_group
*update_group
;
178 /* list of peers that belong to the subgroup */
179 LIST_HEAD(peer_list
, peer_af
) peers
;
182 /* for being part of an update group's subgroup list */
183 LIST_ENTRY(update_subgroup
) updgrp_train
;
185 struct bpacket_queue pkt_queue
;
188 * List of adj-out structures for this subgroup.
189 * It essentially represents the snapshot of every prefix that
190 * has been advertised to the members of the subgroup
192 TAILQ_HEAD(adjout_queue
, bgp_adj_out
) adjq
;
194 /* packet buffer for update generation */
197 /* We use a separate stream to encode MP_REACH_NLRI for efficient
198 * NLRI packing. peer->obuf_work stores all the other attributes. The
199 * actual packet is then constructed by concatenating the two.
201 struct stream
*scratch
;
203 /* synchronization list and time */
204 struct bgp_synchronize
*sync
;
206 /* send prefix count */
209 /* send prefix count prior to packet update */
212 /* announcement attribute hash */
215 struct thread
*t_coalesce
;
218 struct thread
*t_merge_check
;
220 /* table version that the subgroup has caught up to. */
223 /* version maintained to record adj changes */
224 uint64_t adj_version
;
229 * Identifying information about the subgroup that this subgroup was
234 uint64_t update_group_id
;
235 uint64_t subgroup_id
;
238 uint32_t join_events
;
239 uint32_t prune_events
;
242 * This is bumped up when another subgroup merges into this one.
244 uint32_t merge_events
;
245 uint32_t updgrp_switch_events
;
246 uint32_t peer_refreshes_combined
;
248 uint32_t split_events
;
249 uint32_t merge_checks_triggered
;
254 #define SUBGRP_STATUS_DEFAULT_ORIGINATE (1 << 0)
255 #define SUBGRP_STATUS_FORCE_UPDATES (1 << 1)
256 #define SUBGRP_STATUS_TABLE_REPARSING (1 << 2)
258 * This flag has been added to ensure that the SNT counters
259 * gets incremented and decremented only during the creation
260 * and deletion workflows of default originate,
261 * not during the update workflow.
263 #define SUBGRP_STATUS_PEER_DEFAULT_ORIGINATED (1 << 3)
266 #define SUBGRP_FLAG_NEEDS_REFRESH (1 << 0)
270 * Add the given value to the specified counter on a subgroup and its
273 #define SUBGRP_INCR_STAT_BY(subgrp, stat, value) \
275 (subgrp)->stat += (value); \
276 if ((subgrp)->update_group) \
277 UPDGRP_INCR_STAT_BY((subgrp)->update_group, stat, \
282 * Increment a counter on a subgroup and its parent structures.
284 #define SUBGRP_INCR_STAT(subgrp, stat) SUBGRP_INCR_STAT_BY(subgrp, stat, 1)
287 * Decrement a counter on a subgroup and its parent structures.
289 #define SUBGRP_DECR_STAT(subgrp, stat) SUBGRP_INCR_STAT_BY(subgrp, stat, -1)
291 typedef int (*updgrp_walkcb
)(struct update_group
*updgrp
, void *ctx
);
293 /* really a private structure */
294 struct updwalk_context
{
296 struct bgp_dest
*dest
;
297 struct bgp_path_info
*pi
;
300 enum bgp_policy_type policy_type
;
301 const char *policy_name
;
302 int policy_event_start_flag
;
303 bool policy_route_update
;
308 json_object
*json_updategrps
;
310 #define UPDWALK_FLAGS_ADVQUEUE (1 << 0)
311 #define UPDWALK_FLAGS_ADVERTISED (1 << 1)
314 #define UPDWALK_CONTINUE HASHWALK_CONTINUE
315 #define UPDWALK_ABORT HASHWALK_ABORT
317 #define PAF_PEER(p) ((p)->peer)
318 #define PAF_SUBGRP(p) ((p)->subgroup)
319 #define PAF_UPDGRP(p) ((p)->subgroup->update_group)
320 #define PAF_PKTQ(f) SUBGRP_PKTQ((f)->subgroup)
322 #define UPDGRP_PEER(u) ((u)->conf)
323 #define UPDGRP_AFI(u) ((u)->afi)
324 #define UPDGRP_SAFI(u) ((u)->safi)
325 #define UPDGRP_INST(u) ((u)->bgp)
326 #define UPDGRP_AFFLAGS(u) ((u)->conf->af_flags[UPDGRP_AFI(u)][UPDGRP_SAFI(u)])
327 #define UPDGRP_DBG_ON(u) ((u)->num_dbg_en_peers)
328 #define UPDGRP_PEER_DBG_EN(u) (((u)->num_dbg_en_peers)++)
329 #define UPDGRP_PEER_DBG_DIS(u) (((u)->num_dbg_en_peers)--)
330 #define UPDGRP_PEER_DBG_OFF(u) (u)->num_dbg_en_peers = 0
332 #define SUBGRP_AFI(s) UPDGRP_AFI((s)->update_group)
333 #define SUBGRP_SAFI(s) UPDGRP_SAFI((s)->update_group)
334 #define SUBGRP_PEER(s) UPDGRP_PEER((s)->update_group)
335 #define SUBGRP_PCOUNT(s) ((s)->peer_count)
336 #define SUBGRP_PFIRST(s) LIST_FIRST(&((s)->peers))
337 #define SUBGRP_PKTQ(s) &((s)->pkt_queue)
338 #define SUBGRP_INST(s) UPDGRP_INST((s)->update_group)
339 #define SUBGRP_AFFLAGS(s) UPDGRP_AFFLAGS((s)->update_group)
340 #define SUBGRP_UPDGRP(s) ((s)->update_group)
343 * Walk all subgroups in an update group.
345 #define UPDGRP_FOREACH_SUBGRP(updgrp, subgrp) \
346 LIST_FOREACH (subgrp, &((updgrp)->subgrps), updgrp_train)
348 #define UPDGRP_FOREACH_SUBGRP_SAFE(updgrp, subgrp, tmp_subgrp) \
349 LIST_FOREACH_SAFE (subgrp, &((updgrp)->subgrps), updgrp_train, \
352 #define SUBGRP_FOREACH_PEER(subgrp, paf) \
353 LIST_FOREACH (paf, &(subgrp->peers), subgrp_train)
355 #define SUBGRP_FOREACH_PEER_SAFE(subgrp, paf, temp_paf) \
356 LIST_FOREACH_SAFE (paf, &(subgrp->peers), subgrp_train, temp_paf)
358 #define SUBGRP_FOREACH_ADJ(subgrp, adj) \
359 TAILQ_FOREACH (adj, &(subgrp->adjq), subgrp_adj_train)
361 #define SUBGRP_FOREACH_ADJ_SAFE(subgrp, adj, adj_temp) \
362 TAILQ_FOREACH_SAFE (adj, &(subgrp->adjq), subgrp_adj_train, adj_temp)
366 extern void update_bgp_group_init(struct bgp
*);
367 extern void udpate_bgp_group_free(struct bgp
*);
369 extern void update_group_show(struct bgp
*bgp
, afi_t afi
, safi_t safi
,
370 struct vty
*vty
, uint64_t subgrp_id
, bool uj
);
371 extern void update_group_show_stats(struct bgp
*bgp
, struct vty
*vty
);
372 extern void update_group_adjust_peer(struct peer_af
*paf
);
373 extern int update_group_adjust_soloness(struct peer
*peer
, int set
);
375 extern void update_subgroup_remove_peer(struct update_subgroup
*,
377 extern struct bgp_table
*update_subgroup_rib(struct update_subgroup
*);
378 extern void update_subgroup_split_peer(struct peer_af
*, struct update_group
*);
379 extern bool update_subgroup_check_merge(struct update_subgroup
*, const char *);
380 extern bool update_subgroup_trigger_merge_check(struct update_subgroup
*,
382 extern void update_group_policy_update(struct bgp
*bgp
,
383 enum bgp_policy_type ptype
,
384 const char *pname
, bool route_update
,
386 extern void update_group_af_walk(struct bgp
*bgp
, afi_t afi
, safi_t safi
,
387 updgrp_walkcb cb
, void *ctx
);
388 extern void update_group_walk(struct bgp
*bgp
, updgrp_walkcb cb
, void *ctx
);
389 extern void update_group_periodic_merge(struct bgp
*bgp
);
391 update_group_refresh_default_originate_route_map(struct thread
*thread
);
392 extern void update_group_start_advtimer(struct bgp
*bgp
);
394 extern void update_subgroup_inherit_info(struct update_subgroup
*to
,
395 struct update_subgroup
*from
);
397 /* bgp_updgrp_packet.c */
398 extern struct bpacket
*bpacket_alloc(void);
399 extern void bpacket_free(struct bpacket
*pkt
);
400 extern void bpacket_queue_init(struct bpacket_queue
*q
);
401 extern void bpacket_queue_cleanup(struct bpacket_queue
*q
);
402 extern void bpacket_queue_sanity_check(struct bpacket_queue
*q
);
403 extern struct bpacket
*bpacket_queue_add(struct bpacket_queue
*q
,
405 struct bpacket_attr_vec_arr
*vecarr
);
406 struct bpacket
*bpacket_queue_remove(struct bpacket_queue
*q
);
407 extern struct bpacket
*bpacket_queue_first(struct bpacket_queue
*q
);
408 struct bpacket
*bpacket_queue_last(struct bpacket_queue
*q
);
409 unsigned int bpacket_queue_length(struct bpacket_queue
*q
);
410 unsigned int bpacket_queue_hwm_length(struct bpacket_queue
*q
);
411 bool bpacket_queue_is_full(struct bgp
*bgp
, struct bpacket_queue
*q
);
412 extern void bpacket_queue_advance_peer(struct peer_af
*paf
);
413 extern void bpacket_queue_remove_peer(struct peer_af
*paf
);
414 extern void bpacket_add_peer(struct bpacket
*pkt
, struct peer_af
*paf
);
415 unsigned int bpacket_queue_virtual_length(struct peer_af
*paf
);
416 extern void bpacket_queue_show_vty(struct bpacket_queue
*q
, struct vty
*vty
);
417 bool subgroup_packets_to_build(struct update_subgroup
*subgrp
);
418 extern struct bpacket
*subgroup_update_packet(struct update_subgroup
*s
);
419 extern struct bpacket
*subgroup_withdraw_packet(struct update_subgroup
*s
);
420 extern struct stream
*bpacket_reformat_for_peer(struct bpacket
*pkt
,
421 struct peer_af
*paf
);
422 extern void bpacket_attr_vec_arr_reset(struct bpacket_attr_vec_arr
*vecarr
);
423 extern void bpacket_attr_vec_arr_set_vec(struct bpacket_attr_vec_arr
*vecarr
,
424 enum bpacket_attr_vec_type type
,
425 struct stream
*s
, struct attr
*attr
);
426 extern void subgroup_default_update_packet(struct update_subgroup
*subgrp
,
429 extern void subgroup_default_withdraw_packet(struct update_subgroup
*subgrp
);
431 /* bgp_updgrp_adv.c */
432 extern struct bgp_advertise
*
433 bgp_advertise_clean_subgroup(struct update_subgroup
*subgrp
,
434 struct bgp_adj_out
*adj
);
435 extern void update_group_show_adj_queue(struct bgp
*bgp
, afi_t afi
, safi_t safi
,
436 struct vty
*vty
, uint64_t id
);
437 extern void update_group_show_advertised(struct bgp
*bgp
, afi_t afi
,
438 safi_t safi
, struct vty
*vty
,
440 extern void update_group_show_packet_queue(struct bgp
*bgp
, afi_t afi
,
441 safi_t safi
, struct vty
*vty
,
443 extern void subgroup_announce_route(struct update_subgroup
*subgrp
);
444 extern void subgroup_announce_all(struct update_subgroup
*subgrp
);
446 extern void subgroup_default_originate(struct update_subgroup
*subgrp
,
448 extern void group_announce_route(struct bgp
*bgp
, afi_t afi
, safi_t safi
,
449 struct bgp_dest
*dest
,
450 struct bgp_path_info
*pi
);
451 extern void subgroup_clear_table(struct update_subgroup
*subgrp
);
452 extern void update_group_announce(struct bgp
*bgp
);
453 extern void update_group_announce_rrclients(struct bgp
*bgp
);
454 extern void peer_af_announce_route(struct peer_af
*paf
, int combine
);
455 extern struct bgp_adj_out
*bgp_adj_out_alloc(struct update_subgroup
*subgrp
,
456 struct bgp_dest
*dest
,
457 uint32_t addpath_tx_id
);
458 extern void bgp_adj_out_remove_subgroup(struct bgp_dest
*dest
,
459 struct bgp_adj_out
*adj
,
460 struct update_subgroup
*subgrp
);
461 extern void bgp_adj_out_set_subgroup(struct bgp_dest
*dest
,
462 struct update_subgroup
*subgrp
,
464 struct bgp_path_info
*path
);
465 extern void bgp_adj_out_unset_subgroup(struct bgp_dest
*dest
,
466 struct update_subgroup
*subgrp
,
467 char withdraw
, uint32_t addpath_tx_id
);
468 void subgroup_announce_table(struct update_subgroup
*subgrp
,
469 struct bgp_table
*table
);
470 extern void subgroup_trigger_write(struct update_subgroup
*subgrp
);
472 extern int update_group_clear_update_dbg(struct update_group
*updgrp
,
475 extern void update_bgp_group_free(struct bgp
*bgp
);
476 extern bool bgp_addpath_encode_tx(struct peer
*peer
, afi_t afi
, safi_t safi
);
477 extern bool bgp_check_selected(struct bgp_path_info
*bpi
, struct peer
*peer
,
478 bool addpath_capable
, afi_t afi
, safi_t safi
);
485 * bpacket_queue_is_empty
487 static inline int bpacket_queue_is_empty(struct bpacket_queue
*queue
)
491 * The packet queue is empty if it only contains a sentinel.
493 if (queue
->curr_count
!= 1)
496 assert(bpacket_queue_first(queue
)->buffer
== NULL
);
503 * Returns the packet after the given packet in a bpacket queue.
505 static inline struct bpacket
*bpacket_next(struct bpacket
*pkt
)
507 return TAILQ_NEXT(pkt
, pkt_train
);
511 * update_group_adjust_peer_afs
513 * Adjust all peer_af structures for the given peer.
515 static inline void update_group_adjust_peer_afs(struct peer
*peer
)
520 for (afidx
= BGP_AF_START
; afidx
< BGP_AF_MAX
; afidx
++) {
521 paf
= peer
->peer_af_array
[afidx
];
523 update_group_adjust_peer(paf
);
528 * update_group_remove_peer_afs
530 * Remove all peer_af structures for the given peer from their subgroups.
532 static inline void update_group_remove_peer_afs(struct peer
*peer
)
537 for (afidx
= BGP_AF_START
; afidx
< BGP_AF_MAX
; afidx
++) {
538 paf
= peer
->peer_af_array
[afidx
];
540 update_subgroup_remove_peer(PAF_SUBGRP(paf
), paf
);
545 * update_subgroup_needs_refresh
548 update_subgroup_needs_refresh(const struct update_subgroup
*subgrp
)
550 if (CHECK_FLAG(subgrp
->flags
, SUBGRP_FLAG_NEEDS_REFRESH
))
557 * update_subgroup_set_needs_refresh
560 update_subgroup_set_needs_refresh(struct update_subgroup
*subgrp
, int value
)
563 SET_FLAG(subgrp
->flags
, SUBGRP_FLAG_NEEDS_REFRESH
);
565 UNSET_FLAG(subgrp
->flags
, SUBGRP_FLAG_NEEDS_REFRESH
);
568 static inline struct update_subgroup
*peer_subgroup(struct peer
*peer
,
569 afi_t afi
, safi_t safi
)
573 paf
= peer_af_find(peer
, afi
, safi
);
575 return PAF_SUBGRP(paf
);
580 * update_group_adjust_peer_afs
582 * Adjust all peer_af structures for the given peer.
584 static inline void bgp_announce_peer(struct peer
*peer
)
589 for (afidx
= BGP_AF_START
; afidx
< BGP_AF_MAX
; afidx
++) {
590 paf
= peer
->peer_af_array
[afidx
];
592 subgroup_announce_all(PAF_SUBGRP(paf
));
597 * advertise_list_is_empty
599 static inline int advertise_list_is_empty(struct update_subgroup
*subgrp
)
601 if (bgp_adv_fifo_count(&subgrp
->sync
->update
)
602 || bgp_adv_fifo_count(&subgrp
->sync
->withdraw
)
603 || bgp_adv_fifo_count(&subgrp
->sync
->withdraw_low
)) {
610 #endif /* _QUAGGA_BGP_UPDGRP_H */