lib/link_state.h

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