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