Statistics
| Branch: | Revision:

iof-bird-daemon / proto / ospf / neighbor.c @ 035f6acb

History | View | Annotate | Download (12.4 KB)

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 have to be taken acording to a change of state of a 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
    if(state<NEIGHBOR_EXSTART) tm_stop(n->rxmt_timer);
90
    if(state>NEIGHBOR_EXSTART) n->myimms.bit.i=0;
91
  }
92
}
93

    
94
struct ospf_neighbor *
95
electbdr(list nl)
96
{
97
  struct ospf_neighbor *neigh,*n1,*n2;
98

    
99
  n1=NULL;
100
  n2=NULL;
101
  WALK_LIST (neigh, nl)                /* First try those decl. themselves */
102
  {
103
    if(neigh->state>=NEIGHBOR_2WAY)        /* Higher than 2WAY */
104
      if(neigh->priority>0)                /* Eligible */
105
        if(ipa_compare(neigh->ip,neigh->dr)!=0)        /* And not decl. itself DR */
106
        {
107
          if(ipa_compare(neigh->ip,neigh->bdr)==0)        /* Declaring BDR */
108
          {
109
            if(n1!=NULL)
110
            {
111
              if(neigh->priority>n1->priority) n1=neigh;
112
              else if(neigh->priority==n1->priority)
113
                  if(neigh->rid>n1->rid) n1=neigh;
114
            }
115
            else
116
            {
117
              n1=neigh;
118
            }
119
          }
120
          else                                /* And NOT declaring BDR */
121
          {
122
            if(n2!=NULL)
123
            {
124
              if(neigh->priority>n2->priority) n2=neigh;
125
              else if(neigh->priority==n2->priority)
126
                  if(neigh->rid>n2->rid) n2=neigh;
127
            }
128
            else
129
            {
130
              n2=neigh;
131
            }
132
          }
133
      }
134
  }
135
  if(n1==NULL) n1=n2;
136

    
137
  return(n1);
138
}
139

    
140
struct ospf_neighbor *
141
electdr(list nl)
142
{
143
  struct ospf_neighbor *neigh,*n;
144

    
145
  n=NULL;
146
  WALK_LIST (neigh, nl)        /* And now DR */
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 declaring itself DR */
151
        {
152
          if(n!=NULL)
153
          {
154
            if(neigh->priority>n->priority) n=neigh;
155
            else if(neigh->priority==n->priority)
156
                if(neigh->rid>n->rid) n=neigh;
157
          }
158
          else
159
          {
160
            n=neigh;
161
          }
162
      }
163
  }
164

    
165
  return(n);
166
}
167

    
168
int
169
can_do_adj(struct ospf_neighbor *n)
170
{
171
  struct ospf_iface *ifa;
172
  struct proto *p;
173
  int i;
174

    
175
  ifa=n->ifa;
176
  p=(struct proto *)(ifa->proto);
177
  i=0;
178

    
179
  switch(ifa->type)
180
  {
181
    case OSPF_IT_PTP:
182
    case OSPF_IT_VLINK:
183
      i=1;
184
      break;
185
    case OSPF_IT_BCAST:
186
    case OSPF_IT_NBMA:
187
      switch(ifa->state)
188
      {
189
        case OSPF_IS_DOWN:
190
          bug("%s: Iface %s in down state?", p->name, ifa->iface->name);
191
          break;
192
        case OSPF_IS_WAITING:
193
          DBG("%s: Neighbor? on iface %s\n",p->name, ifa->iface->name);
194
          break;
195
        case OSPF_IS_DROTHER:
196
          if(((n->rid==ifa->drid) || (n->rid==ifa->bdrid))
197
            && (n->state>=NEIGHBOR_2WAY)) i=1;
198
          break;
199
        case OSPF_IS_PTP:
200
        case OSPF_IS_BACKUP:
201
        case OSPF_IS_DR:
202
          if(n->state>=NEIGHBOR_2WAY) i=1;
203
          break;
204
        default:
205
          bug("%s: Iface %s in unknown state?",p->name, ifa->iface->name);
206
          break;
207
      }
208
      break;
209
    default:
210
      bug("%s: Iface %s is unknown type?",p->name, ifa->iface->name);
211
      break;
212
  }
213
  DBG("%s: Iface %s can_do_adj=%d\n",p->name, ifa->iface->name,i);
214
  return i;
215
}
216

    
217
/**
218
 * ospf_neigh_sm - ospf neighbor state machine
219
 * @n: neighor
220
 * @event: actual event
221
 *
222
 * This part implements the neighbor state machine as described in 10.3 of
223
 * RFC 2328. The only difference is that state %NEIGHBOR_ATTEMPT is not
224
 * used. We discover neighbors on nonbroadcast networks in the
225
 * same way as on broadcast networks. The only difference is in
226
 * sending hello packets. These are sent to IPs listed in
227
 * @ospf_iface->nbma_list .
228
 */
229
void
230
ospf_neigh_sm(struct ospf_neighbor *n, int event)
231
{
232
  struct proto *p=(struct proto *)(n->ifa->proto);
233
  struct proto_ospf *po=n->ifa->proto;
234

    
235
  DBG("%s: Neighbor state machine for neighbor %I, event \"%s\".\n",
236
    p->name, n->rid, ospf_inm[event]);
237

    
238
  switch(event)
239
  {
240
    case INM_START:
241
      neigh_chstate(n,NEIGHBOR_ATTEMPT);
242
      /* NBMA are used different way */
243
      break;
244
    case INM_HELLOREC:
245
      switch(n->state)
246
      {
247
        case NEIGHBOR_ATTEMPT:
248
        case NEIGHBOR_DOWN:
249
          neigh_chstate(n,NEIGHBOR_INIT);
250
        default:
251
          restart_inactim(n);
252
          break;
253
      }
254
      break;
255
    case INM_2WAYREC:
256
      if(n->state<NEIGHBOR_2WAY) neigh_chstate(n,NEIGHBOR_2WAY);
257
      if((n->state==NEIGHBOR_2WAY) && can_do_adj(n))
258
        neigh_chstate(n,NEIGHBOR_EXSTART);
259
      break;
260
    case INM_NEGDONE:
261
      if(n->state==NEIGHBOR_EXSTART)
262
      {
263
        neigh_chstate(n,NEIGHBOR_EXCHANGE);
264
        while(!EMPTY_LIST(n->ackl))
265
        {
266
          struct lsah_n *no;
267
          no=(struct lsah_n *)HEAD(n->ackl);
268
          rem_node(NODE no);
269
          mb_free(no);
270
        }
271
        s_init_list(&(n->lsrql));
272
        if(n->lsrqh) ospf_top_free(n->lsrqh);
273
        n->lsrqh=ospf_top_new(n->pool, n->ifa->proto);
274
        s_init_list(&(n->lsrtl));
275
        if(n->lsrth) ospf_top_free(n->lsrth);
276
        n->lsrth=ospf_top_new(n->pool, n->ifa->proto);
277
        s_init(&(n->dbsi), &(n->ifa->oa->lsal));
278
        s_init(&(n->lsrqi), &(n->lsrql));
279
        s_init(&(n->lsrti), &(n->lsrtl));
280
        tm_start(n->lsrr_timer,n->ifa->rxmtint);
281
        tm_start(n->ackd_timer,n->ifa->rxmtint/2);
282
      }
283
      else bug("NEGDONE and I'm not in EXSTART?");
284
      break;
285
    case INM_EXDONE:
286
        neigh_chstate(n,NEIGHBOR_LOADING);
287
      break;
288
    case INM_LOADDONE:
289
        neigh_chstate(n,NEIGHBOR_FULL);
290
      break;
291
    case INM_ADJOK:
292
        switch(n->state)
293
        {
294
          case NEIGHBOR_2WAY:
295
            /* Can In build adjacency? */
296
            if(can_do_adj(n))
297
            {
298
              neigh_chstate(n,NEIGHBOR_EXSTART);
299
            }
300
            break;
301
          default:
302
            if(n->state>=NEIGHBOR_EXSTART)
303
              if(!can_do_adj(n))
304
              {
305
                neigh_chstate(n,NEIGHBOR_2WAY);
306
              }
307
            break;
308
        }
309
      break;
310
    case INM_SEQMIS:
311
      OSPF_TRACE(D_EVENTS, "Seq mis!");
312
    case INM_BADLSREQ:
313
      OSPF_TRACE(D_EVENTS, "Bad LS req!");
314
      if(n->state>=NEIGHBOR_EXCHANGE)
315
      {
316
        neigh_chstate(n,NEIGHBOR_EXSTART);
317
      }
318
      break;
319
    case INM_KILLNBR:
320
    case INM_LLDOWN:
321
    case INM_INACTTIM:
322
      neigh_chstate(n,NEIGHBOR_DOWN);
323
      break;
324
    case INM_1WAYREC:
325
      neigh_chstate(n,NEIGHBOR_INIT);
326
      break;
327
    default:
328
      bug("%s: INM - Unknown event?",p->name);
329
      break;
330
  }
331
}
332

    
333
/**
334
 * bdr_election - (Backup) Designed Router election
335
 * @ifa: actual interface
336
 *
337
 * When the wait timer fires, it is time to elect (Backup) Designated Router.
338
 * Structure describing me is added to this list so every electing router
339
 * has the same list. Backup Designated Router is elected before Designated
340
 * Router. This process is described in 9.4 of RFC 2328.
341
 */
342
void
343
bdr_election(struct ospf_iface *ifa)
344
{
345
  struct ospf_neighbor *neigh,*ndr,*nbdr,me,*tmp;
346
  u32 myid;
347
  ip_addr ndrip, nbdrip;
348
  int doadj;
349
  struct proto *p=&ifa->proto->proto;
350

    
351
  DBG("(B)DR election.\n");
352

    
353
  myid=p->cf->global->router_id;
354

    
355
  me.state=NEIGHBOR_2WAY;
356
  me.rid=myid;
357
  me.priority=ifa->priority;
358
  me.dr=ifa->drip;
359
  me.bdr=ifa->bdrip;
360
  me.ip=ifa->iface->addr->ip;
361

    
362
  add_tail(&ifa->neigh_list, NODE &me);
363

    
364
  nbdr=electbdr(ifa->neigh_list);
365
  ndr=electdr(ifa->neigh_list);
366

    
367
  if(ndr==NULL) ndr=nbdr;
368

    
369
  if(((ifa->drid==myid) && (ndr!=&me))
370
    || ((ifa->drid!=myid) && (ndr==&me))
371
    || ((ifa->bdrid==myid) && (nbdr!=&me)) 
372
    || ((ifa->bdrid!=myid) && (nbdr==&me)))
373
  {
374
    if(ndr==NULL) ifa->drip=me.dr=ipa_from_u32(0);
375
    else ifa->drip=me.dr=ndr->ip;
376

    
377
    if(nbdr==NULL) ifa->bdrip=me.bdr=ipa_from_u32(0);
378
    else ifa->bdrip=me.bdr=nbdr->ip;
379

    
380
    nbdr=electbdr(ifa->neigh_list);
381
    ndr=electdr(ifa->neigh_list);
382
  }
383

    
384
  if(ndr==NULL) ndrip=ipa_from_u32(0);
385
  else ndrip=ndr->ip;
386

    
387
  if(nbdr==NULL) nbdrip=ipa_from_u32(0);
388
  else nbdrip=nbdr->ip;
389

    
390
  doadj=0;
391
  if((ipa_compare(ifa->drip,ndrip)!=0) || (ipa_compare(ifa->bdrip,nbdrip)!=0))
392
    doadj=1;
393

    
394
  if(ndr==NULL)
395
  {
396
    ifa->drid=0;
397
    ifa->drip=ipa_from_u32(0);
398
  }
399
  else
400
  {
401
    ifa->drid=ndr->rid;
402
    ifa->drip=ndr->ip;
403
  }
404

    
405
  if(nbdr==NULL)
406
  {
407
    ifa->bdrid=0;
408
    ifa->bdrip=ipa_from_u32(0);
409
  }
410
  else
411
  {
412
    ifa->bdrid=nbdr->rid;
413
    ifa->bdrip=nbdr->ip;
414
  }
415

    
416
  DBG("DR=%I, BDR=%I\n", ifa->drid, ifa->bdrid);
417

    
418
  if(myid==ifa->drid) iface_chstate(ifa, OSPF_IS_DR);
419
  else
420
  {
421
    if(myid==ifa->bdrid) iface_chstate(ifa, OSPF_IS_BACKUP);
422
    else iface_chstate(ifa, OSPF_IS_DROTHER);
423
  }
424

    
425
  rem_node(NODE &me);
426

    
427
  if(doadj)
428
  {
429
    WALK_LIST (neigh, ifa->neigh_list)
430
    {
431
      ospf_neigh_sm(neigh, INM_ADJOK);
432
    }
433
  }
434
}
435

    
436
struct ospf_neighbor *
437
find_neigh(struct ospf_iface *ifa, u32 rid)
438
{
439
  struct ospf_neighbor *n;
440

    
441
  WALK_LIST (n, ifa->neigh_list)
442
    if(n->rid == rid)
443
      return n;
444
  return NULL;
445
}
446

    
447

    
448
/* Find a closest neighbor which is at leas 2-Way */
449
struct ospf_neighbor *
450
find_neigh_noifa(struct proto_ospf *po, u32 rid)
451
{
452
  struct ospf_neighbor *n=NULL,*m;
453
  struct ospf_iface *ifa;
454

    
455
  WALK_LIST (ifa, po->iface_list)
456
    if((m=find_neigh(ifa, rid))!=NULL)
457
    {
458
      if(m->state>=NEIGHBOR_2WAY)
459
      {
460
        if(n==NULL) n=m;
461
        else
462
          if(m->ifa->cost < n->ifa->cost) n=m;
463
      }
464
    }
465
  return n;
466
}
467

    
468
struct ospf_area *
469
ospf_find_area(struct proto_ospf *po, u32 aid)
470
{
471
  struct ospf_area *oa;
472
  WALK_LIST(NODE oa,po->area_list)
473
    if(((struct ospf_area *)oa)->areaid==aid) return oa;
474
  return NULL;
475
}
476

    
477
/* Neighbor is inactive for a long time. Remove it. */
478
void
479
neighbor_timer_hook(timer *timer)
480
{
481
  struct ospf_neighbor *n;
482
  struct ospf_iface *ifa;
483
  struct proto *p;
484

    
485
  n=(struct ospf_neighbor *)timer->data;
486
  ifa=n->ifa;
487
  p=(struct proto *)(ifa->proto);
488
  OSPF_TRACE(D_EVENTS,"Inactivity timer fired on interface %s for neighbor %I.",
489
    ifa->iface->name, n->ip);
490
  ospf_neigh_remove(n);
491
}
492

    
493
void
494
ospf_neigh_remove(struct ospf_neighbor *n)
495
{
496
  struct ospf_iface *ifa;
497
  struct proto *p;
498

    
499
  ifa=n->ifa;
500
  p=(struct proto *)(ifa->proto);
501
  neigh_chstate(n, NEIGHBOR_DOWN);
502
  rem_node(NODE n);
503
  rfree(n->pool);
504
  OSPF_TRACE(D_EVENTS, "Deleting neigbor.");
505
}
506

    
507
void
508
ospf_sh_neigh_info(struct ospf_neighbor *n)
509
{
510
   struct ospf_iface *ifa=n->ifa;
511
   char *pos="other";
512
   char etime[6];
513
   int exp,sec,min;
514

    
515
   exp=n->inactim->expires-now;
516
   sec=exp-(exp/60);
517
   min=(exp-sec)/60;
518
   if(min>59)
519
   {
520
     bsprintf(etime,"-Inf-");
521
   }
522
   else
523
   {
524
     bsprintf(etime,"%02u:%02u", min, sec);
525
   }
526
   
527
   if(n->rid==ifa->drid) pos="dr   ";
528
   if(n->rid==ifa->bdrid) pos="bdr  ";
529
   if(n->ifa->type==OSPF_IT_PTP) pos="ptp  ";
530

    
531
   cli_msg(-1013,"%-1I\t%3u\t%s/%s\t%-5s\t%-1I\t%-10s",n->rid, n->priority,
532
     ospf_ns[n->state], pos, etime, n->ip,ifa->iface->name);
533
}