1 /* Copyright (C) 2012-2013 B.A.T.M.A.N. contributors:
3 * Martin Hundebøll, Jeppe Ledet-Pedersen
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.
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.
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
20 #include <linux/debugfs.h>
24 #include "network-coding.h"
26 #include "originator.h"
27 #include "hard-interface.h"
30 static struct lock_class_key batadv_nc_coding_hash_lock_class_key;
31 static struct lock_class_key batadv_nc_decoding_hash_lock_class_key;
33 static void batadv_nc_worker(struct work_struct *work);
34 static int batadv_nc_recv_coded_packet(struct sk_buff *skb,
35 struct batadv_hard_iface *recv_if);
38 * batadv_nc_init - one-time initialization for network coding
40 int __init batadv_nc_init(void)
44 /* Register our packet type */
45 ret = batadv_recv_handler_register(BATADV_CODED,
46 batadv_nc_recv_coded_packet);
52 * batadv_nc_start_timer - initialise the nc periodic worker
53 * @bat_priv: the bat priv with all the soft interface information
55 static void batadv_nc_start_timer(struct batadv_priv *bat_priv)
57 queue_delayed_work(batadv_event_workqueue, &bat_priv->nc.work,
58 msecs_to_jiffies(10));
62 * batadv_nc_mesh_init - initialise coding hash table and start house keeping
63 * @bat_priv: the bat priv with all the soft interface information
65 int batadv_nc_mesh_init(struct batadv_priv *bat_priv)
67 bat_priv->nc.timestamp_fwd_flush = jiffies;
68 bat_priv->nc.timestamp_sniffed_purge = jiffies;
70 if (bat_priv->nc.coding_hash || bat_priv->nc.decoding_hash)
73 bat_priv->nc.coding_hash = batadv_hash_new(128);
74 if (!bat_priv->nc.coding_hash)
77 batadv_hash_set_lock_class(bat_priv->nc.coding_hash,
78 &batadv_nc_coding_hash_lock_class_key);
80 bat_priv->nc.decoding_hash = batadv_hash_new(128);
81 if (!bat_priv->nc.decoding_hash)
84 batadv_hash_set_lock_class(bat_priv->nc.coding_hash,
85 &batadv_nc_decoding_hash_lock_class_key);
87 INIT_DELAYED_WORK(&bat_priv->nc.work, batadv_nc_worker);
88 batadv_nc_start_timer(bat_priv);
97 * batadv_nc_init_bat_priv - initialise the nc specific bat_priv variables
98 * @bat_priv: the bat priv with all the soft interface information
100 void batadv_nc_init_bat_priv(struct batadv_priv *bat_priv)
102 atomic_set(&bat_priv->network_coding, 1);
103 bat_priv->nc.min_tq = 200;
104 bat_priv->nc.max_fwd_delay = 10;
105 bat_priv->nc.max_buffer_time = 200;
109 * batadv_nc_init_orig - initialise the nc fields of an orig_node
110 * @orig_node: the orig_node which is going to be initialised
112 void batadv_nc_init_orig(struct batadv_orig_node *orig_node)
114 INIT_LIST_HEAD(&orig_node->in_coding_list);
115 INIT_LIST_HEAD(&orig_node->out_coding_list);
116 spin_lock_init(&orig_node->in_coding_list_lock);
117 spin_lock_init(&orig_node->out_coding_list_lock);
121 * batadv_nc_node_free_rcu - rcu callback to free an nc node and remove
122 * its refcount on the orig_node
123 * @rcu: rcu pointer of the nc node
125 static void batadv_nc_node_free_rcu(struct rcu_head *rcu)
127 struct batadv_nc_node *nc_node;
129 nc_node = container_of(rcu, struct batadv_nc_node, rcu);
130 batadv_orig_node_free_ref(nc_node->orig_node);
135 * batadv_nc_node_free_ref - decrements the nc node refcounter and possibly
137 * @nc_node: the nc node to free
139 static void batadv_nc_node_free_ref(struct batadv_nc_node *nc_node)
141 if (atomic_dec_and_test(&nc_node->refcount))
142 call_rcu(&nc_node->rcu, batadv_nc_node_free_rcu);
146 * batadv_nc_path_free_ref - decrements the nc path refcounter and possibly
148 * @nc_path: the nc node to free
150 static void batadv_nc_path_free_ref(struct batadv_nc_path *nc_path)
152 if (atomic_dec_and_test(&nc_path->refcount))
153 kfree_rcu(nc_path, rcu);
157 * batadv_nc_packet_free - frees nc packet
158 * @nc_packet: the nc packet to free
160 static void batadv_nc_packet_free(struct batadv_nc_packet *nc_packet)
163 kfree_skb(nc_packet->skb);
165 batadv_nc_path_free_ref(nc_packet->nc_path);
170 * batadv_nc_to_purge_nc_node - checks whether an nc node has to be purged
171 * @bat_priv: the bat priv with all the soft interface information
172 * @nc_node: the nc node to check
174 * Returns true if the entry has to be purged now, false otherwise
176 static bool batadv_nc_to_purge_nc_node(struct batadv_priv *bat_priv,
177 struct batadv_nc_node *nc_node)
179 if (atomic_read(&bat_priv->mesh_state) != BATADV_MESH_ACTIVE)
182 return batadv_has_timed_out(nc_node->last_seen, BATADV_NC_NODE_TIMEOUT);
186 * batadv_nc_to_purge_nc_path_coding - checks whether an nc path has timed out
187 * @bat_priv: the bat priv with all the soft interface information
188 * @nc_path: the nc path to check
190 * Returns true if the entry has to be purged now, false otherwise
192 static bool batadv_nc_to_purge_nc_path_coding(struct batadv_priv *bat_priv,
193 struct batadv_nc_path *nc_path)
195 if (atomic_read(&bat_priv->mesh_state) != BATADV_MESH_ACTIVE)
198 /* purge the path when no packets has been added for 10 times the
201 return batadv_has_timed_out(nc_path->last_valid,
202 bat_priv->nc.max_fwd_delay * 10);
206 * batadv_nc_to_purge_nc_path_decoding - checks whether an nc path has timed out
207 * @bat_priv: the bat priv with all the soft interface information
208 * @nc_path: the nc path to check
210 * Returns true if the entry has to be purged now, false otherwise
212 static bool batadv_nc_to_purge_nc_path_decoding(struct batadv_priv *bat_priv,
213 struct batadv_nc_path *nc_path)
215 if (atomic_read(&bat_priv->mesh_state) != BATADV_MESH_ACTIVE)
218 /* purge the path when no packets has been added for 10 times the
221 return batadv_has_timed_out(nc_path->last_valid,
222 bat_priv->nc.max_buffer_time*10);
226 * batadv_nc_purge_orig_nc_nodes - go through list of nc nodes and purge stale
228 * @bat_priv: the bat priv with all the soft interface information
229 * @list: list of nc nodes
230 * @lock: nc node list lock
231 * @to_purge: function in charge to decide whether an entry has to be purged or
232 * not. This function takes the nc node as argument and has to return
233 * a boolean value: true if the entry has to be deleted, false
237 batadv_nc_purge_orig_nc_nodes(struct batadv_priv *bat_priv,
238 struct list_head *list,
240 bool (*to_purge)(struct batadv_priv *,
241 struct batadv_nc_node *))
243 struct batadv_nc_node *nc_node, *nc_node_tmp;
245 /* For each nc_node in list */
247 list_for_each_entry_safe(nc_node, nc_node_tmp, list, list) {
248 /* if an helper function has been passed as parameter,
249 * ask it if the entry has to be purged or not
251 if (to_purge && !to_purge(bat_priv, nc_node))
254 batadv_dbg(BATADV_DBG_NC, bat_priv,
255 "Removing nc_node %pM -> %pM\n",
256 nc_node->addr, nc_node->orig_node->orig);
257 list_del_rcu(&nc_node->list);
258 batadv_nc_node_free_ref(nc_node);
260 spin_unlock_bh(lock);
264 * batadv_nc_purge_orig - purges all nc node data attached of the given
266 * @bat_priv: the bat priv with all the soft interface information
267 * @orig_node: orig_node with the nc node entries to be purged
268 * @to_purge: function in charge to decide whether an entry has to be purged or
269 * not. This function takes the nc node as argument and has to return
270 * a boolean value: true is the entry has to be deleted, false
273 void batadv_nc_purge_orig(struct batadv_priv *bat_priv,
274 struct batadv_orig_node *orig_node,
275 bool (*to_purge)(struct batadv_priv *,
276 struct batadv_nc_node *))
278 /* Check ingoing nc_node's of this orig_node */
279 batadv_nc_purge_orig_nc_nodes(bat_priv, &orig_node->in_coding_list,
280 &orig_node->in_coding_list_lock,
283 /* Check outgoing nc_node's of this orig_node */
284 batadv_nc_purge_orig_nc_nodes(bat_priv, &orig_node->out_coding_list,
285 &orig_node->out_coding_list_lock,
290 * batadv_nc_purge_orig_hash - traverse entire originator hash to check if they
291 * have timed out nc nodes
292 * @bat_priv: the bat priv with all the soft interface information
294 static void batadv_nc_purge_orig_hash(struct batadv_priv *bat_priv)
296 struct batadv_hashtable *hash = bat_priv->orig_hash;
297 struct hlist_head *head;
298 struct batadv_orig_node *orig_node;
304 /* For each orig_node */
305 for (i = 0; i < hash->size; i++) {
306 head = &hash->table[i];
309 hlist_for_each_entry_rcu(orig_node, head, hash_entry)
310 batadv_nc_purge_orig(bat_priv, orig_node,
311 batadv_nc_to_purge_nc_node);
317 * batadv_nc_purge_paths - traverse all nc paths part of the hash and remove
319 * @bat_priv: the bat priv with all the soft interface information
320 * @hash: hash table containing the nc paths to check
321 * @to_purge: function in charge to decide whether an entry has to be purged or
322 * not. This function takes the nc node as argument and has to return
323 * a boolean value: true is the entry has to be deleted, false
326 static void batadv_nc_purge_paths(struct batadv_priv *bat_priv,
327 struct batadv_hashtable *hash,
328 bool (*to_purge)(struct batadv_priv *,
329 struct batadv_nc_path *))
331 struct hlist_head *head;
332 struct hlist_node *node_tmp;
333 struct batadv_nc_path *nc_path;
334 spinlock_t *lock; /* Protects lists in hash */
337 for (i = 0; i < hash->size; i++) {
338 head = &hash->table[i];
339 lock = &hash->list_locks[i];
341 /* For each nc_path in this bin */
343 hlist_for_each_entry_safe(nc_path, node_tmp, head, hash_entry) {
344 /* if an helper function has been passed as parameter,
345 * ask it if the entry has to be purged or not
347 if (to_purge && !to_purge(bat_priv, nc_path))
350 /* purging an non-empty nc_path should never happen, but
351 * is observed under high CPU load. Delay the purging
352 * until next iteration to allow the packet_list to be
355 if (!unlikely(list_empty(&nc_path->packet_list))) {
356 net_ratelimited_function(printk,
358 "Skipping free of non-empty nc_path (%pM -> %pM)!\n",
364 /* nc_path is unused, so remove it */
365 batadv_dbg(BATADV_DBG_NC, bat_priv,
366 "Remove nc_path %pM -> %pM\n",
367 nc_path->prev_hop, nc_path->next_hop);
368 hlist_del_rcu(&nc_path->hash_entry);
369 batadv_nc_path_free_ref(nc_path);
371 spin_unlock_bh(lock);
376 * batadv_nc_hash_key_gen - computes the nc_path hash key
377 * @key: buffer to hold the final hash key
378 * @src: source ethernet mac address going into the hash key
379 * @dst: destination ethernet mac address going into the hash key
381 static void batadv_nc_hash_key_gen(struct batadv_nc_path *key, const char *src,
384 memcpy(key->prev_hop, src, sizeof(key->prev_hop));
385 memcpy(key->next_hop, dst, sizeof(key->next_hop));
389 * batadv_nc_hash_choose - compute the hash value for an nc path
390 * @data: data to hash
391 * @size: size of the hash table
393 * Returns the selected index in the hash table for the given data.
395 static uint32_t batadv_nc_hash_choose(const void *data, uint32_t size)
397 const struct batadv_nc_path *nc_path = data;
400 hash = batadv_hash_bytes(hash, &nc_path->prev_hop,
401 sizeof(nc_path->prev_hop));
402 hash = batadv_hash_bytes(hash, &nc_path->next_hop,
403 sizeof(nc_path->next_hop));
406 hash ^= (hash >> 11);
407 hash += (hash << 15);
413 * batadv_nc_hash_compare - comparing function used in the network coding hash
415 * @node: node in the local table
416 * @data2: second object to compare the node to
418 * Returns 1 if the two entry are the same, 0 otherwise
420 static int batadv_nc_hash_compare(const struct hlist_node *node,
423 const struct batadv_nc_path *nc_path1, *nc_path2;
425 nc_path1 = container_of(node, struct batadv_nc_path, hash_entry);
428 /* Return 1 if the two keys are identical */
429 if (memcmp(nc_path1->prev_hop, nc_path2->prev_hop,
430 sizeof(nc_path1->prev_hop)) != 0)
433 if (memcmp(nc_path1->next_hop, nc_path2->next_hop,
434 sizeof(nc_path1->next_hop)) != 0)
441 * batadv_nc_hash_find - search for an existing nc path and return it
442 * @hash: hash table containing the nc path
445 * Returns the nc_path if found, NULL otherwise.
447 static struct batadv_nc_path *
448 batadv_nc_hash_find(struct batadv_hashtable *hash,
451 struct hlist_head *head;
452 struct batadv_nc_path *nc_path, *nc_path_tmp = NULL;
458 index = batadv_nc_hash_choose(data, hash->size);
459 head = &hash->table[index];
462 hlist_for_each_entry_rcu(nc_path, head, hash_entry) {
463 if (!batadv_nc_hash_compare(&nc_path->hash_entry, data))
466 if (!atomic_inc_not_zero(&nc_path->refcount))
469 nc_path_tmp = nc_path;
478 * batadv_nc_send_packet - send non-coded packet and free nc_packet struct
479 * @nc_packet: the nc packet to send
481 static void batadv_nc_send_packet(struct batadv_nc_packet *nc_packet)
483 batadv_send_skb_packet(nc_packet->skb,
484 nc_packet->neigh_node->if_incoming,
485 nc_packet->nc_path->next_hop);
486 nc_packet->skb = NULL;
487 batadv_nc_packet_free(nc_packet);
491 * batadv_nc_sniffed_purge - Checks timestamp of given sniffed nc_packet.
492 * @bat_priv: the bat priv with all the soft interface information
493 * @nc_path: the nc path the packet belongs to
494 * @nc_packet: the nc packet to be checked
496 * Checks whether the given sniffed (overheard) nc_packet has hit its buffering
497 * timeout. If so, the packet is no longer kept and the entry deleted from the
498 * queue. Has to be called with the appropriate locks.
500 * Returns false as soon as the entry in the fifo queue has not been timed out
501 * yet and true otherwise.
503 static bool batadv_nc_sniffed_purge(struct batadv_priv *bat_priv,
504 struct batadv_nc_path *nc_path,
505 struct batadv_nc_packet *nc_packet)
507 unsigned long timeout = bat_priv->nc.max_buffer_time;
510 /* Packets are added to tail, so the remaining packets did not time
511 * out and we can stop processing the current queue
513 if (atomic_read(&bat_priv->mesh_state) == BATADV_MESH_ACTIVE &&
514 !batadv_has_timed_out(nc_packet->timestamp, timeout))
517 /* purge nc packet */
518 list_del(&nc_packet->list);
519 batadv_nc_packet_free(nc_packet);
528 * batadv_nc_fwd_flush - Checks the timestamp of the given nc packet.
529 * @bat_priv: the bat priv with all the soft interface information
530 * @nc_path: the nc path the packet belongs to
531 * @nc_packet: the nc packet to be checked
533 * Checks whether the given nc packet has hit its forward timeout. If so, the
534 * packet is no longer delayed, immediately sent and the entry deleted from the
535 * queue. Has to be called with the appropriate locks.
537 * Returns false as soon as the entry in the fifo queue has not been timed out
538 * yet and true otherwise.
540 static bool batadv_nc_fwd_flush(struct batadv_priv *bat_priv,
541 struct batadv_nc_path *nc_path,
542 struct batadv_nc_packet *nc_packet)
544 unsigned long timeout = bat_priv->nc.max_fwd_delay;
546 /* Packets are added to tail, so the remaining packets did not time
547 * out and we can stop processing the current queue
549 if (atomic_read(&bat_priv->mesh_state) == BATADV_MESH_ACTIVE &&
550 !batadv_has_timed_out(nc_packet->timestamp, timeout))
554 batadv_inc_counter(bat_priv, BATADV_CNT_FORWARD);
555 batadv_add_counter(bat_priv, BATADV_CNT_FORWARD_BYTES,
556 nc_packet->skb->len + ETH_HLEN);
557 list_del(&nc_packet->list);
558 batadv_nc_send_packet(nc_packet);
564 * batadv_nc_process_nc_paths - traverse given nc packet pool and free timed out
566 * @bat_priv: the bat priv with all the soft interface information
567 * @hash: to be processed hash table
568 * @process_fn: Function called to process given nc packet. Should return true
569 * to encourage this function to proceed with the next packet.
570 * Otherwise the rest of the current queue is skipped.
573 batadv_nc_process_nc_paths(struct batadv_priv *bat_priv,
574 struct batadv_hashtable *hash,
575 bool (*process_fn)(struct batadv_priv *,
576 struct batadv_nc_path *,
577 struct batadv_nc_packet *))
579 struct hlist_head *head;
580 struct batadv_nc_packet *nc_packet, *nc_packet_tmp;
581 struct batadv_nc_path *nc_path;
588 /* Loop hash table bins */
589 for (i = 0; i < hash->size; i++) {
590 head = &hash->table[i];
592 /* Loop coding paths */
594 hlist_for_each_entry_rcu(nc_path, head, hash_entry) {
596 spin_lock_bh(&nc_path->packet_list_lock);
597 list_for_each_entry_safe(nc_packet, nc_packet_tmp,
598 &nc_path->packet_list, list) {
599 ret = process_fn(bat_priv, nc_path, nc_packet);
603 spin_unlock_bh(&nc_path->packet_list_lock);
610 * batadv_nc_worker - periodic task for house keeping related to network coding
611 * @work: kernel work struct
613 static void batadv_nc_worker(struct work_struct *work)
615 struct delayed_work *delayed_work;
616 struct batadv_priv_nc *priv_nc;
617 struct batadv_priv *bat_priv;
618 unsigned long timeout;
620 delayed_work = container_of(work, struct delayed_work, work);
621 priv_nc = container_of(delayed_work, struct batadv_priv_nc, work);
622 bat_priv = container_of(priv_nc, struct batadv_priv, nc);
624 batadv_nc_purge_orig_hash(bat_priv);
625 batadv_nc_purge_paths(bat_priv, bat_priv->nc.coding_hash,
626 batadv_nc_to_purge_nc_path_coding);
627 batadv_nc_purge_paths(bat_priv, bat_priv->nc.decoding_hash,
628 batadv_nc_to_purge_nc_path_decoding);
630 timeout = bat_priv->nc.max_fwd_delay;
632 if (batadv_has_timed_out(bat_priv->nc.timestamp_fwd_flush, timeout)) {
633 batadv_nc_process_nc_paths(bat_priv, bat_priv->nc.coding_hash,
634 batadv_nc_fwd_flush);
635 bat_priv->nc.timestamp_fwd_flush = jiffies;
638 if (batadv_has_timed_out(bat_priv->nc.timestamp_sniffed_purge,
639 bat_priv->nc.max_buffer_time)) {
640 batadv_nc_process_nc_paths(bat_priv, bat_priv->nc.decoding_hash,
641 batadv_nc_sniffed_purge);
642 bat_priv->nc.timestamp_sniffed_purge = jiffies;
645 /* Schedule a new check */
646 batadv_nc_start_timer(bat_priv);
650 * batadv_can_nc_with_orig - checks whether the given orig node is suitable for
652 * @bat_priv: the bat priv with all the soft interface information
653 * @orig_node: neighboring orig node which may be used as nc candidate
654 * @ogm_packet: incoming ogm packet also used for the checks
657 * 1) The OGM must have the most recent sequence number.
658 * 2) The TTL must be decremented by one and only one.
659 * 3) The OGM must be received from the first hop from orig_node.
660 * 4) The TQ value of the OGM must be above bat_priv->nc.min_tq.
662 static bool batadv_can_nc_with_orig(struct batadv_priv *bat_priv,
663 struct batadv_orig_node *orig_node,
664 struct batadv_ogm_packet *ogm_packet)
666 if (orig_node->last_real_seqno != ntohl(ogm_packet->seqno))
668 if (orig_node->last_ttl != ogm_packet->header.ttl + 1)
670 if (!batadv_compare_eth(ogm_packet->orig, ogm_packet->prev_sender))
672 if (ogm_packet->tq < bat_priv->nc.min_tq)
679 * batadv_nc_find_nc_node - search for an existing nc node and return it
680 * @orig_node: orig node originating the ogm packet
681 * @orig_neigh_node: neighboring orig node from which we received the ogm packet
682 * (can be equal to orig_node)
683 * @in_coding: traverse incoming or outgoing network coding list
685 * Returns the nc_node if found, NULL otherwise.
687 static struct batadv_nc_node
688 *batadv_nc_find_nc_node(struct batadv_orig_node *orig_node,
689 struct batadv_orig_node *orig_neigh_node,
692 struct batadv_nc_node *nc_node, *nc_node_out = NULL;
693 struct list_head *list;
696 list = &orig_neigh_node->in_coding_list;
698 list = &orig_neigh_node->out_coding_list;
700 /* Traverse list of nc_nodes to orig_node */
702 list_for_each_entry_rcu(nc_node, list, list) {
703 if (!batadv_compare_eth(nc_node->addr, orig_node->orig))
706 if (!atomic_inc_not_zero(&nc_node->refcount))
710 nc_node_out = nc_node;
719 * batadv_nc_get_nc_node - retrieves an nc node or creates the entry if it was
721 * @bat_priv: the bat priv with all the soft interface information
722 * @orig_node: orig node originating the ogm packet
723 * @orig_neigh_node: neighboring orig node from which we received the ogm packet
724 * (can be equal to orig_node)
725 * @in_coding: traverse incoming or outgoing network coding list
727 * Returns the nc_node if found or created, NULL in case of an error.
729 static struct batadv_nc_node
730 *batadv_nc_get_nc_node(struct batadv_priv *bat_priv,
731 struct batadv_orig_node *orig_node,
732 struct batadv_orig_node *orig_neigh_node,
735 struct batadv_nc_node *nc_node;
736 spinlock_t *lock; /* Used to lock list selected by "int in_coding" */
737 struct list_head *list;
739 /* Check if nc_node is already added */
740 nc_node = batadv_nc_find_nc_node(orig_node, orig_neigh_node, in_coding);
746 nc_node = kzalloc(sizeof(*nc_node), GFP_ATOMIC);
750 if (!atomic_inc_not_zero(&orig_neigh_node->refcount))
753 /* Initialize nc_node */
754 INIT_LIST_HEAD(&nc_node->list);
755 memcpy(nc_node->addr, orig_node->orig, ETH_ALEN);
756 nc_node->orig_node = orig_neigh_node;
757 atomic_set(&nc_node->refcount, 2);
759 /* Select ingoing or outgoing coding node */
761 lock = &orig_neigh_node->in_coding_list_lock;
762 list = &orig_neigh_node->in_coding_list;
764 lock = &orig_neigh_node->out_coding_list_lock;
765 list = &orig_neigh_node->out_coding_list;
768 batadv_dbg(BATADV_DBG_NC, bat_priv, "Adding nc_node %pM -> %pM\n",
769 nc_node->addr, nc_node->orig_node->orig);
771 /* Add nc_node to orig_node */
773 list_add_tail_rcu(&nc_node->list, list);
774 spin_unlock_bh(lock);
784 * batadv_nc_update_nc_node - updates stored incoming and outgoing nc node structs
785 * (best called on incoming OGMs)
786 * @bat_priv: the bat priv with all the soft interface information
787 * @orig_node: orig node originating the ogm packet
788 * @orig_neigh_node: neighboring orig node from which we received the ogm packet
789 * (can be equal to orig_node)
790 * @ogm_packet: incoming ogm packet
791 * @is_single_hop_neigh: orig_node is a single hop neighbor
793 void batadv_nc_update_nc_node(struct batadv_priv *bat_priv,
794 struct batadv_orig_node *orig_node,
795 struct batadv_orig_node *orig_neigh_node,
796 struct batadv_ogm_packet *ogm_packet,
797 int is_single_hop_neigh)
799 struct batadv_nc_node *in_nc_node = NULL, *out_nc_node = NULL;
801 /* Check if network coding is enabled */
802 if (!atomic_read(&bat_priv->network_coding))
805 /* accept ogms from 'good' neighbors and single hop neighbors */
806 if (!batadv_can_nc_with_orig(bat_priv, orig_node, ogm_packet) &&
807 !is_single_hop_neigh)
810 /* Add orig_node as in_nc_node on hop */
811 in_nc_node = batadv_nc_get_nc_node(bat_priv, orig_node,
812 orig_neigh_node, true);
816 in_nc_node->last_seen = jiffies;
818 /* Add hop as out_nc_node on orig_node */
819 out_nc_node = batadv_nc_get_nc_node(bat_priv, orig_neigh_node,
824 out_nc_node->last_seen = jiffies;
828 batadv_nc_node_free_ref(in_nc_node);
830 batadv_nc_node_free_ref(out_nc_node);
834 * batadv_nc_get_path - get existing nc_path or allocate a new one
835 * @bat_priv: the bat priv with all the soft interface information
836 * @hash: hash table containing the nc path
837 * @src: ethernet source address - first half of the nc path search key
838 * @dst: ethernet destination address - second half of the nc path search key
840 * Returns pointer to nc_path if the path was found or created, returns NULL
843 static struct batadv_nc_path *batadv_nc_get_path(struct batadv_priv *bat_priv,
844 struct batadv_hashtable *hash,
849 struct batadv_nc_path *nc_path, nc_path_key;
851 batadv_nc_hash_key_gen(&nc_path_key, src, dst);
853 /* Search for existing nc_path */
854 nc_path = batadv_nc_hash_find(hash, (void *)&nc_path_key);
857 /* Set timestamp to delay removal of nc_path */
858 nc_path->last_valid = jiffies;
862 /* No existing nc_path was found; create a new */
863 nc_path = kzalloc(sizeof(*nc_path), GFP_ATOMIC);
868 /* Initialize nc_path */
869 INIT_LIST_HEAD(&nc_path->packet_list);
870 spin_lock_init(&nc_path->packet_list_lock);
871 atomic_set(&nc_path->refcount, 2);
872 nc_path->last_valid = jiffies;
873 memcpy(nc_path->next_hop, dst, ETH_ALEN);
874 memcpy(nc_path->prev_hop, src, ETH_ALEN);
876 batadv_dbg(BATADV_DBG_NC, bat_priv, "Adding nc_path %pM -> %pM\n",
880 /* Add nc_path to hash table */
881 hash_added = batadv_hash_add(hash, batadv_nc_hash_compare,
882 batadv_nc_hash_choose, &nc_path_key,
883 &nc_path->hash_entry);
885 if (hash_added < 0) {
894 * batadv_nc_random_weight_tq - scale the receivers TQ-value to avoid unfair
895 * selection of a receiver with slightly lower TQ than the other
896 * @tq: to be weighted tq value
898 static uint8_t batadv_nc_random_weight_tq(uint8_t tq)
900 uint8_t rand_val, rand_tq;
902 get_random_bytes(&rand_val, sizeof(rand_val));
904 /* randomize the estimated packet loss (max TQ - estimated TQ) */
905 rand_tq = rand_val * (BATADV_TQ_MAX_VALUE - tq);
907 /* normalize the randomized packet loss */
908 rand_tq /= BATADV_TQ_MAX_VALUE;
910 /* convert to (randomized) estimated tq again */
911 return BATADV_TQ_MAX_VALUE - rand_tq;
915 * batadv_nc_memxor - XOR destination with source
916 * @dst: byte array to XOR into
917 * @src: byte array to XOR from
918 * @len: length of destination array
920 static void batadv_nc_memxor(char *dst, const char *src, unsigned int len)
924 for (i = 0; i < len; ++i)
929 * batadv_nc_code_packets - code a received unicast_packet with an nc packet
930 * into a coded_packet and send it
931 * @bat_priv: the bat priv with all the soft interface information
932 * @skb: data skb to forward
933 * @ethhdr: pointer to the ethernet header inside the skb
934 * @nc_packet: structure containing the packet to the skb can be coded with
935 * @neigh_node: next hop to forward packet to
937 * Returns true if both packets are consumed, false otherwise.
939 static bool batadv_nc_code_packets(struct batadv_priv *bat_priv,
941 struct ethhdr *ethhdr,
942 struct batadv_nc_packet *nc_packet,
943 struct batadv_neigh_node *neigh_node)
945 uint8_t tq_weighted_neigh, tq_weighted_coding;
946 struct sk_buff *skb_dest, *skb_src;
947 struct batadv_unicast_packet *packet1;
948 struct batadv_unicast_packet *packet2;
949 struct batadv_coded_packet *coded_packet;
950 struct batadv_neigh_node *neigh_tmp, *router_neigh;
951 struct batadv_neigh_node *router_coding = NULL;
952 uint8_t *first_source, *first_dest, *second_source, *second_dest;
953 __be32 packet_id1, packet_id2;
957 int unicast_size = sizeof(*packet1);
958 int coded_size = sizeof(*coded_packet);
959 int header_add = coded_size - unicast_size;
961 router_neigh = batadv_orig_node_get_router(neigh_node->orig_node);
965 neigh_tmp = nc_packet->neigh_node;
966 router_coding = batadv_orig_node_get_router(neigh_tmp->orig_node);
970 tq_weighted_neigh = batadv_nc_random_weight_tq(router_neigh->tq_avg);
971 tq_weighted_coding = batadv_nc_random_weight_tq(router_coding->tq_avg);
973 /* Select one destination for the MAC-header dst-field based on
974 * weighted TQ-values.
976 if (tq_weighted_neigh >= tq_weighted_coding) {
977 /* Destination from nc_packet is selected for MAC-header */
978 first_dest = nc_packet->nc_path->next_hop;
979 first_source = nc_packet->nc_path->prev_hop;
980 second_dest = neigh_node->addr;
981 second_source = ethhdr->h_source;
982 packet1 = (struct batadv_unicast_packet *)nc_packet->skb->data;
983 packet2 = (struct batadv_unicast_packet *)skb->data;
984 packet_id1 = nc_packet->packet_id;
985 packet_id2 = batadv_skb_crc32(skb,
986 skb->data + sizeof(*packet2));
988 /* Destination for skb is selected for MAC-header */
989 first_dest = neigh_node->addr;
990 first_source = ethhdr->h_source;
991 second_dest = nc_packet->nc_path->next_hop;
992 second_source = nc_packet->nc_path->prev_hop;
993 packet1 = (struct batadv_unicast_packet *)skb->data;
994 packet2 = (struct batadv_unicast_packet *)nc_packet->skb->data;
995 packet_id1 = batadv_skb_crc32(skb,
996 skb->data + sizeof(*packet1));
997 packet_id2 = nc_packet->packet_id;
1000 /* Instead of zero padding the smallest data buffer, we
1001 * code into the largest.
1003 if (skb->len <= nc_packet->skb->len) {
1004 skb_dest = nc_packet->skb;
1008 skb_src = nc_packet->skb;
1011 /* coding_len is used when decoding the packet shorter packet */
1012 coding_len = skb_src->len - unicast_size;
1014 if (skb_linearize(skb_dest) < 0 || skb_linearize(skb_src) < 0)
1017 skb_push(skb_dest, header_add);
1019 coded_packet = (struct batadv_coded_packet *)skb_dest->data;
1020 skb_reset_mac_header(skb_dest);
1022 coded_packet->header.packet_type = BATADV_CODED;
1023 coded_packet->header.version = BATADV_COMPAT_VERSION;
1024 coded_packet->header.ttl = packet1->header.ttl;
1026 /* Info about first unicast packet */
1027 memcpy(coded_packet->first_source, first_source, ETH_ALEN);
1028 memcpy(coded_packet->first_orig_dest, packet1->dest, ETH_ALEN);
1029 coded_packet->first_crc = packet_id1;
1030 coded_packet->first_ttvn = packet1->ttvn;
1032 /* Info about second unicast packet */
1033 memcpy(coded_packet->second_dest, second_dest, ETH_ALEN);
1034 memcpy(coded_packet->second_source, second_source, ETH_ALEN);
1035 memcpy(coded_packet->second_orig_dest, packet2->dest, ETH_ALEN);
1036 coded_packet->second_crc = packet_id2;
1037 coded_packet->second_ttl = packet2->header.ttl;
1038 coded_packet->second_ttvn = packet2->ttvn;
1039 coded_packet->coded_len = htons(coding_len);
1041 /* This is where the magic happens: Code skb_src into skb_dest */
1042 batadv_nc_memxor(skb_dest->data + coded_size,
1043 skb_src->data + unicast_size, coding_len);
1045 /* Update counters accordingly */
1046 if (BATADV_SKB_CB(skb_src)->decoded &&
1047 BATADV_SKB_CB(skb_dest)->decoded) {
1048 /* Both packets are recoded */
1049 count = skb_src->len + ETH_HLEN;
1050 count += skb_dest->len + ETH_HLEN;
1051 batadv_add_counter(bat_priv, BATADV_CNT_NC_RECODE, 2);
1052 batadv_add_counter(bat_priv, BATADV_CNT_NC_RECODE_BYTES, count);
1053 } else if (!BATADV_SKB_CB(skb_src)->decoded &&
1054 !BATADV_SKB_CB(skb_dest)->decoded) {
1055 /* Both packets are newly coded */
1056 count = skb_src->len + ETH_HLEN;
1057 count += skb_dest->len + ETH_HLEN;
1058 batadv_add_counter(bat_priv, BATADV_CNT_NC_CODE, 2);
1059 batadv_add_counter(bat_priv, BATADV_CNT_NC_CODE_BYTES, count);
1060 } else if (BATADV_SKB_CB(skb_src)->decoded &&
1061 !BATADV_SKB_CB(skb_dest)->decoded) {
1062 /* skb_src recoded and skb_dest is newly coded */
1063 batadv_inc_counter(bat_priv, BATADV_CNT_NC_RECODE);
1064 batadv_add_counter(bat_priv, BATADV_CNT_NC_RECODE_BYTES,
1065 skb_src->len + ETH_HLEN);
1066 batadv_inc_counter(bat_priv, BATADV_CNT_NC_CODE);
1067 batadv_add_counter(bat_priv, BATADV_CNT_NC_CODE_BYTES,
1068 skb_dest->len + ETH_HLEN);
1069 } else if (!BATADV_SKB_CB(skb_src)->decoded &&
1070 BATADV_SKB_CB(skb_dest)->decoded) {
1071 /* skb_src is newly coded and skb_dest is recoded */
1072 batadv_inc_counter(bat_priv, BATADV_CNT_NC_CODE);
1073 batadv_add_counter(bat_priv, BATADV_CNT_NC_CODE_BYTES,
1074 skb_src->len + ETH_HLEN);
1075 batadv_inc_counter(bat_priv, BATADV_CNT_NC_RECODE);
1076 batadv_add_counter(bat_priv, BATADV_CNT_NC_RECODE_BYTES,
1077 skb_dest->len + ETH_HLEN);
1080 /* skb_src is now coded into skb_dest, so free it */
1083 /* avoid duplicate free of skb from nc_packet */
1084 nc_packet->skb = NULL;
1085 batadv_nc_packet_free(nc_packet);
1087 /* Send the coded packet and return true */
1088 batadv_send_skb_packet(skb_dest, neigh_node->if_incoming, first_dest);
1092 batadv_neigh_node_free_ref(router_neigh);
1094 batadv_neigh_node_free_ref(router_coding);
1099 * batadv_nc_skb_coding_possible - true if a decoded skb is available at dst.
1100 * @skb: data skb to forward
1101 * @dst: destination mac address of the other skb to code with
1102 * @src: source mac address of skb
1104 * Whenever we network code a packet we have to check whether we received it in
1105 * a network coded form. If so, we may not be able to use it for coding because
1106 * some neighbors may also have received (overheard) the packet in the network
1107 * coded form without being able to decode it. It is hard to know which of the
1108 * neighboring nodes was able to decode the packet, therefore we can only
1109 * re-code the packet if the source of the previous encoded packet is involved.
1110 * Since the source encoded the packet we can be certain it has all necessary
1111 * decode information.
1113 * Returns true if coding of a decoded packet is allowed.
1115 static bool batadv_nc_skb_coding_possible(struct sk_buff *skb,
1116 uint8_t *dst, uint8_t *src)
1118 if (BATADV_SKB_CB(skb)->decoded && !batadv_compare_eth(dst, src))
1125 * batadv_nc_path_search - Find the coding path matching in_nc_node and
1126 * out_nc_node to retrieve a buffered packet that can be used for coding.
1127 * @bat_priv: the bat priv with all the soft interface information
1128 * @in_nc_node: pointer to skb next hop's neighbor nc node
1129 * @out_nc_node: pointer to skb source's neighbor nc node
1130 * @skb: data skb to forward
1131 * @eth_dst: next hop mac address of skb
1133 * Returns true if coding of a decoded skb is allowed.
1135 static struct batadv_nc_packet *
1136 batadv_nc_path_search(struct batadv_priv *bat_priv,
1137 struct batadv_nc_node *in_nc_node,
1138 struct batadv_nc_node *out_nc_node,
1139 struct sk_buff *skb,
1142 struct batadv_nc_path *nc_path, nc_path_key;
1143 struct batadv_nc_packet *nc_packet_out = NULL;
1144 struct batadv_nc_packet *nc_packet, *nc_packet_tmp;
1145 struct batadv_hashtable *hash = bat_priv->nc.coding_hash;
1151 /* Create almost path key */
1152 batadv_nc_hash_key_gen(&nc_path_key, in_nc_node->addr,
1154 idx = batadv_nc_hash_choose(&nc_path_key, hash->size);
1156 /* Check for coding opportunities in this nc_path */
1158 hlist_for_each_entry_rcu(nc_path, &hash->table[idx], hash_entry) {
1159 if (!batadv_compare_eth(nc_path->prev_hop, in_nc_node->addr))
1162 if (!batadv_compare_eth(nc_path->next_hop, out_nc_node->addr))
1165 spin_lock_bh(&nc_path->packet_list_lock);
1166 if (list_empty(&nc_path->packet_list)) {
1167 spin_unlock_bh(&nc_path->packet_list_lock);
1171 list_for_each_entry_safe(nc_packet, nc_packet_tmp,
1172 &nc_path->packet_list, list) {
1173 if (!batadv_nc_skb_coding_possible(nc_packet->skb,
1178 /* Coding opportunity is found! */
1179 list_del(&nc_packet->list);
1180 nc_packet_out = nc_packet;
1184 spin_unlock_bh(&nc_path->packet_list_lock);
1189 return nc_packet_out;
1193 * batadv_nc_skb_src_search - Loops through the list of neighoring nodes of the
1194 * skb's sender (may be equal to the originator).
1195 * @bat_priv: the bat priv with all the soft interface information
1196 * @skb: data skb to forward
1197 * @eth_dst: next hop mac address of skb
1198 * @eth_src: source mac address of skb
1199 * @in_nc_node: pointer to skb next hop's neighbor nc node
1201 * Returns an nc packet if a suitable coding packet was found, NULL otherwise.
1203 static struct batadv_nc_packet *
1204 batadv_nc_skb_src_search(struct batadv_priv *bat_priv,
1205 struct sk_buff *skb,
1208 struct batadv_nc_node *in_nc_node)
1210 struct batadv_orig_node *orig_node;
1211 struct batadv_nc_node *out_nc_node;
1212 struct batadv_nc_packet *nc_packet = NULL;
1214 orig_node = batadv_orig_hash_find(bat_priv, eth_src);
1219 list_for_each_entry_rcu(out_nc_node,
1220 &orig_node->out_coding_list, list) {
1221 /* Check if the skb is decoded and if recoding is possible */
1222 if (!batadv_nc_skb_coding_possible(skb,
1223 out_nc_node->addr, eth_src))
1226 /* Search for an opportunity in this nc_path */
1227 nc_packet = batadv_nc_path_search(bat_priv, in_nc_node,
1228 out_nc_node, skb, eth_dst);
1234 batadv_orig_node_free_ref(orig_node);
1239 * batadv_nc_skb_store_before_coding - set the ethernet src and dst of the
1240 * unicast skb before it is stored for use in later decoding
1241 * @bat_priv: the bat priv with all the soft interface information
1242 * @skb: data skb to store
1243 * @eth_dst_new: new destination mac address of skb
1245 static void batadv_nc_skb_store_before_coding(struct batadv_priv *bat_priv,
1246 struct sk_buff *skb,
1247 uint8_t *eth_dst_new)
1249 struct ethhdr *ethhdr;
1251 /* Copy skb header to change the mac header */
1252 skb = pskb_copy(skb, GFP_ATOMIC);
1256 /* Set the mac header as if we actually sent the packet uncoded */
1257 ethhdr = (struct ethhdr *)skb_mac_header(skb);
1258 memcpy(ethhdr->h_source, ethhdr->h_dest, ETH_ALEN);
1259 memcpy(ethhdr->h_dest, eth_dst_new, ETH_ALEN);
1261 /* Set data pointer to MAC header to mimic packets from our tx path */
1262 skb_push(skb, ETH_HLEN);
1264 /* Add the packet to the decoding packet pool */
1265 batadv_nc_skb_store_for_decoding(bat_priv, skb);
1267 /* batadv_nc_skb_store_for_decoding() clones the skb, so we must free
1274 * batadv_nc_skb_dst_search - Loops through list of neighboring nodes to dst.
1275 * @skb: data skb to forward
1276 * @neigh_node: next hop to forward packet to
1277 * @ethhdr: pointer to the ethernet header inside the skb
1279 * Loops through list of neighboring nodes the next hop has a good connection to
1280 * (receives OGMs with a sufficient quality). We need to find a neighbor of our
1281 * next hop that potentially sent a packet which our next hop also received
1282 * (overheard) and has stored for later decoding.
1284 * Returns true if the skb was consumed (encoded packet sent) or false otherwise
1286 static bool batadv_nc_skb_dst_search(struct sk_buff *skb,
1287 struct batadv_neigh_node *neigh_node,
1288 struct ethhdr *ethhdr)
1290 struct net_device *netdev = neigh_node->if_incoming->soft_iface;
1291 struct batadv_priv *bat_priv = netdev_priv(netdev);
1292 struct batadv_orig_node *orig_node = neigh_node->orig_node;
1293 struct batadv_nc_node *nc_node;
1294 struct batadv_nc_packet *nc_packet = NULL;
1297 list_for_each_entry_rcu(nc_node, &orig_node->in_coding_list, list) {
1298 /* Search for coding opportunity with this in_nc_node */
1299 nc_packet = batadv_nc_skb_src_search(bat_priv, skb,
1301 ethhdr->h_source, nc_node);
1303 /* Opportunity was found, so stop searching */
1312 /* Save packets for later decoding */
1313 batadv_nc_skb_store_before_coding(bat_priv, skb,
1315 batadv_nc_skb_store_before_coding(bat_priv, nc_packet->skb,
1316 nc_packet->neigh_node->addr);
1318 /* Code and send packets */
1319 if (batadv_nc_code_packets(bat_priv, skb, ethhdr, nc_packet,
1323 /* out of mem ? Coding failed - we have to free the buffered packet
1324 * to avoid memleaks. The skb passed as argument will be dealt with
1325 * by the calling function.
1327 batadv_nc_send_packet(nc_packet);
1332 * batadv_nc_skb_add_to_path - buffer skb for later encoding / decoding
1333 * @skb: skb to add to path
1334 * @nc_path: path to add skb to
1335 * @neigh_node: next hop to forward packet to
1336 * @packet_id: checksum to identify packet
1338 * Returns true if the packet was buffered or false in case of an error.
1340 static bool batadv_nc_skb_add_to_path(struct sk_buff *skb,
1341 struct batadv_nc_path *nc_path,
1342 struct batadv_neigh_node *neigh_node,
1345 struct batadv_nc_packet *nc_packet;
1347 nc_packet = kzalloc(sizeof(*nc_packet), GFP_ATOMIC);
1351 /* Initialize nc_packet */
1352 nc_packet->timestamp = jiffies;
1353 nc_packet->packet_id = packet_id;
1354 nc_packet->skb = skb;
1355 nc_packet->neigh_node = neigh_node;
1356 nc_packet->nc_path = nc_path;
1358 /* Add coding packet to list */
1359 spin_lock_bh(&nc_path->packet_list_lock);
1360 list_add_tail(&nc_packet->list, &nc_path->packet_list);
1361 spin_unlock_bh(&nc_path->packet_list_lock);
1367 * batadv_nc_skb_forward - try to code a packet or add it to the coding packet
1369 * @skb: data skb to forward
1370 * @neigh_node: next hop to forward packet to
1371 * @ethhdr: pointer to the ethernet header inside the skb
1373 * Returns true if the skb was consumed (encoded packet sent) or false otherwise
1375 bool batadv_nc_skb_forward(struct sk_buff *skb,
1376 struct batadv_neigh_node *neigh_node,
1377 struct ethhdr *ethhdr)
1379 const struct net_device *netdev = neigh_node->if_incoming->soft_iface;
1380 struct batadv_priv *bat_priv = netdev_priv(netdev);
1381 struct batadv_unicast_packet *packet;
1382 struct batadv_nc_path *nc_path;
1386 /* Check if network coding is enabled */
1387 if (!atomic_read(&bat_priv->network_coding))
1390 /* We only handle unicast packets */
1391 payload = skb_network_header(skb);
1392 packet = (struct batadv_unicast_packet *)payload;
1393 if (packet->header.packet_type != BATADV_UNICAST)
1396 /* Try to find a coding opportunity and send the skb if one is found */
1397 if (batadv_nc_skb_dst_search(skb, neigh_node, ethhdr))
1400 /* Find or create a nc_path for this src-dst pair */
1401 nc_path = batadv_nc_get_path(bat_priv,
1402 bat_priv->nc.coding_hash,
1409 /* Add skb to nc_path */
1410 packet_id = batadv_skb_crc32(skb, payload + sizeof(*packet));
1411 if (!batadv_nc_skb_add_to_path(skb, nc_path, neigh_node, packet_id))
1414 /* Packet is consumed */
1418 batadv_nc_path_free_ref(nc_path);
1420 /* Packet is not consumed */
1425 * batadv_nc_skb_store_for_decoding - save a clone of the skb which can be used
1426 * when decoding coded packets
1427 * @bat_priv: the bat priv with all the soft interface information
1428 * @skb: data skb to store
1430 void batadv_nc_skb_store_for_decoding(struct batadv_priv *bat_priv,
1431 struct sk_buff *skb)
1433 struct batadv_unicast_packet *packet;
1434 struct batadv_nc_path *nc_path;
1435 struct ethhdr *ethhdr = (struct ethhdr *)skb_mac_header(skb);
1439 /* Check if network coding is enabled */
1440 if (!atomic_read(&bat_priv->network_coding))
1443 /* Check for supported packet type */
1444 payload = skb_network_header(skb);
1445 packet = (struct batadv_unicast_packet *)payload;
1446 if (packet->header.packet_type != BATADV_UNICAST)
1449 /* Find existing nc_path or create a new */
1450 nc_path = batadv_nc_get_path(bat_priv,
1451 bat_priv->nc.decoding_hash,
1458 /* Clone skb and adjust skb->data to point at batman header */
1459 skb = skb_clone(skb, GFP_ATOMIC);
1463 if (unlikely(!pskb_may_pull(skb, ETH_HLEN)))
1466 if (unlikely(!skb_pull_rcsum(skb, ETH_HLEN)))
1469 /* Add skb to nc_path */
1470 packet_id = batadv_skb_crc32(skb, payload + sizeof(*packet));
1471 if (!batadv_nc_skb_add_to_path(skb, nc_path, NULL, packet_id))
1474 batadv_inc_counter(bat_priv, BATADV_CNT_NC_BUFFER);
1480 batadv_nc_path_free_ref(nc_path);
1486 * batadv_nc_skb_store_sniffed_unicast - check if a received unicast packet
1487 * should be saved in the decoding buffer and, if so, store it there
1488 * @bat_priv: the bat priv with all the soft interface information
1489 * @skb: unicast skb to store
1491 void batadv_nc_skb_store_sniffed_unicast(struct batadv_priv *bat_priv,
1492 struct sk_buff *skb)
1494 struct ethhdr *ethhdr = (struct ethhdr *)skb_mac_header(skb);
1496 if (batadv_is_my_mac(bat_priv, ethhdr->h_dest))
1499 /* Set data pointer to MAC header to mimic packets from our tx path */
1500 skb_push(skb, ETH_HLEN);
1502 batadv_nc_skb_store_for_decoding(bat_priv, skb);
1506 * batadv_nc_skb_decode_packet - decode given skb using the decode data stored
1508 * @bat_priv: the bat priv with all the soft interface information
1509 * @skb: unicast skb to decode
1510 * @nc_packet: decode data needed to decode the skb
1512 * Returns pointer to decoded unicast packet if the packet was decoded or NULL
1513 * in case of an error.
1515 static struct batadv_unicast_packet *
1516 batadv_nc_skb_decode_packet(struct batadv_priv *bat_priv, struct sk_buff *skb,
1517 struct batadv_nc_packet *nc_packet)
1519 const int h_size = sizeof(struct batadv_unicast_packet);
1520 const int h_diff = sizeof(struct batadv_coded_packet) - h_size;
1521 struct batadv_unicast_packet *unicast_packet;
1522 struct batadv_coded_packet coded_packet_tmp;
1523 struct ethhdr *ethhdr, ethhdr_tmp;
1524 uint8_t *orig_dest, ttl, ttvn;
1525 unsigned int coding_len;
1528 /* Save headers temporarily */
1529 memcpy(&coded_packet_tmp, skb->data, sizeof(coded_packet_tmp));
1530 memcpy(ðhdr_tmp, skb_mac_header(skb), sizeof(ethhdr_tmp));
1532 if (skb_cow(skb, 0) < 0)
1535 if (unlikely(!skb_pull_rcsum(skb, h_diff)))
1538 /* Data points to batman header, so set mac header 14 bytes before
1539 * and network to data
1541 skb_set_mac_header(skb, -ETH_HLEN);
1542 skb_reset_network_header(skb);
1544 /* Reconstruct original mac header */
1545 ethhdr = (struct ethhdr *)skb_mac_header(skb);
1546 memcpy(ethhdr, ðhdr_tmp, sizeof(*ethhdr));
1548 /* Select the correct unicast header information based on the location
1549 * of our mac address in the coded_packet header
1551 if (batadv_is_my_mac(bat_priv, coded_packet_tmp.second_dest)) {
1552 /* If we are the second destination the packet was overheard,
1553 * so the Ethernet address must be copied to h_dest and
1554 * pkt_type changed from PACKET_OTHERHOST to PACKET_HOST
1556 memcpy(ethhdr->h_dest, coded_packet_tmp.second_dest, ETH_ALEN);
1557 skb->pkt_type = PACKET_HOST;
1559 orig_dest = coded_packet_tmp.second_orig_dest;
1560 ttl = coded_packet_tmp.second_ttl;
1561 ttvn = coded_packet_tmp.second_ttvn;
1563 orig_dest = coded_packet_tmp.first_orig_dest;
1564 ttl = coded_packet_tmp.header.ttl;
1565 ttvn = coded_packet_tmp.first_ttvn;
1568 coding_len = ntohs(coded_packet_tmp.coded_len);
1570 if (coding_len > skb->len)
1573 /* Here the magic is reversed:
1574 * extract the missing packet from the received coded packet
1576 batadv_nc_memxor(skb->data + h_size,
1577 nc_packet->skb->data + h_size,
1580 /* Resize decoded skb if decoded with larger packet */
1581 if (nc_packet->skb->len > coding_len + h_size) {
1582 err = pskb_trim_rcsum(skb, coding_len + h_size);
1587 /* Create decoded unicast packet */
1588 unicast_packet = (struct batadv_unicast_packet *)skb->data;
1589 unicast_packet->header.packet_type = BATADV_UNICAST;
1590 unicast_packet->header.version = BATADV_COMPAT_VERSION;
1591 unicast_packet->header.ttl = ttl;
1592 memcpy(unicast_packet->dest, orig_dest, ETH_ALEN);
1593 unicast_packet->ttvn = ttvn;
1595 batadv_nc_packet_free(nc_packet);
1596 return unicast_packet;
1600 * batadv_nc_find_decoding_packet - search through buffered decoding data to
1601 * find the data needed to decode the coded packet
1602 * @bat_priv: the bat priv with all the soft interface information
1603 * @ethhdr: pointer to the ethernet header inside the coded packet
1604 * @coded: coded packet we try to find decode data for
1606 * Returns pointer to nc packet if the needed data was found or NULL otherwise.
1608 static struct batadv_nc_packet *
1609 batadv_nc_find_decoding_packet(struct batadv_priv *bat_priv,
1610 struct ethhdr *ethhdr,
1611 struct batadv_coded_packet *coded)
1613 struct batadv_hashtable *hash = bat_priv->nc.decoding_hash;
1614 struct batadv_nc_packet *tmp_nc_packet, *nc_packet = NULL;
1615 struct batadv_nc_path *nc_path, nc_path_key;
1616 uint8_t *dest, *source;
1623 /* Select the correct packet id based on the location of our mac-addr */
1624 dest = ethhdr->h_source;
1625 if (!batadv_is_my_mac(bat_priv, coded->second_dest)) {
1626 source = coded->second_source;
1627 packet_id = coded->second_crc;
1629 source = coded->first_source;
1630 packet_id = coded->first_crc;
1633 batadv_nc_hash_key_gen(&nc_path_key, source, dest);
1634 index = batadv_nc_hash_choose(&nc_path_key, hash->size);
1636 /* Search for matching coding path */
1638 hlist_for_each_entry_rcu(nc_path, &hash->table[index], hash_entry) {
1639 /* Find matching nc_packet */
1640 spin_lock_bh(&nc_path->packet_list_lock);
1641 list_for_each_entry(tmp_nc_packet,
1642 &nc_path->packet_list, list) {
1643 if (packet_id == tmp_nc_packet->packet_id) {
1644 list_del(&tmp_nc_packet->list);
1646 nc_packet = tmp_nc_packet;
1650 spin_unlock_bh(&nc_path->packet_list_lock);
1658 batadv_dbg(BATADV_DBG_NC, bat_priv,
1659 "No decoding packet found for %u\n", packet_id);
1665 * batadv_nc_recv_coded_packet - try to decode coded packet and enqueue the
1666 * resulting unicast packet
1667 * @skb: incoming coded packet
1668 * @recv_if: pointer to interface this packet was received on
1670 static int batadv_nc_recv_coded_packet(struct sk_buff *skb,
1671 struct batadv_hard_iface *recv_if)
1673 struct batadv_priv *bat_priv = netdev_priv(recv_if->soft_iface);
1674 struct batadv_unicast_packet *unicast_packet;
1675 struct batadv_coded_packet *coded_packet;
1676 struct batadv_nc_packet *nc_packet;
1677 struct ethhdr *ethhdr;
1678 int hdr_size = sizeof(*coded_packet);
1680 /* Check if network coding is enabled */
1681 if (!atomic_read(&bat_priv->network_coding))
1684 /* Make sure we can access (and remove) header */
1685 if (unlikely(!pskb_may_pull(skb, hdr_size)))
1688 coded_packet = (struct batadv_coded_packet *)skb->data;
1689 ethhdr = (struct ethhdr *)skb_mac_header(skb);
1691 /* Verify frame is destined for us */
1692 if (!batadv_is_my_mac(bat_priv, ethhdr->h_dest) &&
1693 !batadv_is_my_mac(bat_priv, coded_packet->second_dest))
1696 /* Update stat counter */
1697 if (batadv_is_my_mac(bat_priv, coded_packet->second_dest))
1698 batadv_inc_counter(bat_priv, BATADV_CNT_NC_SNIFFED);
1700 nc_packet = batadv_nc_find_decoding_packet(bat_priv, ethhdr,
1703 batadv_inc_counter(bat_priv, BATADV_CNT_NC_DECODE_FAILED);
1707 /* Make skb's linear, because decoding accesses the entire buffer */
1708 if (skb_linearize(skb) < 0)
1709 goto free_nc_packet;
1711 if (skb_linearize(nc_packet->skb) < 0)
1712 goto free_nc_packet;
1714 /* Decode the packet */
1715 unicast_packet = batadv_nc_skb_decode_packet(bat_priv, skb, nc_packet);
1716 if (!unicast_packet) {
1717 batadv_inc_counter(bat_priv, BATADV_CNT_NC_DECODE_FAILED);
1718 goto free_nc_packet;
1721 /* Mark packet as decoded to do correct recoding when forwarding */
1722 BATADV_SKB_CB(skb)->decoded = true;
1723 batadv_inc_counter(bat_priv, BATADV_CNT_NC_DECODE);
1724 batadv_add_counter(bat_priv, BATADV_CNT_NC_DECODE_BYTES,
1725 skb->len + ETH_HLEN);
1726 return batadv_recv_unicast_packet(skb, recv_if);
1729 batadv_nc_packet_free(nc_packet);
1734 * batadv_nc_mesh_free - clean up network coding memory
1735 * @bat_priv: the bat priv with all the soft interface information
1737 void batadv_nc_mesh_free(struct batadv_priv *bat_priv)
1739 cancel_delayed_work_sync(&bat_priv->nc.work);
1741 batadv_nc_purge_paths(bat_priv, bat_priv->nc.coding_hash, NULL);
1742 batadv_hash_destroy(bat_priv->nc.coding_hash);
1743 batadv_nc_purge_paths(bat_priv, bat_priv->nc.decoding_hash, NULL);
1744 batadv_hash_destroy(bat_priv->nc.decoding_hash);
1748 * batadv_nc_nodes_seq_print_text - print the nc node information
1749 * @seq: seq file to print on
1752 int batadv_nc_nodes_seq_print_text(struct seq_file *seq, void *offset)
1754 struct net_device *net_dev = (struct net_device *)seq->private;
1755 struct batadv_priv *bat_priv = netdev_priv(net_dev);
1756 struct batadv_hashtable *hash = bat_priv->orig_hash;
1757 struct batadv_hard_iface *primary_if;
1758 struct hlist_head *head;
1759 struct batadv_orig_node *orig_node;
1760 struct batadv_nc_node *nc_node;
1763 primary_if = batadv_seq_print_text_primary_if_get(seq);
1767 /* Traverse list of originators */
1768 for (i = 0; i < hash->size; i++) {
1769 head = &hash->table[i];
1771 /* For each orig_node in this bin */
1773 hlist_for_each_entry_rcu(orig_node, head, hash_entry) {
1774 seq_printf(seq, "Node: %pM\n", orig_node->orig);
1776 seq_puts(seq, " Ingoing: ");
1777 /* For each in_nc_node to this orig_node */
1778 list_for_each_entry_rcu(nc_node,
1779 &orig_node->in_coding_list,
1781 seq_printf(seq, "%pM ",
1783 seq_puts(seq, "\n");
1785 seq_puts(seq, " Outgoing: ");
1786 /* For out_nc_node to this orig_node */
1787 list_for_each_entry_rcu(nc_node,
1788 &orig_node->out_coding_list,
1790 seq_printf(seq, "%pM ",
1792 seq_puts(seq, "\n\n");
1799 batadv_hardif_free_ref(primary_if);
1804 * batadv_nc_init_debugfs - create nc folder and related files in debugfs
1805 * @bat_priv: the bat priv with all the soft interface information
1807 int batadv_nc_init_debugfs(struct batadv_priv *bat_priv)
1809 struct dentry *nc_dir, *file;
1811 nc_dir = debugfs_create_dir("nc", bat_priv->debug_dir);
1815 file = debugfs_create_u8("min_tq", S_IRUGO | S_IWUSR, nc_dir,
1816 &bat_priv->nc.min_tq);
1820 file = debugfs_create_u32("max_fwd_delay", S_IRUGO | S_IWUSR, nc_dir,
1821 &bat_priv->nc.max_fwd_delay);
1825 file = debugfs_create_u32("max_buffer_time", S_IRUGO | S_IWUSR, nc_dir,
1826 &bat_priv->nc.max_buffer_time);