lib/table.h

   1 // SPDX-License-Identifier: GPL-2.0-or-later
   2 /*
   3  * Routing Table
   4  * Copyright (C) 1998 Kunihiro Ishiguro
   5  */
   6
   7 #ifndef _ZEBRA_TABLE_H
   8 #define _ZEBRA_TABLE_H
   9
  10 #include "memory.h"
  11 #include "hash.h"
  12 #include "prefix.h"
  13 #include "typesafe.h"
  14
  15 #ifdef __cplusplus
  16 extern "C" {
  17 #endif
  18
  19 DECLARE_MTYPE(ROUTE_NODE);
  20
  21 /*
  22  * Forward declarations.
  23  */
  24 struct route_node;
  25 struct route_table;
  26
  27 /*
  28  * route_table_delegate_t
  29  *
  30  * Function vector that can be used by a client to customize the
  31  * behavior of one or more route tables.
  32  */
  33 typedef const struct route_table_delegate_t_ route_table_delegate_t;
  34
  35 typedef struct route_node *(*route_table_create_node_func_t)(
  36         route_table_delegate_t *, struct route_table *);
  37
  38 typedef void (*route_table_destroy_node_func_t)(route_table_delegate_t *,
  39                                                 struct route_table *,
  40                                                 struct route_node *);
  41
  42 struct route_table_delegate_t_ {
  43         route_table_create_node_func_t create_node;
  44         route_table_destroy_node_func_t destroy_node;
  45 };
  46
  47 PREDECL_HASH(rn_hash_node);
  48
  49 /* Routing table top structure. */
  50 struct route_table {
  51         struct route_node *top;
  52         struct rn_hash_node_head hash;
  53
  54         /*
  55          * Delegate that performs certain functions for this table.
  56          */
  57         route_table_delegate_t *delegate;
  58         void (*cleanup)(struct route_table *, struct route_node *);
  59
  60         unsigned long count;
  61
  62         /*
  63          * User data.
  64          */
  65         void *info;
  66 };
  67
  68 /*
  69  * node->link is really internal to the table code and should not be
  70  * accessed by outside code.  We don't have any writers (yay), though some
  71  * readers are left to be fixed.
  72  *
  73  * rationale: we need to add a hash table in parallel, to speed up
  74  * exact-match lookups.
  75  *
  76  * same really applies for node->parent, though that's less of an issue.
  77  * table->link should be - and is - NEVER written by outside code
  78  */
  79 #ifdef FRR_COMPILING_TABLE_C
  80 #define table_rdonly(x)         x
  81 #define table_internal(x)       x
  82 #else
  83 #define table_rdonly(x)         const x
  84 #define table_internal(x)                                                      \
  85         const x __attribute__(                                                 \
  86                 (deprecated("this should only be accessed by lib/table.c")))
  87 /* table_internal is for node->link and node->lock, once we have done
  88  * something about remaining accesses */
  89 #endif
  90
  91 /* so... the problem with this is that "const" doesn't mean "readonly".
  92  * It in fact may allow the compiler to optimize based on the assumption
  93  * that the value doesn't change.  Hence, since the only purpose of this
  94  * is to aid in development, don't put the "const" in release builds.
  95  *
  96  * (I haven't seen this actually break, but GCC and LLVM are getting ever
  97  * more aggressive in optimizing...)
  98  */
  99 #ifndef DEV_BUILD
 100 #undef table_rdonly
 101 #define table_rdonly(x) x
 102 #endif
 103
 104 /*
 105  * Macro that defines all fields in a route node.
 106  */
 107 #define ROUTE_NODE_FIELDS                                                      \
 108         /* Actual prefix of this radix. */                                     \
 109         struct prefix p;                                                       \
 110                                                                                \
 111         /* Tree link. */                                                       \
 112         struct route_table *table_rdonly(table);                               \
 113         struct route_node *table_rdonly(parent);                               \
 114         struct route_node *table_rdonly(link[2]);                              \
 115                                                                                \
 116         /* Lock of this radix */                                               \
 117         unsigned int table_rdonly(lock);                                       \
 118                                                                                \
 119         struct rn_hash_node_item nodehash;                                     \
 120         /* Each node of route. */                                              \
 121         void *info;                                                            \
 122
 123
 124 /* Each routing entry. */
 125 struct route_node {
 126         ROUTE_NODE_FIELDS
 127
 128 #define l_left   link[0]
 129 #define l_right  link[1]
 130 };
 131
 132 typedef struct route_table_iter_t_ route_table_iter_t;
 133
 134 typedef enum {
 135         RT_ITER_STATE_INIT,
 136         RT_ITER_STATE_ITERATING,
 137         RT_ITER_STATE_PAUSED,
 138         RT_ITER_STATE_DONE
 139 } route_table_iter_state_t;
 140
 141 /*
 142  * route_table_iter_t
 143  *
 144  * Structure that holds state for iterating over a route table.
 145  */
 146 struct route_table_iter_t_ {
 147
 148         route_table_iter_state_t state;
 149
 150         /*
 151          * Routing table that we are iterating over. The caller must ensure
 152          * that that table outlives the iterator.
 153          */
 154         struct route_table *table;
 155
 156         /*
 157          * The node that the iterator is currently on.
 158          */
 159         struct route_node *current;
 160
 161         /*
 162          * The last prefix that the iterator processed before it was paused.
 163          */
 164         struct prefix pause_prefix;
 165 };
 166
 167 /* Prototypes. */
 168 extern struct route_table *route_table_init(void);
 169
 170 extern struct route_table *
 171 route_table_init_with_delegate(route_table_delegate_t *delegate);
 172
 173 extern route_table_delegate_t *route_table_get_default_delegate(void);
 174
 175 static inline void *route_table_get_info(struct route_table *table)
 176 {
 177         return table->info;
 178 }
 179
 180 static inline void route_table_set_info(struct route_table *table, void *d)
 181 {
 182         table->info = d;
 183 }
 184
 185 extern void route_table_finish(struct route_table *table);
 186 extern struct route_node *route_top(struct route_table *table);
 187 extern struct route_node *route_next(struct route_node *node);
 188 extern struct route_node *route_next_until(struct route_node *node,
 189                                            const struct route_node *limit);
 190 extern struct route_node *route_node_get(struct route_table *table,
 191                                          union prefixconstptr pu);
 192 extern struct route_node *route_node_lookup(struct route_table *table,
 193                                             union prefixconstptr pu);
 194 extern struct route_node *route_node_lookup_maynull(struct route_table *table,
 195                                                     union prefixconstptr pu);
 196 extern struct route_node *route_node_match(struct route_table *table,
 197                                            union prefixconstptr pu);
 198 extern struct route_node *route_node_match_ipv4(struct route_table *table,
 199                                                 const struct in_addr *addr);
 200 extern struct route_node *route_node_match_ipv6(struct route_table *table,
 201                                                 const struct in6_addr *addr);
 202
 203 extern unsigned long route_table_count(struct route_table *table);
 204
 205 extern struct route_node *route_node_create(route_table_delegate_t *delegate,
 206                                             struct route_table *table);
 207 extern void route_node_delete(struct route_node *node);
 208 extern void route_node_destroy(route_table_delegate_t *delegate,
 209                                struct route_table *table,
 210                                struct route_node *node);
 211
 212 extern struct route_node *route_table_get_next(struct route_table *table,
 213                                                union prefixconstptr pu);
 214 extern int route_table_prefix_iter_cmp(const struct prefix *p1,
 215                                        const struct prefix *p2);
 216
 217 /*
 218  * Iterator functions.
 219  */
 220 extern void route_table_iter_init(route_table_iter_t *iter,
 221                                   struct route_table *table);
 222 extern void route_table_iter_pause(route_table_iter_t *iter);
 223 extern void route_table_iter_cleanup(route_table_iter_t *iter);
 224
 225 /*
 226  * Inline functions.
 227  */
 228
 229 /* Lock node. */
 230 static inline struct route_node *route_lock_node(struct route_node *node)
 231 {
 232         (*(unsigned *)&node->lock)++;
 233         return node;
 234 }
 235
 236 /* Unlock node. */
 237 static inline void route_unlock_node(struct route_node *node)
 238 {
 239         assert(node->lock > 0);
 240         (*(unsigned *)&node->lock)--;
 241
 242         if (node->lock == 0)
 243                 route_node_delete(node);
 244 }
 245
 246 static inline unsigned int route_node_get_lock_count(struct route_node *node)
 247 {
 248         return node->lock;
 249 }
 250
 251 /*
 252  * route_table_iter_next
 253  *
 254  * Get the next node in the tree.
 255  */
 256 static inline struct route_node *route_table_iter_next(route_table_iter_t *iter)
 257 {
 258         struct route_node *node;
 259
 260         switch (iter->state) {
 261
 262         case RT_ITER_STATE_INIT:
 263
 264                 /*
 265                  * We're just starting the iteration.
 266                  */
 267                 node = route_top(iter->table);
 268                 break;
 269
 270         case RT_ITER_STATE_ITERATING:
 271                 node = route_next(iter->current);
 272                 break;
 273
 274         case RT_ITER_STATE_PAUSED:
 275
 276                 /*
 277                  * Start with the node following pause_prefix.
 278                  */
 279                 node = route_table_get_next(iter->table, &iter->pause_prefix);
 280                 break;
 281
 282         case RT_ITER_STATE_DONE:
 283                 return NULL;
 284
 285         default:
 286                 /* Suppress uninitialized variable warning */
 287                 node = NULL;
 288                 assert(0);
 289         }
 290
 291         iter->current = node;
 292         if (node)
 293                 iter->state = RT_ITER_STATE_ITERATING;
 294         else
 295                 iter->state = RT_ITER_STATE_DONE;
 296
 297         return node;
 298 }
 299
 300 /*
 301  * route_table_iter_is_done
 302  *
 303  * Returns true if the iteration is complete.
 304  */
 305 static inline int route_table_iter_is_done(route_table_iter_t *iter)
 306 {
 307         return iter->state == RT_ITER_STATE_DONE;
 308 }
 309
 310 /*
 311  * route_table_iter_started
 312  *
 313  * Returns true if this iterator has started iterating over the tree.
 314  */
 315 static inline int route_table_iter_started(route_table_iter_t *iter)
 316 {
 317         return iter->state != RT_ITER_STATE_INIT;
 318 }
 319
 320 #ifdef _FRR_ATTRIBUTE_PRINTFRR
 321 #pragma FRR printfrr_ext "%pRN"  (struct route_node *)
 322 #endif
 323
 324 #ifdef __cplusplus
 325 }
 326 #endif
 327
 328 #endif /* _ZEBRA_TABLE_H */