diff options
Diffstat (limited to 'doc/developer')
| -rw-r--r-- | doc/developer/library.rst | 3 | ||||
| -rw-r--r-- | doc/developer/lists.rst | 594 | ||||
| -rw-r--r-- | doc/developer/ospf-api.rst | 334 | ||||
| -rw-r--r-- | doc/developer/subdir.am | 1 |
4 files changed, 762 insertions, 170 deletions
diff --git a/doc/developer/library.rst b/doc/developer/library.rst index 77b2f229b7..4ba0c0ebc6 100644 --- a/doc/developer/library.rst +++ b/doc/developer/library.rst @@ -7,8 +7,9 @@ Library Facilities (libfrr) .. toctree:: :maxdepth: 2 - logging memtypes + lists + logging hooks cli modules diff --git a/doc/developer/lists.rst b/doc/developer/lists.rst new file mode 100644 index 0000000000..6d60420b2f --- /dev/null +++ b/doc/developer/lists.rst @@ -0,0 +1,594 @@ +List implementations +==================== + +.. note:: + + The term *list* is used generically for lists, skiplists, trees and hash + tables in this document. + +Common list interface +--------------------- + +FRR includes a set of list-like data structure implementations with abstracted +common APIs. The purpose of this is easily allow swapping out one +data structure for another while also making the code easier to read and write. +There is one API for unsorted lists and a similar but not identical API for +sorted lists. + +For unsorted lists, the following implementations exist: + +- single-linked list with tail pointer (e.g. STAILQ in BSD) + +- atomic single-linked list with tail pointer + + +For sorted lists, these data structures are implemented: + +- single-linked list + +- atomic single-linked list + +- skiplist + +- red-black tree (based on OpenBSD RB_TREE) + +- hash table (note below) + +Except for hash tables, each of the sorted data structures has a variant with +unique and non-unique list items. Hash tables always require unique items +and mostly follow the "sorted" API but use the hash value as sorting +key. Also, iterating while modifying does not work with hash tables. + + +The following sorted structures are likely to be implemented at some point +in the future: + +- atomic skiplist + +- atomic hash table (note below) + + +The APIs are all designed to be as type-safe as possible. This means that +there will be a compiler warning when an item doesn't match the list, or +the return value has a different type, or other similar situations. **You +should never use casts with these APIs.** If a cast is neccessary in relation +to these APIs, there is probably something wrong with the overall design. + +Only the following pieces use dynamically allocated memory: + +- the hash table itself is dynamically grown and shrunk + +- skiplists store up to 4 next pointers inline but will dynamically allocate + memory to hold an item's 5th up to 16th next pointer (if they exist) + +Cheat sheet +----------- + +Available types: + +:: + + DECLARE_LIST + DECLARE_ATOMLIST + + DECLARE_SORTLIST_UNIQ + DECLARE_SORTLIST_NONUNIQ + DECLARE_ATOMLIST_UNIQ + DECLARE_ATOMLIST_NONUNIQ + DECLARE_SKIPLIST_UNIQ + DECLARE_SKIPLIST_NONUNIQ + DECLARE_RBTREE_UNIQ + DECLARE_RBTREE_NONUNIQ + + DECLARE_HASH + +Functions provided: + ++------------------------------------+------+------+---------+------------+ +| Function | LIST | HASH | \*_UNIQ | \*_NONUNIQ | ++====================================+======+======+=========+============+ +| _init, _fini | yes | yes | yes | yes | ++------------------------------------+------+------+---------+------------+ +| _first, _next, _next_safe | yes | yes | yes | yes | ++------------------------------------+------+------+---------+------------+ +| _add_head, _add_tail, _add_after | yes | -- | -- | -- | ++------------------------------------+------+------+---------+------------+ +| _add | -- | yes | yes | yes | ++------------------------------------+------+------+---------+------------+ +| _del, _pop | yes | yes | yes | yes | ++------------------------------------+------+------+---------+------------+ +| _find | -- | yes | yes | -- | ++------------------------------------+------+------+---------+------------+ +| _find_lt, _find_gteq | -- | -- | yes | yes | ++------------------------------------+------+------+---------+------------+ +| use with for_each() macros | yes | yes | yes | yes | ++------------------------------------+------+------+---------+------------+ + + +Datastructure type setup +------------------------ + +Each of the data structures has a ``PREDECL_*`` and a ``DECLARE_*`` macro to +set up an "instantiation" of the list. This works somewhat similar to C++ +templating, though much simpler. + +**In all following text, the Z prefix is replaced with a name choosen +for the instance of the datastructure.** + +The common setup pattern will look like this: + +.. code-block:: c + + PREDECL_XXX(Z) + struct item { + int otherdata; + struct Z_item mylistitem; + } + + struct Z_head mylisthead; + + /* unsorted: */ + DECLARE_XXX(Z, struct item, mylistitem) + + /* sorted, items that compare as equal cannot be added to list */ + int compare_func(const struct item *a, const struct item *b); + DECLARE_XXX_UNIQ(Z, struct item, mylistitem, compare_func) + + /* sorted, items that compare as equal can be added to list */ + int compare_func(const struct item *a, const struct item *b); + DECLARE_XXX_NONUNIQ(Z, struct item, mylistitem, compare_func) + + /* hash tables: */ + int compare_func(const struct item *a, const struct item *b); + uint32_t hash_func(const struct item *a); + DECLARE_XXX(Z, struct item, mylistitem, compare_func, hash_func) + +``XXX`` is replaced with the name of the data structure, e.g. ``SKIPLIST`` +or ``ATOMLIST``. The ``DECLARE_XXX`` invocation can either occur in a `.h` +file (if the list needs to be accessed from several C files) or it can be +placed in a `.c` file (if the list is only accessed from that file.) The +``PREDECL_XXX`` invocation defines the ``struct Z_item`` and ``struct +Z_head`` types and must therefore occur before these are used. + +To switch between compatible data structures, only these two lines need to be +changes. To switch to a data structure with a different API, some source +changes are necessary. + +Common iteration macros +----------------------- + +The following iteration macros work across all data structures: + +.. c:function:: for_each(Z, head, item) + + Equivalent to: + + .. code-block:: c + + for (item = Z_first(head); item; item = Z_next(head, item)) + + Note that this will fail if the list is modified while being iterated + over. + +.. c:function:: for_each_safe(Z, head, item) + + Same as the previous, but the next element is pre-loaded into a "hidden" + variable (named ``Z_safe``.) Equivalent to: + + .. code-block:: c + + for (item = Z_first(head); item; item = next) { + next = Z_next_safe(head, item); + ... + } + + .. warning:: + + Iterating over hash tables while adding or removing items is not + possible. The iteration position will be corrupted when the hash + tables is resized while iterating. This will cause items to be + skipped or iterated over twice. + +.. c:function:: for_each_from(Z, head, item, from) + + Iterates over the list, starting at item ``from``. This variant is "safe" + as in the previous macro. Equivalent to: + + .. code-block:: c + + for (item = from; item; item = from) { + from = Z_next_safe(head, item); + ... + } + + .. note:: + + The ``from`` variable is written to. This is intentional - you can + resume iteration after breaking out of the loop by keeping the ``from`` + value persistent and reusing it for the next loop. + +Common API +---------- + +The following documentation assumes that a list has been defined using +``Z`` as the name, and ``itemtype`` being the type of the list items (e.g. +``struct item``.) + +.. c:function:: void Z_init(struct Z_head *) + + Initializes the list for use. For most implementations, this just sets + some values. Hash tables are the only implementation that allocates + memory in this call. + +.. c:function:: void Z_fini(struct Z_head *) + + Reverse the effects of :c:func:`Z_init()`. The list must be empty + when this function is called. + + .. warning:: + + This function may ``assert()`` if the list is not empty. + +.. c:function:: size_t Z_count(struct Z_head *) + + Returns the number of items in a structure. All structures store a + counter in their `Z_head` so that calling this function completes + in O(1). + + .. note:: + + For atomic lists with concurrent access, the value will already be + outdated by the time this function returns and can therefore only be + used as an estimate. + +.. c:function:: itemtype *Z_first(struct Z_head *) + + Returns the first item in the structure, or ``NULL`` if the structure is + empty. This is O(1) for all data structures except red-black trees + where it is O(log n). + +.. c:function:: itemtype *Z_pop(struct Z_head *) + + Remove and return the first item in the structure, or ``NULL`` if the + structure is empty. Like :c:func:`Z_first`, this is O(1) for all + data structures except red-black trees where it is O(log n) again. + + This function can be used to build queues (with unsorted structures) or + priority queues (with sorted structures.) + + Another common pattern is deleting all list items: + + .. code-block:: c + + while ((item = Z_pop(head))) + item_free(item); + + .. note:: + + This function can - and should - be used with hash tables. It is not + affected by the "modification while iterating" problem. To remove + all items from a hash table, use the loop demonstrated above. + +.. c:function:: itemtype *Z_next(struct Z_head *, itemtype *prev) + + Return the item that follows after ``prev``, or ``NULL`` if ``prev`` is + the last item. + + .. warning:: + + ``prev`` must not be ``NULL``! Use :c:func:`Z_next_safe()` if + ``prev`` might be ``NULL``. + +.. c:function:: itemtype *Z_next_safe(struct Z_head *, itemtype *prev) + + Same as :c:func:`Z_next()`, except that ``NULL`` is returned if + ``prev`` is ``NULL``. + +.. c:function:: itemtype *Z_del(struct Z_head *, itemtype *item) + + Remove ``item`` from the list and return it. + + .. note:: + + This function's behaviour is undefined if ``item`` is not actually + on the list. Some structures return ``NULL`` in this case while others + return ``item``. The function may also call ``assert()`` (but most + don't.) + +.. todo:: + + ``Z_del_after()`` / ``Z_del_hint()``? + +API for unsorted structures +--------------------------- + +Since the insertion position is not pre-defined for unsorted data, there +are several functions exposed to insert data: + +.. note:: + + ``item`` must not be ``NULL`` for any of the following functions. + +.. c:function:: DECLARE_XXX(Z, type, field) + + :param listtype XXX: ``LIST`` or ``ATOMLIST`` to select a data structure + implementation. + :param token Z: Gives the name prefix that is used for the functions + created for this instantiation. ``DECLARE_XXX(foo, ...)`` + gives ``struct foo_item``, ``foo_add_head()``, ``foo_count()``, etc. Note + that this must match the value given in ``PREDECL_XXX(foo)``. + :param typename type: Specifies the data type of the list items, e.g. + ``struct item``. Note that ``struct`` must be added here, it is not + automatically added. + :param token field: References a struct member of ``type`` that must be + typed as ``struct foo_item``. This struct member is used to + store "next" pointers or other data structure specific data. + +.. c:function:: void Z_add_head(struct Z_head *, itemtype *item) + + Insert an item at the beginning of the structure, before the first item. + This is an O(1) operation for non-atomic lists. + +.. c:function:: void Z_add_tail(struct Z_head *, itemtype *item) + + Insert an item at the end of the structure, after the last item. + This is also an O(1) operation for non-atomic lists. + +.. c:function:: void Z_add_after(struct Z_head *, itemtype *after, itemtype *item) + + Insert ``item`` behind ``after``. If ``after`` is ``NULL``, the item is + inserted at the beginning of the list as with :c:func:`Z_add_head`. + This is also an O(1) operation for non-atomic lists. + + A common pattern is to keep a "previous" pointer around while iterating: + + .. code-block:: c + + itemtype *prev = NULL, *item; + + for_each_safe(Z, head, item) { + if (something) { + Z_add_after(head, prev, item); + break; + } + prev = item; + } + + .. todo:: + + maybe flip the order of ``item`` & ``after``? + ``Z_add_after(head, item, after)`` + +API for sorted structures +------------------------- + +Sorted data structures do not need to have an insertion position specified, +therefore the insertion calls are different from unsorted lists. Also, +sorted lists can be searched for a value. + +.. c:function:: DECLARE_XXX_UNIQ(Z, type, field, compare_func) + + :param listtype XXX: One of the following: + ``SORTLIST`` (single-linked sorted list), ``SKIPLIST`` (skiplist), + ``RBTREE`` (RB-tree) or ``ATOMSORT`` (atomic single-linked list). + :param token Z: Gives the name prefix that is used for the functions + created for this instantiation. ``DECLARE_XXX(foo, ...)`` + gives ``struct foo_item``, ``foo_add()``, ``foo_count()``, etc. Note + that this must match the value given in ``PREDECL_XXX(foo)``. + :param typename type: Specifies the data type of the list items, e.g. + ``struct item``. Note that ``struct`` must be added here, it is not + automatically added. + :param token field: References a struct member of ``type`` that must be + typed as ``struct foo_item``. This struct member is used to + store "next" pointers or other data structure specific data. + :param funcptr compare_func: Item comparison function, must have the + following function signature: + ``int function(const itemtype *, const itemtype*)``. This function + may be static if the list is only used in one file. + +.. c:function:: DECLARE_XXX_NONUNIQ(Z, type, field, compare_func) + + Same as above, but allow adding multiple items to the list that compare + as equal in ``compare_func``. Ordering between these items is undefined + and depends on the list implementation. + +.. c:function:: itemtype *Z_add(struct Z_head *, itemtype *item) + + Insert an item at the appropriate sorted position. If another item exists + in the list that compares as equal (``compare_func()`` == 0), ``item`` is + not inserted into the list and the already-existing item in the list is + returned. Otherwise, on successful insertion, ``NULL`` is returned. + + For ``_NONUNIQ`` lists, this function always returns NULL since ``item`` + can always be successfully added to the list. + +.. c:function:: itemtype *Z_find(struct Z_head *, const itemtype *ref) + + Search the list for an item that compares equal to ``ref``. If no equal + item is found, return ``NULL``. + + This function is likely used with a temporary stack-allocated value for + ``ref`` like so: + + .. code-block:: c + + itemtype searchfor = { .foo = 123 }; + + itemtype *item = Z_find(head, &searchfor); + + .. note:: + + The ``Z_find()`` function is only available for lists that contain + unique items (i.e. ``DECLARE_XXX_UNIQ``.) This is because on a list + containing non-unique items, more than one item may compare as equal to + the item that is searched for. + +.. c:function:: itemtype *Z_find_gteq(struct Z_head *, const itemtype *ref) + + Search the list for an item that compares greater or equal to + ``ref``. See :c:func:`Z_find()` above. + +.. c:function:: itemtype *Z_find_lt(struct Z_head *, const itemtype *ref) + + Search the list for an item that compares less than + ``ref``. See :c:func:`Z_find()` above. + + +API for hash tables +------------------- + +.. c:function:: DECLARE_XXX(Z, type, field, compare_func, hash_func) + + :param listtype XXX: Only ``HASH`` is currently available. + :param token Z: Gives the name prefix that is used for the functions + created for this instantiation. ``DECLARE_XXX(foo, ...)`` + gives ``struct foo_item``, ``foo_add()``, ``foo_count()``, etc. Note + that this must match the value given in ``PREDECL_XXX(foo)``. + :param typename type: Specifies the data type of the list items, e.g. + ``struct item``. Note that ``struct`` must be added here, it is not + automatically added. + :param token field: References a struct member of ``type`` that must be + typed as ``struct foo_item``. This struct member is used to + store "next" pointers or other data structure specific data. + :param funcptr compare_func: Item comparison function, must have the + following function signature: + ``int function(const itemtype *, const itemtype*)``. This function + may be static if the list is only used in one file. For hash tables, + this function is only used to check for equality, the ordering is + ignored. + :param funcptr hash_func: Hash calculation function, must have the + following function signature: + ``uint32_t function(const itemtype *)``. The hash value for items + stored in a hash table is cached in each item, so this value need not + be cached by the user code. + + .. warning:: + + Items that compare as equal cannot be inserted. Refer to the notes + about sorted structures in the previous section. + +.. c:function:: void Z_init_size(struct Z_head *, size_t size) + + Same as :c:func:`Z_init()` but preset the minimum hash table to + ``size``. + +Hash tables also support :c:func:`Z_add()` and :c:func:`Z_find()` with +the same semantics as noted above. :c:func:`Z_find_gteq()` and +:c:func:`Z_find_lt()` are **not** provided for hash tables. + + +Atomic lists +------------ + +`atomlist.h` provides an unsorted and a sorted atomic single-linked list. +Since atomic memory accesses can be considerably slower than plain memory +accessses (depending on the CPU type), these lists should only be used where +neccessary. + +The following guarantees are provided regarding concurrent access: + +- the operations are lock-free but not wait-free. + + Lock-free means that it is impossible for all threads to be blocked. Some + thread will always make progress, regardless of what other threads do. (This + even includes a random thread being stopped by a debugger in a random + location.) + + Wait-free implies that the time any single thread might spend in one of the + calls is bounded. This is not provided here since it is not normally + relevant to practical operations. What this means is that if some thread is + hammering a particular list with requests, it is possible that another + thread is blocked for an extended time. The lock-free guarantee still + applies since the hammering thread is making progress. + +- without a RCU mechanism in place, the point of contention for atomic lists + is memory deallocation. As it is, **a rwlock is required for correct + operation**. The *read* lock must be held for all accesses, including + reading the list, adding items to the list, and removing items from the + list. The *write* lock must be acquired and released before deallocating + any list element. If this is not followed, an use-after-free can occur + as a MT race condition when an element gets deallocated while another + thread is accessing the list. + + .. note:: + + The *write* lock does not need to be held for deleting items from the + list, and there should not be any instructions between the + ``pthread_rwlock_wrlock`` and ``pthread_rwlock_unlock``. The write lock + is used as a sequence point, not as an exclusion mechanism. + +- insertion operations are always safe to do with the read lock held. + Added items are immediately visible after the insertion call returns and + should not be touched anymore. + +- when removing a *particular* (pre-determined) item, the caller must ensure + that no other thread is attempting to remove that same item. If this cannot + be guaranteed by architecture, a separate lock might need to be added. + +- concurrent `pop` calls are always safe to do with only the read lock held. + This does not fall under the previous rule since the `pop` call will select + the next item if the first is already being removed by another thread. + + **Deallocation locking still applies.** Assume another thread starts + reading the list, but gets task-switched by the kernel while reading the + first item. `pop` will happily remove and return that item. If it is + deallocated without acquiring and releasing the write lock, the other thread + will later resume execution and try to access the now-deleted element. + +- the list count should be considered an estimate. Since there might be + concurrent insertions or removals in progress, it might already be outdated + by the time the call returns. No attempt is made to have it be correct even + for a nanosecond. + +Overall, atomic lists are well-suited for MT queues; concurrent insertion, +iteration and removal operations will work with the read lock held. + +Code snippets +^^^^^^^^^^^^^ + +Iteration: + +.. code-block:: c + + struct item *i; + + pthread_rwlock_rdlock(&itemhead_rwlock); + for_each(itemlist, &itemhead, i) { + /* lock must remain held while iterating */ + ... + } + pthread_rwlock_unlock(&itemhead_rwlock); + +Head removal (pop) and deallocation: + +.. code-block:: c + + struct item *i; + + pthread_rwlock_rdlock(&itemhead_rwlock); + i = itemlist_pop(&itemhead); + pthread_rwlock_unlock(&itemhead_rwlock); + + /* i might still be visible for another thread doing an + * for_each() (but won't be returned by another pop()) */ + ... + + pthread_rwlock_wrlock(&itemhead_rwlock); + pthread_rwlock_unlock(&itemhead_rwlock); + /* i now guaranteed to be gone from the list. + * note nothing between wrlock() and unlock() */ + XFREE(MTYPE_ITEM, i); + +FRR lists +--------- + +.. TODO:: + + document + +BSD lists +--------- + +.. TODO:: + + refer to external docs diff --git a/doc/developer/ospf-api.rst b/doc/developer/ospf-api.rst index f4f38a63e9..41c31b29c3 100644 --- a/doc/developer/ospf-api.rst +++ b/doc/developer/ospf-api.rst @@ -4,76 +4,76 @@ OSPF API Documentation Disclaimer ---------- -The OSPF daemon contains an API for application access to the LSA -database. This API was created by Ralph Keller, originally as patch for -Zebra. Unfortunately, the page containing documentation of the API is no -longer online. This page is an attempt to recreate documentation for the -API (with lots of help of the WayBackMachine) +The OSPF daemon contains an API for application access to the LSA database. +This API and documentation was created by Ralph Keller, originally as patch for +Zebra. Unfortunately, the page containing documentation for the API is no +longer online. This page is an attempt to recreate documentation for the API +(with lots of help from the WayBackMachine). + +Ralph has kindly licensed this documentation under GPLv2+. Please preserve the +acknowledgements at the bottom of this document. Introduction ------------ -This page describes an API that allows external applications to access -the link-state database (LSDB) of the OSPF daemon. The implementation is -based on the OSPF code from FRRouting (forked from Quagga and formerly -Zebra) routing protocol suite and is subject to the GNU General Public -License. The OSPF API provides you with the following functionality: - -- Retrieval of the full or partial link-state database of the OSPF - daemon. This allows applications to obtain an exact copy of the LSDB - including router LSAs, network LSAs and so on. Whenever a new LSA - arrives at the OSPF daemon, the API module immediately informs the - application by sending a message. This way, the application is always - synchronized with the LSDB of the OSPF daemon. -- Origination of own opaque LSAs (of type 9, 10, or 11) which are then - distributed transparently to other routers within the flooding scope - and received by other applications through the OSPF API. - -Opaque LSAs, which are described in RFC 2370 , allow you to distribute -application-specific information within a network using the OSPF -protocol. The information contained in opaque LSAs is transparent for -the routing process but it can be processed by other modules such as -traffic engineering (e.g., MPLS-TE). +This page describes an API that allows external applications to access the +link-state database (LSDB) of the OSPF daemon. The implementation is based on +the OSPF code from FRRouting (forked from Quagga and formerly Zebra) routing +protocol suite and is subject to the GNU General Public License. The OSPF API +provides you with the following functionality: + +- Retrieval of the full or partial link-state database of the OSPF daemon. + This allows applications to obtain an exact copy of the LSDB including router + LSAs, network LSAs and so on. Whenever a new LSA arrives at the OSPF daemon, + the API module immediately informs the application by sending a message. This + way, the application is always synchronized with the LSDB of the OSPF daemon. +- Origination of own opaque LSAs (of type 9, 10, or 11) which are then + distributed transparently to other routers within the flooding scope and + received by other applications through the OSPF API. + +Opaque LSAs, which are described in :rfc:`2370`, allow you to distribute +application-specific information within a network using the OSPF protocol. The +information contained in opaque LSAs is transparent for the routing process but +it can be processed by other modules such as traffic engineering (e.g., +MPLS-TE). Architecture ------------ -The following picture depicts the architecture of the Quagga/Zebra -protocol suite. The OSPF daemon is extended with opaque LSA capabilities -and an API for external applications. The OSPF core module executes the -OSPF protocol by discovering neighbors and exchanging neighbor state. -The opaque module, implemented by Masahiko Endo, provides functions to -exchange opaque LSAs between routers. Opaque LSAs can be generated by -several modules such as the MPLS-TE module or the API server module. -These modules then invoke the opaque module to flood their data to -neighbors within the flooding scope. - -The client, which is an application potentially running on a different -node than the OSPF daemon, links against the OSPF API client library. -This client library establishes a socket connection with the API server -module of the OSPF daemon and uses this connection to retrieve LSAs and -originate opaque LSAs. +The following picture depicts the architecture of the Quagga/Zebra protocol +suite. The OSPF daemon is extended with opaque LSA capabilities and an API for +external applications. The OSPF core module executes the OSPF protocol by +discovering neighbors and exchanging neighbor state. The opaque module, +implemented by Masahiko Endo, provides functions to exchange opaque LSAs +between routers. Opaque LSAs can be generated by several modules such as the +MPLS-TE module or the API server module. These modules then invoke the opaque +module to flood their data to neighbors within the flooding scope. + +The client, which is an application potentially running on a different node +than the OSPF daemon, links against the OSPF API client library. This client +library establishes a socket connection with the API server module of the OSPF +daemon and uses this connection to retrieve LSAs and originate opaque LSAs. .. figure:: ../figures/ospf_api_architecture.png :alt: image image -The OSPF API server module works like any other internal opaque module -(such as the MPLS-TE module), but listens to connections from external -applications that want to communicate with the OSPF daemon. The API -server module can handle multiple clients concurrently. +The OSPF API server module works like any other internal opaque module (such as +the MPLS-TE module), but listens to connections from external applications that +want to communicate with the OSPF daemon. The API server module can handle +multiple clients concurrently. -One of the main objectives of the implementation is to make as little -changes to the existing Zebra code as possible. +One of the main objectives of the implementation is to make as little changes +to the existing Zebra code as possible. Installation & Configuration ---------------------------- -Download FRRouting and unpack +Download FRRouting and unpack it. -Configure your frr version (note that --enable-opaque-lsa also enables -the ospfapi server and ospfclient). +Configure and build FRR (note that ``--enable-opaque-lsa`` also enables the +ospfapi server and ospfclient). :: @@ -83,8 +83,8 @@ the ospfapi server and ospfclient). This should also compile the client library and sample application in ospfclient. -Make sure that you have enabled opaque LSAs in your configuration. Add -the ospf opaque-lsa statement to your ospfd.conf: +Make sure that you have enabled opaque LSAs in your configuration. Add the +``ospf opaque-lsa`` statement to your :file:`ospfd.conf`: :: @@ -108,171 +108,165 @@ Usage ----- In the following we describe how you can use the sample application to -originate opaque LSAs. The sample application first registers with the -OSPF daemon the opaque type it wants to inject and then waits until the -OSPF daemon is ready to accept opaque LSAs of that type. Then the client -application originates an opaque LSA, waits 10 seconds and then updates -the opaque LSA with new opaque data. After another 20 seconds, the -client application deletes the opaque LSA from the LSDB. If the clients -terminates unexpectedly, the OSPF API module will remove all the opaque -LSAs that the application registered. Since the opaque LSAs are flooded -to other routers, we will see the opaque LSAs in all routers according -to the flooding scope of the opaque LSA. +originate opaque LSAs. The sample application first registers with the OSPF +daemon the opaque type it wants to inject and then waits until the OSPF daemon +is ready to accept opaque LSAs of that type. Then the client application +originates an opaque LSA, waits 10 seconds and then updates the opaque LSA with +new opaque data. After another 20 seconds, the client application deletes the +opaque LSA from the LSDB. If the clients terminates unexpectedly, the OSPF API +module will remove all the opaque LSAs that the application registered. Since +the opaque LSAs are flooded to other routers, we will see the opaque LSAs in +all routers according to the flooding scope of the opaque LSA. We have a very simple demo setup, just two routers connected with an ATM -point-to-point link. Start the modified OSPF daemons on two adjacent -routers. First run on msr2: +point-to-point link. Start the modified OSPF daemons on two adjacent routers. +First run on msr2: -:: +.. code-block:: console - > msr2:/home/keller/ospfapi/zebra/ospfd# ./ospfd -f /usr/local/etc/ospfd.conf + # ./ospfd --apiserver -f /usr/local/etc/ospfd.conf And on the neighboring router msr3: -:: +.. code-block:: console - > msr3:/home/keller/ospfapi/zebra/ospfd# ./ospfd -f /usr/local/etc/ospfd.conf + # ./ospfd --apiserver -f /usr/local/etc/ospfd.conf Now the two routers form adjacency and start exchanging their databases. Looking at the OSPF daemon of msr2 (or msr3), you see this: -:: +.. code-block:: console - ospfd> show ip ospf database + ospfd> show ip ospf database - OSPF Router with ID (10.0.0.1) + OSPF Router with ID (10.0.0.1) - Router Link States (Area 0.0.0.1) + Router Link States (Area 0.0.0.1) - Link ID ADV Router Age Seq# CkSum Link count - 10.0.0.1 10.0.0.1 55 0x80000003 0xc62f 2 - 10.0.0.2 10.0.0.2 55 0x80000003 0xe3e4 3 + Link ID ADV Router Age Seq# CkSum Link count + 10.0.0.1 10.0.0.1 55 0x80000003 0xc62f 2 + 10.0.0.2 10.0.0.2 55 0x80000003 0xe3e4 3 - Net Link States (Area 0.0.0.1) + Net Link States (Area 0.0.0.1) - Link ID ADV Router Age Seq# CkSum - 10.0.0.2 10.0.0.2 60 0x80000001 0x5fcb + Link ID ADV Router Age Seq# CkSum + 10.0.0.2 10.0.0.2 60 0x80000001 0x5fcb Now we start the sample main application that originates an opaque LSA. -:: +.. code-block:: console - > cd ospfapi/apiclient - > ./main msr2 10 250 20 0.0.0.0 0.0.0.1 + # cd ospfapi/apiclient + # ./main msr2 10 250 20 0.0.0.0 0.0.0.1 -This originates an opaque LSA of type 10 (area local), with opaque type -250 (experimental), opaque id of 20 (chosen arbitrarily), interface -address 0.0.0.0 (which is used only for opaque LSAs type 9), and area -0.0.0.1 +This originates an opaque LSA of type 10 (area local), with opaque type 250 +(experimental), opaque id of 20 (chosen arbitrarily), interface address 0.0.0.0 +(which is used only for opaque LSAs type 9), and area 0.0.0.1 Again looking at the OSPF database you see: -:: +.. code-block:: console - ospfd> show ip ospf database + ospfd> show ip ospf database - OSPF Router with ID (10.0.0.1) + OSPF Router with ID (10.0.0.1) - Router Link States (Area 0.0.0.1) + Router Link States (Area 0.0.0.1) - Link ID ADV Router Age Seq# CkSum Link count - 10.0.0.1 10.0.0.1 437 0x80000003 0xc62f 2 - 10.0.0.2 10.0.0.2 437 0x80000003 0xe3e4 3 + Link ID ADV Router Age Seq# CkSum Link count + 10.0.0.1 10.0.0.1 437 0x80000003 0xc62f 2 + 10.0.0.2 10.0.0.2 437 0x80000003 0xe3e4 3 - Net Link States (Area 0.0.0.1) + Net Link States (Area 0.0.0.1) - Link ID ADV Router Age Seq# CkSum - 10.0.0.2 10.0.0.2 442 0x80000001 0x5fcb + Link ID ADV Router Age Seq# CkSum + 10.0.0.2 10.0.0.2 442 0x80000001 0x5fcb - Area-Local Opaque-LSA (Area 0.0.0.1) + Area-Local Opaque-LSA (Area 0.0.0.1) - Opaque-Type/Id ADV Router Age Seq# CkSum - 250.0.0.20 10.0.0.1 0 0x80000001 0x58a6 <=== opaque LSA + Opaque-Type/Id ADV Router Age Seq# CkSum + 250.0.0.20 10.0.0.1 0 0x80000001 0x58a6 <=== opaque LSA You can take a closer look at this opaque LSA: -:: +.. code-block:: console - ospfd> show ip ospf database opaque-area + ospfd> show ip ospf database opaque-area - OSPF Router with ID (10.0.0.1) + OSPF Router with ID (10.0.0.1) - Area-Local Opaque-LSA (Area 0.0.0.1) + Area-Local Opaque-LSA (Area 0.0.0.1) - LS age: 4 - Options: 66 - LS Type: Area-Local Opaque-LSA - Link State ID: 250.0.0.20 (Area-Local Opaque-Type/ID) - Advertising Router: 10.0.0.1 - LS Seq Number: 80000001 - Checksum: 0x58a6 - Length: 24 - Opaque-Type 250 (Private/Experimental) - Opaque-ID 0x14 - Opaque-Info: 4 octets of data - Added using OSPF API: 4 octets of opaque data - Opaque data: 1 0 0 0 <==== counter is 1 + LS age: 4 + Options: 66 + LS Type: Area-Local Opaque-LSA + Link State ID: 250.0.0.20 (Area-Local Opaque-Type/ID) + Advertising Router: 10.0.0.1 + LS Seq Number: 80000001 + Checksum: 0x58a6 + Length: 24 + Opaque-Type 250 (Private/Experimental) + Opaque-ID 0x14 + Opaque-Info: 4 octets of data + Added using OSPF API: 4 octets of opaque data + Opaque data: 1 0 0 0 <==== counter is 1 -Note that the main application updates the opaque LSA after 10 seconds, -then it looks as follows: +Note that the main application updates the opaque LSA after 10 seconds, then it +looks as follows: -:: +.. code-block:: console - ospfd> show ip ospf database opaque-area + ospfd> show ip ospf database opaque-area - OSPF Router with ID (10.0.0.1) + OSPF Router with ID (10.0.0.1) - Area-Local Opaque-LSA (Area 0.0.0.1) + Area-Local Opaque-LSA (Area 0.0.0.1) - LS age: 1 - Options: 66 - LS Type: Area-Local Opaque-LSA - Link State ID: 250.0.0.20 (Area-Local Opaque-Type/ID) - Advertising Router: 10.0.0.1 - LS Seq Number: 80000002 - Checksum: 0x59a3 - Length: 24 - Opaque-Type 250 (Private/Experimental) - Opaque-ID 0x14 - Opaque-Info: 4 octets of data - Added using OSPF API: 4 octets of opaque data - Opaque data: 2 0 0 0 <==== counter is now 2 + LS age: 1 + Options: 66 + LS Type: Area-Local Opaque-LSA + Link State ID: 250.0.0.20 (Area-Local Opaque-Type/ID) + Advertising Router: 10.0.0.1 + LS Seq Number: 80000002 + Checksum: 0x59a3 + Length: 24 + Opaque-Type 250 (Private/Experimental) + Opaque-ID 0x14 + Opaque-Info: 4 octets of data + Added using OSPF API: 4 octets of opaque data + Opaque data: 2 0 0 0 <==== counter is now 2 -Note that the payload of the opaque LSA has changed as you can see -above. +Note that the payload of the opaque LSA has changed as you can see above. -Then, again after another 20 seconds, the opaque LSA is flushed from the -LSDB. +Then, again after another 20 seconds, the opaque LSA is flushed from the LSDB. Important note: ^^^^^^^^^^^^^^^ In order to originate an opaque LSA, there must be at least one active -opaque-capable neighbor. Thus, you cannot originate opaque LSAs of no -neighbors are present. If you try to originate even so no neighbor is -ready, you will receive a not ready error message. The reason for this -restriction is that it might be possible that some routers have an -identical opaque LSA from a previous origination in their LSDB that -unfortunately could not be flushed due to a crash, and now if the router -comes up again and starts originating a new opaque LSA, the new opaque -LSA is considered older since it has a lower sequence number and is -ignored by other routers (that consider the stalled opaque LSA as more -recent). However, if the originating router first synchronizes the -database before originating opaque LSAs, it will detect the older opaque -LSA and can flush it first. +opaque-capable neighbor. Thus, you cannot originate opaque LSAs if no neighbors +are present. If you try to originate when no neighbors are ready, you will +receive a not ready error message. The reason for this restriction is that it +might be possible that some routers have an identical opaque LSA from a +previous origination in their LSDB that unfortunately could not be flushed due +to a crash, and now if the router comes up again and starts originating a new +opaque LSA, the new opaque LSA is considered older since it has a lower +sequence number and is ignored by other routers (that consider the stalled +opaque LSA as more recent). However, if the originating router first +synchronizes the database before originating opaque LSAs, it will detect the +older opaque LSA and can flush it first. Protocol and Message Formats ---------------------------- -If you are developing your own client application and you don't want to -make use of the client library (due to the GNU license restriction or -whatever reason), you can implement your own client-side message -handling. The OSPF API uses two connections between the client and the -OSPF API server: One connection is used for a synchronous request /reply -protocol and another connection is used for asynchronous notifications -(e.g., LSA update, neighbor status change). +If you are developing your own client application and you don't want to make +use of the client library (due to the GNU license restriction or whatever +reason), you can implement your own client-side message handling. The OSPF API +uses two connections between the client and the OSPF API server: One connection +is used for a synchronous request /reply protocol and another connection is +used for asynchronous notifications (e.g., LSA update, neighbor status change). Each message begins with the following header: @@ -326,8 +320,8 @@ The synchronous requests and replies have the following message formats: image -The origin field allows to select according to the following types of -origins: +The origin field allows origin-based filtering using the following origin +types: +-------------------------+---------+ | Origin | Value | @@ -339,7 +333,7 @@ origins: | ANY\_ORIGIN | 2 | +-------------------------+---------+ -The reply message has on of the following error codes: +The reply message has one of the following error codes: +--------------------------+---------+ | Error code | Value | @@ -372,16 +366,18 @@ The asynchronous notifications have the following message formats: image + +.. Do not delete these acknowledgements! + Original Acknowledgments from Ralph Keller ------------------------------------------ -I would like to thank Masahiko Endo, the author of the opaque LSA -extension module, for his great support. His wonderful ASCII graphs -explaining the internal workings of this code, and his invaluable input -proved to be crucial in designing a useful API for accessing the link -state database of the OSPF daemon. Once, he even decided to take the -plane from Tokyo to Zurich so that we could actually meet and have -face-to-face discussions, which was a lot of fun. Clearly, without -Masahiko no API would ever be completed. I also would like to thank -Daniel Bauer who wrote an opaque LSA implementation too and was willing +I would like to thank Masahiko Endo, the author of the opaque LSA extension +module, for his great support. His wonderful ASCII graphs explaining the +internal workings of this code, and his invaluable input proved to be crucial +in designing a useful API for accessing the link state database of the OSPF +daemon. Once, he even decided to take the plane from Tokyo to Zurich so that we +could actually meet and have face-to-face discussions, which was a lot of fun. +Clearly, without Masahiko no API would ever be completed. I also would like to +thank Daniel Bauer who wrote an opaque LSA implementation too and was willing to test the OSPF API code in one of his projects. diff --git a/doc/developer/subdir.am b/doc/developer/subdir.am index 7ae48881ab..479aa04d59 100644 --- a/doc/developer/subdir.am +++ b/doc/developer/subdir.am @@ -30,6 +30,7 @@ dev_RSTFILES = \ doc/developer/include-compile.rst \ doc/developer/index.rst \ doc/developer/library.rst \ + doc/developer/lists.rst \ doc/developer/logging.rst \ doc/developer/maintainer-release-build.rst \ doc/developer/memtypes.rst \ |