lib/link_state.h

   1 /*
   2  * Link State Database definition - ted.h
   3  *
   4  * Author: Olivier Dugeon <olivier.dugeon@orange.com>
   5  *
   6  * Copyright (C) 2020 Orange http://www.orange.com
   7  *
   8  * This file is part of Free Range Routing (FRR).
   9  *
  10  * FRR is free software; you can redistribute it and/or modify it
  11  * under the terms of the GNU General Public License as published by the
  12  * Free Software Foundation; either version 2, or (at your option) any
  13  * later version.
  14  *
  15  * FRR is distributed in the hope that it will be useful, but
  16  * WITHOUT ANY WARRANTY; without even the implied warranty of
  17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18  * General Public License for more details.
  19  *
  20  * You should have received a copy of the GNU General Public License along
  21  * with this program; see the file COPYING; if not, write to the Free Software
  22  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  23  */
  24
  25 #ifndef _FRR_LINK_STATE_H_
  26 #define _FRR_LINK_STATE_H_
  27
  28 #include "admin_group.h"
  29 #include "typesafe.h"
  30
  31 #ifdef __cplusplus
  32 extern "C" {
  33 #endif
  34
  35 /**
  36  * This file defines the model used to implement a Link State Database
  37  * suitable to be used by various protocol like RSVP-TE, BGP-LS, PCEP ...
  38  * This database is normally fulfill by the link state routing protocol,
  39  * commonly OSPF or ISIS, carrying Traffic Engineering information within
  40  * Link State Attributes. See, RFC3630.(OSPF-TE) and RFC5305 (ISIS-TE).
  41  *
  42  * At least, 3 types of Link State structure are defined:
  43  *  - Link State Node that groups all information related to a node
  44  *  - Link State Attributes that groups all information related to a link
  45  *  - Link State Prefix that groups all information related to a prefix
  46  *
  47  * These 3 types of structures are those handled by BGP-LS (see RFC7752).
  48  *
  49  * Each structure, in addition to the specific parameters, embed the node
  50  * identifier which advertises the Link State and a bit mask as flags to
  51  * indicates which parameters are valid i.e. for which the value corresponds
  52  * to a Link State information convey by the routing protocol.
  53  * Node identifier is composed of the route id as IPv4 address plus the area
  54  * id for OSPF and the ISO System id plus the IS-IS level for IS-IS.
  55  */
  56
  57 /* external reference */
  58 struct zapi_opaque_reg_info;
  59 struct zclient;
  60
  61 /* Link State Common definitions */
  62 #define MAX_NAME_LENGTH         256
  63 #define ISO_SYS_ID_LEN          6
  64
  65 /* Type of Node */
  66 enum ls_node_type {
  67         NONE = 0,       /* Unknown */
  68         STANDARD,       /* a P or PE node */
  69         ABR,            /* an Array Border Node */
  70         ASBR,           /* an Autonomous System Border Node */
  71         RMT_ASBR,       /* Remote ASBR */
  72         PSEUDO          /* a Pseudo Node */
  73 };
  74
  75 /* Origin of the Link State information */
  76 enum ls_origin { UNKNOWN = 0, ISIS_L1, ISIS_L2, OSPFv2, DIRECT, STATIC };
  77
  78 /**
  79  * Link State Node Identifier as:
  80  *  - IPv4 address + Area ID for OSPF
  81  *  - ISO System ID + ISIS Level for ISIS
  82  */
  83 struct ls_node_id {
  84         enum ls_origin origin;          /* Origin of the LS information */
  85         union {
  86                 struct {
  87                         struct in_addr addr;            /* OSPF Router IS */
  88                         struct in_addr area_id;         /* OSPF Area ID */
  89                 } ip;
  90                 struct {
  91                         uint8_t sys_id[ISO_SYS_ID_LEN]; /* ISIS System ID */
  92                         uint8_t level;                  /* ISIS Level */
  93                         uint8_t padding;
  94                 } iso;
  95         } id;
  96 };
  97
  98 /**
  99  * Check if two Link State Node IDs are equal. Note that this routine has the
 100  * same return value sense as '==' (which is different from a comparison).
 101  *
 102  * @param i1    First Link State Node Identifier
 103  * @param i2    Second Link State Node Identifier
 104  * @return      1 if equal, 0 otherwise
 105  */
 106 extern int ls_node_id_same(struct ls_node_id i1, struct ls_node_id i2);
 107
 108 /* Link State flags to indicate which Node parameters are valid */
 109 #define LS_NODE_UNSET           0x0000
 110 #define LS_NODE_NAME            0x0001
 111 #define LS_NODE_ROUTER_ID       0x0002
 112 #define LS_NODE_ROUTER_ID6      0x0004
 113 #define LS_NODE_FLAG            0x0008
 114 #define LS_NODE_TYPE            0x0010
 115 #define LS_NODE_AS_NUMBER       0x0020
 116 #define LS_NODE_SR              0x0040
 117 #define LS_NODE_SRLB            0x0080
 118 #define LS_NODE_MSD             0x0100
 119
 120 /* Link State Node structure */
 121 struct ls_node {
 122         uint16_t flags;                 /* Flag for parameters validity */
 123         struct ls_node_id adv;          /* Adv. Router of this Link State */
 124         char name[MAX_NAME_LENGTH];     /* Name of the Node (IS-IS only) */
 125         struct in_addr router_id;       /* IPv4 Router ID */
 126         struct in6_addr router_id6;     /* IPv6 Router ID */
 127         uint8_t node_flag;              /* IS-IS or OSPF Node flag */
 128         enum ls_node_type type;         /* Type of Node */
 129         uint32_t as_number;             /* Local or neighbor AS number */
 130         struct ls_srgb {                /* Segment Routing Global Block */
 131                 uint32_t lower_bound;           /* MPLS label lower bound */
 132                 uint32_t range_size;            /* MPLS label range size */
 133                 uint8_t flag;                   /* IS-IS SRGB flags */
 134         } srgb;
 135         struct ls_srlb {                /* Segment Routing Local Block */
 136                 uint32_t lower_bound;           /* MPLS label lower bound */
 137                 uint32_t range_size;            /* MPLS label range size */
 138         } srlb;
 139         uint8_t algo[2];                /* Segment Routing Algorithms */
 140         uint8_t msd;                    /* Maximum Stack Depth */
 141 };
 142
 143 /* Link State flags to indicate which Attribute parameters are valid */
 144 #define LS_ATTR_UNSET           0x00000000
 145 #define LS_ATTR_NAME            0x00000001
 146 #define LS_ATTR_METRIC          0x00000002
 147 #define LS_ATTR_TE_METRIC       0x00000004
 148 #define LS_ATTR_ADM_GRP         0x00000008
 149 #define LS_ATTR_LOCAL_ADDR      0x00000010
 150 #define LS_ATTR_NEIGH_ADDR      0x00000020
 151 #define LS_ATTR_LOCAL_ADDR6     0x00000040
 152 #define LS_ATTR_NEIGH_ADDR6     0x00000080
 153 #define LS_ATTR_LOCAL_ID        0x00000100
 154 #define LS_ATTR_NEIGH_ID        0x00000200
 155 #define LS_ATTR_MAX_BW          0x00000400
 156 #define LS_ATTR_MAX_RSV_BW      0x00000800
 157 #define LS_ATTR_UNRSV_BW        0x00001000
 158 #define LS_ATTR_REMOTE_AS       0x00002000
 159 #define LS_ATTR_REMOTE_ADDR     0x00004000
 160 #define LS_ATTR_REMOTE_ADDR6    0x00008000
 161 #define LS_ATTR_DELAY           0x00010000
 162 #define LS_ATTR_MIN_MAX_DELAY   0x00020000
 163 #define LS_ATTR_JITTER          0x00040000
 164 #define LS_ATTR_PACKET_LOSS     0x00080000
 165 #define LS_ATTR_AVA_BW          0x00100000
 166 #define LS_ATTR_RSV_BW          0x00200000
 167 #define LS_ATTR_USE_BW          0x00400000
 168 #define LS_ATTR_ADJ_SID         0x01000000
 169 #define LS_ATTR_BCK_ADJ_SID     0x02000000
 170 #define LS_ATTR_ADJ_SID6        0x04000000
 171 #define LS_ATTR_BCK_ADJ_SID6    0x08000000
 172 #define LS_ATTR_SRLG            0x10000000
 173 #define LS_ATTR_EXT_ADM_GRP 0x20000000
 174
 175 /* Link State Attributes */
 176 struct ls_attributes {
 177         uint32_t flags;                 /* Flag for parameters validity */
 178         struct ls_node_id adv;          /* Adv. Router of this Link State */
 179         char name[MAX_NAME_LENGTH];     /* Name of the Edge. Could be null */
 180         uint32_t metric;                /* IGP standard metric */
 181         struct ls_standard {            /* Standard TE metrics */
 182                 uint32_t te_metric;             /* Traffic Engineering metric */
 183                 uint32_t admin_group;           /* Administrative Group */
 184                 struct in_addr local;           /* Local IPv4 address */
 185                 struct in_addr remote;          /* Remote IPv4 address */
 186                 struct in6_addr local6;         /* Local IPv6 address */
 187                 struct in6_addr remote6;        /* Remote IPv6 address */
 188                 uint32_t local_id;              /* Local Identifier */
 189                 uint32_t remote_id;             /* Remote Identifier */
 190                 float max_bw;                   /* Maximum Link Bandwidth */
 191                 float max_rsv_bw;               /* Maximum Reservable BW */
 192                 float unrsv_bw[8];              /* Unreserved BW per CT (8) */
 193                 uint32_t remote_as;             /* Remote AS number */
 194                 struct in_addr remote_addr;     /* Remote IPv4 address */
 195                 struct in6_addr remote_addr6;   /* Remote IPv6 address */
 196         } standard;
 197         struct ls_extended {            /* Extended TE Metrics */
 198                 uint32_t delay;         /* Unidirectional average delay */
 199                 uint32_t min_delay;     /* Unidirectional minimum delay */
 200                 uint32_t max_delay;     /* Unidirectional maximum delay */
 201                 uint32_t jitter;        /* Unidirectional delay variation */
 202                 uint32_t pkt_loss;      /* Unidirectional packet loss */
 203                 float ava_bw;           /* Available Bandwidth */
 204                 float rsv_bw;           /* Reserved Bandwidth */
 205                 float used_bw;          /* Utilized Bandwidth */
 206         } extended;
 207         struct admin_group ext_admin_group; /* Extended Admin. Group */
 208 #define ADJ_PRI_IPV4    0
 209 #define ADJ_BCK_IPV4    1
 210 #define ADJ_PRI_IPV6    2
 211 #define ADJ_BCK_IPV6    3
 212 #define LS_ADJ_MAX      4
 213         struct ls_adjacency {           /* (LAN)-Adjacency SID for OSPF */
 214                 uint32_t sid;           /* SID as MPLS label or index */
 215                 uint8_t flags;          /* Flags */
 216                 uint8_t weight;         /* Administrative weight */
 217                 union {
 218                         struct in_addr addr;    /* Neighbor @IP for OSPF */
 219                         uint8_t sysid[ISO_SYS_ID_LEN]; /* or Sys-ID for ISIS */
 220                 } neighbor;
 221         } adj_sid[4];           /* IPv4/IPv6 & Primary/Backup (LAN)-Adj. SID */
 222         uint32_t *srlgs;        /* List of Shared Risk Link Group */
 223         uint8_t srlg_len;       /* number of SRLG in the list */
 224 };
 225
 226 /* Link State flags to indicate which Prefix parameters are valid */
 227 #define LS_PREF_UNSET           0x00
 228 #define LS_PREF_IGP_FLAG        0x01
 229 #define LS_PREF_ROUTE_TAG       0x02
 230 #define LS_PREF_EXTENDED_TAG    0x04
 231 #define LS_PREF_METRIC          0x08
 232 #define LS_PREF_SR              0x10
 233
 234 /* Link State Prefix */
 235 struct ls_prefix {
 236         uint8_t flags;                  /* Flag for parameters validity */
 237         struct ls_node_id adv;          /* Adv. Router of this Link State */
 238         struct prefix pref;             /* IPv4 or IPv6 prefix */
 239         uint8_t igp_flag;               /* IGP Flags associated to the prefix */
 240         uint32_t route_tag;             /* IGP Route Tag */
 241         uint64_t extended_tag;          /* IGP Extended Route Tag */
 242         uint32_t metric;                /* Route metric for this prefix */
 243         struct ls_sid {
 244                 uint32_t sid;           /* Segment Routing ID */
 245                 uint8_t sid_flag;       /* Segment Routing Flags */
 246                 uint8_t algo;           /* Algorithm for Segment Routing */
 247         } sr;
 248 };
 249
 250 /**
 251  * Create a new Link State Node. Structure is dynamically allocated.
 252  *
 253  * @param adv   Mandatory Link State Node ID i.e. advertise router information
 254  * @param rid   Router ID as IPv4 address
 255  * @param rid6  Router ID as IPv6 address
 256  *
 257  * @return      New Link State Node
 258  */
 259 extern struct ls_node *ls_node_new(struct ls_node_id adv, struct in_addr rid,
 260                                    struct in6_addr rid6);
 261
 262 /**
 263  * Remove Link State Node. Data structure is freed.
 264  *
 265  * @param node        Pointer to a valid Link State Node structure
 266  */
 267 extern void ls_node_del(struct ls_node *node);
 268
 269 /**
 270  * Check if two Link State Nodes are equal. Note that this routine has the same
 271  * return value sense as '==' (which is different from a comparison).
 272  *
 273  * @param n1    First Link State Node to be compare
 274  * @param n2    Second Link State Node to be compare
 275  *
 276  * @return      1 if equal, 0 otherwise
 277  */
 278 extern int ls_node_same(struct ls_node *n1, struct ls_node *n2);
 279
 280 /**
 281  * Create a new Link State Attributes. Structure is dynamically allocated.
 282  * At least one of parameters MUST be valid and not equal to 0.
 283  *
 284  * @param adv           Mandatory Link State Node ID i.e. advertise router ID
 285  * @param local         Local IPv4 address
 286  * @param local6        Local Ipv6 address
 287  * @param local_id      Local Identifier
 288  *
 289  * @return              New Link State Attributes
 290  */
 291 extern struct ls_attributes *ls_attributes_new(struct ls_node_id adv,
 292                                                struct in_addr local,
 293                                                struct in6_addr local6,
 294                                                uint32_t local_id);
 295
 296 /**
 297  * Remove SRLGs from Link State Attributes if defined.
 298  *
 299  * @param attr  Pointer to a valid Link State Attribute structure
 300  */
 301 extern void ls_attributes_srlg_del(struct ls_attributes *attr);
 302
 303 /**
 304  * Remove Link State Attributes. Data structure is freed.
 305  *
 306  * @param attr  Pointer to a valid Link State Attribute structure
 307  */
 308 extern void ls_attributes_del(struct ls_attributes *attr);
 309
 310 /**
 311  * Check if two Link State Attributes are equal. Note that this routine has the
 312  * same return value sense as '==' (which is different from a comparison).
 313  *
 314  * @param a1    First Link State Attributes to be compare
 315  * @param a2    Second Link State Attributes to be compare
 316  *
 317  * @return      1 if equal, 0 otherwise
 318  */
 319 extern int ls_attributes_same(struct ls_attributes *a1,
 320                               struct ls_attributes *a2);
 321
 322 /**
 323  * Create a new Link State Prefix. Structure is dynamically allocated.
 324  *
 325  * @param adv   Mandatory Link State Node ID i.e. advertise router ID
 326  * @param p     Mandatory Prefix
 327  *
 328  * @return      New Link State Prefix
 329  */
 330 extern struct ls_prefix *ls_prefix_new(struct ls_node_id adv, struct prefix p);
 331
 332 /**
 333  * Remove Link State Prefix. Data Structure is freed.
 334  *
 335  * @param pref  Pointer to a valid Link State Attribute Prefix.
 336  */
 337 extern void ls_prefix_del(struct ls_prefix *pref);
 338
 339 /**
 340  * Check if two Link State Prefix are equal. Note that this routine has the
 341  * same return value sense as '==' (which is different from a comparison).
 342  *
 343  * @param p1    First Link State Prefix to be compare
 344  * @param p2    Second Link State Prefix to be compare
 345  *
 346  * @return      1 if equal, 0 otherwise
 347  */
 348 extern int ls_prefix_same(struct ls_prefix *p1, struct ls_prefix *p2);
 349
 350 /**
 351  * In addition a Graph model is defined as an overlay on top of link state
 352  * database in order to ease Path Computation algorithm implementation.
 353  * Denoted G(V, E), a graph is composed by a list of Vertices (V) which
 354  * represents the network Node and a list of Edges (E) which represents node
 355  * Link. An additional list of prefixes (P) is also added.
 356  * A prefix (P) is also attached to the Vertex (V) which advertise it.
 357  *
 358  * Vertex (V) contains the list of outgoing Edges (E) that connect this Vertex
 359  * with its direct neighbors and the list of incoming Edges (E) that connect
 360  * the direct neighbors to this Vertex. Indeed, the Edge (E) is unidirectional,
 361  * thus, it is necessary to add 2 Edges to model a bidirectional relation
 362  * between 2 Vertices.
 363  *
 364  * Edge (E) contains the source and destination Vertex that this Edge
 365  * is connecting.
 366  *
 367  * A unique Key is used to identify both Vertices and Edges within the Graph.
 368  * An easy way to build this key is to used the IP address: i.e. loopback
 369  * address for Vertices and link IP address for Edges.
 370  *
 371  *      --------------     ---------------------------    --------------
 372  *      | Connected  |---->| Connected Edge Va to Vb |--->| Connected  |
 373  *  --->|  Vertex    |     ---------------------------    |  Vertex    |---->
 374  *      |            |                                    |            |
 375  *      | - Key (Va) |                                    | - Key (Vb) |
 376  *  <---| - Vertex   |     ---------------------------    | - Vertex   |<----
 377  *      |            |<----| Connected Edge Vb to Va |<---|            |
 378  *      --------------     ---------------------------    --------------
 379  *
 380  */
 381
 382 enum ls_status { UNSET = 0, NEW, UPDATE, DELETE, SYNC, ORPHAN };
 383 enum ls_type { GENERIC = 0, VERTEX, EDGE, SUBNET };
 384
 385 /* Link State Vertex structure */
 386 PREDECL_RBTREE_UNIQ(vertices);
 387 struct ls_vertex {
 388         enum ls_type type;              /* Link State Type */
 389         enum ls_status status;          /* Status of the Vertex in the TED */
 390         struct vertices_item entry;     /* Entry in RB Tree */
 391         uint64_t key;                   /* Unique Key identifier */
 392         struct ls_node *node;           /* Link State Node */
 393         struct list *incoming_edges;    /* List of incoming Link State links */
 394         struct list *outgoing_edges;    /* List of outgoing Link State links */
 395         struct list *prefixes;          /* List of advertised prefix */
 396 };
 397
 398 /* Link State Edge structure */
 399 PREDECL_RBTREE_UNIQ(edges);
 400 struct ls_edge {
 401         enum ls_type type;              /* Link State Type */
 402         enum ls_status status;          /* Status of the Edge in the TED */
 403         struct edges_item entry;        /* Entry in RB tree */
 404         uint64_t key;                   /* Unique Key identifier */
 405         struct ls_attributes *attributes;       /* Link State attributes */
 406         struct ls_vertex *source;       /* Pointer to the source Vertex */
 407         struct ls_vertex *destination;  /* Pointer to the destination Vertex */
 408 };
 409
 410 /* Link State Subnet structure */
 411 PREDECL_RBTREE_UNIQ(subnets);
 412 struct ls_subnet {
 413         enum ls_type type;              /* Link State Type */
 414         enum ls_status status;          /* Status of the Subnet in the TED */
 415         struct subnets_item entry;      /* Entry in RB tree */
 416         struct prefix key;              /* Unique Key identifier */
 417         struct ls_prefix *ls_pref;      /* Link State Prefix */
 418         struct ls_vertex *vertex;       /* Back pointer to the Vertex owner */
 419 };
 420
 421 /* Declaration of Vertices, Edges and Prefixes RB Trees */
 422 macro_inline int vertex_cmp(const struct ls_vertex *node1,
 423                             const struct ls_vertex *node2)
 424 {
 425         return numcmp(node1->key, node2->key);
 426 }
 427 DECLARE_RBTREE_UNIQ(vertices, struct ls_vertex, entry, vertex_cmp);
 428
 429 macro_inline int edge_cmp(const struct ls_edge *edge1,
 430                           const struct ls_edge *edge2)
 431 {
 432         return numcmp(edge1->key, edge2->key);
 433 }
 434 DECLARE_RBTREE_UNIQ(edges, struct ls_edge, entry, edge_cmp);
 435
 436 /*
 437  * Prefix comparison are done to the host part so, 10.0.0.1/24
 438  * and 10.0.0.2/24 are considered come different
 439  */
 440 macro_inline int subnet_cmp(const struct ls_subnet *a,
 441                             const struct ls_subnet *b)
 442 {
 443         if (a->key.family != b->key.family)
 444                 return numcmp(a->key.family, b->key.family);
 445
 446         if (a->key.prefixlen != b->key.prefixlen)
 447                 return numcmp(a->key.prefixlen, b->key.prefixlen);
 448
 449         if (a->key.family == AF_INET)
 450                 return memcmp(&a->key.u.val, &b->key.u.val, 4);
 451
 452         return memcmp(&a->key.u.val, &b->key.u.val, 16);
 453 }
 454 DECLARE_RBTREE_UNIQ(subnets, struct ls_subnet, entry, subnet_cmp);
 455
 456 /* Link State TED Structure */
 457 struct ls_ted {
 458         uint32_t key;                   /* Unique identifier */
 459         char name[MAX_NAME_LENGTH];     /* Name of this graph. Could be null */
 460         uint32_t as_number;             /* AS number of the modeled network */
 461         struct ls_vertex *self;         /* Vertex of the FRR instance */
 462         struct vertices_head vertices;  /* List of Vertices */
 463         struct edges_head edges;        /* List of Edges */
 464         struct subnets_head subnets;    /* List of Subnets */
 465 };
 466
 467 /* Generic Link State Element */
 468 struct ls_element {
 469         enum ls_type type;              /* Link State Element Type */
 470         enum ls_status status;          /* Link State Status in the TED */
 471         void *data;                     /* Link State payload */
 472 };
 473
 474 /**
 475  * Add new vertex to the Link State DB. Vertex is created from the Link State
 476  * Node. Vertex data structure is dynamically allocated.
 477  *
 478  * @param ted   Traffic Engineering Database structure
 479  * @param node  Link State Node
 480  *
 481  * @return      New Vertex or NULL in case of error
 482  */
 483 extern struct ls_vertex *ls_vertex_add(struct ls_ted *ted,
 484                                        struct ls_node *node);
 485
 486 /**
 487  * Delete Link State Vertex. This function clean internal Vertex lists (incoming
 488  * and outgoing Link State Edge and Link State Subnet). Vertex Data structure
 489  * is freed but not the Link State Node. Link State DB is not modified if Vertex
 490  * is NULL or not found in the Data Base. Note that referenced to Link State
 491  * Edges & SubNets are not removed as they could be connected to other Vertices.
 492  *
 493  * @param ted           Traffic Engineering Database structure
 494  * @param vertex        Link State Vertex to be removed
 495  */
 496 extern void ls_vertex_del(struct ls_ted *ted, struct ls_vertex *vertex);
 497
 498 /**
 499  * Delete Link State Vertex as ls_vertex_del() but also removed associated
 500  * Link State Node.
 501  *
 502  * @param ted           Traffic Engineering Database structure
 503  * @param vertex        Link State Vertex to be removed
 504  */
 505 extern void ls_vertex_del_all(struct ls_ted *ted, struct ls_vertex *vertex);
 506
 507 /**
 508  * Update Vertex with the Link State Node. A new vertex is created if no one
 509  * corresponds to the Link State Node.
 510  *
 511  * @param ted   Link State Data Base
 512  * @param node  Link State Node to be updated
 513  *
 514  * @return      Updated Link State Vertex or Null in case of error
 515  */
 516 extern struct ls_vertex *ls_vertex_update(struct ls_ted *ted,
 517                                           struct ls_node *node);
 518
 519 /**
 520  * Clean Vertex structure by removing all Edges and Subnets marked as ORPHAN
 521  * from this vertex. Link State Update message is sent if zclient is not NULL.
 522  *
 523  * @param ted           Link State Data Base
 524  * @param vertex        Link State Vertex to be cleaned
 525  * @param zclient       Reference to Zebra Client
 526  */
 527 extern void ls_vertex_clean(struct ls_ted *ted, struct ls_vertex *vertex,
 528                             struct zclient *zclient);
 529
 530 /**
 531  * This function convert the ISIS ISO system ID into a 64 bits unsigned integer
 532  * following the architecture dependent byte order.
 533  *
 534  * @param sysid The ISO system ID
 535  * @return      Key as 64 bits unsigned integer
 536  */
 537 extern uint64_t sysid_to_key(const uint8_t sysid[ISO_SYS_ID_LEN]);
 538
 539 /**
 540  * Find Vertex in the Link State DB by its unique key.
 541  *
 542  * @param ted   Link State Data Base
 543  * @param key   Vertex Key different from 0
 544  *
 545  * @return      Vertex if found, NULL otherwise
 546  */
 547 extern struct ls_vertex *ls_find_vertex_by_key(struct ls_ted *ted,
 548                                                const uint64_t key);
 549
 550 /**
 551  * Find Vertex in the Link State DB by its Link State Node.
 552  *
 553  * @param ted   Link State Data Base
 554  * @param nid   Link State Node ID
 555  *
 556  * @return      Vertex if found, NULL otherwise
 557  */
 558 extern struct ls_vertex *ls_find_vertex_by_id(struct ls_ted *ted,
 559                                               struct ls_node_id nid);
 560
 561 /**
 562  * Check if two Vertices are equal. Note that this routine has the same return
 563  * value sense as '==' (which is different from a comparison).
 564  *
 565  * @param v1    First vertex to compare
 566  * @param v2    Second vertex to compare
 567  *
 568  * @return      1 if equal, 0 otherwise
 569  */
 570 extern int ls_vertex_same(struct ls_vertex *v1, struct ls_vertex *v2);
 571
 572 /**
 573  * Add new Edge to the Link State DB. Edge is created from the Link State
 574  * Attributes. Edge data structure is dynamically allocated.
 575  *
 576  * @param ted           Link State Data Base
 577  * @param attributes    Link State attributes
 578  *
 579  * @return              New Edge or NULL in case of error
 580  */
 581 extern struct ls_edge *ls_edge_add(struct ls_ted *ted,
 582                                    struct ls_attributes *attributes);
 583
 584 /**
 585  * Update the Link State Attributes information of an existing Edge. If there is
 586  * no corresponding Edge in the Link State Data Base, a new Edge is created.
 587  *
 588  * @param ted           Link State Data Base
 589  * @param attributes    Link State Attributes
 590  *
 591  * @return              Updated Link State Edge, or NULL in case of error
 592  */
 593 extern struct ls_edge *ls_edge_update(struct ls_ted *ted,
 594                                       struct ls_attributes *attributes);
 595
 596 /**
 597  * Check if two Edges are equal. Note that this routine has the same return
 598  * value sense as '==' (which is different from a comparison).
 599  *
 600  * @param e1    First edge to compare
 601  * @param e2    Second edge to compare
 602  *
 603  * @return      1 if equal, 0 otherwise
 604  */
 605 extern int ls_edge_same(struct ls_edge *e1, struct ls_edge *e2);
 606
 607 /**
 608  * Remove Edge from the Link State DB. Edge data structure is freed but not the
 609  * Link State Attributes data structure. Link State DB is not modified if Edge
 610  * is NULL or not found in the Data Base.
 611  *
 612  * @param ted   Link State Data Base
 613  * @param edge  Edge to be removed
 614  */
 615 extern void ls_edge_del(struct ls_ted *ted, struct ls_edge *edge);
 616
 617 /**
 618  * Remove Edge and associated Link State Attributes from the Link State DB.
 619  * Link State DB is not modified if Edge is NULL or not found.
 620  *
 621  * @param ted   Link State Data Base
 622  * @param edge  Edge to be removed
 623  */
 624 extern void ls_edge_del_all(struct ls_ted *ted, struct ls_edge *edge);
 625
 626 /**
 627  * Find Edge in the Link State Data Base by Edge key.
 628  *
 629  * @param ted   Link State Data Base
 630  * @param key   Edge key
 631  *
 632  * @return      Edge if found, NULL otherwise
 633  */
 634 extern struct ls_edge *ls_find_edge_by_key(struct ls_ted *ted,
 635                                            const uint64_t key);
 636
 637 /**
 638  * Find Edge in the Link State Data Base by the source (local IPv4 or IPv6
 639  * address or local ID) informations of the Link State Attributes
 640  *
 641  * @param ted           Link State Data Base
 642  * @param attributes    Link State Attributes
 643  *
 644  * @return              Edge if found, NULL otherwise
 645  */
 646 extern struct ls_edge *
 647 ls_find_edge_by_source(struct ls_ted *ted, struct ls_attributes *attributes);
 648
 649 /**
 650  * Find Edge in the Link State Data Base by the destination (remote IPv4 or IPv6
 651  * address of remote ID) information of the Link State Attributes
 652  *
 653  * @param ted           Link State Data Base
 654  * @param attributes    Link State Attributes
 655  *
 656  * @return              Edge if found, NULL otherwise
 657  */
 658 extern struct ls_edge *
 659 ls_find_edge_by_destination(struct ls_ted *ted,
 660                             struct ls_attributes *attributes);
 661
 662 /**
 663  * Add new Subnet to the Link State DB. Subnet is created from the Link State
 664  * prefix. Subnet data structure is dynamically allocated.
 665  *
 666  * @param ted   Link State Data Base
 667  * @param pref  Link State Prefix
 668  *
 669  * @return      New Subnet
 670  */
 671 extern struct ls_subnet *ls_subnet_add(struct ls_ted *ted,
 672                                        struct ls_prefix *pref);
 673
 674 /**
 675  * Update the Link State Prefix information of an existing Subnet. If there is
 676  * no corresponding Subnet in the Link State Data Base, a new Subnet is created.
 677  *
 678  * @param ted   Link State Data Base
 679  * @param pref  Link State Prefix
 680  *
 681  * @return      Updated Link State Subnet, or NULL in case of error
 682  */
 683 extern struct ls_subnet *ls_subnet_update(struct ls_ted *ted,
 684                                           struct ls_prefix *pref);
 685
 686 /**
 687  * Check if two Subnets are equal. Note that this routine has the same return
 688  * value sense as '==' (which is different from a comparison).
 689  *
 690  * @param s1    First subnet to compare
 691  * @param s2    Second subnet to compare
 692  *
 693  * @return      1 if equal, 0 otherwise
 694  */
 695 extern int ls_subnet_same(struct ls_subnet *s1, struct ls_subnet *s2);
 696
 697 /**
 698  * Remove Subnet from the Link State DB. Subnet data structure is freed but
 699  * not the Link State prefix data structure. Link State DB is not modified
 700  * if Subnet is NULL or not found in the Data Base.
 701  *
 702  * @param ted           Link State Data Base
 703  * @param subnet        Subnet to be removed
 704  */
 705 extern void ls_subnet_del(struct ls_ted *ted, struct ls_subnet *subnet);
 706
 707 /**
 708  * Remove Subnet and the associated Link State Prefix from the Link State DB.
 709  * Link State DB is not modified if Subnet is NULL or not found.
 710  *
 711  * @param ted           Link State Data Base
 712  * @param subnet        Subnet to be removed
 713  */
 714 extern void ls_subnet_del_all(struct ls_ted *ted, struct ls_subnet *subnet);
 715
 716 /**
 717  * Find Subnet in the Link State Data Base by prefix.
 718  *
 719  * @param ted           Link State Data Base
 720  * @param prefix        Link State Prefix
 721  *
 722  * @return              Subnet if found, NULL otherwise
 723  */
 724 extern struct ls_subnet *ls_find_subnet(struct ls_ted *ted,
 725                                         const struct prefix prefix);
 726
 727 /**
 728  * Create a new Link State Data Base.
 729  *
 730  * @param key   Unique key of the data base. Must be different from 0
 731  * @param name  Name of the data base (may be NULL)
 732  * @param asn   AS Number for this data base. 0 if unknown
 733  *
 734  * @return      New Link State Database or NULL in case of error
 735  */
 736 extern struct ls_ted *ls_ted_new(const uint32_t key, const char *name,
 737                                  uint32_t asn);
 738
 739 /**
 740  * Delete existing Link State Data Base. Vertices, Edges, and Subnets are not
 741  * removed.
 742  *
 743  * @param ted   Link State Data Base
 744  */
 745 extern void ls_ted_del(struct ls_ted *ted);
 746
 747 /**
 748  * Delete all Link State Vertices, Edges and SubNets and the Link State DB.
 749  *
 750  * @param ted   Link State Data Base
 751  */
 752 extern void ls_ted_del_all(struct ls_ted **ted);
 753
 754 /**
 755  * Clean Link State Data Base by removing all Vertices, Edges and SubNets marked
 756  * as ORPHAN.
 757  *
 758  * @param ted   Link State Data Base
 759  */
 760 extern void ls_ted_clean(struct ls_ted *ted);
 761
 762 /**
 763  * Connect Source and Destination Vertices by given Edge. Only non NULL source
 764  * and destination vertices are connected.
 765  *
 766  * @param src   Link State Source Vertex
 767  * @param dst   Link State Destination Vertex
 768  * @param edge  Link State Edge. Must not be NULL
 769  */
 770 extern void ls_connect_vertices(struct ls_vertex *src, struct ls_vertex *dst,
 771                                 struct ls_edge *edge);
 772
 773 /**
 774  * Connect Link State Edge to the Link State Vertex which could be a Source or
 775  * a Destination Vertex.
 776  *
 777  * @param vertex        Link State Vertex to be connected. Must not be NULL
 778  * @param edge          Link State Edge connection. Must not be NULL
 779  * @param source        True for a Source, false for a Destination Vertex
 780  */
 781 extern void ls_connect(struct ls_vertex *vertex, struct ls_edge *edge,
 782                        bool source);
 783
 784 /**
 785  * Disconnect Link State Edge from the Link State Vertex which could be a
 786  * Source or a Destination Vertex.
 787  *
 788  * @param vertex        Link State Vertex to be connected. Must not be NULL
 789  * @param edge          Link State Edge connection. Must not be NULL
 790  * @param source        True for a Source, false for a Destination Vertex
 791  */
 792 extern void ls_disconnect(struct ls_vertex *vertex, struct ls_edge *edge,
 793                           bool source);
 794
 795 /**
 796  * Disconnect Link State Edge from both Source and Destination Vertex.
 797  *
 798  * @param edge          Link State Edge to be disconnected
 799  */
 800 extern void ls_disconnect_edge(struct ls_edge *edge);
 801
 802
 803 /**
 804  * The Link State Message is defined to convey Link State parameters from
 805  * the routing protocol (OSPF or IS-IS) to other daemons e.g. BGP.
 806  *
 807  * The structure is composed of:
 808  *  - Event of the message:
 809  *    - Sync: Send the whole LS DB following a request
 810  *    - Add: Send the a new Link State element
 811  *    -  Update: Send an update of an existing Link State element
 812  *    - Delete: Indicate that the given Link State element is removed
 813  *  - Type of Link State element: Node, Attribute or Prefix
 814  *  - Remote node id when known
 815  *  - Data: Node, Attributes or Prefix
 816  *
 817  * A Link State Message can carry only one Link State Element (Node, Attributes
 818  * of Prefix) at once, and only one Link State Message is sent through ZAPI
 819  * Opaque Link State type at once.
 820  */
 821
 822 /* ZAPI Opaque Link State Message Event */
 823 #define LS_MSG_EVENT_UNDEF      0
 824 #define LS_MSG_EVENT_SYNC       1
 825 #define LS_MSG_EVENT_ADD        2
 826 #define LS_MSG_EVENT_UPDATE     3
 827 #define LS_MSG_EVENT_DELETE     4
 828
 829 /* ZAPI Opaque Link State Message sub-Type */
 830 #define LS_MSG_TYPE_NODE        1
 831 #define LS_MSG_TYPE_ATTRIBUTES  2
 832 #define LS_MSG_TYPE_PREFIX      3
 833
 834 /* Link State Message */
 835 struct ls_message {
 836         uint8_t event;          /* Message Event: Sync, Add, Update, Delete */
 837         uint8_t type;           /* Message Data Type: Node, Attribute, Prefix */
 838         struct ls_node_id remote_id;    /* Remote Link State Node ID */
 839         union {
 840                 struct ls_node *node;           /* Link State Node */
 841                 struct ls_attributes *attr;     /* Link State Attributes */
 842                 struct ls_prefix *prefix;       /* Link State Prefix */
 843         } data;
 844 };
 845
 846 /**
 847  * Register Link State daemon as a server or client for Zebra OPAQUE API.
 848  *
 849  * @param zclient  Zebra client structure
 850  * @param server   Register daemon as a server (true) or as a client (false)
 851  *
 852  * @return         0 if success, -1 otherwise
 853  */
 854 extern int ls_register(struct zclient *zclient, bool server);
 855
 856 /**
 857  * Unregister Link State daemon as a server or client for Zebra OPAQUE API.
 858  *
 859  * @param zclient  Zebra client structure
 860  * @param server   Unregister daemon as a server (true) or as a client (false)
 861  *
 862  * @return         0 if success, -1 otherwise
 863  */
 864 extern int ls_unregister(struct zclient *zclient, bool server);
 865
 866 /**
 867  * Send Link State SYNC message to request the complete Link State Database.
 868  *
 869  * @param zclient       Zebra client
 870  *
 871  * @return              0 if success, -1 otherwise
 872  */
 873 extern int ls_request_sync(struct zclient *zclient);
 874
 875 /**
 876  * Parse Link State Message from stream. Used this function once receiving a
 877  * new ZAPI Opaque message of type Link State.
 878  *
 879  * @param s     Stream buffer. Must not be NULL.
 880  *
 881  * @return      New Link State Message or NULL in case of error
 882  */
 883 extern struct ls_message *ls_parse_msg(struct stream *s);
 884
 885 /**
 886  * Delete existing message. Data structure is freed.
 887  *
 888  * @param msg   Link state message to be deleted
 889  */
 890 extern void ls_delete_msg(struct ls_message *msg);
 891
 892 /**
 893  * Send Link State Message as new ZAPI Opaque message of type Link State.
 894  * If destination is not NULL, message is sent as Unicast otherwise it is
 895  * broadcast to all registered daemon.
 896  *
 897  * @param zclient       Zebra Client
 898  * @param msg           Link State Message to be sent
 899  * @param dst           Destination daemon for unicast message,
 900  *                      NULL for broadcast message
 901  *
 902  * @return              0 on success, -1 otherwise
 903  */
 904 extern int ls_send_msg(struct zclient *zclient, struct ls_message *msg,
 905                        struct zapi_opaque_reg_info *dst);
 906
 907 /**
 908  * Create a new Link State Message from a Link State Vertex. If Link State
 909  * Message is NULL, a new data structure is dynamically allocated.
 910  *
 911  * @param msg           Link State Message to be filled or NULL
 912  * @param vertex        Link State Vertex. Must not be NULL
 913  *
 914  * @return              New Link State Message msg parameter is NULL or pointer
 915  *                      to the provided Link State Message
 916  */
 917 extern struct ls_message *ls_vertex2msg(struct ls_message *msg,
 918                                         struct ls_vertex *vertex);
 919
 920 /**
 921  * Create a new Link State Message from a Link State Edge. If Link State
 922  * Message is NULL, a new data structure is dynamically allocated.
 923  *
 924  * @param msg           Link State Message to be filled or NULL
 925  * @param edge          Link State Edge. Must not be NULL
 926  *
 927  * @return              New Link State Message msg parameter is NULL or pointer
 928  *                      to the provided Link State Message
 929  */
 930 extern struct ls_message *ls_edge2msg(struct ls_message *msg,
 931                                       struct ls_edge *edge);
 932
 933 /**
 934  * Create a new Link State Message from a Link State Subnet. If Link State
 935  * Message is NULL, a new data structure is dynamically allocated.
 936  *
 937  * @param msg           Link State Message to be filled or NULL
 938  * @param subnet        Link State Subnet. Must not be NULL
 939  *
 940  * @return              New Link State Message msg parameter is NULL or pointer
 941  *                      to the provided Link State Message
 942  */
 943 extern struct ls_message *ls_subnet2msg(struct ls_message *msg,
 944                                         struct ls_subnet *subnet);
 945
 946 /**
 947  * Convert Link State Message into Vertex and update TED accordingly to
 948  * the message event: SYNC, ADD, UPDATE or DELETE.
 949  *
 950  * @param ted           Link State Database
 951  * @param msg           Link State Message
 952  * @param delete        True to delete the Link State Vertex from the Database,
 953  *                      False otherwise. If true, return value is NULL in case
 954  *                      of deletion.
 955  *
 956  * @return      Vertex if success, NULL otherwise or if Vertex is removed
 957  */
 958 extern struct ls_vertex *ls_msg2vertex(struct ls_ted *ted,
 959                                        struct ls_message *msg, bool delete);
 960
 961 /**
 962  * Convert Link State Message into Edge and update TED accordingly to
 963  * the message event: SYNC, ADD, UPDATE or DELETE.
 964  *
 965  * @param ted           Link State Database
 966  * @param msg           Link State Message
 967  * @param delete        True to delete the Link State Edge from the Database,
 968  *                      False otherwise. If true, return value is NULL in case
 969  *                      of deletion.
 970  *
 971  * @return      Edge if success, NULL otherwise or if Edge is removed
 972  */
 973 extern struct ls_edge *ls_msg2edge(struct ls_ted *ted, struct ls_message *msg,
 974                                    bool delete);
 975
 976 /**
 977  * Convert Link State Message into Subnet and update TED accordingly to
 978  * the message event: SYNC, ADD, UPDATE or DELETE.
 979  *
 980  * @param ted           Link State Database
 981  * @param msg           Link State Message
 982  * @param delete        True to delete the Link State Subnet from the Database,
 983  *                      False otherwise. If true, return value is NULL in case
 984  *                      of deletion.
 985  *
 986  * @return      Subnet if success, NULL otherwise or if Subnet is removed
 987  */
 988 extern struct ls_subnet *ls_msg2subnet(struct ls_ted *ted,
 989                                        struct ls_message *msg, bool delete);
 990
 991 /**
 992  * Convert Link State Message into Link State element (Vertex, Edge or Subnet)
 993  * and update TED accordingly to the message event: SYNC, ADD, UPDATE or DELETE.
 994  *
 995  * @param ted           Link State Database
 996  * @param msg           Link State Message
 997  * @param delete        True to delete the Link State Element from the Database,
 998  *                      False otherwise. If true, return value is NULL in case
 999  *                      of deletion.
1000  *
1001  * @return      Element if success, NULL otherwise or if Element is removed
1002  */
1003 extern struct ls_element *ls_msg2ted(struct ls_ted *ted, struct ls_message *msg,
1004                                      bool delete);
1005
1006 /**
1007  * Convert stream buffer into Link State element (Vertex, Edge or Subnet) and
1008  * update TED accordingly to the message event: SYNC, ADD, UPDATE or DELETE.
1009  *
1010  * @param ted           Link State Database
1011  * @param s             Stream buffer
1012  * @param delete        True to delete the Link State Element from the Database,
1013  *                      False otherwise. If true, return value is NULL in case
1014  *                      of deletion.
1015  *
1016  * @return      Element if success, NULL otherwise or if Element is removed
1017  */
1018 extern struct ls_element *ls_stream2ted(struct ls_ted *ted, struct stream *s,
1019                                         bool delete);
1020
1021 /**
1022  * Send all the content of the Link State Data Base to the given destination.
1023  * Link State content is sent is this order: Vertices, Edges, Subnet.
1024  * This function must be used when a daemon request a Link State Data Base
1025  * Synchronization.
1026  *
1027  * @param ted           Link State Data Base. Must not be NULL
1028  * @param zclient       Zebra Client. Must not be NULL
1029  * @param dst           Destination FRR daemon. Must not be NULL
1030  *
1031  * @return              0 on success, -1 otherwise
1032  */
1033 extern int ls_sync_ted(struct ls_ted *ted, struct zclient *zclient,
1034                        struct zapi_opaque_reg_info *dst);
1035
1036 struct json_object;
1037 struct vty;
1038 /**
1039  * Show Link State Vertex information. If both vty and json are specified,
1040  * Json format output supersedes standard vty output.
1041  *
1042  * @param vertex        Link State Vertex to show. Must not be NULL
1043  * @param vty           Pointer to vty output, could be NULL
1044  * @param json          Pointer to json output, could be NULL
1045  * @param verbose       Set to true for more detail
1046  */
1047 extern void ls_show_vertex(struct ls_vertex *vertex, struct vty *vty,
1048                            struct json_object *json, bool verbose);
1049
1050 /**
1051  * Show all Link State Vertices information. If both vty and json are specified,
1052  * Json format output supersedes standard vty output.
1053  *
1054  * @param ted           Link State Data Base. Must not be NULL
1055  * @param vty           Pointer to vty output, could be NULL
1056  * @param json          Pointer to json output, could be NULL
1057  * @param verbose       Set to true for more detail
1058  */
1059 extern void ls_show_vertices(struct ls_ted *ted, struct vty *vty,
1060                              struct json_object *json, bool verbose);
1061
1062 /**
1063  * Show Link State Edge information. If both vty and json are specified,
1064  * Json format output supersedes standard vty output.
1065  *
1066  * @param edge          Link State Edge to show. Must not be NULL
1067  * @param vty           Pointer to vty output, could be NULL
1068  * @param json          Pointer to json output, could be NULL
1069  * @param verbose       Set to true for more detail
1070  */
1071 extern void ls_show_edge(struct ls_edge *edge, struct vty *vty,
1072                          struct json_object *json, bool verbose);
1073
1074 /**
1075  * Show all Link State Edges information. If both vty and json are specified,
1076  * Json format output supersedes standard vty output.
1077  *
1078  * @param ted           Link State Data Base. Must not be NULL
1079  * @param vty           Pointer to vty output, could be NULL
1080  * @param json          Pointer to json output, could be NULL
1081  * @param verbose       Set to true for more detail
1082  */
1083 extern void ls_show_edges(struct ls_ted *ted, struct vty *vty,
1084                           struct json_object *json, bool verbose);
1085
1086 /**
1087  * Show Link State Subnets information. If both vty and json are specified,
1088  * Json format output supersedes standard vty output.
1089  *
1090  * @param subnet        Link State Subnet to show. Must not be NULL
1091  * @param vty           Pointer to vty output, could be NULL
1092  * @param json          Pointer to json output, could be NULL
1093  * @param verbose       Set to true for more detail
1094  */
1095 extern void ls_show_subnet(struct ls_subnet *subnet, struct vty *vty,
1096                            struct json_object *json, bool verbose);
1097
1098 /**
1099  * Show all Link State Subnet information. If both vty and json are specified,
1100  * Json format output supersedes standard vty output.
1101  *
1102  * @param ted           Link State Data Base. Must not be NULL
1103  * @param vty           Pointer to vty output, could be NULL
1104  * @param json          Pointer to json output, could be NULL
1105  * @param verbose       Set to true for more detail
1106  */
1107 extern void ls_show_subnets(struct ls_ted *ted, struct vty *vty,
1108                             struct json_object *json, bool verbose);
1109
1110 /**
1111  * Show Link State Data Base information. If both vty and json are specified,
1112  * Json format output supersedes standard vty output.
1113  *
1114  * @param ted           Link State Data Base to show. Must not be NULL
1115  * @param vty           Pointer to vty output, could be NULL
1116  * @param json          Pointer to json output, could be NULL
1117  * @param verbose       Set to true for more detail
1118  */
1119 extern void ls_show_ted(struct ls_ted *ted, struct vty *vty,
1120                         struct json_object *json, bool verbose);
1121
1122 /**
1123  * Dump all Link State Data Base elements for debugging purposes
1124  *
1125  * @param ted   Link State Data Base. Must not be NULL
1126  *
1127  */
1128 extern void ls_dump_ted(struct ls_ted *ted);
1129
1130 #ifdef __cplusplus
1131 }
1132 #endif
1133
1134 #endif /* _FRR_LINK_STATE_H_ */