release/src/router/zebra/bgpd/bgp_damp.c

   1 /* BGP flap dampening
   2  * Copyright (C) 2001 IP Infusion Inc.
   3  *
   4  * This file is part of GNU Zebra.
   5  *
   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
   9  * later version.
  10  *
  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.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with GNU Zebra; see the file COPYING.  If not, write to the Free
  18  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  19  * 02111-1307, USA.
  20  */
  21
  22 #include <zebra.h>
  23 #include <math.h>
  24
  25 #include "prefix.h"
  26 #include "table.h"
  27 #include "linklist.h"
  28 #include "memory.h"
  29 #include "command.h"
  30 #include "stream.h"
  31 #include "filter.h"
  32 #include "str.h"
  33 #include "log.h"
  34 #include "routemap.h"
  35 #include "buffer.h"
  36 #include "sockunion.h"
  37 #include "plist.h"
  38 #include "thread.h"
  39
  40 #include "bgpd/bgp_damp.h"
  41 #include "bgpd/bgpd.h"
  42 #include "bgpd/bgp_route.h"
  43
  44 /* Time granularity for reuse lists */
  45 #define DELTA_REUSE 15
  46 /* Time granularity for decay arrays */
  47 #define DELTA_T 1
  48
  49 #define DEFAULT_PENALTY 1000
  50
  51 #define DEFAULT_HARF_LIFE 15
  52 #define DEFAULT_REUSE 750
  53 #define DEFAULT_SUPPRESS 2000
  54 #define REUSE_LIST_SIZE         256
  55 #define REUSE_ARRAY_SIZE        1024
  56
  57 /* Global variable to access damping configuration */
  58 struct bgp_damp_config bgp_damp_cfg;
  59 int reuse_array_offset = 0;
  60 struct thread *bgp_reuse_thread = NULL;
  61 struct bgp_damp_config *prev_bgp_damp_cfg = NULL;
  62
  63 int bgp_reuse_timer(struct thread *);
  64 void bgp_damp_clear_config(struct bgp_damp_config *);
  65 void bgp_damp_clear_reuse_list();
  66
  67 int
  68 bgp_damp_init(struct vty *vty, int hlife, int reuse, int sup, int maxsup)
  69 {
  70   double reuse_max_ratio;
  71   int i;
  72   struct bgp_damp_config *bdc;
  73
  74   if (hlife == -1)
  75     hlife = DEFAULT_HARF_LIFE * 60;
  76
  77   if (reuse == -1)
  78     {
  79       /* Default values */
  80       reuse = DEFAULT_REUSE;
  81       sup = DEFAULT_SUPPRESS;
  82       maxsup = 4*hlife;
  83     }
  84
  85   /* Clear previous configuration if any */
  86   if (prev_bgp_damp_cfg)
  87     bgp_damp_clear_config (&bgp_damp_cfg);
  88
  89   prev_bgp_damp_cfg = bdc = &bgp_damp_cfg;
  90   bdc->suppress_value = sup;
  91   bdc->half_life = hlife;
  92   bdc->reuse_limit = reuse;
  93   bdc->max_suppress_time = maxsup;
  94
  95   /* Initialize system-wide params */
  96   bdc->reuse_list_size = REUSE_LIST_SIZE;
  97   bdc->reuse_index_array_size = REUSE_ARRAY_SIZE;
  98
  99   bdc->ceiling = (int)(bdc->reuse_limit *
 100                        exp((double) (bdc->max_suppress_time/bdc->half_life)) * log(2.0));
 101
 102   /* Decay-array computations */
 103   bdc->decay_array_size = ceil ((double)bdc->max_suppress_time/DELTA_T);
 104   bdc->decay_array = XMALLOC (MTYPE_BGP_DAMP_ARRAY,
 105                               sizeof(double) * (bdc->decay_array_size));
 106   bdc->decay_array[0] = 1.0;
 107   bdc->decay_array[1] = exp ((1.0/(bdc->half_life/DELTA_T)) * log(0.5));
 108
 109   /* Calculate decay values for all possible times */
 110   for (i = 2; i < bdc->decay_array_size; i++)
 111     bdc->decay_array[i] = bdc->decay_array[i-1] * bdc->decay_array[1];
 112
 113   /* Reuse-list computations */
 114   bdc->reuse_list_array = XMALLOC (MTYPE_BGP_DAMP_ARRAY, bdc->reuse_list_size * sizeof (struct bgp_reuse_list *));
 115   memset (bdc->reuse_list_array, 0x00, bdc->reuse_list_size * sizeof (struct bgp_reuse_list*));
 116
 117   /* Reuse-array computations */
 118   bdc->reuse_index_array = XMALLOC (MTYPE_BGP_DAMP_ARRAY,
 119                                     sizeof(int) * bdc->reuse_index_array_size);
 120   reuse_max_ratio = bdc->ceiling/bdc->reuse_limit;
 121   i = (int)exp((1.0/((double)bdc->half_life/(bdc->reuse_list_size*DELTA_REUSE))) * log(2.0));
 122   if ( reuse_max_ratio > i && i != 0 )
 123         reuse_max_ratio = i;
 124
 125   bdc->scale_factor = ceil((double)bdc->reuse_index_array_size/(reuse_max_ratio - 1));
 126
 127   for (i = 0; i < bdc->reuse_index_array_size; i++)
 128     {
 129       bdc->reuse_index_array[i] =
 130                 ceil( (bdc->half_life/DELTA_REUSE)
 131                 * log(1.0/(bdc->reuse_limit * ( 1.0 + ((double)i/bdc->scale_factor)))) / log(0.5) );
 132     }
 133
 134   return CMD_SUCCESS;
 135 }
 136
 137 static double
 138 bgp_damp_get_decay(time_t tdiff)
 139 {
 140   int i;
 141   struct bgp_damp_config *bdc;
 142
 143   bdc = &bgp_damp_cfg;
 144   i = tdiff/DELTA_T;
 145
 146   if (i >= bdc->decay_array_size)
 147     return 0;
 148
 149   return bdc->decay_array[i];
 150 }
 151
 152 static int
 153 bgp_get_reuse_index(int penalty)
 154 {
 155   int i;
 156   struct bgp_damp_config *bdc;
 157
 158   bdc = &bgp_damp_cfg;
 159   i = (int)(((double)penalty / bdc->reuse_limit - 1.0) * bdc->scale_factor);
 160
 161   if ( i >= bdc->reuse_index_array_size )
 162           i = bdc->reuse_index_array_size - 1;
 163   return (bdc->reuse_index_array[i]);
 164 }
 165
 166 static void
 167 bgp_reuse_list_insert(struct bgp_damp_info *bdi)
 168 {
 169   int index;
 170   struct bgp_damp_config *bdc;
 171   static int first_time_insert = 1;
 172
 173   if (first_time_insert)
 174     {
 175       /* Kick off reuse timer */
 176       bgp_reuse_thread
 177         = thread_add_timer (master, bgp_reuse_timer, NULL, DELTA_REUSE);
 178       first_time_insert = 0;
 179     }
 180
 181   bdc = &bgp_damp_cfg;
 182
 183   index = (reuse_array_offset + bgp_get_reuse_index(bdi->penalty)) % bdc->reuse_list_size;
 184   bdi->reuse_next = bdc->reuse_list_array[index];
 185   bdc->reuse_list_array[index] = bdi;
 186
 187   return;
 188 }
 189
 190 /* bgp_reuse_timer is called every DELTA_REUSE seconds.
 191  * Each route in the current reuse-list is evaluated and is used or requeued
 192  */
 193 int
 194 bgp_reuse_timer(struct thread *t)
 195 {
 196   struct bgp_damp_info *bdi, *tbdi;
 197   struct bgp_damp_config *bdc;
 198   time_t t_now, t_diff;
 199
 200   /* Restart the reuse timer */
 201   bgp_reuse_thread = thread_add_timer(master, bgp_reuse_timer,
 202                                       NULL, DELTA_REUSE);
 203
 204   /* zlog(NULL, LOG_INFO, "DAMP:reuse timer:offset: %d", reuse_array_offset); */
 205   t_now = time(NULL);
 206   bdc = &bgp_damp_cfg;
 207   bdi = bdc->reuse_list_array[reuse_array_offset];
 208   bdc->reuse_list_array[reuse_array_offset] = NULL;
 209   reuse_array_offset = (reuse_array_offset + 1 ) % bdc->reuse_list_size;
 210
 211   while (bdi)
 212     {
 213       tbdi = bdi->reuse_next;
 214       bdi->reuse_next = NULL;
 215       t_diff = t_now - bdi->t_updated;
 216       bdi->t_updated = t_now;
 217
 218       if (bdi->bgp_info == NULL )
 219         free(bdi);
 220       else
 221         {
 222           bdi->penalty
 223             = (int)((double)bdi->penalty * bgp_damp_get_decay(t_diff));
 224
 225           /* zlog(NULL, LOG_INFO, "DAMP:reuse timer: updated penalty: %d", bdi->penalty); */
 226
 227           if ( bdi->penalty <= bdc->reuse_limit/2 )
 228             {
 229               UNSET_FLAG (bdi->bgp_info->flags, BGP_INFO_DAMPED);
 230               bdi->bgp_info->bgp_damp_info = NULL;
 231               free(bdi);
 232             }
 233           else if ( bdi->penalty < bdc->reuse_limit )
 234             UNSET_FLAG (bdi->bgp_info->flags, BGP_INFO_DAMPED);
 235           else
 236             bgp_reuse_list_insert(bdi);
 237         }
 238
 239       bdi = tbdi;
 240     }
 241
 242   return 0;
 243 }
 244
 245 int
 246 bgp_damp_withdraw(struct bgp_info *bgp_info)
 247 {
 248   time_t t_now;
 249   struct bgp_damp_info *bdi;
 250   struct bgp_damp_config *bdc;
 251   int status;
 252
 253   bdc = &bgp_damp_cfg;
 254
 255   if (! bdc->enabled)
 256     return BGP_DAMP_DISABLED;
 257
 258   SET_FLAG (bgp_info->flags, BGP_INFO_HISTORY);
 259
 260   t_now = time(NULL);
 261   bdi = bgp_info->bgp_damp_info;
 262
 263   status = BGP_DAMP_CONTINUE;
 264
 265   if (bdi == NULL)
 266     {
 267       bdi = XMALLOC (MTYPE_BGP_DAMP_INFO, sizeof (struct bgp_damp_info));
 268       memset (bdi, 0, sizeof (struct bgp_damp_info));
 269       bgp_info->bgp_damp_info = bdi;
 270       bdi->penalty = DEFAULT_PENALTY;
 271       bdi->flap = 1;
 272       bdi->start_time = t_now;
 273       bdi->bgp_info = bgp_info;
 274     }
 275   else
 276     {
 277       bdi->penalty = (int)(bdi->penalty * bgp_damp_get_decay(t_now - bdi->t_updated)) + DEFAULT_PENALTY;
 278       bdi->flap++;
 279       if (bdi->penalty > bdc->ceiling)
 280         bdi->penalty = bdc->ceiling;
 281     }
 282
 283   /* If the penalty is greater than suppress value or the route is damped,
 284    * no need to send withdraw to peers.
 285    */
 286   if (CHECK_FLAG (bdi->bgp_info->flags, BGP_INFO_DAMPED))
 287     status = BGP_DAMP_DISCONTINUE;
 288   else if (bdi->penalty >= bdc->suppress_value)
 289     {
 290       bgp_reuse_list_insert(bdi);
 291       SET_FLAG (bdi->bgp_info->flags, BGP_INFO_DAMPED);
 292     }
 293   bdi->t_updated = t_now;
 294
 295   /* zlog(NULL, LOG_ERR, "DAMP:Withdraw - penalty: %d, damped: %d", bdi->penalty, bdi->bgp_info->damped); */
 296
 297   return (status);
 298 }
 299
 300 int
 301 bgp_damp_update(struct bgp_info *bgp_info)
 302 {
 303   time_t t_now;
 304   struct bgp_damp_info *bdi;
 305   struct bgp_damp_config *bdc;
 306   int status;
 307
 308   bdc = &bgp_damp_cfg;
 309
 310   if (! bdc->enabled)
 311     return BGP_DAMP_DISABLED;
 312
 313   if ((bdi = bgp_info->bgp_damp_info) == NULL)
 314     return BGP_DAMP_CONTINUE;
 315
 316   t_now = time(NULL);
 317   bdi->penalty = (int) (bdi->penalty * bgp_damp_get_decay(t_now - bdi->t_updated));
 318
 319   /* zlog(NULL, LOG_ERR, "UPDATE: penalty: %d", bdi->penalty); */
 320   if (! CHECK_FLAG (bgp_info->flags, BGP_INFO_DAMPED)
 321       && (bdi->penalty < bdc->suppress_value))
 322     {
 323       status = BGP_DAMP_CONTINUE;
 324     }
 325   else if (CHECK_FLAG (bgp_info->flags, BGP_INFO_DAMPED)
 326            && (bdi->penalty < bdc->reuse_limit) )
 327     {
 328       UNSET_FLAG (bgp_info->flags, BGP_INFO_DAMPED);
 329       status = BGP_DAMP_CONTINUE;
 330     }
 331   else
 332     status = BGP_DAMP_DISCONTINUE;
 333
 334   bdi->t_updated = t_now;
 335
 336   return status;
 337 }
 338
 339 int
 340 bgp_damp_enable(struct vty *vty, int argc, char **argv)
 341 {
 342
 343   bgp_damp_cfg.enabled = 1;
 344
 345   if (argc == 0)
 346     {
 347       if (prev_bgp_damp_cfg)
 348         {
 349           if (! bgp_reuse_thread)
 350             bgp_reuse_thread
 351               = thread_add_timer(master, bgp_reuse_timer, NULL, DELTA_REUSE);
 352
 353           /* zlog(NULL, LOG_ERR, "Using old config"); */
 354
 355           return CMD_SUCCESS;
 356         }
 357
 358       /* zlog(NULL, LOG_ERR, "Using new config"); */
 359
 360       return bgp_damp_init(vty, -1, -1, -1, -1);
 361     }
 362
 363   if ( argc == 1 )
 364     {
 365       return bgp_damp_init (vty, atoi(argv[0])*60, -1, -1, -1);
 366     }
 367
 368   return bgp_damp_init (vty, atoi(argv[0]) * 60, atoi(argv[1]), atoi(argv[2]),
 369                         atoi(argv[3]) * 60);
 370 }
 371
 372 int
 373 bgp_damp_disable( struct vty *vty )
 374 {
 375   bgp_damp_cfg.enabled = 0;
 376
 377   if ( bgp_reuse_thread )
 378     thread_cancel (bgp_reuse_thread);
 379
 380   bgp_reuse_thread = NULL;
 381
 382   /* Clear the reuse list entries */
 383   bgp_damp_clear_reuse_list();
 384
 385   /* Clear configuration */
 386   bgp_damp_clear_config(&bgp_damp_cfg);
 387
 388   return CMD_SUCCESS;
 389 }
 390
 391 void
 392 bgp_damp_clear_config(struct bgp_damp_config *bdc)
 393 {
 394   /* Free decay array */
 395   free (bdc->decay_array);
 396
 397   /* Free reuse index array */
 398   free (bdc->reuse_index_array);
 399
 400   if ( bgp_reuse_thread )
 401     thread_cancel (bgp_reuse_thread);
 402   bgp_reuse_thread = NULL;
 403
 404   /* Remove all entries from reuse lists */
 405   prev_bgp_damp_cfg = NULL;
 406 }
 407
 408 void
 409 bgp_damp_clear_reuse_list()
 410 {
 411   struct bgp_damp_info *bdi, *tbdi;
 412   struct bgp_damp_config *bdc;
 413   int i;
 414
 415   reuse_array_offset = 0;
 416   bdc = &bgp_damp_cfg;
 417
 418   for (i = 0; i < bdc->reuse_list_size; i++)
 419     {
 420       if (bdc->reuse_list_array[i] == NULL)
 421         continue;
 422
 423       bdi = bdc->reuse_list_array[i];
 424       bdc->reuse_list_array[i] = NULL;
 425
 426       while (bdi)
 427         {
 428           tbdi = bdi->reuse_next;
 429
 430           if (bdi->bgp_info)
 431             {
 432               bdi->bgp_info->bgp_damp_info = NULL;
 433               UNSET_FLAG (bdi->bgp_info->flags, BGP_INFO_DAMPED);
 434             }
 435
 436           free (bdi);
 437           bdi = tbdi;
 438         }
 439     }
 440 }
 441
 442 int
 443 bgp_config_write_damp (struct vty *vty)
 444 {
 445   if (bgp_damp_cfg.enabled)
 446     {
 447       if (bgp_damp_cfg.half_life == DEFAULT_HARF_LIFE*60
 448           && bgp_damp_cfg.reuse_limit == DEFAULT_REUSE
 449           && bgp_damp_cfg.suppress_value == DEFAULT_SUPPRESS
 450           && bgp_damp_cfg.max_suppress_time == bgp_damp_cfg.half_life*4)
 451         vty_out (vty, " bgp dampening%s", VTY_NEWLINE);
 452       else if (bgp_damp_cfg.half_life != DEFAULT_HARF_LIFE*60
 453                && bgp_damp_cfg.reuse_limit == DEFAULT_REUSE
 454                && bgp_damp_cfg.suppress_value == DEFAULT_SUPPRESS
 455                && bgp_damp_cfg.max_suppress_time == bgp_damp_cfg.half_life*4)
 456         vty_out (vty, " bgp dampening %d%s",
 457                  bgp_damp_cfg.half_life/60,
 458                  VTY_NEWLINE);
 459       else
 460         vty_out (vty, " bgp dampening %d %d %d %d%s",
 461                  bgp_damp_cfg.half_life/60,
 462                  bgp_damp_cfg.reuse_limit,
 463                  bgp_damp_cfg.suppress_value,
 464                  bgp_damp_cfg.max_suppress_time/60,
 465                  VTY_NEWLINE);
 466       return 1;
 467     }
 468   return 0;
 469 }
 470
 471 #define BGP_UPTIME_LEN 25
 472
 473 int
 474 bgp_damp_info_print (struct vty *vty, struct bgp_info *bgp_info)
 475 {
 476   struct bgp_damp_info *bdi;
 477   time_t t_now;
 478   char timebuf[BGP_UPTIME_LEN];
 479
 480   if ((bdi = bgp_info->bgp_damp_info) == NULL)
 481     return CMD_WARNING;
 482   t_now = time (NULL);
 483   vty_out (vty, "      Dampinfo: penalty %d, flapped %d times in %s",
 484            (int)(bdi->penalty * bgp_damp_get_decay(t_now - bdi->t_updated)),
 485            bdi->flap, peer_uptime (bdi->start_time, timebuf, BGP_UPTIME_LEN));
 486   if (CHECK_FLAG (bdi->bgp_info->flags, BGP_INFO_DAMPED)
 487       && ! CHECK_FLAG (bdi->bgp_info->flags, BGP_INFO_HISTORY))
 488     vty_out (vty, ", reuse in 00:00:00");
 489   vty_out (vty, "%s", VTY_NEWLINE);
 490
 491   return CMD_SUCCESS;
 492 }