Statistics
| Branch: | Revision:

iof-bird-daemon / proto / ospf / neighbor.c @ 23d67029

History | View | Annotate | Download (14.5 KB)

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

    
29
void neighbor_timer_hook(timer * timer);
30
void rxmt_timer_hook(timer * timer);
31
void ackd_timer_hook(timer * t);
32

    
33
struct ospf_neighbor *
34
ospf_neighbor_new(struct ospf_iface *ifa)
35
{
36
  struct proto *p = (struct proto *) (ifa->oa->po);
37
  struct pool *pool = rp_new(p->pool, "OSPF Neighbor");
38
  struct ospf_neighbor *n = mb_allocz(pool, sizeof(struct ospf_neighbor));
39

    
40
  n->pool = pool;
41
  n->ifa = ifa;
42
  add_tail(&ifa->neigh_list, NODE n);
43
  n->adj = 0;
44
  n->csn = 0;
45
  n->ldbdes = mb_allocz(pool, ifa->iface->mtu);
46
  n->state = NEIGHBOR_DOWN;
47

    
48
  n->inactim = tm_new(pool);
49
  n->inactim->data = n;
50
  n->inactim->randomize = 0;
51
  n->inactim->hook = neighbor_timer_hook;
52
  n->inactim->recurrent = 0;
53
  DBG("%s: Installing inactivity timer.\n", p->name);
54

    
55
  n->rxmt_timer = tm_new(pool);
56
  n->rxmt_timer->data = n;
57
  n->rxmt_timer->randomize = 0;
58
  n->rxmt_timer->hook = rxmt_timer_hook;
59
  n->rxmt_timer->recurrent = ifa->rxmtint;
60
  s_init_list(&(n->lsrql));
61
  n->lsrqh = ospf_top_new(pool);
62
  s_init_list(&(n->lsrtl));
63
  n->lsrth = ospf_top_new(pool);
64
  s_init(&(n->lsrqi), &(n->lsrql));
65
  s_init(&(n->lsrti), &(n->lsrtl));
66
  tm_start(n->rxmt_timer, n->ifa->rxmtint);
67
  DBG("%s: Installing rxmt timer.\n", p->name);
68

    
69
  n->ackd_timer = tm_new(pool);
70
  n->ackd_timer->data = n;
71
  n->ackd_timer->randomize = 0;
72
  n->ackd_timer->hook = ackd_timer_hook;
73
  n->ackd_timer->recurrent = ifa->rxmtint / 2;
74
  init_list(&n->ackl[ACKL_DIRECT]);
75
  init_list(&n->ackl[ACKL_DELAY]);
76
  tm_start(n->ackd_timer, n->ifa->rxmtint / 2);
77
  DBG("%s: Installing ackd timer.\n", p->name);
78

    
79
  return (n);
80
}
81

    
82
/**
83
 * neigh_chstate - handles changes related to new or lod state of neighbor
84
 * @n: OSPF neighbor
85
 * @state: new state
86
 *
87
 * Many actions have to be taken acording to a change of state of a neighbor. It
88
 * starts rxmt timers, call interface state machine etc.
89
 */
90

    
91
void
92
neigh_chstate(struct ospf_neighbor *n, u8 state)
93
{
94
  u8 oldstate;
95

    
96
  oldstate = n->state;
97

    
98
  if (oldstate != state)
99
  {
100
    struct ospf_iface *ifa = n->ifa;
101
    struct proto_ospf *po = ifa->oa->po;
102
    struct proto *p = &po->proto;
103

    
104
    n->state = state;
105

    
106
    OSPF_TRACE(D_EVENTS, "Neighbor %I changes state from \"%s\" to \"%s\".",
107
               n->ip, ospf_ns[oldstate], ospf_ns[state]);
108

    
109
    if ((state == NEIGHBOR_2WAY) && (oldstate < NEIGHBOR_2WAY))
110
      ospf_iface_sm(ifa, ISM_NEICH);
111
    if ((state < NEIGHBOR_2WAY) && (oldstate >= NEIGHBOR_2WAY))
112
      ospf_iface_sm(ifa, ISM_NEICH);
113

    
114
    if (oldstate == NEIGHBOR_FULL)        /* Decrease number of adjacencies */
115
    {
116
      ifa->fadj--;
117
      schedule_rt_lsa(ifa->oa);
118
      if (ifa->type == OSPF_IT_VLINK) schedule_rt_lsa(ifa->voa);
119
      schedule_net_lsa(ifa);
120
    }
121

    
122
    if (state == NEIGHBOR_FULL)        /* Increase number of adjacencies */
123
    {
124
      ifa->fadj++;
125
      schedule_rt_lsa(ifa->oa);
126
      if (ifa->type == OSPF_IT_VLINK) schedule_rt_lsa(ifa->voa);
127
      schedule_net_lsa(ifa);
128
    }
129
    if (state == NEIGHBOR_EXSTART)
130
    {
131
      if (n->adj == 0)                /* First time adjacency */
132
      {
133
        n->dds = random_u32();
134
      }
135
      n->dds++;
136
      n->myimms.byte = 0;
137
      n->myimms.bit.ms = 1;
138
      n->myimms.bit.m = 1;
139
      n->myimms.bit.i = 1;
140
    }
141
    if (state > NEIGHBOR_EXSTART)
142
      n->myimms.bit.i = 0;
143
  }
144
}
145

    
146
struct ospf_neighbor *
147
electbdr(list nl)
148
{
149
  struct ospf_neighbor *neigh, *n1, *n2;
150

    
151
  n1 = NULL;
152
  n2 = NULL;
153
  WALK_LIST(neigh, nl)                /* First try those decl. themselves */
154
  {
155
    if (neigh->state >= NEIGHBOR_2WAY)        /* Higher than 2WAY */
156
      if (neigh->priority > 0)        /* Eligible */
157
        if (ipa_compare(neigh->ip, neigh->dr) != 0)        /* And not decl. itself DR */
158
        {
159
          if (ipa_compare(neigh->ip, neigh->bdr) == 0)        /* Declaring BDR */
160
          {
161
            if (n1 != NULL)
162
            {
163
              if (neigh->priority > n1->priority)
164
                n1 = neigh;
165
              else if (neigh->priority == n1->priority)
166
                if (neigh->rid > n1->rid)
167
                  n1 = neigh;
168
            }
169
            else
170
            {
171
              n1 = neigh;
172
            }
173
          }
174
          else                        /* And NOT declaring BDR */
175
          {
176
            if (n2 != NULL)
177
            {
178
              if (neigh->priority > n2->priority)
179
                n2 = neigh;
180
              else if (neigh->priority == n2->priority)
181
                if (neigh->rid > n2->rid)
182
                  n2 = neigh;
183
            }
184
            else
185
            {
186
              n2 = neigh;
187
            }
188
          }
189
        }
190
  }
191
  if (n1 == NULL)
192
    n1 = n2;
193

    
194
  return (n1);
195
}
196

    
197
struct ospf_neighbor *
198
electdr(list nl)
199
{
200
  struct ospf_neighbor *neigh, *n;
201

    
202
  n = NULL;
203
  WALK_LIST(neigh, nl)                /* And now DR */
204
  {
205
    if (neigh->state >= NEIGHBOR_2WAY)        /* Higher than 2WAY */
206
      if (neigh->priority > 0)        /* Eligible */
207
        if (ipa_compare(neigh->ip, neigh->dr) == 0)        /* And declaring itself DR */
208
        {
209
          if (n != NULL)
210
          {
211
            if (neigh->priority > n->priority)
212
              n = neigh;
213
            else if (neigh->priority == n->priority)
214
              if (neigh->rid > n->rid)
215
                n = neigh;
216
          }
217
          else
218
          {
219
            n = neigh;
220
          }
221
        }
222
  }
223

    
224
  return (n);
225
}
226

    
227
static int
228
can_do_adj(struct ospf_neighbor *n)
229
{
230
  struct ospf_iface *ifa;
231
  struct proto *p;
232
  int i;
233

    
234
  ifa = n->ifa;
235
  p = (struct proto *) (ifa->oa->po);
236
  i = 0;
237

    
238
  switch (ifa->type)
239
  {
240
  case OSPF_IT_PTP:
241
  case OSPF_IT_VLINK:
242
    i = 1;
243
    break;
244
  case OSPF_IT_BCAST:
245
  case OSPF_IT_NBMA:
246
    switch (ifa->state)
247
    {
248
    case OSPF_IS_DOWN:
249
      bug("%s: Iface %s in down state?", p->name, ifa->iface->name);
250
      break;
251
    case OSPF_IS_WAITING:
252
      DBG("%s: Neighbor? on iface %s\n", p->name, ifa->iface->name);
253
      break;
254
    case OSPF_IS_DROTHER:
255
      if (((n->rid == ifa->drid) || (n->rid == ifa->bdrid))
256
          && (n->state >= NEIGHBOR_2WAY))
257
        i = 1;
258
      break;
259
    case OSPF_IS_PTP:
260
    case OSPF_IS_BACKUP:
261
    case OSPF_IS_DR:
262
      if (n->state >= NEIGHBOR_2WAY)
263
        i = 1;
264
      break;
265
    default:
266
      bug("%s: Iface %s in unknown state?", p->name, ifa->iface->name);
267
      break;
268
    }
269
    break;
270
  default:
271
    bug("%s: Iface %s is unknown type?", p->name, ifa->iface->name);
272
    break;
273
  }
274
  DBG("%s: Iface %s can_do_adj=%d\n", p->name, ifa->iface->name, i);
275
  return i;
276
}
277

    
278
/**
279
 * ospf_neigh_sm - ospf neighbor state machine
280
 * @n: neighor
281
 * @event: actual event
282
 *
283
 * This part implements the neighbor state machine as described in 10.3 of
284
 * RFC 2328. The only difference is that state %NEIGHBOR_ATTEMPT is not
285
 * used. We discover neighbors on nonbroadcast networks in the
286
 * same way as on broadcast networks. The only difference is in
287
 * sending hello packets. These are sent to IPs listed in
288
 * @ospf_iface->nbma_list .
289
 */
290
void
291
ospf_neigh_sm(struct ospf_neighbor *n, int event)
292
{
293
  struct proto_ospf *po = n->ifa->oa->po;
294
  struct proto *p = &po->proto;
295

    
296
  DBG("Neighbor state machine for neighbor %I, event '%s'\n", n->ip,
297
             ospf_inm[event]);
298

    
299
  switch (event)
300
  {
301
  case INM_START:
302
    neigh_chstate(n, NEIGHBOR_ATTEMPT);
303
    /* NBMA are used different way */
304
    break;
305
  case INM_HELLOREC:
306
    switch (n->state)
307
    {
308
    case NEIGHBOR_ATTEMPT:
309
    case NEIGHBOR_DOWN:
310
      neigh_chstate(n, NEIGHBOR_INIT);
311
    default:
312
      tm_start(n->inactim, n->ifa->dead);        /* Restart inactivity timer */
313
      break;
314
    }
315
    break;
316
  case INM_2WAYREC:
317
    if (n->state < NEIGHBOR_2WAY)
318
      neigh_chstate(n, NEIGHBOR_2WAY);
319
    if ((n->state == NEIGHBOR_2WAY) && can_do_adj(n))
320
      neigh_chstate(n, NEIGHBOR_EXSTART);
321
    break;
322
  case INM_NEGDONE:
323
    if (n->state == NEIGHBOR_EXSTART)
324
    {
325
      neigh_chstate(n, NEIGHBOR_EXCHANGE);
326
      s_init(&(n->dbsi), &po->lsal);
327
      while (!EMPTY_LIST(n->ackl[ACKL_DELAY]))
328
      {
329
        struct lsah_n *no;
330
        no = (struct lsah_n *) HEAD(n->ackl[ACKL_DELAY]);
331
        rem_node(NODE no);
332
        mb_free(no);
333
      }
334
    }
335
    else
336
      bug("NEGDONE and I'm not in EXSTART?");
337
    break;
338
  case INM_EXDONE:
339
    neigh_chstate(n, NEIGHBOR_LOADING);
340
    break;
341
  case INM_LOADDONE:
342
    neigh_chstate(n, NEIGHBOR_FULL);
343
    break;
344
  case INM_ADJOK:
345
    switch (n->state)
346
    {
347
    case NEIGHBOR_2WAY:
348
      /* Can In build adjacency? */
349
      if (can_do_adj(n))
350
      {
351
        neigh_chstate(n, NEIGHBOR_EXSTART);
352
      }
353
      break;
354
    default:
355
      if (n->state >= NEIGHBOR_EXSTART)
356
        if (!can_do_adj(n))
357
        {
358
          neigh_chstate(n, NEIGHBOR_2WAY);
359
        }
360
      break;
361
    }
362
    break;
363
  case INM_SEQMIS:
364
  case INM_BADLSREQ:
365
    if (n->state >= NEIGHBOR_EXCHANGE)
366
    {
367
      neigh_chstate(n, NEIGHBOR_EXSTART);
368
    }
369
    break;
370
  case INM_KILLNBR:
371
  case INM_LLDOWN:
372
  case INM_INACTTIM:
373
    neigh_chstate(n, NEIGHBOR_DOWN);
374
    break;
375
  case INM_1WAYREC:
376
    neigh_chstate(n, NEIGHBOR_INIT);
377
    break;
378
  default:
379
    bug("%s: INM - Unknown event?", p->name);
380
    break;
381
  }
382
}
383

    
384
/**
385
 * bdr_election - (Backup) Designed Router election
386
 * @ifa: actual interface
387
 *
388
 * When the wait timer fires, it is time to elect (Backup) Designated Router.
389
 * Structure describing me is added to this list so every electing router
390
 * has the same list. Backup Designated Router is elected before Designated
391
 * Router. This process is described in 9.4 of RFC 2328.
392
 */
393
void
394
bdr_election(struct ospf_iface *ifa)
395
{
396
  struct ospf_neighbor *neigh, *ndr, *nbdr, me;
397
  u32 myid;
398
  ip_addr ndrip, nbdrip;
399
  int doadj;
400
  struct proto *p = &ifa->oa->po->proto;
401

    
402
  DBG("(B)DR election.\n");
403

    
404
  myid = p->cf->global->router_id;
405

    
406
  me.state = NEIGHBOR_2WAY;
407
  me.rid = myid;
408
  me.priority = ifa->priority;
409
  me.dr = ifa->drip;
410
  me.bdr = ifa->bdrip;
411
  me.ip = ifa->iface->addr->ip;
412

    
413
  add_tail(&ifa->neigh_list, NODE & me);
414

    
415
  nbdr = electbdr(ifa->neigh_list);
416
  ndr = electdr(ifa->neigh_list);
417

    
418
  if (ndr == NULL)
419
    ndr = nbdr;
420

    
421
  if (((ifa->drid == myid) && (ndr != &me))
422
      || ((ifa->drid != myid) && (ndr == &me))
423
      || ((ifa->bdrid == myid) && (nbdr != &me))
424
      || ((ifa->bdrid != myid) && (nbdr == &me)))
425
  {
426
    if (ndr == NULL)
427
      ifa->drip = me.dr = IPA_NONE;
428
    else
429
      ifa->drip = me.dr = ndr->ip;
430

    
431
    if (nbdr == NULL)
432
      ifa->bdrip = me.bdr = IPA_NONE;
433
    else
434
      ifa->bdrip = me.bdr = nbdr->ip;
435

    
436
    nbdr = electbdr(ifa->neigh_list);
437
    ndr = electdr(ifa->neigh_list);
438
  }
439

    
440
  if (ndr == NULL)
441
    ndrip = IPA_NONE;
442
  else
443
    ndrip = ndr->ip;
444

    
445
  if (nbdr == NULL)
446
    nbdrip = IPA_NONE;
447
  else
448
    nbdrip = nbdr->ip;
449

    
450
  doadj = 0;
451
  if ((ipa_compare(ifa->drip, ndrip) != 0)
452
      || (ipa_compare(ifa->bdrip, nbdrip) != 0))
453
    doadj = 1;
454

    
455
  if (ndr == NULL)
456
  {
457
    ifa->drid = 0;
458
    ifa->drip = IPA_NONE;
459
  }
460
  else
461
  {
462
    ifa->drid = ndr->rid;
463
    ifa->drip = ndr->ip;
464
  }
465

    
466
  if (nbdr == NULL)
467
  {
468
    ifa->bdrid = 0;
469
    ifa->bdrip = IPA_NONE;
470
  }
471
  else
472
  {
473
    ifa->bdrid = nbdr->rid;
474
    ifa->bdrip = nbdr->ip;
475
  }
476

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

    
479
  if (myid == ifa->drid)
480
    ospf_iface_chstate(ifa, OSPF_IS_DR);
481
  else
482
  {
483
    if (myid == ifa->bdrid)
484
      ospf_iface_chstate(ifa, OSPF_IS_BACKUP);
485
    else
486
      ospf_iface_chstate(ifa, OSPF_IS_DROTHER);
487
  }
488

    
489
  rem_node(NODE & me);
490

    
491
  if (doadj)
492
  {
493
    WALK_LIST(neigh, ifa->neigh_list)
494
    {
495
      ospf_neigh_sm(neigh, INM_ADJOK);
496
    }
497
  }
498
}
499

    
500
struct ospf_neighbor *
501
find_neigh(struct ospf_iface *ifa, u32 rid)
502
{
503
  struct ospf_neighbor *n;
504

    
505
  WALK_LIST(n, ifa->neigh_list) if (n->rid == rid)
506
    return n;
507
  return NULL;
508
}
509

    
510

    
511
/* Find a closest neighbor which is at least 2-Way */
512
struct ospf_neighbor *
513
find_neigh_noifa(struct proto_ospf *po, u32 rid)
514
{
515
  struct ospf_neighbor *n = NULL, *m;
516
  struct ospf_iface *ifa;
517

    
518
  WALK_LIST(ifa, po->iface_list) if ((m = find_neigh(ifa, rid)) != NULL)
519
  {
520
    if (m->state >= NEIGHBOR_2WAY)
521
    {
522
      if (n == NULL)
523
        n = m;
524
      else if (m->ifa->cost < n->ifa->cost)
525
        n = m;
526
    }
527
  }
528
  return n;
529
}
530

    
531
struct ospf_area *
532
ospf_find_area(struct proto_ospf *po, u32 aid)
533
{
534
  struct ospf_area *oa;
535
  WALK_LIST(oa, po->area_list)
536
    if (((struct ospf_area *) oa)->areaid == aid)
537
    return oa;
538
  return NULL;
539
}
540

    
541
/* Neighbor is inactive for a long time. Remove it. */
542
void
543
neighbor_timer_hook(timer * timer)
544
{
545
  struct ospf_neighbor *n = (struct ospf_neighbor *) timer->data;
546
  struct ospf_iface *ifa = n->ifa;
547
  struct proto *p = &ifa->oa->po->proto;
548

    
549
  OSPF_TRACE(D_EVENTS,
550
             "Inactivity timer fired on interface %s for neighbor %I.",
551
             ifa->iface->name, n->ip);
552
  ospf_neigh_remove(n);
553
}
554

    
555
void
556
ospf_neigh_remove(struct ospf_neighbor *n)
557
{
558
  struct ospf_iface *ifa = n->ifa;
559
  struct proto *p = &ifa->oa->po->proto;
560

    
561
  neigh_chstate(n, NEIGHBOR_DOWN);
562
  rem_node(NODE n);
563
  rfree(n->pool);
564
  OSPF_TRACE(D_EVENTS, "Deleting neigbor.");
565
}
566

    
567
void
568
ospf_sh_neigh_info(struct ospf_neighbor *n)
569
{
570
  struct ospf_iface *ifa = n->ifa;
571
  char *pos = "other";
572
  char etime[6];
573
  int exp, sec, min;
574

    
575
  exp = n->inactim->expires - now;
576
  sec = exp % 60;
577
  min = exp / 60;
578
  if (min > 59)
579
  {
580
    bsprintf(etime, "-Inf-");
581
  }
582
  else
583
  {
584
    bsprintf(etime, "%02u:%02u", min, sec);
585
  }
586

    
587
  if (n->rid == ifa->drid)
588
    pos = "dr   ";
589
  if (n->rid == ifa->bdrid)
590
    pos = "bdr  ";
591
  if ((n->ifa->type == OSPF_IT_PTP) || (n->ifa->type == OSPF_IT_VLINK))
592
    pos = "ptp  ";
593

    
594
  cli_msg(-1013, "%-1I\t%3u\t%s/%s\t%-5s\t%-1I\t%-10s", n->rid, n->priority,
595
          ospf_ns[n->state], pos, etime, n->ip,
596
          (ifa->type == OSPF_IT_VLINK ? "vlink" : ifa->iface->name));
597
}
598

    
599
void
600
rxmt_timer_hook(timer * timer)
601
{
602
  struct ospf_neighbor *n = (struct ospf_neighbor *) timer->data;
603
  struct proto *p = &n->ifa->oa->po->proto;
604
  struct top_hash_entry *en;
605

    
606
  DBG("%s: RXMT timer fired on interface %s for neigh: %I.\n",
607
      p->name, n->ifa->iface->name, n->ip);
608

    
609
  if(n->state < NEIGHBOR_EXSTART) return;
610

    
611
  if (n->state == NEIGHBOR_EXSTART)
612
  {
613
    ospf_dbdes_send(n);
614
    return;
615
  }
616

    
617
  if ((n->state == NEIGHBOR_EXCHANGE) && n->myimms.bit.ms)        /* I'm master */
618
    ospf_dbdes_send(n);
619

    
620

    
621
  if (n->state < NEIGHBOR_FULL)        
622
    ospf_lsreq_send(n);        /* EXCHANGE or LOADING */
623
  else
624
  {
625
    if (!EMPTY_SLIST(n->lsrtl))        /* FULL */
626
    {
627
      list uplist;
628
      slab *upslab;
629
      struct l_lsr_head *llsh;
630

    
631
      init_list(&uplist);
632
      upslab = sl_new(n->pool, sizeof(struct l_lsr_head));
633

    
634
      WALK_SLIST(en, n->lsrtl)
635
      {
636
        if ((SNODE en)->next == (SNODE en))
637
          bug("RTList is cycled");
638
        llsh = sl_alloc(upslab);
639
        llsh->lsh.id = en->lsa.id;
640
        llsh->lsh.rt = en->lsa.rt;
641
        llsh->lsh.type = en->lsa.type;
642
        DBG("Working on ID: %I, RT: %I, Type: %u\n",
643
            en->lsa.id, en->lsa.rt, en->lsa.type);
644
        add_tail(&uplist, NODE llsh);
645
      }
646
      ospf_lsupd_send_list(n, &uplist);
647
      rfree(upslab);
648
    }
649
  }
650
}
651

    
652
void
653
ackd_timer_hook(timer * t)
654
{
655
  struct ospf_neighbor *n = t->data;
656
  ospf_lsack_send(n, ACKL_DELAY);
657
}