Revision a7a7372a proto/ospf/ospf.c

View differences:

proto/ospf/ospf.c
11 11
/**
12 12
 * DOC: Open Shortest Path First (OSPF)
13 13
 * 
14
 * The OSPF protocol is quite complicated and its complex implemenation is
15
 * split to many files. In |ospf.c|, you will find mainly the interface
16
 * for communication with the core (e.g., reconfiguration hooks, shutdown
17
 * and initialisation and so on). In |packet.c|, you will find various
18
 * functions for sending and receiving generic OSPF packets. There are
19
 * also routines for authentication and checksumming. File |iface.c| contains
20
 * the interface state machine and functions for allocation and deallocation of OSPF's
21
 * interface data structures. Source |neighbor.c| includes the neighbor state
22
 * machine and functions for election of Designated Router and Backup
23
 * Designated router. In |hello.c|, there are routines for sending
24
 * and receiving of hello packets as well as functions for maintaining
25
 * wait times and the inactivity timer. Files |lsreq.c|, |lsack.c|, |dbdes.c|
26
 * contain functions for sending and receiving of link-state requests,
27
 * link-state acknowledgements and database descriptions respectively.
28
 * In |lsupd.c|, there are functions for sending and receiving
29
 * of link-state updates and also the flooding algorithm. Source |topology.c| is
30
 * a place where routines for searching LSAs in the link-state database,
31
 * adding and deleting them reside, there also are functions for originating
32
 * of various types of LSAs (router LSA, net LSA, external LSA). File |rt.c|
33
 * contains routines for calculating the routing table. |lsalib.c| is a set
34
 * of various functions for working with the LSAs (endianity conversions,
35
 * calculation of checksum etc.).
14
 * The OSPF protocol is quite complicated and its complex implemenation is split
15
 * to many files. In |ospf.c|, you will find mainly the interface for
16
 * communication with the core (e.g., reconfiguration hooks, shutdown and
17
 * initialisation and so on). File |iface.c| contains the interface state
18
 * machine and functions for allocation and deallocation of OSPF's interface
19
 * data structures. Source |neighbor.c| includes the neighbor state machine and
20
 * functions for election of Designated Router and Backup Designated router. In
21
 * |packet.c|, you will find various functions for sending and receiving generic
22
 * OSPF packets. There are also routines for authentication and checksumming.
23
 * In |hello.c|, there are routines for sending and receiving of hello packets
24
 * as well as functions for maintaining wait times and the inactivity timer.
25
 * Files |lsreq.c|, |lsack.c|, |dbdes.c| contain functions for sending and
26
 * receiving of link-state requests, link-state acknowledgements and database
27
 * descriptions respectively.  In |lsupd.c|, there are functions for sending and
28
 * receiving of link-state updates and also the flooding algorithm. Source
29
 * |topology.c| is a place where routines for searching LSAs in the link-state
30
 * database, adding and deleting them reside, there also are functions for
31
 * originating of various types of LSAs (router LSA, net LSA, external LSA).
32
 * File |rt.c| contains routines for calculating the routing table. |lsalib.c|
33
 * is a set of various functions for working with the LSAs (endianity
34
 * conversions, calculation of checksum etc.).
36 35
 *
37
 * One instance of the protocol is able to hold LSA databases for
38
 * multiple OSPF areas, to exchange routing information between
39
 * multiple neighbors and to calculate the routing tables. The core
40
 * structure is &ospf_proto to which multiple &ospf_area and
41
 * &ospf_iface structures are connected. &ospf_area is also connected to
42
 * &top_hash_graph which is a dynamic hashing structure that
43
 * describes the link-state database. It allows fast search, addition
44
 * and deletion. Each LSA is kept in two pieces: header and body. Both of them are
36
 * One instance of the protocol is able to hold LSA databases for multiple OSPF
37
 * areas, to exchange routing information between multiple neighbors and to
38
 * calculate the routing tables. The core structure is &ospf_proto to which
39
 * multiple &ospf_area and &ospf_iface structures are connected. &ospf_proto is
40
 * also connected to &top_hash_graph which is a dynamic hashing structure that
41
 * describes the link-state database. It allows fast search, addition and
42
 * deletion. Each LSA is kept in two pieces: header and body. Both of them are
45 43
 * kept in the endianity of the CPU.
46 44
 *
47
 * In OSPFv2 specification, it is implied that there is one IP prefix
48
 * for each physical network/interface (unless it is an ptp link). But
49
 * in modern systems, there might be more independent IP prefixes
50
 * associated with an interface.  To handle this situation, we have
51
 * one &ospf_iface for each active IP prefix (instead for each active
52
 * iface); This behaves like virtual interface for the purpose of OSPF.
53
 * If we receive packet, we associate it with a proper virtual interface
54
 * mainly according to its source address.
45
 * In OSPFv2 specification, it is implied that there is one IP prefix for each
46
 * physical network/interface (unless it is an ptp link). But in modern systems,
47
 * there might be more independent IP prefixes associated with an interface.  To
48
 * handle this situation, we have one &ospf_iface for each active IP prefix
49
 * (instead for each active iface); This behaves like virtual interface for the
50
 * purpose of OSPF.  If we receive packet, we associate it with a proper virtual
51
 * interface mainly according to its source address.
55 52
 *
56
 * OSPF keeps one socket per &ospf_iface. This allows us (compared to
57
 * one socket approach) to evade problems with a limit of multicast
58
 * groups per socket and with sending multicast packets to appropriate
59
 * interface in a portable way. The socket is associated with
60
 * underlying physical iface and should not receive packets received
61
 * on other ifaces (unfortunately, this is not true on
62
 * BSD). Generally, one packet can be received by more sockets (for
63
 * example, if there are more &ospf_iface on one physical iface),
64
 * therefore we explicitly filter received packets according to
65
 * src/dst IP address and received iface.
53
 * OSPF keeps one socket per &ospf_iface. This allows us (compared to one socket
54
 * approach) to evade problems with a limit of multicast groups per socket and
55
 * with sending multicast packets to appropriate interface in a portable way.
56
 * The socket is associated with underlying physical iface and should not
57
 * receive packets received on other ifaces (unfortunately, this is not true on
58
 * BSD). Generally, one packet can be received by more sockets (for example, if
59
 * there are more &ospf_iface on one physical iface), therefore we explicitly
60
 * filter received packets according to src/dst IP address and received iface.
66 61
 *
67
 * Vlinks are implemented using particularly degenerate form of
68
 * &ospf_iface, which has several exceptions: it does not have its
69
 * iface or socket (it copies these from 'parent' &ospf_iface) and it
70
 * is present in iface list even when down (it is not freed in
71
 * ospf_iface_down()).
62
 * Vlinks are implemented using particularly degenerate form of &ospf_iface,
63
 * which has several exceptions: it does not have its iface or socket (it copies
64
 * these from 'parent' &ospf_iface) and it is present in iface list even when
65
 * down (it is not freed in ospf_iface_down()).
72 66
 *
73 67
 * The heart beat of ospf is ospf_disp(). It is called at regular intervals
74
 * (&ospf_proto->tick). It is responsible for aging and flushing of LSAs in
75
 * the database, for routing table calculaction and it call area_disp() of every
76
 * ospf_area.
68
 * (&ospf_proto->tick). It is responsible for aging and flushing of LSAs in the
69
 * database, updating topology information in LSAs and for routing table
70
 * calculation.
77 71
 * 
78
 * The function area_disp() is
79
 * responsible for late originating of router LSA and network LSA
80
 * and for cleanup before routing table calculation process in
81
 * the area.
82
 * To every &ospf_iface, we connect one or more
83
 * &ospf_neighbor's -- a structure containing many timers and queues
84
 * for building adjacency and for exchange of routing messages.
72
 * To every &ospf_iface, we connect one or more &ospf_neighbor's -- a structure
73
 * containing many timers and queues for building adjacency and for exchange of
74
 * routing messages.
85 75
 *
86
 * BIRD's OSPF implementation respects RFC2328 in every detail, but
87
 * some of internal algorithms do differ. The RFC recommends making a snapshot
88
 * of the link-state database when a new adjacency is forming and sending
89
 * the database description packets based on the information in this 
90
 * snapshot. The database can be quite large in some networks, so
91
 * rather we walk through a &slist structure which allows us to
92
 * continue even if the actual LSA we were working with is deleted. New
93
 * LSAs are added at the tail of this &slist.
76
 * BIRD's OSPF implementation respects RFC2328 in every detail, but some of
77
 * internal algorithms do differ. The RFC recommends making a snapshot of the
78
 * link-state database when a new adjacency is forming and sending the database
79
 * description packets based on the information in this snapshot. The database
80
 * can be quite large in some networks, so rather we walk through a &slist
81
 * structure which allows us to continue even if the actual LSA we were working
82
 * with is deleted. New LSAs are added at the tail of this &slist.
94 83
 *
95
 * We also don't keep a separate OSPF routing table, because the core
96
 * helps us by being able to recognize when a route is updated
97
 * to an identical one and it suppresses the update automatically.
98
 * Due to this, we can flush all the routes we've recalculated and
99
 * also those we've deleted to the core's routing table and the
100
 * core will take care of the rest. This simplifies the process
84
 * We also do not keep a separate OSPF routing table, because the core helps us
85
 * by being able to recognize when a route is updated to an identical one and it
86
 * suppresses the update automatically. Due to this, we can flush all the routes
87
 * we have recalculated and also those we have deleted to the core's routing
88
 * table and the core will take care of the rest. This simplifies the process
101 89
 * and conserves memory.
102 90
 */
103 91

  
......
145 133
}
146 134

  
147 135
static void
148
ospf_area_add(struct ospf_proto *p, struct ospf_area_config *ac, int reconf)
136
ospf_area_add(struct ospf_proto *p, struct ospf_area_config *ac)
149 137
{
150 138
  struct ospf_area *oa;
151 139

  
......
169 157
    oa->options = ac->type;
170 158
  else
171 159
    oa->options = ac->type | OPT_V6 | (p->stub_router ? 0 : OPT_R);
160

  
161
  ospf_notify_rt_lsa(oa);
172 162
}
173 163

  
174 164
static void
......
252 242
  init_list(&(p->area_list));
253 243
  fib_init(&p->rtf, P->pool, sizeof(ort), 0, ospf_rt_initort);
254 244
  p->areano = 0;
255
  p->gr = ospf_top_new(P->pool);
245
  p->gr = ospf_top_new(p, P->pool);
256 246
  s_init_list(&(p->lsal));
257 247

  
258 248
  WALK_LIST(ac, c->area_list)
259
    ospf_area_add(p, ac, 0);
249
    ospf_area_add(p, ac);
260 250

  
261 251
  if (c->abr)
262 252
    ospf_open_vlink_sk(p);
......
382 372

  
383 373

  
384 374
void
385
schedule_rtcalc(struct ospf_proto *p)
375
ospf_schedule_rtcalc(struct ospf_proto *p)
386 376
{
387 377
  if (p->calcrt)
388 378
    return;
......
418 408
  /* Originate or flush local topology LSAs */
419 409
  ospf_update_topology(p);
420 410

  
421
  /* Age LSA DB */
411
  /* Process LSA DB */
422 412
  ospf_update_lsadb(p);
423 413

  
424 414
  /* Calculate routing table */
......
429 419

  
430 420
/**
431 421
 * ospf_import_control - accept or reject new route from nest's routing table
432
 * @p: current instance of protocol
422
 * @P: OSPF protocol instance
433 423
 * @new: the new route
434 424
 * @attrs: list of attributes
435 425
 * @pool: pool for allocation of attributes
......
475 465

  
476 466
/**
477 467
 * ospf_shutdown - Finish of OSPF instance
478
 * @p: current instance of protocol
468
 * @P: OSPF protocol instance
479 469
 *
480 470
 * RFC does not define any action that should be taken before router
481 471
 * shutdown. To make my neighbors react as fast as possible, I send
......
619 609

  
620 610
/**
621 611
 * ospf_reconfigure - reconfiguration hook
622
 * @p: current instance of protocol (with old configuration)
612
 * @P: current instance of protocol (with old configuration)
623 613
 * @c: new configuration requested by user
624 614
 *
625 615
 * This hook tries to be a little bit intelligent. Instance of OSPF
......
669 659
    if (oa)
670 660
      ospf_area_reconfigure(oa, nac);
671 661
    else
672
      ospf_area_add(p, nac, 1);
662
      ospf_area_add(p, nac);
673 663
  }
674 664

  
675 665
  /* Add and update interfaces */
......
697 687
    if (oa->marked)
698 688
      ospf_area_remove(oa);
699 689

  
700
  schedule_rtcalc(p);
690
  ospf_schedule_rtcalc(p);
701 691
  
702 692
  return 1;
703 693
}
......
1009 999
	/* In OSPFv2, we try to find network-LSA to get prefix/pxlen */
1010 1000
	struct top_hash_entry *net_he = ospf_hash_find_net2(p->gr, he->domain, rtl.id);
1011 1001

  
1012
	if (net_he)
1002
	if (net_he && (net_he->lsa.age < LSA_MAXAGE))
1013 1003
	{
1014 1004
	  struct ospf_lsa_header *net_lsa = &(net_he->lsa);
1015 1005
	  struct ospf_lsa_net *net_ln = net_he->lsa_body;
......
1367 1357
ospf_sh_lsadb(struct lsadb_show_data *ld)
1368 1358
{
1369 1359
  struct ospf_proto *p = (struct ospf_proto *) proto_get_named(ld->name, &proto_ospf);
1370
  int num = p->gr->hash_entries;
1371
  unsigned int i, j;
1360
  uint num = p->gr->hash_entries;
1361
  uint i, j;
1372 1362
  int last_dscope = -1;
1373 1363
  u32 last_domain = 0;
1374 1364
  u16 type_mask = ospf_is_v2(p) ?  0x00ff : 0xffff;	/* see lsa_etype() */

Also available in: Unified diff