drivers/staging/batman-adv/vis.c

   1 /*
   2  * Copyright (C) 2008-2009 B.A.T.M.A.N. contributors:
   3  *
   4  * 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 #include "main.h"
  23 #include "send.h"
  24 #include "translation-table.h"
  25 #include "vis.h"
  26 #include "soft-interface.h"
  27 #include "hard-interface.h"
  28 #include "hash.h"
  29 #include "compat.h"
  30
  31 struct hashtable_t *vis_hash;
  32 DEFINE_SPINLOCK(vis_hash_lock);
  33 static struct vis_info *my_vis_info;
  34 static struct list_head send_list;      /* always locked with vis_hash_lock */
  35
  36 static void start_vis_timer(void);
  37
  38 /* free the info */
  39 static void free_info(void *data)
  40 {
  41         struct vis_info *info = data;
  42         struct recvlist_node *entry, *tmp;
  43
  44         list_del_init(&info->send_list);
  45         list_for_each_entry_safe(entry, tmp, &info->recv_list, list) {
  46                 list_del(&entry->list);
  47                 kfree(entry);
  48         }
  49         kfree(info);
  50 }
  51
  52 /* set the mode of the visualization to client or server */
  53 void vis_set_mode(int mode)
  54 {
  55         unsigned long flags;
  56         spin_lock_irqsave(&vis_hash_lock, flags);
  57
  58         if (my_vis_info != NULL)
  59                 my_vis_info->packet.vis_type = mode;
  60
  61         spin_unlock_irqrestore(&vis_hash_lock, flags);
  62 }
  63
  64 /* is_vis_server(), locked outside */
  65 static int is_vis_server_locked(void)
  66 {
  67         if (my_vis_info != NULL)
  68                 if (my_vis_info->packet.vis_type == VIS_TYPE_SERVER_SYNC)
  69                         return 1;
  70
  71         return 0;
  72 }
  73
  74 /* get the current set mode */
  75 int is_vis_server(void)
  76 {
  77         int ret = 0;
  78         unsigned long flags;
  79
  80         spin_lock_irqsave(&vis_hash_lock, flags);
  81         ret = is_vis_server_locked();
  82         spin_unlock_irqrestore(&vis_hash_lock, flags);
  83
  84         return ret;
  85 }
  86
  87 /* Compare two vis packets, used by the hashing algorithm */
  88 static int vis_info_cmp(void *data1, void *data2)
  89 {
  90         struct vis_info *d1, *d2;
  91         d1 = data1;
  92         d2 = data2;
  93         return compare_orig(d1->packet.vis_orig, d2->packet.vis_orig);
  94 }
  95
  96 /* hash function to choose an entry in a hash table of given size */
  97 /* hash algorithm from http://en.wikipedia.org/wiki/Hash_table */
  98 static int vis_info_choose(void *data, int size)
  99 {
 100         struct vis_info *vis_info = data;
 101         unsigned char *key;
 102         uint32_t hash = 0;
 103         size_t i;
 104
 105         key = vis_info->packet.vis_orig;
 106         for (i = 0; i < ETH_ALEN; i++) {
 107                 hash += key[i];
 108                 hash += (hash << 10);
 109                 hash ^= (hash >> 6);
 110         }
 111
 112         hash += (hash << 3);
 113         hash ^= (hash >> 11);
 114         hash += (hash << 15);
 115
 116         return hash % size;
 117 }
 118
 119 /* insert interface to the list of interfaces of one originator, if it
 120  * does not already exist in the list */
 121 static void proc_vis_insert_interface(const uint8_t *interface,
 122                                       struct hlist_head *if_list,
 123                                       bool primary)
 124 {
 125         struct if_list_entry *entry;
 126         struct hlist_node *pos;
 127
 128         hlist_for_each_entry(entry, pos, if_list, list) {
 129                 if (compare_orig(entry->addr, (void *)interface))
 130                         return;
 131         }
 132
 133         /* its a new address, add it to the list */
 134         entry = kmalloc(sizeof(*entry), GFP_KERNEL);
 135         if (!entry)
 136                 return;
 137         memcpy(entry->addr, interface, ETH_ALEN);
 138         entry->primary = primary;
 139         hlist_add_head(&entry->list, if_list);
 140 }
 141
 142 void proc_vis_read_prim_sec(struct seq_file *seq,
 143                             struct hlist_head *if_list)
 144 {
 145         struct if_list_entry *entry;
 146         struct hlist_node *pos, *n;
 147         char tmp_addr_str[ETH_STR_LEN];
 148
 149         hlist_for_each_entry_safe(entry, pos, n, if_list, list) {
 150                 if (entry->primary) {
 151                         seq_printf(seq, "PRIMARY, ");
 152                 } else {
 153                         addr_to_string(tmp_addr_str, entry->addr);
 154                         seq_printf(seq, "SEC %s, ", tmp_addr_str);
 155                 }
 156
 157                 hlist_del(&entry->list);
 158                 kfree(entry);
 159         }
 160 }
 161
 162 /* read an entry  */
 163 void proc_vis_read_entry(struct seq_file *seq,
 164                                 struct vis_info_entry *entry,
 165                                 struct hlist_head *if_list,
 166                                 uint8_t *vis_orig)
 167 {
 168         char to[40];
 169
 170         addr_to_string(to, entry->dest);
 171         if (entry->quality == 0) {
 172                 proc_vis_insert_interface(vis_orig, if_list, true);
 173                 seq_printf(seq, "HNA %s, ", to);
 174         } else {
 175                 proc_vis_insert_interface(entry->src, if_list,
 176                                           compare_orig(entry->src, vis_orig));
 177                 seq_printf(seq, "TQ %s %d, ", to, entry->quality);
 178         }
 179 }
 180
 181 /* tries to add one entry to the receive list. */
 182 static void recv_list_add(struct list_head *recv_list, char *mac)
 183 {
 184         struct recvlist_node *entry;
 185         entry = kmalloc(sizeof(struct recvlist_node), GFP_ATOMIC);
 186         if (!entry)
 187                 return;
 188
 189         memcpy(entry->mac, mac, ETH_ALEN);
 190         list_add_tail(&entry->list, recv_list);
 191 }
 192
 193 /* returns 1 if this mac is in the recv_list */
 194 static int recv_list_is_in(struct list_head *recv_list, char *mac)
 195 {
 196         struct recvlist_node *entry;
 197
 198         list_for_each_entry(entry, recv_list, list) {
 199                 if (memcmp(entry->mac, mac, ETH_ALEN) == 0)
 200                         return 1;
 201         }
 202
 203         return 0;
 204 }
 205
 206 /* try to add the packet to the vis_hash. return NULL if invalid (e.g. too old,
 207  * broken.. ).  vis hash must be locked outside.  is_new is set when the packet
 208  * is newer than old entries in the hash. */
 209 static struct vis_info *add_packet(struct vis_packet *vis_packet,
 210                                    int vis_info_len, int *is_new)
 211 {
 212         struct vis_info *info, *old_info;
 213         struct vis_info search_elem;
 214
 215         *is_new = 0;
 216         /* sanity check */
 217         if (vis_hash == NULL)
 218                 return NULL;
 219
 220         /* see if the packet is already in vis_hash */
 221         memcpy(search_elem.packet.vis_orig, vis_packet->vis_orig, ETH_ALEN);
 222         old_info = hash_find(vis_hash, &search_elem);
 223
 224         if (old_info != NULL) {
 225                 if (vis_packet->seqno - old_info->packet.seqno <= 0) {
 226                         if (old_info->packet.seqno == vis_packet->seqno) {
 227                                 recv_list_add(&old_info->recv_list,
 228                                               vis_packet->sender_orig);
 229                                 return old_info;
 230                         } else {
 231                                 /* newer packet is already in hash. */
 232                                 return NULL;
 233                         }
 234                 }
 235                 /* remove old entry */
 236                 hash_remove(vis_hash, old_info);
 237                 free_info(old_info);
 238         }
 239
 240         info = kmalloc(sizeof(struct vis_info) + vis_info_len, GFP_ATOMIC);
 241         if (info == NULL)
 242                 return NULL;
 243
 244         INIT_LIST_HEAD(&info->send_list);
 245         INIT_LIST_HEAD(&info->recv_list);
 246         info->first_seen = jiffies;
 247         memcpy(&info->packet, vis_packet,
 248                sizeof(struct vis_packet) + vis_info_len);
 249
 250         /* initialize and add new packet. */
 251         *is_new = 1;
 252
 253         /* repair if entries is longer than packet. */
 254         if (info->packet.entries * sizeof(struct vis_info_entry) > vis_info_len)
 255                 info->packet.entries = vis_info_len / sizeof(struct vis_info_entry);
 256
 257         recv_list_add(&info->recv_list, info->packet.sender_orig);
 258
 259         /* try to add it */
 260         if (hash_add(vis_hash, info) < 0) {
 261                 /* did not work (for some reason) */
 262                 free_info(info);
 263                 info = NULL;
 264         }
 265
 266         return info;
 267 }
 268
 269 /* handle the server sync packet, forward if needed. */
 270 void receive_server_sync_packet(struct vis_packet *vis_packet, int vis_info_len)
 271 {
 272         struct vis_info *info;
 273         int is_new;
 274         unsigned long flags;
 275
 276         spin_lock_irqsave(&vis_hash_lock, flags);
 277         info = add_packet(vis_packet, vis_info_len, &is_new);
 278         if (info == NULL)
 279                 goto end;
 280
 281         /* only if we are server ourselves and packet is newer than the one in
 282          * hash.*/
 283         if (is_vis_server_locked() && is_new) {
 284                 memcpy(info->packet.target_orig, broadcastAddr, ETH_ALEN);
 285                 if (list_empty(&info->send_list))
 286                         list_add_tail(&info->send_list, &send_list);
 287         }
 288 end:
 289         spin_unlock_irqrestore(&vis_hash_lock, flags);
 290 }
 291
 292 /* handle an incoming client update packet and schedule forward if needed. */
 293 void receive_client_update_packet(struct vis_packet *vis_packet,
 294                                   int vis_info_len)
 295 {
 296         struct vis_info *info;
 297         int is_new;
 298         unsigned long flags;
 299
 300         /* clients shall not broadcast. */
 301         if (is_bcast(vis_packet->target_orig))
 302                 return;
 303
 304         spin_lock_irqsave(&vis_hash_lock, flags);
 305         info = add_packet(vis_packet, vis_info_len, &is_new);
 306         if (info == NULL)
 307                 goto end;
 308         /* note that outdated packets will be dropped at this point. */
 309
 310
 311         /* send only if we're the target server or ... */
 312         if (is_vis_server_locked() &&
 313             is_my_mac(info->packet.target_orig) &&
 314             is_new) {
 315                 info->packet.vis_type = VIS_TYPE_SERVER_SYNC;   /* upgrade! */
 316                 memcpy(info->packet.target_orig, broadcastAddr, ETH_ALEN);
 317                 if (list_empty(&info->send_list))
 318                         list_add_tail(&info->send_list, &send_list);
 319
 320                 /* ... we're not the recipient (and thus need to forward). */
 321         } else if (!is_my_mac(info->packet.target_orig)) {
 322                 if (list_empty(&info->send_list))
 323                         list_add_tail(&info->send_list, &send_list);
 324         }
 325 end:
 326         spin_unlock_irqrestore(&vis_hash_lock, flags);
 327 }
 328
 329 /* Walk the originators and find the VIS server with the best tq. Set the packet
 330  * address to its address and return the best_tq.
 331  *
 332  * Must be called with the originator hash locked */
 333 static int find_best_vis_server(struct vis_info *info)
 334 {
 335         HASHIT(hashit);
 336         struct orig_node *orig_node;
 337         int best_tq = -1;
 338
 339         while (hash_iterate(orig_hash, &hashit)) {
 340                 orig_node = hashit.bucket->data;
 341                 if ((orig_node != NULL) &&
 342                     (orig_node->router != NULL) &&
 343                     (orig_node->flags & VIS_SERVER) &&
 344                     (orig_node->router->tq_avg > best_tq)) {
 345                         best_tq = orig_node->router->tq_avg;
 346                         memcpy(info->packet.target_orig, orig_node->orig,
 347                                ETH_ALEN);
 348                 }
 349         }
 350         return best_tq;
 351 }
 352
 353 /* Return true if the vis packet is full. */
 354 static bool vis_packet_full(struct vis_info *info)
 355 {
 356         if (info->packet.entries + 1 >
 357             (1000 - sizeof(struct vis_info)) / sizeof(struct vis_info_entry))
 358                 return true;
 359         return false;
 360 }
 361
 362 /* generates a packet of own vis data,
 363  * returns 0 on success, -1 if no packet could be generated */
 364 static int generate_vis_packet(void)
 365 {
 366         HASHIT(hashit_local);
 367         HASHIT(hashit_global);
 368         struct orig_node *orig_node;
 369         struct vis_info *info = (struct vis_info *)my_vis_info;
 370         struct vis_info_entry *entry, *entry_array;
 371         struct hna_local_entry *hna_local_entry;
 372         int best_tq = -1;
 373         unsigned long flags;
 374
 375         info->first_seen = jiffies;
 376
 377         spin_lock_irqsave(&orig_hash_lock, flags);
 378         memcpy(info->packet.target_orig, broadcastAddr, ETH_ALEN);
 379         info->packet.ttl = TTL;
 380         info->packet.seqno++;
 381         info->packet.entries = 0;
 382
 383         if (!is_vis_server_locked()) {
 384                 best_tq = find_best_vis_server(info);
 385                 if (best_tq < 0) {
 386                         spin_unlock_irqrestore(&orig_hash_lock, flags);
 387                         return -1;
 388                 }
 389         }
 390
 391         entry_array = (struct vis_info_entry *)
 392                 ((char *)info + sizeof(struct vis_info));
 393
 394         while (hash_iterate(orig_hash, &hashit_global)) {
 395                 orig_node = hashit_global.bucket->data;
 396                 if (orig_node->router != NULL
 397                         && compare_orig(orig_node->router->addr, orig_node->orig)
 398                         && orig_node->batman_if
 399                         && (orig_node->batman_if->if_active == IF_ACTIVE)
 400                     && orig_node->router->tq_avg > 0) {
 401
 402                         /* fill one entry into buffer. */
 403                         entry = &entry_array[info->packet.entries];
 404                         memcpy(entry->src, orig_node->batman_if->net_dev->dev_addr, ETH_ALEN);
 405                         memcpy(entry->dest, orig_node->orig, ETH_ALEN);
 406                         entry->quality = orig_node->router->tq_avg;
 407                         info->packet.entries++;
 408
 409                         if (vis_packet_full(info)) {
 410                                 spin_unlock_irqrestore(&orig_hash_lock, flags);
 411                                 return 0;
 412                         }
 413                 }
 414         }
 415
 416         spin_unlock_irqrestore(&orig_hash_lock, flags);
 417
 418         spin_lock_irqsave(&hna_local_hash_lock, flags);
 419         while (hash_iterate(hna_local_hash, &hashit_local)) {
 420                 hna_local_entry = hashit_local.bucket->data;
 421                 entry = &entry_array[info->packet.entries];
 422                 memset(entry->src, 0, ETH_ALEN);
 423                 memcpy(entry->dest, hna_local_entry->addr, ETH_ALEN);
 424                 entry->quality = 0; /* 0 means HNA */
 425                 info->packet.entries++;
 426
 427                 if (vis_packet_full(info)) {
 428                         spin_unlock_irqrestore(&hna_local_hash_lock, flags);
 429                         return 0;
 430                 }
 431         }
 432         spin_unlock_irqrestore(&hna_local_hash_lock, flags);
 433         return 0;
 434 }
 435
 436 static void purge_vis_packets(void)
 437 {
 438         HASHIT(hashit);
 439         struct vis_info *info;
 440
 441         while (hash_iterate(vis_hash, &hashit)) {
 442                 info = hashit.bucket->data;
 443                 if (info == my_vis_info)        /* never purge own data. */
 444                         continue;
 445                 if (time_after(jiffies,
 446                                info->first_seen + (VIS_TIMEOUT*HZ)/1000)) {
 447                         hash_remove_bucket(vis_hash, &hashit);
 448                         free_info(info);
 449                 }
 450         }
 451 }
 452
 453 static void broadcast_vis_packet(struct vis_info *info, int packet_length)
 454 {
 455         HASHIT(hashit);
 456         struct orig_node *orig_node;
 457         unsigned long flags;
 458
 459         spin_lock_irqsave(&orig_hash_lock, flags);
 460
 461         /* send to all routers in range. */
 462         while (hash_iterate(orig_hash, &hashit)) {
 463                 orig_node = hashit.bucket->data;
 464
 465                 /* if it's a vis server and reachable, send it. */
 466                 if (orig_node &&
 467                     (orig_node->flags & VIS_SERVER) &&
 468                     orig_node->batman_if &&
 469                     orig_node->router) {
 470
 471                         /* don't send it if we already received the packet from
 472                          * this node. */
 473                         if (recv_list_is_in(&info->recv_list, orig_node->orig))
 474                                 continue;
 475
 476                         memcpy(info->packet.target_orig,
 477                                orig_node->orig, ETH_ALEN);
 478
 479                         send_raw_packet((unsigned char *) &info->packet,
 480                                         packet_length,
 481                                         orig_node->batman_if,
 482                                         orig_node->router->addr);
 483                 }
 484         }
 485         memcpy(info->packet.target_orig, broadcastAddr, ETH_ALEN);
 486         spin_unlock_irqrestore(&orig_hash_lock, flags);
 487 }
 488
 489 static void unicast_vis_packet(struct vis_info *info, int packet_length)
 490 {
 491         struct orig_node *orig_node;
 492         unsigned long flags;
 493
 494         spin_lock_irqsave(&orig_hash_lock, flags);
 495         orig_node = ((struct orig_node *)
 496                      hash_find(orig_hash, info->packet.target_orig));
 497
 498         if ((orig_node != NULL) &&
 499             (orig_node->batman_if != NULL) &&
 500             (orig_node->router != NULL)) {
 501                 send_raw_packet((unsigned char *) &info->packet, packet_length,
 502                                 orig_node->batman_if,
 503                                 orig_node->router->addr);
 504         }
 505         spin_unlock_irqrestore(&orig_hash_lock, flags);
 506 }
 507
 508 /* only send one vis packet. called from send_vis_packets() */
 509 static void send_vis_packet(struct vis_info *info)
 510 {
 511         int packet_length;
 512
 513         if (info->packet.ttl < 2) {
 514                 printk(KERN_WARNING "batman-adv: Error - can't send vis packet: ttl exceeded\n");
 515                 return;
 516         }
 517
 518         memcpy(info->packet.sender_orig, mainIfAddr, ETH_ALEN);
 519         info->packet.ttl--;
 520
 521         packet_length = sizeof(struct vis_packet) +
 522                 info->packet.entries * sizeof(struct vis_info_entry);
 523
 524         if (is_bcast(info->packet.target_orig))
 525                 broadcast_vis_packet(info, packet_length);
 526         else
 527                 unicast_vis_packet(info, packet_length);
 528         info->packet.ttl++; /* restore TTL */
 529 }
 530
 531 /* called from timer; send (and maybe generate) vis packet. */
 532 static void send_vis_packets(struct work_struct *work)
 533 {
 534         struct vis_info *info, *temp;
 535         unsigned long flags;
 536
 537         spin_lock_irqsave(&vis_hash_lock, flags);
 538         purge_vis_packets();
 539
 540         if (generate_vis_packet() == 0)
 541                 /* schedule if generation was successful */
 542                 list_add_tail(&my_vis_info->send_list, &send_list);
 543
 544         list_for_each_entry_safe(info, temp, &send_list, send_list) {
 545                 list_del_init(&info->send_list);
 546                 send_vis_packet(info);
 547         }
 548         spin_unlock_irqrestore(&vis_hash_lock, flags);
 549         start_vis_timer();
 550 }
 551 static DECLARE_DELAYED_WORK(vis_timer_wq, send_vis_packets);
 552
 553 /* init the vis server. this may only be called when if_list is already
 554  * initialized (e.g. bat0 is initialized, interfaces have been added) */
 555 int vis_init(void)
 556 {
 557         unsigned long flags;
 558         if (vis_hash)
 559                 return 1;
 560
 561         spin_lock_irqsave(&vis_hash_lock, flags);
 562
 563         vis_hash = hash_new(256, vis_info_cmp, vis_info_choose);
 564         if (!vis_hash) {
 565                 printk(KERN_ERR "batman-adv:Can't initialize vis_hash\n");
 566                 goto err;
 567         }
 568
 569         my_vis_info = kmalloc(1000, GFP_ATOMIC);
 570         if (!my_vis_info) {
 571                 printk(KERN_ERR "batman-adv:Can't initialize vis packet\n");
 572                 goto err;
 573         }
 574
 575         /* prefill the vis info */
 576         my_vis_info->first_seen = jiffies - atomic_read(&vis_interval);
 577         INIT_LIST_HEAD(&my_vis_info->recv_list);
 578         INIT_LIST_HEAD(&my_vis_info->send_list);
 579         my_vis_info->packet.version = COMPAT_VERSION;
 580         my_vis_info->packet.packet_type = BAT_VIS;
 581         my_vis_info->packet.vis_type = VIS_TYPE_CLIENT_UPDATE;
 582         my_vis_info->packet.ttl = TTL;
 583         my_vis_info->packet.seqno = 0;
 584         my_vis_info->packet.entries = 0;
 585
 586         INIT_LIST_HEAD(&send_list);
 587
 588         memcpy(my_vis_info->packet.vis_orig, mainIfAddr, ETH_ALEN);
 589         memcpy(my_vis_info->packet.sender_orig, mainIfAddr, ETH_ALEN);
 590
 591         if (hash_add(vis_hash, my_vis_info) < 0) {
 592                 printk(KERN_ERR
 593                           "batman-adv:Can't add own vis packet into hash\n");
 594                 free_info(my_vis_info); /* not in hash, need to remove it
 595                                          * manually. */
 596                 goto err;
 597         }
 598
 599         spin_unlock_irqrestore(&vis_hash_lock, flags);
 600         start_vis_timer();
 601         return 1;
 602
 603 err:
 604         spin_unlock_irqrestore(&vis_hash_lock, flags);
 605         vis_quit();
 606         return 0;
 607 }
 608
 609 /* shutdown vis-server */
 610 void vis_quit(void)
 611 {
 612         unsigned long flags;
 613         if (!vis_hash)
 614                 return;
 615
 616         cancel_delayed_work_sync(&vis_timer_wq);
 617
 618         spin_lock_irqsave(&vis_hash_lock, flags);
 619         /* properly remove, kill timers ... */
 620         hash_delete(vis_hash, free_info);
 621         vis_hash = NULL;
 622         my_vis_info = NULL;
 623         spin_unlock_irqrestore(&vis_hash_lock, flags);
 624 }
 625
 626 /* schedule packets for (re)transmission */
 627 static void start_vis_timer(void)
 628 {
 629         queue_delayed_work(bat_event_workqueue, &vis_timer_wq,
 630                            (atomic_read(&vis_interval) * HZ) / 1000);
 631 }
 632