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 *create_label_chunk(uint8_t proto,
 179                                                unsigned short instance,
 180                                                uint32_t session_id,
 181                                                uint8_t keep, uint32_t start,
 182                                                uint32_t end)
 183 {
 184         /* alloc chunk, fill it and return it */
 185         struct label_manager_chunk *lmc =
 186                 XCALLOC(MTYPE_LM_CHUNK, sizeof(struct label_manager_chunk));
 187
 188         lmc->start = start;
 189         lmc->end = end;
 190         lmc->proto = proto;
 191         lmc->instance = instance;
 192         lmc->session_id = session_id;
 193         lmc->keep = keep;
 194
 195         return lmc;
 196 }
 197
 198 /* attempt to get a specific label chunk */
 199 static struct label_manager_chunk *
 200 assign_specific_label_chunk(uint8_t proto, unsigned short instance,
 201                             uint32_t session_id, uint8_t keep, uint32_t size,
 202                             uint32_t base)
 203 {
 204         struct label_manager_chunk *lmc;
 205         struct listnode *node, *next = NULL;
 206         struct listnode *first_node = NULL;
 207         struct listnode *last_node = NULL;
 208         struct listnode *insert_node = NULL;
 209
 210         /* precompute last label from base and size */
 211         uint32_t end = base + size - 1;
 212
 213         /* sanities */
 214         if ((base < MPLS_LABEL_UNRESERVED_MIN)
 215             || (end > MPLS_LABEL_UNRESERVED_MAX)) {
 216                 zlog_err("Invalid LM request arguments: base: %u, size: %u",
 217                          base, size);
 218                 return NULL;
 219         }
 220
 221         /* Scan the existing chunks to see if the requested range of labels
 222          * falls inside any of such chunks */
 223         for (ALL_LIST_ELEMENTS_RO(lbl_mgr.lc_list, node, lmc)) {
 224
 225                 /* skip chunks for labels < base */
 226                 if (base > lmc->end)
 227                         continue;
 228
 229                 /* requested range is not covered by any existing, free chunk.
 230                  * Therefore, need to insert a chunk */
 231                 if ((end < lmc->start) && !first_node) {
 232                         insert_node = node;
 233                         break;
 234                 }
 235
 236                 if (!first_node)
 237                         first_node = node;
 238
 239                 /* if chunk is used, cannot honor request */
 240                 if (lmc->proto != NO_PROTO)
 241                         return NULL;
 242
 243                 if (end <= lmc->end) {
 244                         last_node = node;
 245                         break;
 246                 }
 247         }
 248
 249         /* insert chunk between existing chunks */
 250         if (insert_node) {
 251                 lmc = create_label_chunk(proto, instance, session_id, keep,
 252                                          base, end);
 253                 listnode_add_before(lbl_mgr.lc_list, insert_node, lmc);
 254                 return lmc;
 255         }
 256
 257         if (first_node) {
 258                 /* get node past the last one, if there */
 259                 if (last_node)
 260                         last_node = listnextnode(last_node);
 261
 262                 /* delete node coming after the above chunk whose labels are
 263                  * included in the previous one */
 264                 for (node = first_node; node && (node != last_node);
 265                      node = next) {
 266                         struct label_manager_chunk *death;
 267
 268                         next = listnextnode(node);
 269                         death = listgetdata(node);
 270                         list_delete_node(lbl_mgr.lc_list, node);
 271                         delete_label_chunk(death);
 272                 }
 273
 274                 lmc = create_label_chunk(proto, instance, session_id, keep,
 275                                          base, end);
 276                 if (last_node)
 277                         listnode_add_before(lbl_mgr.lc_list, last_node, lmc);
 278                 else
 279                         listnode_add(lbl_mgr.lc_list, lmc);
 280
 281                 return lmc;
 282         } else {
 283                 /* create a new chunk past all the existing ones and link at
 284                  * tail */
 285                 lmc = create_label_chunk(proto, instance, session_id, keep,
 286                                          base, end);
 287                 listnode_add(lbl_mgr.lc_list, lmc);
 288                 return lmc;
 289         }
 290 }
 291
 292 /**
 293  * Core function, assigns label chunks
 294  *
 295  * It first searches through the list to check if there's one available
 296  * (previously released). Otherwise it creates and assigns a new one
 297  *
 298  * @param proto Daemon protocol of client, to identify the owner
 299  * @param instance Instance, to identify the owner
 300  * @param keep If set, avoid garbage collection
 301  * @param size Size of the label chunk
 302  * @param base Desired starting label of the chunk; if MPLS_LABEL_BASE_ANY it does not apply
 303  * @return Pointer to the assigned label chunk, or NULL if the request could not be satisfied
 304  */
 305 struct label_manager_chunk *assign_label_chunk(uint8_t proto,
 306                                                unsigned short instance,
 307                                                uint32_t session_id,
 308                                                uint8_t keep, uint32_t size,
 309                                                uint32_t base)
 310 {
 311         struct label_manager_chunk *lmc;
 312         struct listnode *node;
 313         uint32_t prev_end = 0;
 314
 315         /* handle chunks request with a specific base label */
 316         if (base != MPLS_LABEL_BASE_ANY)
 317                 return assign_specific_label_chunk(proto, instance, session_id,
 318                                                    keep, size, base);
 319
 320         /* appease scan-build, who gets confused by the use of macros */
 321         assert(lbl_mgr.lc_list);
 322
 323         /* first check if there's one available */
 324         for (ALL_LIST_ELEMENTS_RO(lbl_mgr.lc_list, node, lmc)) {
 325                 if (lmc->proto == NO_PROTO
 326                     && lmc->end - lmc->start + 1 == size) {
 327                         lmc->proto = proto;
 328                         lmc->instance = instance;
 329                         lmc->session_id = session_id;
 330                         lmc->keep = keep;
 331                         return lmc;
 332                 }
 333                 /* check if we hadve a "hole" behind us that we can squeeze into
 334                  */
 335                 if ((lmc->start > prev_end)
 336                     && (lmc->start - prev_end >= size)) {
 337                         lmc = create_label_chunk(proto, instance, session_id,
 338                                                  keep, prev_end + 1,
 339                                                  prev_end + size);
 340                         listnode_add_before(lbl_mgr.lc_list, node, lmc);
 341                         return lmc;
 342                 }
 343                 prev_end = lmc->end;
 344         }
 345         /* otherwise create a new one */
 346         uint32_t start_free;
 347
 348         if (list_isempty(lbl_mgr.lc_list))
 349                 start_free = MPLS_LABEL_UNRESERVED_MIN;
 350         else
 351                 start_free = ((struct label_manager_chunk *)listgetdata(
 352                                       listtail(lbl_mgr.lc_list)))
 353                                      ->end
 354                              + 1;
 355
 356         if (start_free > MPLS_LABEL_UNRESERVED_MAX - size + 1) {
 357                 flog_err(EC_ZEBRA_LM_EXHAUSTED_LABELS,
 358                          "Reached max labels. Start: %u, size: %u", start_free,
 359                          size);
 360                 return NULL;
 361         }
 362
 363         /* create chunk and link at tail */
 364         lmc = create_label_chunk(proto, instance, session_id, keep, start_free,
 365                                  start_free + size - 1);
 366         listnode_add(lbl_mgr.lc_list, lmc);
 367         return lmc;
 368 }
 369
 370 /**
 371  * Release label chunks from a client.
 372  *
 373  * Called on client disconnection or reconnection. It only releases chunks
 374  * with empty keep value.
 375  *
 376  * @param client Client zapi session
 377  * @param start First label of the chunk
 378  * @param end Last label of the chunk
 379  * @return 0 on success
 380  */
 381 static int label_manager_release_label_chunk(struct zserv *client,
 382                                              uint32_t start, uint32_t end)
 383 {
 384         return release_label_chunk(client->proto, client->instance,
 385                                    client->session_id, start, end);
 386 }
 387
 388 /**
 389  * Core function, release no longer used label chunks
 390  *
 391  * @param proto Daemon protocol of client, to identify the owner
 392  * @param instance Instance, to identify the owner
 393  * @param start First label of the chunk
 394  * @param end Last label of the chunk
 395  * @return 0 on success, -1 otherwise
 396  */
 397 int release_label_chunk(uint8_t proto, unsigned short instance,
 398                         uint32_t session_id, uint32_t start, uint32_t end)
 399 {
 400         struct listnode *node;
 401         struct label_manager_chunk *lmc;
 402         int ret = -1;
 403
 404         /* check that size matches */
 405         if (IS_ZEBRA_DEBUG_PACKET)
 406                 zlog_debug("Releasing label chunk: %u - %u", start, end);
 407         /* find chunk and disown */
 408         for (ALL_LIST_ELEMENTS_RO(lbl_mgr.lc_list, node, lmc)) {
 409                 if (lmc->start != start)
 410                         continue;
 411                 if (lmc->end != end)
 412                         continue;
 413                 if (lmc->proto != proto || lmc->instance != instance ||
 414                     lmc->session_id != session_id) {
 415                         flog_err(EC_ZEBRA_LM_DAEMON_MISMATCH,
 416                                  "%s: Daemon mismatch!!", __func__);
 417                         continue;
 418                 }
 419                 lmc->proto = NO_PROTO;
 420                 lmc->instance = 0;
 421                 lmc->session_id = 0;
 422                 lmc->keep = 0;
 423                 ret = 0;
 424                 break;
 425         }
 426         if (ret != 0)
 427                 flog_err(EC_ZEBRA_LM_UNRELEASED_CHUNK,
 428                          "%s: Label chunk not released!!", __func__);
 429
 430         return ret;
 431 }
 432
 433 /* default functions to be called on hooks  */
 434 static int label_manager_connect(struct zserv *client, vrf_id_t vrf_id)
 435 {
 436         /*
 437          * Release previous labels of same protocol and instance.
 438          * This is done in case it restarted from an unexpected shutdown.
 439          */
 440         release_daemon_label_chunks(client);
 441         return zsend_label_manager_connect_response(client, vrf_id, 0);
 442 }
 443 static int label_manager_disconnect(struct zserv *client)
 444 {
 445         release_daemon_label_chunks(client);
 446         return 0;
 447 }
 448 static int label_manager_get_chunk(struct label_manager_chunk **lmc,
 449                                    struct zserv *client, uint8_t keep,
 450                                    uint32_t size, uint32_t base,
 451                                    vrf_id_t vrf_id)
 452 {
 453         *lmc = assign_label_chunk(client->proto, client->instance,
 454                                   client->session_id, keep, size, base);
 455         return lm_get_chunk_response(*lmc, client, vrf_id);
 456 }
 457
 458 /* Respond to a connect request */
 459 int lm_client_connect_response(uint8_t proto, uint16_t instance,
 460                                uint32_t session_id, vrf_id_t vrf_id,
 461                                uint8_t result)
 462 {
 463         struct zserv *client = zserv_find_client_session(proto, instance,
 464                                                          session_id);
 465         if (!client) {
 466                 zlog_err("%s: could not find client for daemon %s instance %u session %u",
 467                          __func__, zebra_route_string(proto), instance,
 468                          session_id);
 469                 return 1;
 470         }
 471         return zsend_label_manager_connect_response(client, vrf_id, result);
 472 }
 473
 474 /* Respond to a get_chunk request */
 475 int lm_get_chunk_response(struct label_manager_chunk *lmc, struct zserv *client,
 476                           vrf_id_t vrf_id)
 477 {
 478         if (!lmc)
 479                 flog_err(EC_ZEBRA_LM_CANNOT_ASSIGN_CHUNK,
 480                          "Unable to assign Label Chunk to %s instance %u",
 481                          zebra_route_string(client->proto), client->instance);
 482         else if (IS_ZEBRA_DEBUG_PACKET)
 483                 zlog_debug("Assigned Label Chunk %u - %u to %s instance %u",
 484                            lmc->start, lmc->end,
 485                            zebra_route_string(client->proto), client->instance);
 486
 487         return zsend_assign_label_chunk_response(client, vrf_id, lmc);
 488 }
 489
 490 void label_manager_close(void)
 491 {
 492         list_delete(&lbl_mgr.lc_list);
 493 }