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; 39struct 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 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 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. */ 109int 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 struct bgp *bgp; 116 int bgp_process (struct bgp *, struct bgp_node *, afi_t, safi_t); 117 118 damp->t_reuse = NULL; 119 damp->t_reuse = 120 thread_add_timer (master, bgp_reuse_timer, NULL, DELTA_REUSE); 121 122 bgp = bgp_get_default (); 123 if (! bgp) 124 return 0; 125 126 t_now = time (NULL); 127 128 /* 1. save a pointer to the current zeroth queue head and zero the 129 list head entry. */ 130 bdi = damp->reuse_list[damp->reuse_offset]; 131 damp->reuse_list[damp->reuse_offset] = NULL; 132 133 /* 2. set offset = modulo reuse-list-size ( offset + 1 ), thereby 134 rotating the circular queue of list-heads. */ 135 damp->reuse_offset = (damp->reuse_offset + 1) % damp->reuse_list_size; 136 137 /* 3. if ( the saved list head pointer is non-empty ) */ 138 for (; bdi; bdi = next) 139 { 140 next = bdi->next; 141 142 /* Set t-diff = t-now - t-updated. */ 143 t_diff = t_now - bdi->t_updated; 144 145 /* Set figure-of-merit = figure-of-merit * decay-array-ok [t-diff] */ 146 bdi->penalty = bgp_damp_decay (t_diff, bdi->penalty); 147 148 /* Set t-updated = t-now. */ 149 bdi->t_updated = t_now; 150 151 /* if (figure-of-merit < reuse). */ 152 if (bdi->penalty < damp->reuse_limit) 153 { 154 /* Reuse the route. */ 155 UNSET_FLAG (bdi->binfo->flags, BGP_INFO_DAMPED); 156 bdi->suppress_time = 0; 157 158 if (bdi->lastrecord == BGP_RECORD_UPDATE) 159 { 160 UNSET_FLAG (bdi->binfo->flags, BGP_INFO_HISTORY); 161 bgp_aggregate_increment (bgp, &bdi->rn->p, bdi->binfo, 162 bdi->afi, bdi->safi); 163 bgp_process (bgp, bdi->rn, bdi->afi, bdi->safi); 164 } 165 166 if (bdi->penalty <= damp->reuse_limit / 2.0) 167 bgp_damp_info_free (bdi, 1); 168 else 169 BGP_DAMP_LIST_ADD (damp, bdi); 170 } 171 else 172 /* Re-insert into another list (See RFC2439 Section 4.8.6). */ 173 bgp_reuse_list_add (bdi); 174 } 175 176 return 0; 177} 178 179/* A route becomes unreachable (RFC2439 Section 4.8.2). */ 180int 181bgp_damp_withdraw (struct bgp_info *binfo, struct bgp_node *rn, 182 afi_t afi, safi_t safi, int attr_change) 183{ 184 time_t t_now; 185 struct bgp_damp_info *bdi; 186 double last_penalty = 0; 187 188 t_now = time (NULL); 189 190 /* Processing Unreachable Messages. */ 191 bdi = binfo->damp_info; 192 193 if (bdi == NULL) 194 { 195 /* If there is no previous stability history. */ 196 197 /* RFC2439 said: 198 1. allocate a damping structure. 199 2. set figure-of-merit = 1. 200 3. withdraw the route. */ 201 202 bdi = XCALLOC (MTYPE_BGP_DAMP_INFO, sizeof (struct bgp_damp_info)); 203 bdi->binfo = binfo; 204 bdi->rn = rn; 205 bdi->penalty = (attr_change ? DEFAULT_PENALTY / 2 : DEFAULT_PENALTY); 206 bdi->flap = 1; 207 bdi->start_time = t_now; 208 bdi->suppress_time = 0; 209 bdi->index = -1; 210 bdi->afi = afi; 211 bdi->safi = safi; 212 binfo->damp_info = bdi; 213 BGP_DAMP_LIST_ADD (damp, bdi); 214 } 215 else 216 { 217 last_penalty = bdi->penalty; 218 219 /* 1. Set t-diff = t-now - t-updated. */ 220 bdi->penalty = 221 (bgp_damp_decay (t_now - bdi->t_updated, bdi->penalty) 222 + (attr_change ? DEFAULT_PENALTY / 2 : DEFAULT_PENALTY)); 223 224 if (bdi->penalty > damp->ceiling) 225 bdi->penalty = damp->ceiling; 226 227 bdi->flap++; 228 } 229 230 bdi->lastrecord = BGP_RECORD_WITHDRAW; 231 bdi->t_updated = t_now; 232 233 /* Make this route as historical status. */ 234 SET_FLAG (binfo->flags, BGP_INFO_HISTORY); 235 236 /* Remove the route from a reuse list if it is on one. */ 237 if (CHECK_FLAG (bdi->binfo->flags, BGP_INFO_DAMPED)) 238 { 239 /* If decay rate isn't equal to 0, reinsert brn. */ 240 if (bdi->penalty != last_penalty) 241 { 242 bgp_reuse_list_delete (bdi); 243 bgp_reuse_list_add (bdi); 244 } 245 return BGP_DAMP_SUPPRESSED; 246 } 247 248 /* If not suppressed before, do annonunce this withdraw and 249 insert into reuse_list. */ 250 if (bdi->penalty >= damp->suppress_value) 251 { 252 SET_FLAG (bdi->binfo->flags, BGP_INFO_DAMPED); 253 bdi->suppress_time = t_now; 254 BGP_DAMP_LIST_DEL (damp, bdi); 255 bgp_reuse_list_add (bdi); 256 } 257 258 return BGP_DAMP_USED; 259} 260 261int 262bgp_damp_update (struct bgp_info *binfo, struct bgp_node *rn, 263 afi_t afi, safi_t safi) 264{ 265 time_t t_now; 266 struct bgp_damp_info *bdi; 267 int status; 268 269 bdi = binfo->damp_info; 270 if (! bdi) 271 return BGP_DAMP_USED; 272 273 t_now = time (NULL); 274 UNSET_FLAG (binfo->flags, BGP_INFO_HISTORY); 275 276 bdi->lastrecord = BGP_RECORD_UPDATE; 277 bdi->penalty = bgp_damp_decay (t_now - bdi->t_updated, bdi->penalty); 278 279 if (! CHECK_FLAG (bdi->binfo->flags, BGP_INFO_DAMPED) 280 && (bdi->penalty < damp->suppress_value)) 281 status = BGP_DAMP_USED; 282 else if (CHECK_FLAG (bdi->binfo->flags, BGP_INFO_DAMPED) 283 && (bdi->penalty < damp->reuse_limit) ) 284 { 285 UNSET_FLAG (bdi->binfo->flags, BGP_INFO_DAMPED); 286 bgp_reuse_list_delete (bdi); 287 BGP_DAMP_LIST_ADD (damp, bdi); 288 bdi->suppress_time = 0; 289 status = BGP_DAMP_USED; 290 } 291 else 292 status = BGP_DAMP_SUPPRESSED; 293 294 if (bdi->penalty > damp->reuse_limit / 2.0) 295 bdi->t_updated = t_now; 296 else 297 bgp_damp_info_free (bdi, 0); 298 299 return status; 300} 301 302/* Remove dampening information and history route. */ 303int 304bgp_damp_scan (struct bgp_info *binfo, afi_t afi, safi_t safi) 305{ 306 time_t t_now, t_diff; 307 struct bgp_damp_info *bdi; 308 309 t_now = time (NULL); 310 bdi = binfo->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 UNSET_FLAG (binfo->flags, 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 void bgp_info_delete (struct bgp_node *, struct bgp_info *); 354 void bgp_info_free (struct bgp_info *); 355 356 if (! bdi) 357 return; 358 359 binfo = bdi->binfo; 360 binfo->damp_info = NULL; 361 362 if (CHECK_FLAG (binfo->flags, BGP_INFO_DAMPED)) 363 bgp_reuse_list_delete (bdi); 364 else 365 BGP_DAMP_LIST_DEL (damp, bdi); 366 367 UNSET_FLAG (binfo->flags, BGP_INFO_DAMPED); 368 UNSET_FLAG (binfo->flags, BGP_INFO_HISTORY); 369 370 if (bdi->lastrecord == BGP_RECORD_WITHDRAW && withdraw) 371 { 372 bgp_info_delete (bdi->rn, binfo); 373 bgp_info_free (binfo); 374 bgp_unlock_node (bdi->rn); 375 } 376 XFREE (MTYPE_BGP_DAMP_INFO, bdi); 377} 378 379void 380bgp_damp_parameter_set (int hlife, int reuse, int sup, int maxsup) 381{ 382 double reuse_max_ratio; 383 int i; 384 double j; 385 386 damp->suppress_value = sup; 387 damp->half_life = hlife; 388 damp->reuse_limit = reuse; 389 damp->max_suppress_time = maxsup; 390 391 /* Initialize params per bgp_damp_config. */ 392 damp->reuse_index_size = REUSE_ARRAY_SIZE; 393 394 damp->ceiling = (int)(damp->reuse_limit * (pow(2, (double)damp->max_suppress_time/damp->half_life))); 395 396 /* Decay-array computations */ 397 damp->decay_array_size = ceil ((double) damp->max_suppress_time / DELTA_T); 398 damp->decay_array = XMALLOC (MTYPE_BGP_DAMP_ARRAY, 399 sizeof(double) * (damp->decay_array_size)); 400 damp->decay_array[0] = 1.0; 401 damp->decay_array[1] = exp ((1.0/((double)damp->half_life/DELTA_T)) * log(0.5)); 402 403 /* Calculate decay values for all possible times */ 404 for (i = 2; i < damp->decay_array_size; i++) 405 damp->decay_array[i] = damp->decay_array[i-1] * damp->decay_array[1]; 406 407 /* Reuse-list computations */ 408 i = ceil ((double)damp->max_suppress_time / DELTA_REUSE) + 1; 409 if (i > REUSE_LIST_SIZE || i == 0) 410 i = REUSE_LIST_SIZE; 411 damp->reuse_list_size = i; 412 413 damp->reuse_list = XCALLOC (MTYPE_BGP_DAMP_ARRAY, 414 damp->reuse_list_size 415 * sizeof (struct bgp_reuse_node *)); 416 memset (damp->reuse_list, 0x00, 417 damp->reuse_list_size * sizeof (struct bgp_reuse_node *)); 418 419 /* Reuse-array computations */ 420 damp->reuse_index = XMALLOC (MTYPE_BGP_DAMP_ARRAY, 421 sizeof(int) * damp->reuse_index_size); 422 memset (damp->reuse_index, 0x00, 423 damp->reuse_list_size * sizeof (int)); 424 425 reuse_max_ratio = (double)damp->ceiling/damp->reuse_limit; 426 j = (exp((double)damp->max_suppress_time/damp->half_life) * log10(2.0)); 427 if ( reuse_max_ratio > j && j != 0 ) 428 reuse_max_ratio = j; 429 430 damp->scale_factor = (double)damp->reuse_index_size/(reuse_max_ratio - 1); 431 432 for (i = 0; i < damp->reuse_index_size; i++) 433 { 434 damp->reuse_index[i] = 435 (int)(((double)damp->half_life / DELTA_REUSE) 436 * log10 (1.0 / (damp->reuse_limit * ( 1.0 + ((double)i/damp->scale_factor)))) / log10(0.5)); 437 } 438} 439 440int 441bgp_damp_enable (struct bgp *bgp, afi_t afi, safi_t safi, int half, 442 int reuse, int suppress, int max) 443{ 444 if (CHECK_FLAG (bgp->af_flags[afi][safi], BGP_CONFIG_DAMPENING)) 445 { 446 if (damp->half_life == half 447 && damp->reuse_limit == reuse 448 && damp->suppress_value == suppress 449 && damp->max_suppress_time == max) 450 return 0; 451 bgp_damp_disable (bgp, afi, safi); 452 } 453 454 SET_FLAG (bgp->af_flags[afi][safi], BGP_CONFIG_DAMPENING); 455 bgp_damp_parameter_set (half, reuse, suppress, max); 456 457 /* Register reuse timer. */ 458 if (! damp->t_reuse) 459 damp->t_reuse = 460 thread_add_timer (master, bgp_reuse_timer, NULL, DELTA_REUSE); 461 462 return 0; 463} 464 465void 466bgp_damp_config_clean (struct bgp_damp_config *damp) 467{ 468 /* Free decay array */ 469 XFREE (MTYPE_BGP_DAMP_ARRAY, damp->decay_array); 470 471 /* Free reuse index array */ 472 XFREE (MTYPE_BGP_DAMP_ARRAY, damp->reuse_index); 473 474 /* Free reuse list array. */ 475 XFREE (MTYPE_BGP_DAMP_ARRAY, damp->reuse_list); 476} 477 478/* Clean all the bgp_damp_info stored in reuse_list. */ 479void 480bgp_damp_info_clean () 481{ 482 int i; 483 struct bgp_damp_info *bdi, *next; 484 485 damp->reuse_offset = 0; 486 487 for (i = 0; i < damp->reuse_list_size; i++) 488 { 489 if (! damp->reuse_list[i]) 490 continue; 491 492 for (bdi = damp->reuse_list[i]; bdi; bdi = next) 493 { 494 next = bdi->next; 495 bgp_damp_info_free (bdi, 1); 496 } 497 damp->reuse_list[i] = NULL; 498 } 499 500 for (bdi = damp->no_reuse_list; bdi; bdi = next) 501 { 502 next = bdi->next; 503 bgp_damp_info_free (bdi, 1); 504 } 505 damp->no_reuse_list = NULL; 506} 507 508int 509bgp_damp_disable (struct bgp *bgp, afi_t afi, safi_t safi) 510{ 511 /* Cancel reuse thread. */ 512 if (damp->t_reuse ) 513 thread_cancel (damp->t_reuse); 514 damp->t_reuse = NULL; 515 516 /* Clean BGP dampening information. */ 517 bgp_damp_info_clean (); 518 519 /* Clear configuration */ 520 bgp_damp_config_clean (&bgp_damp_cfg); 521 522 UNSET_FLAG (bgp->af_flags[afi][safi], BGP_CONFIG_DAMPENING); 523 return 0; 524} 525 526int 527bgp_config_write_damp (struct vty *vty) 528{ 529 if (&bgp_damp_cfg) 530 { 531 if (bgp_damp_cfg.half_life == DEFAULT_HALF_LIFE*60 532 && bgp_damp_cfg.reuse_limit == DEFAULT_REUSE 533 && bgp_damp_cfg.suppress_value == DEFAULT_SUPPRESS 534 && bgp_damp_cfg.max_suppress_time == bgp_damp_cfg.half_life*4) 535 vty_out (vty, " bgp dampening%s", VTY_NEWLINE); 536 else if (bgp_damp_cfg.half_life != DEFAULT_HALF_LIFE*60 537 && bgp_damp_cfg.reuse_limit == DEFAULT_REUSE 538 && bgp_damp_cfg.suppress_value == DEFAULT_SUPPRESS 539 && bgp_damp_cfg.max_suppress_time == bgp_damp_cfg.half_life*4) 540 vty_out (vty, " bgp dampening %d%s", 541 bgp_damp_cfg.half_life/60, 542 VTY_NEWLINE); 543 else 544 vty_out (vty, " bgp dampening %d %d %d %d%s", 545 bgp_damp_cfg.half_life/60, 546 bgp_damp_cfg.reuse_limit, 547 bgp_damp_cfg.suppress_value, 548 bgp_damp_cfg.max_suppress_time/60, 549 VTY_NEWLINE); 550 return 1; 551 } 552 return 0; 553} 554 555#define BGP_UPTIME_LEN 25 556 557char * 558bgp_get_reuse_time (int penalty, char *buf, size_t len) 559{ 560 time_t reuse_time = 0; 561 struct tm *tm = NULL; 562 563 if (penalty > damp->reuse_limit) 564 { 565 reuse_time = (int) (DELTA_T * ((log((double)damp->reuse_limit/penalty))/(log(damp->decay_array[1])))); 566 567 if (reuse_time > damp->max_suppress_time) 568 reuse_time = damp->max_suppress_time; 569 570 tm = gmtime (&reuse_time); 571 } 572 else 573 reuse_time = 0; 574 575 /* Making formatted timer strings. */ 576#define ONE_DAY_SECOND 60*60*24 577#define ONE_WEEK_SECOND 60*60*24*7 578 if (reuse_time == 0) 579 snprintf (buf, len, "00:00:00"); 580 else if (reuse_time < ONE_DAY_SECOND) 581 snprintf (buf, len, "%02d:%02d:%02d", 582 tm->tm_hour, tm->tm_min, tm->tm_sec); 583 else if (reuse_time < ONE_WEEK_SECOND) 584 snprintf (buf, len, "%dd%02dh%02dm", 585 tm->tm_yday, tm->tm_hour, tm->tm_min); 586 else 587 snprintf (buf, len, "%02dw%dd%02dh", 588 tm->tm_yday/7, tm->tm_yday - ((tm->tm_yday/7) * 7), tm->tm_hour); 589 590 return buf; 591} 592 593void 594bgp_damp_info_vty (struct vty *vty, struct bgp_info *binfo) 595{ 596 struct bgp_damp_info *bdi; 597 time_t t_now, t_diff; 598 char timebuf[BGP_UPTIME_LEN]; 599 int penalty; 600 601 /* BGP dampening information. */ 602 bdi = binfo->damp_info; 603 604 /* If dampening is not enabled or there is no dampening information, 605 return immediately. */ 606 if (! damp || ! bdi) 607 return; 608 609 /* Calculate new penalty. */ 610 t_now = time (NULL); 611 t_diff = t_now - bdi->t_updated; 612 penalty = bgp_damp_decay (t_diff, bdi->penalty); 613 614 vty_out (vty, " Dampinfo: penalty %d, flapped %d times in %s", 615 penalty, bdi->flap, 616 peer_uptime (bdi->start_time, timebuf, BGP_UPTIME_LEN)); 617 618 if (CHECK_FLAG (binfo->flags, BGP_INFO_DAMPED) 619 && ! CHECK_FLAG (binfo->flags, BGP_INFO_HISTORY)) 620 vty_out (vty, ", reuse in %s", 621 bgp_get_reuse_time (penalty, timebuf, BGP_UPTIME_LEN)); 622 623 vty_out (vty, "%s", VTY_NEWLINE); 624} 625 626char * 627bgp_damp_reuse_time_vty (struct vty *vty, struct bgp_info *binfo) 628{ 629 struct bgp_damp_info *bdi; 630 time_t t_now, t_diff; 631 char timebuf[BGP_UPTIME_LEN]; 632 int penalty; 633 634 /* BGP dampening information. */ 635 bdi = binfo->damp_info; 636 637 /* If dampening is not enabled or there is no dampening information, 638 return immediately. */ 639 if (! damp || ! bdi) 640 return NULL; 641 642 /* Calculate new penalty. */ 643 t_now = time (NULL); 644 t_diff = t_now - bdi->t_updated; 645 penalty = bgp_damp_decay (t_diff, bdi->penalty); 646 647 return bgp_get_reuse_time (penalty, timebuf, BGP_UPTIME_LEN); 648} 649