diff options
Diffstat (limited to 'doc/developer')
| -rw-r--r-- | doc/developer/building.rst | 1 | ||||
| -rw-r--r-- | doc/developer/cross-compiling.rst | 326 | ||||
| -rw-r--r-- | doc/developer/index.rst | 2 | ||||
| -rw-r--r-- | doc/developer/library.rst | 3 | ||||
| -rw-r--r-- | doc/developer/link-state.rst | 314 | ||||
| -rw-r--r-- | doc/developer/logging.rst | 2 | ||||
| -rw-r--r-- | doc/developer/lua.rst | 65 | ||||
| -rw-r--r-- | doc/developer/ospf-sr.rst | 66 | ||||
| -rw-r--r-- | doc/developer/path-internals-daemon.rst | 115 | ||||
| -rw-r--r-- | doc/developer/path-internals-pcep.rst | 193 | ||||
| -rw-r--r-- | doc/developer/path-internals.rst | 11 | ||||
| -rw-r--r-- | doc/developer/path.rst | 11 | ||||
| -rw-r--r-- | doc/developer/scripting.rst | 433 | ||||
| -rw-r--r-- | doc/developer/subdir.am | 10 | ||||
| -rw-r--r-- | doc/developer/topotests-markers.rst | 114 | ||||
| -rw-r--r-- | doc/developer/topotests.rst | 29 | ||||
| -rw-r--r-- | doc/developer/tracing.rst | 27 | ||||
| -rw-r--r-- | doc/developer/workflow.rst | 3 | ||||
| -rw-r--r-- | doc/developer/xrefs.rst | 170 |
19 files changed, 1826 insertions, 69 deletions
diff --git a/doc/developer/building.rst b/doc/developer/building.rst index a6cd545872..c687ba8dc8 100644 --- a/doc/developer/building.rst +++ b/doc/developer/building.rst @@ -29,3 +29,4 @@ Building FRR building-frr-for-ubuntu2004 building-frr-for-archlinux building-docker + cross-compiling diff --git a/doc/developer/cross-compiling.rst b/doc/developer/cross-compiling.rst new file mode 100644 index 0000000000..339e00c921 --- /dev/null +++ b/doc/developer/cross-compiling.rst @@ -0,0 +1,326 @@ +Cross-Compiling +=============== + +FRR is capable of being cross-compiled to a number of different architectures. +With an adequate toolchain this process is fairly straightforward, though one +must exercise caution to validate this toolchain's correctness before attempting +to compile FRR or its dependencies; small oversights in the construction of the +build tools may lead to problems which quickly become difficult to diagnose. + +Toolchain Preliminary +--------------------- + +The first step to cross-compiling any program is to identify the system which +the program (FRR) will run on. From here on this will be called the "host" +machine, following autotools' convention, while the machine building FRR will be +called the "build" machine. The toolchain will of course be installed onto the +build machine and be leveraged to build FRR for the host machine to run. + +.. note:: + + The build machine used while writing this guide was ``x86_64-pc-linux-gnu`` + and the target machine was ``arm-linux-gnueabihf`` (a Raspberry Pi 3B+). + Replace this with your targeted tuple below if you plan on running the + commands from this guide: + + .. code-block:: shell + + export HOST_ARCH="arm-linux-gnueabihf" + + For your given target, the build system's OS may have some support for + building cross compilers natively, or may even offer binary toolchains built + upstream for the target architecture. Check your package manager or OS + documentation before committing to building a toolchain from scratch. + +This guide will not detail *how* to build a cross-compiling toolchain but +will instead assume one already exists and is installed on the build system. +The methods for building the toolchain itself may differ between operating +systems so consult the OS documentation for any particulars regarding +cross-compilers. The OSDev wiki has a `pleasant tutorial`_ on cross-compiling in +the context of operating system development which bootstraps from only the +native GCC and binutils on the build machine. This may be useful if the build +machine's OS does not offer existing tools to build a cross-compiler targeting +the host. + +.. _pleasant tutorial: https://wiki.osdev.org/GCC_Cross-Compiler + +This guide will also not demonstrate how to build all of FRR's dependencies for the +target architecture. Instead, general instructions for using a cross-compiling +toolchain to compile packages using CMake, Autotools, and Makefiles are +provided; these three cases apply to almost all FRR dependencies. + +.. _glibc mismatch: + +.. warning:: + + Ensure the versions and implementations of the C standard library (glibc or + what have you) match on the host and the build toolchain. ``ldd --version`` + will help you here. Upgrade one or the other if the they do not match. + +Testing the Toolchain +--------------------- + +Before any cross-compilation begins it would be prudent to test the new +toolchain by writing, compiling and linking a simple program. + +.. code-block:: shell + + # A small program + cat > nothing.c <<EOF + int main() { return 0; } + EOF + + # Build and link with the cross-compiler + ${HOST_ARCH}-gcc -o nothing nothing.c + + # Inspect the resulting binary, results may vary + file ./nothing + + # nothing: ELF 32-bit LSB pie executable, ARM, EABI5 version 1 (SYSV), + # dynamically linked, interpreter /lib/ld-linux-armhf.so.3, + # for GNU/Linux 3.2.0, not stripped + +If this produced no errors then the installed toolchain is probably ready to +start compiling the build dependencies and eventually FRR itself. There still +may be lurking issues but fundamentally the toolchain can produce binaries and +that's good enough to start working with it. + +.. warning:: + + If any errors occurred during the previous functional test please look back + and address them before moving on; this indicates your cross-compiling + toolchain is *not* in a position to build FRR or its dependencies. Even if + everything was fine, keep in mind that many errors from here on *may still + be related* to your toolchain (e.g. libstdc++.so or other components) and this + small test is not a guarantee of complete toolchain coherence. + +Cross-compiling Dependencies +---------------------------- + +When compiling FRR it is necessary to compile some of its dependencies alongside +it on the build machine. This is so symbols from the shared libraries (which +will be loaded at run-time on the host machine) can be linked to the FRR +binaries at compile time; additionally, headers for these libraries are needed +during the compile stage for a successful build. + +Sysroot Overview +^^^^^^^^^^^^^^^^ + +All build dependencies should be installed into a "root" directory on the build +computer, hereafter called the "sysroot". This directory will be prefixed to +paths while searching for requisite libraries and headers during the build +process. Often this may be set via a ``--prefix`` flag when building the +dependent packages, meaning a ``make install`` will copy compiled libraries into +(e.g.) ``/usr/${HOST_ARCH}/usr``. + +If the toolchain was built on the build machine then there is likely already a +sysroot where those tools and standard libraries were installed; it may be +helpful to use that directory as the sysroot for this build as well. + +Basic Workflow +^^^^^^^^^^^^^^ + +Before compiling or building any dependencies, make note of which daemons are +being targeted and which libraries will be needed. Not all dependencies are +necessary if only building with a subset of the daemons. + +The following workflow will compile and install any libraries which can be built +with Autotools. The resultant library will be installed into the sysroot +``/usr/${HOST_ARCH}``. + +.. code-block:: shell + + ./configure \ + CC=${HOST_ARCH}-gcc \ + CXX=${HOST_ARCH}-g++ \ + --build=${HOST_ARCH} \ + --prefix=/usr/${HOST_ARCH} + make + make install + +Some libraries like ``json-c`` and ``libyang`` are packaged with CMake and can +be built and installed generally like: + +.. code-block:: shell + + mkdir build + cd build + CC=${HOST_ARCH}-gcc \ + CXX=${HOST_ARCH}-g++ \ + cmake \ + -DCMAKE_INSTALL_PREFIX=/usr/${HOST_ARCH} \ + .. + make + make install + +For programs with only a Makefile (e.g. ``libcap``) the process may look still a +little different: + +.. code-block:: shell + + CC=${HOST_ARCH}-gcc make + make install DESTDIR=/usr/${HOST_ARCH} + +These three workflows should handle the bulk of building and installing the +build-time dependencies for FRR. Verify that the installed files are being +placed correctly into the sysroot and were actually built using the +cross-compile toolchain, not by the native toolchain by accident. + +Dependency Notes +^^^^^^^^^^^^^^^^ + +There are a lot of things that can go wrong during a cross-compilation. Some of +the more common errors and a few special considerations are collected below for +reference. + +libyang +""""""" + +``-DENABLE_LYD_PRIV=ON`` should be provided during the CMake step. + +Ensure also that the version of ``libyang`` being installed corresponds to the +version required by the targeted FRR version. + +gRPC +"""" + +This piece is requisite only if the ``--enable-grpc`` flag will be passed +later on to FRR. One may get burned when compiling gRPC if the ``protoc`` +version on the build machine differs from the version of ``protoc`` being linked +to during a gRPC build. The error messages from this defect look like: + +.. code-block:: terminal + + gens/src/proto/grpc/channelz/channelz.pb.h: In member function ‘void grpc::channelz::v1::ServerRef::set_name(const char*, size_t)’: + gens/src/proto/grpc/channelz/channelz.pb.h:9127:64: error: ‘EmptyDefault’ is not a member of ‘google::protobuf::internal::ArenaStringPtr’ + 9127 | name_.Set(::PROTOBUF_NAMESPACE_ID::internal::ArenaStringPtr::EmptyDefault{}, ::std::string( + +This happens because protocol buffer code generation uses ``protoc`` to create +classes with different getters and setters corresponding to the protobuf data +defined by the source tree's ``.proto`` files. Clearly the cross-compiled +``protoc`` cannot be used for this code generation because that binary is built +for a different CPU. + +The solution is to install matching versions of native and cross-compiled +protocol buffers; this way the native binary will generate code and the +cross-compiled library will be linked to by gRPC and these versions will not +disagree. + +---- + +The ``-latomic`` linker flag may also be necessary here if using ``libstdc++`` +since GCC's C++11 implementation makes library calls in certain cases for +``<atomic>`` so ``-latomic`` cannot be assumed. + +Cross-compiling FRR Itself +-------------------------- + +With all the necessary libraries cross-compiled and installed into the sysroot, +the last thing to actually build is FRR itself: + +.. code-block:: shell + + # Clone and bootstrap the build + git clone 'https://github.com/FRRouting/frr.git' + # (e.g.) git checkout stable/7.5 + ./bootstrap.sh + + # Build clippy using the native toolchain + mkdir build-clippy + cd build-clippy + ../configure --enable-clippy-only + make clippy-only + cd .. + + # Next, configure FRR and use the clippy we just built + ./configure \ + CC=${HOST_ARCH}-gcc \ + CXX=${HOST_ARCH}-g++ \ + --host=${HOST_ARCH} \ + --with-sysroot=/usr/${HOST_ARCH} \ + --with-clippy=./build-clippy/lib/clippy \ + --sysconfdir=/etc/frr \ + --sbindir="\${prefix}/lib/frr" \ + --localstatedir=/var/run/frr \ + --prefix=/usr \ + --enable-user=frr \ + --enable-group=frr \ + --enable-vty-group=frrvty \ + --disable-doc \ + --enable-grpc + + # Send it + make + +Installation to Host Machine +---------------------------- + +If no errors were observed during the previous steps it is safe to ``make +install`` FRR into its own directory. + +.. code-block:: shell + + # Install FRR its own "sysroot" + make install DESTDIR=/some/path/to/sysroot + +After running the above command, FRR binaries, modules and example configuration +files will be installed into some path on the build machine. The directory +will have folders like ``/usr`` and ``/etc``; this "root" should now be copied +to the host and installed on top of the root directory there. + +.. code-block:: shell + + # Tar this sysroot (preserving permissions) + tar -C /some/path/to/sysroot -cpvf frr-${HOST_ARCH}.tar . + + # Transfer tar file to host machine + scp frr-${HOST_ARCH}.tar me@host-machine: + + # Overlay the tarred sysroot on top of the host machine's root + ssh me@host-machine <<-EOF + # May need to elevate permissions here + tar -C / -xpvf frr-${HOST_ARCH}.tar.gz . + EOF + +Now FRR should be installed just as if ``make install`` had been run on the host +machine. Create configuration files and assign permissions as needed. Lastly, +ensure the correct users and groups exist for FRR on the host machine. + +Troubleshooting +--------------- + +Even when every precaution has been taken some things may still go wrong! This +section details some common runtime problems. + +Mismatched Libraries +^^^^^^^^^^^^^^^^^^^^ + +If you see something like this after installing on the host: + +.. code-block:: console + + /usr/lib/frr/zebra: error while loading shared libraries: libyang.so.1: cannot open shared object file: No such file or directory + +... at least one of FRR's dependencies which was linked to the binary earlier is +not available on the host OS. Even if it has been installed the host +repository's version may lag what is needed for more recent FRR builds (this is +likely to happen with YANG at the moment). + +If the matching library is not available from the host OS package manager it may +be possible to compile them using the same toolchain used to compile FRR. The +library may have already been built earlier when compiling FRR on the build +machine, in which case it may be as simple as following the same workflow laid +out during the `Installation to Host Machine`_. + +Mismatched Glibc Versions +^^^^^^^^^^^^^^^^^^^^^^^^^ + +The version and implementation of the C standard library must match on both the +host and build toolchain. The error corresponding to this misconfiguration will +look like: + +.. code-block:: console + + /usr/lib/frr/zebra: /lib/${HOST_ARCH}/libc.so.6: version `GLIBC_2.32' not found (required by /usr/lib/libfrr.so.0) + +See the earlier warning about preventing a `glibc mismatch`_. diff --git a/doc/developer/index.rst b/doc/developer/index.rst index 5a7da806ff..8e7913419f 100644 --- a/doc/developer/index.rst +++ b/doc/developer/index.rst @@ -18,3 +18,5 @@ FRRouting Developer's Guide ospf zebra vtysh + path + link-state diff --git a/doc/developer/library.rst b/doc/developer/library.rst index 3d5c6a2a15..2e36c253ea 100644 --- a/doc/developer/library.rst +++ b/doc/developer/library.rst @@ -11,10 +11,11 @@ Library Facilities (libfrr) rcu lists logging + xrefs locking hooks cli modules - lua + scripting diff --git a/doc/developer/link-state.rst b/doc/developer/link-state.rst new file mode 100644 index 0000000000..f1fc52966b --- /dev/null +++ b/doc/developer/link-state.rst @@ -0,0 +1,314 @@ +Link State API Documentation +============================ + +Introduction +------------ + +The Link State (LS) API aims to provide a set of structures and functions to +build and manage a Traffic Engineering Database for the various FRR daemons. +This API has been designed for several use cases: + +- BGP Link State (BGP-LS): where BGP protocol need to collect the link state + information from the routing daemons (IS-IS and/or OSPF) to implement RFC7572 +- Path Computation Element (PCE): where path computation algorithms are based + on Traffic Engineering Database +- ReSerVation Protocol (RSVP): where signaling need to know the Traffic + Engineering topology of the network in order to determine the path of + RSVP tunnels + +Architecture +------------ + +The main requirements from the various uses cases are as follow: + +- Provides a set of data model and function to ease Link State information + manipulation (storage, serialize, parse ...) +- Ease and normalize Link State information exchange between FRR daemons +- Provides database structure for Traffic Engineering Database (TED) + +To ease Link State understanding, FRR daemons have been classified into two +categories: + +- **Consumer**: Daemons that consume Link State information e.g. BGPd +- **Producer**: Daemons that are able to collect Link State information and + send them to consumer daemons e.g. OSPFd IS-ISd + +Zebra daemon, and more precisely, the ZAPI message is used to convey the Link +State information between *producer* and *consumer*, but, Zebra acts as a +simple pass through and does not store any Link State information. A new ZAPI +**Opaque** message has been design for that purpose. + +Each consumer and producer daemons are free to store or not Link State data and +organise the information following the Traffic Engineering Database model +provided by the API or any other data structure e.g. Hash, RB-tree ... + +Link State API +-------------- + +This is the low level API that allows any daemons manipulate the Link State +elements that are stored in the Link State Database. + +Data structures +^^^^^^^^^^^^^^^ + +3 types of Link State structure have been defined: + +.. c:type:: struct ls_node + + that groups all information related to a node + +.. c:type:: struct ls_attributes + + that groups all information related to a link + +.. c:type:: struct ls_prefix + + that groups all information related to a prefix + +These 3 types of structures are those handled by BGP-LS (see RFC7752) and +suitable to describe a Traffic Engineering topology. + +Each structure, in addition to the specific parameters, embed the node +identifier which advertises the Link State and a bit mask as flags to +indicates which parameters are valid i.e. for which the value is valid and +corresponds to a Link State information conveyed by the routing protocol. + +.. c:type:: struct ls_node_id + + defines the Node identifier as router ID IPv4 address plus the area ID for + OSPF or the ISO System ID plus the IS-IS level for IS-IS. + +Functions +^^^^^^^^^ + +A set of functions is provided to create, delete and compare Link State Node: + +.. c:function:: struct ls_node *ls_node_new(struct ls_node_id adv, struct in_addr router_id, struct in6_addr router6_id) +.. c:function:: voidls_node_del(struct ls_node *node) +.. c:function:: int ls_node_same(struct ls_node *n1, struct ls_node *n2) + +and Link State Attributes: + +.. c:function:: struct ls_attributes *ls_attributes_new(struct ls_node_id adv, struct in_addr local, struct in6_addr local6, uint32_t local_id) +.. c:function:: void ls_attributes_del(struct ls_attributes *attr) +.. c:function:: int ls_attributes_same(struct ls_attributes *a1, struct ls_attributes *a2) + +The low level API doesn't provide any particular functions for the Link State +Prefix structure as this latter is simpler to manipulate. + +Link State TED +-------------- + +This is the high level API that provides functions to create, update, delete a +Link State Database to from a Traffic Engineering Database (TED). + +Data Structures +^^^^^^^^^^^^^^^ + +The Traffic Engineering is modeled as a Graph in order to ease Path Computation +algorithm implementation. Denoted **G(V, E)**, a graph is composed by a list of +**Vertices (V)** which represents the network Node and a list of **Edges (E)** +which represents Link. An additional list of **prefixes (P)** is also added and +also attached to the *Vertex (V)* which advertise it. + +*Vertex (V)* contains the list of outgoing *Edges (E)* that connect this Vertex +with its direct neighbors and the list of incoming *Edges (E)* that connect +the direct neighbors to this Vertex. Indeed, the *Edge (E)* is unidirectional, +thus, it is necessary to add 2 Edges to model a bidirectional relation between +2 Vertices. Finally, the *Vertex (V)* contains a pointer to the corresponding +Link State Node. + +*Edge (E)* contains the source and destination Vertex that this Edge +is connecting and a pointer to the corresponding Link State Attributes. + +A unique Key is used to identify both Vertices and Edges within the Graph. + + +:: + + -------------- --------------------------- -------------- + | Connected |---->| Connected Edge Va to Vb |--->| Connected | + --->| Vertex | --------------------------- | Vertex |----> + | | | | + | - Key (Va) | | - Key (Vb) | + <---| - Vertex | --------------------------- | - Vertex |<---- + | |<----| Connected Edge Vb to Va |<---| | + -------------- --------------------------- -------------- + + +4 data structures have been defined to implement the Graph model: + +.. c:type:: struct ls_vertex +.. c:type:: struct ls_edge +.. c:type:: struct ls_prefix +.. c:type:: struct ls_ted + + +Functions +^^^^^^^^^ + +.. c:function:: struct ls_vertex *ls_vertex_add(struct ls_ted *ted, struct ls_node *node) +.. c:function:: struct ls_vertex *ls_vertex_update(struct ls_ted *ted, struct ls_node *node) +.. c:function:: void ls_vertex_del(struct ls_ted *ted, struct ls_vertex *vertex) +.. c:function:: struct ls_vertex *ls_find_vertex_by_key(struct ls_ted *ted, const uint64_t key) +.. c:function:: struct ls_vertex *ls_find_vertex_by_id(struct ls_ted *ted, struct ls_node_id id) +.. c:function:: int ls_vertex_same(struct ls_vertex *v1, struct ls_vertex *v2) + +.. c:function:: struct ls_edge *ls_edge_add(struct ls_ted *ted, struct ls_attributes *attributes) +.. c:function:: struct ls_edge *ls_edge_update(struct ls_ted *ted, struct ls_attributes *attributes) +.. c:function:: void ls_edge_del(struct ls_ted *ted, struct ls_edge *edge) +.. c:function:: struct ls_edge *ls_find_edge_by_key(struct ls_ted *ted, const uint64_t key) +.. c:function:: struct ls_edge *ls_find_edge_by_source(struct ls_ted *ted, struct ls_attributes *attributes); +.. c:function:: struct ls_edge *ls_find_edge_by_destination(struct ls_ted *ted, struct ls_attributes *attributes); + +.. c:function:: struct ls_subnet *ls_subnet_add(struct ls_ted *ted, struct ls_prefix *pref) +.. c:function:: void ls_subnet_del(struct ls_ted *ted, struct ls_subnet *subnet) +.. c:function:: struct ls_subnet *ls_find_subnet(struct ls_ted *ted, const struct prefix prefix) + +.. c:function:: struct ls_ted *ls_ted_new(const uint32_t key, char *name, uint32_t asn) +.. c:function:: void ls_ted_del(struct ls_ted *ted) +.. c:function:: void ls_connect_vertices(struct ls_vertex *src, struct ls_vertex *dst, struct ls_edge *edge) +.. c:function:: void ls_connect(struct ls_vertex *vertex, struct ls_edge *edge, bool source) +.. c:function:: void ls_disconnect(struct ls_vertex *vertex, struct ls_edge *edge, bool source) +.. c:function:: void ls_disconnect_edge(struct ls_edge *edge) + + +Link State Messages +------------------- + +This part of the API provides functions and data structure to ease the +communication between the *Producer* and *Consumer* daemons. + +Communications principles +^^^^^^^^^^^^^^^^^^^^^^^^^ + +Recent ZAPI Opaque Message is used to exchange Link State data between daemons. +For that purpose, Link State API provides new functions to serialize and parse +Link State information through the ZAPI Opaque message. A dedicated flag, +named ZAPI_OPAQUE_FLAG_UNICAST, allows daemons to send a unicast or a multicast +Opaque message and is used as follow for the Link State exchange: + +- Multicast: To send data update to all daemons that have subscribed to the + Link State Update message +- Unicast: To send initial Link State information from a particular daemon. All + data are send only to the daemon that request Link State Synchronisatio + +Figure 1 below, illustrates the ZAPI Opaque message exchange between a +*Producer* (an IGP like OSPF or IS-IS) and a *Consumer* (e.g. BGP). The +message sequences are as follows: + +- First, both *Producer* and *Consumer* must register to their respective ZAPI + Opaque Message. **Link State Sync** for the *Producer* in order to receive + Database synchronisation request from a *Consumer*. **Link State Update** for + the *Consumer* in order to received any Link State update from a *Producer*. + These register messages are stored by Zebra to determine to which daemon it + should redistribute the ZAPI messages it receives. +- Then, the *Consumer* sends a **Link State Synchronistation** request with the + Multicast method in order to receive the complete Link State Database from a + *Producer*. ZEBRA daemon forwards this message to any *Producer* daemons that + previously registered to this message. If no *Producer* has yet registered, + the request is lost. Thus, if the *Consumer* receives no response whithin a + given timer, it means that no *Producer* are available right now. So, the + *Consumer* must send the same request until it receives a Link State Database + Synchronistation message. This behaviour is necessary as we can't control in + which order daemons are started. It is up to the *Consumer* daemon to fix the + timeout and the number of retry. +- When a *Producer* receives a **Link State Synchronisation** request, it + starts sending all elements of its own Link State Database through the + **Link State Database Synchronisation** message. These messages are send with + the Unicast method to avoid flooding other daemons with these elements. ZEBRA + layer ensures to forward the message to the right daemon. +- When a *Producer* update its Link State Database, it automatically sends a + **Link State Update** message with the Multicast method. In turn, ZEBRA + daemon forwards the message to all *Consumer* daemons that previously + registered to this message. if no daemon is registered, the message is lost. +- A daemon could unregister from the ZAPI Opaque message registry at any time. + In this case, the ZEBRA daemon stops to forward any messages it receives to + this daemon, even if it was previously converns. + +:: + + IGP ZEBRA Consumer + (OSPF/IS-IS) (ZAPI Opaque Thread) (e.g. BGP) + | | | \ + | | Register LS Update | | + | |<----------------------------| Register Phase + | | | | + | | Request LS Sync | | + | |<----------------------------| | + : : : A | + | Register LS Sync | | | | + |----------------------------->| | | / + : : : |TimeOut + : : : | + | | | | + | | Request LS Sync | v \ + | Request LS Sync |<----------------------------| | + |<-----------------------------| | Synchronistation + | LS DB Sync | | Phase + |----------------------------->| LS DB Sync | | + | |---------------------------->| | + | LS DB Sync (cont'd) | | | + |----------------------------->| LS DB Sync (cont'd) | | + | . |---------------------------->| | + | . | . | | + | . | . | | + | LS DB Sync (end) | . | | + |----------------------------->| LS DB Sync (end) | | + | |---------------------------->| | + | | | / + : : : + : : : + | LS Update | | \ + |----------------------------->| LS Update | | + | |---------------------------->| Update Phase + | | | | + : : : / + : : : + | | | \ + | | Unregister LS Update | | + | |<----------------------------| Deregister Phase + | | | | + | LS Update | | | + |----------------------------->| | | + | | | / + | | | + + Figure 1: Link State messages exchange + + +Data Structures +^^^^^^^^^^^^^^^ + +The Link State Message is defined to convey Link State parameters from +the routing protocol (OSPF or IS-IS) to other daemons e.g. BGP. + +.. c:type:: struct ls_message + +The structure is composed of: + +- Event of the message: + + - Sync: Send the whole LS DB following a request + - Add: Send the a new Link State element + - Update: Send an update of an existing Link State element + - Delete: Indicate that the given Link State element is removed + +- Type of Link State element: Node, Attribute or Prefix +- Remote node id when known +- Data: Node, Attributes or Prefix + +A Link State Message can carry only one Link State Element (Node, Attributes +of Prefix) at once, and only one Link State Message is sent through ZAPI +Opaque Link State type at once. + +Functions +^^^^^^^^^ + +.. c:function:: struct ls_message *ls_parse_msg(struct stream *s) +.. c:function:: int ls_send_msg(struct zclient *zclient, struct ls_message *msg, struct zapi_opaque_reg_info *dst) +.. c:function:: struct ls_message *ls_vertex2msg(struct ls_message *msg, struct ls_vertex *vertex) +.. c:function:: struct ls_message *ls_edge2msg(struct ls_message *msg, struct ls_edge *edge) +.. c:function:: struct ls_message *ls_subnet2msg(struct ls_message *msg, struct ls_subnet *subnet) +.. c:function:: int ls_sync_ted(struct ls_ted *ted, struct zclient *zclient, struct zapi_opaque_reg_info *dst) + diff --git a/doc/developer/logging.rst b/doc/developer/logging.rst index 2f2444373c..cf3aa8d17f 100644 --- a/doc/developer/logging.rst +++ b/doc/developer/logging.rst @@ -83,7 +83,7 @@ Extensions +-----------+--------------------------+----------------------------------------------+ | ``%pNHs`` | ``struct nexthop *`` | ``1.2.3.4 if 15`` | +-----------+--------------------------+----------------------------------------------+ -| ``%pFX`` + ``struct bgp_dest *`` | ``fe80::1234/64`` available in BGP only | +| ``%pFX`` | ``struct bgp_dest *`` | ``fe80::1234/64`` (available in BGP only) | +-----------+--------------------------+----------------------------------------------+ Printf features like field lengths can be used normally with these extensions, diff --git a/doc/developer/lua.rst b/doc/developer/lua.rst deleted file mode 100644 index 3315c31ad7..0000000000 --- a/doc/developer/lua.rst +++ /dev/null @@ -1,65 +0,0 @@ -.. _lua: - -Lua -=== - -Lua is currently experimental within FRR and has very limited -support. If you would like to compile FRR with Lua you must -follow these steps: - -1. Installation of Relevant Libraries - - .. code-block:: shell - - apt-get install lua5.3 liblua5-3 liblua5.3-dev - - These are the Debian libraries that are needed. There should - be equivalent RPM's that can be found - -2. Compilation - - Configure needs these options - - .. code-block:: shell - - ./configure --enable-dev-build --enable-lua <all other interesting options> - - Typically you just include the two new enable lines to build with it. - -3. Using Lua - - * Copy tools/lua.scr into /etc/frr - - * Create a route-map match command - - .. code-block:: console - - ! - router bgp 55 - neighbor 10.50.11.116 remote-as external - address-family ipv4 unicast - neighbor 10.50.11.116 route-map TEST in - exit-address-family - ! - route-map TEST permit 10 - match command mooey - ! - - * In the lua.scr file make sure that you have a function named 'mooey' - - .. code-block:: console - - function mooey () - zlog_debug(string.format("afi: %d: %s %d ifdx: %d aspath: %s localpref: %d", - prefix.family, prefix.route, nexthop.metric, - nexthop.ifindex, nexthop.aspath, nexthop.localpref)) - - nexthop.metric = 33 - nexthop.localpref = 13 - return 3 - end - -4. General Comments - - Please be aware that this is extremely experimental and needs a ton of work - to get this up into a state that is usable. diff --git a/doc/developer/ospf-sr.rst b/doc/developer/ospf-sr.rst index efe9b1b12f..263db9dfb9 100644 --- a/doc/developer/ospf-sr.rst +++ b/doc/developer/ospf-sr.rst @@ -17,6 +17,7 @@ Supported Features * Automatic provisioning of MPLS table * Equal Cost Multi-Path (ECMP) * Static route configuration with label stack up to 32 labels +* TI-LFA (for P2P interfaces only) Interoperability ---------------- @@ -182,6 +183,71 @@ called. Once check the validity of labels, they are send to ZEBRA layer through command for deletion. This is completed by a new labelled route through `ZEBRA_ROUTE_ADD` command, respectively `ZEBRA_ROUTE_DELETE` command. +TI-LFA +^^^^^^ + +Experimental support for Topology Independent LFA (Loop-Free Alternate), see +for example 'draft-bashandy-rtgwg-segment-routing-ti-lfa-05'. The related +files are `ospf_ti_lfa.c/h`. + +The current implementation is rather naive and does not support the advanced +optimizations suggested in e.g. RFC7490 or RFC8102. It focuses on providing +the essential infrastructure which can also later be used to enhance the +algorithmic aspects. + +Supported features: + +* Link and node protection +* Intra-area support +* Proper use of Prefix- and Adjacency-SIDs in label stacks +* Asymmetric weights (using reverse SPF) +* Non-adjacent P/Q spaces +* Protection of Prefix-SIDs + +If configured for every SPF run the routing table is enriched with additional +backup paths for every prefix. The corresponding Prefix-SIDs are updated with +backup paths too within the OSPF SR update task. + +Informal High-Level Algorithm Description: + +:: + + p_spaces = empty_list() + + for every protected_resource (link or node): + p_space = generate_p_space(protected_resource) + p_space.q_spaces = empty_list() + + for every destination that is affected by the protected_resource: + q_space = generate_q_space(destination) + + # The label stack is stored in q_space + generate_label_stack(p_space, q_space) + + # The p_space collects all its q_spaces + p_spaces.q_spaces.add(q_space) + + p_spaces.add(p_space) + + adjust_routing_table(p_spaces) + +Possible Performance Improvements: + +* Improve overall datastructures, get away from linked lists for vertices +* Don't calculate a Q space for every destination, but for a minimum set of + backup paths that cover all destinations in the post-convergence SPF. The + thinking here is that once a backup path is known that it is also a backup + path for all nodes on the path themselves. This can be done by using the + leafs of a trimmed minimum spanning tree generated out of the post- + convergence SPF tree for that particular P space. +* For an alternative (maybe better) optimization look at + https://tools.ietf.org/html/rfc7490#section-5.2.1.3 which describes using + the Q space of the node which is affected by e.g. a link failure. Note that + this optimization is topology dependent. + +It is highly recommended to read e.g. `Segment Routing I/II` by Filsfils to +understand the basics of Ti-LFA. + Configuration ------------- diff --git a/doc/developer/path-internals-daemon.rst b/doc/developer/path-internals-daemon.rst new file mode 100644 index 0000000000..29f017284f --- /dev/null +++ b/doc/developer/path-internals-daemon.rst @@ -0,0 +1,115 @@ +PATHD Internals +=============== + +Architecture +------------ + +Overview +........ + +The pathd deamon manages the segment routing policies, it owns the data +structures representing them and can load modules that manipulate them like the +PCEP module. Its responsibility is to select a candidate path for each +configured policy and to install it into Zebra. + +Zebra +..... + +Zebra manages policies that are active or pending to be activated due to the +next hop not being available yet. In zebra, policy data structures and APIs are +defined in `zebra_srte.[hc]`. + +The responsibilities of Zebra are: + + - Store the policies' segment list. + - Install the policies when their next-hop is available. + - Notify other daemons of the status of the policies. + +Adding and removing policies is done using the commands `ZEBRA_SR_POLICY_SET` +and `ZEBRA_SR_POLICY_DELETE` as parameter of the function `zebra_send_sr_policy` +all defined in `zclient.[hc]`. + +If the first segment of the policy is an unknown label, it is kept until +notified by the mpls hooks `zebra_mpls_label_created`, and then it is installed. + +To get notified when a policy status changes, a client can implement the +`sr_policy_notify_status` callback defined in `zclient.[hc]`. + +For encoding/decoding the various data structures used to comunicate with zebra, +the following functions are available from `zclient.[hc]`: +`zapi_sr_policy_encode`, `zapi_sr_policy_decode` and +`zapi_sr_policy_notify_status_decode`. + + +Pathd +..... + + +The pathd daemon manages all the possible candidate paths for the segment +routing policies and selects the best one following the +`segment routing policy draft <https://tools.ietf.org/html/draft-ietf-spring-segment-routing-policy-06#section-2.9>`_. +It also supports loadable modules for handling dynamic candidate paths and the +creation of new policies and candidate paths at runtime. + +The responsibilities of the pathd base daemon, not including any optional +modules, are: + + - Store the policies and all the possible candidate paths for them. + - Select the best candidate path for each policy and send it to Zebra. + - Provide VTYSH configuration to set up policies and candidate paths. + - Provide a Northbound API to manipulate **configured** policies and candidate paths. + - Handle loadable modules for extending the functionality. + - Provide an API to the loadable module to manipulate policies and candidate paths. + + +Threading Model +--------------- + +The daemon runs completely inside the main thread using FRR event model, there +is no threading involved. + + +Source Code +----------- + +Internal Data Structures +........................ + +The main data structures for policies and candidate paths are defined in +`pathd.h` and implemented in `pathd.c`. + +When modifying these structures, either directly or through the functions +exported by `pathd.h`, nothing should be deleted/freed right away. The deletion +or modification flags must be set and when all the changes are done, the +function `srte_apply_changes` must be called. When called, a new candidate path +may be elected and sent to Zebra, and all the structures flagged as deleted +will be freed. In addition, a hook will be called so dynamic modules can perform +any required action when the elected candidate path changes. + + +Northbound API +.............. + +The northbound API is defined in `path_nb.[ch]` and implemented in +`path_nb_config.c` for configuration data and `path_nb_state.c` for operational +data. + + +Command Line Client +................... + +The command-line client (VTYSH) is implemented in `path_cli.c`. + + +Interface with Zebra +.................... + +All the functions interfacing with Zebra are defined and implemented in +`path_zebra.[hc]`. + + +Loadable Module API +................... + +For the time being, the API the loadable module uses is defined by `pathd.h`, +but in the future, it should be moved to a dedicated include file. diff --git a/doc/developer/path-internals-pcep.rst b/doc/developer/path-internals-pcep.rst new file mode 100644 index 0000000000..ca318314f1 --- /dev/null +++ b/doc/developer/path-internals-pcep.rst @@ -0,0 +1,193 @@ +PCEP Module Internals +===================== + +Introduction +------------ + +The PCEP module for the pathd daemon implements the PCEP protocol described in +:rfc:`5440` to update the policies and candidate paths. + +The protocol encoding/decoding and the basic session management is handled by +the `pceplib external library 1.2 <https://github.com/volta-networks/pceplib/tree/devel-1.2>`_. + +Together with pceplib, this module supports at least partially: + + - :rfc:`5440` + + Most of the protocol defined in the RFC is implemented. + All the messages can be parsed, but this was only tested in the context + of segment routing. Only a very small subset of metric types can be + configured, and there is a known issue with some Cisco routers not + following the IANA numbers for metrics. + + - :rfc:`8231` + + Support delegation of candidate path after performing the initial + computation request. If the PCE does not respond or cannot compute + a path, an empty candidate path is delegated to the PCE. + Only tested in the context of segment routing. + + - :rfc:`8408` + + Only used to comunicate the support for segment routing to the PCE. + + - :rfc:`8664` + + All the NAI types are implemented, but only the MPLS NAI are supported. + If the PCE provide segments that are not MPLS labels, the PCC will + return an error. + +Note that pceplib supports more RFCs and drafts, see pceplib +`README <https://github.com/volta-networks/pceplib/blob/master/README.md>`_ +for more details. + + +Architecture +------------ + +Overview +........ + +The module is separated into multiple layers: + + - pathd interface + - command-line console + - controller + - PCC + - pceplib interface + +The pathd interface handles all the interactions with the daemon API. + +The command-line console handles all the VTYSH configuration commands. + +The controller manages the multiple PCC connections and the interaction between +them and the daemon interface. + +The PCC handles a single connection to a PCE through a pceplib session. + +The pceplib interface abstracts the API of the pceplib. + +.. figure:: ../figures/pcep_module_threading_overview.svg + + +Threading Model +--------------- + +The module requires multiple threads to cooperate: + + - The main thread used by the pathd daemon. + - The controller pthread used to isolate the PCC from the main thread. + - The possible threads started in the pceplib library. + +To ensure thread safety, all the controller and PCC state data structures can +only be read and modified in the controller thread, and all the global data +structures can only be read and modified in the main thread. Most of the +interactions between these threads are done through FRR timers and events. + +The controller is the bridge between the two threads, all the functions that +**MUST** be called from the main thread start with the prefix `pcep_ctrl_` and +all the functions that **MUST** be called from the controller thread start +with the prefix `pcep_thread_`. When an asynchronous action must be taken in +a different thread, an FRR event is sent to the thread. If some synchronous +operation is needed, the calling thread will block and run a callback in the +other thread, there the result is **COPIED** and returned to the calling thread. + +No function other than the controller functions defined for it should be called +from the main thread. The only exception being some utility functions from +`path_pcep_lib.[hc]`. + +All the calls to pathd API functions **MUST** be performed in the main thread, +for that, the controller sends FRR events handled in function +`path_pcep.c:pcep_main_event_handler`. + +For the same reason, the console client only runs in the main thread. It can +freely use the global variable, but **MUST** use controller's `pcep_ctrl_` +functions to interact with the PCCs. + + +Source Code +----------- + +Generic Data Structures +....................... + +The data structures are defined in multiple places, and where they are defined +dictates where they can be used. + +The data structures defined in `path_pcep.h` can be used anywhere in the module. + +Internally, throughout the module, the `struct path` data structure is used +to describe PCEP messages. It is a simplified flattened structure that can +represent multiple complex PCEP message types. The conversion from this +structure to the PCEP data structures used by pceplib is done in the pceplib +interface layer. + +The data structures defined in `path_pcep_controller.h` should only be used +in `path_pcep_controller.c`. Even if a structure pointer is passed as a parameter +to functions defined in `path_pcep_pcc.h`, these should consider it as an opaque +data structure only used to call back controller functions. + +The same applies to the structures defined in `path_pcep_pcc.h`, even if the +controller owns a reference to this data structure, it should never read or +modify it directly, it should be considered an opaque structure. + +The global data structure can be accessed from the pathd interface layer +`path_pcep.c` and the command line client code `path_pcep_cli.c`. + + +Interface With Pathd +.................... + +All the functions calling or called by the pathd daemon are implemented in +`path_pcep.c`. These functions **MUST** run in the main FRR thread, and +all the interactions with the controller and the PCCs **MUST** pass through +the controller's `pcep_ctrl_` prefixed functions. + +To handle asynchronous events from the PCCs, a callback is passed to +`pcep_ctrl_initialize` that is called in the FRR main thread context. + + +Command Line Client +................... + +All the command line configuration commands (VTYSH) are implemented in +`path_pcep_cli.c`. All the functions there run in the main FRR thread and +can freely access the global variables. All the interaction with the +controller's and the PCCs **MUST** pass through the controller `pcep_ctrl_` +prefixed functions. + + +Debugging Helpers +................. + +All the functions formating data structures for debugging and logging purposes +are implemented in `path_pcep_debug.[hc]`. + + +Interface with pceplib +...................... + +All the functions calling the pceplib external library are defined in +`path_pcep_lib.[hc]`. Some functions are called from the main FRR thread, like +`pcep_lib_initialize`, `pcep_lib_finalize`; some can be called from either +thread, like `pcep_lib_free_counters`; some function must be called from the +controller thread, like `pcep_lib_connect`. This will probably be formalized +later on with function prefix like done in the controller. + + +Controller +.......... + +The controller is defined and implemented in `path_pcep_controller.[hc]`. +Part of the controller code runs in FRR main thread and part runs in its own +FRR pthread started to isolate the main thread from the PCCs' event loop. +To communicate between the threads it uses FRR events, timers and +`thread_execute` calls. + + +PCC +... + +Each PCC instance owns its state and runs in the controller thread. They are +defined and implemented in `path_pcep_pcc.[hc]`. All the interactions with +the daemon must pass through some controller's `pcep_thread_` prefixed function. diff --git a/doc/developer/path-internals.rst b/doc/developer/path-internals.rst new file mode 100644 index 0000000000..2c2df0f378 --- /dev/null +++ b/doc/developer/path-internals.rst @@ -0,0 +1,11 @@ +.. _path_internals: + +********* +Internals +********* + +.. toctree:: + :maxdepth: 2 + + path-internals-daemon + path-internals-pcep diff --git a/doc/developer/path.rst b/doc/developer/path.rst new file mode 100644 index 0000000000..b6d2438c58 --- /dev/null +++ b/doc/developer/path.rst @@ -0,0 +1,11 @@ +.. _path: + +***** +PATHD +***** + +.. toctree:: + :maxdepth: 2 + + path-internals + diff --git a/doc/developer/scripting.rst b/doc/developer/scripting.rst new file mode 100644 index 0000000000..b0413619ab --- /dev/null +++ b/doc/developer/scripting.rst @@ -0,0 +1,433 @@ +.. _scripting: + +Scripting +========= + +.. seealso:: User docs for scripting + +Overview +-------- + +FRR has the ability to call Lua scripts to perform calculations, make +decisions, or otherwise extend builtin behavior with arbitrary user code. This +is implemented using the standard Lua C bindings. The supported version of Lua +is 5.3. + +C objects may be passed into Lua and Lua objects may be retrieved by C code via +a marshalling system. In this way, arbitrary data from FRR may be passed to +scripts. It is possible to pass C functions as well. + +The Lua environment is isolated from the C environment; user scripts cannot +access FRR's address space unless explicitly allowed by FRR. + +For general information on how Lua is used to extend C, refer to Part IV of +"Programming in Lua". + +https://www.lua.org/pil/contents.html#24 + + +Design +------ + +Why Lua +^^^^^^^ + +Lua is designed to be embedded in C applications. It is very small; the +standard library is 220K. It is relatively fast. It has a simple, minimal +syntax that is relatively easy to learn and can be understood by someone with +little to no programming experience. Moreover it is widely used to add +scripting capabilities to applications. In short it is designed for this task. + +Reasons against supporting multiple scripting languages: + +- Each language would require different FFI methods, and specifically + different object encoders; a lot of code +- Languages have different capabilities that would have to be brought to + parity with each other; a lot of work +- Languages have vastly different performance characteristics; this would + create alot of basically unfixable issues, and result in a single de facto + standard scripting language (the fastest) +- Each language would need a dedicated maintainer for the above reasons; + this is pragmatically difficult +- Supporting multiple languages fractures the community and limits the audience + with which a given script can be shared + +General +^^^^^^^ + +FRR's concept of a script is somewhat abstracted away from the fact that it is +Lua underneath. A script in has two things: + +- name +- state + +In code: + +.. code-block:: c + + struct frrscript { + /* Script name */ + char *name; + + /* Lua state */ + struct lua_State *L; + }; + + +``name`` is simply a string. Everything else is in ``state``, which is itself a +Lua library object (``lua_State``). This is an opaque struct that is +manipulated using ``lua_*`` functions. The basic ones are imported from +``lua.h`` and the rest are implemented within FRR to fill our use cases. The +thing to remember is that all operations beyond the initial loading the script +take place on this opaque state object. + +There are four basic actions that can be done on a script: + +- load +- execute +- query state +- unload + +They are typically done in this order. + + +Loading +^^^^^^^ + +A snippet of Lua code is referred to as a "chunk". These are simply text. FRR +presently assumes chunks are located in individual files specific to one task. +These files are stored in the scripts directory and must end in ``.lua``. + +A script object is created by loading a script. This is done with +``frrscript_load()``. This function takes the name of the script and an +optional callback function. The string ".lua" is appended to the script name, +and the resultant filename is looked for in the scripts directory. + +For example, to load ``/etc/frr/scripts/bingus.lua``: + +.. code-block:: c + + struct frrscript *fs = frrscript_load("bingus", NULL); + +During loading the script is validated for syntax and its initial environment +is setup. By default this does not include the Lua standard library; there are +security issues to consider, though for practical purposes untrusted users +should not be able to write the scripts directory anyway. If desired the Lua +standard library may be added to the script environment using +``luaL_openlibs(fs->L)`` after loading the script. Further information on +setting up the script environment is in the Lua manual. + + +Executing +^^^^^^^^^ + +After loading, scripts may be executed. A script may take input in the form of +variable bindings set in its environment prior to being run, and may provide +results by setting the value of variables. Arbitrary C values may be +transferred into the script environment, including functions. + +A typical execution call looks something like this: + +.. code-block:: c + + struct frrscript *fs = frrscript_load(...); + + int status_ok = 0, status_fail = 1; + struct prefix p = ...; + + struct frrscript_env env[] = { + {"integer", "STATUS_FAIL", &status_fail}, + {"integer", "STATUS_OK", &status_ok}, + {"prefix", "myprefix", &p}, + {}}; + + int result = frrscript_call(fs, env); + + +To execute a loaded script, we need to define the inputs. These inputs are +passed by binding values to variable names that will be accessible within the +Lua environment. Basically, all communication with the script takes place via +global variables within the script, and to provide inputs we predefine globals +before the script runs. This is done by passing ``frrscript_call()`` an array +of ``struct frrscript_env``. Each struct has three fields. The first identifies +the type of the value being passed; more on this later. The second defines the +name of the global variable within the script environment to bind the third +argument (the value) to. + +The script is then executed and returns a general status code. In the success +case this will be 0, otherwise it will be nonzero. The script itself does not +determine this code, it is provided by the Lua interpreter. + + +Querying State +^^^^^^^^^^^^^^ + +When a chunk is executed, its state at exit is preserved and can be inspected. + +After running a script, results may be retrieved by querying the script's +state. Again this is done by retrieving the values of global variables, which +are known to the script author to be "output" variables. + +A result is retrieved like so: + +.. code-block:: c + + struct frrscript_env myresult = {"string", "myresult"}; + + char *myresult = frrscript_get_result(fs, &myresult); + + ... do something ... + + XFREE(MTYPE_TMP, myresult); + + +As with arguments, results are retrieved by providing a ``struct +frrscript_env`` specifying a type and a global name. No value is necessary, nor +is it modified by ``frrscript_get_result()``. That function simply extracts the +requested value from the script state and returns it. + +In most cases the returned value will be allocated with ``MTYPE_TMP`` and will +need to be freed after use. + + +Unloading +^^^^^^^^^ + +To destroy a script and its associated state: + +.. code-block:: c + + frrscript_unload(fs); + +Values returned by ``frrscript_get_result`` are still valid after the script +they were retrieved from is unloaded. + +Note that you must unload and then load the script if you want to reset its +state, for example to run it again with different inputs. Otherwise the state +from the previous run carries over into subsequent runs. + + +.. _marshalling: + +Marshalling +^^^^^^^^^^^ + +Earlier sections glossed over the meaning of the type name field in ``struct +frrscript_env`` and how data is passed between C and Lua. Lua, as a dynamically +typed, garbage collected language, cannot directly use C values without some +kind of marshalling / unmarshalling system to translate types between the two +runtimes. + +Lua communicates with C code using a stack. C code wishing to provide data to +Lua scripts must provide a function that marshalls the C data into a Lua +representation and pushes it on the stack. C code wishing to retrieve data from +Lua must provide a corresponding unmarshalling function that retrieves a Lua +value from the stack and converts it to the corresponding C type. These two +functions, together with a chosen name of the type they operate on, are +referred to as ``codecs`` in FRR. + +A codec is defined as: + +.. code-block:: c + + typedef void (*encoder_func)(lua_State *, const void *); + typedef void *(*decoder_func)(lua_State *, int); + + struct frrscript_codec { + const char *typename; + encoder_func encoder; + decoder_func decoder; + }; + +A typename string and two function pointers. + +``typename`` can be anything you want. For example, for the combined types of +``struct prefix`` and its equivalent in Lua I have chosen the name ``prefix``. +There is no restriction on naming here, it is just a human name used as a key +and specified when passing and retrieving values. + +``encoder`` is a function that takes a ``lua_State *`` and a C type and pushes +onto the Lua stack a value representing the C type. For C structs, the usual +case, this will typically be a Lua table (tables are the only datastructure Lua +has). For example, here is the encoder function for ``struct prefix``: + + +.. code-block:: c + + void lua_pushprefix(lua_State *L, const struct prefix *prefix) + { + char buffer[PREFIX_STRLEN]; + + zlog_debug("frrlua: pushing prefix table"); + + lua_newtable(L); + lua_pushstring(L, prefix2str(prefix, buffer, PREFIX_STRLEN)); + lua_setfield(L, -2, "network"); + lua_pushinteger(L, prefix->prefixlen); + lua_setfield(L, -2, "length"); + lua_pushinteger(L, prefix->family); + lua_setfield(L, -2, "family"); + } + +This function pushes a single value onto the Lua stack. It is a table whose equivalent in Lua is: + +.. code-block:: + + { ["network"] = "1.2.3.4/24", ["prefixlen"] = 24, ["family"] = 2 } + + +``decoder`` does the reverse; it takes a ``lua_State *`` and an index into the +stack, and unmarshalls a Lua value there into the corresponding C type. Again +for ``struct prefix``: + + +.. code-block:: c + + void *lua_toprefix(lua_State *L, int idx) + { + struct prefix *p = XCALLOC(MTYPE_TMP, sizeof(struct prefix)); + + lua_getfield(L, idx, "network"); + str2prefix(lua_tostring(L, -1), p); + lua_pop(L, 1); + + return p; + } + +By convention these functions should be called ``lua_to*``, as this is the +naming convention used by the Lua C library for the basic types e.g. +``lua_tointeger`` and ``lua_tostring``. + +The returned data must always be copied off the stack and the copy must be +allocated with ``MTYPE_TMP``. This way it is possible to unload the script +(destroy the state) without invalidating any references to values stored in it. + +To register a new type with its corresponding encoding functions: + +.. code-block:: c + + struct frrscript_codec frrscript_codecs_lib[] = { + {.typename = "prefix", + .encoder = (encoder_func)lua_pushprefix, + .decoder = lua_toprefix}, + {.typename = "sockunion", + .encoder = (encoder_func)lua_pushsockunion, + .decoder = lua_tosockunion}, + ... + {}}; + + frrscript_register_type_codecs(frrscript_codecs_lib); + +From this point on the type names are available to be used when calling any +script and getting its results. + +.. note:: + + Marshalled types are not restricted to simple values like integers, strings + and tables. It is possible to marshall a type such that the resultant object + in Lua is an actual object-oriented object, complete with methods that call + back into defined C functions. See the Lua manual for how to do this; for a + code example, look at how zlog is exported into the script environment. + + +Script Environment +------------------ + +Logging +^^^^^^^ + +For convenience, script environments are populated by default with a ``log`` +object which contains methods corresponding to each of the ``zlog`` levels: + +.. code-block:: lua + + log.info("info") + log.warn("warn") + log.error("error") + log.notice("notice") + log.debug("debug") + +The log messages will show up in the daemon's log output. + + +Examples +-------- + +For a complete code example involving passing custom types, retrieving results, +and doing complex calculations in Lua, look at the implementation of the +``match script SCRIPT`` command for BGP routemaps. This example calls into a +script with a route prefix and attributes received from a peer and expects the +script to return a match / no match / match and update result. + +An example script to use with this follows. This script matches, does not match +or updates a route depending on how many BGP UPDATE messages the peer has +received when the script is called, simply as a demonstration of what can be +accomplished with scripting. + +.. code-block:: lua + + + -- Example route map matching + -- author: qlyoung + -- + -- The following variables are available to us: + -- log + -- logging library, with the usual functions + -- prefix + -- the route under consideration + -- attributes + -- the route's attributes + -- peer + -- the peer which received this route + -- RM_FAILURE + -- status code in case of failure + -- RM_NOMATCH + -- status code for no match + -- RM_MATCH + -- status code for match + -- RM_MATCH_AND_CHANGE + -- status code for match-and-set + -- + -- We need to set the following out values: + -- action + -- Set to the appropriate status code to indicate what we did + -- attributes + -- Setting fields on here will propagate them back up to the caller if + -- 'action' is set to RM_MATCH_AND_CHANGE. + + + log.info("Evaluating route " .. prefix.network .. " from peer " .. peer.remote_id.string) + + function on_match (prefix, attrs) + log.info("Match") + action = RM_MATCH + end + + function on_nomatch (prefix, attrs) + log.info("No match") + action = RM_NOMATCH + end + + function on_match_and_change (prefix, attrs) + action = RM_MATCH_AND_CHANGE + log.info("Match and change") + attrs["metric"] = attrs["metric"] + 7 + end + + special_routes = { + ["172.16.10.4/24"] = on_match, + ["172.16.13.1/8"] = on_nomatch, + ["192.168.0.24/8"] = on_match_and_change, + } + + + if special_routes[prefix.network] then + special_routes[prefix.network](prefix, attributes) + elseif peer.stats.update_in % 3 == 0 then + on_match(prefix, attributes) + elseif peer.stats.update_in % 2 == 0 then + on_nomatch(prefix, attributes) + else + on_match_and_change(prefix, attributes) + end + diff --git a/doc/developer/subdir.am b/doc/developer/subdir.am index 3c0d203007..f7e4486ef0 100644 --- a/doc/developer/subdir.am +++ b/doc/developer/subdir.am @@ -27,16 +27,17 @@ dev_RSTFILES = \ doc/developer/building.rst \ doc/developer/cli.rst \ doc/developer/conf.py \ + doc/developer/cross-compiling.rst \ doc/developer/frr-release-procedure.rst \ doc/developer/grpc.rst \ doc/developer/hooks.rst \ doc/developer/include-compile.rst \ doc/developer/index.rst \ doc/developer/library.rst \ + doc/developer/link-state.rst \ doc/developer/lists.rst \ doc/developer/locking.rst \ doc/developer/logging.rst \ - doc/developer/lua.rst \ doc/developer/memtypes.rst \ doc/developer/modules.rst \ doc/developer/next-hop-tracking.rst \ @@ -46,12 +47,19 @@ dev_RSTFILES = \ doc/developer/packaging-debian.rst \ doc/developer/packaging-redhat.rst \ doc/developer/packaging.rst \ + doc/developer/path-internals-daemon.rst \ + doc/developer/path-internals-pcep.rst \ + doc/developer/path-internals.rst \ + doc/developer/path.rst \ doc/developer/rcu.rst \ + doc/developer/scripting.rst \ doc/developer/static-linking.rst \ + doc/developer/tracing.rst \ doc/developer/testing.rst \ doc/developer/topotests-snippets.rst \ doc/developer/topotests.rst \ doc/developer/workflow.rst \ + doc/developer/xrefs.rst \ doc/developer/zebra.rst \ # end diff --git a/doc/developer/topotests-markers.rst b/doc/developer/topotests-markers.rst new file mode 100644 index 0000000000..9f92412595 --- /dev/null +++ b/doc/developer/topotests-markers.rst @@ -0,0 +1,114 @@ +.. _topotests-markers: + +Markers +-------- + +To allow for automated selective testing on large scale continuous integration +systems, all tests must be marked with at least one of the following markers: + +* babeld +* bfdd +* bgpd +* eigrpd +* isisd +* ldpd +* nhrpd +* ospf6d +* ospfd +* pathd +* pbrd +* pimd +* ripd +* ripngd +* sharpd +* staticd +* vrrpd + +The markers corespond to the daemon subdirectories in FRR's source code and have +to be added to tests on a module level depending on which daemons are used +during the test. + +The goal is to have continuous integration systems scan code submissions, detect +changes to files in a daemons subdirectory and select only tests using that +daemon to run to shorten developers waiting times for test results and save test +infrastructure resources. + +Newly written modules and code changes on tests, which do not contain any or +incorrect markers will be rejected by reviewers. + + +Registering markers +^^^^^^^^^^^^^^^^^^^ +The Registration of new markers takes place in the file +``tests/topotests/pytest.ini``: + +.. code:: python3 + + # tests/topotests/pytest.ini + [pytest] + ... + markers = + babeld: Tests that run against BABELD + bfdd: Tests that run against BFDD + ... + vrrpd: Tests that run against VRRPD + + +Adding markers to tests +^^^^^^^^^^^^^^^^^^^^^^^ +Markers are added to a test by placing a global variable in the test module. + +Adding a single marker: + +.. code:: python3 + + import pytest + ... + + # add after imports, before defining classes or functions: + pytestmark = pytest.mark.bfdd + + ... + + def test_using_bfdd(): + + +Adding multiple markers: + +.. code:: python3 + + import pytest + ... + + # add after imports, before defining classes or functions: + pytestmark = [ + pytest.mark.bgpd, + pytest.mark.ospfd, + pytest.mark.ospf6d + ] + + ... + + def test_using_bgpd_ospfd_ospf6d(): + + +Selecting marked modules for testing +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ +Selecting by a single marker: + +.. code:: bash + + pytest -v -m isisd + +Selecting by multiple markers: + +.. code:: bash + + pytest -v -m "isisd or ldpd or nhrpd" + + +Further Information +^^^^^^^^^^^^^^^^^^^ +The `online pytest documentation <https://docs.pytest.org/en/stable/example/markers.html>`_ +provides further information and usage examples for pytest markers. + diff --git a/doc/developer/topotests.rst b/doc/developer/topotests.rst index 5486fd826d..93d81548b2 100644 --- a/doc/developer/topotests.rst +++ b/doc/developer/topotests.rst @@ -21,8 +21,10 @@ Installing Mininet Infrastructure apt-get install mininet apt-get install python-pip apt-get install iproute + apt-get install iperf pip install ipaddr pip install "pytest<5" + pip install "scapy>=2.4.2" pip install exabgp==3.4.17 (Newer 4.0 version of exabgp is not yet supported) useradd -d /var/run/exabgp/ -s /bin/false exabgp @@ -49,6 +51,28 @@ Next, update security limits by changing :file:`/etc/security/limits.conf` to:: Reboot for options to take effect. +SNMP Utilities Installation +""""""""""""""""""""""""""" + +To run SNMP test you need to install SNMP utilities and MIBs. Unfortunately +there are some errors in the upstream MIBS which need to be patched up. The +following steps will get you there on Ubuntu 20.04. + +.. code:: shell + + apt install snmpd snmp + apt install snmp-mibs-downloader + download-mibs + wget http://www.iana.org/assignments/ianaippmmetricsregistry-mib/ianaippmmetricsregistry-mib -O /usr/share/snmp/mibs/iana/IANA-IPPM-METRICS-REGISTRY-MIB + wget http://pastebin.com/raw.php?i=p3QyuXzZ -O /usr/share/snmp/mibs/ietf/SNMPv2-PDU + wget http://pastebin.com/raw.php?i=gG7j8nyk -O /usr/share/snmp/mibs/ietf/IPATM-IPMC-MIB + edit /etc/snmp/snmp.conf to look like this + # As the snmp packages come without MIB files due to license reasons, loading + # of MIBs is disabled by default. If you added the MIBs you can reenable + # loading them by commenting out the following line. + mibs +ALL + + FRR Installation ^^^^^^^^^^^^^^^^ @@ -84,6 +108,7 @@ If you prefer to manually build FRR, then use the following suggested config: --enable-user=frr \ --enable-group=frr \ --enable-vty-group=frrvty \ + --enable-snmp=agentx \ --with-pkg-extra-version=-my-manual-build And create ``frr`` user and ``frrvty`` group as follows: @@ -769,6 +794,8 @@ Requirements: conforms with this, run it without the :option:`-s` parameter. - Use `black <https://github.com/psf/black>`_ code formatter before creating a pull request. This ensures we have a unified code style. +- Mark test modules with pytest markers depending on the daemons used during the + tests (s. Markers) Tips: @@ -927,6 +954,8 @@ does what you need. If nothing is similar, then you may create a new topology, preferably, using the newest template (:file:`tests/topotests/example-test/test_template.py`). +.. include:: topotests-markers.rst + .. include:: topotests-snippets.rst License diff --git a/doc/developer/tracing.rst b/doc/developer/tracing.rst index ee0a6be008..c194ae1270 100644 --- a/doc/developer/tracing.rst +++ b/doc/developer/tracing.rst @@ -57,7 +57,7 @@ run the target in non-forking mode (no ``-d``) and use LTTng as usual (refer to LTTng user manual). When using USDT probes with LTTng, follow the example in `this article <https://lttng.org/blog/2019/10/15/new-dynamic-user-space-tracing-in-lttng/>`_. -To trace with dtrace or SystemTap, compile with :option:`--enable-usdt=yes` and +To trace with dtrace or SystemTap, compile with `--enable-usdt=yes` and use your tracer as usual. To see available USDT probes:: @@ -308,6 +308,31 @@ Limitations Tracers do not like ``fork()`` or ``dlopen()``. LTTng has some workarounds for this involving interceptor libraries using ``LD_PRELOAD``. +If you're running FRR in a typical daemonizing way (``-d`` to the daemons) +you'll need to run the daemons like so: + +.. code-block:: shell + + LD_PRELOAD=liblttng-ust-fork.so <daemon> + + +If you're using systemd this you can accomplish this for all daemons by +modifying ``frr.service`` like so: + +.. code-block:: diff + + --- a/frr.service + +++ b/frr.service + @@ -7,6 +7,7 @@ Before=network.target + OnFailure=heartbeat-failed@%n.service + + [Service] + +Environment="LD_PRELOAD=liblttng-ust-fork.so" + Nice=-5 + Type=forking + NotifyAccess=all + + USDT tracepoints are relatively high overhead and probably shouldn't be used for "flight recorder" functionality, i.e. enabling and passively recording all events for monitoring purposes. It's generally okay to use LTTng like this, diff --git a/doc/developer/workflow.rst b/doc/developer/workflow.rst index 4183ac6480..861d87b998 100644 --- a/doc/developer/workflow.rst +++ b/doc/developer/workflow.rst @@ -1262,6 +1262,9 @@ When documented this way, CLI commands can be cross referenced with the This is very helpful for users who want to quickly remind themselves what a particular command does. +When documenting a cli that has a ``no`` form, please do not include +the ``no`` in the ``.. index::`` line. + Configuration Snippets ^^^^^^^^^^^^^^^^^^^^^^ diff --git a/doc/developer/xrefs.rst b/doc/developer/xrefs.rst new file mode 100644 index 0000000000..6a0794d41b --- /dev/null +++ b/doc/developer/xrefs.rst @@ -0,0 +1,170 @@ +.. _xrefs: + +Introspection (xrefs) +===================== + +The FRR library provides an introspection facility called "xrefs." The intent +is to provide structured access to annotated entities in the compiled binary, +such as log messages and thread scheduling calls. + +Enabling and use +---------------- + +Support for emitting an xref is included in the macros for the specific +entities, e.g. :c:func:`zlog_info` contains the relevant statements. The only +requirement for the system to work is a GNU compatible linker that supports +section start/end symbols. (The only known linker on any system FRR supports +that does not do this is the Solaris linker.) + +To verify xrefs have been included in a binary or dynamic library, run +``readelf -n binary``. For individual object files, it's +``readelf -S object.o | grep xref_array`` instead. + +An extraction tool will be added in a future commit. + +Structure and contents +---------------------- + +As a slight improvement to security and fault detection, xrefs are divided into +a ``const struct xref *`` and an optional ``struct xrefdata *``. The required +const part contains: + +.. c:member:: enum xref_type xref.type + + Identifies what kind of object the xref points to. + +.. c:member:: int line +.. c:member:: const char *xref.file +.. c:member:: const char *xref.func + + Source code location of the xref. ``func`` will be ``<global>`` for + xrefs outside of a function. + +.. c:member:: struct xrefdata *xref.xrefdata + + The optional writable part of the xref. NULL if no non-const part exists. + +The optional non-const part has: + +.. c:member:: const struct xref *xrefdata.xref + + Pointer back to the constant part. Since circular pointers are close to + impossible to emit from inside a function body's static variables, this + is initialized at startup. + +.. c:member:: char xrefdata.uid[16] + + Unique identifier, see below. + +.. c:member:: const char *xrefdata.hashstr +.. c:member:: uint32_t xrefdata.hashu32[2] + + Input to unique identifier calculation. These should encompass all + details needed to make an xref unique. If more than one string should + be considered, use string concatenation for the initializer. + +Both structures can be extended by embedding them in a larger type-specific +struct, e.g. ``struct xref_logmsg *``. + +Unique identifiers +------------------ + +All xrefs that have a writable ``struct xrefdata *`` part are assigned an +unique identifier, which is formed as base32 (crockford) SHA256 on: + +- the source filename +- the ``hashstr`` field +- the ``hashu32`` fields + +.. note:: + + Function names and line numbers are intentionally not included to allow + moving items within a file without affecting the identifier. + +For running executables, this hash is calculated once at startup. When +directly reading from an ELF file with external tooling, the value must be +calculated when necessary. + +The identifiers have the form ``AXXXX-XXXXX`` where ``X`` is +``0-9, A-Z except I,L,O,U`` and ``A`` is ``G-Z except I,L,O,U`` (i.e. the +identifiers always start with a letter.) When reading identifiers from user +input, ``I`` and ``L`` should be replaced with ``1`` and ``O`` should be +replaced with ``0``. There are 49 bits of entropy in this identifier. + +Underlying machinery +-------------------- + +Xrefs are nothing other than global variables with some extra glue to make +them possible to find from the outside by looking at the binary. The first +non-obvious part is that they can occur inside of functions, since they're +defined as ``static``. They don't have a visible name -- they don't need one. + +To make finding these variables possible, another global variable, a pointer +to the first one, is created in the same way. However, it is put in a special +ELF section through ``__attribute__((section("xref_array")))``. This is the +section you can see with readelf. + +Finally, on the level of a whole executable or library, the linker will stuff +the individual pointers consecutive to each other since they're in the same +section — hence the array. Start and end of this array is given by the +linker-autogenerated ``__start_xref_array`` and ``__stop_xref_array`` symbols. +Using these, both a constructor to run at startup as well as an ELF note are +created. + +The ELF note is the entrypoint for externally retrieving xrefs from a binary +without having to run it. It can be found by walking through the ELF data +structures even if the binary has been fully stripped of debug and section +information. SystemTap's SDT probes & LTTng's trace points work in the same +way (though they emit 1 note for each probe, while xrefs only emit one note +in total which refers to the array.) Using xrefs does not impact SystemTap +or LTTng, the notes have identifiers they can be distinguished by. + +The ELF structure of a linked binary (library or executable) will look like +this:: + + $ readelf --wide -l -n lib/.libs/libfrr.so + + Elf file type is DYN (Shared object file) + Entry point 0x67d21 + There are 12 program headers, starting at offset 64 + + Program Headers: + Type Offset VirtAddr PhysAddr FileSiz MemSiz Flg Align + PHDR 0x000040 0x0000000000000040 0x0000000000000040 0x0002a0 0x0002a0 R 0x8 + INTERP 0x125560 0x0000000000125560 0x0000000000125560 0x00001c 0x00001c R 0x10 + [Requesting program interpreter: /lib64/ld-linux-x86-64.so.2] + LOAD 0x000000 0x0000000000000000 0x0000000000000000 0x02aff0 0x02aff0 R 0x1000 + LOAD 0x02b000 0x000000000002b000 0x000000000002b000 0x0b2889 0x0b2889 R E 0x1000 + LOAD 0x0de000 0x00000000000de000 0x00000000000de000 0x070048 0x070048 R 0x1000 + LOAD 0x14e428 0x000000000014f428 0x000000000014f428 0x00fb70 0x01a2b8 RW 0x1000 + DYNAMIC 0x157a40 0x0000000000158a40 0x0000000000158a40 0x000270 0x000270 RW 0x8 + NOTE 0x0002e0 0x00000000000002e0 0x00000000000002e0 0x00004c 0x00004c R 0x4 + TLS 0x14e428 0x000000000014f428 0x000000000014f428 0x000000 0x000008 R 0x8 + GNU_EH_FRAME 0x12557c 0x000000000012557c 0x000000000012557c 0x00819c 0x00819c R 0x4 + GNU_STACK 0x000000 0x0000000000000000 0x0000000000000000 0x000000 0x000000 RW 0x10 + GNU_RELRO 0x14e428 0x000000000014f428 0x000000000014f428 0x009bd8 0x009bd8 R 0x1 + + (...) + + Displaying notes found in: .note.gnu.build-id + Owner Data size Description + GNU 0x00000014 NT_GNU_BUILD_ID (unique build ID bitstring) Build ID: 6a1f66be38b523095ebd6ec13cc15820cede903d + + Displaying notes found in: .note.FRR + Owner Data size Description + FRRouting 0x00000010 Unknown note type: (0x46455258) description data: 6c eb 15 00 00 00 00 00 74 ec 15 00 00 00 00 00 + +Where 0x15eb6c…0x15ec74 are the offsets (relative to the note itself) where +the xref array is in the file. Also note the owner is clearly marked as +"FRRouting" and the type is "XREF" in hex. + +For SystemTap's use of ELF notes, refer to +https://libstapsdt.readthedocs.io/en/latest/how-it-works/internals.html as an +entry point. + +.. note:: + + Due to GCC bug 41091, the "xref_array" section is not correctly generated + for C++ code when compiled by GCC. A workaround is present for runtime + functionality, but to extract the xrefs from a C++ source file, it needs + to be built with clang (or a future fixed version of GCC) instead. |