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