src/tc_set.h

   1
   2 /*
   3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
   4  * Copyright (c) 2004-2009, the olsr.org team - see HISTORY file
   5  * All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  *
  11  * * Redistributions of source code must retain the above copyright
  12  *   notice, this list of conditions and the following disclaimer.
  13  * * Redistributions in binary form must reproduce the above copyright
  14  *   notice, this list of conditions and the following disclaimer in
  15  *   the documentation and/or other materials provided with the
  16  *   distribution.
  17  * * Neither the name of olsr.org, olsrd nor the names of its
  18  *   contributors may be used to endorse or promote products derived
  19  *   from this software without specific prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  25  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  26  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  29  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  31  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  32  * POSSIBILITY OF SUCH DAMAGE.
  33  *
  34  * Visit http://www.olsr.org for more information.
  35  *
  36  * If you find this software useful feel free to make a donation
  37  * to the project. For more information see the website or contact
  38  * the copyright holders.
  39  *
  40  */
  41 #ifndef _OLSR_TOP_SET
  42 #define _OLSR_TOP_SET
  43
  44 #include "defs.h"
  45 #include "common/avl.h"
  46 #include "common/list.h"
  47 #include "olsr_protocol.h"
  48 #include "lq_packet.h"
  49 #include "scheduler.h"
  50 #include "olsr_cookie.h"
  51 #include "duplicate_set.h"
  52
  53 /*
  54  * This file holds the definitions for the link state database.
  55  * The lsdb consists of nodes and edges.
  56  * During input parsing all nodes and edges are extracted and synthesized.
  57  * The SPF calculation operates on these datasets.
  58  */
  59
  60 struct tc_edge_entry {
  61   struct avl_node edge_node;           /* edge_tree node in tc_entry */
  62   union olsr_ip_addr T_dest_addr;      /* edge_node key */
  63   struct tc_edge_entry *edge_inv;      /* shortcut, used during SPF calculation */
  64   struct tc_entry *tc;                 /* backpointer to owning tc entry */
  65   olsr_linkcost cost;                  /* metric for tc received by this tc */
  66   olsr_linkcost common_cost;           /* common metric of both edges used for SPF calculation */
  67   unsigned int is_local:1;             /* 1 if this is a local edge */
  68   unsigned int is_virtual:1;           /* 1 if this is a virtual edge created by the neighbors TC ? */
  69   uint16_t ansn;                       /* ansn of this edge, used for multipart msgs */
  70 };
  71
  72 AVLNODE2STRUCT(edge_tree2tc_edge, struct tc_edge_entry, edge_node);
  73
  74 struct tc_entry {
  75   struct avl_node vertex_node;         /* node keyed by ip address */
  76   union olsr_ip_addr addr;             /* vertex_node key */
  77   struct avl_node cand_tree_node;      /* SPF candidate heap, node keyed by path_etx */
  78   olsr_linkcost path_cost;             /* SPF calculated distance, cand_tree_node key */
  79   struct list_node path_list_node;     /* SPF result list */
  80   struct avl_tree edge_tree;           /* subtree for edges */
  81   struct avl_tree prefix_tree;         /* subtree for prefixes */
  82   struct avl_tree mid_tree;            /* subtree for MID entries */
  83   struct avl_tree hna_tree;            /* subtree for HNA entries */
  84   struct timer_entry *mid_timer;       /* aging timer for MID advertisements */
  85   struct link_entry *next_hop;         /* SPF calculated link to the 1st hop neighbor */
  86   struct timer_entry *edge_gc_timer;   /* used for edge garbage collection */
  87   struct timer_entry *validity_timer;  /* tc validity time */
  88   uint32_t refcount;                   /* reference counter */
  89   bool is_virtual;                     /* true if tc is already timed out */
  90   int tc_seq;                          /* sequence number of the tc message */
  91   int mid_seq;                         /* sequence number of the mid message */
  92   int hna_seq;                         /* sequence number of the hna message */
  93   uint8_t msg_hops;                    /* hopcount as per the tc message */
  94   uint8_t hops;                        /* SPF calculated hopcount */
  95   uint16_t ansn;                       /* ANSN number of the tc message */
  96   uint16_t ignored;                    /* how many TC messages ignored in a sequence
  97                                           (kindof emergency brake) */
  98   uint16_t err_seq;                    /* sequence number of an unplausible TC */
  99   bool err_seq_valid;                  /* do we have an error (unplauible seq/ansn) */
 100 };
 101
 102 /*
 103  * Garbage collection time for edges.
 104  * This is used for multipart messages.
 105  */
 106 #define OLSR_TC_EDGE_GC_TIME (2*1000)   /* milliseconds */
 107 #define OLSR_TC_EDGE_GC_JITTER 5        /* percent */
 108
 109 #define OLSR_TC_VTIME_JITTER 5 /* percent */
 110
 111
 112 AVLNODE2STRUCT(vertex_tree2tc, struct tc_entry, vertex_node);
 113 AVLNODE2STRUCT(cand_tree2tc, struct tc_entry, cand_tree_node);
 114 LISTNODE2STRUCT(pathlist2tc, struct tc_entry, path_list_node);
 115
 116 /*
 117  * macros for traversing vertices, edges and prefixes in the link state database.
 118  * it is recommended to use this because it hides all the internal
 119  * datastructure from the callers.
 120  *
 121  * the loop prefetches the next node in order to not loose context if
 122  * for example the caller wants to delete the current entry.
 123  */
 124 #define OLSR_FOR_ALL_TC_ENTRIES(tc) \
 125 { \
 126   struct avl_node *tc_tree_node, *next_tc_tree_node; \
 127   for (tc_tree_node = avl_walk_first(&tc_tree); \
 128     tc_tree_node; tc_tree_node = next_tc_tree_node) { \
 129     next_tc_tree_node = avl_walk_next(tc_tree_node); \
 130     tc = vertex_tree2tc(tc_tree_node);
 131 #define OLSR_FOR_ALL_TC_ENTRIES_END(tc) }}
 132
 133 #define OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) \
 134 { \
 135   struct avl_node *tc_edge_node, *next_tc_edge_node; \
 136   for (tc_edge_node = avl_walk_first(&tc->edge_tree); \
 137     tc_edge_node; tc_edge_node = next_tc_edge_node) { \
 138     next_tc_edge_node = avl_walk_next(tc_edge_node); \
 139     tc_edge = edge_tree2tc_edge(tc_edge_node);
 140 #define OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge) }}
 141
 142 #define OLSR_FOR_ALL_PREFIX_ENTRIES(tc, rtp) \
 143 { \
 144   struct avl_node *rtp_node, *next_rtp_node; \
 145   for (rtp_node = avl_walk_first(&tc->prefix_tree); \
 146     rtp_node; rtp_node = next_rtp_node) { \
 147     next_rtp_node = avl_walk_next(rtp_node); \
 148     rtp = rtp_prefix_tree2rtp(rtp_node);
 149 #define OLSR_FOR_ALL_PREFIX_ENTRIES_END(tc, rtp) }}
 150
 151 extern struct avl_tree EXPORT(tc_tree);
 152 extern struct tc_entry *tc_myself;
 153 extern struct olsr_cookie_info *tc_mem_cookie;
 154 extern struct olsr_cookie_info *spf_backoff_timer_cookie;
 155
 156 void olsr_init_tc(void);
 157 void olsr_change_myself_tc(void);
 158 void olsr_print_tc_table(void);
 159 void olsr_time_out_tc_set(void);
 160
 161 /* tc msg input parser */
 162 void olsr_input_tc(union olsr_message *, struct interface *, union olsr_ip_addr *, enum duplicate_status);
 163
 164 /* tc_entry manipulation */
 165 struct tc_entry *EXPORT(olsr_lookup_tc_entry) (const union olsr_ip_addr *);
 166 struct tc_entry *olsr_locate_tc_entry(const union olsr_ip_addr *);
 167
 168 /*
 169  * Increment the reference counter.
 170  */
 171 static INLINE void
 172 olsr_lock_tc_entry(struct tc_entry *tc)
 173 {
 174   tc->refcount++;
 175 }
 176
 177 /*
 178  * Unlock and free a tc_entry once all references are gone.
 179  */
 180 static INLINE void
 181 olsr_unlock_tc_entry(struct tc_entry *tc)
 182 {
 183   if (--tc->refcount == 0) {    /* All references are gone. */
 184     olsr_cookie_free(tc_mem_cookie, tc);
 185   }
 186 }
 187
 188 /* tc_edge_entry manipulation */
 189 struct tc_edge_entry *EXPORT(olsr_lookup_tc_edge) (struct tc_entry *, union olsr_ip_addr *);
 190 struct tc_edge_entry *olsr_add_tc_edge_entry(struct tc_entry *, union olsr_ip_addr *, uint16_t);
 191 void olsr_delete_tc_entry(struct tc_entry *);
 192 void olsr_delete_tc_edge_entry(struct tc_edge_entry *);
 193 bool olsr_calc_tc_edge_entry_etx(struct tc_edge_entry *);
 194 void olsr_set_tc_edge_timer(struct tc_edge_entry *, unsigned int);
 195 void olsr_delete_all_tc_entries(void);
 196 uint32_t EXPORT(getRelevantTcCount) (void);
 197 void olsr_output_lq_tc(void *ifp);
 198 #endif
 199
 200 /*
 201  * Local Variables:
 202  * c-basic-offset: 2
 203  * indent-tabs-mode: nil
 204  * End:
 205  */