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