lib/srcdest_table.c

   1 // SPDX-License-Identifier: GPL-2.0-or-later
   2 /*
   3  * SRC-DEST Routing Table
   4  *
   5  * Copyright (C) 2017 by David Lamparter & Christian Franke,
   6  *                       Open Source Routing / NetDEF Inc.
   7  *
   8  * This file is part of FRRouting (FRR)
   9  */
  10
  11 #include <zebra.h>
  12
  13 #include "srcdest_table.h"
  14
  15 #include "memory.h"
  16 #include "prefix.h"
  17 #include "table.h"
  18 #include "printfrr.h"
  19
  20 DEFINE_MTYPE_STATIC(LIB, ROUTE_SRC_NODE, "Route source node");
  21
  22 /* ----- functions to manage rnodes _with_ srcdest table ----- */
  23 struct srcdest_rnode {
  24         /* must be first in structure for casting to/from route_node */
  25         ROUTE_NODE_FIELDS;
  26
  27         struct route_table *src_table;
  28 };
  29
  30 static struct srcdest_rnode *srcdest_rnode_from_rnode(struct route_node *rn)
  31 {
  32         assert(rnode_is_dstnode(rn));
  33         return (struct srcdest_rnode *)rn;
  34 }
  35
  36 static struct route_node *srcdest_rnode_to_rnode(struct srcdest_rnode *srn)
  37 {
  38         return (struct route_node *)srn;
  39 }
  40
  41 static struct route_node *srcdest_rnode_create(route_table_delegate_t *delegate,
  42                                                struct route_table *table)
  43 {
  44         struct srcdest_rnode *srn;
  45         srn = XCALLOC(MTYPE_ROUTE_NODE, sizeof(struct srcdest_rnode));
  46         return srcdest_rnode_to_rnode(srn);
  47 }
  48
  49 static void srcdest_rnode_destroy(route_table_delegate_t *delegate,
  50                                   struct route_table *table,
  51                                   struct route_node *rn)
  52 {
  53         struct srcdest_rnode *srn = srcdest_rnode_from_rnode(rn);
  54         struct route_table *src_table;
  55
  56         /* Clear route node's src_table here already, otherwise the
  57          * deletion of the last node in the src_table will trigger
  58          * another call to route_table_finish for the src_table.
  59          *
  60          * (Compare with srcdest_srcnode_destroy)
  61          */
  62         src_table = srn->src_table;
  63         srn->src_table = NULL;
  64         route_table_finish(src_table);
  65         XFREE(MTYPE_ROUTE_NODE, rn);
  66 }
  67
  68 route_table_delegate_t _srcdest_dstnode_delegate = {
  69         .create_node = srcdest_rnode_create,
  70         .destroy_node = srcdest_rnode_destroy};
  71
  72 /* ----- functions to manage rnodes _in_ srcdest table ----- */
  73
  74 /* node creation / deletion for srcdest source prefix nodes.
  75  * the route_node isn't actually different from the normal route_node,
  76  * but the cleanup is special to free the table (and possibly the
  77  * destination prefix's route_node) */
  78
  79 static struct route_node *
  80 srcdest_srcnode_create(route_table_delegate_t *delegate,
  81                        struct route_table *table)
  82 {
  83         return XCALLOC(MTYPE_ROUTE_SRC_NODE, sizeof(struct route_node));
  84 }
  85
  86 static void srcdest_srcnode_destroy(route_table_delegate_t *delegate,
  87                                     struct route_table *table,
  88                                     struct route_node *rn)
  89 {
  90         struct srcdest_rnode *srn;
  91
  92         XFREE(MTYPE_ROUTE_SRC_NODE, rn);
  93
  94         srn = route_table_get_info(table);
  95         if (srn->src_table && route_table_count(srn->src_table) == 0) {
  96                 /* deleting the route_table from inside destroy_node is ONLY
  97                  * permitted IF table->count is 0!  see lib/table.c
  98                  * route_node_delete()
  99                  * for details */
 100                 route_table_finish(srn->src_table);
 101                 srn->src_table = NULL;
 102
 103                 /* drop the ref we're holding in srcdest_node_get().  there
 104                  * might be
 105                  * non-srcdest routes, so the route_node may still exist.
 106                  * hence, it's
 107                  * important to clear src_table above. */
 108                 route_unlock_node(srcdest_rnode_to_rnode(srn));
 109         }
 110 }
 111
 112 route_table_delegate_t _srcdest_srcnode_delegate = {
 113         .create_node = srcdest_srcnode_create,
 114         .destroy_node = srcdest_srcnode_destroy};
 115
 116 /* NB: read comments in code for refcounting before using! */
 117 static struct route_node *srcdest_srcnode_get(struct route_node *rn,
 118                                               const struct prefix_ipv6 *src_p)
 119 {
 120         struct srcdest_rnode *srn;
 121
 122         if (!src_p || src_p->prefixlen == 0)
 123                 return rn;
 124
 125         srn = srcdest_rnode_from_rnode(rn);
 126         if (!srn->src_table) {
 127                 /* this won't use srcdest_rnode, we're already on the source
 128                  * here */
 129                 srn->src_table = route_table_init_with_delegate(
 130                         &_srcdest_srcnode_delegate);
 131                 route_table_set_info(srn->src_table, srn);
 132
 133                 /* there is no route_unlock_node on the original rn here.
 134                  * The reference is kept for the src_table. */
 135         } else {
 136                 /* only keep 1 reference for the src_table, makes the
 137                  * refcounting
 138                  * more similar to the non-srcdest case.  Either way after
 139                  * return from
 140                  * function, the only reference held is the one on the return
 141                  * value.
 142                  *
 143                  * We can safely drop our reference here because src_table is
 144                  * holding
 145                  * another reference, so this won't free rn */
 146                 route_unlock_node(rn);
 147         }
 148
 149         return route_node_get(srn->src_table, (const struct prefix *)src_p);
 150 }
 151
 152 static struct route_node *srcdest_srcnode_lookup(
 153         struct route_node *rn,
 154         const struct prefix_ipv6 *src_p)
 155 {
 156         struct srcdest_rnode *srn;
 157
 158         if (!rn || !src_p || src_p->prefixlen == 0)
 159                 return rn;
 160
 161         /* We got this rn from a lookup, so its refcnt was incremented. As we
 162          * won't
 163          * return return rn from any point beyond here, we should decrement its
 164          * refcnt.
 165          */
 166         route_unlock_node(rn);
 167
 168         srn = srcdest_rnode_from_rnode(rn);
 169         if (!srn->src_table)
 170                 return NULL;
 171
 172         return route_node_lookup(srn->src_table, (const struct prefix *)src_p);
 173 }
 174
 175 /* ----- exported functions ----- */
 176
 177 struct route_table *srcdest_table_init(void)
 178 {
 179         return route_table_init_with_delegate(&_srcdest_dstnode_delegate);
 180 }
 181
 182 struct route_node *srcdest_route_next(struct route_node *rn)
 183 {
 184         struct route_node *next, *parent;
 185
 186         /* For a non src-dest node, just return route_next */
 187         if (!(rnode_is_dstnode(rn) || rnode_is_srcnode(rn)))
 188                 return route_next(rn);
 189
 190         if (rnode_is_dstnode(rn)) {
 191                 /* This means the route_node is part of the top hierarchy
 192                  * and refers to a destination prefix. */
 193                 struct srcdest_rnode *srn = srcdest_rnode_from_rnode(rn);
 194
 195                 if (srn->src_table)
 196                         next = route_top(srn->src_table);
 197                 else
 198                         next = NULL;
 199
 200                 if (next) {
 201                         /* There is a source prefix. Return the node for it */
 202                         route_unlock_node(rn);
 203                         return next;
 204                 } else {
 205                         /* There is no source prefix, just continue as usual */
 206                         return route_next(rn);
 207                 }
 208         }
 209
 210         /* This part handles the case of iterating source nodes. */
 211         parent = route_lock_node(route_table_get_info(rn->table));
 212         next = route_next(rn);
 213
 214         if (next) {
 215                 /* There is another source node, continue in the source table */
 216                 route_unlock_node(parent);
 217                 return next;
 218         } else {
 219                 /* The source table is complete, continue in the parent table */
 220                 return route_next(parent);
 221         }
 222 }
 223
 224 struct route_node *srcdest_rnode_get(struct route_table *table,
 225                                      union prefixconstptr dst_pu,
 226                                      const struct prefix_ipv6 *src_p)
 227 {
 228         const struct prefix_ipv6 *dst_p = dst_pu.p6;
 229         struct route_node *rn;
 230
 231         rn = route_node_get(table, (const struct prefix *)dst_p);
 232         return srcdest_srcnode_get(rn, src_p);
 233 }
 234
 235 struct route_node *srcdest_rnode_lookup(struct route_table *table,
 236                                         union prefixconstptr dst_pu,
 237                                         const struct prefix_ipv6 *src_p)
 238 {
 239         const struct prefix_ipv6 *dst_p = dst_pu.p6;
 240         struct route_node *rn;
 241         struct route_node *srn;
 242
 243         rn = route_node_lookup_maynull(table, (const struct prefix *)dst_p);
 244         srn = srcdest_srcnode_lookup(rn, src_p);
 245
 246         if (rn != NULL && rn == srn && !rn->info) {
 247                 /* Match the behavior of route_node_lookup and don't return an
 248                  * empty route-node for a dest-route */
 249                 route_unlock_node(rn);
 250                 return NULL;
 251         }
 252         return srn;
 253 }
 254
 255 void srcdest_rnode_prefixes(const struct route_node *rn,
 256                             const struct prefix **p,
 257                             const struct prefix **src_p)
 258 {
 259         if (rnode_is_srcnode(rn)) {
 260                 struct route_node *dst_rn = route_table_get_info(rn->table);
 261                 if (p)
 262                         *p = &dst_rn->p;
 263                 if (src_p)
 264                         *src_p = &rn->p;
 265         } else {
 266                 if (p)
 267                         *p = &rn->p;
 268                 if (src_p)
 269                         *src_p = NULL;
 270         }
 271 }
 272
 273 const char *srcdest2str(const struct prefix *dst_p,
 274                         const struct prefix_ipv6 *src_p,
 275                         char *str, int size)
 276 {
 277         char dst_buf[PREFIX_STRLEN], src_buf[PREFIX_STRLEN];
 278
 279         snprintf(str, size, "%s%s%s",
 280                  prefix2str(dst_p, dst_buf, sizeof(dst_buf)),
 281                  (src_p && src_p->prefixlen) ? " from " : "",
 282                  (src_p && src_p->prefixlen)
 283                          ? prefix2str(src_p, src_buf, sizeof(src_buf))
 284                          : "");
 285         return str;
 286 }
 287
 288 const char *srcdest_rnode2str(const struct route_node *rn, char *str, int size)
 289 {
 290         const struct prefix *dst_p, *src_p;
 291
 292         srcdest_rnode_prefixes(rn, &dst_p, &src_p);
 293         return srcdest2str(dst_p, (const struct prefix_ipv6 *)src_p, str, size);
 294 }
 295
 296 printfrr_ext_autoreg_p("RN", printfrr_rn);
 297 static ssize_t printfrr_rn(struct fbuf *buf, struct printfrr_eargs *ea,
 298                            const void *ptr)
 299 {
 300         const struct route_node *rn = ptr;
 301         const struct prefix *dst_p, *src_p;
 302         char cbuf[PREFIX_STRLEN * 2 + 6];
 303
 304         if (!rn)
 305                 return bputs(buf, "(null)");
 306
 307         srcdest_rnode_prefixes(rn, &dst_p, &src_p);
 308         srcdest2str(dst_p, (const struct prefix_ipv6 *)src_p,
 309                     cbuf, sizeof(cbuf));
 310         return bputs(buf, cbuf);
 311 }
 312
 313 struct route_table *srcdest_srcnode_table(struct route_node *rn)
 314 {
 315         if (rnode_is_dstnode(rn)) {
 316                 struct srcdest_rnode *srn = srcdest_rnode_from_rnode(rn);
 317
 318                 return srn->src_table;
 319         }
 320         return NULL;
 321 }