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 "log.h"
  29 #include "send.h"
  30 #include "soft-interface.h"
  31 #include "hard-interface.h"
  32 #include "device.h"
  33 #include "translation-table.h"
  34 #include "types.h"
  35 #include "hash.h"
  36 #include "ring_buffer.h"
  37 #include "vis.h"
  38 #include "aggregation.h"
  39 #include "compat.h"
  40
  41
  42
  43 DECLARE_WAIT_QUEUE_HEAD(thread_wait);
  44 static DECLARE_DELAYED_WORK(purge_orig_wq, purge_orig);
  45
  46 static atomic_t data_ready_cond;
  47 atomic_t exit_cond;
  48
  49 static void start_purge_timer(void)
  50 {
  51         queue_delayed_work(bat_event_workqueue, &purge_orig_wq, 1 * HZ);
  52 }
  53
  54 int originator_init(void)
  55 {
  56         if (orig_hash)
  57                 return 1;
  58
  59         spin_lock(&orig_hash_lock);
  60         orig_hash = hash_new(128, compare_orig, choose_orig);
  61
  62         if (!orig_hash)
  63                 goto err;
  64
  65         spin_unlock(&orig_hash_lock);
  66         start_purge_timer();
  67         return 1;
  68
  69 err:
  70         spin_unlock(&orig_hash_lock);
  71         return 0;
  72 }
  73
  74 void originator_free(void)
  75 {
  76         if (!orig_hash)
  77                 return;
  78
  79         cancel_delayed_work_sync(&purge_orig_wq);
  80
  81         spin_lock(&orig_hash_lock);
  82         hash_delete(orig_hash, free_orig_node);
  83         orig_hash = NULL;
  84         spin_unlock(&orig_hash_lock);
  85 }
  86
  87 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)
  88 {
  89         struct neigh_node *neigh_node;
  90
  91         debug_log(LOG_TYPE_BATMAN, "Creating new last-hop neighbour of originator\n");
  92
  93         neigh_node = kmalloc(sizeof(struct neigh_node), GFP_ATOMIC);
  94         memset(neigh_node, 0, sizeof(struct neigh_node));
  95         INIT_LIST_HEAD(&neigh_node->list);
  96
  97         memcpy(neigh_node->addr, neigh, ETH_ALEN);
  98         neigh_node->orig_node = orig_neigh_node;
  99         neigh_node->if_incoming = if_incoming;
 100
 101         list_add_tail(&neigh_node->list, &orig_node->neigh_list);
 102         return neigh_node;
 103 }
 104
 105 void free_orig_node(void *data)
 106 {
 107         struct list_head *list_pos, *list_pos_tmp;
 108         struct neigh_node *neigh_node;
 109         struct orig_node *orig_node = (struct orig_node *)data;
 110
 111         /* for all neighbours towards this originator ... */
 112         list_for_each_safe(list_pos, list_pos_tmp, &orig_node->neigh_list) {
 113                 neigh_node = list_entry(list_pos, struct neigh_node, list);
 114
 115                 list_del(list_pos);
 116                 kfree(neigh_node);
 117         }
 118
 119         hna_global_del_orig(orig_node, "originator timed out");
 120
 121         kfree(orig_node->bcast_own);
 122         kfree(orig_node->bcast_own_sum);
 123         kfree(orig_node);
 124 }
 125
 126 /* this function finds or creates an originator entry for the given address if it does not exits */
 127 static struct orig_node *get_orig_node(uint8_t *addr)
 128 {
 129         struct orig_node *orig_node;
 130         struct hashtable_t *swaphash;
 131         char orig_str[ETH_STR_LEN];
 132
 133         orig_node = ((struct orig_node *)hash_find(orig_hash, addr));
 134
 135         if (orig_node != NULL)
 136                 return orig_node;
 137
 138         addr_to_string(orig_str, addr);
 139         debug_log(LOG_TYPE_BATMAN, "Creating new originator: %s \n", orig_str);
 140
 141         orig_node = kmalloc(sizeof(struct orig_node), GFP_ATOMIC);
 142         memset(orig_node, 0, sizeof(struct orig_node));
 143         INIT_LIST_HEAD(&orig_node->neigh_list);
 144
 145         memcpy(orig_node->orig, addr, ETH_ALEN);
 146         orig_node->router = NULL;
 147         orig_node->batman_if = NULL;
 148         orig_node->hna_buff = NULL;
 149
 150         orig_node->bcast_own = kmalloc(num_ifs * sizeof(TYPE_OF_WORD) * NUM_WORDS, GFP_ATOMIC);
 151         memset(orig_node->bcast_own, 0, num_ifs * sizeof(TYPE_OF_WORD) * NUM_WORDS);
 152
 153         orig_node->bcast_own_sum = kmalloc(num_ifs * sizeof(uint8_t), GFP_ATOMIC);
 154         memset(orig_node->bcast_own_sum, 0, num_ifs * sizeof(uint8_t));
 155
 156         hash_add(orig_hash, orig_node);
 157
 158         if (orig_hash->elements * 4 > orig_hash->size) {
 159                 swaphash = hash_resize(orig_hash, orig_hash->size * 2);
 160
 161                 if (swaphash == NULL)
 162                         debug_log(LOG_TYPE_CRIT, "Couldn't resize orig hash table \n");
 163                 else
 164                         orig_hash = swaphash;
 165         }
 166
 167         return orig_node;
 168 }
 169
 170 void slide_own_bcast_window(struct batman_if *batman_if)
 171 {
 172         struct hash_it_t *hashit = NULL;
 173         struct orig_node *orig_node;
 174
 175         spin_lock(&orig_hash_lock);
 176
 177         while (NULL != (hashit = hash_iterate(orig_hash, hashit))) {
 178                 orig_node = hashit->bucket->data;
 179
 180                 bit_get_packet((TYPE_OF_WORD *)&(orig_node->bcast_own[batman_if->if_num * NUM_WORDS]), 1, 0);
 181                 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]));
 182         }
 183
 184         spin_unlock(&orig_hash_lock);
 185 }
 186
 187 static void update_routes(struct orig_node *orig_node, struct neigh_node *neigh_node, unsigned char *hna_buff, int hna_buff_len)
 188 {
 189         char orig_str[ETH_STR_LEN], neigh_str[ETH_STR_LEN], router_str[ETH_STR_LEN];
 190
 191         if (orig_node == NULL)
 192                 return;
 193
 194         if (orig_node->router != neigh_node) {
 195                 addr_to_string(orig_str, orig_node->orig);
 196
 197                 /* route deleted */
 198                 if ((orig_node->router != NULL) && (neigh_node == NULL)) {
 199
 200                         debug_log(LOG_TYPE_ROUTES, "Deleting route towards: %s\n", orig_str);
 201                         hna_global_del_orig(orig_node, "originator timed out");
 202
 203                 /* route added */
 204                 } else if ((orig_node->router == NULL) && (neigh_node != NULL)) {
 205
 206                         addr_to_string(neigh_str, neigh_node->addr);
 207                         debug_log(LOG_TYPE_ROUTES, "Adding route towards: %s (via %s)\n", orig_str, neigh_str);
 208                         hna_global_add_orig(orig_node, hna_buff, hna_buff_len);
 209
 210                 /* route changed */
 211                 } else {
 212
 213                         addr_to_string(neigh_str, neigh_node->addr);
 214                         addr_to_string(router_str, orig_node->router->addr);
 215                         debug_log(LOG_TYPE_ROUTES, "Changing route towards: %s (now via %s - was via %s)\n", orig_str, neigh_str, router_str);
 216
 217                 }
 218
 219                 if (neigh_node != NULL)
 220                         orig_node->batman_if = neigh_node->if_incoming;
 221                 else
 222                         orig_node->batman_if = NULL;
 223
 224                 orig_node->router = neigh_node;
 225
 226         /* may be just HNA changed */
 227         } else {
 228
 229                 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))) {
 230
 231                         if (orig_node->hna_buff_len > 0)
 232                                 hna_global_del_orig(orig_node, "originator changed hna");
 233
 234                         if ((hna_buff_len > 0) && (hna_buff != NULL))
 235                                 hna_global_add_orig(orig_node, hna_buff, hna_buff_len);
 236
 237                 }
 238
 239         }
 240 }
 241
 242 static int isBidirectionalNeigh(struct orig_node *orig_node, struct orig_node *orig_neigh_node, struct batman_packet *batman_packet, struct batman_if *if_incoming)
 243 {
 244         struct neigh_node *neigh_node = NULL, *tmp_neigh_node = NULL;
 245         char orig_str[ETH_STR_LEN], neigh_str[ETH_STR_LEN];
 246         unsigned char total_count;
 247
 248         addr_to_string(orig_str, orig_node->orig);
 249         addr_to_string(neigh_str, orig_neigh_node->orig);
 250
 251         if (orig_node == orig_neigh_node) {
 252                 list_for_each_entry(tmp_neigh_node, &orig_node->neigh_list, list) {
 253
 254                         if (compare_orig(tmp_neigh_node->addr, orig_neigh_node->orig) && (tmp_neigh_node->if_incoming == if_incoming))
 255                                 neigh_node = tmp_neigh_node;
 256                 }
 257
 258                 if (neigh_node == NULL)
 259                         neigh_node = create_neighbor(orig_node, orig_neigh_node, orig_neigh_node->orig, if_incoming);
 260
 261                 neigh_node->last_valid = jiffies;
 262         } else {
 263                 /* find packet count of corresponding one hop neighbor */
 264                 list_for_each_entry(tmp_neigh_node, &orig_neigh_node->neigh_list, list) {
 265
 266                         if (compare_orig(tmp_neigh_node->addr, orig_neigh_node->orig) && (tmp_neigh_node->if_incoming == if_incoming))
 267                                 neigh_node = tmp_neigh_node;
 268                 }
 269
 270                 if (neigh_node == NULL)
 271                         neigh_node = create_neighbor(orig_neigh_node, orig_neigh_node, orig_neigh_node->orig, if_incoming);
 272         }
 273
 274         orig_node->last_valid = jiffies;
 275
 276         /* pay attention to not get a value bigger than 100 % */
 277         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]);
 278
 279         /* if we have too few packets (too less data) we set tq_own to zero */
 280         /* if we receive too few packets it is not considered bidirectional */
 281         if ((total_count < TQ_LOCAL_BIDRECT_SEND_MINIMUM) || (neigh_node->real_packet_count < TQ_LOCAL_BIDRECT_RECV_MINIMUM))
 282                 orig_neigh_node->tq_own = 0;
 283         else
 284                 /* neigh_node->real_packet_count is never zero as we only purge old information when getting new information */
 285                 orig_neigh_node->tq_own = (TQ_MAX_VALUE * total_count) / neigh_node->real_packet_count;
 286
 287         /*
 288          * 1 - ((1-x) ** 3), normalized to TQ_MAX_VALUE
 289          * this does affect the nearly-symmetric links only a little,
 290          * but punishes asymmetric links more.
 291          * this will give a value between 0 and TQ_MAX_VALUE
 292          */
 293         orig_neigh_node->tq_asym_penalty = TQ_MAX_VALUE - (TQ_MAX_VALUE *
 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 - neigh_node->real_packet_count)) /
 297                         (TQ_LOCAL_WINDOW_SIZE * TQ_LOCAL_WINDOW_SIZE * TQ_LOCAL_WINDOW_SIZE);
 298
 299         batman_packet->tq = ((batman_packet->tq * orig_neigh_node->tq_own * orig_neigh_node->tq_asym_penalty) / (TQ_MAX_VALUE *  TQ_MAX_VALUE));
 300
 301         debug_log(LOG_TYPE_BATMAN, "bidirectional: orig = %-15s neigh = %-15s => own_bcast = %2i, real recv = %2i, local tq: %3i, asym_penalty: %3i, total tq: %3i \n",
 302                   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);
 303
 304         /* if link has the minimum required transmission quality consider it bidirectional */
 305         if (batman_packet->tq >= TQ_TOTAL_BIDRECT_LIMIT)
 306                 return 1;
 307
 308         return 0;
 309 }
 310
 311 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)
 312 {
 313         struct neigh_node *neigh_node = NULL, *tmp_neigh_node = NULL;
 314         int tmp_hna_buff_len;
 315
 316         debug_log(LOG_TYPE_BATMAN, "update_originator(): Searching and updating originator entry of received packet \n");
 317
 318         list_for_each_entry(tmp_neigh_node, &orig_node->neigh_list, list) {
 319                 if (compare_orig(tmp_neigh_node->addr, ethhdr->h_source) && (tmp_neigh_node->if_incoming == if_incoming)) {
 320                         neigh_node = tmp_neigh_node;
 321                         continue;
 322                 }
 323
 324                 if (is_duplicate)
 325                         continue;
 326
 327                 ring_buffer_set(tmp_neigh_node->tq_recv, &tmp_neigh_node->tq_index, 0);
 328                 tmp_neigh_node->tq_avg = ring_buffer_avg(tmp_neigh_node->tq_recv);
 329         }
 330
 331         if (neigh_node == NULL)
 332                 neigh_node = create_neighbor(orig_node, get_orig_node(ethhdr->h_source), ethhdr->h_source, if_incoming);
 333         else
 334                 debug_log(LOG_TYPE_BATMAN, "Updating existing last-hop neighbour of originator\n");
 335
 336         orig_node->flags = batman_packet->flags;
 337         neigh_node->last_valid = jiffies;
 338
 339         ring_buffer_set(neigh_node->tq_recv, &neigh_node->tq_index, batman_packet->tq);
 340         neigh_node->tq_avg = ring_buffer_avg(neigh_node->tq_recv);
 341
 342         if (!is_duplicate) {
 343                 orig_node->last_ttl = batman_packet->ttl;
 344                 neigh_node->last_ttl = batman_packet->ttl;
 345         }
 346
 347         tmp_hna_buff_len = (hna_buff_len > batman_packet->num_hna * ETH_ALEN ? batman_packet->num_hna * ETH_ALEN : hna_buff_len);
 348
 349         /* if this neighbor already is our next hop there is nothing to change */
 350         if (orig_node->router == neigh_node)
 351                 goto update_hna;
 352
 353         /* if this neighbor does not offer a better TQ we won't consider it */
 354         if ((orig_node->router) &&
 355             (orig_node->router->tq_avg > neigh_node->tq_avg))
 356                 goto update_hna;
 357
 358         /* if the TQ is the same and the link not more symetric we won't consider it either */
 359         if ((orig_node->router) &&
 360              ((neigh_node->tq_avg == orig_node->router->tq_avg) &&
 361              (orig_node->router->orig_node->bcast_own_sum[if_incoming->if_num] >=
 362               neigh_node->orig_node->bcast_own_sum[if_incoming->if_num])))
 363                 goto update_hna;
 364
 365         update_routes(orig_node, neigh_node, hna_buff, tmp_hna_buff_len);
 366         return;
 367
 368 update_hna:
 369         update_routes(orig_node, orig_node->router, hna_buff, tmp_hna_buff_len);
 370         return;
 371 }
 372
 373 static char count_real_packets(struct ethhdr *ethhdr, struct batman_packet *batman_packet, struct batman_if *if_incoming)
 374 {
 375         struct orig_node *orig_node;
 376         struct neigh_node *tmp_neigh_node;
 377         char is_duplicate = 0;
 378
 379
 380         orig_node = get_orig_node(batman_packet->orig);
 381         if (orig_node == NULL)
 382                 return 0;
 383
 384
 385         list_for_each_entry(tmp_neigh_node, &orig_node->neigh_list, list) {
 386
 387                 if (!is_duplicate)
 388                         is_duplicate = get_bit_status(tmp_neigh_node->real_bits, orig_node->last_real_seqno, batman_packet->seqno);
 389
 390                 if (compare_orig(tmp_neigh_node->addr, ethhdr->h_source) && (tmp_neigh_node->if_incoming == if_incoming))
 391                         bit_get_packet(tmp_neigh_node->real_bits, batman_packet->seqno - orig_node->last_real_seqno, 1);
 392                 else
 393                         bit_get_packet(tmp_neigh_node->real_bits, batman_packet->seqno - orig_node->last_real_seqno, 0);
 394
 395                 tmp_neigh_node->real_packet_count = bit_packet_count(tmp_neigh_node->real_bits);
 396         }
 397
 398         if (!is_duplicate) {
 399                 debug_log(LOG_TYPE_BATMAN, "updating last_seqno: old %d, new %d \n", 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         debug_log(LOG_TYPE_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                 debug_log(LOG_TYPE_BATMAN, "Drop packet: incompatible batman version (%i) \n", batman_packet->version);
 460                 return;
 461         }
 462
 463         if (is_my_addr) {
 464                 debug_log(LOG_TYPE_BATMAN, "Drop packet: received my own broadcast (sender: %s) \n", neigh_str);
 465                 return;
 466         }
 467
 468         if (is_broadcast) {
 469                 debug_log(LOG_TYPE_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                 debug_log(LOG_TYPE_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                 debug_log(LOG_TYPE_BATMAN, "Drop packet: originator packet with tq equal 0 \n");
 492                 return;
 493         }
 494
 495         if (is_my_oldorig) {
 496                 debug_log(LOG_TYPE_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                 debug_log(LOG_TYPE_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                 debug_log(LOG_TYPE_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                 debug_log(LOG_TYPE_BATMAN, "Forwarding packet: rebroadcast neighbour packet with direct link flag \n");
 541                 return;
 542         }
 543
 544         /* multihop originator */
 545         if (!is_bidirectional) {
 546                 debug_log(LOG_TYPE_BATMAN, "Drop packet: not received via bidirectional link\n");
 547                 return;
 548         }
 549
 550         if (is_duplicate) {
 551                 debug_log(LOG_TYPE_BATMAN, "Drop packet: duplicate packet received\n");
 552                 return;
 553         }
 554
 555         debug_log(LOG_TYPE_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                         debug_log(LOG_TYPE_BATMAN, "Originator timeout: originator %s, last_valid %u \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                                         debug_log(LOG_TYPE_BATMAN, "Neighbour timeout: originator %s, neighbour: %s, last_valid %u \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                 debug_log(LOG_TYPE_CRIT, "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                                                 debug_log(LOG_TYPE_NOTICE,
 681                                                           "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                                         debug_log(LOG_TYPE_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                                                 debug_log(LOG_TYPE_NOTICE, "Error - 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                                                 debug_log(LOG_TYPE_NOTICE, "Error - 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                                 debug_log(LOG_TYPE_CRIT, "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