lib/srcdest_table.c

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