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