proto/ospf/neighbor.c

   1 /*
   2  *      BIRD -- OSPF
   3  *
   4  *      (c) 1999 - 2004 Ondrej Filip <feela@network.cz>
   5  *
   6  *      Can be freely distributed and used under the terms of the GNU GPL.
   7  */
   8
   9 #include "ospf.h"
  10
  11 char *ospf_ns[] = { "    down",
  12   " attempt",
  13   "    init",
  14   "    2way",
  15   " exstart",
  16   "exchange",
  17   " loading",
  18   "    full"
  19 };
  20
  21 const char *ospf_inm[] =
  22   { "hello received", "neighbor start", "2-way received",
  23   "negotiation done", "exstart done", "bad ls request", "load done",
  24   "adjacency ok?", "sequence mismatch", "1-way received", "kill neighbor",
  25   "inactivity timer", "line down"
  26 };
  27
  28 static void neigh_chstate(struct ospf_neighbor *n, u8 state);
  29 static struct ospf_neighbor *electbdr(list nl);
  30 static struct ospf_neighbor *electdr(list nl);
  31 static void neighbor_timer_hook(timer * timer);
  32 static void rxmt_timer_hook(timer * timer);
  33 static void ackd_timer_hook(timer * t);
  34
  35 static void
  36 init_lists(struct ospf_neighbor *n)
  37 {
  38   s_init_list(&(n->lsrql));
  39   n->lsrqh = ospf_top_new(n->pool);
  40   s_init(&(n->lsrqi), &(n->lsrql));
  41
  42   s_init_list(&(n->lsrtl));
  43   n->lsrth = ospf_top_new(n->pool);
  44   s_init(&(n->lsrti), &(n->lsrtl));
  45 }
  46
  47 /* Resets LSA request and retransmit lists.
  48  * We do not reset DB summary list iterator here,
  49  * it is reset during entering EXCHANGE state.
  50  */
  51 static void
  52 reset_lists(struct ospf_neighbor *n)
  53 {
  54   ospf_top_free(n->lsrqh);
  55   ospf_top_free(n->lsrth);
  56   init_lists(n);
  57 }
  58
  59 struct ospf_neighbor *
  60 ospf_neighbor_new(struct ospf_iface *ifa)
  61 {
  62   struct proto *p = (struct proto *) (ifa->oa->po);
  63   struct proto_ospf *po = ifa->oa->po;
  64   struct pool *pool = rp_new(p->pool, "OSPF Neighbor");
  65   struct ospf_neighbor *n = mb_allocz(pool, sizeof(struct ospf_neighbor));
  66
  67   n->pool = pool;
  68   n->ifa = ifa;
  69   add_tail(&ifa->neigh_list, NODE n);
  70   n->adj = 0;
  71   n->csn = 0;
  72   n->ldbdes = mb_allocz(pool, ifa->iface->mtu);
  73   n->state = NEIGHBOR_DOWN;
  74
  75   init_lists(n);
  76   s_init(&(n->dbsi), &(po->lsal));
  77
  78   n->inactim = tm_new(pool);
  79   n->inactim->data = n;
  80   n->inactim->randomize = 0;
  81   n->inactim->hook = neighbor_timer_hook;
  82   n->inactim->recurrent = 0;
  83   DBG("%s: Installing inactivity timer.\n", p->name);
  84
  85   n->rxmt_timer = tm_new(pool);
  86   n->rxmt_timer->data = n;
  87   n->rxmt_timer->randomize = 0;
  88   n->rxmt_timer->hook = rxmt_timer_hook;
  89   n->rxmt_timer->recurrent = ifa->rxmtint;
  90   tm_start(n->rxmt_timer, n->ifa->rxmtint);
  91   DBG("%s: Installing rxmt timer.\n", p->name);
  92
  93   n->ackd_timer = tm_new(pool);
  94   n->ackd_timer->data = n;
  95   n->ackd_timer->randomize = 0;
  96   n->ackd_timer->hook = ackd_timer_hook;
  97   n->ackd_timer->recurrent = ifa->rxmtint / 2;
  98   init_list(&n->ackl[ACKL_DIRECT]);
  99   init_list(&n->ackl[ACKL_DELAY]);
 100   tm_start(n->ackd_timer, n->ifa->rxmtint / 2);
 101   DBG("%s: Installing ackd timer.\n", p->name);
 102
 103   return (n);
 104 }
 105
 106 /**
 107  * neigh_chstate - handles changes related to new or lod state of neighbor
 108  * @n: OSPF neighbor
 109  * @state: new state
 110  *
 111  * Many actions have to be taken acording to a change of state of a neighbor. It
 112  * starts rxmt timers, call interface state machine etc.
 113  */
 114
 115 static void
 116 neigh_chstate(struct ospf_neighbor *n, u8 state)
 117 {
 118   u8 oldstate;
 119
 120   oldstate = n->state;
 121
 122   if (oldstate != state)
 123   {
 124     struct ospf_iface *ifa = n->ifa;
 125     struct proto_ospf *po = ifa->oa->po;
 126     struct proto *p = &po->proto;
 127
 128     n->state = state;
 129
 130     OSPF_TRACE(D_EVENTS, "Neighbor %I changes state from \"%s\" to \"%s\".",
 131                n->ip, ospf_ns[oldstate], ospf_ns[state]);
 132
 133     if ((state == NEIGHBOR_2WAY) && (oldstate < NEIGHBOR_2WAY))
 134       ospf_iface_sm(ifa, ISM_NEICH);
 135     if ((state < NEIGHBOR_2WAY) && (oldstate >= NEIGHBOR_2WAY))
 136       ospf_iface_sm(ifa, ISM_NEICH);
 137
 138     if (oldstate == NEIGHBOR_FULL)      /* Decrease number of adjacencies */
 139     {
 140       ifa->fadj--;
 141       schedule_rt_lsa(ifa->oa);
 142       if (ifa->type == OSPF_IT_VLINK) schedule_rt_lsa(ifa->voa);
 143       schedule_net_lsa(ifa);
 144     }
 145
 146     if (state == NEIGHBOR_FULL) /* Increase number of adjacencies */
 147     {
 148       ifa->fadj++;
 149       schedule_rt_lsa(ifa->oa);
 150       if (ifa->type == OSPF_IT_VLINK) schedule_rt_lsa(ifa->voa);
 151       schedule_net_lsa(ifa);
 152     }
 153     if (state == NEIGHBOR_EXSTART)
 154     {
 155       if (n->adj == 0)          /* First time adjacency */
 156       {
 157         n->dds = random_u32();
 158       }
 159       n->dds++;
 160       n->myimms.byte = 0;
 161       n->myimms.bit.ms = 1;
 162       n->myimms.bit.m = 1;
 163       n->myimms.bit.i = 1;
 164     }
 165     if (state > NEIGHBOR_EXSTART)
 166       n->myimms.bit.i = 0;
 167   }
 168 }
 169
 170 static struct ospf_neighbor *
 171 electbdr(list nl)
 172 {
 173   struct ospf_neighbor *neigh, *n1, *n2;
 174   u32 nid;
 175
 176   n1 = NULL;
 177   n2 = NULL;
 178   WALK_LIST(neigh, nl)                  /* First try those decl. themselves */
 179   {
 180 #ifdef OSPFv2
 181     nid = ipa_to_u32(neigh->ip);
 182 #else /* OSPFv3 */
 183     nid = neigh->rid;
 184 #endif
 185
 186     if (neigh->state >= NEIGHBOR_2WAY)  /* Higher than 2WAY */
 187       if (neigh->priority > 0)          /* Eligible */
 188         if (neigh->dr != nid)           /* And not decl. itself DR */
 189         {
 190           if (neigh->bdr == nid)        /* Declaring BDR */
 191           {
 192             if (n1 != NULL)
 193             {
 194               if (neigh->priority > n1->priority)
 195                 n1 = neigh;
 196               else if (neigh->priority == n1->priority)
 197                 if (neigh->rid > n1->rid)
 198                   n1 = neigh;
 199             }
 200             else
 201             {
 202               n1 = neigh;
 203             }
 204           }
 205           else                  /* And NOT declaring BDR */
 206           {
 207             if (n2 != NULL)
 208             {
 209               if (neigh->priority > n2->priority)
 210                 n2 = neigh;
 211               else if (neigh->priority == n2->priority)
 212                 if (neigh->rid > n2->rid)
 213                   n2 = neigh;
 214             }
 215             else
 216             {
 217               n2 = neigh;
 218             }
 219           }
 220         }
 221   }
 222   if (n1 == NULL)
 223     n1 = n2;
 224
 225   return (n1);
 226 }
 227
 228 static struct ospf_neighbor *
 229 electdr(list nl)
 230 {
 231   struct ospf_neighbor *neigh, *n;
 232   u32 nid;
 233
 234   n = NULL;
 235   WALK_LIST(neigh, nl)                  /* And now DR */
 236   {
 237 #ifdef OSPFv2
 238     nid = ipa_to_u32(neigh->ip);
 239 #else /* OSPFv3 */
 240     nid = neigh->rid;
 241 #endif
 242
 243     if (neigh->state >= NEIGHBOR_2WAY)  /* Higher than 2WAY */
 244       if (neigh->priority > 0)          /* Eligible */
 245         if (neigh->dr == nid)           /* And declaring itself DR */
 246         {
 247           if (n != NULL)
 248           {
 249             if (neigh->priority > n->priority)
 250               n = neigh;
 251             else if (neigh->priority == n->priority)
 252               if (neigh->rid > n->rid)
 253                 n = neigh;
 254           }
 255           else
 256           {
 257             n = neigh;
 258           }
 259         }
 260   }
 261
 262   return (n);
 263 }
 264
 265 static int
 266 can_do_adj(struct ospf_neighbor *n)
 267 {
 268   struct ospf_iface *ifa;
 269   struct proto *p;
 270   int i;
 271
 272   ifa = n->ifa;
 273   p = (struct proto *) (ifa->oa->po);
 274   i = 0;
 275
 276   switch (ifa->type)
 277   {
 278   case OSPF_IT_PTP:
 279   case OSPF_IT_PTMP:
 280   case OSPF_IT_VLINK:
 281     i = 1;
 282     break;
 283   case OSPF_IT_BCAST:
 284   case OSPF_IT_NBMA:
 285     switch (ifa->state)
 286     {
 287     case OSPF_IS_DOWN:
 288     case OSPF_IS_LOOP:
 289       bug("%s: Iface %s in down state?", p->name, ifa->iface->name);
 290       break;
 291     case OSPF_IS_WAITING:
 292       DBG("%s: Neighbor? on iface %s\n", p->name, ifa->iface->name);
 293       break;
 294     case OSPF_IS_DROTHER:
 295       if (((n->rid == ifa->drid) || (n->rid == ifa->bdrid))
 296           && (n->state >= NEIGHBOR_2WAY))
 297         i = 1;
 298       break;
 299     case OSPF_IS_PTP:
 300     case OSPF_IS_BACKUP:
 301     case OSPF_IS_DR:
 302       if (n->state >= NEIGHBOR_2WAY)
 303         i = 1;
 304       break;
 305     default:
 306       bug("%s: Iface %s in unknown state?", p->name, ifa->iface->name);
 307       break;
 308     }
 309     break;
 310   default:
 311     bug("%s: Iface %s is unknown type?", p->name, ifa->iface->name);
 312     break;
 313   }
 314   DBG("%s: Iface %s can_do_adj=%d\n", p->name, ifa->iface->name, i);
 315   return i;
 316 }
 317
 318 /**
 319  * ospf_neigh_sm - ospf neighbor state machine
 320  * @n: neighor
 321  * @event: actual event
 322  *
 323  * This part implements the neighbor state machine as described in 10.3 of
 324  * RFC 2328. The only difference is that state %NEIGHBOR_ATTEMPT is not
 325  * used. We discover neighbors on nonbroadcast networks in the
 326  * same way as on broadcast networks. The only difference is in
 327  * sending hello packets. These are sent to IPs listed in
 328  * @ospf_iface->nbma_list .
 329  */
 330 void
 331 ospf_neigh_sm(struct ospf_neighbor *n, int event)
 332 {
 333   struct proto_ospf *po = n->ifa->oa->po;
 334   struct proto *p = &po->proto;
 335
 336   DBG("Neighbor state machine for neighbor %I, event '%s'\n", n->ip,
 337              ospf_inm[event]);
 338
 339   switch (event)
 340   {
 341   case INM_START:
 342     neigh_chstate(n, NEIGHBOR_ATTEMPT);
 343     /* NBMA are used different way */
 344     break;
 345   case INM_HELLOREC:
 346     switch (n->state)
 347     {
 348     case NEIGHBOR_ATTEMPT:
 349     case NEIGHBOR_DOWN:
 350       neigh_chstate(n, NEIGHBOR_INIT);
 351     default:
 352       tm_start(n->inactim, n->ifa->deadint);    /* Restart inactivity timer */
 353       break;
 354     }
 355     break;
 356   case INM_2WAYREC:
 357     if (n->state < NEIGHBOR_2WAY)
 358       neigh_chstate(n, NEIGHBOR_2WAY);
 359     if ((n->state == NEIGHBOR_2WAY) && can_do_adj(n))
 360       neigh_chstate(n, NEIGHBOR_EXSTART);
 361     break;
 362   case INM_NEGDONE:
 363     if (n->state == NEIGHBOR_EXSTART)
 364     {
 365       neigh_chstate(n, NEIGHBOR_EXCHANGE);
 366
 367       /* Reset DB summary list iterator */
 368       s_get(&(n->dbsi));
 369       s_init(&(n->dbsi), &po->lsal);
 370
 371       while (!EMPTY_LIST(n->ackl[ACKL_DELAY]))
 372       {
 373         struct lsah_n *no;
 374         no = (struct lsah_n *) HEAD(n->ackl[ACKL_DELAY]);
 375         rem_node(NODE no);
 376         mb_free(no);
 377       }
 378     }
 379     else
 380       bug("NEGDONE and I'm not in EXSTART?");
 381     break;
 382   case INM_EXDONE:
 383     neigh_chstate(n, NEIGHBOR_LOADING);
 384     break;
 385   case INM_LOADDONE:
 386     neigh_chstate(n, NEIGHBOR_FULL);
 387     break;
 388   case INM_ADJOK:
 389     switch (n->state)
 390     {
 391     case NEIGHBOR_2WAY:
 392       /* Can In build adjacency? */
 393       if (can_do_adj(n))
 394       {
 395         neigh_chstate(n, NEIGHBOR_EXSTART);
 396       }
 397       break;
 398     default:
 399       if (n->state >= NEIGHBOR_EXSTART)
 400         if (!can_do_adj(n))
 401         {
 402           reset_lists(n);
 403           neigh_chstate(n, NEIGHBOR_2WAY);
 404         }
 405       break;
 406     }
 407     break;
 408   case INM_SEQMIS:
 409   case INM_BADLSREQ:
 410     if (n->state >= NEIGHBOR_EXCHANGE)
 411     {
 412       reset_lists(n);
 413       neigh_chstate(n, NEIGHBOR_EXSTART);
 414     }
 415     break;
 416   case INM_KILLNBR:
 417   case INM_LLDOWN:
 418   case INM_INACTTIM:
 419     reset_lists(n);
 420     neigh_chstate(n, NEIGHBOR_DOWN);
 421     break;
 422   case INM_1WAYREC:
 423     reset_lists(n);
 424     neigh_chstate(n, NEIGHBOR_INIT);
 425     break;
 426   default:
 427     bug("%s: INM - Unknown event?", p->name);
 428     break;
 429   }
 430 }
 431
 432 /**
 433  * bdr_election - (Backup) Designed Router election
 434  * @ifa: actual interface
 435  *
 436  * When the wait timer fires, it is time to elect (Backup) Designated Router.
 437  * Structure describing me is added to this list so every electing router
 438  * has the same list. Backup Designated Router is elected before Designated
 439  * Router. This process is described in 9.4 of RFC 2328.
 440  */
 441 void
 442 bdr_election(struct ospf_iface *ifa)
 443 {
 444   struct proto_ospf *po = ifa->oa->po;
 445   u32 myid = po->router_id;
 446   struct ospf_neighbor *neigh, *ndr, *nbdr, me;
 447   int doadj;
 448
 449   DBG("(B)DR election.\n");
 450
 451   me.state = NEIGHBOR_2WAY;
 452   me.rid = myid;
 453   me.priority = ifa->priority;
 454   me.ip = ifa->addr->ip;
 455
 456 #ifdef OSPFv2
 457   me.dr = ipa_to_u32(ifa->drip);
 458   me.bdr = ipa_to_u32(ifa->bdrip);
 459 #else /* OSPFv3 */
 460   me.dr = ifa->drid;
 461   me.bdr = ifa->bdrid;
 462   me.iface_id = ifa->iface->index;
 463 #endif
 464
 465   add_tail(&ifa->neigh_list, NODE & me);
 466
 467   nbdr = electbdr(ifa->neigh_list);
 468   ndr = electdr(ifa->neigh_list);
 469
 470   if (ndr == NULL)
 471     ndr = nbdr;
 472
 473   /* 9.4. (4) */
 474   if (((ifa->drid == myid) && (ndr != &me))
 475       || ((ifa->drid != myid) && (ndr == &me))
 476       || ((ifa->bdrid == myid) && (nbdr != &me))
 477       || ((ifa->bdrid != myid) && (nbdr == &me)))
 478   {
 479 #ifdef OSPFv2
 480     me.dr = ndr ? ipa_to_u32(ndr->ip) : 0;
 481     me.bdr = nbdr ? ipa_to_u32(nbdr->ip) : 0;
 482 #else /* OSPFv3 */
 483     me.dr = ndr ? ndr->rid : 0;
 484     me.bdr = nbdr ? nbdr->rid : 0;
 485 #endif
 486
 487     nbdr = electbdr(ifa->neigh_list);
 488     ndr = electdr(ifa->neigh_list);
 489
 490     if (ndr == NULL)
 491       ndr = nbdr;
 492   }
 493
 494   u32 odrid = ifa->drid;
 495   u32 obdrid = ifa->bdrid;
 496
 497   ifa->drid = ndr ? ndr->rid : 0;
 498   ifa->drip = ndr ? ndr->ip  : IPA_NONE;
 499   ifa->bdrid = nbdr ? nbdr->rid : 0;
 500   ifa->bdrip = nbdr ? nbdr->ip  : IPA_NONE;
 501
 502 #ifdef OSPFv3
 503   ifa->dr_iface_id = ndr ? ndr->iface_id : 0;
 504 #endif
 505
 506   DBG("DR=%R, BDR=%R\n", ifa->drid, ifa->bdrid);
 507
 508   doadj = ((ifa->drid != odrid) || (ifa->bdrid != obdrid));
 509
 510   if (myid == ifa->drid)
 511     ospf_iface_chstate(ifa, OSPF_IS_DR);
 512   else
 513   {
 514     if (myid == ifa->bdrid)
 515       ospf_iface_chstate(ifa, OSPF_IS_BACKUP);
 516     else
 517       ospf_iface_chstate(ifa, OSPF_IS_DROTHER);
 518   }
 519
 520   rem_node(NODE & me);
 521
 522   if (doadj)
 523   {
 524     WALK_LIST(neigh, ifa->neigh_list)
 525     {
 526       ospf_neigh_sm(neigh, INM_ADJOK);
 527     }
 528   }
 529 }
 530
 531 struct ospf_neighbor *
 532 find_neigh(struct ospf_iface *ifa, u32 rid)
 533 {
 534   struct ospf_neighbor *n;
 535   WALK_LIST(n, ifa->neigh_list)
 536     if (n->rid == rid)
 537       return n;
 538   return NULL;
 539 }
 540
 541 struct ospf_neighbor *
 542 find_neigh_by_ip(struct ospf_iface *ifa, ip_addr ip)
 543 {
 544   struct ospf_neighbor *n;
 545   WALK_LIST(n, ifa->neigh_list)
 546     if (ipa_equal(n->ip, ip))
 547       return n;
 548   return NULL;
 549 }
 550
 551 /* Neighbor is inactive for a long time. Remove it. */
 552 static void
 553 neighbor_timer_hook(timer * timer)
 554 {
 555   struct ospf_neighbor *n = (struct ospf_neighbor *) timer->data;
 556   struct ospf_iface *ifa = n->ifa;
 557   struct proto *p = &ifa->oa->po->proto;
 558
 559   OSPF_TRACE(D_EVENTS,
 560              "Inactivity timer fired on interface %s for neighbor %I.",
 561              ifa->iface->name, n->ip);
 562   ospf_neigh_remove(n);
 563 }
 564
 565 void
 566 ospf_neigh_remove(struct ospf_neighbor *n)
 567 {
 568   struct ospf_iface *ifa = n->ifa;
 569   struct proto *p = &ifa->oa->po->proto;
 570
 571   if ((ifa->type == OSPF_IT_NBMA) || (ifa->type == OSPF_IT_PTMP))
 572   {
 573     struct nbma_node *nn = find_nbma_node(ifa, n->ip);
 574     if (nn)
 575       nn->found = 0;
 576   }
 577
 578   s_get(&(n->dbsi));
 579   neigh_chstate(n, NEIGHBOR_DOWN);
 580   rem_node(NODE n);
 581   rfree(n->pool);
 582   OSPF_TRACE(D_EVENTS, "Deleting neigbor.");
 583 }
 584
 585 void
 586 ospf_sh_neigh_info(struct ospf_neighbor *n)
 587 {
 588   struct ospf_iface *ifa = n->ifa;
 589   char *pos = "other";
 590   char etime[6];
 591   int exp, sec, min;
 592
 593   exp = n->inactim->expires - now;
 594   sec = exp % 60;
 595   min = exp / 60;
 596   if (min > 59)
 597   {
 598     bsprintf(etime, "-Inf-");
 599   }
 600   else
 601   {
 602     bsprintf(etime, "%02u:%02u", min, sec);
 603   }
 604
 605   if (n->rid == ifa->drid)
 606     pos = "dr   ";
 607   else if (n->rid == ifa->bdrid)
 608     pos = "bdr  ";
 609   else if ((n->ifa->type == OSPF_IT_PTP) || (n->ifa->type == OSPF_IT_PTMP) ||
 610            (n->ifa->type == OSPF_IT_VLINK))
 611     pos = "ptp  ";
 612
 613   cli_msg(-1013, "%-1R\t%3u\t%s/%s\t%-5s\t%-10s %-1I", n->rid, n->priority,
 614           ospf_ns[n->state], pos, etime,
 615           (ifa->type == OSPF_IT_VLINK ? "vlink" : ifa->iface->name), n->ip);
 616 }
 617
 618 static void
 619 rxmt_timer_hook(timer * timer)
 620 {
 621   struct ospf_neighbor *n = (struct ospf_neighbor *) timer->data;
 622   // struct proto *p = &n->ifa->oa->po->proto;
 623   struct top_hash_entry *en;
 624
 625   DBG("%s: RXMT timer fired on interface %s for neigh: %I.\n",
 626       p->name, n->ifa->iface->name, n->ip);
 627
 628   if(n->state < NEIGHBOR_EXSTART) return;
 629
 630   if (n->state == NEIGHBOR_EXSTART)
 631   {
 632     ospf_dbdes_send(n, 1);
 633     return;
 634   }
 635
 636   if ((n->state == NEIGHBOR_EXCHANGE) && n->myimms.bit.ms)      /* I'm master */
 637     ospf_dbdes_send(n, 0);
 638
 639
 640   if (n->state < NEIGHBOR_FULL)
 641     ospf_lsreq_send(n); /* EXCHANGE or LOADING */
 642   else
 643   {
 644     if (!EMPTY_SLIST(n->lsrtl)) /* FULL */
 645     {
 646       list uplist;
 647       slab *upslab;
 648       struct l_lsr_head *llsh;
 649
 650       init_list(&uplist);
 651       upslab = sl_new(n->pool, sizeof(struct l_lsr_head));
 652
 653       WALK_SLIST(en, n->lsrtl)
 654       {
 655         if ((SNODE en)->next == (SNODE en))
 656           bug("RTList is cycled");
 657         llsh = sl_alloc(upslab);
 658         llsh->lsh.id = en->lsa.id;
 659         llsh->lsh.rt = en->lsa.rt;
 660         llsh->lsh.type = en->lsa.type;
 661         DBG("Working on ID: %R, RT: %R, Type: %u\n",
 662             en->lsa.id, en->lsa.rt, en->lsa.type);
 663         add_tail(&uplist, NODE llsh);
 664       }
 665       ospf_lsupd_send_list(n, &uplist);
 666       rfree(upslab);
 667     }
 668   }
 669 }
 670
 671 static void
 672 ackd_timer_hook(timer * t)
 673 {
 674   struct ospf_neighbor *n = t->data;
 675   ospf_lsack_send(n, ACKL_DELAY);
 676 }