zebra/label_manager.c

   1 // SPDX-License-Identifier: GPL-2.0-or-later
   2 /*
   3  * Label Manager for FRR
   4  *
   5  * Copyright (C) 2017 by Bingen Eguzkitza,
   6  *                       Volta Networks Inc.
   7  *
   8  * This file is part of FRRouting (FRR)
   9  */
  10
  11 #include <zebra.h>
  12 #include <stdio.h>
  13 #include <string.h>
  14 #include <sys/types.h>
  15
  16 #include "lib/log.h"
  17 #include "lib/memory.h"
  18 #include "lib/mpls.h"
  19 #include "lib/network.h"
  20 #include "lib/stream.h"
  21 #include "lib/zclient.h"
  22 #include "lib/libfrr.h"
  23
  24 //#include "zebra/zserv.h"
  25 #include "zebra/zebra_router.h"
  26 #include "zebra/label_manager.h"
  27 #include "zebra/zebra_errors.h"
  28 #include "zebra/zapi_msg.h"
  29 #include "zebra/debug.h"
  30
  31 #define CONNECTION_DELAY 5
  32
  33 struct label_manager lbl_mgr;
  34
  35 DEFINE_MGROUP(LBL_MGR, "Label Manager");
  36 DEFINE_MTYPE_STATIC(LBL_MGR, LM_CHUNK, "Label Manager Chunk");
  37
  38 /* define hooks for the basic API, so that it can be specialized or served
  39  * externally
  40  */
  41
  42 DEFINE_HOOK(lm_client_connect, (struct zserv *client, vrf_id_t vrf_id),
  43             (client, vrf_id));
  44 DEFINE_HOOK(lm_client_disconnect, (struct zserv *client), (client));
  45 DEFINE_HOOK(lm_get_chunk,
  46              (struct label_manager_chunk * *lmc, struct zserv *client,
  47               uint8_t keep, uint32_t size, uint32_t base, vrf_id_t vrf_id),
  48              (lmc, client, keep, size, base, vrf_id));
  49 DEFINE_HOOK(lm_release_chunk,
  50              (struct zserv *client, uint32_t start, uint32_t end),
  51              (client, start, end));
  52 DEFINE_HOOK(lm_cbs_inited, (), ());
  53
  54 /* define wrappers to be called in zapi_msg.c (as hooks must be called in
  55  * source file where they were defined)
  56  */
  57 void lm_client_connect_call(struct zserv *client, vrf_id_t vrf_id)
  58 {
  59         hook_call(lm_client_connect, client, vrf_id);
  60 }
  61 void lm_get_chunk_call(struct label_manager_chunk **lmc, struct zserv *client,
  62                        uint8_t keep, uint32_t size, uint32_t base,
  63                        vrf_id_t vrf_id)
  64 {
  65         hook_call(lm_get_chunk, lmc, client, keep, size, base, vrf_id);
  66 }
  67 void lm_release_chunk_call(struct zserv *client, uint32_t start, uint32_t end)
  68 {
  69         hook_call(lm_release_chunk, client, start, end);
  70 }
  71
  72 /* forward declarations of the static functions to be used for some hooks */
  73 static int label_manager_connect(struct zserv *client, vrf_id_t vrf_id);
  74 static int label_manager_disconnect(struct zserv *client);
  75 static int label_manager_get_chunk(struct label_manager_chunk **lmc,
  76                                    struct zserv *client, uint8_t keep,
  77                                    uint32_t size, uint32_t base,
  78                                    vrf_id_t vrf_id);
  79 static int label_manager_release_label_chunk(struct zserv *client,
  80                                              uint32_t start, uint32_t end);
  81
  82 void delete_label_chunk(void *val)
  83 {
  84         XFREE(MTYPE_LM_CHUNK, val);
  85 }
  86
  87 /**
  88  * Release label chunks from a client.
  89  *
  90  * Called on client disconnection or reconnection. It only releases chunks
  91  * with empty keep value.
  92  *
  93  * @param proto Daemon protocol of client, to identify the owner
  94  * @param instance Instance, to identify the owner
  95  * @return Number of chunks released
  96  */
  97 int release_daemon_label_chunks(struct zserv *client)
  98 {
  99         struct listnode *node;
 100         struct label_manager_chunk *lmc;
 101         int count = 0;
 102         int ret;
 103
 104         if (IS_ZEBRA_DEBUG_PACKET)
 105                 zlog_debug("%s: Releasing chunks for client proto %s, instance %d, session %u",
 106                            __func__, zebra_route_string(client->proto),
 107                            client->instance, client->session_id);
 108
 109         for (ALL_LIST_ELEMENTS_RO(lbl_mgr.lc_list, node, lmc)) {
 110                 if (lmc->proto == client->proto &&
 111                     lmc->instance == client->instance &&
 112                     lmc->session_id == client->session_id && lmc->keep == 0) {
 113                         ret = release_label_chunk(lmc->proto, lmc->instance,
 114                                                   lmc->session_id,
 115                                                   lmc->start, lmc->end);
 116                         if (ret == 0)
 117                                 count++;
 118                 }
 119         }
 120
 121         if (IS_ZEBRA_DEBUG_PACKET)
 122                 zlog_debug("%s: Released %d label chunks", __func__, count);
 123
 124         return count;
 125 }
 126
 127 int lm_client_disconnect_cb(struct zserv *client)
 128 {
 129         hook_call(lm_client_disconnect, client);
 130         return 0;
 131 }
 132
 133 void lm_hooks_register(void)
 134 {
 135         hook_register(lm_client_connect, label_manager_connect);
 136         hook_register(lm_client_disconnect, label_manager_disconnect);
 137         hook_register(lm_get_chunk, label_manager_get_chunk);
 138         hook_register(lm_release_chunk, label_manager_release_label_chunk);
 139 }
 140 void lm_hooks_unregister(void)
 141 {
 142         hook_unregister(lm_client_connect, label_manager_connect);
 143         hook_unregister(lm_client_disconnect, label_manager_disconnect);
 144         hook_unregister(lm_get_chunk, label_manager_get_chunk);
 145         hook_unregister(lm_release_chunk, label_manager_release_label_chunk);
 146 }
 147
 148 /**
 149  * Init label manager (or proxy to an external one)
 150  */
 151 void label_manager_init(void)
 152 {
 153         lbl_mgr.lc_list = list_new();
 154         lbl_mgr.lc_list->del = delete_label_chunk;
 155         hook_register(zserv_client_close, lm_client_disconnect_cb);
 156
 157         /* register default hooks for the label manager actions */
 158         lm_hooks_register();
 159
 160         /* notify any external module that we are done */
 161         hook_call(lm_cbs_inited);
 162 }
 163
 164 /* alloc and fill a label chunk */
 165 struct label_manager_chunk *
 166 create_label_chunk(uint8_t proto, unsigned short instance, uint32_t session_id,
 167                    uint8_t keep, uint32_t start, uint32_t end)
 168 {
 169         /* alloc chunk, fill it and return it */
 170         struct label_manager_chunk *lmc =
 171                 XCALLOC(MTYPE_LM_CHUNK, sizeof(struct label_manager_chunk));
 172
 173         lmc->start = start;
 174         lmc->end = end;
 175         lmc->proto = proto;
 176         lmc->instance = instance;
 177         lmc->session_id = session_id;
 178         lmc->keep = keep;
 179
 180         return lmc;
 181 }
 182
 183 /* attempt to get a specific label chunk */
 184 static struct label_manager_chunk *
 185 assign_specific_label_chunk(uint8_t proto, unsigned short instance,
 186                             uint32_t session_id, uint8_t keep, uint32_t size,
 187                             uint32_t base)
 188 {
 189         struct label_manager_chunk *lmc;
 190         struct listnode *node, *next = NULL;
 191         struct listnode *first_node = NULL;
 192         struct listnode *last_node = NULL;
 193         struct listnode *insert_node = NULL;
 194
 195         /* precompute last label from base and size */
 196         uint32_t end = base + size - 1;
 197
 198         /* sanities */
 199         if ((base < MPLS_LABEL_UNRESERVED_MIN)
 200             || (end > MPLS_LABEL_UNRESERVED_MAX)) {
 201                 zlog_err("Invalid LM request arguments: base: %u, size: %u",
 202                          base, size);
 203                 return NULL;
 204         }
 205
 206         /* Scan the existing chunks to see if the requested range of labels
 207          * falls inside any of such chunks */
 208         for (ALL_LIST_ELEMENTS_RO(lbl_mgr.lc_list, node, lmc)) {
 209
 210                 /* skip chunks for labels < base */
 211                 if (base > lmc->end)
 212                         continue;
 213
 214                 /* requested range is not covered by any existing, free chunk.
 215                  * Therefore, need to insert a chunk */
 216                 if ((end < lmc->start) && !first_node) {
 217                         insert_node = node;
 218                         break;
 219                 }
 220
 221                 if (!first_node)
 222                         first_node = node;
 223
 224                 /* if chunk is used, cannot honor request */
 225                 if (lmc->proto != NO_PROTO)
 226                         return NULL;
 227
 228                 if (end <= lmc->end) {
 229                         last_node = node;
 230                         break;
 231                 }
 232         }
 233
 234         /* insert chunk between existing chunks */
 235         if (insert_node) {
 236                 lmc = create_label_chunk(proto, instance, session_id, keep,
 237                                          base, end);
 238                 listnode_add_before(lbl_mgr.lc_list, insert_node, lmc);
 239                 return lmc;
 240         }
 241
 242         if (first_node) {
 243                 /* get node past the last one, if there */
 244                 if (last_node)
 245                         last_node = listnextnode(last_node);
 246
 247                 /* delete node coming after the above chunk whose labels are
 248                  * included in the previous one */
 249                 for (node = first_node; node && (node != last_node);
 250                      node = next) {
 251                         struct label_manager_chunk *death;
 252
 253                         next = listnextnode(node);
 254                         death = listgetdata(node);
 255                         list_delete_node(lbl_mgr.lc_list, node);
 256                         delete_label_chunk(death);
 257                 }
 258
 259                 lmc = create_label_chunk(proto, instance, session_id, keep,
 260                                          base, end);
 261                 if (last_node)
 262                         listnode_add_before(lbl_mgr.lc_list, last_node, lmc);
 263                 else
 264                         listnode_add(lbl_mgr.lc_list, lmc);
 265
 266                 return lmc;
 267         } else {
 268                 /* create a new chunk past all the existing ones and link at
 269                  * tail */
 270                 lmc = create_label_chunk(proto, instance, session_id, keep,
 271                                          base, end);
 272                 listnode_add(lbl_mgr.lc_list, lmc);
 273                 return lmc;
 274         }
 275 }
 276
 277 /**
 278  * Core function, assigns label chunks
 279  *
 280  * It first searches through the list to check if there's one available
 281  * (previously released). Otherwise it creates and assigns a new one
 282  *
 283  * @param proto Daemon protocol of client, to identify the owner
 284  * @param instance Instance, to identify the owner
 285  * @param keep If set, avoid garbage collection
 286  * @param size Size of the label chunk
 287  * @param base Desired starting label of the chunk; if MPLS_LABEL_BASE_ANY it does not apply
 288  * @return Pointer to the assigned label chunk, or NULL if the request could not be satisfied
 289  */
 290 struct label_manager_chunk *
 291 assign_label_chunk(uint8_t proto, unsigned short instance, uint32_t session_id,
 292                    uint8_t keep, uint32_t size, uint32_t base)
 293 {
 294         struct label_manager_chunk *lmc;
 295         struct listnode *node;
 296         uint32_t prev_end = MPLS_LABEL_UNRESERVED_MIN;
 297
 298         /* handle chunks request with a specific base label */
 299         if (base != MPLS_LABEL_BASE_ANY)
 300                 return assign_specific_label_chunk(proto, instance, session_id,
 301                                                    keep, size, base);
 302
 303         /* appease scan-build, who gets confused by the use of macros */
 304         assert(lbl_mgr.lc_list);
 305
 306         /* first check if there's one available */
 307         for (ALL_LIST_ELEMENTS_RO(lbl_mgr.lc_list, node, lmc)) {
 308                 if (lmc->proto == NO_PROTO
 309                     && lmc->end - lmc->start + 1 == size) {
 310                         lmc->proto = proto;
 311                         lmc->instance = instance;
 312                         lmc->session_id = session_id;
 313                         lmc->keep = keep;
 314                         return lmc;
 315                 }
 316                 /* check if we hadve a "hole" behind us that we can squeeze into
 317                  */
 318                 if ((lmc->start > prev_end) && (lmc->start - prev_end > size)) {
 319                         lmc = create_label_chunk(proto, instance, session_id,
 320                                                  keep, prev_end + 1,
 321                                                  prev_end + size);
 322                         listnode_add_before(lbl_mgr.lc_list, node, lmc);
 323                         return lmc;
 324                 }
 325                 prev_end = lmc->end;
 326         }
 327         /* otherwise create a new one */
 328         uint32_t start_free;
 329
 330         if (list_isempty(lbl_mgr.lc_list))
 331                 start_free = MPLS_LABEL_UNRESERVED_MIN;
 332         else
 333                 start_free = ((struct label_manager_chunk *)listgetdata(
 334                                       listtail(lbl_mgr.lc_list)))
 335                                      ->end
 336                              + 1;
 337
 338         if (start_free > MPLS_LABEL_UNRESERVED_MAX - size + 1) {
 339                 flog_err(EC_ZEBRA_LM_EXHAUSTED_LABELS,
 340                          "Reached max labels. Start: %u, size: %u", start_free,
 341                          size);
 342                 return NULL;
 343         }
 344
 345         /* create chunk and link at tail */
 346         lmc = create_label_chunk(proto, instance, session_id, keep, start_free,
 347                                  start_free + size - 1);
 348         listnode_add(lbl_mgr.lc_list, lmc);
 349         return lmc;
 350 }
 351
 352 /**
 353  * Release label chunks from a client.
 354  *
 355  * Called on client disconnection or reconnection. It only releases chunks
 356  * with empty keep value.
 357  *
 358  * @param client Client zapi session
 359  * @param start First label of the chunk
 360  * @param end Last label of the chunk
 361  * @return 0 on success
 362  */
 363 static int label_manager_release_label_chunk(struct zserv *client,
 364                                              uint32_t start, uint32_t end)
 365 {
 366         return release_label_chunk(client->proto, client->instance,
 367                                    client->session_id, start, end);
 368 }
 369
 370 /**
 371  * Core function, release no longer used label chunks
 372  *
 373  * @param proto Daemon protocol of client, to identify the owner
 374  * @param instance Instance, to identify the owner
 375  * @param session_id Zclient session ID, to identify the zclient session
 376  * @param start First label of the chunk
 377  * @param end Last label of the chunk
 378  * @return 0 on success, -1 otherwise
 379  */
 380 int release_label_chunk(uint8_t proto, unsigned short instance,
 381                         uint32_t session_id, uint32_t start, uint32_t end)
 382 {
 383         struct listnode *node;
 384         struct label_manager_chunk *lmc;
 385         int ret = -1;
 386
 387         /* check that size matches */
 388         if (IS_ZEBRA_DEBUG_PACKET)
 389                 zlog_debug("Releasing label chunk: %u - %u", start, end);
 390         /* find chunk and disown */
 391         for (ALL_LIST_ELEMENTS_RO(lbl_mgr.lc_list, node, lmc)) {
 392                 if (lmc->start != start)
 393                         continue;
 394                 if (lmc->end != end)
 395                         continue;
 396                 if (lmc->proto != proto || lmc->instance != instance ||
 397                     lmc->session_id != session_id) {
 398                         flog_err(EC_ZEBRA_LM_DAEMON_MISMATCH,
 399                                  "%s: Daemon mismatch!!", __func__);
 400                         continue;
 401                 }
 402                 lmc->proto = NO_PROTO;
 403                 lmc->instance = 0;
 404                 lmc->session_id = 0;
 405                 lmc->keep = 0;
 406                 ret = 0;
 407                 break;
 408         }
 409         if (ret != 0)
 410                 flog_err(EC_ZEBRA_LM_UNRELEASED_CHUNK,
 411                          "%s: Label chunk not released!!", __func__);
 412
 413         return ret;
 414 }
 415
 416 /* default functions to be called on hooks  */
 417 static int label_manager_connect(struct zserv *client, vrf_id_t vrf_id)
 418 {
 419         /*
 420          * Release previous labels of same protocol and instance.
 421          * This is done in case it restarted from an unexpected shutdown.
 422          */
 423         release_daemon_label_chunks(client);
 424         return zsend_label_manager_connect_response(client, vrf_id, 0);
 425 }
 426 static int label_manager_disconnect(struct zserv *client)
 427 {
 428         release_daemon_label_chunks(client);
 429         return 0;
 430 }
 431 static int label_manager_get_chunk(struct label_manager_chunk **lmc,
 432                                    struct zserv *client, uint8_t keep,
 433                                    uint32_t size, uint32_t base,
 434                                    vrf_id_t vrf_id)
 435 {
 436         *lmc = assign_label_chunk(client->proto, client->instance,
 437                                   client->session_id, keep, size, base);
 438         return lm_get_chunk_response(*lmc, client, vrf_id);
 439 }
 440
 441 /* Respond to a connect request */
 442 int lm_client_connect_response(uint8_t proto, uint16_t instance,
 443                                uint32_t session_id, vrf_id_t vrf_id,
 444                                uint8_t result)
 445 {
 446         struct zserv *client = zserv_find_client_session(proto, instance,
 447                                                          session_id);
 448         if (!client) {
 449                 zlog_err("%s: could not find client for daemon %s instance %u session %u",
 450                          __func__, zebra_route_string(proto), instance,
 451                          session_id);
 452                 return 1;
 453         }
 454         return zsend_label_manager_connect_response(client, vrf_id, result);
 455 }
 456
 457 /* Respond to a get_chunk request */
 458 int lm_get_chunk_response(struct label_manager_chunk *lmc, struct zserv *client,
 459                           vrf_id_t vrf_id)
 460 {
 461         if (!lmc)
 462                 flog_err(EC_ZEBRA_LM_CANNOT_ASSIGN_CHUNK,
 463                          "Unable to assign Label Chunk to %s instance %u",
 464                          zebra_route_string(client->proto), client->instance);
 465         else if (IS_ZEBRA_DEBUG_PACKET)
 466                 zlog_debug("Assigned Label Chunk %u - %u to %s instance %u",
 467                            lmc->start, lmc->end,
 468                            zebra_route_string(client->proto), client->instance);
 469
 470         return zsend_assign_label_chunk_response(client, vrf_id, lmc);
 471 }
 472
 473 void label_manager_close(void)
 474 {
 475         list_delete(&lbl_mgr.lc_list);
 476 }