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 /* Link State Common definitions */
  57 #define MAX_NAME_LENGTH         256
  58 #define ISO_SYS_ID_LEN          6
  59
  60 /* Type of Node */
  61 enum ls_node_type {
  62         STANDARD,       /* a P or PE node */
  63         ABR,            /* an Array Border Node */
  64         ASBR,           /* an Autonomous System Border Node */
  65         PSEUDO,         /* a Pseudo Node */
  66 };
  67
  68 /* Origin of the Link State information */
  69 enum ls_origin {NONE = 0, ISIS_L1, ISIS_L2, OSPFv2, DIRECT, STATIC};
  70
  71 /**
  72  * Link State Node Identifier as:
  73  *  - IPv4 address + Area ID for OSPF
  74  *  - ISO System ID + ISIS Level for ISIS
  75  */
  76 struct ls_node_id {
  77         enum ls_origin origin;          /* Origin of the LS information */
  78         union {
  79                 struct {
  80                         struct in_addr addr;            /* OSPF Router IS */
  81                         struct in_addr area_id;         /* OSPF Area ID */
  82                 } ip;
  83                 struct {
  84                         uint8_t sys_id[ISO_SYS_ID_LEN]; /* ISIS System ID */
  85                         uint8_t level;                  /* ISIS Level */
  86                         uint8_t padding;
  87                 } iso;
  88         } id __attribute__((aligned(8)));
  89 };
  90
  91 /* Link State flags to indicate which Node parameters are valid */
  92 #define LS_NODE_UNSET           0x0000
  93 #define LS_NODE_NAME            0x0001
  94 #define LS_NODE_ROUTER_ID       0x0002
  95 #define LS_NODE_ROUTER_ID6      0x0004
  96 #define LS_NODE_FLAG            0x0008
  97 #define LS_NODE_TYPE            0x0010
  98 #define LS_NODE_AS_NUMBER       0x0020
  99 #define LS_NODE_SR              0x0040
 100 #define LS_NODE_SRLB            0x0080
 101 #define LS_NODE_MSD             0x0100
 102
 103 /* Link State Node structure */
 104 struct ls_node {
 105         uint16_t flags;                 /* Flag for parameters validity */
 106         struct ls_node_id adv;          /* Adv. Router of this Link State */
 107         char name[MAX_NAME_LENGTH];     /* Name of the Node (IS-IS only) */
 108         struct in_addr router_id;       /* IPv4 Router ID */
 109         struct in6_addr router6_id;     /* IPv6 Router ID */
 110         uint8_t node_flag;              /* IS-IS or OSPF Node flag */
 111         enum node_type type;            /* Type of Node */
 112         uint32_t as_number;             /* Local or neighbor AS number */
 113         struct {                        /* Segment Routing Global Block */
 114                 uint32_t lower_bound;           /* MPLS label lower bound */
 115                 uint32_t range_size;            /* MPLS label range size */
 116                 uint8_t flag;                   /* IS-IS SRGB flags */
 117         } srgb;
 118 #define LS_NODE_SRGB_SIZE       9
 119         struct {                        /* Segment Routing Local Block */
 120                 uint32_t lower_bound;           /* MPLS label lower bound */
 121                 uint32_t range_size;            /* MPLS label range size */
 122         } srlb;
 123 #define LS_NODE_SRLB_SIZE       8
 124         uint8_t algo[2];                /* Segment Routing Algorithms */
 125         uint8_t msd;                    /* Maximum Stack Depth */
 126 };
 127
 128 /* Link State flags to indicate which Attribute parameters are valid */
 129 #define LS_ATTR_UNSET           0x00000000
 130 #define LS_ATTR_NAME            0x00000001
 131 #define LS_ATTR_METRIC          0x00000002
 132 #define LS_ATTR_TE_METRIC       0x00000004
 133 #define LS_ATTR_ADM_GRP         0x00000008
 134 #define LS_ATTR_LOCAL_ADDR      0x00000010
 135 #define LS_ATTR_NEIGH_ADDR      0x00000020
 136 #define LS_ATTR_LOCAL_ADDR6     0x00000040
 137 #define LS_ATTR_NEIGH_ADDR6     0x00000080
 138 #define LS_ATTR_LOCAL_ID        0x00000100
 139 #define LS_ATTR_NEIGH_ID        0x00000200
 140 #define LS_ATTR_MAX_BW          0x00000400
 141 #define LS_ATTR_MAX_RSV_BW      0x00000800
 142 #define LS_ATTR_UNRSV_BW        0x00001000
 143 #define LS_ATTR_REMOTE_AS       0x00002000
 144 #define LS_ATTR_REMOTE_ADDR     0x00004000
 145 #define LS_ATTR_REMOTE_ADDR6    0x00008000
 146 #define LS_ATTR_DELAY           0x00010000
 147 #define LS_ATTR_MIN_MAX_DELAY   0x00020000
 148 #define LS_ATTR_JITTER          0x00040000
 149 #define LS_ATTR_PACKET_LOSS     0x00080000
 150 #define LS_ATTR_AVA_BW          0x00100000
 151 #define LS_ATTR_RSV_BW          0x00200000
 152 #define LS_ATTR_USE_BW          0x00400000
 153 #define LS_ATTR_ADJ_SID         0x00800000
 154 #define LS_ATTR_BCK_ADJ_SID     0x01000000
 155 #define LS_ATTR_SRLG            0x02000000
 156
 157 /* Link State Attributes */
 158 struct ls_attributes {
 159         uint32_t flags;                 /* Flag for parameters validity */
 160         struct ls_node_id adv;          /* Adv. Router of this Link State */
 161         char name[MAX_NAME_LENGTH];     /* Name of the Edge. Could be null */
 162         struct {                        /* Standard TE metrics */
 163                 uint32_t metric;                /* IGP standard metric */
 164                 uint32_t te_metric;             /* Traffic Engineering metric */
 165                 uint32_t admin_group;           /* Administrative Group */
 166                 struct in_addr local;           /* Local IPv4 address */
 167                 struct in_addr remote;          /* Remote IPv4 address */
 168                 struct in6_addr local6;         /* Local IPv6 address */
 169                 struct in6_addr remote6;        /* Remote IPv6 address */
 170                 uint32_t local_id;              /* Local Identifier */
 171                 uint32_t remote_id;             /* Remote Identifier */
 172                 float max_bw;                   /* Maximum Link Bandwidth */
 173                 float max_rsv_bw;               /* Maximum Reservable BW */
 174                 float unrsv_bw[8];              /* Unreserved BW per CT (8) */
 175                 uint32_t remote_as;             /* Remote AS number */
 176                 struct in_addr remote_addr;     /* Remote IPv4 address */
 177                 struct in6_addr remote_addr6;   /* Remote IPv6 address */
 178         } standard;
 179 #define LS_ATTR_STANDARD_SIZE   124
 180         struct {                /* Extended TE Metrics */
 181                 uint32_t delay;         /* Unidirectional average delay */
 182                 uint32_t min_delay;     /* Unidirectional minimum delay */
 183                 uint32_t max_delay;     /* Unidirectional maximum delay */
 184                 uint32_t jitter;        /* Unidirectional delay variation */
 185                 uint32_t pkt_loss;      /* Unidirectional packet loss */
 186                 float ava_bw;           /* Available Bandwidth */
 187                 float rsv_bw;           /* Reserved Bandwidth */
 188                 float used_bw;          /* Utilized Bandwidth */
 189         } extended;
 190 #define LS_ATTR_EXTENDED_SIZE   32
 191         struct {                /* (LAN)-Adjacency SID for OSPF */
 192                 uint32_t sid;           /* SID as MPLS label or index */
 193                 uint8_t flags;          /* Flags */
 194                 uint8_t weight;         /* Administrative weight */
 195                 union {
 196                         struct in_addr addr;    /* Neighbor @IP for OSPF */
 197                         uint8_t sysid[ISO_SYS_ID_LEN]; /* or Sys-ID for ISIS */
 198                 } neighbor;
 199         } adj_sid[2];           /* Primary & Backup (LAN)-Adj. SID */
 200 #define LS_ATTR_ADJ_SID_SIZE    120
 201         uint32_t *srlgs;        /* List of Shared Risk Link Group */
 202         uint8_t srlg_len;       /* number of SRLG in the list */
 203 };
 204
 205 /* Link State flags to indicate which Prefix parameters are valid */
 206 #define LS_PREF_UNSET           0x00
 207 #define LS_PREF_IGP_FLAG        0x01
 208 #define LS_PREF_ROUTE_TAG       0x02
 209 #define LS_PREF_EXTENDED_TAG    0x04
 210 #define LS_PREF_METRIC          0x08
 211 #define LS_PREF_SR              0x10
 212
 213 /* Link State Prefix */
 214 struct ls_prefix {
 215         uint8_t flags;                  /* Flag for parameters validity */
 216         struct ls_node_id adv;          /* Adv. Router of this Link State */
 217         struct prefix pref;             /* IPv4 or IPv6 prefix */
 218         uint8_t igp_flag;               /* IGP Flags associated to the prefix */
 219         uint32_t route_tag;             /* IGP Route Tag */
 220         uint64_t extended_tag;          /* IGP Extended Route Tag */
 221         uint32_t metric;                /* Route metric for this prefix */
 222         struct {
 223                 uint32_t sid;           /* Segment Routing ID */
 224                 uint8_t sid_flag;       /* Segment Routing Flags */
 225                 uint8_t algo;           /* Algorithm for Segment Routing */
 226         } sr;
 227 };
 228
 229 /**
 230  * Create a new Link State Node. Structure is dynamically allocated.
 231  *
 232  * @param adv   Mandatory Link State Node ID i.e. advertise router information
 233  * @param rid   Router ID as IPv4 address
 234  * @param rid6  Router ID as IPv6 address
 235  *
 236  * @return      New Link State Node
 237  */
 238 extern struct ls_node *ls_node_new(struct ls_node_id adv, struct in_addr rid,
 239                                    struct in6_addr rid6);
 240
 241 /**
 242  * Remove Link State Node. Data structure is freed.
 243  *
 244  * @param node        Pointer to a valid Link State Node structure
 245  */
 246 extern void ls_node_del(struct ls_node *node);
 247
 248 /**
 249  * Check if two Link State Nodes are equal. Note that this routine has the same
 250  * return value sense as '==' (which is different from a comparison).
 251  *
 252  * @param n1    First Link State Node to be compare
 253  * @param n2    Second Link State Node to be compare
 254  *
 255  * @return      1 if equal, 0 otherwise
 256  */
 257 extern int ls_node_same(struct ls_node *n1, struct ls_node *n2);
 258
 259 /**
 260  * Create a new Link State Attributes. Structure is dynamically allocated.
 261  * At least one of parameters MUST be valid and not equal to 0.
 262  *
 263  * @param adv           Mandatory Link State Node ID i.e. advertise router ID
 264  * @param local         Local IPv4 address
 265  * @param local6        Local Ipv6 address
 266  * @param local_id      Local Identifier
 267  *
 268  * @return              New Link State Attributes
 269  */
 270 extern struct ls_attributes *ls_attributes_new(struct ls_node_id adv,
 271                                                struct in_addr local,
 272                                                struct in6_addr local6,
 273                                                uint32_t local_id);
 274
 275 /**
 276  * Remove Link State Attributes. Data structure is freed.
 277  *
 278  * @param attr           Pointer to a valid Link State Attribute structure
 279  */
 280 extern void ls_attributes_del(struct ls_attributes *attr);
 281
 282 /**
 283  * Check if two Link State Attributes are equal. Note that this routine has the
 284  * same return value sense as '==' (which is different from a comparison).
 285  *
 286  * @param a1    First Link State Attributes to be compare
 287  * @param a2    Second Link State Attributes to be compare
 288  *
 289  * @return      1 if equal, 0 otherwise
 290  */
 291 extern int ls_attributes_same(struct ls_attributes *a1,
 292                               struct ls_attributes *a2);
 293
 294 /**
 295  * In addition a Graph model is defined as an overlay on top of link state
 296  * database in order to ease Path Computation algorithm implementation.
 297  * Denoted G(V, E), a graph is composed by a list of Vertices (V) which
 298  * represents the network Node and a list of Edges (E) which represents node
 299  * Link. An additional list of prefixes (P) is also added.
 300  * A prefix (P) is also attached to the Vertex (V) which advertise it.
 301  *
 302  * Vertex (V) contains the list of outgoing Edges (E) that connect this Vertex
 303  * with its direct neighbors and the list of incoming Edges (E) that connect
 304  * the direct neighbors to this Vertex. Indeed, the Edge (E) is unidirectional,
 305  * thus, it is necessary to add 2 Edges to model a bidirectional relation
 306  * between 2 Vertices.
 307  *
 308  * Edge (E) contains the source and destination Vertex that this Edge
 309  * is connecting.
 310  *
 311  * A unique Key is used to identify both Vertices and Edges within the Graph.
 312  * An easy way to build this key is to used the IP address: i.e. loopback
 313  * address for Vertices and link IP address for Edges.
 314  *
 315  *      --------------     ---------------------------    --------------
 316  *      | Connected  |---->| Connected Edge Va to Vb |--->| Connected  |
 317  *  --->|  Vertex    |     ---------------------------    |  Vertex    |---->
 318  *      |            |                                    |            |
 319  *      | - Key (Va) |                                    | - Key (Vb) |
 320  *  <---| - Vertex   |     ---------------------------    | - Vertex   |<----
 321  *      |            |<----| Connected Edge Vb to Va |<---|            |
 322  *      --------------     ---------------------------    --------------
 323  *
 324  */
 325
 326 /* Link State Vertex structure */
 327 PREDECL_RBTREE_UNIQ(vertices)
 328 struct ls_vertex {
 329         struct vertices_item entry;     /* Entry in RB Tree */
 330         uint64_t key;                   /* Unique Key identifier */
 331         struct ls_node *node;           /* Link State Node */
 332         struct list *incoming_edges;    /* List of incoming Link State links */
 333         struct list *outgoing_edges;    /* List of outgoing Link State links */
 334         struct list *prefixes;          /* List of advertised prefix */
 335 };
 336
 337 /* Link State Edge structure */
 338 PREDECL_RBTREE_UNIQ(edges)
 339 struct ls_edge {
 340         struct edges_item entry;        /* Entry in RB tree */
 341         uint64_t key;                   /* Unique Key identifier */
 342         struct ls_attributes *attributes;       /* Link State attributes */
 343         struct ls_vertex *source;       /* Pointer to the source Vertex */
 344         struct ls_vertex *destination;  /* Pointer to the destination Vertex */
 345 };
 346
 347 /* Link State Subnet structure */
 348 PREDECL_RBTREE_UNIQ(subnets)
 349 struct ls_subnet {
 350         struct subnets_item entry;      /* Entry in RB tree */
 351         struct prefix key;              /* Unique Key identifier */
 352         struct ls_vertex *vertex;       /* Back pointer to the Vertex owner */
 353         struct ls_prefix *ls_pref;      /* Link State Prefix */
 354 };
 355
 356 /* Declaration of Vertices, Edges and Prefixes RB Trees */
 357 macro_inline int vertex_cmp(const struct ls_vertex *node1,
 358                             const struct ls_vertex *node2)
 359 {
 360         return (node1->key - node2->key);
 361 }
 362 DECLARE_RBTREE_UNIQ(vertices, struct ls_vertex, entry, vertex_cmp)
 363
 364 macro_inline int edge_cmp(const struct ls_edge *edge1,
 365                           const struct ls_edge *edge2)
 366 {
 367         return (edge1->key - edge2->key);
 368 }
 369 DECLARE_RBTREE_UNIQ(edges, struct ls_edge, entry, edge_cmp)
 370
 371 macro_inline int subnet_cmp(const struct ls_subnet *a,
 372                              const struct ls_subnet *b)
 373 {
 374         return prefix_cmp(&a->key, &b->key);
 375 }
 376 DECLARE_RBTREE_UNIQ(subnets, struct ls_subnet, entry, subnet_cmp)
 377
 378 /* Link State TED Structure */
 379 struct ls_ted {
 380         uint32_t key;                   /* Unique identifier */
 381         char name[MAX_NAME_LENGTH];     /* Name of this graph. Could be null */
 382         uint32_t as_number;             /* AS number of the modeled network */
 383         struct ls_vertex *self;         /* Vertex of the FRR instance */
 384         struct vertices_head vertices;  /* List of Vertices */
 385         struct edges_head edges;        /* List of Edges */
 386         struct subnets_head subnets;    /* List of Subnets */
 387 };
 388
 389 /**
 390  * Create a new Link State Vertex structure and initialize is with the Link
 391  * State Node parameter.
 392  *
 393  * @param node  Link State Node
 394  *
 395  * @return      New Vertex
 396  */
 397 extern struct ls_vertex *ls_vertex_new(struct ls_node *node);
 398
 399 /**
 400  * Delete Link State Vertex. This function clean internal Vertex lists (incoming
 401  * and outgoing Link State Edge and Link State Subnet). Note that referenced
 402  * objects of the different lists (Edges & SubNet) are not removed as they could
 403  * be connected to other Vertices.
 404  *
 405  * @param vertex        Link State Vertex to be removed
 406  */
 407 extern void ls_vertex_del(struct ls_vertex *vertex);
 408
 409 /**
 410  * Add new vertex to the Link State DB. Vertex is created from the Link State
 411  * Node. Vertex data structure is dynamically allocated.
 412  *
 413  * @param ted   Traffic Engineering Database structure
 414  * @param node  Link State Node
 415  *
 416  * @return      New Vertex or NULL in case of error
 417  */
 418 extern struct ls_vertex *ls_vertex_add(struct ls_ted *ted,
 419                                        struct ls_node *node);
 420
 421 /**
 422  * Update Vertex with the Link State Node. A new vertex is created if no one
 423  * corresponds to the Link State Node.
 424  *
 425  * @param ted   Link State Data Base
 426  * @param node  Link State Node to be updated
 427  *
 428  * @return      Updated Link State Vertex or Null in case of error
 429  */
 430 extern struct ls_vertex *ls_vertex_update(struct ls_ted *ted,
 431                                           struct ls_node *node);
 432
 433 /**
 434  * Remove Vertex from the Link State DB. Vertex Data structure is freed but
 435  * not the Link State Node. Link State DB is not modified if Vertex is NULL or
 436  * not found in the Data Base.
 437  *
 438  * @param ted           Link State Data Base
 439  * @param vertex        Vertex to be removed
 440  */
 441 extern void ls_vertex_remove(struct ls_ted *ted, struct ls_vertex *vertex);
 442
 443 /**
 444  * Find Vertex in the Link State DB by its unique key.
 445  *
 446  * @param ted   Link State Data Base
 447  * @param key   Vertex Key different from 0
 448  *
 449  * @return      Vertex if found, NULL otherwise
 450  */
 451 extern struct ls_vertex *ls_find_vertex_by_key(struct ls_ted *ted,
 452                                                const uint64_t key);
 453
 454 /**
 455  * Find Vertex in the Link State DB by its Link State Node.
 456  *
 457  * @param ted   Link State Data Base
 458  * @param nid   Link State Node ID
 459  *
 460  * @return      Vertex if found, NULL otherwise
 461  */
 462 extern struct ls_vertex *ls_find_vertex_by_id(struct ls_ted *ted,
 463                                               struct ls_node_id nid);
 464
 465 /**
 466  * Check if two Vertices are equal. Note that this routine has the same return
 467  * value sense as '==' (which is different from a comparison).
 468  *
 469  * @param v1    First vertex to compare
 470  * @param v2    Second vertex to compare
 471  *
 472  * @return      1 if equal, 0 otherwise
 473  */
 474 extern int ls_vertex_same(struct ls_vertex *v1, struct ls_vertex *v2);
 475
 476 /**
 477  * Add new Edge to the Link State DB. Edge is created from the Link State
 478  * Attributes. Edge data structure is dynamically allocated.
 479  *
 480  * @param ted           Link State Data Base
 481  * @param attributes    Link State attributes
 482  *
 483  * @return              New Edge or NULL in case of error
 484  */
 485 extern struct ls_edge *ls_edge_add(struct ls_ted *ted,
 486                                    struct ls_attributes *attributes);
 487
 488 /**
 489  * Update the Link State Attributes information of an existing Edge. If there is
 490  * no corresponding Edge in the Link State Data Base, a new Edge is created.
 491  *
 492  * @param ted           Link State Data Base
 493  * @param attributes    Link State Attributes
 494  *
 495  * @return              Updated Link State Edge, or NULL in case of error
 496  */
 497 extern struct ls_edge *ls_edge_update(struct ls_ted *ted,
 498                                       struct ls_attributes *attributes);
 499
 500 /**
 501  * Remove Edge from the Link State DB. Edge data structure is freed but not the
 502  * Link State Attributes data structure. Link State DB is not modified if Edge
 503  * is NULL or not found in the Data Base.
 504  *
 505  * @param ted   Link State Data Base
 506  * @param edge  Edge to be removed
 507  */
 508 extern void ls_edge_del(struct ls_ted *ted, struct ls_edge *edge);
 509
 510 /**
 511  * Find Edge in the Link State Data Base by Edge key.
 512  *
 513  * @param ted   Link State Data Base
 514  * @param key   Edge key
 515  *
 516  * @return      Edge if found, NULL otherwise
 517  */
 518 extern struct ls_edge *ls_find_edge_by_key(struct ls_ted *ted,
 519                                            const uint64_t key);
 520
 521 /**
 522  * Find Edge in the Link State Data Base by the source (local IPv4 or IPv6
 523  * address or local ID) informations of the Link
 524  * State Attributes
 525  *
 526  * @param ted           Link State Data Base
 527  * @param attributes    Link State Attributes
 528  *
 529  * @return              Edge if found, NULL otherwise
 530  */
 531 extern struct ls_edge *
 532 ls_find_edge_by_source(struct ls_ted *ted, struct ls_attributes *attributes);
 533
 534 /**
 535  * Find Edge in the Link State Data Base by the destination (remote IPv4 or IPv6
 536  * address of remote ID) information of the Link State Attributes
 537  *
 538  * @param ted           Link State Data Base
 539  * @param attributes    Link State Attributes
 540  *
 541  * @return              Edge if found, NULL otherwise
 542  */
 543 extern struct ls_edge *
 544 ls_find_edge_by_destination(struct ls_ted *ted,
 545                             struct ls_attributes *attributes);
 546
 547 /**
 548  * Add new Subnet to the Link State DB. Subnet is created from the Link State
 549  * prefix. Subnet data structure is dynamically allocated.
 550  *
 551  * @param ted   Link State Data Base
 552  * @param pref  Link State Prefix
 553  *
 554  * @return      New Subnet
 555  */
 556 extern struct ls_subnet *ls_subnet_add(struct ls_ted *ted,
 557                                        struct ls_prefix *pref);
 558
 559 /**
 560  * Remove Subnet from the Link State DB. Subnet data structure is freed but
 561  * not the Link State prefix data structure. Link State DB is not modified
 562  * if Subnet is NULL or not found in the Data Base.
 563  *
 564  * @param ted           Link State Data Base
 565  * @param subnet        Subnet to be removed
 566  */
 567 extern void ls_subnet_del(struct ls_ted *ted, struct ls_subnet *subnet);
 568
 569 /**
 570  * Find Subnet in the Link State Data Base by prefix.
 571  *
 572  * @param ted           Link State Data Base
 573  * @param prefix        Link State Prefix
 574  *
 575  * @return              Subnet if found, NULL otherwise
 576  */
 577 extern struct ls_subnet *ls_find_subnet(struct ls_ted *ted,
 578                                         const struct prefix prefix);
 579
 580 /**
 581  * Create a new Link State Data Base.
 582  *
 583  * @param key   Unique key of the data base. Must be different from 0
 584  * @param name  Name of the data base (may be NULL)
 585  * @param asn   AS Number for this data base. Must be different from 0
 586  *
 587  * @return      New Link State Database or NULL in case of error
 588  */
 589 extern struct ls_ted *ls_ted_new(const uint32_t key, const char *name,
 590                                  uint32_t asn);
 591
 592 /**
 593  * Delete existing Link State Data Base.
 594  *
 595  * @param ted   Link State Data Base
 596  */
 597 extern void ls_ted_del(struct ls_ted *ted);
 598
 599 /**
 600  * Connect Source and Destination Vertices by given Edge. Only non NULL source
 601  * and destination vertices are connected.
 602  *
 603  * @param src   Link State Source Vertex
 604  * @param dst   Link State Destination Vertex
 605  * @param edge  Link State Edge. Must not be NULL
 606  */
 607 extern void ls_connect_vertices(struct ls_vertex *src, struct ls_vertex *dst,
 608                                 struct ls_edge *edge);
 609
 610 /**
 611  * Connect Link State Edge to the Link State Vertex which could be a Source or
 612  * a Destination Vertex.
 613  *
 614  * @param vertex        Link State Vertex to be connected. Must not be NULL
 615  * @param edge          Link State Edge connection. Must not be NULL
 616  * @param source        True for a Source, false for a Destination Vertex
 617  */
 618 extern void ls_connect(struct ls_vertex *vertex, struct ls_edge *edge,
 619                        bool source);
 620
 621 /**
 622  * Disconnect Link State Edge from the Link State Vertex which could be a
 623  * Source or a Destination Vertex.
 624  *
 625  * @param vertex        Link State Vertex to be connected. Must not be NULL
 626  * @param edge          Link State Edge connection. Must not be NULL
 627  * @param source        True for a Source, false for a Destination Vertex
 628  */
 629 extern void ls_disconnect(struct ls_vertex *vertex, struct ls_edge *edge,
 630                           bool source);
 631
 632 /**
 633  * Disconnect Link State Edge from both Source and Destination Vertex.
 634  *
 635  * @param edge          Link State Edge to be disconnected
 636  */
 637 extern void ls_disconnect_edge(struct ls_edge *edge);
 638
 639
 640 /**
 641  * The Link State Message is defined to convey Link State parameters from
 642  * the routing protocol (OSPF or IS-IS) to other daemons e.g. BGP.
 643  *
 644  * The structure is composed of:
 645  *  - Event of the message:
 646  *    - Sync: Send the whole LS DB following a request
 647  *    - Add: Send the a new Link State element
 648  *    -  Update: Send an update of an existing Link State element
 649  *    - Delete: Indicate that the given Link State element is removed
 650  *  - Type of Link State element: Node, Attribute or Prefix
 651  *  - Remote node id when known
 652  *  - Data: Node, Attributes or Prefix
 653  *
 654  * A Link State Message can carry only one Link State Element (Node, Attributes
 655  * of Prefix) at once, and only one Link State Message is sent through ZAPI
 656  * Opaque Link State type at once.
 657  */
 658
 659 /* ZAPI Opaque Link State Message Event */
 660 #define LS_MSG_EVENT_SYNC       1
 661 #define LS_MSG_EVENT_ADD        2
 662 #define LS_MSG_EVENT_UPDATE     3
 663 #define LS_MSG_EVENT_DELETE     4
 664
 665 /* ZAPI Opaque Link State Message sub-Type */
 666 #define LS_MSG_TYPE_NODE        1
 667 #define LS_MSG_TYPE_ATTRIBUTES  2
 668 #define LS_MSG_TYPE_PREFIX      3
 669
 670 /* Link State Message */
 671 struct ls_message {
 672         uint8_t event;          /* Message Event: Sync, Add, Update, Delete */
 673         uint8_t type;           /* Message Data Type: Node, Attribute, Prefix */
 674         struct ls_node_id remote_id;    /* Remote Link State Node ID */
 675         union {
 676                 struct ls_node *node;           /* Link State Node */
 677                 struct ls_attributes *attr;     /* Link State Attributes */
 678                 struct ls_prefix *prefix;       /* Link State Prefix */
 679         } data;
 680 };
 681
 682 /**
 683  * Parse Link State Message from stream. Used this function once receiving a
 684  * new ZAPI Opaque message of type Link State.
 685  *
 686  * @param s     Stream buffer. Must not be NULL.
 687  *
 688  * @return      New Link State Message or NULL in case of error
 689  */
 690 extern struct ls_message *ls_parse_msg(struct stream *s);
 691
 692 /**
 693  * Delete existing message, freeing all substructure.
 694  *
 695  * @param msg   Link state message to be deleted
 696  */
 697 extern void ls_delete_msg(struct ls_message *msg);
 698
 699 /**
 700  * Send Link State Message as new ZAPI Opaque message of type Link State.
 701  * If destination is not NULL, message is sent as Unicast otherwise it is
 702  * broadcast to all registered daemon.
 703  *
 704  * @param zclient       Zebra Client
 705  * @param msg           Link State Message to be sent
 706  * @param dst           Destination daemon for unicast message,
 707  *                      NULL for broadcast message
 708  *
 709  * @return              0 on success, -1 otherwise
 710  */
 711 extern int ls_send_msg(struct zclient *zclient, struct ls_message *msg,
 712                        struct zapi_opaque_reg_info *dst);
 713
 714 /**
 715  * Create a new Link State Message from a Link State Vertex. If Link State
 716  * Message is NULL, a new data structure is dynamically allocated.
 717  *
 718  * @param msg           Link State Message to be filled or NULL
 719  * @param vertex        Link State Vertex. Must not be NULL
 720  *
 721  * @return              New Link State Message msg parameter is NULL or pointer
 722  *                      to the provided Link State Message
 723  */
 724 extern struct ls_message *ls_vertex2msg(struct ls_message *msg,
 725                                         struct ls_vertex *vertex);
 726
 727 /**
 728  * Create a new Link State Message from a Link State Edge. If Link State
 729  * Message is NULL, a new data structure is dynamically allocated.
 730  *
 731  * @param msg           Link State Message to be filled or NULL
 732  * @param edge          Link State Edge. Must not be NULL
 733  *
 734  * @return              New Link State Message msg parameter is NULL or pointer
 735  *                      to the provided Link State Message
 736  */
 737 extern struct ls_message *ls_edge2msg(struct ls_message *msg,
 738                                       struct ls_edge *edge);
 739
 740 /**
 741  * Create a new Link State Message from a Link State Subnet. If Link State
 742  * Message is NULL, a new data structure is dynamically allocated.
 743  *
 744  * @param msg           Link State Message to be filled or NULL
 745  * @param subnet        Link State Subnet. Must not be NULL
 746  *
 747  * @return              New Link State Message msg parameter is NULL or pointer
 748  *                      to the provided Link State Message
 749  */
 750 extern struct ls_message *ls_subnet2msg(struct ls_message *msg,
 751                                         struct ls_subnet *subnet);
 752
 753 /**
 754  * Send all the content of the Link State Data Base to the given destination.
 755  * Link State content is sent is this order: Vertices, Edges, Subnet.
 756  * This function must be used when a daemon request a Link State Data Base
 757  * Synchronization.
 758  *
 759  * @param ted           Link State Data Base. Must not be NULL
 760  * @param zclient       Zebra Client. Must not be NULL
 761  * @param dst           Destination FRR daemon. Must not be NULL
 762  *
 763  * @return              0 on success, -1 otherwise
 764  */
 765 extern int ls_sync_ted(struct ls_ted *ted, struct zclient *zclient,
 766                        struct zapi_opaque_reg_info *dst);
 767
 768 /**
 769  * Dump all Link State Data Base elements for debugging purposes
 770  *
 771  * @param ted   Link State Data Base. Must not be NULL
 772  *
 773  */
 774 extern void ls_dump_ted(struct ls_ted *ted);
 775
 776 #ifdef __cplusplus
 777 }
 778 #endif
 779
 780 #endif /* _FRR_LINK_STATE_H_ */