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