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 FreeRangeRouting (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,
  56             (uint8_t proto, uint16_t instance, vrf_id_t vrf_id),
  57             (proto, instance, vrf_id));
  58 DEFINE_HOOK(lm_client_disconnect, (uint8_t proto, uint16_t instance),
  59             (proto, instance));
  60 DEFINE_HOOK(lm_get_chunk,
  61             (struct label_manager_chunk * *lmc, uint8_t proto,
  62              uint16_t instance, uint8_t keep, uint32_t size, uint32_t base,
  63              vrf_id_t vrf_id),
  64             (lmc, proto, instance, keep, size, base, vrf_id));
  65 DEFINE_HOOK(lm_release_chunk,
  66             (uint8_t proto, uint16_t instance, uint32_t start, uint32_t end),
  67             (proto, instance, start, end));
  68 DEFINE_HOOK(lm_cbs_inited, (), ());
  69
  70 /* define wrappers to be called in zapi_msg.c (as hooks must be called in
  71  * source file where they were defined)
  72  */
  73 void lm_client_connect_call(uint8_t proto, uint16_t instance, vrf_id_t vrf_id)
  74 {
  75         hook_call(lm_client_connect, proto, instance, vrf_id);
  76 }
  77 void lm_get_chunk_call(struct label_manager_chunk **lmc, uint8_t proto,
  78                        uint16_t instance, uint8_t keep, uint32_t size,
  79                        uint32_t base, vrf_id_t vrf_id)
  80 {
  81         hook_call(lm_get_chunk, lmc, proto, instance, keep, size, base, vrf_id);
  82 }
  83 void lm_release_chunk_call(uint8_t proto, uint16_t instance, uint32_t start,
  84                            uint32_t end)
  85 {
  86         hook_call(lm_release_chunk, proto, instance, start, end);
  87 }
  88
  89 /* forward declarations of the static functions to be used for some hooks */
  90 static int label_manager_connect(uint8_t proto, uint16_t instance,
  91                                  vrf_id_t vrf_id);
  92 static int label_manager_disconnect(uint8_t proto, uint16_t instance);
  93 static int label_manager_get_chunk(struct label_manager_chunk **lmc,
  94                                    uint8_t proto, uint16_t instance,
  95                                    uint8_t keep, uint32_t size, uint32_t base,
  96                                    vrf_id_t vrf_id);
  97
  98 void delete_label_chunk(void *val)
  99 {
 100         XFREE(MTYPE_LM_CHUNK, val);
 101 }
 102
 103 /**
 104  * Release label chunks from a client.
 105  *
 106  * Called on client disconnection or reconnection. It only releases chunks
 107  * with empty keep value.
 108  *
 109  * @param proto Daemon protocol of client, to identify the owner
 110  * @param instance Instance, to identify the owner
 111  * @return Number of chunks released
 112  */
 113 int release_daemon_label_chunks(uint8_t proto, unsigned short instance)
 114 {
 115         struct listnode *node;
 116         struct label_manager_chunk *lmc;
 117         int count = 0;
 118         int ret;
 119
 120         if (IS_ZEBRA_DEBUG_PACKET)
 121                 zlog_debug("%s: Releasing chunks for client proto %s, instance %d",
 122                            __func__, zebra_route_string(proto), instance);
 123
 124         for (ALL_LIST_ELEMENTS_RO(lbl_mgr.lc_list, node, lmc)) {
 125                 if (lmc->proto == proto && lmc->instance == instance
 126                     && lmc->keep == 0) {
 127                         ret = release_label_chunk(lmc->proto, lmc->instance,
 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         uint8_t proto = client->proto;
 143         uint16_t instance = client->instance;
 144
 145         hook_call(lm_client_disconnect, proto, instance);
 146         return 0;
 147 }
 148
 149 void lm_hooks_register(void)
 150 {
 151         hook_register(lm_client_connect, label_manager_connect);
 152         hook_register(lm_client_disconnect, label_manager_disconnect);
 153         hook_register(lm_get_chunk, label_manager_get_chunk);
 154         hook_register(lm_release_chunk, release_label_chunk);
 155 }
 156 void lm_hooks_unregister(void)
 157 {
 158         hook_unregister(lm_client_connect, label_manager_connect);
 159         hook_unregister(lm_client_disconnect, label_manager_disconnect);
 160         hook_unregister(lm_get_chunk, label_manager_get_chunk);
 161         hook_unregister(lm_release_chunk, release_label_chunk);
 162 }
 163
 164 /**
 165  * Init label manager (or proxy to an external one)
 166  */
 167 void label_manager_init(void)
 168 {
 169         lbl_mgr.lc_list = list_new();
 170         lbl_mgr.lc_list->del = delete_label_chunk;
 171         hook_register(zserv_client_close, lm_client_disconnect_cb);
 172
 173         /* register default hooks for the label manager actions */
 174         lm_hooks_register();
 175
 176         /* notify any external module that we are done */
 177         hook_call(lm_cbs_inited);
 178 }
 179
 180 /* alloc and fill a label chunk */
 181 struct label_manager_chunk *create_label_chunk(uint8_t proto,
 182                                                unsigned short instance,
 183                                                uint8_t keep, uint32_t start,
 184                                                uint32_t end)
 185 {
 186         /* alloc chunk, fill it and return it */
 187         struct label_manager_chunk *lmc =
 188                 XCALLOC(MTYPE_LM_CHUNK, sizeof(struct label_manager_chunk));
 189
 190         lmc->start = start;
 191         lmc->end = end;
 192         lmc->proto = proto;
 193         lmc->instance = instance;
 194         lmc->keep = keep;
 195
 196         return lmc;
 197 }
 198
 199 /* attempt to get a specific label chunk */
 200 static struct label_manager_chunk *
 201 assign_specific_label_chunk(uint8_t proto, unsigned short instance,
 202                             uint8_t keep, uint32_t size, 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, keep, base, end);
 252                 listnode_add_before(lbl_mgr.lc_list, insert_node, lmc);
 253                 return lmc;
 254         }
 255
 256         if (first_node) {
 257                 /* get node past the last one, if there */
 258                 if (last_node)
 259                         last_node = listnextnode(last_node);
 260
 261                 /* delete node coming after the above chunk whose labels are
 262                  * included in the previous one */
 263                 for (node = first_node; node && (node != last_node);
 264                      node = next) {
 265                         next = listnextnode(node);
 266                         list_delete_node(lbl_mgr.lc_list, node);
 267                 }
 268
 269                 lmc = create_label_chunk(proto, instance, keep, base, end);
 270                 if (last_node)
 271                         listnode_add_before(lbl_mgr.lc_list, last_node, lmc);
 272                 else
 273                         listnode_add(lbl_mgr.lc_list, lmc);
 274
 275                 return lmc;
 276         } else {
 277                 /* create a new chunk past all the existing ones and link at
 278                  * tail */
 279                 lmc = create_label_chunk(proto, instance, keep, base, end);
 280                 listnode_add(lbl_mgr.lc_list, lmc);
 281                 return lmc;
 282         }
 283 }
 284
 285 /**
 286  * Core function, assigns label chunks
 287  *
 288  * It first searches through the list to check if there's one available
 289  * (previously released). Otherwise it creates and assigns a new one
 290  *
 291  * @param proto Daemon protocol of client, to identify the owner
 292  * @param instance Instance, to identify the owner
 293  * @param keep If set, avoid garbage collection
 294  * @param size Size of the label chunk
 295  * @param base Desired starting label of the chunk; if MPLS_LABEL_BASE_ANY it does not apply
 296  * @return Pointer to the assigned label chunk, or NULL if the request could not be satisfied
 297  */
 298 struct label_manager_chunk *assign_label_chunk(uint8_t proto,
 299                                                unsigned short instance,
 300                                                uint8_t keep, uint32_t size,
 301                                                uint32_t base)
 302 {
 303         struct label_manager_chunk *lmc;
 304         struct listnode *node;
 305         uint32_t prev_end = 0;
 306
 307         /* handle chunks request with a specific base label */
 308         if (base != MPLS_LABEL_BASE_ANY)
 309                 return assign_specific_label_chunk(proto, instance, keep, size,
 310                                                    base);
 311
 312         /* appease scan-build, who gets confused by the use of macros */
 313         assert(lbl_mgr.lc_list);
 314
 315         /* first check if there's one available */
 316         for (ALL_LIST_ELEMENTS_RO(lbl_mgr.lc_list, node, lmc)) {
 317                 if (lmc->proto == NO_PROTO
 318                     && lmc->end - lmc->start + 1 == size) {
 319                         lmc->proto = proto;
 320                         lmc->instance = instance;
 321                         lmc->keep = keep;
 322                         return lmc;
 323                 }
 324                 /* check if we hadve a "hole" behind us that we can squeeze into
 325                  */
 326                 if ((lmc->start > prev_end)
 327                     && (lmc->start - prev_end >= size)) {
 328                         lmc = create_label_chunk(proto, instance, keep,
 329                                                  prev_end + 1, prev_end + size);
 330                         listnode_add_before(lbl_mgr.lc_list, node, lmc);
 331                         return lmc;
 332                 }
 333                 prev_end = lmc->end;
 334         }
 335         /* otherwise create a new one */
 336         uint32_t start_free;
 337
 338         if (list_isempty(lbl_mgr.lc_list))
 339                 start_free = MPLS_LABEL_UNRESERVED_MIN;
 340         else
 341                 start_free = ((struct label_manager_chunk *)listgetdata(
 342                                       listtail(lbl_mgr.lc_list)))
 343                                      ->end
 344                              + 1;
 345
 346         if (start_free > MPLS_LABEL_UNRESERVED_MAX - size + 1) {
 347                 flog_err(EC_ZEBRA_LM_EXHAUSTED_LABELS,
 348                          "Reached max labels. Start: %u, size: %u", start_free,
 349                          size);
 350                 return NULL;
 351         }
 352
 353         /* create chunk and link at tail */
 354         lmc = create_label_chunk(proto, instance, keep, start_free,
 355                                  start_free + size - 1);
 356         listnode_add(lbl_mgr.lc_list, lmc);
 357         return lmc;
 358 }
 359
 360 /**
 361  * Core function, release no longer used label chunks
 362  *
 363  * @param proto Daemon protocol of client, to identify the owner
 364  * @param instance Instance, to identify the owner
 365  * @param start First label of the chunk
 366  * @param end Last label of the chunk
 367  * @return 0 on success, -1 otherwise
 368  */
 369 int release_label_chunk(uint8_t proto, unsigned short instance, uint32_t start,
 370                         uint32_t end)
 371 {
 372         struct listnode *node;
 373         struct label_manager_chunk *lmc;
 374         int ret = -1;
 375
 376         /* check that size matches */
 377         if (IS_ZEBRA_DEBUG_PACKET)
 378                 zlog_debug("Releasing label chunk: %u - %u", start, end);
 379         /* find chunk and disown */
 380         for (ALL_LIST_ELEMENTS_RO(lbl_mgr.lc_list, node, lmc)) {
 381                 if (lmc->start != start)
 382                         continue;
 383                 if (lmc->end != end)
 384                         continue;
 385                 if (lmc->proto != proto || lmc->instance != instance) {
 386                         flog_err(EC_ZEBRA_LM_DAEMON_MISMATCH,
 387                                  "%s: Daemon mismatch!!", __func__);
 388                         continue;
 389                 }
 390                 lmc->proto = NO_PROTO;
 391                 lmc->instance = 0;
 392                 lmc->keep = 0;
 393                 ret = 0;
 394                 break;
 395         }
 396         if (ret != 0)
 397                 flog_err(EC_ZEBRA_LM_UNRELEASED_CHUNK,
 398                          "%s: Label chunk not released!!", __func__);
 399
 400         return ret;
 401 }
 402
 403 /* default functions to be called on hooks  */
 404 static int label_manager_connect(uint8_t proto, uint16_t instance,
 405                                  vrf_id_t vrf_id)
 406 {
 407         /*
 408          * Release previous labels of same protocol and instance.
 409          * This is done in case it restarted from an unexpected shutdown.
 410          */
 411         release_daemon_label_chunks(proto, instance);
 412         return lm_client_connect_response(proto, instance, vrf_id, 0);
 413 }
 414 static int label_manager_disconnect(uint8_t proto, uint16_t instance)
 415 {
 416         release_daemon_label_chunks(proto, instance);
 417         return 0;
 418 }
 419 static int label_manager_get_chunk(struct label_manager_chunk **lmc,
 420                                    uint8_t proto, uint16_t instance,
 421                                    uint8_t keep, uint32_t size, uint32_t base,
 422                                    vrf_id_t vrf_id)
 423 {
 424         *lmc = assign_label_chunk(proto, instance, keep, size, base);
 425         return lm_get_chunk_response(*lmc, proto, instance, vrf_id);
 426 }
 427
 428 /* Respond to a connect request */
 429 int lm_client_connect_response(uint8_t proto, uint16_t instance,
 430                                vrf_id_t vrf_id, uint8_t result)
 431 {
 432         struct zserv *client = zserv_find_client(proto, instance);
 433         if (!client) {
 434                 zlog_err("%s: could not find client for daemon %s instance %u",
 435                          __func__, zebra_route_string(proto), instance);
 436                 return 1;
 437         }
 438         return zsend_label_manager_connect_response(client, vrf_id, result);
 439 }
 440
 441 /* Respond to a get_chunk request */
 442 int lm_get_chunk_response(struct label_manager_chunk *lmc, uint8_t proto,
 443                           uint16_t instance, vrf_id_t vrf_id)
 444 {
 445         struct zserv *client = zserv_find_client(proto, instance);
 446         if (!client) {
 447                 zlog_err("%s: could not find client for daemon %s instance %u",
 448                          __func__, zebra_route_string(proto), instance);
 449                 return 1;
 450         }
 451         return zsend_assign_label_chunk_response(client, vrf_id, proto,
 452                                                  instance, lmc);
 453 }
 454
 455 void label_manager_close(void)
 456 {
 457         list_delete(&lbl_mgr.lc_list);
 458 }