drivers/staging/batman-adv/routing.c

   1 /*
   2  * Copyright (C) 2007-2009 B.A.T.M.A.N. contributors:
   3  *
   4  * Marek Lindner, Simon Wunderlich
   5  *
   6  * This program is free software; you can redistribute it and/or
   7  * modify it under the terms of version 2 of the GNU General Public
   8  * License as published by the Free Software Foundation.
   9  *
  10  * This program is distributed in the hope that it will be useful, but
  11  * WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  13  * General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software
  17  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  18  * 02110-1301, USA
  19  *
  20  */
  21
  22
  23
  24
  25
  26 #include "main.h"
  27 #include "routing.h"
  28 #include "send.h"
  29 #include "soft-interface.h"
  30 #include "hard-interface.h"
  31 #include "device.h"
  32 #include "translation-table.h"
  33 #include "types.h"
  34 #include "hash.h"
  35 #include "ring_buffer.h"
  36 #include "vis.h"
  37 #include "aggregation.h"
  38 #include "compat.h"
  39
  40
  41
  42 DECLARE_WAIT_QUEUE_HEAD(thread_wait);
  43 static DECLARE_DELAYED_WORK(purge_orig_wq, purge_orig);
  44
  45 static atomic_t data_ready_cond;
  46 atomic_t exit_cond;
  47
  48 static void start_purge_timer(void)
  49 {
  50         queue_delayed_work(bat_event_workqueue, &purge_orig_wq, 1 * HZ);
  51 }
  52
  53 int originator_init(void)
  54 {
  55         if (orig_hash)
  56                 return 1;
  57
  58         spin_lock(&orig_hash_lock);
  59         orig_hash = hash_new(128, compare_orig, choose_orig);
  60
  61         if (!orig_hash)
  62                 goto err;
  63
  64         spin_unlock(&orig_hash_lock);
  65         start_purge_timer();
  66         return 1;
  67
  68 err:
  69         spin_unlock(&orig_hash_lock);
  70         return 0;
  71 }
  72
  73 void originator_free(void)
  74 {
  75         if (!orig_hash)
  76                 return;
  77
  78         cancel_delayed_work_sync(&purge_orig_wq);
  79
  80         spin_lock(&orig_hash_lock);
  81         hash_delete(orig_hash, free_orig_node);
  82         orig_hash = NULL;
  83         spin_unlock(&orig_hash_lock);
  84 }
  85
  86 static struct neigh_node *create_neighbor(struct orig_node *orig_node, struct orig_node *orig_neigh_node, uint8_t *neigh, struct batman_if *if_incoming)
  87 {
  88         struct neigh_node *neigh_node;
  89
  90         bat_dbg(DBG_BATMAN, "Creating new last-hop neighbour of originator\n");
  91
  92         neigh_node = kmalloc(sizeof(struct neigh_node), GFP_ATOMIC);
  93         memset(neigh_node, 0, sizeof(struct neigh_node));
  94         INIT_LIST_HEAD(&neigh_node->list);
  95
  96         memcpy(neigh_node->addr, neigh, ETH_ALEN);
  97         neigh_node->orig_node = orig_neigh_node;
  98         neigh_node->if_incoming = if_incoming;
  99
 100         list_add_tail(&neigh_node->list, &orig_node->neigh_list);
 101         return neigh_node;
 102 }
 103
 104 void free_orig_node(void *data)
 105 {
 106         struct list_head *list_pos, *list_pos_tmp;
 107         struct neigh_node *neigh_node;
 108         struct orig_node *orig_node = (struct orig_node *)data;
 109
 110         /* for all neighbours towards this originator ... */
 111         list_for_each_safe(list_pos, list_pos_tmp, &orig_node->neigh_list) {
 112                 neigh_node = list_entry(list_pos, struct neigh_node, list);
 113
 114                 list_del(list_pos);
 115                 kfree(neigh_node);
 116         }
 117
 118         hna_global_del_orig(orig_node, "originator timed out");
 119
 120         kfree(orig_node->bcast_own);
 121         kfree(orig_node->bcast_own_sum);
 122         kfree(orig_node);
 123 }
 124
 125 /* this function finds or creates an originator entry for the given address if it does not exits */
 126 static struct orig_node *get_orig_node(uint8_t *addr)
 127 {
 128         struct orig_node *orig_node;
 129         struct hashtable_t *swaphash;
 130         char orig_str[ETH_STR_LEN];
 131
 132         orig_node = ((struct orig_node *)hash_find(orig_hash, addr));
 133
 134         if (orig_node != NULL)
 135                 return orig_node;
 136
 137         addr_to_string(orig_str, addr);
 138         bat_dbg(DBG_BATMAN, "Creating new originator: %s \n", orig_str);
 139
 140         orig_node = kmalloc(sizeof(struct orig_node), GFP_ATOMIC);
 141         memset(orig_node, 0, sizeof(struct orig_node));
 142         INIT_LIST_HEAD(&orig_node->neigh_list);
 143
 144         memcpy(orig_node->orig, addr, ETH_ALEN);
 145         orig_node->router = NULL;
 146         orig_node->batman_if = NULL;
 147         orig_node->hna_buff = NULL;
 148
 149         orig_node->bcast_own = kmalloc(num_ifs * sizeof(TYPE_OF_WORD) * NUM_WORDS, GFP_ATOMIC);
 150         memset(orig_node->bcast_own, 0, num_ifs * sizeof(TYPE_OF_WORD) * NUM_WORDS);
 151
 152         orig_node->bcast_own_sum = kmalloc(num_ifs * sizeof(uint8_t), GFP_ATOMIC);
 153         memset(orig_node->bcast_own_sum, 0, num_ifs * sizeof(uint8_t));
 154
 155         hash_add(orig_hash, orig_node);
 156
 157         if (orig_hash->elements * 4 > orig_hash->size) {
 158                 swaphash = hash_resize(orig_hash, orig_hash->size * 2);
 159
 160                 if (swaphash == NULL)
 161                         printk(KERN_ERR "batman-adv:Couldn't resize orig hash table \n");
 162                 else
 163                         orig_hash = swaphash;
 164         }
 165
 166         return orig_node;
 167 }
 168
 169 void slide_own_bcast_window(struct batman_if *batman_if)
 170 {
 171         struct hash_it_t *hashit = NULL;
 172         struct orig_node *orig_node;
 173
 174         spin_lock(&orig_hash_lock);
 175
 176         while (NULL != (hashit = hash_iterate(orig_hash, hashit))) {
 177                 orig_node = hashit->bucket->data;
 178
 179                 bit_get_packet((TYPE_OF_WORD *)&(orig_node->bcast_own[batman_if->if_num * NUM_WORDS]), 1, 0);
 180                 orig_node->bcast_own_sum[batman_if->if_num] = bit_packet_count((TYPE_OF_WORD *)&(orig_node->bcast_own[batman_if->if_num * NUM_WORDS]));
 181         }
 182
 183         spin_unlock(&orig_hash_lock);
 184 }
 185
 186 static void update_routes(struct orig_node *orig_node, struct neigh_node *neigh_node, unsigned char *hna_buff, int hna_buff_len)
 187 {
 188         char orig_str[ETH_STR_LEN], neigh_str[ETH_STR_LEN], router_str[ETH_STR_LEN];
 189
 190         if (orig_node == NULL)
 191                 return;
 192
 193         if (orig_node->router != neigh_node) {
 194                 addr_to_string(orig_str, orig_node->orig);
 195
 196                 /* route deleted */
 197                 if ((orig_node->router != NULL) && (neigh_node == NULL)) {
 198                         bat_dbg(DBG_ROUTES, "Deleting route towards: %s\n",
 199                                 orig_str);
 200                         hna_global_del_orig(orig_node, "originator timed out");
 201
 202                 /* route added */
 203                 } else if ((orig_node->router == NULL) && (neigh_node != NULL)) {
 204
 205                         addr_to_string(neigh_str, neigh_node->addr);
 206                         bat_dbg(DBG_ROUTES, "Adding route towards: %s (via %s)\n", orig_str, neigh_str);
 207                         hna_global_add_orig(orig_node, hna_buff, hna_buff_len);
 208
 209                 /* route changed */
 210                 } else {
 211
 212                         addr_to_string(neigh_str, neigh_node->addr);
 213                         addr_to_string(router_str, orig_node->router->addr);
 214                         bat_dbg(DBG_ROUTES, "Changing route towards: %s (now via %s - was via %s)\n", orig_str, neigh_str, router_str);
 215
 216                 }
 217
 218                 if (neigh_node != NULL)
 219                         orig_node->batman_if = neigh_node->if_incoming;
 220                 else
 221                         orig_node->batman_if = NULL;
 222
 223                 orig_node->router = neigh_node;
 224
 225         /* may be just HNA changed */
 226         } else {
 227
 228                 if ((hna_buff_len != orig_node->hna_buff_len) || ((hna_buff_len > 0) && (orig_node->hna_buff_len > 0) && (memcmp(orig_node->hna_buff, hna_buff, hna_buff_len) != 0))) {
 229
 230                         if (orig_node->hna_buff_len > 0)
 231                                 hna_global_del_orig(orig_node, "originator changed hna");
 232
 233                         if ((hna_buff_len > 0) && (hna_buff != NULL))
 234                                 hna_global_add_orig(orig_node, hna_buff, hna_buff_len);
 235
 236                 }
 237
 238         }
 239 }
 240
 241 static int isBidirectionalNeigh(struct orig_node *orig_node, struct orig_node *orig_neigh_node, struct batman_packet *batman_packet, struct batman_if *if_incoming)
 242 {
 243         struct neigh_node *neigh_node = NULL, *tmp_neigh_node = NULL;
 244         char orig_str[ETH_STR_LEN], neigh_str[ETH_STR_LEN];
 245         unsigned char total_count;
 246
 247         addr_to_string(orig_str, orig_node->orig);
 248         addr_to_string(neigh_str, orig_neigh_node->orig);
 249
 250         if (orig_node == orig_neigh_node) {
 251                 list_for_each_entry(tmp_neigh_node, &orig_node->neigh_list, list) {
 252
 253                         if (compare_orig(tmp_neigh_node->addr, orig_neigh_node->orig) && (tmp_neigh_node->if_incoming == if_incoming))
 254                                 neigh_node = tmp_neigh_node;
 255                 }
 256
 257                 if (neigh_node == NULL)
 258                         neigh_node = create_neighbor(orig_node, orig_neigh_node, orig_neigh_node->orig, if_incoming);
 259
 260                 neigh_node->last_valid = jiffies;
 261         } else {
 262                 /* find packet count of corresponding one hop neighbor */
 263                 list_for_each_entry(tmp_neigh_node, &orig_neigh_node->neigh_list, list) {
 264
 265                         if (compare_orig(tmp_neigh_node->addr, orig_neigh_node->orig) && (tmp_neigh_node->if_incoming == if_incoming))
 266                                 neigh_node = tmp_neigh_node;
 267                 }
 268
 269                 if (neigh_node == NULL)
 270                         neigh_node = create_neighbor(orig_neigh_node, orig_neigh_node, orig_neigh_node->orig, if_incoming);
 271         }
 272
 273         orig_node->last_valid = jiffies;
 274
 275         /* pay attention to not get a value bigger than 100 % */
 276         total_count = (orig_neigh_node->bcast_own_sum[if_incoming->if_num] > neigh_node->real_packet_count ? neigh_node->real_packet_count : orig_neigh_node->bcast_own_sum[if_incoming->if_num]);
 277
 278         /* if we have too few packets (too less data) we set tq_own to zero */
 279         /* if we receive too few packets it is not considered bidirectional */
 280         if ((total_count < TQ_LOCAL_BIDRECT_SEND_MINIMUM) || (neigh_node->real_packet_count < TQ_LOCAL_BIDRECT_RECV_MINIMUM))
 281                 orig_neigh_node->tq_own = 0;
 282         else
 283                 /* neigh_node->real_packet_count is never zero as we only purge old information when getting new information */
 284                 orig_neigh_node->tq_own = (TQ_MAX_VALUE * total_count) / neigh_node->real_packet_count;
 285
 286         /*
 287          * 1 - ((1-x) ** 3), normalized to TQ_MAX_VALUE
 288          * this does affect the nearly-symmetric links only a little,
 289          * but punishes asymmetric links more.
 290          * this will give a value between 0 and TQ_MAX_VALUE
 291          */
 292         orig_neigh_node->tq_asym_penalty = TQ_MAX_VALUE - (TQ_MAX_VALUE *
 293                         (TQ_LOCAL_WINDOW_SIZE - neigh_node->real_packet_count) *
 294                         (TQ_LOCAL_WINDOW_SIZE - neigh_node->real_packet_count) *
 295                         (TQ_LOCAL_WINDOW_SIZE - neigh_node->real_packet_count)) /
 296                         (TQ_LOCAL_WINDOW_SIZE * TQ_LOCAL_WINDOW_SIZE * TQ_LOCAL_WINDOW_SIZE);
 297
 298         batman_packet->tq = ((batman_packet->tq * orig_neigh_node->tq_own * orig_neigh_node->tq_asym_penalty) / (TQ_MAX_VALUE *  TQ_MAX_VALUE));
 299
 300         bat_dbg(DBG_BATMAN, "bidirectional: orig = %-15s neigh = %-15s => own_bcast = %2i, real recv = %2i, local tq: %3i, asym_penalty: %3i, total tq: %3i \n",
 301                   orig_str, neigh_str, total_count, neigh_node->real_packet_count, orig_neigh_node->tq_own, orig_neigh_node->tq_asym_penalty, batman_packet->tq);
 302
 303         /* if link has the minimum required transmission quality consider it bidirectional */
 304         if (batman_packet->tq >= TQ_TOTAL_BIDRECT_LIMIT)
 305                 return 1;
 306
 307         return 0;
 308 }
 309
 310 static void update_orig(struct orig_node *orig_node, struct ethhdr *ethhdr, struct batman_packet *batman_packet, struct batman_if *if_incoming, unsigned char *hna_buff, int hna_buff_len, char is_duplicate)
 311 {
 312         struct neigh_node *neigh_node = NULL, *tmp_neigh_node = NULL;
 313         int tmp_hna_buff_len;
 314
 315         bat_dbg(DBG_BATMAN, "update_originator(): Searching and updating originator entry of received packet \n");
 316
 317         list_for_each_entry(tmp_neigh_node, &orig_node->neigh_list, list) {
 318                 if (compare_orig(tmp_neigh_node->addr, ethhdr->h_source) && (tmp_neigh_node->if_incoming == if_incoming)) {
 319                         neigh_node = tmp_neigh_node;
 320                         continue;
 321                 }
 322
 323                 if (is_duplicate)
 324                         continue;
 325
 326                 ring_buffer_set(tmp_neigh_node->tq_recv, &tmp_neigh_node->tq_index, 0);
 327                 tmp_neigh_node->tq_avg = ring_buffer_avg(tmp_neigh_node->tq_recv);
 328         }
 329
 330         if (neigh_node == NULL)
 331                 neigh_node = create_neighbor(orig_node, get_orig_node(ethhdr->h_source), ethhdr->h_source, if_incoming);
 332         else
 333                 bat_dbg(DBG_BATMAN, "Updating existing last-hop neighbour of originator\n");
 334
 335         orig_node->flags = batman_packet->flags;
 336         neigh_node->last_valid = jiffies;
 337
 338         ring_buffer_set(neigh_node->tq_recv, &neigh_node->tq_index, batman_packet->tq);
 339         neigh_node->tq_avg = ring_buffer_avg(neigh_node->tq_recv);
 340
 341         if (!is_duplicate) {
 342                 orig_node->last_ttl = batman_packet->ttl;
 343                 neigh_node->last_ttl = batman_packet->ttl;
 344         }
 345
 346         tmp_hna_buff_len = (hna_buff_len > batman_packet->num_hna * ETH_ALEN ? batman_packet->num_hna * ETH_ALEN : hna_buff_len);
 347
 348         /* if this neighbor already is our next hop there is nothing to change */
 349         if (orig_node->router == neigh_node)
 350                 goto update_hna;
 351
 352         /* if this neighbor does not offer a better TQ we won't consider it */
 353         if ((orig_node->router) &&
 354             (orig_node->router->tq_avg > neigh_node->tq_avg))
 355                 goto update_hna;
 356
 357         /* if the TQ is the same and the link not more symetric we won't consider it either */
 358         if ((orig_node->router) &&
 359              ((neigh_node->tq_avg == orig_node->router->tq_avg) &&
 360              (orig_node->router->orig_node->bcast_own_sum[if_incoming->if_num] >=
 361               neigh_node->orig_node->bcast_own_sum[if_incoming->if_num])))
 362                 goto update_hna;
 363
 364         update_routes(orig_node, neigh_node, hna_buff, tmp_hna_buff_len);
 365         return;
 366
 367 update_hna:
 368         update_routes(orig_node, orig_node->router, hna_buff, tmp_hna_buff_len);
 369         return;
 370 }
 371
 372 static char count_real_packets(struct ethhdr *ethhdr, struct batman_packet *batman_packet, struct batman_if *if_incoming)
 373 {
 374         struct orig_node *orig_node;
 375         struct neigh_node *tmp_neigh_node;
 376         char is_duplicate = 0;
 377
 378
 379         orig_node = get_orig_node(batman_packet->orig);
 380         if (orig_node == NULL)
 381                 return 0;
 382
 383
 384         list_for_each_entry(tmp_neigh_node, &orig_node->neigh_list, list) {
 385
 386                 if (!is_duplicate)
 387                         is_duplicate = get_bit_status(tmp_neigh_node->real_bits, orig_node->last_real_seqno, batman_packet->seqno);
 388
 389                 if (compare_orig(tmp_neigh_node->addr, ethhdr->h_source) && (tmp_neigh_node->if_incoming == if_incoming))
 390                         bit_get_packet(tmp_neigh_node->real_bits, batman_packet->seqno - orig_node->last_real_seqno, 1);
 391                 else
 392                         bit_get_packet(tmp_neigh_node->real_bits, batman_packet->seqno - orig_node->last_real_seqno, 0);
 393
 394                 tmp_neigh_node->real_packet_count = bit_packet_count(tmp_neigh_node->real_bits);
 395         }
 396
 397         if (!is_duplicate) {
 398                 bat_dbg(DBG_BATMAN, "updating last_seqno: old %d, new %d \n",
 399                         orig_node->last_real_seqno, batman_packet->seqno);
 400                 orig_node->last_real_seqno = batman_packet->seqno;
 401         }
 402
 403         return is_duplicate;
 404 }
 405
 406 void receive_bat_packet(struct ethhdr *ethhdr, struct batman_packet *batman_packet, unsigned char *hna_buff, int hna_buff_len, struct batman_if *if_incoming)
 407 {
 408         struct batman_if *batman_if;
 409         struct orig_node *orig_neigh_node, *orig_node;
 410         char orig_str[ETH_STR_LEN], prev_sender_str[ETH_STR_LEN], neigh_str[ETH_STR_LEN];
 411         char has_directlink_flag;
 412         char is_my_addr = 0, is_my_orig = 0, is_my_oldorig = 0, is_broadcast = 0, is_bidirectional, is_single_hop_neigh, is_duplicate;
 413         unsigned short if_incoming_seqno;
 414
 415         /* Silently drop when the batman packet is actually not a correct packet.
 416          *
 417          * This might happen if a packet is padded (e.g. Ethernet has a
 418          * minimum frame length of 64 byte) and the aggregation interprets
 419          * it as an additional length.
 420          *
 421          * TODO: A more sane solution would be to have a bit in the batman_packet
 422          * to detect whether the packet is the last packet in an aggregation.
 423          * Here we expect that the padding is always zero (or not 0x01)
 424          */
 425         if (batman_packet->packet_type != BAT_PACKET)
 426                 return;
 427
 428         /* could be changed by schedule_own_packet() */
 429         if_incoming_seqno = atomic_read(&if_incoming->seqno);
 430
 431         addr_to_string(orig_str, batman_packet->orig);
 432         addr_to_string(prev_sender_str, batman_packet->prev_sender);
 433         addr_to_string(neigh_str, ethhdr->h_source);
 434
 435         has_directlink_flag = (batman_packet->flags & DIRECTLINK ? 1 : 0);
 436
 437         is_single_hop_neigh = (compare_orig(ethhdr->h_source, batman_packet->orig) ? 1 : 0);
 438
 439         bat_dbg(DBG_BATMAN, "Received BATMAN packet via NB: %s, IF: %s [%s] (from OG: %s, via prev OG: %s, seqno %d, tq %d, TTL %d, V %d, IDF %d) \n", neigh_str, if_incoming->dev, if_incoming->addr_str, orig_str, prev_sender_str, batman_packet->seqno, batman_packet->tq, batman_packet->ttl, batman_packet->version, has_directlink_flag);
 440
 441         list_for_each_entry_rcu(batman_if, &if_list, list) {
 442                 if (batman_if->if_active != IF_ACTIVE)
 443                         continue;
 444
 445                 if (compare_orig(ethhdr->h_source, batman_if->net_dev->dev_addr))
 446                         is_my_addr = 1;
 447
 448                 if (compare_orig(batman_packet->orig, batman_if->net_dev->dev_addr))
 449                         is_my_orig = 1;
 450
 451                 if (compare_orig(batman_packet->prev_sender, batman_if->net_dev->dev_addr))
 452                         is_my_oldorig = 1;
 453
 454                 if (compare_orig(ethhdr->h_source, broadcastAddr))
 455                         is_broadcast = 1;
 456         }
 457
 458         if (batman_packet->version != COMPAT_VERSION) {
 459                 bat_dbg(DBG_BATMAN, "Drop packet: incompatible batman version (%i) \n", batman_packet->version);
 460                 return;
 461         }
 462
 463         if (is_my_addr) {
 464                 bat_dbg(DBG_BATMAN, "Drop packet: received my own broadcast (sender: %s) \n", neigh_str);
 465                 return;
 466         }
 467
 468         if (is_broadcast) {
 469                 bat_dbg(DBG_BATMAN, "Drop packet: ignoring all packets with broadcast source addr (sender: %s) \n", neigh_str);
 470                 return;
 471         }
 472
 473         if (is_my_orig) {
 474                 orig_neigh_node = get_orig_node(ethhdr->h_source);
 475
 476                 /* neighbour has to indicate direct link and it has to come via the corresponding interface */
 477                 /* if received seqno equals last send seqno save new seqno for bidirectional check */
 478                 if (has_directlink_flag && compare_orig(if_incoming->net_dev->dev_addr, batman_packet->orig) &&
 479                                   (batman_packet->seqno - if_incoming_seqno + 2 == 0)) {
 480                         bit_mark((TYPE_OF_WORD *)&(orig_neigh_node->bcast_own[if_incoming->if_num * NUM_WORDS]), 0);
 481                         orig_neigh_node->bcast_own_sum[if_incoming->if_num] = bit_packet_count((TYPE_OF_WORD *)&(orig_neigh_node->bcast_own[if_incoming->if_num * NUM_WORDS]));
 482                 }
 483
 484                 bat_dbg(DBG_BATMAN, "Drop packet: originator packet from myself (via neighbour) \n");
 485                 return;
 486         }
 487
 488         if (batman_packet->tq == 0) {
 489                 count_real_packets(ethhdr, batman_packet, if_incoming);
 490
 491                 bat_dbg(DBG_BATMAN, "Drop packet: originator packet with tq equal 0 \n");
 492                 return;
 493         }
 494
 495         if (is_my_oldorig) {
 496                 bat_dbg(DBG_BATMAN, "Drop packet: ignoring all rebroadcast echos (sender: %s) \n", neigh_str);
 497                 return;
 498         }
 499
 500         is_duplicate = count_real_packets(ethhdr, batman_packet, if_incoming);
 501
 502         orig_node = get_orig_node(batman_packet->orig);
 503         if (orig_node == NULL)
 504                 return;
 505
 506         /* avoid temporary routing loops */
 507         if ((orig_node->router) && (orig_node->router->orig_node->router) &&
 508             (compare_orig(orig_node->router->addr, batman_packet->prev_sender)) &&
 509             !(compare_orig(batman_packet->orig, batman_packet->prev_sender)) &&
 510             (compare_orig(orig_node->router->addr, orig_node->router->orig_node->router->addr))) {
 511                 bat_dbg(DBG_BATMAN, "Drop packet: ignoring all rebroadcast packets that may make me loop (sender: %s) \n", neigh_str);
 512                 return;
 513         }
 514
 515         /* if sender is a direct neighbor the sender mac equals originator mac */
 516         orig_neigh_node = (is_single_hop_neigh ? orig_node : get_orig_node(ethhdr->h_source));
 517         if (orig_neigh_node == NULL)
 518                 return;
 519
 520         /* drop packet if sender is not a direct neighbor and if we don't route towards it */
 521         if (!is_single_hop_neigh && (orig_neigh_node->router == NULL)) {
 522                 bat_dbg(DBG_BATMAN, "Drop packet: OGM via unknown neighbor!\n");
 523                 return;
 524         }
 525
 526         is_bidirectional = isBidirectionalNeigh(orig_node, orig_neigh_node, batman_packet, if_incoming);
 527
 528         /* update ranking if it is not a duplicate or has the same seqno and similar ttl as the non-duplicate */
 529         if (is_bidirectional && (!is_duplicate ||
 530                 ((orig_node->last_real_seqno == batman_packet->seqno) &&
 531                         (orig_node->last_ttl - 3 <= batman_packet->ttl))))
 532                 update_orig(orig_node, ethhdr, batman_packet, if_incoming, hna_buff, hna_buff_len, is_duplicate);
 533
 534         /* is single hop (direct) neighbour */
 535         if (is_single_hop_neigh) {
 536
 537                 /* mark direct link on incoming interface */
 538                 schedule_forward_packet(orig_node, ethhdr, batman_packet, 1, hna_buff_len, if_incoming);
 539
 540                 bat_dbg(DBG_BATMAN, "Forwarding packet: rebroadcast neighbour packet with direct link flag\n");
 541                 return;
 542         }
 543
 544         /* multihop originator */
 545         if (!is_bidirectional) {
 546                 bat_dbg(DBG_BATMAN, "Drop packet: not received via bidirectional link\n");
 547                 return;
 548         }
 549
 550         if (is_duplicate) {
 551                 bat_dbg(DBG_BATMAN, "Drop packet: duplicate packet received\n");
 552                 return;
 553         }
 554
 555         bat_dbg(DBG_BATMAN, "Forwarding packet: rebroadcast originator packet\n");
 556         schedule_forward_packet(orig_node, ethhdr, batman_packet, 0, hna_buff_len, if_incoming);
 557 }
 558
 559 void purge_orig(struct work_struct *work)
 560 {
 561         struct list_head *list_pos, *list_pos_tmp;
 562         struct hash_it_t *hashit = NULL;
 563         struct orig_node *orig_node;
 564         struct neigh_node *neigh_node, *best_neigh_node;
 565         char orig_str[ETH_STR_LEN], neigh_str[ETH_STR_LEN], neigh_purged;
 566
 567         spin_lock(&orig_hash_lock);
 568
 569         /* for all origins... */
 570         while (NULL != (hashit = hash_iterate(orig_hash, hashit))) {
 571
 572                 orig_node = hashit->bucket->data;
 573                 addr_to_string(orig_str, orig_node->orig);
 574
 575                 if (time_after(jiffies, orig_node->last_valid + ((2 * PURGE_TIMEOUT * HZ) / 1000))) {
 576
 577                         bat_dbg(DBG_BATMAN, "Originator timeout: originator %s, last_valid %lu\n", orig_str, (orig_node->last_valid / HZ));
 578
 579                         hash_remove_bucket(orig_hash, hashit);
 580                         free_orig_node(orig_node);
 581
 582                 } else {
 583
 584                         best_neigh_node = NULL;
 585                         neigh_purged = 0;
 586
 587                         /* for all neighbours towards this originator ... */
 588                         list_for_each_safe(list_pos, list_pos_tmp, &orig_node->neigh_list) {
 589                                 neigh_node = list_entry(list_pos, struct neigh_node, list);
 590
 591                                 if (time_after(jiffies, neigh_node->last_valid + ((PURGE_TIMEOUT * HZ) / 1000))) {
 592
 593                                         addr_to_string(neigh_str, neigh_node->addr);
 594                                         bat_dbg(DBG_BATMAN, "Neighbour timeout: originator %s, neighbour: %s, last_valid %lu\n", orig_str, neigh_str, (neigh_node->last_valid / HZ));
 595
 596                                         neigh_purged = 1;
 597                                         list_del(list_pos);
 598                                         kfree(neigh_node);
 599
 600                                 } else {
 601
 602                                         if ((best_neigh_node == NULL) || (neigh_node->tq_avg > best_neigh_node->tq_avg))
 603                                                 best_neigh_node = neigh_node;
 604
 605                                 }
 606
 607                         }
 608
 609                         if (neigh_purged)
 610                                 update_routes(orig_node, best_neigh_node, orig_node->hna_buff, orig_node->hna_buff_len);
 611
 612                 }
 613
 614         }
 615
 616         spin_unlock(&orig_hash_lock);
 617
 618         start_purge_timer();
 619 }
 620
 621 static int receive_raw_packet(struct socket *raw_sock, unsigned char *packet_buff, int packet_buff_len)
 622 {
 623         struct kvec iov;
 624         struct msghdr msg;
 625
 626         iov.iov_base = packet_buff;
 627         iov.iov_len = packet_buff_len;
 628
 629         msg.msg_flags = MSG_DONTWAIT;   /* non-blocking */
 630         msg.msg_name = NULL;
 631         msg.msg_namelen = 0;
 632         msg.msg_control = NULL;
 633
 634         return kernel_recvmsg(raw_sock, &msg, &iov, 1, packet_buff_len, MSG_DONTWAIT);
 635 }
 636
 637 int packet_recv_thread(void *data)
 638 {
 639         struct batman_if *batman_if;
 640         struct ethhdr *ethhdr;
 641         struct batman_packet *batman_packet;
 642         struct unicast_packet *unicast_packet;
 643         struct bcast_packet *bcast_packet;
 644         struct icmp_packet *icmp_packet;
 645         struct vis_packet *vis_packet;
 646         struct orig_node *orig_node;
 647         unsigned char *packet_buff, src_str[ETH_STR_LEN], dst_str[ETH_STR_LEN];
 648         int vis_info_len;
 649         int result;
 650
 651         atomic_set(&data_ready_cond, 0);
 652         atomic_set(&exit_cond, 0);
 653         packet_buff = kmalloc(PACKBUFF_SIZE, GFP_KERNEL);
 654         if (!packet_buff) {
 655                 printk(KERN_ERR "batman-adv:Could allocate memory for the packet buffer. :(\n");
 656                 return -1;
 657         }
 658
 659         while ((!kthread_should_stop()) && (!atomic_read(&exit_cond))) {
 660
 661                 wait_event_interruptible(thread_wait, (atomic_read(&data_ready_cond) || atomic_read(&exit_cond)));
 662
 663                 atomic_set(&data_ready_cond, 0);
 664
 665                 if (kthread_should_stop() || atomic_read(&exit_cond))
 666                         break;
 667
 668                 /* we only want to safely traverse the list, hard-interfaces
 669                  * won't be deleted anyway as long as this thread runs. */
 670
 671                 rcu_read_lock();
 672                 list_for_each_entry_rcu(batman_if, &if_list, list) {
 673                         rcu_read_unlock();
 674
 675                         result = -1;
 676
 677                         while (1) {
 678                                 if (batman_if->if_active != IF_ACTIVE) {
 679                                         if (batman_if->if_active != IF_TO_BE_ACTIVATED)
 680                                                 printk(KERN_WARNING
 681                                                        "batman-adv:Could not read from deactivated interface %s!\n",
 682                                                        batman_if->dev);
 683
 684                                         if (batman_if->raw_sock)
 685                                                 receive_raw_packet(batman_if->raw_sock, packet_buff, PACKBUFF_SIZE);
 686                                         result = 0;
 687                                         break;
 688                                 }
 689
 690                                 result = receive_raw_packet(batman_if->raw_sock, packet_buff, PACKBUFF_SIZE);
 691                                 if (result <= 0)
 692                                         break;
 693
 694                                 if (result < sizeof(struct ethhdr) + 2)
 695                                         continue;
 696
 697                                 ethhdr = (struct ethhdr *)packet_buff;
 698                                 batman_packet = (struct batman_packet *)(packet_buff + sizeof(struct ethhdr));
 699
 700                                 if (batman_packet->version != COMPAT_VERSION) {
 701                                         bat_dbg(DBG_BATMAN, "Drop packet: incompatible batman version (%i)\n", batman_packet->version);
 702                                         continue;
 703                                 }
 704
 705                                 switch (batman_packet->packet_type) {
 706                                 /* batman originator packet */
 707                                 case BAT_PACKET:
 708                                         /* packet with broadcast indication but unicast recipient */
 709                                         if (!is_bcast(ethhdr->h_dest))
 710                                                 continue;
 711
 712                                         /* packet with broadcast sender address */
 713                                         if (is_bcast(ethhdr->h_source))
 714                                                 continue;
 715
 716                                         /* drop packet if it has not at least one batman packet as payload */
 717                                         if (result < sizeof(struct ethhdr) + sizeof(struct batman_packet))
 718                                                 continue;
 719
 720                                         spin_lock(&orig_hash_lock);
 721                                         receive_aggr_bat_packet(ethhdr,
 722                                                                 packet_buff + sizeof(struct ethhdr),
 723                                                                 result - sizeof(struct ethhdr),
 724                                                                 batman_if);
 725                                         spin_unlock(&orig_hash_lock);
 726
 727                                         break;
 728
 729                                 /* batman icmp packet */
 730                                 case BAT_ICMP:
 731                                         /* packet with unicast indication but broadcast recipient */
 732                                         if (is_bcast(ethhdr->h_dest))
 733                                                 continue;
 734
 735                                         /* packet with broadcast sender address */
 736                                         if (is_bcast(ethhdr->h_source))
 737                                                 continue;
 738
 739                                         /* not for me */
 740                                         if (!is_my_mac(ethhdr->h_dest))
 741                                                 continue;
 742
 743                                         /* drop packet if it has not necessary minimum size */
 744                                         if (result < sizeof(struct ethhdr) + sizeof(struct icmp_packet))
 745                                                 continue;
 746
 747                                         icmp_packet = (struct icmp_packet *)(packet_buff + sizeof(struct ethhdr));
 748
 749                                         /* packet for me */
 750                                         if (is_my_mac(icmp_packet->dst)) {
 751
 752                                                 /* add data to device queue */
 753                                                 if (icmp_packet->msg_type != ECHO_REQUEST) {
 754                                                         bat_device_receive_packet(icmp_packet);
 755                                                         continue;
 756                                                 }
 757
 758                                                 /* answer echo request (ping) */
 759                                                 /* get routing information */
 760                                                 spin_lock(&orig_hash_lock);
 761                                                 orig_node = ((struct orig_node *)hash_find(orig_hash, icmp_packet->orig));
 762
 763                                                 if ((orig_node != NULL) && (orig_node->batman_if != NULL) && (orig_node->router != NULL)) {
 764
 765                                                         memcpy(icmp_packet->dst, icmp_packet->orig, ETH_ALEN);
 766                                                         memcpy(icmp_packet->orig, ethhdr->h_dest, ETH_ALEN);
 767                                                         icmp_packet->msg_type = ECHO_REPLY;
 768                                                         icmp_packet->ttl = TTL;
 769
 770                                                         send_raw_packet(packet_buff + sizeof(struct ethhdr),
 771                                                                         result - sizeof(struct ethhdr),
 772                                                                         orig_node->batman_if,
 773                                                                         orig_node->router->addr);
 774
 775                                                 }
 776
 777                                                 spin_unlock(&orig_hash_lock);
 778                                                 continue;
 779
 780                                         }
 781
 782                                         /* TTL exceeded */
 783                                         if (icmp_packet->ttl < 2) {
 784
 785                                                 addr_to_string(src_str, icmp_packet->orig);
 786                                                 addr_to_string(dst_str, icmp_packet->dst);
 787
 788                                                 printk(KERN_WARNING "batman-adv:Warning - can't send packet from %s to %s: ttl exceeded\n", src_str, dst_str);
 789
 790                                                 /* send TTL exceeded if packet is an echo request (traceroute) */
 791                                                 if (icmp_packet->msg_type != ECHO_REQUEST)
 792                                                         continue;
 793
 794                                                 /* get routing information */
 795                                                 spin_lock(&orig_hash_lock);
 796                                                 orig_node = ((struct orig_node *)hash_find(orig_hash, icmp_packet->orig));
 797
 798                                                 if ((orig_node != NULL) && (orig_node->batman_if != NULL) && (orig_node->router != NULL)) {
 799
 800                                                         memcpy(icmp_packet->dst, icmp_packet->orig, ETH_ALEN);
 801                                                         memcpy(icmp_packet->orig, ethhdr->h_dest, ETH_ALEN);
 802                                                         icmp_packet->msg_type = TTL_EXCEEDED;
 803                                                         icmp_packet->ttl = TTL;
 804
 805                                                         send_raw_packet(packet_buff + sizeof(struct ethhdr),
 806                                                                         result - sizeof(struct ethhdr),
 807                                                                         orig_node->batman_if,
 808                                                                         orig_node->router->addr);
 809
 810                                                 }
 811
 812                                                 spin_unlock(&orig_hash_lock);
 813                                                 continue;
 814
 815                                         }
 816
 817                                         /* get routing information */
 818                                         spin_lock(&orig_hash_lock);
 819                                         orig_node = ((struct orig_node *)hash_find(orig_hash, icmp_packet->dst));
 820
 821                                         if ((orig_node != NULL) && (orig_node->batman_if != NULL) && (orig_node->router != NULL)) {
 822
 823                                                 /* decrement ttl */
 824                                                 icmp_packet->ttl--;
 825
 826                                                 /* route it */
 827                                                 send_raw_packet(packet_buff + sizeof(struct ethhdr),
 828                                                                 result - sizeof(struct ethhdr),
 829                                                                 orig_node->batman_if,
 830                                                                 orig_node->router->addr);
 831                                         }
 832
 833                                         spin_unlock(&orig_hash_lock);
 834                                         break;
 835
 836                                 /* unicast packet */
 837                                 case BAT_UNICAST:
 838                                         /* packet with unicast indication but broadcast recipient */
 839                                         if (is_bcast(ethhdr->h_dest))
 840                                                 continue;
 841
 842                                         /* packet with broadcast sender address */
 843                                         if (is_bcast(ethhdr->h_source))
 844                                                 continue;
 845
 846                                         /* not for me */
 847                                         if (!is_my_mac(ethhdr->h_dest))
 848                                                 continue;
 849
 850                                         /* drop packet if it has not necessary minimum size */
 851                                         if (result < sizeof(struct ethhdr) + sizeof(struct unicast_packet))
 852                                                 continue;
 853
 854                                         unicast_packet = (struct unicast_packet *)(packet_buff + sizeof(struct ethhdr));
 855
 856                                         /* packet for me */
 857                                         if (is_my_mac(unicast_packet->dest)) {
 858
 859                                                 interface_rx(soft_device, packet_buff + sizeof(struct ethhdr) + sizeof(struct unicast_packet), result - sizeof(struct ethhdr) - sizeof(struct unicast_packet));
 860                                                 continue;
 861
 862                                         }
 863
 864                                         /* TTL exceeded */
 865                                         if (unicast_packet->ttl < 2) {
 866                                                 addr_to_string(src_str, ((struct ethhdr *)(unicast_packet + 1))->h_source);
 867                                                 addr_to_string(dst_str, unicast_packet->dest);
 868
 869                                                 printk(KERN_WARNING "batman-adv:Warning - can't send packet from %s to %s: ttl exceeded\n", src_str, dst_str);
 870                                                 continue;
 871                                         }
 872
 873                                         /* get routing information */
 874                                         spin_lock(&orig_hash_lock);
 875                                         orig_node = ((struct orig_node *)hash_find(orig_hash, unicast_packet->dest));
 876
 877                                         if ((orig_node != NULL) && (orig_node->batman_if != NULL) && (orig_node->router != NULL)) {
 878                                                 /* decrement ttl */
 879                                                 unicast_packet->ttl--;
 880
 881                                                 /* route it */
 882                                                 send_raw_packet(packet_buff + sizeof(struct ethhdr),
 883                                                                 result - sizeof(struct ethhdr),
 884                                                                 orig_node->batman_if,
 885                                                                 orig_node->router->addr);
 886                                         }
 887
 888                                         spin_unlock(&orig_hash_lock);
 889                                         break;
 890
 891                                 /* broadcast packet */
 892                                 case BAT_BCAST:
 893                                         /* packet with broadcast indication but unicast recipient */
 894                                         if (!is_bcast(ethhdr->h_dest))
 895                                                 continue;
 896
 897                                         /* packet with broadcast sender address */
 898                                         if (is_bcast(ethhdr->h_source))
 899                                                 continue;
 900
 901                                         /* drop packet if it has not necessary minimum size */
 902                                         if (result < sizeof(struct ethhdr) + sizeof(struct bcast_packet))
 903                                                 continue;
 904
 905                                         /* ignore broadcasts sent by myself */
 906                                         if (is_my_mac(ethhdr->h_source))
 907                                                 continue;
 908
 909                                         bcast_packet = (struct bcast_packet *)(packet_buff + sizeof(struct ethhdr));
 910
 911                                         /* ignore broadcasts originated by myself */
 912                                         if (is_my_mac(bcast_packet->orig))
 913                                                 continue;
 914
 915                                         spin_lock(&orig_hash_lock);
 916                                         orig_node = ((struct orig_node *)hash_find(orig_hash, bcast_packet->orig));
 917
 918                                         if (orig_node == NULL) {
 919                                                 spin_unlock(&orig_hash_lock);
 920                                                 continue;
 921                                         }
 922
 923                                         /* check flood history */
 924                                         if (get_bit_status(orig_node->bcast_bits, orig_node->last_bcast_seqno, ntohs(bcast_packet->seqno))) {
 925                                                 spin_unlock(&orig_hash_lock);
 926                                                 continue;
 927                                         }
 928
 929                                         /* mark broadcast in flood history */
 930                                         if (bit_get_packet(orig_node->bcast_bits, ntohs(bcast_packet->seqno) - orig_node->last_bcast_seqno, 1))
 931                                                 orig_node->last_bcast_seqno = ntohs(bcast_packet->seqno);
 932
 933                                         spin_unlock(&orig_hash_lock);
 934
 935                                         /* broadcast for me */
 936                                         interface_rx(soft_device, packet_buff + sizeof(struct ethhdr) + sizeof(struct bcast_packet), result - sizeof(struct ethhdr) - sizeof(struct bcast_packet));
 937
 938                                         /* rebroadcast packet */
 939                                         add_bcast_packet_to_list(packet_buff + sizeof(struct ethhdr),
 940                                                                         result - sizeof(struct ethhdr));
 941
 942                                         break;
 943
 944                                 /* vis packet */
 945                                 case BAT_VIS:
 946                                         /* drop if too short. */
 947                                         if (result < sizeof(struct ethhdr) + sizeof(struct vis_packet))
 948                                                 continue;
 949
 950                                         /* not for me */
 951                                         if (!is_my_mac(ethhdr->h_dest))
 952                                                 continue;
 953
 954                                         vis_packet = (struct vis_packet *)(packet_buff + sizeof(struct ethhdr));
 955                                         vis_info_len = result  - sizeof(struct ethhdr) - sizeof(struct vis_packet);
 956
 957                                         /* ignore own packets */
 958                                         if (is_my_mac(vis_packet->vis_orig))
 959                                                 continue;
 960
 961                                         if (is_my_mac(vis_packet->sender_orig))
 962                                                 continue;
 963
 964                                         switch (vis_packet->vis_type) {
 965                                         case VIS_TYPE_SERVER_SYNC:
 966                                                 receive_server_sync_packet(vis_packet, vis_info_len);
 967                                                 break;
 968
 969                                         case VIS_TYPE_CLIENT_UPDATE:
 970                                                 receive_client_update_packet(vis_packet, vis_info_len);
 971                                                 break;
 972
 973                                         default:        /* ignore unknown packet */
 974                                                 break;
 975                                         }
 976
 977                                         break;
 978                                 }
 979
 980                         }
 981
 982                         if ((result < 0) && (result != -EAGAIN))
 983                                 printk(KERN_ERR "batman-adv:Could not receive packet from interface %s: %i\n", batman_if->dev, result);
 984
 985                         /* lock for the next iteration */
 986                         rcu_read_lock();
 987                 }
 988                 rcu_read_unlock();
 989
 990         }
 991         kfree(packet_buff);
 992
 993         /* do not exit until kthread_stop() is actually called, otherwise it will wait for us
 994          * forever. */
 995         while (!kthread_should_stop())
 996                 schedule();
 997
 998         return 0;
 999 }
1000
1001 void batman_data_ready(struct sock *sk, int len)
1002 {
1003         void (*data_ready)(struct sock *, int) = sk->sk_user_data;
1004
1005         data_ready(sk, len);
1006
1007         atomic_set(&data_ready_cond, 1);
1008         wake_up_interruptible(&thread_wait);
1009 }
1010