aboutsummaryrefslogtreecommitdiffstats
path: root/net/batman-adv/network-coding.c
diff options
context:
space:
mode:
authorMartin Hundebøll <martin@hundeboll.net>2013-01-25 05:12:40 -0500
committerAntonio Quartulli <ordex@autistici.org>2013-03-13 17:53:49 -0400
commit953324776d6d23eb81f5b825870027b9c069db29 (patch)
treeca6a07caecd098623031cffcf8a2dd80a4d1a4e6 /net/batman-adv/network-coding.c
parentd56b1705e28c196312607bc8bdde0e91879c20b6 (diff)
batman-adv: network coding - buffer unicast packets before forward
Two be able to network code two packets, one packet must be buffered until the next is available. This is done in a "coding buffer", which is essentially a hash table with lists of packets. Each entry in the hash table corresponds to a specific src-dst pair, which has a linked list of packets that are buffered. This patch adds skbs to the buffer just before forwarding them. The buffer is traversed every 10 ms, where timed skbs are removed from the buffer and transmitted. To allow experiments with the network coding scheme, the timeout is tunable through a file in debugfs. Signed-off-by: Martin Hundebøll <martin@hundeboll.net> Signed-off-by: Marek Lindner <lindner_marek@yahoo.de> Signed-off-by: Antonio Quartulli <ordex@autistici.org>
Diffstat (limited to 'net/batman-adv/network-coding.c')
-rw-r--r--net/batman-adv/network-coding.c487
1 files changed, 487 insertions, 0 deletions
diff --git a/net/batman-adv/network-coding.c b/net/batman-adv/network-coding.c
index ff4985d84726..2c38c540c6db 100644
--- a/net/batman-adv/network-coding.c
+++ b/net/batman-adv/network-coding.c
@@ -20,10 +20,14 @@
20#include <linux/debugfs.h> 20#include <linux/debugfs.h>
21 21
22#include "main.h" 22#include "main.h"
23#include "hash.h"
23#include "network-coding.h" 24#include "network-coding.h"
25#include "send.h"
24#include "originator.h" 26#include "originator.h"
25#include "hard-interface.h" 27#include "hard-interface.h"
26 28
29static struct lock_class_key batadv_nc_coding_hash_lock_class_key;
30
27static void batadv_nc_worker(struct work_struct *work); 31static void batadv_nc_worker(struct work_struct *work);
28 32
29/** 33/**
@@ -42,10 +46,25 @@ static void batadv_nc_start_timer(struct batadv_priv *bat_priv)
42 */ 46 */
43int batadv_nc_init(struct batadv_priv *bat_priv) 47int batadv_nc_init(struct batadv_priv *bat_priv)
44{ 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
45 INIT_DELAYED_WORK(&bat_priv->nc.work, batadv_nc_worker); 61 INIT_DELAYED_WORK(&bat_priv->nc.work, batadv_nc_worker);
46 batadv_nc_start_timer(bat_priv); 62 batadv_nc_start_timer(bat_priv);
47 63
48 return 0; 64 return 0;
65
66err:
67 return -ENOMEM;
49} 68}
50 69
51/** 70/**
@@ -56,6 +75,7 @@ void batadv_nc_init_bat_priv(struct batadv_priv *bat_priv)
56{ 75{
57 atomic_set(&bat_priv->network_coding, 1); 76 atomic_set(&bat_priv->network_coding, 1);
58 bat_priv->nc.min_tq = 200; 77 bat_priv->nc.min_tq = 200;
78 bat_priv->nc.max_fwd_delay = 10;
59} 79}
60 80
61/** 81/**
@@ -96,6 +116,30 @@ static void batadv_nc_node_free_ref(struct batadv_nc_node *nc_node)
96} 116}
97 117
98/** 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/**
99 * batadv_nc_to_purge_nc_node - checks whether an nc node has to be purged 143 * batadv_nc_to_purge_nc_node - checks whether an nc node has to be purged
100 * @bat_priv: the bat priv with all the soft interface information 144 * @bat_priv: the bat priv with all the soft interface information
101 * @nc_node: the nc node to check 145 * @nc_node: the nc node to check
@@ -112,6 +156,26 @@ static bool batadv_nc_to_purge_nc_node(struct batadv_priv *bat_priv,
112} 156}
113 157
114/** 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/**
115 * batadv_nc_purge_orig_nc_nodes - go through list of nc nodes and purge stale 179 * batadv_nc_purge_orig_nc_nodes - go through list of nc nodes and purge stale
116 * entries 180 * entries
117 * @bat_priv: the bat priv with all the soft interface information 181 * @bat_priv: the bat priv with all the soft interface information
@@ -203,6 +267,262 @@ static void batadv_nc_purge_orig_hash(struct batadv_priv *bat_priv)
203} 267}
204 268
205/** 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/**
206 * batadv_nc_worker - periodic task for house keeping related to network coding 526 * batadv_nc_worker - periodic task for house keeping related to network coding
207 * @work: kernel work struct 527 * @work: kernel work struct
208 */ 528 */
@@ -211,12 +531,23 @@ static void batadv_nc_worker(struct work_struct *work)
211 struct delayed_work *delayed_work; 531 struct delayed_work *delayed_work;
212 struct batadv_priv_nc *priv_nc; 532 struct batadv_priv_nc *priv_nc;
213 struct batadv_priv *bat_priv; 533 struct batadv_priv *bat_priv;
534 unsigned long timeout;
214 535
215 delayed_work = container_of(work, struct delayed_work, work); 536 delayed_work = container_of(work, struct delayed_work, work);
216 priv_nc = container_of(delayed_work, struct batadv_priv_nc, work); 537 priv_nc = container_of(delayed_work, struct batadv_priv_nc, work);
217 bat_priv = container_of(priv_nc, struct batadv_priv, nc); 538 bat_priv = container_of(priv_nc, struct batadv_priv, nc);
218 539
219 batadv_nc_purge_orig_hash(bat_priv); 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 }
220 551
221 /* Schedule a new check */ 552 /* Schedule a new check */
222 batadv_nc_start_timer(bat_priv); 553 batadv_nc_start_timer(bat_priv);
@@ -407,12 +738,163 @@ out:
407} 738}
408 739
409/** 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/**
410 * batadv_nc_free - clean up network coding memory 890 * batadv_nc_free - clean up network coding memory
411 * @bat_priv: the bat priv with all the soft interface information 891 * @bat_priv: the bat priv with all the soft interface information
412 */ 892 */
413void batadv_nc_free(struct batadv_priv *bat_priv) 893void batadv_nc_free(struct batadv_priv *bat_priv)
414{ 894{
415 cancel_delayed_work_sync(&bat_priv->nc.work); 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);
416} 898}
417 899
418/** 900/**
@@ -488,6 +970,11 @@ int batadv_nc_init_debugfs(struct batadv_priv *bat_priv)
488 if (!file) 970 if (!file)
489 goto out; 971 goto out;
490 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
491 return 0; 978 return 0;
492 979
493out: 980out: