proto/ospf/neighbor.c

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