network-coding.c revision 953324776d6d23eb81f5b825870027b9c069db29
1/* Copyright (C) 2012-2013 B.A.T.M.A.N. contributors: 2 * 3 * Martin Hundebøll, Jeppe Ledet-Pedersen 4 * 5 * This program is free software; you can redistribute it and/or 6 * modify it under the terms of version 2 of the GNU General Public 7 * License as published by the Free Software Foundation. 8 * 9 * This program is distributed in the hope that it will be useful, but 10 * WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 12 * General Public License for more details. 13 * 14 * You should have received a copy of the GNU General Public License 15 * along with this program; if not, write to the Free Software 16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 17 * 02110-1301, USA 18 */ 19 20#include <linux/debugfs.h> 21 22#include "main.h" 23#include "hash.h" 24#include "network-coding.h" 25#include "send.h" 26#include "originator.h" 27#include "hard-interface.h" 28 29static struct lock_class_key batadv_nc_coding_hash_lock_class_key; 30 31static void batadv_nc_worker(struct work_struct *work); 32 33/** 34 * batadv_nc_start_timer - initialise the nc periodic worker 35 * @bat_priv: the bat priv with all the soft interface information 36 */ 37static void batadv_nc_start_timer(struct batadv_priv *bat_priv) 38{ 39 queue_delayed_work(batadv_event_workqueue, &bat_priv->nc.work, 40 msecs_to_jiffies(10)); 41} 42 43/** 44 * batadv_nc_init - initialise coding hash table and start house keeping 45 * @bat_priv: the bat priv with all the soft interface information 46 */ 47int batadv_nc_init(struct batadv_priv *bat_priv) 48{ 49 bat_priv->nc.timestamp_fwd_flush = jiffies; 50 51 if (bat_priv->nc.coding_hash) 52 return 0; 53 54 bat_priv->nc.coding_hash = batadv_hash_new(128); 55 if (!bat_priv->nc.coding_hash) 56 goto err; 57 58 batadv_hash_set_lock_class(bat_priv->nc.coding_hash, 59 &batadv_nc_coding_hash_lock_class_key); 60 61 INIT_DELAYED_WORK(&bat_priv->nc.work, batadv_nc_worker); 62 batadv_nc_start_timer(bat_priv); 63 64 return 0; 65 66err: 67 return -ENOMEM; 68} 69 70/** 71 * batadv_nc_init_bat_priv - initialise the nc specific bat_priv variables 72 * @bat_priv: the bat priv with all the soft interface information 73 */ 74void batadv_nc_init_bat_priv(struct batadv_priv *bat_priv) 75{ 76 atomic_set(&bat_priv->network_coding, 1); 77 bat_priv->nc.min_tq = 200; 78 bat_priv->nc.max_fwd_delay = 10; 79} 80 81/** 82 * batadv_nc_init_orig - initialise the nc fields of an orig_node 83 * @orig_node: the orig_node which is going to be initialised 84 */ 85void batadv_nc_init_orig(struct batadv_orig_node *orig_node) 86{ 87 INIT_LIST_HEAD(&orig_node->in_coding_list); 88 INIT_LIST_HEAD(&orig_node->out_coding_list); 89 spin_lock_init(&orig_node->in_coding_list_lock); 90 spin_lock_init(&orig_node->out_coding_list_lock); 91} 92 93/** 94 * batadv_nc_node_free_rcu - rcu callback to free an nc node and remove 95 * its refcount on the orig_node 96 * @rcu: rcu pointer of the nc node 97 */ 98static void batadv_nc_node_free_rcu(struct rcu_head *rcu) 99{ 100 struct batadv_nc_node *nc_node; 101 102 nc_node = container_of(rcu, struct batadv_nc_node, rcu); 103 batadv_orig_node_free_ref(nc_node->orig_node); 104 kfree(nc_node); 105} 106 107/** 108 * batadv_nc_node_free_ref - decrements the nc node refcounter and possibly 109 * frees it 110 * @nc_node: the nc node to free 111 */ 112static void batadv_nc_node_free_ref(struct batadv_nc_node *nc_node) 113{ 114 if (atomic_dec_and_test(&nc_node->refcount)) 115 call_rcu(&nc_node->rcu, batadv_nc_node_free_rcu); 116} 117 118/** 119 * batadv_nc_path_free_ref - decrements the nc path refcounter and possibly 120 * frees it 121 * @nc_path: the nc node to free 122 */ 123static void batadv_nc_path_free_ref(struct batadv_nc_path *nc_path) 124{ 125 if (atomic_dec_and_test(&nc_path->refcount)) 126 kfree_rcu(nc_path, rcu); 127} 128 129/** 130 * batadv_nc_packet_free - frees nc packet 131 * @nc_packet: the nc packet to free 132 */ 133static void batadv_nc_packet_free(struct batadv_nc_packet *nc_packet) 134{ 135 if (nc_packet->skb) 136 kfree_skb(nc_packet->skb); 137 138 batadv_nc_path_free_ref(nc_packet->nc_path); 139 kfree(nc_packet); 140} 141 142/** 143 * batadv_nc_to_purge_nc_node - checks whether an nc node has to be purged 144 * @bat_priv: the bat priv with all the soft interface information 145 * @nc_node: the nc node to check 146 * 147 * Returns true if the entry has to be purged now, false otherwise 148 */ 149static bool batadv_nc_to_purge_nc_node(struct batadv_priv *bat_priv, 150 struct batadv_nc_node *nc_node) 151{ 152 if (atomic_read(&bat_priv->mesh_state) != BATADV_MESH_ACTIVE) 153 return true; 154 155 return batadv_has_timed_out(nc_node->last_seen, BATADV_NC_NODE_TIMEOUT); 156} 157 158/** 159 * batadv_nc_to_purge_nc_path_coding - checks whether an nc path has timed out 160 * @bat_priv: the bat priv with all the soft interface information 161 * @nc_path: the nc path to check 162 * 163 * Returns true if the entry has to be purged now, false otherwise 164 */ 165static bool batadv_nc_to_purge_nc_path_coding(struct batadv_priv *bat_priv, 166 struct batadv_nc_path *nc_path) 167{ 168 if (atomic_read(&bat_priv->mesh_state) != BATADV_MESH_ACTIVE) 169 return true; 170 171 /* purge the path when no packets has been added for 10 times the 172 * max_fwd_delay time 173 */ 174 return batadv_has_timed_out(nc_path->last_valid, 175 bat_priv->nc.max_fwd_delay * 10); 176} 177 178/** 179 * batadv_nc_purge_orig_nc_nodes - go through list of nc nodes and purge stale 180 * entries 181 * @bat_priv: the bat priv with all the soft interface information 182 * @list: list of nc nodes 183 * @lock: nc node list lock 184 * @to_purge: function in charge to decide whether an entry has to be purged or 185 * not. This function takes the nc node as argument and has to return 186 * a boolean value: true if the entry has to be deleted, false 187 * otherwise 188 */ 189static void 190batadv_nc_purge_orig_nc_nodes(struct batadv_priv *bat_priv, 191 struct list_head *list, 192 spinlock_t *lock, 193 bool (*to_purge)(struct batadv_priv *, 194 struct batadv_nc_node *)) 195{ 196 struct batadv_nc_node *nc_node, *nc_node_tmp; 197 198 /* For each nc_node in list */ 199 spin_lock_bh(lock); 200 list_for_each_entry_safe(nc_node, nc_node_tmp, list, list) { 201 /* if an helper function has been passed as parameter, 202 * ask it if the entry has to be purged or not 203 */ 204 if (to_purge && !to_purge(bat_priv, nc_node)) 205 continue; 206 207 batadv_dbg(BATADV_DBG_NC, bat_priv, 208 "Removing nc_node %pM -> %pM\n", 209 nc_node->addr, nc_node->orig_node->orig); 210 list_del_rcu(&nc_node->list); 211 batadv_nc_node_free_ref(nc_node); 212 } 213 spin_unlock_bh(lock); 214} 215 216/** 217 * batadv_nc_purge_orig - purges all nc node data attached of the given 218 * originator 219 * @bat_priv: the bat priv with all the soft interface information 220 * @orig_node: orig_node with the nc node entries to be purged 221 * @to_purge: function in charge to decide whether an entry has to be purged or 222 * not. This function takes the nc node as argument and has to return 223 * a boolean value: true is the entry has to be deleted, false 224 * otherwise 225 */ 226void batadv_nc_purge_orig(struct batadv_priv *bat_priv, 227 struct batadv_orig_node *orig_node, 228 bool (*to_purge)(struct batadv_priv *, 229 struct batadv_nc_node *)) 230{ 231 /* Check ingoing nc_node's of this orig_node */ 232 batadv_nc_purge_orig_nc_nodes(bat_priv, &orig_node->in_coding_list, 233 &orig_node->in_coding_list_lock, 234 to_purge); 235 236 /* Check outgoing nc_node's of this orig_node */ 237 batadv_nc_purge_orig_nc_nodes(bat_priv, &orig_node->out_coding_list, 238 &orig_node->out_coding_list_lock, 239 to_purge); 240} 241 242/** 243 * batadv_nc_purge_orig_hash - traverse entire originator hash to check if they 244 * have timed out nc nodes 245 * @bat_priv: the bat priv with all the soft interface information 246 */ 247static void batadv_nc_purge_orig_hash(struct batadv_priv *bat_priv) 248{ 249 struct batadv_hashtable *hash = bat_priv->orig_hash; 250 struct hlist_head *head; 251 struct batadv_orig_node *orig_node; 252 uint32_t i; 253 254 if (!hash) 255 return; 256 257 /* For each orig_node */ 258 for (i = 0; i < hash->size; i++) { 259 head = &hash->table[i]; 260 261 rcu_read_lock(); 262 hlist_for_each_entry_rcu(orig_node, head, hash_entry) 263 batadv_nc_purge_orig(bat_priv, orig_node, 264 batadv_nc_to_purge_nc_node); 265 rcu_read_unlock(); 266 } 267} 268 269/** 270 * batadv_nc_purge_paths - traverse all nc paths part of the hash and remove 271 * unused ones 272 * @bat_priv: the bat priv with all the soft interface information 273 * @hash: hash table containing the nc paths to check 274 * @to_purge: function in charge to decide whether an entry has to be purged or 275 * not. This function takes the nc node as argument and has to return 276 * a boolean value: true is the entry has to be deleted, false 277 * otherwise 278 */ 279static void batadv_nc_purge_paths(struct batadv_priv *bat_priv, 280 struct batadv_hashtable *hash, 281 bool (*to_purge)(struct batadv_priv *, 282 struct batadv_nc_path *)) 283{ 284 struct hlist_head *head; 285 struct hlist_node *node_tmp; 286 struct batadv_nc_path *nc_path; 287 spinlock_t *lock; /* Protects lists in hash */ 288 uint32_t i; 289 290 for (i = 0; i < hash->size; i++) { 291 head = &hash->table[i]; 292 lock = &hash->list_locks[i]; 293 294 /* For each nc_path in this bin */ 295 spin_lock_bh(lock); 296 hlist_for_each_entry_safe(nc_path, node_tmp, head, hash_entry) { 297 /* if an helper function has been passed as parameter, 298 * ask it if the entry has to be purged or not 299 */ 300 if (to_purge && !to_purge(bat_priv, nc_path)) 301 continue; 302 303 /* purging an non-empty nc_path should never happen, but 304 * is observed under high CPU load. Delay the purging 305 * until next iteration to allow the packet_list to be 306 * emptied first. 307 */ 308 if (!unlikely(list_empty(&nc_path->packet_list))) { 309 net_ratelimited_function(printk, 310 KERN_WARNING 311 "Skipping free of non-empty nc_path (%pM -> %pM)!\n", 312 nc_path->prev_hop, 313 nc_path->next_hop); 314 continue; 315 } 316 317 /* nc_path is unused, so remove it */ 318 batadv_dbg(BATADV_DBG_NC, bat_priv, 319 "Remove nc_path %pM -> %pM\n", 320 nc_path->prev_hop, nc_path->next_hop); 321 hlist_del_rcu(&nc_path->hash_entry); 322 batadv_nc_path_free_ref(nc_path); 323 } 324 spin_unlock_bh(lock); 325 } 326} 327 328/** 329 * batadv_nc_hash_key_gen - computes the nc_path hash key 330 * @key: buffer to hold the final hash key 331 * @src: source ethernet mac address going into the hash key 332 * @dst: destination ethernet mac address going into the hash key 333 */ 334static void batadv_nc_hash_key_gen(struct batadv_nc_path *key, const char *src, 335 const char *dst) 336{ 337 memcpy(key->prev_hop, src, sizeof(key->prev_hop)); 338 memcpy(key->next_hop, dst, sizeof(key->next_hop)); 339} 340 341/** 342 * batadv_nc_hash_choose - compute the hash value for an nc path 343 * @data: data to hash 344 * @size: size of the hash table 345 * 346 * Returns the selected index in the hash table for the given data. 347 */ 348static uint32_t batadv_nc_hash_choose(const void *data, uint32_t size) 349{ 350 const struct batadv_nc_path *nc_path = data; 351 uint32_t hash = 0; 352 353 hash = batadv_hash_bytes(hash, &nc_path->prev_hop, 354 sizeof(nc_path->prev_hop)); 355 hash = batadv_hash_bytes(hash, &nc_path->next_hop, 356 sizeof(nc_path->next_hop)); 357 358 hash += (hash << 3); 359 hash ^= (hash >> 11); 360 hash += (hash << 15); 361 362 return hash % size; 363} 364 365/** 366 * batadv_nc_hash_compare - comparing function used in the network coding hash 367 * tables 368 * @node: node in the local table 369 * @data2: second object to compare the node to 370 * 371 * Returns 1 if the two entry are the same, 0 otherwise 372 */ 373static int batadv_nc_hash_compare(const struct hlist_node *node, 374 const void *data2) 375{ 376 const struct batadv_nc_path *nc_path1, *nc_path2; 377 378 nc_path1 = container_of(node, struct batadv_nc_path, hash_entry); 379 nc_path2 = data2; 380 381 /* Return 1 if the two keys are identical */ 382 if (memcmp(nc_path1->prev_hop, nc_path2->prev_hop, 383 sizeof(nc_path1->prev_hop)) != 0) 384 return 0; 385 386 if (memcmp(nc_path1->next_hop, nc_path2->next_hop, 387 sizeof(nc_path1->next_hop)) != 0) 388 return 0; 389 390 return 1; 391} 392 393/** 394 * batadv_nc_hash_find - search for an existing nc path and return it 395 * @hash: hash table containing the nc path 396 * @data: search key 397 * 398 * Returns the nc_path if found, NULL otherwise. 399 */ 400static struct batadv_nc_path * 401batadv_nc_hash_find(struct batadv_hashtable *hash, 402 void *data) 403{ 404 struct hlist_head *head; 405 struct batadv_nc_path *nc_path, *nc_path_tmp = NULL; 406 int index; 407 408 if (!hash) 409 return NULL; 410 411 index = batadv_nc_hash_choose(data, hash->size); 412 head = &hash->table[index]; 413 414 rcu_read_lock(); 415 hlist_for_each_entry_rcu(nc_path, head, hash_entry) { 416 if (!batadv_nc_hash_compare(&nc_path->hash_entry, data)) 417 continue; 418 419 if (!atomic_inc_not_zero(&nc_path->refcount)) 420 continue; 421 422 nc_path_tmp = nc_path; 423 break; 424 } 425 rcu_read_unlock(); 426 427 return nc_path_tmp; 428} 429 430/** 431 * batadv_nc_send_packet - send non-coded packet and free nc_packet struct 432 * @nc_packet: the nc packet to send 433 */ 434static void batadv_nc_send_packet(struct batadv_nc_packet *nc_packet) 435{ 436 batadv_send_skb_packet(nc_packet->skb, 437 nc_packet->neigh_node->if_incoming, 438 nc_packet->nc_path->next_hop); 439 nc_packet->skb = NULL; 440 batadv_nc_packet_free(nc_packet); 441} 442 443/** 444 * batadv_nc_fwd_flush - Checks the timestamp of the given nc packet. 445 * @bat_priv: the bat priv with all the soft interface information 446 * @nc_path: the nc path the packet belongs to 447 * @nc_packet: the nc packet to be checked 448 * 449 * Checks whether the given nc packet has hit its forward timeout. If so, the 450 * packet is no longer delayed, immediately sent and the entry deleted from the 451 * queue. Has to be called with the appropriate locks. 452 * 453 * Returns false as soon as the entry in the fifo queue has not been timed out 454 * yet and true otherwise. 455 */ 456static bool batadv_nc_fwd_flush(struct batadv_priv *bat_priv, 457 struct batadv_nc_path *nc_path, 458 struct batadv_nc_packet *nc_packet) 459{ 460 unsigned long timeout = bat_priv->nc.max_fwd_delay; 461 462 /* Packets are added to tail, so the remaining packets did not time 463 * out and we can stop processing the current queue 464 */ 465 if (atomic_read(&bat_priv->mesh_state) == BATADV_MESH_ACTIVE && 466 !batadv_has_timed_out(nc_packet->timestamp, timeout)) 467 return false; 468 469 /* Send packet */ 470 batadv_inc_counter(bat_priv, BATADV_CNT_FORWARD); 471 batadv_add_counter(bat_priv, BATADV_CNT_FORWARD_BYTES, 472 nc_packet->skb->len + ETH_HLEN); 473 list_del(&nc_packet->list); 474 batadv_nc_send_packet(nc_packet); 475 476 return true; 477} 478 479/** 480 * batadv_nc_process_nc_paths - traverse given nc packet pool and free timed out 481 * nc packets 482 * @bat_priv: the bat priv with all the soft interface information 483 * @hash: to be processed hash table 484 * @process_fn: Function called to process given nc packet. Should return true 485 * to encourage this function to proceed with the next packet. 486 * Otherwise the rest of the current queue is skipped. 487 */ 488static void 489batadv_nc_process_nc_paths(struct batadv_priv *bat_priv, 490 struct batadv_hashtable *hash, 491 bool (*process_fn)(struct batadv_priv *, 492 struct batadv_nc_path *, 493 struct batadv_nc_packet *)) 494{ 495 struct hlist_head *head; 496 struct batadv_nc_packet *nc_packet, *nc_packet_tmp; 497 struct batadv_nc_path *nc_path; 498 bool ret; 499 int i; 500 501 if (!hash) 502 return; 503 504 /* Loop hash table bins */ 505 for (i = 0; i < hash->size; i++) { 506 head = &hash->table[i]; 507 508 /* Loop coding paths */ 509 rcu_read_lock(); 510 hlist_for_each_entry_rcu(nc_path, head, hash_entry) { 511 /* Loop packets */ 512 spin_lock_bh(&nc_path->packet_list_lock); 513 list_for_each_entry_safe(nc_packet, nc_packet_tmp, 514 &nc_path->packet_list, list) { 515 ret = process_fn(bat_priv, nc_path, nc_packet); 516 if (!ret) 517 break; 518 } 519 spin_unlock_bh(&nc_path->packet_list_lock); 520 } 521 rcu_read_unlock(); 522 } 523} 524 525/** 526 * batadv_nc_worker - periodic task for house keeping related to network coding 527 * @work: kernel work struct 528 */ 529static void batadv_nc_worker(struct work_struct *work) 530{ 531 struct delayed_work *delayed_work; 532 struct batadv_priv_nc *priv_nc; 533 struct batadv_priv *bat_priv; 534 unsigned long timeout; 535 536 delayed_work = container_of(work, struct delayed_work, work); 537 priv_nc = container_of(delayed_work, struct batadv_priv_nc, work); 538 bat_priv = container_of(priv_nc, struct batadv_priv, nc); 539 540 batadv_nc_purge_orig_hash(bat_priv); 541 batadv_nc_purge_paths(bat_priv, bat_priv->nc.coding_hash, 542 batadv_nc_to_purge_nc_path_coding); 543 544 timeout = bat_priv->nc.max_fwd_delay; 545 546 if (batadv_has_timed_out(bat_priv->nc.timestamp_fwd_flush, timeout)) { 547 batadv_nc_process_nc_paths(bat_priv, bat_priv->nc.coding_hash, 548 batadv_nc_fwd_flush); 549 bat_priv->nc.timestamp_fwd_flush = jiffies; 550 } 551 552 /* Schedule a new check */ 553 batadv_nc_start_timer(bat_priv); 554} 555 556/** 557 * batadv_can_nc_with_orig - checks whether the given orig node is suitable for 558 * coding or not 559 * @bat_priv: the bat priv with all the soft interface information 560 * @orig_node: neighboring orig node which may be used as nc candidate 561 * @ogm_packet: incoming ogm packet also used for the checks 562 * 563 * Returns true if: 564 * 1) The OGM must have the most recent sequence number. 565 * 2) The TTL must be decremented by one and only one. 566 * 3) The OGM must be received from the first hop from orig_node. 567 * 4) The TQ value of the OGM must be above bat_priv->nc.min_tq. 568 */ 569static bool batadv_can_nc_with_orig(struct batadv_priv *bat_priv, 570 struct batadv_orig_node *orig_node, 571 struct batadv_ogm_packet *ogm_packet) 572{ 573 if (orig_node->last_real_seqno != ogm_packet->seqno) 574 return false; 575 if (orig_node->last_ttl != ogm_packet->header.ttl + 1) 576 return false; 577 if (!batadv_compare_eth(ogm_packet->orig, ogm_packet->prev_sender)) 578 return false; 579 if (ogm_packet->tq < bat_priv->nc.min_tq) 580 return false; 581 582 return true; 583} 584 585/** 586 * batadv_nc_find_nc_node - search for an existing nc node and return it 587 * @orig_node: orig node originating the ogm packet 588 * @orig_neigh_node: neighboring orig node from which we received the ogm packet 589 * (can be equal to orig_node) 590 * @in_coding: traverse incoming or outgoing network coding list 591 * 592 * Returns the nc_node if found, NULL otherwise. 593 */ 594static struct batadv_nc_node 595*batadv_nc_find_nc_node(struct batadv_orig_node *orig_node, 596 struct batadv_orig_node *orig_neigh_node, 597 bool in_coding) 598{ 599 struct batadv_nc_node *nc_node, *nc_node_out = NULL; 600 struct list_head *list; 601 602 if (in_coding) 603 list = &orig_neigh_node->in_coding_list; 604 else 605 list = &orig_neigh_node->out_coding_list; 606 607 /* Traverse list of nc_nodes to orig_node */ 608 rcu_read_lock(); 609 list_for_each_entry_rcu(nc_node, list, list) { 610 if (!batadv_compare_eth(nc_node->addr, orig_node->orig)) 611 continue; 612 613 if (!atomic_inc_not_zero(&nc_node->refcount)) 614 continue; 615 616 /* Found a match */ 617 nc_node_out = nc_node; 618 break; 619 } 620 rcu_read_unlock(); 621 622 return nc_node_out; 623} 624 625/** 626 * batadv_nc_get_nc_node - retrieves an nc node or creates the entry if it was 627 * not found 628 * @bat_priv: the bat priv with all the soft interface information 629 * @orig_node: orig node originating the ogm packet 630 * @orig_neigh_node: neighboring orig node from which we received the ogm packet 631 * (can be equal to orig_node) 632 * @in_coding: traverse incoming or outgoing network coding list 633 * 634 * Returns the nc_node if found or created, NULL in case of an error. 635 */ 636static struct batadv_nc_node 637*batadv_nc_get_nc_node(struct batadv_priv *bat_priv, 638 struct batadv_orig_node *orig_node, 639 struct batadv_orig_node *orig_neigh_node, 640 bool in_coding) 641{ 642 struct batadv_nc_node *nc_node; 643 spinlock_t *lock; /* Used to lock list selected by "int in_coding" */ 644 struct list_head *list; 645 646 /* Check if nc_node is already added */ 647 nc_node = batadv_nc_find_nc_node(orig_node, orig_neigh_node, in_coding); 648 649 /* Node found */ 650 if (nc_node) 651 return nc_node; 652 653 nc_node = kzalloc(sizeof(*nc_node), GFP_ATOMIC); 654 if (!nc_node) 655 return NULL; 656 657 if (!atomic_inc_not_zero(&orig_neigh_node->refcount)) 658 goto free; 659 660 /* Initialize nc_node */ 661 INIT_LIST_HEAD(&nc_node->list); 662 memcpy(nc_node->addr, orig_node->orig, ETH_ALEN); 663 nc_node->orig_node = orig_neigh_node; 664 atomic_set(&nc_node->refcount, 2); 665 666 /* Select ingoing or outgoing coding node */ 667 if (in_coding) { 668 lock = &orig_neigh_node->in_coding_list_lock; 669 list = &orig_neigh_node->in_coding_list; 670 } else { 671 lock = &orig_neigh_node->out_coding_list_lock; 672 list = &orig_neigh_node->out_coding_list; 673 } 674 675 batadv_dbg(BATADV_DBG_NC, bat_priv, "Adding nc_node %pM -> %pM\n", 676 nc_node->addr, nc_node->orig_node->orig); 677 678 /* Add nc_node to orig_node */ 679 spin_lock_bh(lock); 680 list_add_tail_rcu(&nc_node->list, list); 681 spin_unlock_bh(lock); 682 683 return nc_node; 684 685free: 686 kfree(nc_node); 687 return NULL; 688} 689 690/** 691 * batadv_nc_update_nc_node - updates stored incoming and outgoing nc node structs 692 * (best called on incoming OGMs) 693 * @bat_priv: the bat priv with all the soft interface information 694 * @orig_node: orig node originating the ogm packet 695 * @orig_neigh_node: neighboring orig node from which we received the ogm packet 696 * (can be equal to orig_node) 697 * @ogm_packet: incoming ogm packet 698 * @is_single_hop_neigh: orig_node is a single hop neighbor 699 */ 700void batadv_nc_update_nc_node(struct batadv_priv *bat_priv, 701 struct batadv_orig_node *orig_node, 702 struct batadv_orig_node *orig_neigh_node, 703 struct batadv_ogm_packet *ogm_packet, 704 int is_single_hop_neigh) 705{ 706 struct batadv_nc_node *in_nc_node = NULL, *out_nc_node = NULL; 707 708 /* Check if network coding is enabled */ 709 if (!atomic_read(&bat_priv->network_coding)) 710 goto out; 711 712 /* accept ogms from 'good' neighbors and single hop neighbors */ 713 if (!batadv_can_nc_with_orig(bat_priv, orig_node, ogm_packet) && 714 !is_single_hop_neigh) 715 goto out; 716 717 /* Add orig_node as in_nc_node on hop */ 718 in_nc_node = batadv_nc_get_nc_node(bat_priv, orig_node, 719 orig_neigh_node, true); 720 if (!in_nc_node) 721 goto out; 722 723 in_nc_node->last_seen = jiffies; 724 725 /* Add hop as out_nc_node on orig_node */ 726 out_nc_node = batadv_nc_get_nc_node(bat_priv, orig_neigh_node, 727 orig_node, false); 728 if (!out_nc_node) 729 goto out; 730 731 out_nc_node->last_seen = jiffies; 732 733out: 734 if (in_nc_node) 735 batadv_nc_node_free_ref(in_nc_node); 736 if (out_nc_node) 737 batadv_nc_node_free_ref(out_nc_node); 738} 739 740/** 741 * batadv_nc_get_path - get existing nc_path or allocate a new one 742 * @bat_priv: the bat priv with all the soft interface information 743 * @hash: hash table containing the nc path 744 * @src: ethernet source address - first half of the nc path search key 745 * @dst: ethernet destination address - second half of the nc path search key 746 * 747 * Returns pointer to nc_path if the path was found or created, returns NULL 748 * on error. 749 */ 750static struct batadv_nc_path *batadv_nc_get_path(struct batadv_priv *bat_priv, 751 struct batadv_hashtable *hash, 752 uint8_t *src, 753 uint8_t *dst) 754{ 755 int hash_added; 756 struct batadv_nc_path *nc_path, nc_path_key; 757 758 batadv_nc_hash_key_gen(&nc_path_key, src, dst); 759 760 /* Search for existing nc_path */ 761 nc_path = batadv_nc_hash_find(hash, (void *)&nc_path_key); 762 763 if (nc_path) { 764 /* Set timestamp to delay removal of nc_path */ 765 nc_path->last_valid = jiffies; 766 return nc_path; 767 } 768 769 /* No existing nc_path was found; create a new */ 770 nc_path = kzalloc(sizeof(*nc_path), GFP_ATOMIC); 771 772 if (!nc_path) 773 return NULL; 774 775 /* Initialize nc_path */ 776 INIT_LIST_HEAD(&nc_path->packet_list); 777 spin_lock_init(&nc_path->packet_list_lock); 778 atomic_set(&nc_path->refcount, 2); 779 nc_path->last_valid = jiffies; 780 memcpy(nc_path->next_hop, dst, ETH_ALEN); 781 memcpy(nc_path->prev_hop, src, ETH_ALEN); 782 783 batadv_dbg(BATADV_DBG_NC, bat_priv, "Adding nc_path %pM -> %pM\n", 784 nc_path->prev_hop, 785 nc_path->next_hop); 786 787 /* Add nc_path to hash table */ 788 hash_added = batadv_hash_add(hash, batadv_nc_hash_compare, 789 batadv_nc_hash_choose, &nc_path_key, 790 &nc_path->hash_entry); 791 792 if (hash_added < 0) { 793 kfree(nc_path); 794 return NULL; 795 } 796 797 return nc_path; 798} 799 800/** 801 * batadv_nc_skb_add_to_path - buffer skb for later encoding / decoding 802 * @skb: skb to add to path 803 * @nc_path: path to add skb to 804 * @neigh_node: next hop to forward packet to 805 * @packet_id: checksum to identify packet 806 * 807 * Returns true if the packet was buffered or false in case of an error. 808 */ 809static bool batadv_nc_skb_add_to_path(struct sk_buff *skb, 810 struct batadv_nc_path *nc_path, 811 struct batadv_neigh_node *neigh_node, 812 __be32 packet_id) 813{ 814 struct batadv_nc_packet *nc_packet; 815 816 nc_packet = kzalloc(sizeof(*nc_packet), GFP_ATOMIC); 817 if (!nc_packet) 818 return false; 819 820 /* Initialize nc_packet */ 821 nc_packet->timestamp = jiffies; 822 nc_packet->packet_id = packet_id; 823 nc_packet->skb = skb; 824 nc_packet->neigh_node = neigh_node; 825 nc_packet->nc_path = nc_path; 826 827 /* Add coding packet to list */ 828 spin_lock_bh(&nc_path->packet_list_lock); 829 list_add_tail(&nc_packet->list, &nc_path->packet_list); 830 spin_unlock_bh(&nc_path->packet_list_lock); 831 832 return true; 833} 834 835/** 836 * batadv_nc_skb_forward - try to code a packet or add it to the coding packet 837 * buffer 838 * @skb: data skb to forward 839 * @neigh_node: next hop to forward packet to 840 * @ethhdr: pointer to the ethernet header inside the skb 841 * 842 * Returns true if the skb was consumed (encoded packet sent) or false otherwise 843 */ 844bool batadv_nc_skb_forward(struct sk_buff *skb, 845 struct batadv_neigh_node *neigh_node, 846 struct ethhdr *ethhdr) 847{ 848 const struct net_device *netdev = neigh_node->if_incoming->soft_iface; 849 struct batadv_priv *bat_priv = netdev_priv(netdev); 850 struct batadv_unicast_packet *packet; 851 struct batadv_nc_path *nc_path; 852 __be32 packet_id; 853 u8 *payload; 854 855 /* Check if network coding is enabled */ 856 if (!atomic_read(&bat_priv->network_coding)) 857 goto out; 858 859 /* We only handle unicast packets */ 860 payload = skb_network_header(skb); 861 packet = (struct batadv_unicast_packet *)payload; 862 if (packet->header.packet_type != BATADV_UNICAST) 863 goto out; 864 865 /* Find or create a nc_path for this src-dst pair */ 866 nc_path = batadv_nc_get_path(bat_priv, 867 bat_priv->nc.coding_hash, 868 ethhdr->h_source, 869 neigh_node->addr); 870 871 if (!nc_path) 872 goto out; 873 874 /* Add skb to nc_path */ 875 packet_id = batadv_skb_crc32(skb, payload + sizeof(*packet)); 876 if (!batadv_nc_skb_add_to_path(skb, nc_path, neigh_node, packet_id)) 877 goto free_nc_path; 878 879 /* Packet is consumed */ 880 return true; 881 882free_nc_path: 883 batadv_nc_path_free_ref(nc_path); 884out: 885 /* Packet is not consumed */ 886 return false; 887} 888 889/** 890 * batadv_nc_free - clean up network coding memory 891 * @bat_priv: the bat priv with all the soft interface information 892 */ 893void batadv_nc_free(struct batadv_priv *bat_priv) 894{ 895 cancel_delayed_work_sync(&bat_priv->nc.work); 896 batadv_nc_purge_paths(bat_priv, bat_priv->nc.coding_hash, NULL); 897 batadv_hash_destroy(bat_priv->nc.coding_hash); 898} 899 900/** 901 * batadv_nc_nodes_seq_print_text - print the nc node information 902 * @seq: seq file to print on 903 * @offset: not used 904 */ 905int batadv_nc_nodes_seq_print_text(struct seq_file *seq, void *offset) 906{ 907 struct net_device *net_dev = (struct net_device *)seq->private; 908 struct batadv_priv *bat_priv = netdev_priv(net_dev); 909 struct batadv_hashtable *hash = bat_priv->orig_hash; 910 struct batadv_hard_iface *primary_if; 911 struct hlist_head *head; 912 struct batadv_orig_node *orig_node; 913 struct batadv_nc_node *nc_node; 914 int i; 915 916 primary_if = batadv_seq_print_text_primary_if_get(seq); 917 if (!primary_if) 918 goto out; 919 920 /* Traverse list of originators */ 921 for (i = 0; i < hash->size; i++) { 922 head = &hash->table[i]; 923 924 /* For each orig_node in this bin */ 925 rcu_read_lock(); 926 hlist_for_each_entry_rcu(orig_node, head, hash_entry) { 927 seq_printf(seq, "Node: %pM\n", orig_node->orig); 928 929 seq_printf(seq, " Ingoing: "); 930 /* For each in_nc_node to this orig_node */ 931 list_for_each_entry_rcu(nc_node, 932 &orig_node->in_coding_list, 933 list) 934 seq_printf(seq, "%pM ", 935 nc_node->addr); 936 seq_printf(seq, "\n"); 937 938 seq_printf(seq, " Outgoing: "); 939 /* For out_nc_node to this orig_node */ 940 list_for_each_entry_rcu(nc_node, 941 &orig_node->out_coding_list, 942 list) 943 seq_printf(seq, "%pM ", 944 nc_node->addr); 945 seq_printf(seq, "\n\n"); 946 } 947 rcu_read_unlock(); 948 } 949 950out: 951 if (primary_if) 952 batadv_hardif_free_ref(primary_if); 953 return 0; 954} 955 956/** 957 * batadv_nc_init_debugfs - create nc folder and related files in debugfs 958 * @bat_priv: the bat priv with all the soft interface information 959 */ 960int batadv_nc_init_debugfs(struct batadv_priv *bat_priv) 961{ 962 struct dentry *nc_dir, *file; 963 964 nc_dir = debugfs_create_dir("nc", bat_priv->debug_dir); 965 if (!nc_dir) 966 goto out; 967 968 file = debugfs_create_u8("min_tq", S_IRUGO | S_IWUSR, nc_dir, 969 &bat_priv->nc.min_tq); 970 if (!file) 971 goto out; 972 973 file = debugfs_create_u32("max_fwd_delay", S_IRUGO | S_IWUSR, nc_dir, 974 &bat_priv->nc.max_fwd_delay); 975 if (!file) 976 goto out; 977 978 return 0; 979 980out: 981 return -ENOMEM; 982} 983