Statistics
| Branch: | Revision:

iof-bird-daemon / proto / ospf / neighbor.c @ e43ae633

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 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
}