1/* BGP flap dampening 2 Copyright (C) 2001 IP Infusion Inc. 3 4This file is part of GNU Zebra. 5 6GNU Zebra is free software; you can redistribute it and/or modify it 7under the terms of the GNU General Public License as published by the 8Free Software Foundation; either version 2, or (at your option) any 9later version. 10 11GNU Zebra is distributed in the hope that it will be useful, but 12WITHOUT ANY WARRANTY; without even the implied warranty of 13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14General Public License for more details. 15 16You should have received a copy of the GNU General Public License 17along with GNU Zebra; see the file COPYING. If not, write to the Free 18Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 1902111-1307, USA. */ 20 21#include <zebra.h> 22#include <math.h> 23 24#include "prefix.h" 25#include "memory.h" 26#include "command.h" 27#include "log.h" 28#include "thread.h" 29 30#include "bgpd/bgpd.h" 31#include "bgpd/bgp_damp.h" 32#include "bgpd/bgp_table.h" 33#include "bgpd/bgp_route.h" 34#include "bgpd/bgp_attr.h" 35#include "bgpd/bgp_advertise.h" 36 37/* Global variable to access damping configuration */ 38struct bgp_damp_config bgp_damp_cfg; 39static struct bgp_damp_config *damp = &bgp_damp_cfg; 40 41/* Utility macro to add and delete BGP dampening information to no 42 used list. */ 43#define BGP_DAMP_LIST_ADD(N,A) BGP_INFO_ADD(N,A,no_reuse_list) 44#define BGP_DAMP_LIST_DEL(N,A) BGP_INFO_DEL(N,A,no_reuse_list) 45 46/* Calculate reuse list index by penalty value. */ 47static int 48bgp_reuse_index (int penalty) 49{ 50 unsigned int i; 51 int index; 52 53 i = (int)(((double) penalty / damp->reuse_limit - 1.0) * damp->scale_factor); 54 55 if ( i >= damp->reuse_index_size ) 56 i = damp->reuse_index_size - 1; 57 58 index = damp->reuse_index[i] - damp->reuse_index[0]; 59 60 return (damp->reuse_offset + index) % damp->reuse_list_size; 61} 62 63/* Add BGP dampening information to reuse list. */ 64static void 65bgp_reuse_list_add (struct bgp_damp_info *bdi) 66{ 67 int index; 68 69 index = bdi->index = bgp_reuse_index (bdi->penalty); 70 71 bdi->prev = NULL; 72 bdi->next = damp->reuse_list[index]; 73 if (damp->reuse_list[index]) 74 damp->reuse_list[index]->prev = bdi; 75 damp->reuse_list[index] = bdi; 76} 77 78/* Delete BGP dampening information from reuse list. */ 79static void 80bgp_reuse_list_delete (struct bgp_damp_info *bdi) 81{ 82 if (bdi->next) 83 bdi->next->prev = bdi->prev; 84 if (bdi->prev) 85 bdi->prev->next = bdi->next; 86 else 87 damp->reuse_list[bdi->index] = bdi->next; 88} 89 90/* Return decayed penalty value. */ 91int 92bgp_damp_decay (time_t tdiff, int penalty) 93{ 94 unsigned int i; 95 96 i = (int) ((double) tdiff / DELTA_T); 97 98 if (i == 0) 99 return penalty; 100 101 if (i >= damp->decay_array_size) 102 return 0; 103 104 return (int) (penalty * damp->decay_array[i]); 105} 106 107/* Handler of reuse timer event. Each route in the current reuse-list 108 is evaluated. RFC2439 Section 4.8.7. */ 109static int 110bgp_reuse_timer (struct thread *t) 111{ 112 struct bgp_damp_info *bdi; 113 struct bgp_damp_info *next; 114 time_t t_now, t_diff; 115 116 damp->t_reuse = NULL; 117 damp->t_reuse = 118 thread_add_timer (master, bgp_reuse_timer, NULL, DELTA_REUSE); 119 120 t_now = bgp_clock (); 121 122 /* 1. save a pointer to the current zeroth queue head and zero the 123 list head entry. */ 124 bdi = damp->reuse_list[damp->reuse_offset]; 125 damp->reuse_list[damp->reuse_offset] = NULL; 126 127 /* 2. set offset = modulo reuse-list-size ( offset + 1 ), thereby 128 rotating the circular queue of list-heads. */ 129 damp->reuse_offset = (damp->reuse_offset + 1) % damp->reuse_list_size; 130 131 /* 3. if ( the saved list head pointer is non-empty ) */ 132 for (; bdi; bdi = next) 133 { 134 struct bgp *bgp = bdi->binfo->peer->bgp; 135 136 next = bdi->next; 137 138 /* Set t-diff = t-now - t-updated. */ 139 t_diff = t_now - bdi->t_updated; 140 141 /* Set figure-of-merit = figure-of-merit * decay-array-ok [t-diff] */ 142 bdi->penalty = bgp_damp_decay (t_diff, bdi->penalty); 143 144 /* Set t-updated = t-now. */ 145 bdi->t_updated = t_now; 146 147 /* if (figure-of-merit < reuse). */ 148 if (bdi->penalty < damp->reuse_limit) 149 { 150 /* Reuse the route. */ 151 bgp_info_unset_flag (bdi->rn, bdi->binfo, BGP_INFO_DAMPED); 152 bdi->suppress_time = 0; 153 154 if (bdi->lastrecord == BGP_RECORD_UPDATE) 155 { 156 bgp_info_unset_flag (bdi->rn, bdi->binfo, BGP_INFO_HISTORY); 157 bgp_aggregate_increment (bgp, &bdi->rn->p, bdi->binfo, 158 bdi->afi, bdi->safi); 159 bgp_process (bgp, bdi->rn, bdi->afi, bdi->safi); 160 } 161 162 if (bdi->penalty <= damp->reuse_limit / 2.0) 163 bgp_damp_info_free (bdi, 1); 164 else 165 BGP_DAMP_LIST_ADD (damp, bdi); 166 } 167 else 168 /* Re-insert into another list (See RFC2439 Section 4.8.6). */ 169 bgp_reuse_list_add (bdi); 170 } 171 172 return 0; 173} 174 175/* A route becomes unreachable (RFC2439 Section 4.8.2). */ 176int 177bgp_damp_withdraw (struct bgp_info *binfo, struct bgp_node *rn, 178 afi_t afi, safi_t safi, int attr_change) 179{ 180 time_t t_now; 181 struct bgp_damp_info *bdi = NULL; 182 double last_penalty = 0; 183 184 t_now = bgp_clock (); 185 186 /* Processing Unreachable Messages. */ 187 if (binfo->extra) 188 bdi = binfo->extra->damp_info; 189 190 if (bdi == NULL) 191 { 192 /* If there is no previous stability history. */ 193 194 /* RFC2439 said: 195 1. allocate a damping structure. 196 2. set figure-of-merit = 1. 197 3. withdraw the route. */ 198 199 bdi = XCALLOC (MTYPE_BGP_DAMP_INFO, sizeof (struct bgp_damp_info)); 200 bdi->binfo = binfo; 201 bdi->rn = rn; 202 bdi->penalty = (attr_change ? DEFAULT_PENALTY / 2 : DEFAULT_PENALTY); 203 bdi->flap = 1; 204 bdi->start_time = t_now; 205 bdi->suppress_time = 0; 206 bdi->index = -1; 207 bdi->afi = afi; 208 bdi->safi = safi; 209 (bgp_info_extra_get (binfo))->damp_info = bdi; 210 BGP_DAMP_LIST_ADD (damp, bdi); 211 } 212 else 213 { 214 last_penalty = bdi->penalty; 215 216 /* 1. Set t-diff = t-now - t-updated. */ 217 bdi->penalty = 218 (bgp_damp_decay (t_now - bdi->t_updated, bdi->penalty) 219 + (attr_change ? DEFAULT_PENALTY / 2 : DEFAULT_PENALTY)); 220 221 if (bdi->penalty > damp->ceiling) 222 bdi->penalty = damp->ceiling; 223 224 bdi->flap++; 225 } 226 227 assert ((rn == bdi->rn) && (binfo == bdi->binfo)); 228 229 bdi->lastrecord = BGP_RECORD_WITHDRAW; 230 bdi->t_updated = t_now; 231 232 /* Make this route as historical status. */ 233 bgp_info_set_flag (rn, binfo, BGP_INFO_HISTORY); 234 235 /* Remove the route from a reuse list if it is on one. */ 236 if (CHECK_FLAG (bdi->binfo->flags, BGP_INFO_DAMPED)) 237 { 238 /* If decay rate isn't equal to 0, reinsert brn. */ 239 if (bdi->penalty != last_penalty) 240 { 241 bgp_reuse_list_delete (bdi); 242 bgp_reuse_list_add (bdi); 243 } 244 return BGP_DAMP_SUPPRESSED; 245 } 246 247 /* If not suppressed before, do annonunce this withdraw and 248 insert into reuse_list. */ 249 if (bdi->penalty >= damp->suppress_value) 250 { 251 bgp_info_set_flag (rn, binfo, BGP_INFO_DAMPED); 252 bdi->suppress_time = t_now; 253 BGP_DAMP_LIST_DEL (damp, bdi); 254 bgp_reuse_list_add (bdi); 255 } 256 257 return BGP_DAMP_USED; 258} 259 260int 261bgp_damp_update (struct bgp_info *binfo, struct bgp_node *rn, 262 afi_t afi, safi_t safi) 263{ 264 time_t t_now; 265 struct bgp_damp_info *bdi; 266 int status; 267 268 if (!binfo->extra || !((bdi = binfo->extra->damp_info))) 269 return BGP_DAMP_USED; 270 271 t_now = bgp_clock (); 272 bgp_info_unset_flag (rn, binfo, BGP_INFO_HISTORY); 273 274 bdi->lastrecord = BGP_RECORD_UPDATE; 275 bdi->penalty = bgp_damp_decay (t_now - bdi->t_updated, bdi->penalty); 276 277 if (! CHECK_FLAG (bdi->binfo->flags, BGP_INFO_DAMPED) 278 && (bdi->penalty < damp->suppress_value)) 279 status = BGP_DAMP_USED; 280 else if (CHECK_FLAG (bdi->binfo->flags, BGP_INFO_DAMPED) 281 && (bdi->penalty < damp->reuse_limit) ) 282 { 283 bgp_info_unset_flag (rn, binfo, BGP_INFO_DAMPED); 284 bgp_reuse_list_delete (bdi); 285 BGP_DAMP_LIST_ADD (damp, bdi); 286 bdi->suppress_time = 0; 287 status = BGP_DAMP_USED; 288 } 289 else 290 status = BGP_DAMP_SUPPRESSED; 291 292 if (bdi->penalty > damp->reuse_limit / 2.0) 293 bdi->t_updated = t_now; 294 else 295 bgp_damp_info_free (bdi, 0); 296 297 return status; 298} 299 300/* Remove dampening information and history route. */ 301int 302bgp_damp_scan (struct bgp_info *binfo, afi_t afi, safi_t safi) 303{ 304 time_t t_now, t_diff; 305 struct bgp_damp_info *bdi; 306 307 assert (binfo->extra && binfo->extra->damp_info); 308 309 t_now = bgp_clock (); 310 bdi = binfo->extra->damp_info; 311 312 if (CHECK_FLAG (binfo->flags, BGP_INFO_DAMPED)) 313 { 314 t_diff = t_now - bdi->suppress_time; 315 316 if (t_diff >= damp->max_suppress_time) 317 { 318 bgp_info_unset_flag (bdi->rn, binfo, BGP_INFO_DAMPED); 319 bgp_reuse_list_delete (bdi); 320 BGP_DAMP_LIST_ADD (damp, bdi); 321 bdi->penalty = damp->reuse_limit; 322 bdi->suppress_time = 0; 323 bdi->t_updated = t_now; 324 325 /* Need to announce UPDATE once this binfo is usable again. */ 326 if (bdi->lastrecord == BGP_RECORD_UPDATE) 327 return 1; 328 else 329 return 0; 330 } 331 } 332 else 333 { 334 t_diff = t_now - bdi->t_updated; 335 bdi->penalty = bgp_damp_decay (t_diff, bdi->penalty); 336 337 if (bdi->penalty <= damp->reuse_limit / 2.0) 338 { 339 /* release the bdi, bdi->binfo. */ 340 bgp_damp_info_free (bdi, 1); 341 return 0; 342 } 343 else 344 bdi->t_updated = t_now; 345 } 346 return 0; 347} 348 349void 350bgp_damp_info_free (struct bgp_damp_info *bdi, int withdraw) 351{ 352 struct bgp_info *binfo; 353 354 if (! bdi) 355 return; 356 357 binfo = bdi->binfo; 358 binfo->extra->damp_info = NULL; 359 360 if (CHECK_FLAG (binfo->flags, BGP_INFO_DAMPED)) 361 bgp_reuse_list_delete (bdi); 362 else 363 BGP_DAMP_LIST_DEL (damp, bdi); 364 365 bgp_info_unset_flag (bdi->rn, binfo, BGP_INFO_HISTORY|BGP_INFO_DAMPED); 366 367 if (bdi->lastrecord == BGP_RECORD_WITHDRAW && withdraw) 368 bgp_info_delete (bdi->rn, binfo); 369 370 XFREE (MTYPE_BGP_DAMP_INFO, bdi); 371} 372 373static void 374bgp_damp_parameter_set (int hlife, int reuse, int sup, int maxsup) 375{ 376 double reuse_max_ratio; 377 unsigned int i; 378 double j; 379 380 damp->suppress_value = sup; 381 damp->half_life = hlife; 382 damp->reuse_limit = reuse; 383 damp->max_suppress_time = maxsup; 384 385 /* Initialize params per bgp_damp_config. */ 386 damp->reuse_index_size = REUSE_ARRAY_SIZE; 387 388 damp->ceiling = (int)(damp->reuse_limit * (pow(2, (double)damp->max_suppress_time/damp->half_life))); 389 390 /* Decay-array computations */ 391 damp->decay_array_size = ceil ((double) damp->max_suppress_time / DELTA_T); 392 damp->decay_array = XMALLOC (MTYPE_BGP_DAMP_ARRAY, 393 sizeof(double) * (damp->decay_array_size)); 394 damp->decay_array[0] = 1.0; 395 damp->decay_array[1] = exp ((1.0/((double)damp->half_life/DELTA_T)) * log(0.5)); 396 397 /* Calculate decay values for all possible times */ 398 for (i = 2; i < damp->decay_array_size; i++) 399 damp->decay_array[i] = damp->decay_array[i-1] * damp->decay_array[1]; 400 401 /* Reuse-list computations */ 402 i = ceil ((double)damp->max_suppress_time / DELTA_REUSE) + 1; 403 if (i > REUSE_LIST_SIZE || i == 0) 404 i = REUSE_LIST_SIZE; 405 damp->reuse_list_size = i; 406 407 damp->reuse_list = XCALLOC (MTYPE_BGP_DAMP_ARRAY, 408 damp->reuse_list_size 409 * sizeof (struct bgp_reuse_node *)); 410 411 /* Reuse-array computations */ 412 damp->reuse_index = XCALLOC (MTYPE_BGP_DAMP_ARRAY, 413 sizeof(int) * damp->reuse_index_size); 414 415 reuse_max_ratio = (double)damp->ceiling/damp->reuse_limit; 416 j = (exp((double)damp->max_suppress_time/damp->half_life) * log10(2.0)); 417 if ( reuse_max_ratio > j && j != 0 ) 418 reuse_max_ratio = j; 419 420 damp->scale_factor = (double)damp->reuse_index_size/(reuse_max_ratio - 1); 421 422 for (i = 0; i < damp->reuse_index_size; i++) 423 { 424 damp->reuse_index[i] = 425 (int)(((double)damp->half_life / DELTA_REUSE) 426 * log10 (1.0 / (damp->reuse_limit * ( 1.0 + ((double)i/damp->scale_factor)))) / log10(0.5)); 427 } 428} 429 430int 431bgp_damp_enable (struct bgp *bgp, afi_t afi, safi_t safi, time_t half, 432 unsigned int reuse, unsigned int suppress, time_t max) 433{ 434 if (CHECK_FLAG (bgp->af_flags[afi][safi], BGP_CONFIG_DAMPENING)) 435 { 436 if (damp->half_life == half 437 && damp->reuse_limit == reuse 438 && damp->suppress_value == suppress 439 && damp->max_suppress_time == max) 440 return 0; 441 bgp_damp_disable (bgp, afi, safi); 442 } 443 444 SET_FLAG (bgp->af_flags[afi][safi], BGP_CONFIG_DAMPENING); 445 bgp_damp_parameter_set (half, reuse, suppress, max); 446 447 /* Register reuse timer. */ 448 if (! damp->t_reuse) 449 damp->t_reuse = 450 thread_add_timer (master, bgp_reuse_timer, NULL, DELTA_REUSE); 451 452 return 0; 453} 454 455static void 456bgp_damp_config_clean (struct bgp_damp_config *damp) 457{ 458 /* Free decay array */ 459 XFREE (MTYPE_BGP_DAMP_ARRAY, damp->decay_array); 460 461 /* Free reuse index array */ 462 XFREE (MTYPE_BGP_DAMP_ARRAY, damp->reuse_index); 463 464 /* Free reuse list array. */ 465 XFREE (MTYPE_BGP_DAMP_ARRAY, damp->reuse_list); 466} 467 468/* Clean all the bgp_damp_info stored in reuse_list. */ 469void 470bgp_damp_info_clean (void) 471{ 472 unsigned int i; 473 struct bgp_damp_info *bdi, *next; 474 475 damp->reuse_offset = 0; 476 477 for (i = 0; i < damp->reuse_list_size; i++) 478 { 479 if (! damp->reuse_list[i]) 480 continue; 481 482 for (bdi = damp->reuse_list[i]; bdi; bdi = next) 483 { 484 next = bdi->next; 485 bgp_damp_info_free (bdi, 1); 486 } 487 damp->reuse_list[i] = NULL; 488 } 489 490 for (bdi = damp->no_reuse_list; bdi; bdi = next) 491 { 492 next = bdi->next; 493 bgp_damp_info_free (bdi, 1); 494 } 495 damp->no_reuse_list = NULL; 496} 497 498int 499bgp_damp_disable (struct bgp *bgp, afi_t afi, safi_t safi) 500{ 501 /* If it wasn't enabled, there's nothing to do. */ 502 if (! CHECK_FLAG (bgp->af_flags[afi][safi], BGP_CONFIG_DAMPENING)) 503 return 0; 504 505 /* Cancel reuse thread. */ 506 if (damp->t_reuse ) 507 thread_cancel (damp->t_reuse); 508 damp->t_reuse = NULL; 509 510 /* Clean BGP dampening information. */ 511 bgp_damp_info_clean (); 512 513 /* Clear configuration */ 514 bgp_damp_config_clean (&bgp_damp_cfg); 515 516 UNSET_FLAG (bgp->af_flags[afi][safi], BGP_CONFIG_DAMPENING); 517 return 0; 518} 519 520void 521bgp_config_write_damp (struct vty *vty) 522{ 523 if (bgp_damp_cfg.half_life == DEFAULT_HALF_LIFE*60 524 && bgp_damp_cfg.reuse_limit == DEFAULT_REUSE 525 && bgp_damp_cfg.suppress_value == DEFAULT_SUPPRESS 526 && bgp_damp_cfg.max_suppress_time == bgp_damp_cfg.half_life*4) 527 vty_out (vty, " bgp dampening%s", VTY_NEWLINE); 528 else if (bgp_damp_cfg.half_life != DEFAULT_HALF_LIFE*60 529 && bgp_damp_cfg.reuse_limit == DEFAULT_REUSE 530 && bgp_damp_cfg.suppress_value == DEFAULT_SUPPRESS 531 && bgp_damp_cfg.max_suppress_time == bgp_damp_cfg.half_life*4) 532 vty_out (vty, " bgp dampening %ld%s", 533 bgp_damp_cfg.half_life/60, 534 VTY_NEWLINE); 535 else 536 vty_out (vty, " bgp dampening %ld %d %d %ld%s", 537 bgp_damp_cfg.half_life/60, 538 bgp_damp_cfg.reuse_limit, 539 bgp_damp_cfg.suppress_value, 540 bgp_damp_cfg.max_suppress_time/60, 541 VTY_NEWLINE); 542} 543 544static const char * 545bgp_get_reuse_time (unsigned int penalty, char *buf, size_t len) 546{ 547 time_t reuse_time = 0; 548 struct tm *tm = NULL; 549 550 if (penalty > damp->reuse_limit) 551 { 552 reuse_time = (int) (DELTA_T * ((log((double)damp->reuse_limit/penalty))/(log(damp->decay_array[1])))); 553 554 if (reuse_time > damp->max_suppress_time) 555 reuse_time = damp->max_suppress_time; 556 557 tm = gmtime (&reuse_time); 558 } 559 else 560 reuse_time = 0; 561 562 /* Making formatted timer strings. */ 563#define ONE_DAY_SECOND 60*60*24 564#define ONE_WEEK_SECOND 60*60*24*7 565 if (reuse_time == 0) 566 snprintf (buf, len, "00:00:00"); 567 else if (reuse_time < ONE_DAY_SECOND) 568 snprintf (buf, len, "%02d:%02d:%02d", 569 tm->tm_hour, tm->tm_min, tm->tm_sec); 570 else if (reuse_time < ONE_WEEK_SECOND) 571 snprintf (buf, len, "%dd%02dh%02dm", 572 tm->tm_yday, tm->tm_hour, tm->tm_min); 573 else 574 snprintf (buf, len, "%02dw%dd%02dh", 575 tm->tm_yday/7, tm->tm_yday - ((tm->tm_yday/7) * 7), tm->tm_hour); 576 577 return buf; 578} 579 580void 581bgp_damp_info_vty (struct vty *vty, struct bgp_info *binfo) 582{ 583 struct bgp_damp_info *bdi; 584 time_t t_now, t_diff; 585 char timebuf[BGP_UPTIME_LEN]; 586 int penalty; 587 588 if (!binfo->extra) 589 return; 590 591 /* BGP dampening information. */ 592 bdi = binfo->extra->damp_info; 593 594 /* If dampening is not enabled or there is no dampening information, 595 return immediately. */ 596 if (! damp || ! bdi) 597 return; 598 599 /* Calculate new penalty. */ 600 t_now = bgp_clock (); 601 t_diff = t_now - bdi->t_updated; 602 penalty = bgp_damp_decay (t_diff, bdi->penalty); 603 604 vty_out (vty, " Dampinfo: penalty %d, flapped %d times in %s", 605 penalty, bdi->flap, 606 peer_uptime (bdi->start_time, timebuf, BGP_UPTIME_LEN)); 607 608 if (CHECK_FLAG (binfo->flags, BGP_INFO_DAMPED) 609 && ! CHECK_FLAG (binfo->flags, BGP_INFO_HISTORY)) 610 vty_out (vty, ", reuse in %s", 611 bgp_get_reuse_time (penalty, timebuf, BGP_UPTIME_LEN)); 612 613 vty_out (vty, "%s", VTY_NEWLINE); 614} 615 616const char * 617bgp_damp_reuse_time_vty (struct vty *vty, struct bgp_info *binfo, 618 char *timebuf, size_t len) 619{ 620 struct bgp_damp_info *bdi; 621 time_t t_now, t_diff; 622 int penalty; 623 624 if (!binfo->extra) 625 return NULL; 626 627 /* BGP dampening information. */ 628 bdi = binfo->extra->damp_info; 629 630 /* If dampening is not enabled or there is no dampening information, 631 return immediately. */ 632 if (! damp || ! bdi) 633 return NULL; 634 635 /* Calculate new penalty. */ 636 t_now = bgp_clock (); 637 t_diff = t_now - bdi->t_updated; 638 penalty = bgp_damp_decay (t_diff, bdi->penalty); 639 640 return bgp_get_reuse_time (penalty, timebuf, len); 641} 642