isisd/isis_flex_algo.c

   1 // SPDX-License-Identifier: GPL-2.0-or-later
   2 /*********************************************************************
   3  * Copyright 2022 Hiroki Shirokura, LINE Corporation
   4  * Copyright 2022 Masakazu Asama
   5  * Copyright 2022 6WIND S.A.
   6  *
   7  * isis_flex_algo.c: IS-IS Flexible Algorithm
   8  *
   9  * Authors
  10  * -------
  11  * Hiroki Shirokura
  12  * Masakazu Asama
  13  * Louis Scalbert
  14  */
  15
  16 #include <zebra.h>
  17
  18 #include "memory.h"
  19 #include "stream.h"
  20 #include "sbuf.h"
  21 #include "network.h"
  22 #include "command.h"
  23 #include "bitfield.h"
  24
  25 #include "isisd/isisd.h"
  26 #include "isisd/isis_tlvs.h"
  27 #include "isisd/isis_common.h"
  28 #include "isisd/isis_mt.h"
  29 #include "isisd/isis_misc.h"
  30 #include "isisd/isis_adjacency.h"
  31 #include "isisd/isis_circuit.h"
  32 #include "isisd/isis_pdu.h"
  33 #include "isisd/isis_lsp.h"
  34 #include "isisd/isis_spf.h"
  35 #include "isisd/isis_te.h"
  36 #include "isisd/isis_sr.h"
  37 #include "isisd/isis_spf_private.h"
  38 #include "isisd/isis_flex_algo.h"
  39
  40 #ifndef FABRICD
  41 DEFINE_MTYPE_STATIC(ISISD, FLEX_ALGO, "ISIS Flex Algo");
  42
  43 void *isis_flex_algo_data_alloc(void *voidarg)
  44 {
  45         struct isis_flex_algo_alloc_arg *arg = voidarg;
  46         struct isis_flex_algo_data *data;
  47
  48         data = XCALLOC(MTYPE_FLEX_ALGO, sizeof(struct isis_flex_algo_data));
  49
  50         for (int tree = SPFTREE_IPV4; tree < SPFTREE_COUNT; tree++) {
  51                 for (int level = ISIS_LEVEL1; level <= ISIS_LEVEL2; level++) {
  52                         if (!(arg->area->is_type & level))
  53                                 continue;
  54                         data->spftree[tree][level - 1] = isis_spftree_new(
  55                                 arg->area, &arg->area->lspdb[level - 1],
  56                                 arg->area->isis->sysid, level, tree,
  57                                 SPF_TYPE_FORWARD, 0, arg->algorithm);
  58                 }
  59         }
  60
  61         return data;
  62 }
  63
  64 void isis_flex_algo_data_free(void *voiddata)
  65 {
  66         struct isis_flex_algo_data *data = voiddata;
  67
  68         for (int tree = SPFTREE_IPV4; tree < SPFTREE_COUNT; tree++)
  69                 for (int level = ISIS_LEVEL1; level <= ISIS_LEVEL2; level++)
  70                         if (data->spftree[tree][level - 1])
  71                                 isis_spftree_del(
  72                                         data->spftree[tree][level - 1]);
  73         XFREE(MTYPE_FLEX_ALGO, data);
  74 }
  75
  76 static struct isis_router_cap_fad *
  77 isis_flex_algo_definition_cmp(struct isis_router_cap_fad *elected,
  78                               struct isis_router_cap_fad *fa)
  79 {
  80         if (!elected || fa->fad.priority > elected->fad.priority ||
  81             (fa->fad.priority == elected->fad.priority &&
  82              lsp_id_cmp(fa->sysid, elected->sysid) > 0))
  83                 return fa;
  84
  85         return elected;
  86 }
  87
  88 /**
  89  * @brief Look up the flex-algo definition with the highest priority in the LSP
  90  * Database (LSDB). If the value of priority is the same, the flex-algo
  91  * definition with the highest sysid will be selected.
  92  * @param algorithm flex-algo algorithm number
  93  * @param area pointer
  94  * @param local router capability Flex-Algo Definition (FAD) double pointer.
  95  *    - fad is NULL: use the local router capability FAD from LSDB for the
  96  *      election.
  97  *    - fad is not NULL and *fad is NULL: use no local router capability FAD for
  98  *      the election.
  99  *    - fad and *fad are not NULL: uses the *fad local definition instead of the
 100  *      local definition from LSDB for the election.
 101  * @return elected flex-algo-definition object if exist, else NULL
 102  */
 103 static struct isis_router_cap_fad *
 104 _isis_flex_algo_elected(int algorithm, const struct isis_area *area,
 105                         struct isis_router_cap_fad **fad)
 106 {
 107         struct flex_algo *flex_ago;
 108         const struct isis_lsp *lsp;
 109         struct isis_router_cap_fad *fa, *elected = NULL;
 110
 111         if (!flex_algo_id_valid(algorithm))
 112                 return NULL;
 113
 114         /* No elected FAD if the algorithm is not locally configured */
 115         flex_ago = flex_algo_lookup(area->flex_algos, algorithm);
 116         if (!flex_ago)
 117                 return NULL;
 118
 119         /* No elected FAD if no data-plane is enabled
 120          * Currently, only Segment-Routing MPLS is supported.
 121          * Segment-Routing SRv6 and IP will be configured in the future.
 122          */
 123         if (!CHECK_FLAG(flex_ago->dataplanes, FLEX_ALGO_SR_MPLS))
 124                 return NULL;
 125
 126         /*
 127          * Perform FAD comparison. First, compare the priority, and if they are
 128          * the same, compare the sys-id.
 129          */
 130         /* clang-format off */
 131         frr_each_const(lspdb, &area->lspdb[ISIS_LEVEL1 - 1], lsp) {
 132                 /* clang-format on */
 133
 134                 if (!lsp->tlvs || !lsp->tlvs->router_cap)
 135                         continue;
 136
 137                 if (lsp->own_lsp && fad)
 138                         continue;
 139
 140                 fa = lsp->tlvs->router_cap->fads[algorithm];
 141
 142                 if (!fa)
 143                         continue;
 144
 145                 assert(algorithm == fa->fad.algorithm);
 146
 147                 memcpy(fa->sysid, lsp->hdr.lsp_id, ISIS_SYS_ID_LEN + 2);
 148
 149                 elected = isis_flex_algo_definition_cmp(elected, fa);
 150         }
 151
 152         if (fad && *fad)
 153                 elected = isis_flex_algo_definition_cmp(elected, *fad);
 154
 155         return elected;
 156 }
 157
 158 struct isis_router_cap_fad *isis_flex_algo_elected(int algorithm,
 159                                                    const struct isis_area *area)
 160 {
 161         return _isis_flex_algo_elected(algorithm, area, NULL);
 162 }
 163
 164 /**
 165  * @brief Check the Flex-Algo Definition is supported by the current FRR version
 166  * @param flex-algo
 167  * @return true if supported else false
 168  */
 169 bool isis_flex_algo_supported(struct flex_algo *fad)
 170 {
 171         if (fad->calc_type != CALC_TYPE_SPF)
 172                 return false;
 173         if (fad->metric_type != MT_IGP)
 174                 return false;
 175         if (fad->flags != 0)
 176                 return false;
 177         if (fad->exclude_srlg)
 178                 return false;
 179         if (fad->unsupported_subtlv)
 180                 return false;
 181
 182         return true;
 183 }
 184
 185 /**
 186  * @brief Look for the elected Flex-Algo Definition and check that it is
 187  * supported by the current FRR version
 188  * @param algorithm flex-algo algorithm number
 189  * @param area pointer
 190  * @param local router capability Flex-Algo Definition (FAD) double pointer.
 191  * @return elected flex-algo-definition object if exist and supported, else NULL
 192  */
 193 static struct isis_router_cap_fad *
 194 _isis_flex_algo_elected_supported(int algorithm, const struct isis_area *area,
 195                                   struct isis_router_cap_fad **fad)
 196 {
 197         struct isis_router_cap_fad *elected_fad;
 198
 199         elected_fad = _isis_flex_algo_elected(algorithm, area, fad);
 200         if (!elected_fad)
 201                 return NULL;
 202
 203         if (isis_flex_algo_supported(&elected_fad->fad))
 204                 return elected_fad;
 205
 206         return NULL;
 207 }
 208
 209 struct isis_router_cap_fad *
 210 isis_flex_algo_elected_supported(int algorithm, const struct isis_area *area)
 211 {
 212         return _isis_flex_algo_elected_supported(algorithm, area, NULL);
 213 }
 214
 215 struct isis_router_cap_fad *
 216 isis_flex_algo_elected_supported_local_fad(int algorithm,
 217                                            const struct isis_area *area,
 218                                            struct isis_router_cap_fad **fad)
 219 {
 220         return _isis_flex_algo_elected_supported(algorithm, area, fad);
 221 }
 222
 223 /**
 224  * Check LSP is participating specified SR Algorithm
 225  *
 226  * @param lsp        IS-IS lsp
 227  * @param algorithm  SR Algorithm
 228  * @return           Return true if sr-algorithm tlv includes specified
 229  *                   algorithm in router capability tlv
 230  */
 231 bool sr_algorithm_participated(const struct isis_lsp *lsp, uint8_t algorithm)
 232 {
 233         if (!lsp || !lsp->tlvs || !lsp->tlvs->router_cap)
 234                 return false;
 235         for (int i = 0; i < SR_ALGORITHM_COUNT; i++)
 236                 if (lsp->tlvs->router_cap->algo[i] == algorithm)
 237                         return true;
 238         return false;
 239 }
 240
 241 bool isis_flex_algo_constraint_drop(struct isis_spftree *spftree,
 242                                     struct isis_lsp *lsp,
 243                                     struct isis_extended_reach *reach)
 244 {
 245         bool ret;
 246         struct isis_ext_subtlvs *subtlvs = reach->subtlvs;
 247         struct isis_router_cap_fad *fad;
 248         struct isis_asla_subtlvs *asla;
 249         struct listnode *node;
 250         uint32_t *link_admin_group = NULL;
 251         uint32_t link_ext_admin_group_bitmap0;
 252         struct admin_group *link_ext_admin_group = NULL;
 253
 254         fad = isis_flex_algo_elected_supported(spftree->algorithm,
 255                                                spftree->area);
 256         if (!fad)
 257                 return true;
 258
 259         for (ALL_LIST_ELEMENTS_RO(subtlvs->aslas, node, asla)) {
 260                 if (!CHECK_FLAG(asla->standard_apps, ISIS_SABM_FLAG_X))
 261                         continue;
 262                 if (asla->legacy) {
 263                         if (IS_SUBTLV(subtlvs, EXT_ADM_GRP))
 264                                 link_admin_group = &subtlvs->adm_group;
 265
 266                         if (IS_SUBTLV(subtlvs, EXT_EXTEND_ADM_GRP) &&
 267                             admin_group_nb_words(&subtlvs->ext_admin_group) !=
 268                                     0)
 269                                 link_ext_admin_group =
 270                                         &subtlvs->ext_admin_group;
 271                 } else {
 272                         if (IS_SUBTLV(asla, EXT_ADM_GRP))
 273                                 link_admin_group = &asla->admin_group;
 274                         if (IS_SUBTLV(asla, EXT_EXTEND_ADM_GRP) &&
 275                             admin_group_nb_words(&asla->ext_admin_group) != 0)
 276                                 link_ext_admin_group = &asla->ext_admin_group;
 277                 }
 278                 break;
 279         }
 280
 281         /* RFC7308 section 2.3.1
 282          * A receiving node that notices that the AG differs from the first 32
 283          * bits of the EAG SHOULD report this mismatch to the operator.
 284          */
 285         if (link_admin_group && link_ext_admin_group) {
 286                 link_ext_admin_group_bitmap0 =
 287                         admin_group_get_offset(link_ext_admin_group, 0);
 288                 if (*link_admin_group != link_ext_admin_group_bitmap0)
 289                         zlog_warn(
 290                                 "ISIS-SPF: LSP from %pPN neighbor %pPN. Admin-group 0x%08x differs from ext admin-group 0x%08x.",
 291                                 lsp->hdr.lsp_id, reach->id, *link_admin_group,
 292                                 link_ext_admin_group_bitmap0);
 293         }
 294
 295         /*
 296          * Exclude Any
 297          */
 298         if (!admin_group_zero(&fad->fad.admin_group_exclude_any)) {
 299                 ret = admin_group_match_any(&fad->fad.admin_group_exclude_any,
 300                                             link_admin_group,
 301                                             link_ext_admin_group);
 302                 if (ret)
 303                         return true;
 304         }
 305
 306         /*
 307          * Include Any
 308          */
 309         if (!admin_group_zero(&fad->fad.admin_group_include_any)) {
 310                 ret = admin_group_match_any(&fad->fad.admin_group_include_any,
 311                                             link_admin_group,
 312                                             link_ext_admin_group);
 313                 if (!ret)
 314                         return true;
 315         }
 316
 317         /*
 318          * Include All
 319          */
 320         if (!admin_group_zero(&fad->fad.admin_group_include_all)) {
 321                 ret = admin_group_match_all(&fad->fad.admin_group_include_all,
 322                                             link_admin_group,
 323                                             link_ext_admin_group);
 324                 if (!ret)
 325                         return true;
 326         }
 327
 328         return false;
 329 }
 330
 331 #endif /* ifndef FABRICD */