nest/neighbor.c

   1 /*
   2  *      BIRD -- Neighbor Cache
   3  *
   4  *      (c) 1998--2000 Martin Mares <mj@ucw.cz>
   5  *
   6  *      Can be freely distributed and used under the terms of the GNU GPL.
   7  */
   8
   9 #undef LOCAL_DEBUG
  10
  11 #include "nest/bird.h"
  12 #include "nest/iface.h"
  13 #include "nest/protocol.h"
  14 #include "lib/resource.h"
  15
  16 #define NEIGH_HASH_SIZE 256
  17
  18 static slab *neigh_slab;
  19 static list sticky_neigh_list, neigh_hash_table[NEIGH_HASH_SIZE];
  20
  21 static inline unsigned int
  22 neigh_hash(struct proto *p, ip_addr *a)
  23 {
  24   return (p->hash_key ^ ipa_hash(*a)) & (NEIGH_HASH_SIZE-1);
  25 }
  26
  27 static int
  28 if_connected(ip_addr *a, struct iface *i) /* -1=error, 1=match, 0=no match */
  29 {
  30   struct ifa *b;
  31
  32   if (!(i->flags & IF_UP))
  33     return -1;
  34   WALK_LIST(b, i->addrs)
  35     {
  36       if (ipa_equal(*a, b->ip))
  37         return SCOPE_HOST;
  38       if (b->flags & IA_UNNUMBERED)
  39         {
  40           if (ipa_equal(*a, b->opposite))
  41             return b->scope;
  42         }
  43       else
  44         {
  45           if (ipa_in_net(*a, b->prefix, b->pxlen))
  46             {
  47               if (ipa_equal(*a, b->prefix) ||   /* Network address */
  48                   ipa_equal(*a, b->brd))        /* Broadcast */
  49                 return -1;
  50               return b->scope;
  51             }
  52         }
  53       }
  54   return -1;
  55 }
  56
  57 neighbor *
  58 neigh_find(struct proto *p, ip_addr *a, unsigned flags)
  59 {
  60   neighbor *n;
  61   int class, scope = SCOPE_HOST;
  62   unsigned int h = neigh_hash(p, a);
  63   struct iface *i, *j;
  64
  65   WALK_LIST(n, neigh_hash_table[h])     /* Search the cache */
  66     if (n->proto == p && ipa_equal(*a, n->addr))
  67       return n;
  68
  69   class = ipa_classify(*a);
  70   if (class < 0)                        /* Invalid address */
  71     return NULL;
  72   if ((class & IADDR_SCOPE_MASK) < SCOPE_SITE ||
  73       !(class & IADDR_HOST))
  74     return NULL;                        /* Bad scope or a somecast */
  75
  76   j = NULL;
  77   WALK_LIST(i, iface_list)
  78     if ((scope = if_connected(a, i)) >= 0)
  79       {
  80         j = i;
  81         break;
  82       }
  83   if (!j && !(flags & NEF_STICKY))
  84     return NULL;
  85
  86   n = sl_alloc(neigh_slab);
  87   n->addr = *a;
  88   n->iface = j;
  89   if (j)
  90     {
  91       add_tail(&neigh_hash_table[h], &n->n);
  92       add_tail(&j->neighbors, &n->if_n);
  93     }
  94   else
  95     {
  96       add_tail(&sticky_neigh_list, &n->n);
  97       scope = 0;
  98     }
  99   n->proto = p;
 100   n->data = NULL;
 101   n->aux = 0;
 102   n->flags = flags;
 103   n->scope = scope;
 104   return n;
 105 }
 106
 107 void
 108 neigh_dump(neighbor *n)
 109 {
 110   debug("%p %I ", n, n->addr);
 111   if (n->iface)
 112     debug("%s ", n->iface->name);
 113   else
 114     debug("[] ");
 115   debug("%s %p %08x scope %s", n->proto->name, n->data, n->aux, ip_scope_text(n->scope));
 116   if (n->flags & NEF_STICKY)
 117     debug(" STICKY");
 118   debug("\n");
 119 }
 120
 121 void
 122 neigh_dump_all(void)
 123 {
 124   neighbor *n;
 125   int i;
 126
 127   debug("Known neighbors:\n");
 128   WALK_LIST(n, sticky_neigh_list)
 129     neigh_dump(n);
 130   for(i=0; i<NEIGH_HASH_SIZE; i++)
 131     WALK_LIST(n, neigh_hash_table[i])
 132       neigh_dump(n);
 133   debug("\n");
 134 }
 135
 136 void
 137 neigh_if_up(struct iface *i)
 138 {
 139   neighbor *n, *next;
 140   int scope;
 141
 142   WALK_LIST_DELSAFE(n, next, sticky_neigh_list)
 143     if ((scope = if_connected(&n->addr, i)) >= 0)
 144       {
 145         n->iface = i;
 146         n->scope = scope;
 147         add_tail(&i->neighbors, &n->if_n);
 148         rem_node(&n->n);
 149         add_tail(&neigh_hash_table[neigh_hash(n->proto, &n->addr)], &n->n);
 150         DBG("Waking up sticky neighbor %I\n", n->addr);
 151         if (n->proto->neigh_notify && n->proto->core_state != FS_FLUSHING)
 152           n->proto->neigh_notify(n);
 153       }
 154 }
 155
 156 void
 157 neigh_if_down(struct iface *i)
 158 {
 159   node *x, *y;
 160
 161   WALK_LIST_DELSAFE(x, y, i->neighbors)
 162     {
 163       neighbor *n = SKIP_BACK(neighbor, if_n, x);
 164       DBG("Flushing neighbor %I on %s\n", n->addr, i->name);
 165       rem_node(&n->if_n);
 166       n->iface = NULL;
 167       if (n->proto->neigh_notify && n->proto->core_state != FS_FLUSHING)
 168         n->proto->neigh_notify(n);
 169       rem_node(&n->n);
 170       if (n->flags & NEF_STICKY)
 171         add_tail(&sticky_neigh_list, &n->n);
 172       else
 173         sl_free(neigh_slab, n);
 174     }
 175 }
 176
 177 static inline void
 178 neigh_prune_one(neighbor *n)
 179 {
 180   if (n->proto->core_state != FS_FLUSHING)
 181     return;
 182   rem_node(&n->n);
 183   if (n->iface)
 184     rem_node(&n->if_n);
 185   sl_free(neigh_slab, n);
 186 }
 187
 188 void
 189 neigh_prune(void)
 190 {
 191   neighbor *n;
 192   node *m;
 193   int i;
 194
 195   DBG("Pruning neighbors\n");
 196   for(i=0; i<NEIGH_HASH_SIZE; i++)
 197     WALK_LIST_DELSAFE(n, m, neigh_hash_table[i])
 198       neigh_prune_one(n);
 199   WALK_LIST_DELSAFE(n, m, sticky_neigh_list)
 200     neigh_prune_one(n);
 201 }
 202
 203 void
 204 neigh_init(pool *if_pool)
 205 {
 206   int i;
 207
 208   neigh_slab = sl_new(if_pool, sizeof(neighbor));
 209   init_list(&sticky_neigh_list);
 210   for(i=0; i<NEIGH_HASH_SIZE; i++)
 211     init_list(&neigh_hash_table[i]);
 212 }