1 /* 2 * Copyright (C) 2009-2011 B.A.T.M.A.N. contributors: 3 * 4 * Marek Lindner 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 "bat_sysfs.h" 24 #include "gateway_client.h" 25 #include "gateway_common.h" 26 #include "hard-interface.h" 27 #include "originator.h" 28 #include "translation-table.h" 29 #include "routing.h" 30 #include <linux/ip.h> 31 #include <linux/ipv6.h> 32 #include <linux/udp.h> 33 #include <linux/if_vlan.h> 34 35 /* This is the offset of the options field in a dhcp packet starting at 36 * the beginning of the dhcp header */ 37 #define DHCP_OPTIONS_OFFSET 240 38 #define DHCP_REQUEST 3 39 40 static void gw_node_free_ref(struct gw_node *gw_node) 41 { 42 if (atomic_dec_and_test(&gw_node->refcount)) 43 kfree_rcu(gw_node, rcu); 44 } 45 46 static struct gw_node *gw_get_selected_gw_node(struct bat_priv *bat_priv) 47 { 48 struct gw_node *gw_node; 49 50 rcu_read_lock(); 51 gw_node = rcu_dereference(bat_priv->curr_gw); 52 if (!gw_node) 53 goto out; 54 55 if (!atomic_inc_not_zero(&gw_node->refcount)) 56 gw_node = NULL; 57 58 out: 59 rcu_read_unlock(); 60 return gw_node; 61 } 62 63 struct orig_node *gw_get_selected_orig(struct bat_priv *bat_priv) 64 { 65 struct gw_node *gw_node; 66 struct orig_node *orig_node = NULL; 67 68 gw_node = gw_get_selected_gw_node(bat_priv); 69 if (!gw_node) 70 goto out; 71 72 rcu_read_lock(); 73 orig_node = gw_node->orig_node; 74 if (!orig_node) 75 goto unlock; 76 77 if (!atomic_inc_not_zero(&orig_node->refcount)) 78 orig_node = NULL; 79 80 unlock: 81 rcu_read_unlock(); 82 out: 83 if (gw_node) 84 gw_node_free_ref(gw_node); 85 return orig_node; 86 } 87 88 static void gw_select(struct bat_priv *bat_priv, struct gw_node *new_gw_node) 89 { 90 struct gw_node *curr_gw_node; 91 92 spin_lock_bh(&bat_priv->gw_list_lock); 93 94 if (new_gw_node && !atomic_inc_not_zero(&new_gw_node->refcount)) 95 new_gw_node = NULL; 96 97 curr_gw_node = rcu_dereference_protected(bat_priv->curr_gw, 1); 98 rcu_assign_pointer(bat_priv->curr_gw, new_gw_node); 99 100 if (curr_gw_node) 101 gw_node_free_ref(curr_gw_node); 102 103 spin_unlock_bh(&bat_priv->gw_list_lock); 104 } 105 106 void gw_deselect(struct bat_priv *bat_priv) 107 { 108 atomic_set(&bat_priv->gw_reselect, 1); 109 } 110 111 static struct gw_node *gw_get_best_gw_node(struct bat_priv *bat_priv) 112 { 113 struct neigh_node *router; 114 struct hlist_node *node; 115 struct gw_node *gw_node, *curr_gw = NULL; 116 uint32_t max_gw_factor = 0, tmp_gw_factor = 0; 117 uint8_t max_tq = 0; 118 int down, up; 119 120 rcu_read_lock(); 121 hlist_for_each_entry_rcu(gw_node, node, &bat_priv->gw_list, list) { 122 if (gw_node->deleted) 123 continue; 124 125 router = orig_node_get_router(gw_node->orig_node); 126 if (!router) 127 continue; 128 129 if (!atomic_inc_not_zero(&gw_node->refcount)) 130 goto next; 131 132 switch (atomic_read(&bat_priv->gw_sel_class)) { 133 case 1: /* fast connection */ 134 gw_bandwidth_to_kbit(gw_node->orig_node->gw_flags, 135 &down, &up); 136 137 tmp_gw_factor = (router->tq_avg * router->tq_avg * 138 down * 100 * 100) / 139 (TQ_LOCAL_WINDOW_SIZE * 140 TQ_LOCAL_WINDOW_SIZE * 64); 141 142 if ((tmp_gw_factor > max_gw_factor) || 143 ((tmp_gw_factor == max_gw_factor) && 144 (router->tq_avg > max_tq))) { 145 if (curr_gw) 146 gw_node_free_ref(curr_gw); 147 curr_gw = gw_node; 148 atomic_inc(&curr_gw->refcount); 149 } 150 break; 151 152 default: /** 153 * 2: stable connection (use best statistic) 154 * 3: fast-switch (use best statistic but change as 155 * soon as a better gateway appears) 156 * XX: late-switch (use best statistic but change as 157 * soon as a better gateway appears which has 158 * $routing_class more tq points) 159 **/ 160 if (router->tq_avg > max_tq) { 161 if (curr_gw) 162 gw_node_free_ref(curr_gw); 163 curr_gw = gw_node; 164 atomic_inc(&curr_gw->refcount); 165 } 166 break; 167 } 168 169 if (router->tq_avg > max_tq) 170 max_tq = router->tq_avg; 171 172 if (tmp_gw_factor > max_gw_factor) 173 max_gw_factor = tmp_gw_factor; 174 175 gw_node_free_ref(gw_node); 176 177 next: 178 neigh_node_free_ref(router); 179 } 180 rcu_read_unlock(); 181 182 return curr_gw; 183 } 184 185 void gw_election(struct bat_priv *bat_priv) 186 { 187 struct gw_node *curr_gw = NULL, *next_gw = NULL; 188 struct neigh_node *router = NULL; 189 char gw_addr[18] = { '\0' }; 190 191 /** 192 * The batman daemon checks here if we already passed a full originator 193 * cycle in order to make sure we don't choose the first gateway we 194 * hear about. This check is based on the daemon's uptime which we 195 * don't have. 196 **/ 197 if (atomic_read(&bat_priv->gw_mode) != GW_MODE_CLIENT) 198 goto out; 199 200 if (!atomic_dec_not_zero(&bat_priv->gw_reselect)) 201 goto out; 202 203 curr_gw = gw_get_selected_gw_node(bat_priv); 204 205 next_gw = gw_get_best_gw_node(bat_priv); 206 207 if (curr_gw == next_gw) 208 goto out; 209 210 if (next_gw) { 211 sprintf(gw_addr, "%pM", next_gw->orig_node->orig); 212 213 router = orig_node_get_router(next_gw->orig_node); 214 if (!router) { 215 gw_deselect(bat_priv); 216 goto out; 217 } 218 } 219 220 if ((curr_gw) && (!next_gw)) { 221 bat_dbg(DBG_BATMAN, bat_priv, 222 "Removing selected gateway - no gateway in range\n"); 223 throw_uevent(bat_priv, UEV_GW, UEV_DEL, NULL); 224 } else if ((!curr_gw) && (next_gw)) { 225 bat_dbg(DBG_BATMAN, bat_priv, 226 "Adding route to gateway %pM (gw_flags: %i, tq: %i)\n", 227 next_gw->orig_node->orig, 228 next_gw->orig_node->gw_flags, 229 router->tq_avg); 230 throw_uevent(bat_priv, UEV_GW, UEV_ADD, gw_addr); 231 } else { 232 bat_dbg(DBG_BATMAN, bat_priv, 233 "Changing route to gateway %pM " 234 "(gw_flags: %i, tq: %i)\n", 235 next_gw->orig_node->orig, 236 next_gw->orig_node->gw_flags, 237 router->tq_avg); 238 throw_uevent(bat_priv, UEV_GW, UEV_CHANGE, gw_addr); 239 } 240 241 gw_select(bat_priv, next_gw); 242 243 out: 244 if (curr_gw) 245 gw_node_free_ref(curr_gw); 246 if (next_gw) 247 gw_node_free_ref(next_gw); 248 if (router) 249 neigh_node_free_ref(router); 250 } 251 252 void gw_check_election(struct bat_priv *bat_priv, struct orig_node *orig_node) 253 { 254 struct orig_node *curr_gw_orig; 255 struct neigh_node *router_gw = NULL, *router_orig = NULL; 256 uint8_t gw_tq_avg, orig_tq_avg; 257 258 curr_gw_orig = gw_get_selected_orig(bat_priv); 259 if (!curr_gw_orig) 260 goto deselect; 261 262 router_gw = orig_node_get_router(curr_gw_orig); 263 if (!router_gw) 264 goto deselect; 265 266 /* this node already is the gateway */ 267 if (curr_gw_orig == orig_node) 268 goto out; 269 270 router_orig = orig_node_get_router(orig_node); 271 if (!router_orig) 272 goto out; 273 274 gw_tq_avg = router_gw->tq_avg; 275 orig_tq_avg = router_orig->tq_avg; 276 277 /* the TQ value has to be better */ 278 if (orig_tq_avg < gw_tq_avg) 279 goto out; 280 281 /** 282 * if the routing class is greater than 3 the value tells us how much 283 * greater the TQ value of the new gateway must be 284 **/ 285 if ((atomic_read(&bat_priv->gw_sel_class) > 3) && 286 (orig_tq_avg - gw_tq_avg < atomic_read(&bat_priv->gw_sel_class))) 287 goto out; 288 289 bat_dbg(DBG_BATMAN, bat_priv, 290 "Restarting gateway selection: better gateway found (tq curr: " 291 "%i, tq new: %i)\n", 292 gw_tq_avg, orig_tq_avg); 293 294 deselect: 295 gw_deselect(bat_priv); 296 out: 297 if (curr_gw_orig) 298 orig_node_free_ref(curr_gw_orig); 299 if (router_gw) 300 neigh_node_free_ref(router_gw); 301 if (router_orig) 302 neigh_node_free_ref(router_orig); 303 304 return; 305 } 306 307 static void gw_node_add(struct bat_priv *bat_priv, 308 struct orig_node *orig_node, uint8_t new_gwflags) 309 { 310 struct gw_node *gw_node; 311 int down, up; 312 313 gw_node = kzalloc(sizeof(*gw_node), GFP_ATOMIC); 314 if (!gw_node) 315 return; 316 317 INIT_HLIST_NODE(&gw_node->list); 318 gw_node->orig_node = orig_node; 319 atomic_set(&gw_node->refcount, 1); 320 321 spin_lock_bh(&bat_priv->gw_list_lock); 322 hlist_add_head_rcu(&gw_node->list, &bat_priv->gw_list); 323 spin_unlock_bh(&bat_priv->gw_list_lock); 324 325 gw_bandwidth_to_kbit(new_gwflags, &down, &up); 326 bat_dbg(DBG_BATMAN, bat_priv, 327 "Found new gateway %pM -> gw_class: %i - %i%s/%i%s\n", 328 orig_node->orig, new_gwflags, 329 (down > 2048 ? down / 1024 : down), 330 (down > 2048 ? "MBit" : "KBit"), 331 (up > 2048 ? up / 1024 : up), 332 (up > 2048 ? "MBit" : "KBit")); 333 } 334 335 void gw_node_update(struct bat_priv *bat_priv, 336 struct orig_node *orig_node, uint8_t new_gwflags) 337 { 338 struct hlist_node *node; 339 struct gw_node *gw_node, *curr_gw; 340 341 /** 342 * Note: We don't need a NULL check here, since curr_gw never gets 343 * dereferenced. If curr_gw is NULL we also should not exit as we may 344 * have this gateway in our list (duplication check!) even though we 345 * have no currently selected gateway. 346 */ 347 curr_gw = gw_get_selected_gw_node(bat_priv); 348 349 rcu_read_lock(); 350 hlist_for_each_entry_rcu(gw_node, node, &bat_priv->gw_list, list) { 351 if (gw_node->orig_node != orig_node) 352 continue; 353 354 bat_dbg(DBG_BATMAN, bat_priv, 355 "Gateway class of originator %pM changed from " 356 "%i to %i\n", 357 orig_node->orig, gw_node->orig_node->gw_flags, 358 new_gwflags); 359 360 gw_node->deleted = 0; 361 362 if (new_gwflags == NO_FLAGS) { 363 gw_node->deleted = jiffies; 364 bat_dbg(DBG_BATMAN, bat_priv, 365 "Gateway %pM removed from gateway list\n", 366 orig_node->orig); 367 368 if (gw_node == curr_gw) 369 goto deselect; 370 } 371 372 goto unlock; 373 } 374 375 if (new_gwflags == NO_FLAGS) 376 goto unlock; 377 378 gw_node_add(bat_priv, orig_node, new_gwflags); 379 goto unlock; 380 381 deselect: 382 gw_deselect(bat_priv); 383 unlock: 384 rcu_read_unlock(); 385 386 if (curr_gw) 387 gw_node_free_ref(curr_gw); 388 } 389 390 void gw_node_delete(struct bat_priv *bat_priv, struct orig_node *orig_node) 391 { 392 gw_node_update(bat_priv, orig_node, 0); 393 } 394 395 void gw_node_purge(struct bat_priv *bat_priv) 396 { 397 struct gw_node *gw_node, *curr_gw; 398 struct hlist_node *node, *node_tmp; 399 unsigned long timeout = 2 * PURGE_TIMEOUT * HZ; 400 int do_deselect = 0; 401 402 curr_gw = gw_get_selected_gw_node(bat_priv); 403 404 spin_lock_bh(&bat_priv->gw_list_lock); 405 406 hlist_for_each_entry_safe(gw_node, node, node_tmp, 407 &bat_priv->gw_list, list) { 408 if (((!gw_node->deleted) || 409 (time_before(jiffies, gw_node->deleted + timeout))) && 410 atomic_read(&bat_priv->mesh_state) == MESH_ACTIVE) 411 continue; 412 413 if (curr_gw == gw_node) 414 do_deselect = 1; 415 416 hlist_del_rcu(&gw_node->list); 417 gw_node_free_ref(gw_node); 418 } 419 420 spin_unlock_bh(&bat_priv->gw_list_lock); 421 422 /* gw_deselect() needs to acquire the gw_list_lock */ 423 if (do_deselect) 424 gw_deselect(bat_priv); 425 426 if (curr_gw) 427 gw_node_free_ref(curr_gw); 428 } 429 430 /** 431 * fails if orig_node has no router 432 */ 433 static int _write_buffer_text(struct bat_priv *bat_priv, struct seq_file *seq, 434 const struct gw_node *gw_node) 435 { 436 struct gw_node *curr_gw; 437 struct neigh_node *router; 438 int down, up, ret = -1; 439 440 gw_bandwidth_to_kbit(gw_node->orig_node->gw_flags, &down, &up); 441 442 router = orig_node_get_router(gw_node->orig_node); 443 if (!router) 444 goto out; 445 446 curr_gw = gw_get_selected_gw_node(bat_priv); 447 448 ret = seq_printf(seq, "%s %pM (%3i) %pM [%10s]: %3i - %i%s/%i%s\n", 449 (curr_gw == gw_node ? "=>" : " "), 450 gw_node->orig_node->orig, 451 router->tq_avg, router->addr, 452 router->if_incoming->net_dev->name, 453 gw_node->orig_node->gw_flags, 454 (down > 2048 ? down / 1024 : down), 455 (down > 2048 ? "MBit" : "KBit"), 456 (up > 2048 ? up / 1024 : up), 457 (up > 2048 ? "MBit" : "KBit")); 458 459 neigh_node_free_ref(router); 460 if (curr_gw) 461 gw_node_free_ref(curr_gw); 462 out: 463 return ret; 464 } 465 466 int gw_client_seq_print_text(struct seq_file *seq, void *offset) 467 { 468 struct net_device *net_dev = (struct net_device *)seq->private; 469 struct bat_priv *bat_priv = netdev_priv(net_dev); 470 struct hard_iface *primary_if; 471 struct gw_node *gw_node; 472 struct hlist_node *node; 473 int gw_count = 0, ret = 0; 474 475 primary_if = primary_if_get_selected(bat_priv); 476 if (!primary_if) { 477 ret = seq_printf(seq, "BATMAN mesh %s disabled - please " 478 "specify interfaces to enable it\n", 479 net_dev->name); 480 goto out; 481 } 482 483 if (primary_if->if_status != IF_ACTIVE) { 484 ret = seq_printf(seq, "BATMAN mesh %s disabled - " 485 "primary interface not active\n", 486 net_dev->name); 487 goto out; 488 } 489 490 seq_printf(seq, " %-12s (%s/%i) %17s [%10s]: gw_class ... " 491 "[B.A.T.M.A.N. adv %s, MainIF/MAC: %s/%pM (%s)]\n", 492 "Gateway", "#", TQ_MAX_VALUE, "Nexthop", 493 "outgoingIF", SOURCE_VERSION, primary_if->net_dev->name, 494 primary_if->net_dev->dev_addr, net_dev->name); 495 496 rcu_read_lock(); 497 hlist_for_each_entry_rcu(gw_node, node, &bat_priv->gw_list, list) { 498 if (gw_node->deleted) 499 continue; 500 501 /* fails if orig_node has no router */ 502 if (_write_buffer_text(bat_priv, seq, gw_node) < 0) 503 continue; 504 505 gw_count++; 506 } 507 rcu_read_unlock(); 508 509 if (gw_count == 0) 510 seq_printf(seq, "No gateways in range ...\n"); 511 512 out: 513 if (primary_if) 514 hardif_free_ref(primary_if); 515 return ret; 516 } 517 518 static bool is_type_dhcprequest(struct sk_buff *skb, int header_len) 519 { 520 int ret = false; 521 unsigned char *p; 522 int pkt_len; 523 524 if (skb_linearize(skb) < 0) 525 goto out; 526 527 pkt_len = skb_headlen(skb); 528 529 if (pkt_len < header_len + DHCP_OPTIONS_OFFSET + 1) 530 goto out; 531 532 p = skb->data + header_len + DHCP_OPTIONS_OFFSET; 533 pkt_len -= header_len + DHCP_OPTIONS_OFFSET + 1; 534 535 /* Access the dhcp option lists. Each entry is made up by: 536 * - octet 1: option type 537 * - octet 2: option data len (only if type != 255 and 0) 538 * - octet 3: option data */ 539 while (*p != 255 && !ret) { 540 /* p now points to the first octet: option type */ 541 if (*p == 53) { 542 /* type 53 is the message type option. 543 * Jump the len octet and go to the data octet */ 544 if (pkt_len < 2) 545 goto out; 546 p += 2; 547 548 /* check if the message type is what we need */ 549 if (*p == DHCP_REQUEST) 550 ret = true; 551 break; 552 } else if (*p == 0) { 553 /* option type 0 (padding), just go forward */ 554 if (pkt_len < 1) 555 goto out; 556 pkt_len--; 557 p++; 558 } else { 559 /* This is any other option. So we get the length... */ 560 if (pkt_len < 1) 561 goto out; 562 pkt_len--; 563 p++; 564 565 /* ...and then we jump over the data */ 566 if (pkt_len < *p) 567 goto out; 568 pkt_len -= *p; 569 p += (*p); 570 } 571 } 572 out: 573 return ret; 574 } 575 576 bool gw_is_dhcp_target(struct sk_buff *skb, unsigned int *header_len) 577 { 578 struct ethhdr *ethhdr; 579 struct iphdr *iphdr; 580 struct ipv6hdr *ipv6hdr; 581 struct udphdr *udphdr; 582 583 /* check for ethernet header */ 584 if (!pskb_may_pull(skb, *header_len + ETH_HLEN)) 585 return false; 586 ethhdr = (struct ethhdr *)skb->data; 587 *header_len += ETH_HLEN; 588 589 /* check for initial vlan header */ 590 if (ntohs(ethhdr->h_proto) == ETH_P_8021Q) { 591 if (!pskb_may_pull(skb, *header_len + VLAN_HLEN)) 592 return false; 593 ethhdr = (struct ethhdr *)(skb->data + VLAN_HLEN); 594 *header_len += VLAN_HLEN; 595 } 596 597 /* check for ip header */ 598 switch (ntohs(ethhdr->h_proto)) { 599 case ETH_P_IP: 600 if (!pskb_may_pull(skb, *header_len + sizeof(*iphdr))) 601 return false; 602 iphdr = (struct iphdr *)(skb->data + *header_len); 603 *header_len += iphdr->ihl * 4; 604 605 /* check for udp header */ 606 if (iphdr->protocol != IPPROTO_UDP) 607 return false; 608 609 break; 610 case ETH_P_IPV6: 611 if (!pskb_may_pull(skb, *header_len + sizeof(*ipv6hdr))) 612 return false; 613 ipv6hdr = (struct ipv6hdr *)(skb->data + *header_len); 614 *header_len += sizeof(*ipv6hdr); 615 616 /* check for udp header */ 617 if (ipv6hdr->nexthdr != IPPROTO_UDP) 618 return false; 619 620 break; 621 default: 622 return false; 623 } 624 625 if (!pskb_may_pull(skb, *header_len + sizeof(*udphdr))) 626 return false; 627 udphdr = (struct udphdr *)(skb->data + *header_len); 628 *header_len += sizeof(*udphdr); 629 630 /* check for bootp port */ 631 if ((ntohs(ethhdr->h_proto) == ETH_P_IP) && 632 (ntohs(udphdr->dest) != 67)) 633 return false; 634 635 if ((ntohs(ethhdr->h_proto) == ETH_P_IPV6) && 636 (ntohs(udphdr->dest) != 547)) 637 return false; 638 639 return true; 640 } 641 642 bool gw_out_of_range(struct bat_priv *bat_priv, 643 struct sk_buff *skb, struct ethhdr *ethhdr) 644 { 645 struct neigh_node *neigh_curr = NULL, *neigh_old = NULL; 646 struct orig_node *orig_dst_node = NULL; 647 struct gw_node *curr_gw = NULL; 648 bool ret, out_of_range = false; 649 unsigned int header_len = 0; 650 uint8_t curr_tq_avg; 651 652 ret = gw_is_dhcp_target(skb, &header_len); 653 if (!ret) 654 goto out; 655 656 orig_dst_node = transtable_search(bat_priv, ethhdr->h_source, 657 ethhdr->h_dest); 658 if (!orig_dst_node) 659 goto out; 660 661 if (!orig_dst_node->gw_flags) 662 goto out; 663 664 ret = is_type_dhcprequest(skb, header_len); 665 if (!ret) 666 goto out; 667 668 switch (atomic_read(&bat_priv->gw_mode)) { 669 case GW_MODE_SERVER: 670 /* If we are a GW then we are our best GW. We can artificially 671 * set the tq towards ourself as the maximum value */ 672 curr_tq_avg = TQ_MAX_VALUE; 673 break; 674 case GW_MODE_CLIENT: 675 curr_gw = gw_get_selected_gw_node(bat_priv); 676 if (!curr_gw) 677 goto out; 678 679 /* packet is going to our gateway */ 680 if (curr_gw->orig_node == orig_dst_node) 681 goto out; 682 683 /* If the dhcp packet has been sent to a different gw, 684 * we have to evaluate whether the old gw is still 685 * reliable enough */ 686 neigh_curr = find_router(bat_priv, curr_gw->orig_node, NULL); 687 if (!neigh_curr) 688 goto out; 689 690 curr_tq_avg = neigh_curr->tq_avg; 691 break; 692 case GW_MODE_OFF: 693 default: 694 goto out; 695 } 696 697 neigh_old = find_router(bat_priv, orig_dst_node, NULL); 698 if (!neigh_old) 699 goto out; 700 701 if (curr_tq_avg - neigh_old->tq_avg > GW_THRESHOLD) 702 out_of_range = true; 703 704 out: 705 if (orig_dst_node) 706 orig_node_free_ref(orig_dst_node); 707 if (curr_gw) 708 gw_node_free_ref(curr_gw); 709 if (neigh_old) 710 neigh_node_free_ref(neigh_old); 711 if (neigh_curr) 712 neigh_node_free_ref(neigh_curr); 713 return out_of_range; 714 } 715