]>
git.proxmox.com Git - mirror_frr.git/blob - bgpd/bgp_damp.c
2 * Copyright (C) 2001 IP Infusion Inc.
4 * This file is part of GNU Zebra.
6 * GNU Zebra is free software; you can redistribute it and/or modify it
7 * under the terms of the GNU General Public License as published by the
8 * Free Software Foundation; either version 2, or (at your option) any
11 * GNU Zebra is distributed in the hope that it will be useful, but
12 * WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * General Public License for more details.
16 * You should have received a copy of the GNU General Public License along
17 * with this program; see the file COPYING; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
32 #include "bgpd/bgpd.h"
33 #include "bgpd/bgp_damp.h"
34 #include "bgpd/bgp_table.h"
35 #include "bgpd/bgp_route.h"
36 #include "bgpd/bgp_attr.h"
37 #include "bgpd/bgp_advertise.h"
39 /* Global variable to access damping configuration */
40 static struct bgp_damp_config damp
[AFI_MAX
][SAFI_MAX
];
42 /* Utility macro to add and delete BGP dampening information to no
44 #define BGP_DAMP_LIST_ADD(N, A) BGP_PATH_INFO_ADD(N, A, no_reuse_list)
45 #define BGP_DAMP_LIST_DEL(N, A) BGP_PATH_INFO_DEL(N, A, no_reuse_list)
47 /* Calculate reuse list index by penalty value. */
48 static int bgp_reuse_index(int penalty
, struct bgp_damp_config
*bdc
)
53 i
= (int)(((double)penalty
/ bdc
->reuse_limit
- 1.0)
56 if (i
>= bdc
->reuse_index_size
)
57 i
= bdc
->reuse_index_size
- 1;
59 index
= bdc
->reuse_index
[i
] - bdc
->reuse_index
[0];
61 return (bdc
->reuse_offset
+ index
) % bdc
->reuse_list_size
;
64 /* Add BGP dampening information to reuse list. */
65 static void bgp_reuse_list_add(struct bgp_damp_info
*bdi
,
66 struct bgp_damp_config
*bdc
)
70 index
= bdi
->index
= bgp_reuse_index(bdi
->penalty
, bdc
);
73 bdi
->next
= bdc
->reuse_list
[index
];
74 if (bdc
->reuse_list
[index
])
75 bdc
->reuse_list
[index
]->prev
= bdi
;
76 bdc
->reuse_list
[index
] = bdi
;
79 /* Delete BGP dampening information from reuse list. */
80 static void bgp_reuse_list_delete(struct bgp_damp_info
*bdi
,
81 struct bgp_damp_config
*bdc
)
84 bdi
->next
->prev
= bdi
->prev
;
86 bdi
->prev
->next
= bdi
->next
;
88 bdc
->reuse_list
[bdi
->index
] = bdi
->next
;
91 /* Return decayed penalty value. */
92 int bgp_damp_decay(time_t tdiff
, int penalty
, struct bgp_damp_config
*bdc
)
96 i
= (int)((double)tdiff
/ DELTA_T
);
101 if (i
>= bdc
->decay_array_size
)
104 return (int)(penalty
* bdc
->decay_array
[i
]);
107 /* Handler of reuse timer event. Each route in the current reuse-list
108 is evaluated. RFC2439 Section 4.8.7. */
109 static int bgp_reuse_timer(struct thread
*t
)
111 struct bgp_damp_info
*bdi
;
112 struct bgp_damp_info
*next
;
113 time_t t_now
, t_diff
;
115 struct bgp_damp_config
*bdc
= THREAD_ARG(t
);
118 thread_add_timer(bm
->master
, bgp_reuse_timer
, bdc
, DELTA_REUSE
,
123 /* 1. save a pointer to the current zeroth queue head and zero the
125 bdi
= bdc
->reuse_list
[bdc
->reuse_offset
];
126 bdc
->reuse_list
[bdc
->reuse_offset
] = NULL
;
128 /* 2. set offset = modulo reuse-list-size ( offset + 1 ), thereby
129 rotating the circular queue of list-heads. */
130 bdc
->reuse_offset
= (bdc
->reuse_offset
+ 1) % bdc
->reuse_list_size
;
132 /* 3. if ( the saved list head pointer is non-empty ) */
133 for (; bdi
; bdi
= next
) {
134 struct bgp
*bgp
= bdi
->path
->peer
->bgp
;
138 /* Set t-diff = t-now - t-updated. */
139 t_diff
= t_now
- bdi
->t_updated
;
141 /* Set figure-of-merit = figure-of-merit * decay-array-ok
143 bdi
->penalty
= bgp_damp_decay(t_diff
, bdi
->penalty
, bdc
);
145 /* Set t-updated = t-now. */
146 bdi
->t_updated
= t_now
;
148 /* if (figure-of-merit < reuse). */
149 if (bdi
->penalty
< bdc
->reuse_limit
) {
150 /* Reuse the route. */
151 bgp_path_info_unset_flag(bdi
->rn
, bdi
->path
,
153 bdi
->suppress_time
= 0;
155 if (bdi
->lastrecord
== BGP_RECORD_UPDATE
) {
156 bgp_path_info_unset_flag(bdi
->rn
, bdi
->path
,
158 bgp_aggregate_increment(bgp
, &bdi
->rn
->p
,
161 bgp_process(bgp
, bdi
->rn
, bdi
->afi
, bdi
->safi
);
164 if (bdi
->penalty
<= bdc
->reuse_limit
/ 2.0)
165 bgp_damp_info_free(bdi
, 1, bdc
->afi
, bdc
->safi
);
167 BGP_DAMP_LIST_ADD(bdc
, bdi
);
169 /* Re-insert into another list (See RFC2439 Section
171 bgp_reuse_list_add(bdi
, bdc
);
177 /* A route becomes unreachable (RFC2439 Section 4.8.2). */
178 int bgp_damp_withdraw(struct bgp_path_info
*path
, struct bgp_node
*rn
,
179 afi_t afi
, safi_t safi
, int attr_change
)
182 struct bgp_damp_info
*bdi
= NULL
;
183 unsigned int last_penalty
= 0;
184 struct bgp_damp_config
*bdc
= &damp
[afi
][safi
];
188 /* Processing Unreachable Messages. */
190 bdi
= path
->extra
->damp_info
;
193 /* If there is no previous stability history. */
196 1. allocate a damping structure.
197 2. set figure-of-merit = 1.
198 3. withdraw the route. */
200 bdi
= XCALLOC(MTYPE_BGP_DAMP_INFO
,
201 sizeof(struct bgp_damp_info
));
205 (attr_change
? DEFAULT_PENALTY
/ 2 : DEFAULT_PENALTY
);
207 bdi
->start_time
= t_now
;
208 bdi
->suppress_time
= 0;
212 (bgp_path_info_extra_get(path
))->damp_info
= bdi
;
213 BGP_DAMP_LIST_ADD(bdc
, bdi
);
215 last_penalty
= bdi
->penalty
;
217 /* 1. Set t-diff = t-now - t-updated. */
218 bdi
->penalty
= (bgp_damp_decay(t_now
- bdi
->t_updated
,
220 + (attr_change
? DEFAULT_PENALTY
/ 2
223 if (bdi
->penalty
> bdc
->ceiling
)
224 bdi
->penalty
= bdc
->ceiling
;
229 assert((rn
== bdi
->rn
) && (path
== bdi
->path
));
231 bdi
->lastrecord
= BGP_RECORD_WITHDRAW
;
232 bdi
->t_updated
= t_now
;
234 /* Make this route as historical status. */
235 bgp_path_info_set_flag(rn
, path
, BGP_PATH_HISTORY
);
237 /* Remove the route from a reuse list if it is on one. */
238 if (CHECK_FLAG(bdi
->path
->flags
, BGP_PATH_DAMPED
)) {
239 /* If decay rate isn't equal to 0, reinsert brn. */
240 if (bdi
->penalty
!= last_penalty
&& bdi
->index
>= 0) {
241 bgp_reuse_list_delete(bdi
, bdc
);
242 bgp_reuse_list_add(bdi
, bdc
);
244 return BGP_DAMP_SUPPRESSED
;
247 /* If not suppressed before, do annonunce this withdraw and
248 insert into reuse_list. */
249 if (bdi
->penalty
>= bdc
->suppress_value
) {
250 bgp_path_info_set_flag(rn
, path
, BGP_PATH_DAMPED
);
251 bdi
->suppress_time
= t_now
;
252 BGP_DAMP_LIST_DEL(bdc
, bdi
);
253 bgp_reuse_list_add(bdi
, bdc
);
256 return BGP_DAMP_USED
;
259 int bgp_damp_update(struct bgp_path_info
*path
, struct bgp_node
*rn
, afi_t afi
,
263 struct bgp_damp_info
*bdi
;
265 struct bgp_damp_config
*bdc
= &damp
[afi
][safi
];
267 if (!path
->extra
|| !((bdi
= path
->extra
->damp_info
)))
268 return BGP_DAMP_USED
;
271 bgp_path_info_unset_flag(rn
, path
, BGP_PATH_HISTORY
);
273 bdi
->lastrecord
= BGP_RECORD_UPDATE
;
275 bgp_damp_decay(t_now
- bdi
->t_updated
, bdi
->penalty
, bdc
);
277 if (!CHECK_FLAG(bdi
->path
->flags
, BGP_PATH_DAMPED
)
278 && (bdi
->penalty
< bdc
->suppress_value
))
279 status
= BGP_DAMP_USED
;
280 else if (CHECK_FLAG(bdi
->path
->flags
, BGP_PATH_DAMPED
)
281 && (bdi
->penalty
< bdc
->reuse_limit
)) {
282 bgp_path_info_unset_flag(rn
, path
, BGP_PATH_DAMPED
);
283 bgp_reuse_list_delete(bdi
, bdc
);
284 BGP_DAMP_LIST_ADD(bdc
, bdi
);
285 bdi
->suppress_time
= 0;
286 status
= BGP_DAMP_USED
;
288 status
= BGP_DAMP_SUPPRESSED
;
290 if (bdi
->penalty
> bdc
->reuse_limit
/ 2.0)
291 bdi
->t_updated
= t_now
;
293 bgp_damp_info_free(bdi
, 0, afi
, safi
);
298 void bgp_damp_info_free(struct bgp_damp_info
*bdi
, int withdraw
, afi_t afi
,
301 struct bgp_path_info
*path
;
302 struct bgp_damp_config
*bdc
= &damp
[afi
][safi
];
308 path
->extra
->damp_info
= NULL
;
310 if (CHECK_FLAG(path
->flags
, BGP_PATH_DAMPED
))
311 bgp_reuse_list_delete(bdi
, bdc
);
313 BGP_DAMP_LIST_DEL(bdc
, bdi
);
315 bgp_path_info_unset_flag(bdi
->rn
, path
,
316 BGP_PATH_HISTORY
| BGP_PATH_DAMPED
);
318 if (bdi
->lastrecord
== BGP_RECORD_WITHDRAW
&& withdraw
)
319 bgp_path_info_delete(bdi
->rn
, path
);
321 XFREE(MTYPE_BGP_DAMP_INFO
, bdi
);
324 static void bgp_damp_parameter_set(int hlife
, int reuse
, int sup
, int maxsup
,
325 struct bgp_damp_config
*bdc
)
327 double reuse_max_ratio
;
331 bdc
->suppress_value
= sup
;
332 bdc
->half_life
= hlife
;
333 bdc
->reuse_limit
= reuse
;
334 bdc
->max_suppress_time
= maxsup
;
336 /* Initialize params per bgp_damp_config. */
337 bdc
->reuse_index_size
= REUSE_ARRAY_SIZE
;
339 bdc
->ceiling
= (int)(bdc
->reuse_limit
340 * (pow(2, (double)bdc
->max_suppress_time
343 /* Decay-array computations */
344 bdc
->decay_array_size
= ceil((double)bdc
->max_suppress_time
/ DELTA_T
);
345 bdc
->decay_array
= XMALLOC(MTYPE_BGP_DAMP_ARRAY
,
346 sizeof(double) * (bdc
->decay_array_size
));
347 bdc
->decay_array
[0] = 1.0;
348 bdc
->decay_array
[1] =
349 exp((1.0 / ((double)bdc
->half_life
/ DELTA_T
)) * log(0.5));
351 /* Calculate decay values for all possible times */
352 for (i
= 2; i
< bdc
->decay_array_size
; i
++)
353 bdc
->decay_array
[i
] =
354 bdc
->decay_array
[i
- 1] * bdc
->decay_array
[1];
356 /* Reuse-list computations */
357 i
= ceil((double)bdc
->max_suppress_time
/ DELTA_REUSE
) + 1;
358 if (i
> REUSE_LIST_SIZE
|| i
== 0)
360 bdc
->reuse_list_size
= i
;
363 XCALLOC(MTYPE_BGP_DAMP_ARRAY
,
364 bdc
->reuse_list_size
* sizeof(struct bgp_reuse_node
*));
366 /* Reuse-array computations */
367 bdc
->reuse_index
= XCALLOC(MTYPE_BGP_DAMP_ARRAY
,
368 sizeof(int) * bdc
->reuse_index_size
);
370 reuse_max_ratio
= (double)bdc
->ceiling
/ bdc
->reuse_limit
;
371 j
= (exp((double)bdc
->max_suppress_time
/ bdc
->half_life
) * log10(2.0));
372 if (reuse_max_ratio
> j
&& j
!= 0)
376 (double)bdc
->reuse_index_size
/ (reuse_max_ratio
- 1);
378 for (i
= 0; i
< bdc
->reuse_index_size
; i
++) {
379 bdc
->reuse_index
[i
] =
380 (int)(((double)bdc
->half_life
/ DELTA_REUSE
)
384 + ((double)i
/ bdc
->scale_factor
))))
389 int bgp_damp_enable(struct bgp
*bgp
, afi_t afi
, safi_t safi
, time_t half
,
390 unsigned int reuse
, unsigned int suppress
, time_t max
)
392 struct bgp_damp_config
*bdc
= &damp
[afi
][safi
];
394 if (CHECK_FLAG(bgp
->af_flags
[afi
][safi
], BGP_CONFIG_DAMPENING
)) {
395 if (bdc
->half_life
== half
&& bdc
->reuse_limit
== reuse
396 && bdc
->suppress_value
== suppress
397 && bdc
->max_suppress_time
== max
)
399 bgp_damp_disable(bgp
, afi
, safi
);
402 SET_FLAG(bgp
->af_flags
[afi
][safi
], BGP_CONFIG_DAMPENING
);
403 bgp_damp_parameter_set(half
, reuse
, suppress
, max
, bdc
);
405 /* Register reuse timer. */
406 thread_add_timer(bm
->master
, bgp_reuse_timer
, bdc
, DELTA_REUSE
,
412 static void bgp_damp_config_clean(struct bgp_damp_config
*bdc
)
414 /* Free decay array */
415 XFREE(MTYPE_BGP_DAMP_ARRAY
, bdc
->decay_array
);
416 bdc
->decay_array_size
= 0;
418 /* Free reuse index array */
419 XFREE(MTYPE_BGP_DAMP_ARRAY
, bdc
->reuse_index
);
420 bdc
->reuse_index_size
= 0;
422 /* Free reuse list array. */
423 XFREE(MTYPE_BGP_DAMP_ARRAY
, bdc
->reuse_list
);
424 bdc
->reuse_list_size
= 0;
427 /* Clean all the bgp_damp_info stored in reuse_list. */
428 void bgp_damp_info_clean(afi_t afi
, safi_t safi
)
431 struct bgp_damp_info
*bdi
, *next
;
432 struct bgp_damp_config
*bdc
= &damp
[afi
][safi
];
434 bdc
->reuse_offset
= 0;
436 for (i
= 0; i
< bdc
->reuse_list_size
; i
++) {
437 if (!bdc
->reuse_list
[i
])
440 for (bdi
= bdc
->reuse_list
[i
]; bdi
; bdi
= next
) {
442 bgp_damp_info_free(bdi
, 1, afi
, safi
);
444 bdc
->reuse_list
[i
] = NULL
;
447 for (bdi
= bdc
->no_reuse_list
; bdi
; bdi
= next
) {
449 bgp_damp_info_free(bdi
, 1, afi
, safi
);
451 bdc
->no_reuse_list
= NULL
;
454 int bgp_damp_disable(struct bgp
*bgp
, afi_t afi
, safi_t safi
)
456 struct bgp_damp_config
*bdc
= &damp
[afi
][safi
];
457 /* If it wasn't enabled, there's nothing to do. */
458 if (!CHECK_FLAG(bgp
->af_flags
[afi
][safi
], BGP_CONFIG_DAMPENING
))
461 /* Cancel reuse thread. */
463 thread_cancel(bdc
->t_reuse
);
466 /* Clean BGP dampening information. */
467 bgp_damp_info_clean(afi
, safi
);
469 /* Clear configuration */
470 bgp_damp_config_clean(bdc
);
472 UNSET_FLAG(bgp
->af_flags
[afi
][safi
], BGP_CONFIG_DAMPENING
);
476 void bgp_config_write_damp(struct vty
*vty
, afi_t afi
, safi_t safi
)
478 if (damp
[afi
][safi
].half_life
== DEFAULT_HALF_LIFE
* 60
479 && damp
[afi
][safi
].reuse_limit
== DEFAULT_REUSE
480 && damp
[afi
][safi
].suppress_value
== DEFAULT_SUPPRESS
481 && damp
[afi
][safi
].max_suppress_time
482 == damp
[afi
][safi
].half_life
* 4)
483 vty_out(vty
, " bgp dampening\n");
484 else if (damp
[afi
][safi
].half_life
!= DEFAULT_HALF_LIFE
* 60
485 && damp
[afi
][safi
].reuse_limit
== DEFAULT_REUSE
486 && damp
[afi
][safi
].suppress_value
== DEFAULT_SUPPRESS
487 && damp
[afi
][safi
].max_suppress_time
488 == damp
[afi
][safi
].half_life
* 4)
489 vty_out(vty
, " bgp dampening %lld\n",
490 damp
[afi
][safi
].half_life
/ 60LL);
492 vty_out(vty
, " bgp dampening %lld %d %d %lld\n",
493 damp
[afi
][safi
].half_life
/ 60LL,
494 damp
[afi
][safi
].reuse_limit
,
495 damp
[afi
][safi
].suppress_value
,
496 damp
[afi
][safi
].max_suppress_time
/ 60LL);
499 static const char *bgp_get_reuse_time(unsigned int penalty
, char *buf
,
500 size_t len
, afi_t afi
, safi_t safi
,
501 bool use_json
, json_object
*json
)
503 time_t reuse_time
= 0;
504 struct tm
*tm
= NULL
;
507 if (penalty
> damp
[afi
][safi
].reuse_limit
) {
508 reuse_time
= (int)(DELTA_T
509 * ((log((double)damp
[afi
][safi
].reuse_limit
511 / (log(damp
[afi
][safi
].decay_array
[1]))));
513 if (reuse_time
> damp
[afi
][safi
].max_suppress_time
)
514 reuse_time
= damp
[afi
][safi
].max_suppress_time
;
516 tm
= gmtime(&reuse_time
);
520 /* Making formatted timer strings. */
521 if (reuse_time
== 0) {
523 json_object_int_add(json
, "reuseTimerMsecs", 0);
525 snprintf(buf
, len
, "00:00:00");
526 } else if (reuse_time
< ONE_DAY_SECOND
) {
528 time_store
= (3600000 * tm
->tm_hour
)
529 + (60000 * tm
->tm_min
)
530 + (1000 * tm
->tm_sec
);
531 json_object_int_add(json
, "reuseTimerMsecs",
534 snprintf(buf
, len
, "%02d:%02d:%02d", tm
->tm_hour
,
535 tm
->tm_min
, tm
->tm_sec
);
536 } else if (reuse_time
< ONE_WEEK_SECOND
) {
538 time_store
= (86400000 * tm
->tm_yday
)
539 + (3600000 * tm
->tm_hour
)
540 + (60000 * tm
->tm_min
)
541 + (1000 * tm
->tm_sec
);
542 json_object_int_add(json
, "reuseTimerMsecs",
545 snprintf(buf
, len
, "%dd%02dh%02dm", tm
->tm_yday
,
546 tm
->tm_hour
, tm
->tm_min
);
550 (604800000 * tm
->tm_yday
/ 7)
552 * (tm
->tm_yday
- ((tm
->tm_yday
/ 7) * 7)))
553 + (3600000 * tm
->tm_hour
) + (60000 * tm
->tm_min
)
554 + (1000 * tm
->tm_sec
);
555 json_object_int_add(json
, "reuseTimerMsecs",
558 snprintf(buf
, len
, "%02dw%dd%02dh", tm
->tm_yday
/ 7,
559 tm
->tm_yday
- ((tm
->tm_yday
/ 7) * 7),
566 void bgp_damp_info_vty(struct vty
*vty
, struct bgp_path_info
*path
, afi_t afi
,
567 safi_t safi
, json_object
*json_path
)
569 struct bgp_damp_info
*bdi
;
570 time_t t_now
, t_diff
;
571 char timebuf
[BGP_UPTIME_LEN
];
573 struct bgp_damp_config
*bdc
= &damp
[afi
][safi
];
578 /* BGP dampening information. */
579 bdi
= path
->extra
->damp_info
;
581 /* If dampening is not enabled or there is no dampening information,
582 return immediately. */
586 /* Calculate new penalty. */
588 t_diff
= t_now
- bdi
->t_updated
;
589 penalty
= bgp_damp_decay(t_diff
, bdi
->penalty
, bdc
);
592 json_object_int_add(json_path
, "dampeningPenalty", penalty
);
593 json_object_int_add(json_path
, "dampeningFlapCount", bdi
->flap
);
594 peer_uptime(bdi
->start_time
, timebuf
, BGP_UPTIME_LEN
, 1,
597 if (CHECK_FLAG(path
->flags
, BGP_PATH_DAMPED
)
598 && !CHECK_FLAG(path
->flags
, BGP_PATH_HISTORY
))
599 bgp_get_reuse_time(penalty
, timebuf
, BGP_UPTIME_LEN
,
600 afi
, safi
, 1, json_path
);
603 " Dampinfo: penalty %d, flapped %d times in %s",
605 peer_uptime(bdi
->start_time
, timebuf
, BGP_UPTIME_LEN
, 0,
608 if (CHECK_FLAG(path
->flags
, BGP_PATH_DAMPED
)
609 && !CHECK_FLAG(path
->flags
, BGP_PATH_HISTORY
))
610 vty_out(vty
, ", reuse in %s",
611 bgp_get_reuse_time(penalty
, timebuf
,
612 BGP_UPTIME_LEN
, afi
, safi
, 0,
619 const char *bgp_damp_reuse_time_vty(struct vty
*vty
, struct bgp_path_info
*path
,
620 char *timebuf
, size_t len
, afi_t afi
,
621 safi_t safi
, bool use_json
,
624 struct bgp_damp_info
*bdi
;
625 time_t t_now
, t_diff
;
627 struct bgp_damp_config
*bdc
= &damp
[afi
][safi
];
632 /* BGP dampening information. */
633 bdi
= path
->extra
->damp_info
;
635 /* If dampening is not enabled or there is no dampening information,
636 return immediately. */
640 /* Calculate new penalty. */
642 t_diff
= t_now
- bdi
->t_updated
;
643 penalty
= bgp_damp_decay(t_diff
, bdi
->penalty
, bdc
);
645 return bgp_get_reuse_time(penalty
, timebuf
, len
, afi
, safi
, use_json
,
649 int bgp_show_dampening_parameters(struct vty
*vty
, afi_t afi
, safi_t safi
)
652 bgp
= bgp_get_default();
655 vty_out(vty
, "No BGP process is configured\n");
659 if (CHECK_FLAG(bgp
->af_flags
[afi
][safi
], BGP_CONFIG_DAMPENING
)) {
660 vty_out(vty
, "Half-life time: %lld min\n",
661 (long long)damp
[afi
][safi
].half_life
/ 60);
662 vty_out(vty
, "Reuse penalty: %d\n",
663 damp
[afi
][safi
].reuse_limit
);
664 vty_out(vty
, "Suppress penalty: %d\n",
665 damp
[afi
][safi
].suppress_value
);
666 vty_out(vty
, "Max suppress time: %lld min\n",
667 (long long)damp
[afi
][safi
].max_suppress_time
/ 60);
668 vty_out(vty
, "Max suppress penalty: %u\n",
669 damp
[afi
][safi
].ceiling
);
672 vty_out(vty
, "dampening not enabled for %s\n",
673 afi
== AFI_IP
? "IPv4" : "IPv6");