embedaddon/bird/doc/prog-5.html - view

File: [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird / doc / prog-5.html
Revision 1.1.1.2 (vendor branch): download - view: text, annotated - select for diffs - revision graph
Wed Mar 17 19:50:23 2021 UTC (3 years, 4 months ago) by misho
Branches: bird, MAIN
CVS tags: v1_6_8p3, HEAD

bird 1.6.8

1: <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN"> 2: <HTML> 3: <HEAD> 4: <META NAME="GENERATOR" CONTENT="LinuxDoc-Tools 1.0.9"> 5: <TITLE>BIRD Programmer's Documentation: Protocols</TITLE> 6: <LINK HREF="prog-6.html" REL=next> 7: <LINK HREF="prog-4.html" REL=previous> 8: <LINK HREF="prog.html#toc5" REL=contents> 9: </HEAD> 10: <BODY> 11: <A HREF="prog-6.html">Next</A> 12: <A HREF="prog-4.html">Previous</A> 13: <A HREF="prog.html#toc5">Contents</A> 14: <HR> 15: <H2><A NAME="s5">5.</A> <A HREF="prog.html#toc5">Protocols</A></H2> 16: 17: <H2><A NAME="ss5.1">5.1</A> <A HREF="prog.html#toc5.1">The Babel protocol</A> 18: </H2> 19: 20:  21: Babel (RFC6126) is a loop-avoiding distance-vector routing protocol that is 22: robust and efficient both in ordinary wired networks and in wireless mesh 23: networks. 24: The Babel protocol keeps state for each neighbour in a babel_neighbor 25: struct, tracking received Hello and I Heard You (IHU) messages. A 26: babel_interface struct keeps hello and update times for each interface, and 27: a separate hello seqno is maintained for each interface. 28: For each prefix, Babel keeps track of both the possible routes (with next hop 29: and router IDs), as well as the feasibility distance for each prefix and 30: router id. The prefix itself is tracked in a babel_entry struct, while the 31: possible routes for the prefix are tracked as babel_route entries and the 32: feasibility distance is maintained through babel_source structures. 33: The main route selection is done in babel_select_route(). This is called when 34: an entry is updated by receiving updates from the network or when modified by 35: internal timers. It performs feasibility checks on the available routes for 36: the prefix and selects the one with the lowest metric to be announced to the 37: core. 38:  39: <HR><H3>Function</H3> 40: void 41: babel_announce_rte 42: (struct babel_proto * p, struct babel_entry * e) -- announce selected route to the core 43:  44: <H3>Arguments</H3> 45:  46: <DL> 47: <DT>struct babel_proto * p<DD>Babel protocol instance 48: <DT>struct babel_entry * e<DD>Babel route entry to announce 49: </DL> 50: <H3>Description</H3> 51: This function announces a Babel entry to the core if it has a selected 52: incoming path, and retracts it otherwise. If the selected entry has infinite 53: metric, the route is announced as unreachable. 54: 55: 56: <HR><H3>Function</H3> 57: void 58: babel_select_route 59: (struct babel_entry * e) -- select best route for given route entry 60:  61: <H3>Arguments</H3> 62:  63: <DL> 64: <DT>struct babel_entry * e<DD>Babel entry to select the best route for 65: </DL> 66: <H3>Description</H3> 67: Select the best feasible route for a given prefix among the routes received 68: from peers, and propagate it to the nest. This just selects the feasible 69: route with the lowest metric. 70: If no feasible route is available for a prefix that previously had a route 71: selected, a seqno request is sent to try to get a valid route. In the 72: meantime, the route is marked as infeasible in the nest (to blackhole packets 73: going to it, as per the RFC). 74: If no feasible route is available, and no previous route is selected, the 75: route is removed from the nest entirely. 76: 77: 78: <HR><H3>Function</H3> 79: void 80: babel_send_update 81: (struct babel_iface * ifa, bird_clock_t changed) -- send route table updates 82:  83: <H3>Arguments</H3> 84:  85: <DL> 86: <DT>struct babel_iface * ifa<DD>Interface to transmit on 87: <DT>bird_clock_t changed<DD>Only send entries changed since this time 88: </DL> 89: <H3>Description</H3> 90: This function produces update TLVs for all entries changed since the time 91: indicated by the changed parameter and queues them for transmission on the 92: selected interface. During the process, the feasibility distance for each 93: transmitted entry is updated. 94: 95: 96: <HR><H3>Function</H3> 97: void 98: babel_handle_update 99: (union babel_msg * m, struct babel_iface * ifa) -- handle incoming route updates 100:  101: <H3>Arguments</H3> 102:  103: <DL> 104: <DT>union babel_msg * m<DD>Incoming update TLV 105: <DT>struct babel_iface * ifa<DD>Interface the update was received on 106: </DL> 107: <H3>Description</H3> 108: This function is called as a handler for update TLVs and handles the updating 109: and maintenance of route entries in Babel's internal routing cache. The 110: handling follows the actions described in the Babel RFC, and at the end of 111: each update handling, babel_select_route() is called on the affected entry to 112: optionally update the selected routes and propagate them to the core. 113: 114: 115: <HR><H3>Function</H3> 116: void 117: babel_iface_timer 118: (timer * t) -- Babel interface timer handler 119:  120: <H3>Arguments</H3> 121:  122: <DL> 123: <DT>timer * t<DD>Timer 124: </DL> 125: <H3>Description</H3> 126: This function is called by the per-interface timer and triggers sending of 127: periodic Hello's and both triggered and periodic updates. Periodic Hello's 128: and updates are simply handled by setting the next_{hello,regular} variables 129: on the interface, and triggering an update (and resetting the variable) 130: whenever 'now' exceeds that value. 131: For triggered updates, babel_trigger_iface_update() will set the 132: want_triggered field on the interface to a timestamp value. If this is set 133: (and the next_triggered time has passed; this is a rate limiting mechanism), 134: babel_send_update() will be called with this timestamp as the second 135: parameter. This causes updates to be send consisting of only the routes that 136: have changed since the time saved in want_triggered. 137: Mostly when an update is triggered, the route being modified will be set to 138: the value of 'now' at the time of the trigger; the >= comparison for 139: selecting which routes to send in the update will make sure this is included. 140: 141: 142: <HR><H3>Function</H3> 143: void 144: babel_timer 145: (timer * t) -- global timer hook 146:  147: <H3>Arguments</H3> 148:  149: <DL> 150: <DT>timer * t<DD>Timer 151: </DL> 152: <H3>Description</H3> 153: This function is called by the global protocol instance timer and handles 154: expiration of routes and neighbours as well as pruning of the seqno request 155: cache. 156: 157: 158: <HR><H3>Function</H3> 159: uint 160: babel_write_queue 161: (struct babel_iface * ifa, list * queue) -- Write a TLV queue to a transmission buffer 162:  163: <H3>Arguments</H3> 164:  165: <DL> 166: <DT>struct babel_iface * ifa<DD>Interface holding the transmission buffer 167: <DT>list * queue<DD>TLV queue to write (containing internal-format TLVs) 168: </DL> 169: <H3>Description</H3> 170: This function writes a packet to the interface transmission buffer with as 171: many TLVs from the queue as will fit in the buffer. It returns the number of 172: bytes written (NOT counting the packet header). The function is called by 173: babel_send_queue() and babel_send_unicast() to construct packets for 174: transmission, and uses per-TLV helper functions to convert the 175: internal-format TLVs to their wire representations. 176: The TLVs in the queue are freed after they are written to the buffer. 177: 178: 179: <HR><H3>Function</H3> 180: void 181: babel_send_unicast 182: (union babel_msg * msg, struct babel_iface * ifa, ip_addr dest) -- send a single TLV via unicast to a destination 183:  184: <H3>Arguments</H3> 185:  186: <DL> 187: <DT>union babel_msg * msg<DD>TLV to send 188: <DT>struct babel_iface * ifa<DD>Interface to send via 189: <DT>ip_addr dest<DD>Destination of the TLV 190: </DL> 191: <H3>Description</H3> 192: This function is used to send a single TLV via unicast to a designated 193: receiver. This is used for replying to certain incoming requests, and for 194: sending unicast requests to refresh routes before they expire. 195: 196: 197: <HR><H3>Function</H3> 198: void 199: babel_enqueue 200: (union babel_msg * msg, struct babel_iface * ifa) -- enqueue a TLV for transmission on an interface 201:  202: <H3>Arguments</H3> 203:  204: <DL> 205: <DT>union babel_msg * msg<DD>TLV to enqueue (in internal TLV format) 206: <DT>struct babel_iface * ifa<DD>Interface to enqueue to 207: </DL> 208: <H3>Description</H3> 209: This function is called to enqueue a TLV for subsequent transmission on an 210: interface. The transmission event is triggered whenever a TLV is enqueued; 211: this ensures that TLVs will be transmitted in a timely manner, but that TLVs 212: which are enqueued in rapid succession can be transmitted together in one 213: packet. 214: 215: 216: <HR><H3>Function</H3> 217: void 218: babel_process_packet 219: (struct babel_pkt_header * pkt, int len, ip_addr saddr, struct babel_iface * ifa) -- process incoming data packet 220:  221: <H3>Arguments</H3> 222:  223: <DL> 224: <DT>struct babel_pkt_header * pkt<DD>Pointer to the packet data 225: <DT>int len<DD>Length of received packet 226: <DT>ip_addr saddr<DD>Address of packet sender 227: <DT>struct babel_iface * ifa<DD>Interface packet was received on. 228: </DL> 229: <H3>Description</H3> 230: This function is the main processing hook of incoming Babel packets. It 231: checks that the packet header is well-formed, then processes the TLVs 232: contained in the packet. This is done in two passes: First all TLVs are 233: parsed into the internal TLV format. If a TLV parser fails, processing of the 234: rest of the packet is aborted. 235: After the parsing step, the TLV handlers are called for each parsed TLV in 236: order. 237: 238: <H2><A NAME="ss5.2">5.2</A> <A HREF="prog.html#toc5.2">Bidirectional Forwarding Detection</A> 239: </H2> 240: 241:  242: The BFD protocol is implemented in three files: <CODE>bfd.c</CODE> containing the 243: protocol logic and the protocol glue with BIRD core, <CODE>packets.c</CODE> handling BFD 244: packet processing, RX, TX and protocol sockets. <CODE>io.c</CODE> then contains generic 245: code for the event loop, threads and event sources (sockets, microsecond 246: timers). This generic code will be merged to the main BIRD I/O code in the 247: future. 248: The BFD implementation uses a separate thread with an internal event loop for 249: handling the protocol logic, which requires high-res and low-latency timing, 250: so it is not affected by the rest of BIRD, which has several low-granularity 251: hooks in the main loop, uses second-based timers and cannot offer good 252: latency. The core of BFD protocol (the code related to BFD sessions, 253: interfaces and packets) runs in the BFD thread, while the rest (the code 254: related to BFD requests, BFD neighbors and the protocol glue) runs in the 255: main thread. 256: BFD sessions are represented by structure bfd_session that contains a state 257: related to the session and two timers (TX timer for periodic packets and hold 258: timer for session timeout). These sessions are allocated from session_slab 259: and are accessible by two hash tables, session_hash_id (by session ID) and 260: session_hash_ip (by IP addresses of neighbors). Slab and both hashes are in 261: the main protocol structure bfd_proto. The protocol logic related to BFD 262: sessions is implemented in internal functions bfd_session_*(), which are 263: expected to be called from the context of BFD thread, and external functions 264: bfd_add_session(), bfd_remove_session() and bfd_reconfigure_session(), which 265: form an interface to the BFD core for the rest and are expected to be called 266: from the context of main thread. 267: Each BFD session has an associated BFD interface, represented by structure 268: bfd_iface. A BFD interface contains a socket used for TX (the one for RX is 269: shared in bfd_proto), an interface configuration and reference counter. 270: Compared to interface structures of other protocols, these structures are not 271: created and removed based on interface notification events, but according to 272: the needs of BFD sessions. When a new session is created, it requests a 273: proper BFD interface by function bfd_get_iface(), which either finds an 274: existing one in iface_list (from bfd_proto) or allocates a new one. When a 275: session is removed, an associated iface is discharged by bfd_free_iface(). 276: BFD requests are the external API for the other protocols. When a protocol 277: wants a BFD session, it calls bfd_request_session(), which creates a 278: structure bfd_request containing approprite information and an notify hook. 279: This structure is a resource associated with the caller's resource pool. When 280: a BFD protocol is available, a BFD request is submitted to the protocol, an 281: appropriate BFD session is found or created and the request is attached to 282: the session. When a session changes state, all attached requests (and related 283: protocols) are notified. Note that BFD requests do not depend on BFD protocol 284: running. When the BFD protocol is stopped or removed (or not available from 285: beginning), related BFD requests are stored in bfd_wait_list, where waits 286: for a new protocol. 287: BFD neighbors are just a way to statically configure BFD sessions without 288: requests from other protocol. Structures bfd_neighbor are part of BFD 289: configuration (like static routes in the static protocol). BFD neighbors are 290: handled by BFD protocol like it is a BFD client -- when a BFD neighbor is 291: ready, the protocol just creates a BFD request like any other protocol. 292: The protocol uses a new generic event loop (structure birdloop) from <CODE>io.c</CODE>, 293: which supports sockets, timers and events like the main loop. Timers 294: (structure timer2) are new microsecond based timers, while sockets and 295: events are the same. A birdloop is associated with a thread (field thread) 296: in which event hooks are executed. Most functions for setting event sources 297: (like sk_start() or tm2_start()) must be called from the context of that 298: thread. Birdloop allows to temporarily acquire the context of that thread for 299: the main thread by calling birdloop_enter() and then birdloop_leave(), which 300: also ensures mutual exclusion with all event hooks. Note that resources 301: associated with a birdloop (like timers) should be attached to the 302: independent resource pool, detached from the main resource tree. 303: There are two kinds of interaction between the BFD core (running in the BFD 304: thread) and the rest of BFD (running in the main thread). The first kind are 305: configuration calls from main thread to the BFD thread (like bfd_add_session()). 306: These calls are synchronous and use birdloop_enter() mechanism for mutual 307: exclusion. The second kind is a notification about session changes from the 308: BFD thread to the main thread. This is done in an asynchronous way, sesions 309: with pending notifications are linked (in the BFD thread) to notify_list in 310: bfd_proto, and then bfd_notify_hook() in the main thread is activated using 311: bfd_notify_kick() and a pipe. The hook then processes scheduled sessions and 312: calls hooks from associated BFD requests. This notify_list (and state fields 313: in structure bfd_session) is protected by a spinlock in bfd_proto and 314: functions bfd_lock_sessions() / bfd_unlock_sessions(). 315: There are few data races (accessing p->p.debug from TRACE() from the BFD 316: thread and accessing some some private fields of bfd_session from 317: bfd_show_sessions() from the main thread, but these are harmless (i hope). 318: TODO: document functions and access restrictions for fields in BFD structures. 319: Supported standards: 320: - RFC 5880 - main BFD standard 321: - RFC 5881 - BFD for IP links 322: - RFC 5882 - generic application of BFD 323: - RFC 5883 - BFD for multihop paths 324:  325:  326: <H2><A NAME="ss5.3">5.3</A> <A HREF="prog.html#toc5.3">Border Gateway Protocol</A> 327: </H2> 328: 329:  330: The BGP protocol is implemented in three parts: <CODE>bgp.c</CODE> which takes care of the 331: connection and most of the interface with BIRD core, <CODE>packets.c</CODE> handling 332: both incoming and outgoing BGP packets and <CODE>attrs.c</CODE> containing functions for 333: manipulation with BGP attribute lists. 334: As opposed to the other existing routing daemons, BIRD has a sophisticated core 335: architecture which is able to keep all the information needed by BGP in the 336: primary routing table, therefore no complex data structures like a central 337: BGP table are needed. This increases memory footprint of a BGP router with 338: many connections, but not too much and, which is more important, it makes 339: BGP much easier to implement. 340: Each instance of BGP (corresponding to a single BGP peer) is described by a bgp_proto 341: structure to which are attached individual connections represented by bgp_connection 342: (usually, there exists only one connection, but during BGP session setup, there 343: can be more of them). The connections are handled according to the BGP state machine 344: defined in the RFC with all the timers and all the parameters configurable. 345: In incoming direction, we listen on the connection's socket and each time we receive 346: some input, we pass it to bgp_rx(). It decodes packet headers and the markers and 347: passes complete packets to bgp_rx_packet() which distributes the packet according 348: to its type. 349: In outgoing direction, we gather all the routing updates and sort them to buckets 350: (bgp_bucket) according to their attributes (we keep a hash table for fast comparison 351: of rta's and a fib which helps us to find if we already have another route for 352: the same destination queued for sending, so that we can replace it with the new one 353: immediately instead of sending both updates). There also exists a special bucket holding 354: all the route withdrawals which cannot be queued anywhere else as they don't have any 355: attributes. If we have any packet to send (due to either new routes or the connection 356: tracking code wanting to send a Open, Keepalive or Notification message), we call 357: bgp_schedule_packet() which sets the corresponding bit in a packet_to_send 358: bit field in bgp_conn and as soon as the transmit socket buffer becomes empty, 359: we call bgp_fire_tx(). It inspects state of all the packet type bits and calls 360: the corresponding bgp_create_xx() functions, eventually rescheduling the same packet 361: type if we have more data of the same type to send. 362: The processing of attributes consists of two functions: bgp_decode_attrs() for checking 363: of the attribute blocks and translating them to the language of BIRD's extended attributes 364: and bgp_encode_attrs() which does the converse. Both functions are built around a 365: bgp_attr_table array describing all important characteristics of all known attributes. 366: Unknown transitive attributes are attached to the route as EAF_TYPE_OPAQUE byte streams. 367: BGP protocol implements graceful restart in both restarting (local restart) 368: and receiving (neighbor restart) roles. The first is handled mostly by the 369: graceful restart code in the nest, BGP protocol just handles capabilities, 370: sets gr_wait and locks graceful restart until end-of-RIB mark is received. 371: The second is implemented by internal restart of the BGP state to BS_IDLE 372: and protocol state to PS_START, but keeping the protocol up from the core 373: point of view and therefore maintaining received routes. Routing table 374: refresh cycle (rt_refresh_begin(), rt_refresh_end()) is used for removing 375: stale routes after reestablishment of BGP session during graceful restart. 376:  377: <HR><H3>Function</H3> 378: int 379: bgp_open 380: (struct bgp_proto * p) -- open a BGP instance 381:  382: <H3>Arguments</H3> 383:  384: <DL> 385: <DT>struct bgp_proto * p<DD>BGP instance 386: </DL> 387: <H3>Description</H3> 388: This function allocates and configures shared BGP resources. 389: Should be called as the last step during initialization 390: (when lock is acquired and neighbor is ready). 391: When error, state changed to PS_DOWN, -1 is returned and caller 392: should return immediately. 393: 394: 395: <HR><H3>Function</H3> 396: void 397: bgp_close 398: (struct bgp_proto * p, int apply_md5) -- close a BGP instance 399:  400: <H3>Arguments</H3> 401:  402: <DL> 403: <DT>struct bgp_proto * p<DD>BGP instance 404: <DT>int apply_md5<DD>0 to disable unsetting MD5 auth 405: </DL> 406: <H3>Description</H3> 407: This function frees and deconfigures shared BGP resources. 408: apply_md5 is set to 0 when bgp_close is called as a cleanup 409: from failed bgp_open(). 410: 411: 412: <HR><H3>Function</H3> 413: void 414: bgp_start_timer 415: (timer * t, int value) -- start a BGP timer 416:  417: <H3>Arguments</H3> 418:  419: <DL> 420: <DT>timer * t<DD>timer 421: <DT>int value<DD>time to fire (0 to disable the timer) 422: </DL> 423: <H3>Description</H3> 424: This functions calls tm_start() on t with time value and the 425: amount of randomization suggested by the BGP standard. Please use 426: it for all BGP timers. 427: 428: 429: <HR><H3>Function</H3> 430: void 431: bgp_close_conn 432: (struct bgp_conn * conn) -- close a BGP connection 433:  434: <H3>Arguments</H3> 435:  436: <DL> 437: <DT>struct bgp_conn * conn<DD>connection to close 438: </DL> 439: <H3>Description</H3> 440: This function takes a connection described by the bgp_conn structure, 441: closes its socket and frees all resources associated with it. 442: 443: 444: <HR><H3>Function</H3> 445: void 446: bgp_update_startup_delay 447: (struct bgp_proto * p) -- update a startup delay 448:  449: <H3>Arguments</H3> 450:  451: <DL> 452: <DT>struct bgp_proto * p<DD>BGP instance 453: </DL> 454: <H3>Description</H3> 455: This function updates a startup delay that is used to postpone next BGP connect. 456: It also handles disable_after_error and might stop BGP instance when error 457: happened and disable_after_error is on. 458: It should be called when BGP protocol error happened. 459: 460: 461: <HR><H3>Function</H3> 462: void 463: bgp_handle_graceful_restart 464: (struct bgp_proto * p) -- handle detected BGP graceful restart 465:  466: <H3>Arguments</H3> 467:  468: <DL> 469: <DT>struct bgp_proto * p<DD>BGP instance 470: </DL> 471: <H3>Description</H3> 472: This function is called when a BGP graceful restart of the neighbor is 473: detected (when the TCP connection fails or when a new TCP connection 474: appears). The function activates processing of the restart - starts routing 475: table refresh cycle and activates BGP restart timer. The protocol state goes 476: back to PS_START, but changing BGP state back to BS_IDLE is left for the 477: caller. 478: 479: 480: <HR><H3>Function</H3> 481: void 482: bgp_graceful_restart_done 483: (struct bgp_proto * p) -- finish active BGP graceful restart 484:  485: <H3>Arguments</H3> 486:  487: <DL> 488: <DT>struct bgp_proto * p<DD>BGP instance 489: </DL> 490: <H3>Description</H3> 491: This function is called when the active BGP graceful restart of the neighbor 492: should be finished - either successfully (the neighbor sends all paths and 493: reports end-of-RIB on the new session) or unsuccessfully (the neighbor does 494: not support BGP graceful restart on the new session). The function ends 495: routing table refresh cycle and stops BGP restart timer. 496: 497: 498: <HR><H3>Function</H3> 499: void 500: bgp_graceful_restart_timeout 501: (timer * t) -- timeout of graceful restart 'restart timer' 502:  503: <H3>Arguments</H3> 504:  505: <DL> 506: <DT>timer * t<DD>timer 507: </DL> 508: <H3>Description</H3> 509: This function is a timeout hook for gr_timer, implementing BGP restart time 510: limit for reestablisment of the BGP session after the graceful restart. When 511: fired, we just proceed with the usual protocol restart. 512: 513: 514: <HR><H3>Function</H3> 515: void 516: bgp_refresh_begin 517: (struct bgp_proto * p) -- start incoming enhanced route refresh sequence 518:  519: <H3>Arguments</H3> 520:  521: <DL> 522: <DT>struct bgp_proto * p<DD>BGP instance 523: </DL> 524: <H3>Description</H3> 525: This function is called when an incoming enhanced route refresh sequence is 526: started by the neighbor, demarcated by the BoRR packet. The function updates 527: the load state and starts the routing table refresh cycle. Note that graceful 528: restart also uses routing table refresh cycle, but RFC 7313 and load states 529: ensure that these two sequences do not overlap. 530: 531: 532: <HR><H3>Function</H3> 533: void 534: bgp_refresh_end 535: (struct bgp_proto * p) -- finish incoming enhanced route refresh sequence 536:  537: <H3>Arguments</H3> 538:  539: <DL> 540: <DT>struct bgp_proto * p<DD>BGP instance 541: </DL> 542: <H3>Description</H3> 543: This function is called when an incoming enhanced route refresh sequence is 544: finished by the neighbor, demarcated by the EoRR packet. The function updates 545: the load state and ends the routing table refresh cycle. Routes not received 546: during the sequence are removed by the nest. 547: 548: 549: <HR><H3>Function</H3> 550: void 551: bgp_connect 552: (struct bgp_proto * p) -- initiate an outgoing connection 553:  554: <H3>Arguments</H3> 555:  556: <DL> 557: <DT>struct bgp_proto * p<DD>BGP instance 558: </DL> 559: <H3>Description</H3> 560: The bgp_connect() function creates a new bgp_conn and initiates 561: a TCP connection to the peer. The rest of connection setup is governed 562: by the BGP state machine as described in the standard. 563: 564: 565: <HR><H3>Function</H3> 566: struct bgp_proto * 567: bgp_find_proto 568: (sock * sk) -- find existing proto for incoming connection 569:  570: <H3>Arguments</H3> 571:  572: <DL> 573: <DT>sock * sk<DD>TCP socket 574: </DL> 575: 576: 577: <HR><H3>Function</H3> 578: int 579: bgp_incoming_connection 580: (sock * sk, uint dummy UNUSED) -- handle an incoming connection 581:  582: <H3>Arguments</H3> 583:  584: <DL> 585: <DT>sock * sk<DD>TCP socket 586: <DT>uint dummy UNUSED<DD>-- undescribed -- 587: </DL> 588: <H3>Description</H3> 589: This function serves as a socket hook for accepting of new BGP 590: connections. It searches a BGP instance corresponding to the peer 591: which has connected and if such an instance exists, it creates a 592: bgp_conn structure, attaches it to the instance and either sends 593: an Open message or (if there already is an active connection) it 594: closes the new connection by sending a Notification message. 595: 596: 597: <HR><H3>Function</H3> 598: void 599: bgp_error 600: (struct bgp_conn * c, unsigned code, unsigned subcode, byte * data, int len) -- report a protocol error 601:  602: <H3>Arguments</H3> 603:  604: <DL> 605: <DT>struct bgp_conn * c<DD>connection 606: <DT>unsigned code<DD>error code (according to the RFC) 607: <DT>unsigned subcode<DD>error sub-code 608: <DT>byte * data<DD>data to be passed in the Notification message 609: <DT>int len<DD>length of the data 610: </DL> 611: <H3>Description</H3> 612: bgp_error() sends a notification packet to tell the other side that a protocol 613: error has occurred (including the data considered erroneous if possible) and 614: closes the connection. 615: 616: 617: <HR><H3>Function</H3> 618: void 619: bgp_store_error 620: (struct bgp_proto * p, struct bgp_conn * c, u8 class, u32 code) -- store last error for status report 621:  622: <H3>Arguments</H3> 623:  624: <DL> 625: <DT>struct bgp_proto * p<DD>BGP instance 626: <DT>struct bgp_conn * c<DD>connection 627: <DT>u8 class<DD>error class (BE_xxx constants) 628: <DT>u32 code<DD>error code (class specific) 629: </DL> 630: <H3>Description</H3> 631: bgp_store_error() decides whether given error is interesting enough 632: and store that error to last_error variables of p 633: 634: 635: <HR><H3>Function</H3> 636: int 637: bgp_fire_tx 638: (struct bgp_conn * conn) -- transmit packets 639:  640: <H3>Arguments</H3> 641:  642: <DL> 643: <DT>struct bgp_conn * conn<DD>connection 644: </DL> 645: <H3>Description</H3> 646: Whenever the transmit buffers of the underlying TCP connection 647: are free and we have any packets queued for sending, the socket functions 648: call bgp_fire_tx() which takes care of selecting the highest priority packet 649: queued (Notification > Keepalive > Open > Update), assembling its header 650: and body and sending it to the connection. 651: 652: 653: <HR><H3>Function</H3> 654: void 655: bgp_schedule_packet 656: (struct bgp_conn * conn, int type) -- schedule a packet for transmission 657:  658: <H3>Arguments</H3> 659:  660: <DL> 661: <DT>struct bgp_conn * conn<DD>connection 662: <DT>int type<DD>packet type 663: </DL> 664: <H3>Description</H3> 665: Schedule a packet of type type to be sent as soon as possible. 666: 667: 668: <HR><H3>Function</H3> 669: const char * 670: bgp_error_dsc 671: (unsigned code, unsigned subcode) -- return BGP error description 672:  673: <H3>Arguments</H3> 674:  675: <DL> 676: <DT>unsigned code<DD>BGP error code 677: <DT>unsigned subcode<DD>BGP error subcode 678: </DL> 679: <H3>Description</H3> 680: bgp_error_dsc() returns error description for BGP errors 681: which might be static string or given temporary buffer. 682: 683: 684: <HR><H3>Function</H3> 685: void 686: bgp_rx_packet 687: (struct bgp_conn * conn, byte * pkt, unsigned len) -- handle a received packet 688:  689: <H3>Arguments</H3> 690:  691: <DL> 692: <DT>struct bgp_conn * conn<DD>BGP connection 693: <DT>byte * pkt<DD>start of the packet 694: <DT>unsigned len<DD>packet size 695: </DL> 696: <H3>Description</H3> 697: bgp_rx_packet() takes a newly received packet and calls the corresponding 698: packet handler according to the packet type. 699: 700: 701: <HR><H3>Function</H3> 702: int 703: bgp_rx 704: (sock * sk, uint size) -- handle received data 705:  706: <H3>Arguments</H3> 707:  708: <DL> 709: <DT>sock * sk<DD>socket 710: <DT>uint size<DD>amount of data received 711: </DL> 712: <H3>Description</H3> 713: bgp_rx() is called by the socket layer whenever new data arrive from 714: the underlying TCP connection. It assembles the data fragments to packets, 715: checks their headers and framing and passes complete packets to 716: bgp_rx_packet(). 717: 718: 719: <HR><H3>Function</H3> 720: uint 721: bgp_encode_attrs 722: (struct bgp_proto * p, byte * w, ea_list * attrs, int remains) -- encode BGP attributes 723:  724: <H3>Arguments</H3> 725:  726: <DL> 727: <DT>struct bgp_proto * p<DD>BGP instance (or NULL) 728: <DT>byte * w<DD>buffer 729: <DT>ea_list * attrs<DD>a list of extended attributes 730: <DT>int remains<DD>remaining space in the buffer 731: </DL> 732: <H3>Description</H3> 733: The bgp_encode_attrs() function takes a list of extended attributes 734: and converts it to its BGP representation (a part of an Update message). 735: <H3>Result</H3> 736: Length of the attribute block generated or -1 if not enough space. 737: 738: 739: <HR><H3>Function</H3> 740: struct rta * 741: bgp_decode_attrs 742: (struct bgp_conn * conn, byte * attr, uint len, struct linpool * pool, int mandatory) -- check and decode BGP attributes 743:  744: <H3>Arguments</H3> 745:  746: <DL> 747: <DT>struct bgp_conn * conn<DD>connection 748: <DT>byte * attr<DD>start of attribute block 749: <DT>uint len<DD>length of attribute block 750: <DT>struct linpool * pool<DD>linear pool to make all the allocations in 751: <DT>int mandatory<DD>1 iff presence of mandatory attributes has to be checked 752: </DL> 753: <H3>Description</H3> 754: This function takes a BGP attribute block (a part of an Update message), checks 755: its consistency and converts it to a list of BIRD route attributes represented 756: by a rta. 757: 758: <H2><A NAME="ss5.4">5.4</A> <A HREF="prog.html#toc5.4">Multi-Threaded Routing Toolkit (MRT) protocol</A> 759: </H2> 760: 761:  762: The MRT protocol is implemented in just one file: <CODE>mrt.c</CODE>. It contains of 763: several parts: Generic functions for preparing MRT messages in a buffer, 764: functions for MRT table dump (called from timer or CLI), functions for MRT 765: BGP4MP dump (called from BGP), and the usual protocol glue. For the MRT table 766: dump, the key structure is struct mrt_table_dump_state, which contains all 767: necessary data and created when the MRT dump cycle is started for the 768: duration of the MRT dump. The MBGP4MP dump is currently not bound to MRT 769: protocol instance and uses the config->mrtdump_file fd. 770: The protocol is simple, just periodically scans routing table and export it 771: to a file. It does not use the regular update mechanism, but a direct access 772: in order to handle iteration through multiple routing tables. The table dump 773: needs to dump all peers first and then use indexes to address the peers, we 774: use a hash table (peer_hash) to find peer index based on BGP protocol key 775: attributes. 776: One thing worth documenting is the locking. During processing, the currently 777: processed table (table field in the state structure) is locked and also the 778: explicitly named table is locked (table_ptr field in the state structure) if 779: specified. Between dumps no table is locked. Also the current config is 780: locked (by config_add_obstacle()) during table dumps as some data (strings, 781: filters) are shared from the config and the running table dump may be 782: interrupted by reconfiguration. 783: Supported standards: 784: - RFC 6396 - MRT format standard 785: - RFC 8050 - ADD_PATH extension 786:  787:  788: <H2><A NAME="ss5.5">5.5</A> <A HREF="prog.html#toc5.5">Open Shortest Path First (OSPF)</A> 789: </H2> 790: 791:  792: The OSPF protocol is quite complicated and its complex implemenation is split 793: to many files. In <CODE>ospf.c</CODE>, you will find mainly the interface for 794: communication with the core (e.g., reconfiguration hooks, shutdown and 795: initialisation and so on). File <CODE>iface.c</CODE> contains the interface state 796: machine and functions for allocation and deallocation of OSPF's interface 797: data structures. Source <CODE>neighbor.c</CODE> includes the neighbor state machine and 798: functions for election of Designated Router and Backup Designated router. In 799: <CODE>packet.c</CODE>, you will find various functions for sending and receiving generic 800: OSPF packets. There are also routines for authentication and checksumming. 801: In <CODE>hello.c</CODE>, there are routines for sending and receiving of hello packets 802: as well as functions for maintaining wait times and the inactivity timer. 803: Files <CODE>lsreq.c</CODE>, <CODE>lsack.c</CODE>, <CODE>dbdes.c</CODE> contain functions for sending and 804: receiving of link-state requests, link-state acknowledgements and database 805: descriptions respectively. In <CODE>lsupd.c</CODE>, there are functions for sending and 806: receiving of link-state updates and also the flooding algorithm. Source 807: <CODE>topology.c</CODE> is a place where routines for searching LSAs in the link-state 808: database, adding and deleting them reside, there also are functions for 809: originating of various types of LSAs (router LSA, net LSA, external LSA). 810: File <CODE>rt.c</CODE> contains routines for calculating the routing table. <CODE>lsalib.c</CODE> 811: is a set of various functions for working with the LSAs (endianity 812: conversions, calculation of checksum etc.). 813: One instance of the protocol is able to hold LSA databases for multiple OSPF 814: areas, to exchange routing information between multiple neighbors and to 815: calculate the routing tables. The core structure is ospf_proto to which 816: multiple ospf_area and ospf_iface structures are connected. ospf_proto is 817: also connected to top_hash_graph which is a dynamic hashing structure that 818: describes the link-state database. It allows fast search, addition and 819: deletion. Each LSA is kept in two pieces: header and body. Both of them are 820: kept in the endianity of the CPU. 821: In OSPFv2 specification, it is implied that there is one IP prefix for each 822: physical network/interface (unless it is an ptp link). But in modern systems, 823: there might be more independent IP prefixes associated with an interface. To 824: handle this situation, we have one ospf_iface for each active IP prefix 825: (instead for each active iface); This behaves like virtual interface for the 826: purpose of OSPF. If we receive packet, we associate it with a proper virtual 827: interface mainly according to its source address. 828: OSPF keeps one socket per ospf_iface. This allows us (compared to one socket 829: approach) to evade problems with a limit of multicast groups per socket and 830: with sending multicast packets to appropriate interface in a portable way. 831: The socket is associated with underlying physical iface and should not 832: receive packets received on other ifaces (unfortunately, this is not true on 833: BSD). Generally, one packet can be received by more sockets (for example, if 834: there are more ospf_iface on one physical iface), therefore we explicitly 835: filter received packets according to src/dst IP address and received iface. 836: Vlinks are implemented using particularly degenerate form of ospf_iface, 837: which has several exceptions: it does not have its iface or socket (it copies 838: these from 'parent' ospf_iface) and it is present in iface list even when 839: down (it is not freed in ospf_iface_down()). 840: The heart beat of ospf is ospf_disp(). It is called at regular intervals 841: (ospf_proto->tick). It is responsible for aging and flushing of LSAs in the 842: database, updating topology information in LSAs and for routing table 843: calculation. 844: To every ospf_iface, we connect one or more ospf_neighbor's -- a structure 845: containing many timers and queues for building adjacency and for exchange of 846: routing messages. 847: BIRD's OSPF implementation respects RFC2328 in every detail, but some of 848: internal algorithms do differ. The RFC recommends making a snapshot of the 849: link-state database when a new adjacency is forming and sending the database 850: description packets based on the information in this snapshot. The database 851: can be quite large in some networks, so rather we walk through a slist 852: structure which allows us to continue even if the actual LSA we were working 853: with is deleted. New LSAs are added at the tail of this slist. 854: We also do not keep a separate OSPF routing table, because the core helps us 855: by being able to recognize when a route is updated to an identical one and it 856: suppresses the update automatically. Due to this, we can flush all the routes 857: we have recalculated and also those we have deleted to the core's routing 858: table and the core will take care of the rest. This simplifies the process 859: and conserves memory. 860: Supported standards: 861: - RFC 2328 - main OSPFv2 standard 862: - RFC 5340 - main OSPFv3 standard 863: - RFC 3101 - OSPFv2 NSSA areas 864: - RFC 6549 - OSPFv2 multi-instance extensions 865: - RFC 6987 - OSPF stub router advertisement 866:  867: <HR><H3>Function</H3> 868: void 869: ospf_disp 870: (timer * timer) -- invokes routing table calculation, aging and also area_disp() 871:  872: <H3>Arguments</H3> 873:  874: <DL> 875: <DT>timer * timer<DD>timer usually called every ospf_proto->tick second, timer->data 876: point to ospf_proto 877: </DL> 878: 879: 880: <HR><H3>Function</H3> 881: int 882: ospf_import_control 883: (struct proto * P, rte ** new, ea_list ** attrs, struct linpool * pool) -- accept or reject new route from nest's routing table 884:  885: <H3>Arguments</H3> 886:  887: <DL> 888: <DT>struct proto * P<DD>OSPF protocol instance 889: <DT>rte ** new<DD>the new route 890: <DT>ea_list ** attrs<DD>list of attributes 891: <DT>struct linpool * pool<DD>pool for allocation of attributes 892: </DL> 893: <H3>Description</H3> 894: Its quite simple. It does not accept our own routes and leaves the decision on 895: import to the filters. 896: 897: 898: <HR><H3>Function</H3> 899: int 900: ospf_shutdown 901: (struct proto * P) -- Finish of OSPF instance 902:  903: <H3>Arguments</H3> 904:  905: <DL> 906: <DT>struct proto * P<DD>OSPF protocol instance 907: </DL> 908: <H3>Description</H3> 909: RFC does not define any action that should be taken before router 910: shutdown. To make my neighbors react as fast as possible, I send 911: them hello packet with empty neighbor list. They should start 912: their neighbor state machine with event NEIGHBOR_1WAY. 913: 914: 915: <HR><H3>Function</H3> 916: int 917: ospf_reconfigure 918: (struct proto * P, struct proto_config * c) -- reconfiguration hook 919:  920: <H3>Arguments</H3> 921:  922: <DL> 923: <DT>struct proto * P<DD>current instance of protocol (with old configuration) 924: <DT>struct proto_config * c<DD>new configuration requested by user 925: </DL> 926: <H3>Description</H3> 927: This hook tries to be a little bit intelligent. Instance of OSPF 928: will survive change of many constants like hello interval, 929: password change, addition or deletion of some neighbor on 930: nonbroadcast network, cost of interface, etc. 931: 932: 933: <HR><H3>Function</H3> 934: struct top_hash_entry * 935: ospf_install_lsa 936: (struct ospf_proto * p, struct ospf_lsa_header * lsa, u32 type, u32 domain, void * body) -- install new LSA into database 937:  938: <H3>Arguments</H3> 939:  940: <DL> 941: <DT>struct ospf_proto * p<DD>OSPF protocol instance 942: <DT>struct ospf_lsa_header * lsa<DD>LSA header 943: <DT>u32 type<DD>type of LSA 944: <DT>u32 domain<DD>domain of LSA 945: <DT>void * body<DD>pointer to LSA body 946: </DL> 947: <H3>Description</H3> 948: This function ensures installing new LSA received in LS update into LSA 949: database. Old instance is replaced. Several actions are taken to detect if 950: new routing table calculation is necessary. This is described in 13.2 of RFC 951: 2328. This function is for received LSA only, locally originated LSAs are 952: installed by ospf_originate_lsa(). 953: The LSA body in body is expected to be mb_allocated by the caller and its 954: ownership is transferred to the LSA entry structure. 955: 956: 957: <HR><H3>Function</H3> 958: void 959: ospf_advance_lsa 960: (struct ospf_proto * p, struct top_hash_entry * en, struct ospf_lsa_header * lsa, u32 type, u32 domain, void * body) -- handle received unexpected self-originated LSA 961:  962: <H3>Arguments</H3> 963:  964: <DL> 965: <DT>struct ospf_proto * p<DD>OSPF protocol instance 966: <DT>struct top_hash_entry * en<DD>current LSA entry or NULL 967: <DT>struct ospf_lsa_header * lsa<DD>new LSA header 968: <DT>u32 type<DD>type of LSA 969: <DT>u32 domain<DD>domain of LSA 970: <DT>void * body<DD>pointer to LSA body 971: </DL> 972: <H3>Description</H3> 973: This function handles received unexpected self-originated LSA (lsa, body) 974: by either advancing sequence number of the local LSA instance (en) and 975: propagating it, or installing the received LSA and immediately flushing it 976: (if there is no local LSA; i.e., en is NULL or MaxAge). 977: The LSA body in body is expected to be mb_allocated by the caller and its 978: ownership is transferred to the LSA entry structure or it is freed. 979: 980: 981: <HR><H3>Function</H3> 982: struct top_hash_entry * 983: ospf_originate_lsa 984: (struct ospf_proto * p, struct ospf_new_lsa * lsa) -- originate new LSA 985:  986: <H3>Arguments</H3> 987:  988: <DL> 989: <DT>struct ospf_proto * p<DD>OSPF protocol instance 990: <DT>struct ospf_new_lsa * lsa<DD>New LSA specification 991: </DL> 992: <H3>Description</H3> 993: This function prepares a new LSA, installs it into the LSA database and 994: floods it. If the new LSA cannot be originated now (because the old instance 995: was originated within MinLSInterval, or because the LSA seqnum is currently 996: wrapping), the origination is instead scheduled for later. If the new LSA is 997: equivalent to the current LSA, the origination is skipped. In all cases, the 998: corresponding LSA entry is returned. The new LSA is based on the LSA 999: specification (lsa) and the LSA body from lsab buffer of p, which is 1000: emptied after the call. The opposite of this function is ospf_flush_lsa(). 1001: 1002: 1003: <HR><H3>Function</H3> 1004: void 1005: ospf_flush_lsa 1006: (struct ospf_proto * p, struct top_hash_entry * en) -- flush LSA from OSPF domain 1007:  1008: <H3>Arguments</H3> 1009:  1010: <DL> 1011: <DT>struct ospf_proto * p<DD>OSPF protocol instance 1012: <DT>struct top_hash_entry * en<DD>LSA entry to flush 1013: </DL> 1014: <H3>Description</H3> 1015: This function flushes en from the OSPF domain by setting its age to 1016: LSA_MAXAGE and flooding it. That also triggers subsequent events in LSA 1017: lifecycle leading to removal of the LSA from the LSA database (e.g. the LSA 1018: content is freed when flushing is acknowledged by neighbors). The function 1019: does nothing if the LSA is already being flushed. LSA entries are not 1020: immediately removed when being flushed, the caller may assume that en still 1021: exists after the call. The function is the opposite of ospf_originate_lsa() 1022: and is supposed to do the right thing even in cases of postponed 1023: origination. 1024: 1025: 1026: <HR><H3>Function</H3> 1027: void 1028: ospf_update_lsadb 1029: (struct ospf_proto * p) -- update LSA database 1030:  1031: <H3>Arguments</H3> 1032:  1033: <DL> 1034: <DT>struct ospf_proto * p<DD>OSPF protocol instance 1035: </DL> 1036: <H3>Description</H3> 1037: This function is periodicaly invoked from ospf_disp(). It does some periodic 1038: or postponed processing related to LSA entries. It originates postponed LSAs 1039: scheduled by ospf_originate_lsa(), It continues in flushing processes started 1040: by ospf_flush_lsa(). It also periodically refreshs locally originated LSAs -- 1041: when the current instance is older LSREFRESHTIME, a new instance is originated. 1042: Finally, it also ages stored LSAs and flushes ones that reached LSA_MAXAGE. 1043: The RFC 2328 says that a router should periodically check checksums of all 1044: stored LSAs to detect hardware problems. This is not implemented. 1045: 1046: 1047: <HR><H3>Function</H3> 1048: void 1049: ospf_originate_ext_lsa 1050: (struct ospf_proto * p, struct ospf_area * oa, ort * nf, u8 mode, u32 metric, u32 ebit, ip_addr fwaddr, u32 tag, int pbit) -- new route received from nest and filters 1051:  1052: <H3>Arguments</H3> 1053:  1054: <DL> 1055: <DT>struct ospf_proto * p<DD>OSPF protocol instance 1056: <DT>struct ospf_area * oa<DD>ospf_area for which LSA is originated 1057: <DT>ort * nf<DD>network prefix and mask 1058: <DT>u8 mode<DD>the mode of the LSA (LSA_M_EXPORT or LSA_M_RTCALC) 1059: <DT>u32 metric<DD>the metric of a route 1060: <DT>u32 ebit<DD>E-bit for route metric (bool) 1061: <DT>ip_addr fwaddr<DD>the forwarding address 1062: <DT>u32 tag<DD>the route tag 1063: <DT>int pbit<DD>P-bit for NSSA LSAs (bool), ignored for external LSAs 1064: </DL> 1065: <H3>Description</H3> 1066: If I receive a message that new route is installed, I try to originate an 1067: external LSA. If oa is an NSSA area, NSSA-LSA is originated instead. 1068: oa should not be a stub area. src does not specify whether the LSA 1069: is external or NSSA, but it specifies the source of origination - 1070: the export from ospf_rt_notify(), or the NSSA-EXT translation. 1071: 1072: 1073: <HR><H3>Function</H3> 1074: struct top_graph * 1075: ospf_top_new 1076: (struct ospf_proto *p UNUSED4 UNUSED6, pool * pool) -- allocated new topology database 1077:  1078: <H3>Arguments</H3> 1079:  1080: <DL> 1081: <DT>struct ospf_proto *p UNUSED4 UNUSED6<DD>-- undescribed -- 1082: <DT>pool * pool<DD>pool for allocation 1083: </DL> 1084: <H3>Description</H3> 1085: This dynamically hashed structure is used for keeping LSAs. Mainly it is used 1086: for the LSA database of the OSPF protocol, but also for LSA retransmission 1087: and request lists of OSPF neighbors. 1088: 1089: 1090: <HR><H3>Function</H3> 1091: void 1092: ospf_neigh_chstate 1093: (struct ospf_neighbor * n, u8 state) -- handles changes related to new or lod state of neighbor 1094:  1095: <H3>Arguments</H3> 1096:  1097: <DL> 1098: <DT>struct ospf_neighbor * n<DD>OSPF neighbor 1099: <DT>u8 state<DD>new state 1100: </DL> 1101: <H3>Description</H3> 1102: Many actions have to be taken acording to a change of state of a neighbor. It 1103: starts rxmt timers, call interface state machine etc. 1104: 1105: 1106: <HR><H3>Function</H3> 1107: void 1108: ospf_neigh_sm 1109: (struct ospf_neighbor * n, int event) -- ospf neighbor state machine 1110:  1111: <H3>Arguments</H3> 1112:  1113: <DL> 1114: <DT>struct ospf_neighbor * n<DD>neighor 1115: <DT>int event<DD>actual event 1116: </DL> 1117: <H3>Description</H3> 1118: This part implements the neighbor state machine as described in 10.3 of 1119: RFC 2328. The only difference is that state NEIGHBOR_ATTEMPT is not 1120: used. We discover neighbors on nonbroadcast networks in the 1121: same way as on broadcast networks. The only difference is in 1122: sending hello packets. These are sent to IPs listed in 1123: ospf_iface->nbma_list . 1124: 1125: 1126: <HR><H3>Function</H3> 1127: void 1128: ospf_dr_election 1129: (struct ospf_iface * ifa) -- (Backup) Designed Router election 1130:  1131: <H3>Arguments</H3> 1132:  1133: <DL> 1134: <DT>struct ospf_iface * ifa<DD>actual interface 1135: </DL> 1136: <H3>Description</H3> 1137: When the wait timer fires, it is time to elect (Backup) Designated Router. 1138: Structure describing me is added to this list so every electing router has 1139: the same list. Backup Designated Router is elected before Designated 1140: Router. This process is described in 9.4 of RFC 2328. The function is 1141: supposed to be called only from ospf_iface_sm() as a part of the interface 1142: state machine. 1143: 1144: 1145: <HR><H3>Function</H3> 1146: void 1147: ospf_iface_chstate 1148: (struct ospf_iface * ifa, u8 state) -- handle changes of interface state 1149:  1150: <H3>Arguments</H3> 1151:  1152: <DL> 1153: <DT>struct ospf_iface * ifa<DD>OSPF interface 1154: <DT>u8 state<DD>new state 1155: </DL> 1156: <H3>Description</H3> 1157: Many actions must be taken according to interface state changes. New network 1158: LSAs must be originated, flushed, new multicast sockets to listen for messages for 1159: ALLDROUTERS have to be opened, etc. 1160: 1161: 1162: <HR><H3>Function</H3> 1163: void 1164: ospf_iface_sm 1165: (struct ospf_iface * ifa, int event) -- OSPF interface state machine 1166:  1167: <H3>Arguments</H3> 1168:  1169: <DL> 1170: <DT>struct ospf_iface * ifa<DD>OSPF interface 1171: <DT>int event<DD>event comming to state machine 1172: </DL> 1173: <H3>Description</H3> 1174: This fully respects 9.3 of RFC 2328 except we have slightly 1175: different handling of DOWN and LOOP state. We remove intefaces 1176: that are DOWN. DOWN state is used when an interface is waiting 1177: for a lock. LOOP state is used when an interface does not have a 1178: link. 1179: 1180: 1181: <HR><H3>Function</H3> 1182: int 1183: ospf_rx_hook 1184: (sock * sk, uint len) 1185: <H3>Arguments</H3> 1186:  1187: <DL> 1188: <DT>sock * sk<DD>socket we received the packet. 1189: <DT>uint len<DD>size of the packet 1190: </DL> 1191: <H3>Description</H3> 1192: This is the entry point for messages from neighbors. Many checks (like 1193: authentication, checksums, size) are done before the packet is passed to 1194: non generic functions. 1195: 1196: 1197: <HR><H3>Function</H3> 1198: int 1199: lsa_validate 1200: (struct ospf_lsa_header * lsa, u32 lsa_type, int ospf2, void * body) -- check whether given LSA is valid 1201:  1202: <H3>Arguments</H3> 1203:  1204: <DL> 1205: <DT>struct ospf_lsa_header * lsa<DD>LSA header 1206: <DT>u32 lsa_type<DD>one of LSA_T_xxx 1207: <DT>int ospf2<DD>true means OSPF version 2, false means OSPF version 3 1208: <DT>void * body<DD>pointer to LSA body 1209: </DL> 1210: <H3>Description</H3> 1211: Checks internal structure of given LSA body (minimal length, 1212: consistency). Returns true if valid. 1213: 1214: 1215: <HR><H3>Function</H3> 1216: void 1217: ospf_send_dbdes 1218: (struct ospf_proto * p, struct ospf_neighbor * n) -- transmit database description packet 1219:  1220: <H3>Arguments</H3> 1221:  1222: <DL> 1223: <DT>struct ospf_proto * p<DD>OSPF protocol instance 1224: <DT>struct ospf_neighbor * n<DD>neighbor 1225: </DL> 1226: <H3>Description</H3> 1227: Sending of a database description packet is described in 10.8 of RFC 2328. 1228: Reception of each packet is acknowledged in the sequence number of another. 1229: When I send a packet to a neighbor I keep a copy in a buffer. If the neighbor 1230: does not reply, I don't create a new packet but just send the content 1231: of the buffer. 1232: 1233: 1234: <HR><H3>Function</H3> 1235: void 1236: ospf_rt_spf 1237: (struct ospf_proto * p) -- calculate internal routes 1238:  1239: <H3>Arguments</H3> 1240:  1241: <DL> 1242: <DT>struct ospf_proto * p<DD>OSPF protocol instance 1243: </DL> 1244: <H3>Description</H3> 1245: Calculation of internal paths in an area is described in 16.1 of RFC 2328. 1246: It's based on Dijkstra's shortest path tree algorithms. 1247: This function is invoked from ospf_disp(). 1248: 1249: <H2><A NAME="ss5.6">5.6</A> <A HREF="prog.html#toc5.6">Pipe</A> 1250: </H2> 1251: 1252:  1253: The Pipe protocol is very simple. It just connects to two routing tables 1254: using proto_add_announce_hook() and whenever it receives a rt_notify() 1255: about a change in one of the tables, it converts it to a rte_update() 1256: in the other one. 1257: To avoid pipe loops, Pipe keeps a `being updated' flag in each routing 1258: table. 1259: A pipe has two announce hooks, the first connected to the main 1260: table, the second connected to the peer table. When a new route is 1261: announced on the main table, it gets checked by an export filter in 1262: ahook 1, and, after that, it is announced to the peer table via 1263: rte_update(), an import filter in ahook 2 is called. When a new 1264: route is announced in the peer table, an export filter in ahook2 1265: and an import filter in ahook 1 are used. Oviously, there is no 1266: need in filtering the same route twice, so both import filters are 1267: set to accept, while user configured 'import' and 'export' filters 1268: are used as export filters in ahooks 2 and 1. Route limits are 1269: handled similarly, but on the import side of ahooks. 1270:  1271:  1272: <H2><A NAME="ss5.7">5.7</A> <A HREF="prog.html#toc5.7">Routing Information Protocol (RIP)</A> 1273: </H2> 1274: 1275:  1276: The RIP protocol is implemented in two files: <CODE>rip.c</CODE> containing the protocol 1277: logic, route management and the protocol glue with BIRD core, and <CODE>packets.c</CODE> 1278: handling RIP packet processing, RX, TX and protocol sockets. 1279: Each instance of RIP is described by a structure rip_proto, which contains 1280: an internal RIP routing table, a list of protocol interfaces and the main 1281: timer responsible for RIP routing table cleanup. 1282: RIP internal routing table contains incoming and outgoing routes. For each 1283: network (represented by structure rip_entry) there is one outgoing route 1284: stored directly in rip_entry and an one-way linked list of incoming routes 1285: (structures rip_rte). The list contains incoming routes from different RIP 1286: neighbors, but only routes with the lowest metric are stored (i.e., all 1287: stored incoming routes have the same metric). 1288: Note that RIP itself does not select outgoing route, that is done by the core 1289: routing table. When a new incoming route is received, it is propagated to the 1290: RIP table by rip_update_rte() and possibly stored in the list of incoming 1291: routes. Then the change may be propagated to the core by rip_announce_rte(). 1292: The core selects the best route and propagate it to RIP by rip_rt_notify(), 1293: which updates outgoing route part of rip_entry and possibly triggers route 1294: propagation by rip_trigger_update(). 1295: RIP interfaces are represented by structures rip_iface. A RIP interface 1296: contains a per-interface socket, a list of associated neighbors, interface 1297: configuration, and state information related to scheduled interface events 1298: and running update sessions. RIP interfaces are added and removed based on 1299: core interface notifications. 1300: There are two RIP interface events - regular updates and triggered updates. 1301: Both are managed from the RIP interface timer (rip_iface_timer()). Regular 1302: updates are called at fixed interval and propagate the whole routing table, 1303: while triggered updates are scheduled by rip_trigger_update() due to some 1304: routing table change and propagate only the routes modified since the time 1305: they were scheduled. There are also unicast-destined requested updates, but 1306: these are sent directly as a reaction to received RIP request message. The 1307: update session is started by rip_send_table(). There may be at most one 1308: active update session per interface, as the associated state (including the 1309: fib iterator) is stored directly in rip_iface structure. 1310: RIP neighbors are represented by structures rip_neighbor. Compared to 1311: neighbor handling in other routing protocols, RIP does not have explicit 1312: neighbor discovery and adjacency maintenance, which makes the rip_neighbor 1313: related code a bit peculiar. RIP neighbors are interlinked with core neighbor 1314: structures (neighbor) and use core neighbor notifications to ensure that RIP 1315: neighbors are timely removed. RIP neighbors are added based on received route 1316: notifications and removed based on core neighbor and RIP interface events. 1317: RIP neighbors are linked by RIP routes and use counter to track the number of 1318: associated routes, but when these RIP routes timeout, associated RIP neighbor 1319: is still alive (with zero counter). When RIP neighbor is removed but still 1320: has some associated routes, it is not freed, just changed to detached state 1321: (core neighbors and RIP ifaces are unlinked), then during the main timer 1322: cleanup phase the associated routes are removed and the rip_neighbor 1323: structure is finally freed. 1324: Supported standards: 1325: - RFC 1058 - RIPv1 1326: - RFC 2453 - RIPv2 1327: - RFC 2080 - RIPng 1328: - RFC 4822 - RIP cryptographic authentication 1329:  1330: <HR><H3>Function</H3> 1331: void 1332: rip_announce_rte 1333: (struct rip_proto * p, struct rip_entry * en) -- announce route from RIP routing table to the core 1334:  1335: <H3>Arguments</H3> 1336:  1337: <DL> 1338: <DT>struct rip_proto * p<DD>RIP instance 1339: <DT>struct rip_entry * en<DD>related network 1340: </DL> 1341: <H3>Description</H3> 1342: The function takes a list of incoming routes from en, prepare appropriate 1343: rte for the core and propagate it by rte_update(). 1344: 1345: 1346: <HR><H3>Function</H3> 1347: void 1348: rip_update_rte 1349: (struct rip_proto * p, ip_addr * prefix, int pxlen, struct rip_rte * new) -- enter a route update to RIP routing table 1350:  1351: <H3>Arguments</H3> 1352:  1353: <DL> 1354: <DT>struct rip_proto * p<DD>RIP instance 1355: <DT>ip_addr * prefix<DD>network prefix 1356: <DT>int pxlen<DD>network prefix length 1357: <DT>struct rip_rte * new<DD>a rip_rte representing the new route 1358: </DL> 1359: <H3>Description</H3> 1360: The function is called by the RIP packet processing code whenever it receives 1361: a reachable route. The appropriate routing table entry is found and the list 1362: of incoming routes is updated. Eventually, the change is also propagated to 1363: the core by rip_announce_rte(). Note that for unreachable routes, 1364: rip_withdraw_rte() should be called instead of rip_update_rte(). 1365: 1366: 1367: <HR><H3>Function</H3> 1368: void 1369: rip_withdraw_rte 1370: (struct rip_proto * p, ip_addr * prefix, int pxlen, struct rip_neighbor * from) -- enter a route withdraw to RIP routing table 1371:  1372: <H3>Arguments</H3> 1373:  1374: <DL> 1375: <DT>struct rip_proto * p<DD>RIP instance 1376: <DT>ip_addr * prefix<DD>network prefix 1377: <DT>int pxlen<DD>network prefix length 1378: <DT>struct rip_neighbor * from<DD>a rip_neighbor propagating the withdraw 1379: </DL> 1380: <H3>Description</H3> 1381: The function is called by the RIP packet processing code whenever it receives 1382: an unreachable route. The incoming route for given network from nbr from is 1383: removed. Eventually, the change is also propagated by rip_announce_rte(). 1384: 1385: 1386: <HR><H3>Function</H3> 1387: void 1388: rip_timer 1389: (timer * t) -- RIP main timer hook 1390:  1391: <H3>Arguments</H3> 1392:  1393: <DL> 1394: <DT>timer * t<DD>timer 1395: </DL> 1396: <H3>Description</H3> 1397: The RIP main timer is responsible for routing table maintenance. Invalid or 1398: expired routes (rip_rte) are removed and garbage collection of stale routing 1399: table entries (rip_entry) is done. Changes are propagated to core tables, 1400: route reload is also done here. Note that garbage collection uses a maximal 1401: GC time, while interfaces maintain an illusion of per-interface GC times in 1402: rip_send_response(). 1403: Keeping incoming routes and the selected outgoing route are two independent 1404: functions, therefore after garbage collection some entries now considered 1405: invalid (RIP_ENTRY_DUMMY) still may have non-empty list of incoming routes, 1406: while some valid entries (representing an outgoing route) may have that list 1407: empty. 1408: The main timer is not scheduled periodically but it uses the time of the 1409: current next event and the minimal interval of any possible event to compute 1410: the time of the next run. 1411: 1412: 1413: <HR><H3>Function</H3> 1414: void 1415: rip_iface_timer 1416: (timer * t) -- RIP interface timer hook 1417:  1418: <H3>Arguments</H3> 1419:  1420: <DL> 1421: <DT>timer * t<DD>timer 1422: </DL> 1423: <H3>Description</H3> 1424: RIP interface timers are responsible for scheduling both regular and 1425: triggered updates. Fixed, delay-independent period is used for regular 1426: updates, while minimal separating interval is enforced for triggered updates. 1427: The function also ensures that a new update is not started when the old one 1428: is still running. 1429: 1430: 1431: <HR><H3>Function</H3> 1432: void 1433: rip_send_table 1434: (struct rip_proto * p, struct rip_iface * ifa, ip_addr addr, bird_clock_t changed) -- RIP interface timer hook 1435:  1436: <H3>Arguments</H3> 1437:  1438: <DL> 1439: <DT>struct rip_proto * p<DD>RIP instance 1440: <DT>struct rip_iface * ifa<DD>RIP interface 1441: <DT>ip_addr addr<DD>destination IP address 1442: <DT>bird_clock_t changed<DD>time limit for triggered updates 1443: </DL> 1444: <H3>Description</H3> 1445: The function activates an update session and starts sending routing update 1446: packets (using rip_send_response()). The session may be finished during the 1447: call or may continue in rip_tx_hook() until all appropriate routes are 1448: transmitted. Note that there may be at most one active update session per 1449: interface, the function will terminate the old active session before 1450: activating the new one. 1451: 1452: <H2><A NAME="ss5.8">5.8</A> <A HREF="prog.html#toc5.8">Router Advertisements</A> 1453: </H2> 1454: 1455:  1456: The RAdv protocol is implemented in two files: <CODE>radv.c</CODE> containing the 1457: interface with BIRD core and the protocol logic and <CODE>packets.c</CODE> handling low 1458: level protocol stuff (RX, TX and packet formats). The protocol does not 1459: export any routes. 1460: The RAdv is structured in the usual way - for each handled interface there is 1461: a structure radv_iface that contains a state related to that interface 1462: together with its resources (a socket, a timer). There is also a prepared RA 1463: stored in a TX buffer of the socket associated with an iface. These iface 1464: structures are created and removed according to iface events from BIRD core 1465: handled by radv_if_notify() callback. 1466: The main logic of RAdv consists of two functions: radv_iface_notify(), which 1467: processes asynchronous events (specified by RA_EV_* codes), and radv_timer(), 1468: which triggers sending RAs and computes the next timeout. 1469: The RAdv protocol could receive routes (through radv_import_control() and 1470: radv_rt_notify()), but only the configured trigger route is tracked (in 1471: active var). When a radv protocol is reconfigured, the connected routing 1472: table is examined (in radv_check_active()) to have proper active value in 1473: case of the specified trigger prefix was changed. 1474: Supported standards: 1475: - RFC 4861 - main RA standard 1476: - RFC 4191 - Default Router Preferences and More-Specific Routes 1477: - RFC 6106 - DNS extensions (RDDNS, DNSSL) 1478:  1479:  1480: <H2><A NAME="ss5.9">5.9</A> <A HREF="prog.html#toc5.9">Static</A> 1481: </H2> 1482: 1483:  1484: The Static protocol is implemented in a straightforward way. It keeps 1485: two lists of static routes: one containing interface routes and one 1486: holding the remaining ones. Interface routes are inserted and removed according 1487: to interface events received from the core via the if_notify() hook. Routes 1488: pointing to a neighboring router use a sticky node in the neighbor cache 1489: to be notified about gaining or losing the neighbor. Special 1490: routes like black holes or rejects are inserted all the time. 1491: Multipath routes are tricky. Because these routes depends on 1492: several neighbors we need to integrate that to the neighbor 1493: notification handling, we use dummy static_route nodes, one for 1494: each nexthop. Therefore, a multipath route consists of a master 1495: static_route node (of dest RTD_MULTIPATH), which specifies prefix 1496: and is used in most circumstances, and a list of dummy static_route 1497: nodes (of dest RTD_NONE), which stores info about nexthops and are 1498: connected to neighbor entries and neighbor notifications. Dummy 1499: nodes are chained using mp_next, they aren't in other_routes list, 1500: and abuse some fields (masklen, if_name) for other purposes. 1501: The only other thing worth mentioning is that when asked for reconfiguration, 1502: Static not only compares the two configurations, but it also calculates 1503: difference between the lists of static routes and it just inserts the 1504: newly added routes and removes the obsolete ones. 1505:  1506:  1507: <H2><A NAME="ss5.10">5.10</A> <A HREF="prog.html#toc5.10">Direct</A> 1508: </H2> 1509: 1510:  1511: The Direct protocol works by converting all ifa_notify() events it receives 1512: to rte_update() calls for the corresponding network. 1513:  1514:  1515:  1516: <HR> 1517: <A HREF="prog-6.html">Next</A> 1518: <A HREF="prog-4.html">Previous</A> 1519: <A HREF="prog.html#toc5">Contents</A> 1520: </BODY> 1521: </HTML>