zebra/label_manager.c

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