~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/net/batman-adv/network-coding.c

Version: ~ [ linux-5.13-rc2 ] ~ [ linux-5.12.4 ] ~ [ linux-5.11.21 ] ~ [ linux-5.10.37 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.119 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.190 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.232 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.268 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.268 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.18.140 ] ~ [ linux-3.16.85 ] ~ [ linux-3.14.79 ] ~ [ linux-3.12.74 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 /* Copyright (C) 2012-2016  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, see <http://www.gnu.org/licenses/>.
 16  */
 17 
 18 #include "network-coding.h"
 19 #include "main.h"
 20 
 21 #include <linux/atomic.h>
 22 #include <linux/bitops.h>
 23 #include <linux/byteorder/generic.h>
 24 #include <linux/compiler.h>
 25 #include <linux/debugfs.h>
 26 #include <linux/errno.h>
 27 #include <linux/etherdevice.h>
 28 #include <linux/fs.h>
 29 #include <linux/if_ether.h>
 30 #include <linux/if_packet.h>
 31 #include <linux/init.h>
 32 #include <linux/jhash.h>
 33 #include <linux/jiffies.h>
 34 #include <linux/kernel.h>
 35 #include <linux/kref.h>
 36 #include <linux/list.h>
 37 #include <linux/lockdep.h>
 38 #include <linux/netdevice.h>
 39 #include <linux/printk.h>
 40 #include <linux/random.h>
 41 #include <linux/rculist.h>
 42 #include <linux/rcupdate.h>
 43 #include <linux/seq_file.h>
 44 #include <linux/skbuff.h>
 45 #include <linux/slab.h>
 46 #include <linux/spinlock.h>
 47 #include <linux/stat.h>
 48 #include <linux/stddef.h>
 49 #include <linux/string.h>
 50 #include <linux/workqueue.h>
 51 
 52 #include "hard-interface.h"
 53 #include "hash.h"
 54 #include "originator.h"
 55 #include "packet.h"
 56 #include "routing.h"
 57 #include "send.h"
 58 
 59 static struct lock_class_key batadv_nc_coding_hash_lock_class_key;
 60 static struct lock_class_key batadv_nc_decoding_hash_lock_class_key;
 61 
 62 static void batadv_nc_worker(struct work_struct *work);
 63 static int batadv_nc_recv_coded_packet(struct sk_buff *skb,
 64                                        struct batadv_hard_iface *recv_if);
 65 
 66 /**
 67  * batadv_nc_init - one-time initialization for network coding
 68  *
 69  * Return: 0 on success or negative error number in case of failure
 70  */
 71 int __init batadv_nc_init(void)
 72 {
 73         int ret;
 74 
 75         /* Register our packet type */
 76         ret = batadv_recv_handler_register(BATADV_CODED,
 77                                            batadv_nc_recv_coded_packet);
 78 
 79         return ret;
 80 }
 81 
 82 /**
 83  * batadv_nc_start_timer - initialise the nc periodic worker
 84  * @bat_priv: the bat priv with all the soft interface information
 85  */
 86 static void batadv_nc_start_timer(struct batadv_priv *bat_priv)
 87 {
 88         queue_delayed_work(batadv_event_workqueue, &bat_priv->nc.work,
 89                            msecs_to_jiffies(10));
 90 }
 91 
 92 /**
 93  * batadv_nc_tvlv_container_update - update the network coding tvlv container
 94  *  after network coding setting change
 95  * @bat_priv: the bat priv with all the soft interface information
 96  */
 97 static void batadv_nc_tvlv_container_update(struct batadv_priv *bat_priv)
 98 {
 99         char nc_mode;
100 
101         nc_mode = atomic_read(&bat_priv->network_coding);
102 
103         switch (nc_mode) {
104         case 0:
105                 batadv_tvlv_container_unregister(bat_priv, BATADV_TVLV_NC, 1);
106                 break;
107         case 1:
108                 batadv_tvlv_container_register(bat_priv, BATADV_TVLV_NC, 1,
109                                                NULL, 0);
110                 break;
111         }
112 }
113 
114 /**
115  * batadv_nc_status_update - update the network coding tvlv container after
116  *  network coding setting change
117  * @net_dev: the soft interface net device
118  */
119 void batadv_nc_status_update(struct net_device *net_dev)
120 {
121         struct batadv_priv *bat_priv = netdev_priv(net_dev);
122 
123         batadv_nc_tvlv_container_update(bat_priv);
124 }
125 
126 /**
127  * batadv_nc_tvlv_ogm_handler_v1 - process incoming nc tvlv container
128  * @bat_priv: the bat priv with all the soft interface information
129  * @orig: the orig_node of the ogm
130  * @flags: flags indicating the tvlv state (see batadv_tvlv_handler_flags)
131  * @tvlv_value: tvlv buffer containing the gateway data
132  * @tvlv_value_len: tvlv buffer length
133  */
134 static void batadv_nc_tvlv_ogm_handler_v1(struct batadv_priv *bat_priv,
135                                           struct batadv_orig_node *orig,
136                                           u8 flags,
137                                           void *tvlv_value, u16 tvlv_value_len)
138 {
139         if (flags & BATADV_TVLV_HANDLER_OGM_CIFNOTFND)
140                 clear_bit(BATADV_ORIG_CAPA_HAS_NC, &orig->capabilities);
141         else
142                 set_bit(BATADV_ORIG_CAPA_HAS_NC, &orig->capabilities);
143 }
144 
145 /**
146  * batadv_nc_mesh_init - initialise coding hash table and start house keeping
147  * @bat_priv: the bat priv with all the soft interface information
148  *
149  * Return: 0 on success or negative error number in case of failure
150  */
151 int batadv_nc_mesh_init(struct batadv_priv *bat_priv)
152 {
153         bat_priv->nc.timestamp_fwd_flush = jiffies;
154         bat_priv->nc.timestamp_sniffed_purge = jiffies;
155 
156         if (bat_priv->nc.coding_hash || bat_priv->nc.decoding_hash)
157                 return 0;
158 
159         bat_priv->nc.coding_hash = batadv_hash_new(128);
160         if (!bat_priv->nc.coding_hash)
161                 goto err;
162 
163         batadv_hash_set_lock_class(bat_priv->nc.coding_hash,
164                                    &batadv_nc_coding_hash_lock_class_key);
165 
166         bat_priv->nc.decoding_hash = batadv_hash_new(128);
167         if (!bat_priv->nc.decoding_hash)
168                 goto err;
169 
170         batadv_hash_set_lock_class(bat_priv->nc.decoding_hash,
171                                    &batadv_nc_decoding_hash_lock_class_key);
172 
173         INIT_DELAYED_WORK(&bat_priv->nc.work, batadv_nc_worker);
174         batadv_nc_start_timer(bat_priv);
175 
176         batadv_tvlv_handler_register(bat_priv, batadv_nc_tvlv_ogm_handler_v1,
177                                      NULL, BATADV_TVLV_NC, 1,
178                                      BATADV_TVLV_HANDLER_OGM_CIFNOTFND);
179         batadv_nc_tvlv_container_update(bat_priv);
180         return 0;
181 
182 err:
183         return -ENOMEM;
184 }
185 
186 /**
187  * batadv_nc_init_bat_priv - initialise the nc specific bat_priv variables
188  * @bat_priv: the bat priv with all the soft interface information
189  */
190 void batadv_nc_init_bat_priv(struct batadv_priv *bat_priv)
191 {
192         atomic_set(&bat_priv->network_coding, 0);
193         bat_priv->nc.min_tq = 200;
194         bat_priv->nc.max_fwd_delay = 10;
195         bat_priv->nc.max_buffer_time = 200;
196 }
197 
198 /**
199  * batadv_nc_init_orig - initialise the nc fields of an orig_node
200  * @orig_node: the orig_node which is going to be initialised
201  */
202 void batadv_nc_init_orig(struct batadv_orig_node *orig_node)
203 {
204         INIT_LIST_HEAD(&orig_node->in_coding_list);
205         INIT_LIST_HEAD(&orig_node->out_coding_list);
206         spin_lock_init(&orig_node->in_coding_list_lock);
207         spin_lock_init(&orig_node->out_coding_list_lock);
208 }
209 
210 /**
211  * batadv_nc_node_release - release nc_node from lists and queue for free after
212  *  rcu grace period
213  * @ref: kref pointer of the nc_node
214  */
215 static void batadv_nc_node_release(struct kref *ref)
216 {
217         struct batadv_nc_node *nc_node;
218 
219         nc_node = container_of(ref, struct batadv_nc_node, refcount);
220 
221         batadv_orig_node_put(nc_node->orig_node);
222         kfree_rcu(nc_node, rcu);
223 }
224 
225 /**
226  * batadv_nc_node_put - decrement the nc_node refcounter and possibly
227  *  release it
228  * @nc_node: nc_node to be free'd
229  */
230 static void batadv_nc_node_put(struct batadv_nc_node *nc_node)
231 {
232         kref_put(&nc_node->refcount, batadv_nc_node_release);
233 }
234 
235 /**
236  * batadv_nc_path_release - release nc_path from lists and queue for free after
237  *  rcu grace period
238  * @ref: kref pointer of the nc_path
239  */
240 static void batadv_nc_path_release(struct kref *ref)
241 {
242         struct batadv_nc_path *nc_path;
243 
244         nc_path = container_of(ref, struct batadv_nc_path, refcount);
245 
246         kfree_rcu(nc_path, rcu);
247 }
248 
249 /**
250  * batadv_nc_path_put - decrement the nc_path refcounter and possibly
251  *  release it
252  * @nc_path: nc_path to be free'd
253  */
254 static void batadv_nc_path_put(struct batadv_nc_path *nc_path)
255 {
256         kref_put(&nc_path->refcount, batadv_nc_path_release);
257 }
258 
259 /**
260  * batadv_nc_packet_free - frees nc packet
261  * @nc_packet: the nc packet to free
262  */
263 static void batadv_nc_packet_free(struct batadv_nc_packet *nc_packet)
264 {
265         kfree_skb(nc_packet->skb);
266         batadv_nc_path_put(nc_packet->nc_path);
267         kfree(nc_packet);
268 }
269 
270 /**
271  * batadv_nc_to_purge_nc_node - checks whether an nc node has to be purged
272  * @bat_priv: the bat priv with all the soft interface information
273  * @nc_node: the nc node to check
274  *
275  * Return: true if the entry has to be purged now, false otherwise
276  */
277 static bool batadv_nc_to_purge_nc_node(struct batadv_priv *bat_priv,
278                                        struct batadv_nc_node *nc_node)
279 {
280         if (atomic_read(&bat_priv->mesh_state) != BATADV_MESH_ACTIVE)
281                 return true;
282 
283         return batadv_has_timed_out(nc_node->last_seen, BATADV_NC_NODE_TIMEOUT);
284 }
285 
286 /**
287  * batadv_nc_to_purge_nc_path_coding - checks whether an nc path has timed out
288  * @bat_priv: the bat priv with all the soft interface information
289  * @nc_path: the nc path to check
290  *
291  * Return: true if the entry has to be purged now, false otherwise
292  */
293 static bool batadv_nc_to_purge_nc_path_coding(struct batadv_priv *bat_priv,
294                                               struct batadv_nc_path *nc_path)
295 {
296         if (atomic_read(&bat_priv->mesh_state) != BATADV_MESH_ACTIVE)
297                 return true;
298 
299         /* purge the path when no packets has been added for 10 times the
300          * max_fwd_delay time
301          */
302         return batadv_has_timed_out(nc_path->last_valid,
303                                     bat_priv->nc.max_fwd_delay * 10);
304 }
305 
306 /**
307  * batadv_nc_to_purge_nc_path_decoding - checks whether an nc path has timed out
308  * @bat_priv: the bat priv with all the soft interface information
309  * @nc_path: the nc path to check
310  *
311  * Return: true if the entry has to be purged now, false otherwise
312  */
313 static bool batadv_nc_to_purge_nc_path_decoding(struct batadv_priv *bat_priv,
314                                                 struct batadv_nc_path *nc_path)
315 {
316         if (atomic_read(&bat_priv->mesh_state) != BATADV_MESH_ACTIVE)
317                 return true;
318 
319         /* purge the path when no packets has been added for 10 times the
320          * max_buffer time
321          */
322         return batadv_has_timed_out(nc_path->last_valid,
323                                     bat_priv->nc.max_buffer_time * 10);
324 }
325 
326 /**
327  * batadv_nc_purge_orig_nc_nodes - go through list of nc nodes and purge stale
328  *  entries
329  * @bat_priv: the bat priv with all the soft interface information
330  * @list: list of nc nodes
331  * @lock: nc node list lock
332  * @to_purge: function in charge to decide whether an entry has to be purged or
333  *            not. This function takes the nc node as argument and has to return
334  *            a boolean value: true if the entry has to be deleted, false
335  *            otherwise
336  */
337 static void
338 batadv_nc_purge_orig_nc_nodes(struct batadv_priv *bat_priv,
339                               struct list_head *list,
340                               spinlock_t *lock,
341                               bool (*to_purge)(struct batadv_priv *,
342                                                struct batadv_nc_node *))
343 {
344         struct batadv_nc_node *nc_node, *nc_node_tmp;
345 
346         /* For each nc_node in list */
347         spin_lock_bh(lock);
348         list_for_each_entry_safe(nc_node, nc_node_tmp, list, list) {
349                 /* if an helper function has been passed as parameter,
350                  * ask it if the entry has to be purged or not
351                  */
352                 if (to_purge && !to_purge(bat_priv, nc_node))
353                         continue;
354 
355                 batadv_dbg(BATADV_DBG_NC, bat_priv,
356                            "Removing nc_node %pM -> %pM\n",
357                            nc_node->addr, nc_node->orig_node->orig);
358                 list_del_rcu(&nc_node->list);
359                 batadv_nc_node_put(nc_node);
360         }
361         spin_unlock_bh(lock);
362 }
363 
364 /**
365  * batadv_nc_purge_orig - purges all nc node data attached of the given
366  *  originator
367  * @bat_priv: the bat priv with all the soft interface information
368  * @orig_node: orig_node with the nc node entries to be purged
369  * @to_purge: function in charge to decide whether an entry has to be purged or
370  *            not. This function takes the nc node as argument and has to return
371  *            a boolean value: true is the entry has to be deleted, false
372  *            otherwise
373  */
374 void batadv_nc_purge_orig(struct batadv_priv *bat_priv,
375                           struct batadv_orig_node *orig_node,
376                           bool (*to_purge)(struct batadv_priv *,
377                                            struct batadv_nc_node *))
378 {
379         /* Check ingoing nc_node's of this orig_node */
380         batadv_nc_purge_orig_nc_nodes(bat_priv, &orig_node->in_coding_list,
381                                       &orig_node->in_coding_list_lock,
382                                       to_purge);
383 
384         /* Check outgoing nc_node's of this orig_node */
385         batadv_nc_purge_orig_nc_nodes(bat_priv, &orig_node->out_coding_list,
386                                       &orig_node->out_coding_list_lock,
387                                       to_purge);
388 }
389 
390 /**
391  * batadv_nc_purge_orig_hash - traverse entire originator hash to check if they
392  *  have timed out nc nodes
393  * @bat_priv: the bat priv with all the soft interface information
394  */
395 static void batadv_nc_purge_orig_hash(struct batadv_priv *bat_priv)
396 {
397         struct batadv_hashtable *hash = bat_priv->orig_hash;
398         struct hlist_head *head;
399         struct batadv_orig_node *orig_node;
400         u32 i;
401 
402         if (!hash)
403                 return;
404 
405         /* For each orig_node */
406         for (i = 0; i < hash->size; i++) {
407                 head = &hash->table[i];
408 
409                 rcu_read_lock();
410                 hlist_for_each_entry_rcu(orig_node, head, hash_entry)
411                         batadv_nc_purge_orig(bat_priv, orig_node,
412                                              batadv_nc_to_purge_nc_node);
413                 rcu_read_unlock();
414         }
415 }
416 
417 /**
418  * batadv_nc_purge_paths - traverse all nc paths part of the hash and remove
419  *  unused ones
420  * @bat_priv: the bat priv with all the soft interface information
421  * @hash: hash table containing the nc paths to check
422  * @to_purge: function in charge to decide whether an entry has to be purged or
423  *            not. This function takes the nc node as argument and has to return
424  *            a boolean value: true is the entry has to be deleted, false
425  *            otherwise
426  */
427 static void batadv_nc_purge_paths(struct batadv_priv *bat_priv,
428                                   struct batadv_hashtable *hash,
429                                   bool (*to_purge)(struct batadv_priv *,
430                                                    struct batadv_nc_path *))
431 {
432         struct hlist_head *head;
433         struct hlist_node *node_tmp;
434         struct batadv_nc_path *nc_path;
435         spinlock_t *lock; /* Protects lists in hash */
436         u32 i;
437 
438         for (i = 0; i < hash->size; i++) {
439                 head = &hash->table[i];
440                 lock = &hash->list_locks[i];
441 
442                 /* For each nc_path in this bin */
443                 spin_lock_bh(lock);
444                 hlist_for_each_entry_safe(nc_path, node_tmp, head, hash_entry) {
445                         /* if an helper function has been passed as parameter,
446                          * ask it if the entry has to be purged or not
447                          */
448                         if (to_purge && !to_purge(bat_priv, nc_path))
449                                 continue;
450 
451                         /* purging an non-empty nc_path should never happen, but
452                          * is observed under high CPU load. Delay the purging
453                          * until next iteration to allow the packet_list to be
454                          * emptied first.
455                          */
456                         if (!unlikely(list_empty(&nc_path->packet_list))) {
457                                 net_ratelimited_function(printk,
458                                                          KERN_WARNING
459                                                          "Skipping free of non-empty nc_path (%pM -> %pM)!\n",
460                                                          nc_path->prev_hop,
461                                                          nc_path->next_hop);
462                                 continue;
463                         }
464 
465                         /* nc_path is unused, so remove it */
466                         batadv_dbg(BATADV_DBG_NC, bat_priv,
467                                    "Remove nc_path %pM -> %pM\n",
468                                    nc_path->prev_hop, nc_path->next_hop);
469                         hlist_del_rcu(&nc_path->hash_entry);
470                         batadv_nc_path_put(nc_path);
471                 }
472                 spin_unlock_bh(lock);
473         }
474 }
475 
476 /**
477  * batadv_nc_hash_key_gen - computes the nc_path hash key
478  * @key: buffer to hold the final hash key
479  * @src: source ethernet mac address going into the hash key
480  * @dst: destination ethernet mac address going into the hash key
481  */
482 static void batadv_nc_hash_key_gen(struct batadv_nc_path *key, const char *src,
483                                    const char *dst)
484 {
485         memcpy(key->prev_hop, src, sizeof(key->prev_hop));
486         memcpy(key->next_hop, dst, sizeof(key->next_hop));
487 }
488 
489 /**
490  * batadv_nc_hash_choose - compute the hash value for an nc path
491  * @data: data to hash
492  * @size: size of the hash table
493  *
494  * Return: the selected index in the hash table for the given data.
495  */
496 static u32 batadv_nc_hash_choose(const void *data, u32 size)
497 {
498         const struct batadv_nc_path *nc_path = data;
499         u32 hash = 0;
500 
501         hash = jhash(&nc_path->prev_hop, sizeof(nc_path->prev_hop), hash);
502         hash = jhash(&nc_path->next_hop, sizeof(nc_path->next_hop), hash);
503 
504         return hash % size;
505 }
506 
507 /**
508  * batadv_nc_hash_compare - comparing function used in the network coding hash
509  *  tables
510  * @node: node in the local table
511  * @data2: second object to compare the node to
512  *
513  * Return: 1 if the two entry are the same, 0 otherwise
514  */
515 static int batadv_nc_hash_compare(const struct hlist_node *node,
516                                   const void *data2)
517 {
518         const struct batadv_nc_path *nc_path1, *nc_path2;
519 
520         nc_path1 = container_of(node, struct batadv_nc_path, hash_entry);
521         nc_path2 = data2;
522 
523         /* Return 1 if the two keys are identical */
524         if (memcmp(nc_path1->prev_hop, nc_path2->prev_hop,
525                    sizeof(nc_path1->prev_hop)) != 0)
526                 return 0;
527 
528         if (memcmp(nc_path1->next_hop, nc_path2->next_hop,
529                    sizeof(nc_path1->next_hop)) != 0)
530                 return 0;
531 
532         return 1;
533 }
534 
535 /**
536  * batadv_nc_hash_find - search for an existing nc path and return it
537  * @hash: hash table containing the nc path
538  * @data: search key
539  *
540  * Return: the nc_path if found, NULL otherwise.
541  */
542 static struct batadv_nc_path *
543 batadv_nc_hash_find(struct batadv_hashtable *hash,
544                     void *data)
545 {
546         struct hlist_head *head;
547         struct batadv_nc_path *nc_path, *nc_path_tmp = NULL;
548         int index;
549 
550         if (!hash)
551                 return NULL;
552 
553         index = batadv_nc_hash_choose(data, hash->size);
554         head = &hash->table[index];
555 
556         rcu_read_lock();
557         hlist_for_each_entry_rcu(nc_path, head, hash_entry) {
558                 if (!batadv_nc_hash_compare(&nc_path->hash_entry, data))
559                         continue;
560 
561                 if (!kref_get_unless_zero(&nc_path->refcount))
562                         continue;
563 
564                 nc_path_tmp = nc_path;
565                 break;
566         }
567         rcu_read_unlock();
568 
569         return nc_path_tmp;
570 }
571 
572 /**
573  * batadv_nc_send_packet - send non-coded packet and free nc_packet struct
574  * @nc_packet: the nc packet to send
575  */
576 static void batadv_nc_send_packet(struct batadv_nc_packet *nc_packet)
577 {
578         batadv_send_unicast_skb(nc_packet->skb, nc_packet->neigh_node);
579         nc_packet->skb = NULL;
580         batadv_nc_packet_free(nc_packet);
581 }
582 
583 /**
584  * batadv_nc_sniffed_purge - Checks timestamp of given sniffed nc_packet.
585  * @bat_priv: the bat priv with all the soft interface information
586  * @nc_path: the nc path the packet belongs to
587  * @nc_packet: the nc packet to be checked
588  *
589  * Checks whether the given sniffed (overheard) nc_packet has hit its buffering
590  * timeout. If so, the packet is no longer kept and the entry deleted from the
591  * queue. Has to be called with the appropriate locks.
592  *
593  * Return: false as soon as the entry in the fifo queue has not been timed out
594  * yet and true otherwise.
595  */
596 static bool batadv_nc_sniffed_purge(struct batadv_priv *bat_priv,
597                                     struct batadv_nc_path *nc_path,
598                                     struct batadv_nc_packet *nc_packet)
599 {
600         unsigned long timeout = bat_priv->nc.max_buffer_time;
601         bool res = false;
602 
603         lockdep_assert_held(&nc_path->packet_list_lock);
604 
605         /* Packets are added to tail, so the remaining packets did not time
606          * out and we can stop processing the current queue
607          */
608         if (atomic_read(&bat_priv->mesh_state) == BATADV_MESH_ACTIVE &&
609             !batadv_has_timed_out(nc_packet->timestamp, timeout))
610                 goto out;
611 
612         /* purge nc packet */
613         list_del(&nc_packet->list);
614         batadv_nc_packet_free(nc_packet);
615 
616         res = true;
617 
618 out:
619         return res;
620 }
621 
622 /**
623  * batadv_nc_fwd_flush - Checks the timestamp of the given nc packet.
624  * @bat_priv: the bat priv with all the soft interface information
625  * @nc_path: the nc path the packet belongs to
626  * @nc_packet: the nc packet to be checked
627  *
628  * Checks whether the given nc packet has hit its forward timeout. If so, the
629  * packet is no longer delayed, immediately sent and the entry deleted from the
630  * queue. Has to be called with the appropriate locks.
631  *
632  * Return: false as soon as the entry in the fifo queue has not been timed out
633  * yet and true otherwise.
634  */
635 static bool batadv_nc_fwd_flush(struct batadv_priv *bat_priv,
636                                 struct batadv_nc_path *nc_path,
637                                 struct batadv_nc_packet *nc_packet)
638 {
639         unsigned long timeout = bat_priv->nc.max_fwd_delay;
640 
641         lockdep_assert_held(&nc_path->packet_list_lock);
642 
643         /* Packets are added to tail, so the remaining packets did not time
644          * out and we can stop processing the current queue
645          */
646         if (atomic_read(&bat_priv->mesh_state) == BATADV_MESH_ACTIVE &&
647             !batadv_has_timed_out(nc_packet->timestamp, timeout))
648                 return false;
649 
650         /* Send packet */
651         batadv_inc_counter(bat_priv, BATADV_CNT_FORWARD);
652         batadv_add_counter(bat_priv, BATADV_CNT_FORWARD_BYTES,
653                            nc_packet->skb->len + ETH_HLEN);
654         list_del(&nc_packet->list);
655         batadv_nc_send_packet(nc_packet);
656 
657         return true;
658 }
659 
660 /**
661  * batadv_nc_process_nc_paths - traverse given nc packet pool and free timed out
662  *  nc packets
663  * @bat_priv: the bat priv with all the soft interface information
664  * @hash: to be processed hash table
665  * @process_fn: Function called to process given nc packet. Should return true
666  *              to encourage this function to proceed with the next packet.
667  *              Otherwise the rest of the current queue is skipped.
668  */
669 static void
670 batadv_nc_process_nc_paths(struct batadv_priv *bat_priv,
671                            struct batadv_hashtable *hash,
672                            bool (*process_fn)(struct batadv_priv *,
673                                               struct batadv_nc_path *,
674                                               struct batadv_nc_packet *))
675 {
676         struct hlist_head *head;
677         struct batadv_nc_packet *nc_packet, *nc_packet_tmp;
678         struct batadv_nc_path *nc_path;
679         bool ret;
680         int i;
681 
682         if (!hash)
683                 return;
684 
685         /* Loop hash table bins */
686         for (i = 0; i < hash->size; i++) {
687                 head = &hash->table[i];
688 
689                 /* Loop coding paths */
690                 rcu_read_lock();
691                 hlist_for_each_entry_rcu(nc_path, head, hash_entry) {
692                         /* Loop packets */
693                         spin_lock_bh(&nc_path->packet_list_lock);
694                         list_for_each_entry_safe(nc_packet, nc_packet_tmp,
695                                                  &nc_path->packet_list, list) {
696                                 ret = process_fn(bat_priv, nc_path, nc_packet);
697                                 if (!ret)
698                                         break;
699                         }
700                         spin_unlock_bh(&nc_path->packet_list_lock);
701                 }
702                 rcu_read_unlock();
703         }
704 }
705 
706 /**
707  * batadv_nc_worker - periodic task for house keeping related to network coding
708  * @work: kernel work struct
709  */
710 static void batadv_nc_worker(struct work_struct *work)
711 {
712         struct delayed_work *delayed_work;
713         struct batadv_priv_nc *priv_nc;
714         struct batadv_priv *bat_priv;
715         unsigned long timeout;
716 
717         delayed_work = container_of(work, struct delayed_work, work);
718         priv_nc = container_of(delayed_work, struct batadv_priv_nc, work);
719         bat_priv = container_of(priv_nc, struct batadv_priv, nc);
720 
721         batadv_nc_purge_orig_hash(bat_priv);
722         batadv_nc_purge_paths(bat_priv, bat_priv->nc.coding_hash,
723                               batadv_nc_to_purge_nc_path_coding);
724         batadv_nc_purge_paths(bat_priv, bat_priv->nc.decoding_hash,
725                               batadv_nc_to_purge_nc_path_decoding);
726 
727         timeout = bat_priv->nc.max_fwd_delay;
728 
729         if (batadv_has_timed_out(bat_priv->nc.timestamp_fwd_flush, timeout)) {
730                 batadv_nc_process_nc_paths(bat_priv, bat_priv->nc.coding_hash,
731                                            batadv_nc_fwd_flush);
732                 bat_priv->nc.timestamp_fwd_flush = jiffies;
733         }
734 
735         if (batadv_has_timed_out(bat_priv->nc.timestamp_sniffed_purge,
736                                  bat_priv->nc.max_buffer_time)) {
737                 batadv_nc_process_nc_paths(bat_priv, bat_priv->nc.decoding_hash,
738                                            batadv_nc_sniffed_purge);
739                 bat_priv->nc.timestamp_sniffed_purge = jiffies;
740         }
741 
742         /* Schedule a new check */
743         batadv_nc_start_timer(bat_priv);
744 }
745 
746 /**
747  * batadv_can_nc_with_orig - checks whether the given orig node is suitable for
748  *  coding or not
749  * @bat_priv: the bat priv with all the soft interface information
750  * @orig_node: neighboring orig node which may be used as nc candidate
751  * @ogm_packet: incoming ogm packet also used for the checks
752  *
753  * Return: true if:
754  *  1) The OGM must have the most recent sequence number.
755  *  2) The TTL must be decremented by one and only one.
756  *  3) The OGM must be received from the first hop from orig_node.
757  *  4) The TQ value of the OGM must be above bat_priv->nc.min_tq.
758  */
759 static bool batadv_can_nc_with_orig(struct batadv_priv *bat_priv,
760                                     struct batadv_orig_node *orig_node,
761                                     struct batadv_ogm_packet *ogm_packet)
762 {
763         struct batadv_orig_ifinfo *orig_ifinfo;
764         u32 last_real_seqno;
765         u8 last_ttl;
766 
767         orig_ifinfo = batadv_orig_ifinfo_get(orig_node, BATADV_IF_DEFAULT);
768         if (!orig_ifinfo)
769                 return false;
770 
771         last_ttl = orig_ifinfo->last_ttl;
772         last_real_seqno = orig_ifinfo->last_real_seqno;
773         batadv_orig_ifinfo_put(orig_ifinfo);
774 
775         if (last_real_seqno != ntohl(ogm_packet->seqno))
776                 return false;
777         if (last_ttl != ogm_packet->ttl + 1)
778                 return false;
779         if (!batadv_compare_eth(ogm_packet->orig, ogm_packet->prev_sender))
780                 return false;
781         if (ogm_packet->tq < bat_priv->nc.min_tq)
782                 return false;
783 
784         return true;
785 }
786 
787 /**
788  * batadv_nc_find_nc_node - search for an existing nc node and return it
789  * @orig_node: orig node originating the ogm packet
790  * @orig_neigh_node: neighboring orig node from which we received the ogm packet
791  *  (can be equal to orig_node)
792  * @in_coding: traverse incoming or outgoing network coding list
793  *
794  * Return: the nc_node if found, NULL otherwise.
795  */
796 static struct batadv_nc_node
797 *batadv_nc_find_nc_node(struct batadv_orig_node *orig_node,
798                         struct batadv_orig_node *orig_neigh_node,
799                         bool in_coding)
800 {
801         struct batadv_nc_node *nc_node, *nc_node_out = NULL;
802         struct list_head *list;
803 
804         if (in_coding)
805                 list = &orig_neigh_node->in_coding_list;
806         else
807                 list = &orig_neigh_node->out_coding_list;
808 
809         /* Traverse list of nc_nodes to orig_node */
810         rcu_read_lock();
811         list_for_each_entry_rcu(nc_node, list, list) {
812                 if (!batadv_compare_eth(nc_node->addr, orig_node->orig))
813                         continue;
814 
815                 if (!kref_get_unless_zero(&nc_node->refcount))
816                         continue;
817 
818                 /* Found a match */
819                 nc_node_out = nc_node;
820                 break;
821         }
822         rcu_read_unlock();
823 
824         return nc_node_out;
825 }
826 
827 /**
828  * batadv_nc_get_nc_node - retrieves an nc node or creates the entry if it was
829  *  not found
830  * @bat_priv: the bat priv with all the soft interface information
831  * @orig_node: orig node originating the ogm packet
832  * @orig_neigh_node: neighboring orig node from which we received the ogm packet
833  *  (can be equal to orig_node)
834  * @in_coding: traverse incoming or outgoing network coding list
835  *
836  * Return: the nc_node if found or created, NULL in case of an error.
837  */
838 static struct batadv_nc_node
839 *batadv_nc_get_nc_node(struct batadv_priv *bat_priv,
840                        struct batadv_orig_node *orig_node,
841                        struct batadv_orig_node *orig_neigh_node,
842                        bool in_coding)
843 {
844         struct batadv_nc_node *nc_node;
845         spinlock_t *lock; /* Used to lock list selected by "int in_coding" */
846         struct list_head *list;
847 
848         /* Check if nc_node is already added */
849         nc_node = batadv_nc_find_nc_node(orig_node, orig_neigh_node, in_coding);
850 
851         /* Node found */
852         if (nc_node)
853                 return nc_node;
854 
855         nc_node = kzalloc(sizeof(*nc_node), GFP_ATOMIC);
856         if (!nc_node)
857                 return NULL;
858 
859         if (!kref_get_unless_zero(&orig_neigh_node->refcount))
860                 goto free;
861 
862         /* Initialize nc_node */
863         INIT_LIST_HEAD(&nc_node->list);
864         ether_addr_copy(nc_node->addr, orig_node->orig);
865         nc_node->orig_node = orig_neigh_node;
866         kref_init(&nc_node->refcount);
867         kref_get(&nc_node->refcount);
868 
869         /* Select ingoing or outgoing coding node */
870         if (in_coding) {
871                 lock = &orig_neigh_node->in_coding_list_lock;
872                 list = &orig_neigh_node->in_coding_list;
873         } else {
874                 lock = &orig_neigh_node->out_coding_list_lock;
875                 list = &orig_neigh_node->out_coding_list;
876         }
877 
878         batadv_dbg(BATADV_DBG_NC, bat_priv, "Adding nc_node %pM -> %pM\n",
879                    nc_node->addr, nc_node->orig_node->orig);
880 
881         /* Add nc_node to orig_node */
882         spin_lock_bh(lock);
883         list_add_tail_rcu(&nc_node->list, list);
884         spin_unlock_bh(lock);
885 
886         return nc_node;
887 
888 free:
889         kfree(nc_node);
890         return NULL;
891 }
892 
893 /**
894  * batadv_nc_update_nc_node - updates stored incoming and outgoing nc node
895  *  structs (best called on incoming OGMs)
896  * @bat_priv: the bat priv with all the soft interface information
897  * @orig_node: orig node originating the ogm packet
898  * @orig_neigh_node: neighboring orig node from which we received the ogm packet
899  *  (can be equal to orig_node)
900  * @ogm_packet: incoming ogm packet
901  * @is_single_hop_neigh: orig_node is a single hop neighbor
902  */
903 void batadv_nc_update_nc_node(struct batadv_priv *bat_priv,
904                               struct batadv_orig_node *orig_node,
905                               struct batadv_orig_node *orig_neigh_node,
906                               struct batadv_ogm_packet *ogm_packet,
907                               int is_single_hop_neigh)
908 {
909         struct batadv_nc_node *in_nc_node = NULL;
910         struct batadv_nc_node *out_nc_node = NULL;
911 
912         /* Check if network coding is enabled */
913         if (!atomic_read(&bat_priv->network_coding))
914                 goto out;
915 
916         /* check if orig node is network coding enabled */
917         if (!test_bit(BATADV_ORIG_CAPA_HAS_NC, &orig_node->capabilities))
918                 goto out;
919 
920         /* accept ogms from 'good' neighbors and single hop neighbors */
921         if (!batadv_can_nc_with_orig(bat_priv, orig_node, ogm_packet) &&
922             !is_single_hop_neigh)
923                 goto out;
924 
925         /* Add orig_node as in_nc_node on hop */
926         in_nc_node = batadv_nc_get_nc_node(bat_priv, orig_node,
927                                            orig_neigh_node, true);
928         if (!in_nc_node)
929                 goto out;
930 
931         in_nc_node->last_seen = jiffies;
932 
933         /* Add hop as out_nc_node on orig_node */
934         out_nc_node = batadv_nc_get_nc_node(bat_priv, orig_neigh_node,
935                                             orig_node, false);
936         if (!out_nc_node)
937                 goto out;
938 
939         out_nc_node->last_seen = jiffies;
940 
941 out:
942         if (in_nc_node)
943                 batadv_nc_node_put(in_nc_node);
944         if (out_nc_node)
945                 batadv_nc_node_put(out_nc_node);
946 }
947 
948 /**
949  * batadv_nc_get_path - get existing nc_path or allocate a new one
950  * @bat_priv: the bat priv with all the soft interface information
951  * @hash: hash table containing the nc path
952  * @src: ethernet source address - first half of the nc path search key
953  * @dst: ethernet destination address - second half of the nc path search key
954  *
955  * Return: pointer to nc_path if the path was found or created, returns NULL
956  * on error.
957  */
958 static struct batadv_nc_path *batadv_nc_get_path(struct batadv_priv *bat_priv,
959                                                  struct batadv_hashtable *hash,
960                                                  u8 *src,
961                                                  u8 *dst)
962 {
963         int hash_added;
964         struct batadv_nc_path *nc_path, nc_path_key;
965 
966         batadv_nc_hash_key_gen(&nc_path_key, src, dst);
967 
968         /* Search for existing nc_path */
969         nc_path = batadv_nc_hash_find(hash, (void *)&nc_path_key);
970 
971         if (nc_path) {
972                 /* Set timestamp to delay removal of nc_path */
973                 nc_path->last_valid = jiffies;
974                 return nc_path;
975         }
976 
977         /* No existing nc_path was found; create a new */
978         nc_path = kzalloc(sizeof(*nc_path), GFP_ATOMIC);
979 
980         if (!nc_path)
981                 return NULL;
982 
983         /* Initialize nc_path */
984         INIT_LIST_HEAD(&nc_path->packet_list);
985         spin_lock_init(&nc_path->packet_list_lock);
986         kref_init(&nc_path->refcount);
987         kref_get(&nc_path->refcount);
988         nc_path->last_valid = jiffies;
989         ether_addr_copy(nc_path->next_hop, dst);
990         ether_addr_copy(nc_path->prev_hop, src);
991 
992         batadv_dbg(BATADV_DBG_NC, bat_priv, "Adding nc_path %pM -> %pM\n",
993                    nc_path->prev_hop,
994                    nc_path->next_hop);
995 
996         /* Add nc_path to hash table */
997         hash_added = batadv_hash_add(hash, batadv_nc_hash_compare,
998                                      batadv_nc_hash_choose, &nc_path_key,
999                                      &nc_path->hash_entry);
1000 
1001         if (hash_added < 0) {
1002                 kfree(nc_path);
1003                 return NULL;
1004         }
1005 
1006         return nc_path;
1007 }
1008 
1009 /**
1010  * batadv_nc_random_weight_tq - scale the receivers TQ-value to avoid unfair
1011  *  selection of a receiver with slightly lower TQ than the other
1012  * @tq: to be weighted tq value
1013  *
1014  * Return: scaled tq value
1015  */
1016 static u8 batadv_nc_random_weight_tq(u8 tq)
1017 {
1018         u8 rand_val, rand_tq;
1019 
1020         get_random_bytes(&rand_val, sizeof(rand_val));
1021 
1022         /* randomize the estimated packet loss (max TQ - estimated TQ) */
1023         rand_tq = rand_val * (BATADV_TQ_MAX_VALUE - tq);
1024 
1025         /* normalize the randomized packet loss */
1026         rand_tq /= BATADV_TQ_MAX_VALUE;
1027 
1028         /* convert to (randomized) estimated tq again */
1029         return BATADV_TQ_MAX_VALUE - rand_tq;
1030 }
1031 
1032 /**
1033  * batadv_nc_memxor - XOR destination with source
1034  * @dst: byte array to XOR into
1035  * @src: byte array to XOR from
1036  * @len: length of destination array
1037  */
1038 static void batadv_nc_memxor(char *dst, const char *src, unsigned int len)
1039 {
1040         unsigned int i;
1041 
1042         for (i = 0; i < len; ++i)
1043                 dst[i] ^= src[i];
1044 }
1045 
1046 /**
1047  * batadv_nc_code_packets - code a received unicast_packet with an nc packet
1048  *  into a coded_packet and send it
1049  * @bat_priv: the bat priv with all the soft interface information
1050  * @skb: data skb to forward
1051  * @ethhdr: pointer to the ethernet header inside the skb
1052  * @nc_packet: structure containing the packet to the skb can be coded with
1053  * @neigh_node: next hop to forward packet to
1054  *
1055  * Return: true if both packets are consumed, false otherwise.
1056  */
1057 static bool batadv_nc_code_packets(struct batadv_priv *bat_priv,
1058                                    struct sk_buff *skb,
1059                                    struct ethhdr *ethhdr,
1060                                    struct batadv_nc_packet *nc_packet,
1061                                    struct batadv_neigh_node *neigh_node)
1062 {
1063         u8 tq_weighted_neigh, tq_weighted_coding, tq_tmp;
1064         struct sk_buff *skb_dest, *skb_src;
1065         struct batadv_unicast_packet *packet1;
1066         struct batadv_unicast_packet *packet2;
1067         struct batadv_coded_packet *coded_packet;
1068         struct batadv_neigh_node *neigh_tmp, *router_neigh, *first_dest;
1069         struct batadv_neigh_node *router_coding = NULL, *second_dest;
1070         struct batadv_neigh_ifinfo *router_neigh_ifinfo = NULL;
1071         struct batadv_neigh_ifinfo *router_coding_ifinfo = NULL;
1072         u8 *first_source, *second_source;
1073         __be32 packet_id1, packet_id2;
1074         size_t count;
1075         bool res = false;
1076         int coding_len;
1077         int unicast_size = sizeof(*packet1);
1078         int coded_size = sizeof(*coded_packet);
1079         int header_add = coded_size - unicast_size;
1080 
1081         /* TODO: do we need to consider the outgoing interface for
1082          * coded packets?
1083          */
1084         router_neigh = batadv_orig_router_get(neigh_node->orig_node,
1085                                               BATADV_IF_DEFAULT);
1086         if (!router_neigh)
1087                 goto out;
1088 
1089         router_neigh_ifinfo = batadv_neigh_ifinfo_get(router_neigh,
1090                                                       BATADV_IF_DEFAULT);
1091         if (!router_neigh_ifinfo)
1092                 goto out;
1093 
1094         neigh_tmp = nc_packet->neigh_node;
1095         router_coding = batadv_orig_router_get(neigh_tmp->orig_node,
1096                                                BATADV_IF_DEFAULT);
1097         if (!router_coding)
1098                 goto out;
1099 
1100         router_coding_ifinfo = batadv_neigh_ifinfo_get(router_coding,
1101                                                        BATADV_IF_DEFAULT);
1102         if (!router_coding_ifinfo)
1103                 goto out;
1104 
1105         tq_tmp = router_neigh_ifinfo->bat_iv.tq_avg;
1106         tq_weighted_neigh = batadv_nc_random_weight_tq(tq_tmp);
1107         tq_tmp = router_coding_ifinfo->bat_iv.tq_avg;
1108         tq_weighted_coding = batadv_nc_random_weight_tq(tq_tmp);
1109 
1110         /* Select one destination for the MAC-header dst-field based on
1111          * weighted TQ-values.
1112          */
1113         if (tq_weighted_neigh >= tq_weighted_coding) {
1114                 /* Destination from nc_packet is selected for MAC-header */
1115                 first_dest = nc_packet->neigh_node;
1116                 first_source = nc_packet->nc_path->prev_hop;
1117                 second_dest = neigh_node;
1118                 second_source = ethhdr->h_source;
1119                 packet1 = (struct batadv_unicast_packet *)nc_packet->skb->data;
1120                 packet2 = (struct batadv_unicast_packet *)skb->data;
1121                 packet_id1 = nc_packet->packet_id;
1122                 packet_id2 = batadv_skb_crc32(skb,
1123                                               skb->data + sizeof(*packet2));
1124         } else {
1125                 /* Destination for skb is selected for MAC-header */
1126                 first_dest = neigh_node;
1127                 first_source = ethhdr->h_source;
1128                 second_dest = nc_packet->neigh_node;
1129                 second_source = nc_packet->nc_path->prev_hop;
1130                 packet1 = (struct batadv_unicast_packet *)skb->data;
1131                 packet2 = (struct batadv_unicast_packet *)nc_packet->skb->data;
1132                 packet_id1 = batadv_skb_crc32(skb,
1133                                               skb->data + sizeof(*packet1));
1134                 packet_id2 = nc_packet->packet_id;
1135         }
1136 
1137         /* Instead of zero padding the smallest data buffer, we
1138          * code into the largest.
1139          */
1140         if (skb->len <= nc_packet->skb->len) {
1141                 skb_dest = nc_packet->skb;
1142                 skb_src = skb;
1143         } else {
1144                 skb_dest = skb;
1145                 skb_src = nc_packet->skb;
1146         }
1147 
1148         /* coding_len is used when decoding the packet shorter packet */
1149         coding_len = skb_src->len - unicast_size;
1150 
1151         if (skb_linearize(skb_dest) < 0 || skb_linearize(skb_src) < 0)
1152                 goto out;
1153 
1154         skb_push(skb_dest, header_add);
1155 
1156         coded_packet = (struct batadv_coded_packet *)skb_dest->data;
1157         skb_reset_mac_header(skb_dest);
1158 
1159         coded_packet->packet_type = BATADV_CODED;
1160         coded_packet->version = BATADV_COMPAT_VERSION;
1161         coded_packet->ttl = packet1->ttl;
1162 
1163         /* Info about first unicast packet */
1164         ether_addr_copy(coded_packet->first_source, first_source);
1165         ether_addr_copy(coded_packet->first_orig_dest, packet1->dest);
1166         coded_packet->first_crc = packet_id1;
1167         coded_packet->first_ttvn = packet1->ttvn;
1168 
1169         /* Info about second unicast packet */
1170         ether_addr_copy(coded_packet->second_dest, second_dest->addr);
1171         ether_addr_copy(coded_packet->second_source, second_source);
1172         ether_addr_copy(coded_packet->second_orig_dest, packet2->dest);
1173         coded_packet->second_crc = packet_id2;
1174         coded_packet->second_ttl = packet2->ttl;
1175         coded_packet->second_ttvn = packet2->ttvn;
1176         coded_packet->coded_len = htons(coding_len);
1177 
1178         /* This is where the magic happens: Code skb_src into skb_dest */
1179         batadv_nc_memxor(skb_dest->data + coded_size,
1180                          skb_src->data + unicast_size, coding_len);
1181 
1182         /* Update counters accordingly */
1183         if (BATADV_SKB_CB(skb_src)->decoded &&
1184             BATADV_SKB_CB(skb_dest)->decoded) {
1185                 /* Both packets are recoded */
1186                 count = skb_src->len + ETH_HLEN;
1187                 count += skb_dest->len + ETH_HLEN;
1188                 batadv_add_counter(bat_priv, BATADV_CNT_NC_RECODE, 2);
1189                 batadv_add_counter(bat_priv, BATADV_CNT_NC_RECODE_BYTES, count);
1190         } else if (!BATADV_SKB_CB(skb_src)->decoded &&
1191                    !BATADV_SKB_CB(skb_dest)->decoded) {
1192                 /* Both packets are newly coded */
1193                 count = skb_src->len + ETH_HLEN;
1194                 count += skb_dest->len + ETH_HLEN;
1195                 batadv_add_counter(bat_priv, BATADV_CNT_NC_CODE, 2);
1196                 batadv_add_counter(bat_priv, BATADV_CNT_NC_CODE_BYTES, count);
1197         } else if (BATADV_SKB_CB(skb_src)->decoded &&
1198                    !BATADV_SKB_CB(skb_dest)->decoded) {
1199                 /* skb_src recoded and skb_dest is newly coded */
1200                 batadv_inc_counter(bat_priv, BATADV_CNT_NC_RECODE);
1201                 batadv_add_counter(bat_priv, BATADV_CNT_NC_RECODE_BYTES,
1202                                    skb_src->len + ETH_HLEN);
1203                 batadv_inc_counter(bat_priv, BATADV_CNT_NC_CODE);
1204                 batadv_add_counter(bat_priv, BATADV_CNT_NC_CODE_BYTES,
1205                                    skb_dest->len + ETH_HLEN);
1206         } else if (!BATADV_SKB_CB(skb_src)->decoded &&
1207                    BATADV_SKB_CB(skb_dest)->decoded) {
1208                 /* skb_src is newly coded and skb_dest is recoded */
1209                 batadv_inc_counter(bat_priv, BATADV_CNT_NC_CODE);
1210                 batadv_add_counter(bat_priv, BATADV_CNT_NC_CODE_BYTES,
1211                                    skb_src->len + ETH_HLEN);
1212                 batadv_inc_counter(bat_priv, BATADV_CNT_NC_RECODE);
1213                 batadv_add_counter(bat_priv, BATADV_CNT_NC_RECODE_BYTES,
1214                                    skb_dest->len + ETH_HLEN);
1215         }
1216 
1217         /* skb_src is now coded into skb_dest, so free it */
1218         kfree_skb(skb_src);
1219 
1220         /* avoid duplicate free of skb from nc_packet */
1221         nc_packet->skb = NULL;
1222         batadv_nc_packet_free(nc_packet);
1223 
1224         /* Send the coded packet and return true */
1225         batadv_send_unicast_skb(skb_dest, first_dest);
1226         res = true;
1227 out:
1228         if (router_neigh)
1229                 batadv_neigh_node_put(router_neigh);
1230         if (router_coding)
1231                 batadv_neigh_node_put(router_coding);
1232         if (router_neigh_ifinfo)
1233                 batadv_neigh_ifinfo_put(router_neigh_ifinfo);
1234         if (router_coding_ifinfo)
1235                 batadv_neigh_ifinfo_put(router_coding_ifinfo);
1236         return res;
1237 }
1238 
1239 /**
1240  * batadv_nc_skb_coding_possible - true if a decoded skb is available at dst.
1241  * @skb: data skb to forward
1242  * @dst: destination mac address of the other skb to code with
1243  * @src: source mac address of skb
1244  *
1245  * Whenever we network code a packet we have to check whether we received it in
1246  * a network coded form. If so, we may not be able to use it for coding because
1247  * some neighbors may also have received (overheard) the packet in the network
1248  * coded form without being able to decode it. It is hard to know which of the
1249  * neighboring nodes was able to decode the packet, therefore we can only
1250  * re-code the packet if the source of the previous encoded packet is involved.
1251  * Since the source encoded the packet we can be certain it has all necessary
1252  * decode information.
1253  *
1254  * Return: true if coding of a decoded packet is allowed.
1255  */
1256 static bool batadv_nc_skb_coding_possible(struct sk_buff *skb, u8 *dst, u8 *src)
1257 {
1258         if (BATADV_SKB_CB(skb)->decoded && !batadv_compare_eth(dst, src))
1259                 return false;
1260         return true;
1261 }
1262 
1263 /**
1264  * batadv_nc_path_search - Find the coding path matching in_nc_node and
1265  *  out_nc_node to retrieve a buffered packet that can be used for coding.
1266  * @bat_priv: the bat priv with all the soft interface information
1267  * @in_nc_node: pointer to skb next hop's neighbor nc node
1268  * @out_nc_node: pointer to skb source's neighbor nc node
1269  * @skb: data skb to forward
1270  * @eth_dst: next hop mac address of skb
1271  *
1272  * Return: true if coding of a decoded skb is allowed.
1273  */
1274 static struct batadv_nc_packet *
1275 batadv_nc_path_search(struct batadv_priv *bat_priv,
1276                       struct batadv_nc_node *in_nc_node,
1277                       struct batadv_nc_node *out_nc_node,
1278                       struct sk_buff *skb,
1279                       u8 *eth_dst)
1280 {
1281         struct batadv_nc_path *nc_path, nc_path_key;
1282         struct batadv_nc_packet *nc_packet_out = NULL;
1283         struct batadv_nc_packet *nc_packet, *nc_packet_tmp;
1284         struct batadv_hashtable *hash = bat_priv->nc.coding_hash;
1285         int idx;
1286 
1287         if (!hash)
1288                 return NULL;
1289 
1290         /* Create almost path key */
1291         batadv_nc_hash_key_gen(&nc_path_key, in_nc_node->addr,
1292                                out_nc_node->addr);
1293         idx = batadv_nc_hash_choose(&nc_path_key, hash->size);
1294 
1295         /* Check for coding opportunities in this nc_path */
1296         rcu_read_lock();
1297         hlist_for_each_entry_rcu(nc_path, &hash->table[idx], hash_entry) {
1298                 if (!batadv_compare_eth(nc_path->prev_hop, in_nc_node->addr))
1299                         continue;
1300 
1301                 if (!batadv_compare_eth(nc_path->next_hop, out_nc_node->addr))
1302                         continue;
1303 
1304                 spin_lock_bh(&nc_path->packet_list_lock);
1305                 if (list_empty(&nc_path->packet_list)) {
1306                         spin_unlock_bh(&nc_path->packet_list_lock);
1307                         continue;
1308                 }
1309 
1310                 list_for_each_entry_safe(nc_packet, nc_packet_tmp,
1311                                          &nc_path->packet_list, list) {
1312                         if (!batadv_nc_skb_coding_possible(nc_packet->skb,
1313                                                            eth_dst,
1314                                                            in_nc_node->addr))
1315                                 continue;
1316 
1317                         /* Coding opportunity is found! */
1318                         list_del(&nc_packet->list);
1319                         nc_packet_out = nc_packet;
1320                         break;
1321                 }
1322 
1323                 spin_unlock_bh(&nc_path->packet_list_lock);
1324                 break;
1325         }
1326         rcu_read_unlock();
1327 
1328         return nc_packet_out;
1329 }
1330 
1331 /**
1332  * batadv_nc_skb_src_search - Loops through the list of neighoring nodes of the
1333  *  skb's sender (may be equal to the originator).
1334  * @bat_priv: the bat priv with all the soft interface information
1335  * @skb: data skb to forward
1336  * @eth_dst: next hop mac address of skb
1337  * @eth_src: source mac address of skb
1338  * @in_nc_node: pointer to skb next hop's neighbor nc node
1339  *
1340  * Return: an nc packet if a suitable coding packet was found, NULL otherwise.
1341  */
1342 static struct batadv_nc_packet *
1343 batadv_nc_skb_src_search(struct batadv_priv *bat_priv,
1344                          struct sk_buff *skb,
1345                          u8 *eth_dst,
1346                          u8 *eth_src,
1347                          struct batadv_nc_node *in_nc_node)
1348 {
1349         struct batadv_orig_node *orig_node;
1350         struct batadv_nc_node *out_nc_node;
1351         struct batadv_nc_packet *nc_packet = NULL;
1352 
1353         orig_node = batadv_orig_hash_find(bat_priv, eth_src);
1354         if (!orig_node)
1355                 return NULL;
1356 
1357         rcu_read_lock();
1358         list_for_each_entry_rcu(out_nc_node,
1359                                 &orig_node->out_coding_list, list) {
1360                 /* Check if the skb is decoded and if recoding is possible */
1361                 if (!batadv_nc_skb_coding_possible(skb,
1362                                                    out_nc_node->addr, eth_src))
1363                         continue;
1364 
1365                 /* Search for an opportunity in this nc_path */
1366                 nc_packet = batadv_nc_path_search(bat_priv, in_nc_node,
1367                                                   out_nc_node, skb, eth_dst);
1368                 if (nc_packet)
1369                         break;
1370         }
1371         rcu_read_unlock();
1372 
1373         batadv_orig_node_put(orig_node);
1374         return nc_packet;
1375 }
1376 
1377 /**
1378  * batadv_nc_skb_store_before_coding - set the ethernet src and dst of the
1379  *  unicast skb before it is stored for use in later decoding
1380  * @bat_priv: the bat priv with all the soft interface information
1381  * @skb: data skb to store
1382  * @eth_dst_new: new destination mac address of skb
1383  */
1384 static void batadv_nc_skb_store_before_coding(struct batadv_priv *bat_priv,
1385                                               struct sk_buff *skb,
1386                                               u8 *eth_dst_new)
1387 {
1388         struct ethhdr *ethhdr;
1389 
1390         /* Copy skb header to change the mac header */
1391         skb = pskb_copy_for_clone(skb, GFP_ATOMIC);
1392         if (!skb)
1393                 return;
1394 
1395         /* Set the mac header as if we actually sent the packet uncoded */
1396         ethhdr = eth_hdr(skb);
1397         ether_addr_copy(ethhdr->h_source, ethhdr->h_dest);
1398         ether_addr_copy(ethhdr->h_dest, eth_dst_new);
1399 
1400         /* Set data pointer to MAC header to mimic packets from our tx path */
1401         skb_push(skb, ETH_HLEN);
1402 
1403         /* Add the packet to the decoding packet pool */
1404         batadv_nc_skb_store_for_decoding(bat_priv, skb);
1405 
1406         /* batadv_nc_skb_store_for_decoding() clones the skb, so we must free
1407          * our ref
1408          */
1409         kfree_skb(skb);
1410 }
1411 
1412 /**
1413  * batadv_nc_skb_dst_search - Loops through list of neighboring nodes to dst.
1414  * @skb: data skb to forward
1415  * @neigh_node: next hop to forward packet to
1416  * @ethhdr: pointer to the ethernet header inside the skb
1417  *
1418  * Loops through list of neighboring nodes the next hop has a good connection to
1419  * (receives OGMs with a sufficient quality). We need to find a neighbor of our
1420  * next hop that potentially sent a packet which our next hop also received
1421  * (overheard) and has stored for later decoding.
1422  *
1423  * Return: true if the skb was consumed (encoded packet sent) or false otherwise
1424  */
1425 static bool batadv_nc_skb_dst_search(struct sk_buff *skb,
1426                                      struct batadv_neigh_node *neigh_node,
1427                                      struct ethhdr *ethhdr)
1428 {
1429         struct net_device *netdev = neigh_node->if_incoming->soft_iface;
1430         struct batadv_priv *bat_priv = netdev_priv(netdev);
1431         struct batadv_orig_node *orig_node = neigh_node->orig_node;
1432         struct batadv_nc_node *nc_node;
1433         struct batadv_nc_packet *nc_packet = NULL;
1434 
1435         rcu_read_lock();
1436         list_for_each_entry_rcu(nc_node, &orig_node->in_coding_list, list) {
1437                 /* Search for coding opportunity with this in_nc_node */
1438                 nc_packet = batadv_nc_skb_src_search(bat_priv, skb,
1439                                                      neigh_node->addr,
1440                                                      ethhdr->h_source, nc_node);
1441 
1442                 /* Opportunity was found, so stop searching */
1443                 if (nc_packet)
1444                         break;
1445         }
1446         rcu_read_unlock();
1447 
1448         if (!nc_packet)
1449                 return false;
1450 
1451         /* Save packets for later decoding */
1452         batadv_nc_skb_store_before_coding(bat_priv, skb,
1453                                           neigh_node->addr);
1454         batadv_nc_skb_store_before_coding(bat_priv, nc_packet->skb,
1455                                           nc_packet->neigh_node->addr);
1456 
1457         /* Code and send packets */
1458         if (batadv_nc_code_packets(bat_priv, skb, ethhdr, nc_packet,
1459                                    neigh_node))
1460                 return true;
1461 
1462         /* out of mem ? Coding failed - we have to free the buffered packet
1463          * to avoid memleaks. The skb passed as argument will be dealt with
1464          * by the calling function.
1465          */
1466         batadv_nc_send_packet(nc_packet);
1467         return false;
1468 }
1469 
1470 /**
1471  * batadv_nc_skb_add_to_path - buffer skb for later encoding / decoding
1472  * @skb: skb to add to path
1473  * @nc_path: path to add skb to
1474  * @neigh_node: next hop to forward packet to
1475  * @packet_id: checksum to identify packet
1476  *
1477  * Return: true if the packet was buffered or false in case of an error.
1478  */
1479 static bool batadv_nc_skb_add_to_path(struct sk_buff *skb,
1480                                       struct batadv_nc_path *nc_path,
1481                                       struct batadv_neigh_node *neigh_node,
1482                                       __be32 packet_id)
1483 {
1484         struct batadv_nc_packet *nc_packet;
1485 
1486         nc_packet = kzalloc(sizeof(*nc_packet), GFP_ATOMIC);
1487         if (!nc_packet)
1488                 return false;
1489 
1490         /* Initialize nc_packet */
1491         nc_packet->timestamp = jiffies;
1492         nc_packet->packet_id = packet_id;
1493         nc_packet->skb = skb;
1494         nc_packet->neigh_node = neigh_node;
1495         nc_packet->nc_path = nc_path;
1496 
1497         /* Add coding packet to list */
1498         spin_lock_bh(&nc_path->packet_list_lock);
1499         list_add_tail(&nc_packet->list, &nc_path->packet_list);
1500         spin_unlock_bh(&nc_path->packet_list_lock);
1501 
1502         return true;
1503 }
1504 
1505 /**
1506  * batadv_nc_skb_forward - try to code a packet or add it to the coding packet
1507  *  buffer
1508  * @skb: data skb to forward
1509  * @neigh_node: next hop to forward packet to
1510  *
1511  * Return: true if the skb was consumed (encoded packet sent) or false otherwise
1512  */
1513 bool batadv_nc_skb_forward(struct sk_buff *skb,
1514                            struct batadv_neigh_node *neigh_node)
1515 {
1516         const struct net_device *netdev = neigh_node->if_incoming->soft_iface;
1517         struct batadv_priv *bat_priv = netdev_priv(netdev);
1518         struct batadv_unicast_packet *packet;
1519         struct batadv_nc_path *nc_path;
1520         struct ethhdr *ethhdr = eth_hdr(skb);
1521         __be32 packet_id;
1522         u8 *payload;
1523 
1524         /* Check if network coding is enabled */
1525         if (!atomic_read(&bat_priv->network_coding))
1526                 goto out;
1527 
1528         /* We only handle unicast packets */
1529         payload = skb_network_header(skb);
1530         packet = (struct batadv_unicast_packet *)payload;
1531         if (packet->packet_type != BATADV_UNICAST)
1532                 goto out;
1533 
1534         /* Try to find a coding opportunity and send the skb if one is found */
1535         if (batadv_nc_skb_dst_search(skb, neigh_node, ethhdr))
1536                 return true;
1537 
1538         /* Find or create a nc_path for this src-dst pair */
1539         nc_path = batadv_nc_get_path(bat_priv,
1540                                      bat_priv->nc.coding_hash,
1541                                      ethhdr->h_source,
1542                                      neigh_node->addr);
1543 
1544         if (!nc_path)
1545                 goto out;
1546 
1547         /* Add skb to nc_path */
1548         packet_id = batadv_skb_crc32(skb, payload + sizeof(*packet));
1549         if (!batadv_nc_skb_add_to_path(skb, nc_path, neigh_node, packet_id))
1550                 goto free_nc_path;
1551 
1552         /* Packet is consumed */
1553         return true;
1554 
1555 free_nc_path:
1556         batadv_nc_path_put(nc_path);
1557 out:
1558         /* Packet is not consumed */
1559         return false;
1560 }
1561 
1562 /**
1563  * batadv_nc_skb_store_for_decoding - save a clone of the skb which can be used
1564  *  when decoding coded packets
1565  * @bat_priv: the bat priv with all the soft interface information
1566  * @skb: data skb to store
1567  */
1568 void batadv_nc_skb_store_for_decoding(struct batadv_priv *bat_priv,
1569                                       struct sk_buff *skb)
1570 {
1571         struct batadv_unicast_packet *packet;
1572         struct batadv_nc_path *nc_path;
1573         struct ethhdr *ethhdr = eth_hdr(skb);
1574         __be32 packet_id;
1575         u8 *payload;
1576 
1577         /* Check if network coding is enabled */
1578         if (!atomic_read(&bat_priv->network_coding))
1579                 goto out;
1580 
1581         /* Check for supported packet type */
1582         payload = skb_network_header(skb);
1583         packet = (struct batadv_unicast_packet *)payload;
1584         if (packet->packet_type != BATADV_UNICAST)
1585                 goto out;
1586 
1587         /* Find existing nc_path or create a new */
1588         nc_path = batadv_nc_get_path(bat_priv,
1589                                      bat_priv->nc.decoding_hash,
1590                                      ethhdr->h_source,
1591                                      ethhdr->h_dest);
1592 
1593         if (!nc_path)
1594                 goto out;
1595 
1596         /* Clone skb and adjust skb->data to point at batman header */
1597         skb = skb_clone(skb, GFP_ATOMIC);
1598         if (unlikely(!skb))
1599                 goto free_nc_path;
1600 
1601         if (unlikely(!pskb_may_pull(skb, ETH_HLEN)))
1602                 goto free_skb;
1603 
1604         if (unlikely(!skb_pull_rcsum(skb, ETH_HLEN)))
1605                 goto free_skb;
1606 
1607         /* Add skb to nc_path */
1608         packet_id = batadv_skb_crc32(skb, payload + sizeof(*packet));
1609         if (!batadv_nc_skb_add_to_path(skb, nc_path, NULL, packet_id))
1610                 goto free_skb;
1611 
1612         batadv_inc_counter(bat_priv, BATADV_CNT_NC_BUFFER);
1613         return;
1614 
1615 free_skb:
1616         kfree_skb(skb);
1617 free_nc_path:
1618         batadv_nc_path_put(nc_path);
1619 out:
1620         return;
1621 }
1622 
1623 /**
1624  * batadv_nc_skb_store_sniffed_unicast - check if a received unicast packet
1625  *  should be saved in the decoding buffer and, if so, store it there
1626  * @bat_priv: the bat priv with all the soft interface information
1627  * @skb: unicast skb to store
1628  */
1629 void batadv_nc_skb_store_sniffed_unicast(struct batadv_priv *bat_priv,
1630                                          struct sk_buff *skb)
1631 {
1632         struct ethhdr *ethhdr = eth_hdr(skb);
1633 
1634         if (batadv_is_my_mac(bat_priv, ethhdr->h_dest))
1635                 return;
1636 
1637         /* Set data pointer to MAC header to mimic packets from our tx path */
1638         skb_push(skb, ETH_HLEN);
1639 
1640         batadv_nc_skb_store_for_decoding(bat_priv, skb);
1641 }
1642 
1643 /**
1644  * batadv_nc_skb_decode_packet - decode given skb using the decode data stored
1645  *  in nc_packet
1646  * @bat_priv: the bat priv with all the soft interface information
1647  * @skb: unicast skb to decode
1648  * @nc_packet: decode data needed to decode the skb
1649  *
1650  * Return: pointer to decoded unicast packet if the packet was decoded or NULL
1651  * in case of an error.
1652  */
1653 static struct batadv_unicast_packet *
1654 batadv_nc_skb_decode_packet(struct batadv_priv *bat_priv, struct sk_buff *skb,
1655                             struct batadv_nc_packet *nc_packet)
1656 {
1657         const int h_size = sizeof(struct batadv_unicast_packet);
1658         const int h_diff = sizeof(struct batadv_coded_packet) - h_size;
1659         struct batadv_unicast_packet *unicast_packet;
1660         struct batadv_coded_packet coded_packet_tmp;
1661         struct ethhdr *ethhdr, ethhdr_tmp;
1662         u8 *orig_dest, ttl, ttvn;
1663         unsigned int coding_len;
1664         int err;
1665 
1666         /* Save headers temporarily */
1667         memcpy(&coded_packet_tmp, skb->data, sizeof(coded_packet_tmp));
1668         memcpy(&ethhdr_tmp, skb_mac_header(skb), sizeof(ethhdr_tmp));
1669 
1670         if (skb_cow(skb, 0) < 0)
1671                 return NULL;
1672 
1673         if (unlikely(!skb_pull_rcsum(skb, h_diff)))
1674                 return NULL;
1675 
1676         /* Data points to batman header, so set mac header 14 bytes before
1677          * and network to data
1678          */
1679         skb_set_mac_header(skb, -ETH_HLEN);
1680         skb_reset_network_header(skb);
1681 
1682         /* Reconstruct original mac header */
1683         ethhdr = eth_hdr(skb);
1684         *ethhdr = ethhdr_tmp;
1685 
1686         /* Select the correct unicast header information based on the location
1687          * of our mac address in the coded_packet header
1688          */
1689         if (batadv_is_my_mac(bat_priv, coded_packet_tmp.second_dest)) {
1690                 /* If we are the second destination the packet was overheard,
1691                  * so the Ethernet address must be copied to h_dest and
1692                  * pkt_type changed from PACKET_OTHERHOST to PACKET_HOST
1693                  */
1694                 ether_addr_copy(ethhdr->h_dest, coded_packet_tmp.second_dest);
1695                 skb->pkt_type = PACKET_HOST;
1696 
1697                 orig_dest = coded_packet_tmp.second_orig_dest;
1698                 ttl = coded_packet_tmp.second_ttl;
1699                 ttvn = coded_packet_tmp.second_ttvn;
1700         } else {
1701                 orig_dest = coded_packet_tmp.first_orig_dest;
1702                 ttl = coded_packet_tmp.ttl;
1703                 ttvn = coded_packet_tmp.first_ttvn;
1704         }
1705 
1706         coding_len = ntohs(coded_packet_tmp.coded_len);
1707 
1708         if (coding_len > skb->len)
1709                 return NULL;
1710 
1711         /* Here the magic is reversed:
1712          *   extract the missing packet from the received coded packet
1713          */
1714         batadv_nc_memxor(skb->data + h_size,
1715                          nc_packet->skb->data + h_size,
1716                          coding_len);
1717 
1718         /* Resize decoded skb if decoded with larger packet */
1719         if (nc_packet->skb->len > coding_len + h_size) {
1720                 err = pskb_trim_rcsum(skb, coding_len + h_size);
1721                 if (err)
1722                         return NULL;
1723         }
1724 
1725         /* Create decoded unicast packet */
1726         unicast_packet = (struct batadv_unicast_packet *)skb->data;
1727         unicast_packet->packet_type = BATADV_UNICAST;
1728         unicast_packet->version = BATADV_COMPAT_VERSION;
1729         unicast_packet->ttl = ttl;
1730         ether_addr_copy(unicast_packet->dest, orig_dest);
1731         unicast_packet->ttvn = ttvn;
1732 
1733         batadv_nc_packet_free(nc_packet);
1734         return unicast_packet;
1735 }
1736 
1737 /**
1738  * batadv_nc_find_decoding_packet - search through buffered decoding data to
1739  *  find the data needed to decode the coded packet
1740  * @bat_priv: the bat priv with all the soft interface information
1741  * @ethhdr: pointer to the ethernet header inside the coded packet
1742  * @coded: coded packet we try to find decode data for
1743  *
1744  * Return: pointer to nc packet if the needed data was found or NULL otherwise.
1745  */
1746 static struct batadv_nc_packet *
1747 batadv_nc_find_decoding_packet(struct batadv_priv *bat_priv,
1748                                struct ethhdr *ethhdr,
1749                                struct batadv_coded_packet *coded)
1750 {
1751         struct batadv_hashtable *hash = bat_priv->nc.decoding_hash;
1752         struct batadv_nc_packet *tmp_nc_packet, *nc_packet = NULL;
1753         struct batadv_nc_path *nc_path, nc_path_key;
1754         u8 *dest, *source;
1755         __be32 packet_id;
1756         int index;
1757 
1758         if (!hash)
1759                 return NULL;
1760 
1761         /* Select the correct packet id based on the location of our mac-addr */
1762         dest = ethhdr->h_source;
1763         if (!batadv_is_my_mac(bat_priv, coded->second_dest)) {
1764                 source = coded->second_source;
1765                 packet_id = coded->second_crc;
1766         } else {
1767                 source = coded->first_source;
1768                 packet_id = coded->first_crc;
1769         }
1770 
1771         batadv_nc_hash_key_gen(&nc_path_key, source, dest);
1772         index = batadv_nc_hash_choose(&nc_path_key, hash->size);
1773 
1774         /* Search for matching coding path */
1775         rcu_read_lock();
1776         hlist_for_each_entry_rcu(nc_path, &hash->table[index], hash_entry) {
1777                 /* Find matching nc_packet */
1778                 spin_lock_bh(&nc_path->packet_list_lock);
1779                 list_for_each_entry(tmp_nc_packet,
1780                                     &nc_path->packet_list, list) {
1781                         if (packet_id == tmp_nc_packet->packet_id) {
1782                                 list_del(&tmp_nc_packet->list);
1783 
1784                                 nc_packet = tmp_nc_packet;
1785                                 break;
1786                         }
1787                 }
1788                 spin_unlock_bh(&nc_path->packet_list_lock);
1789 
1790                 if (nc_packet)
1791                         break;
1792         }
1793         rcu_read_unlock();
1794 
1795         if (!nc_packet)
1796                 batadv_dbg(BATADV_DBG_NC, bat_priv,
1797                            "No decoding packet found for %u\n", packet_id);
1798 
1799         return nc_packet;
1800 }
1801 
1802 /**
1803  * batadv_nc_recv_coded_packet - try to decode coded packet and enqueue the
1804  *  resulting unicast packet
1805  * @skb: incoming coded packet
1806  * @recv_if: pointer to interface this packet was received on
1807  *
1808  * Return: NET_RX_SUCCESS if the packet has been consumed or NET_RX_DROP
1809  * otherwise.
1810  */
1811 static int batadv_nc_recv_coded_packet(struct sk_buff *skb,
1812                                        struct batadv_hard_iface *recv_if)
1813 {
1814         struct batadv_priv *bat_priv = netdev_priv(recv_if->soft_iface);
1815         struct batadv_unicast_packet *unicast_packet;
1816         struct batadv_coded_packet *coded_packet;
1817         struct batadv_nc_packet *nc_packet;
1818         struct ethhdr *ethhdr;
1819         int hdr_size = sizeof(*coded_packet);
1820 
1821         /* Check if network coding is enabled */
1822         if (!atomic_read(&bat_priv->network_coding))
1823                 return NET_RX_DROP;
1824 
1825         /* Make sure we can access (and remove) header */
1826         if (unlikely(!pskb_may_pull(skb, hdr_size)))
1827                 return NET_RX_DROP;
1828 
1829         coded_packet = (struct batadv_coded_packet *)skb->data;
1830         ethhdr = eth_hdr(skb);
1831 
1832         /* Verify frame is destined for us */
1833         if (!batadv_is_my_mac(bat_priv, ethhdr->h_dest) &&
1834             !batadv_is_my_mac(bat_priv, coded_packet->second_dest))
1835                 return NET_RX_DROP;
1836 
1837         /* Update stat counter */
1838         if (batadv_is_my_mac(bat_priv, coded_packet->second_dest))
1839                 batadv_inc_counter(bat_priv, BATADV_CNT_NC_SNIFFED);
1840 
1841         nc_packet = batadv_nc_find_decoding_packet(bat_priv, ethhdr,
1842                                                    coded_packet);
1843         if (!nc_packet) {
1844                 batadv_inc_counter(bat_priv, BATADV_CNT_NC_DECODE_FAILED);
1845                 return NET_RX_DROP;
1846         }
1847 
1848         /* Make skb's linear, because decoding accesses the entire buffer */
1849         if (skb_linearize(skb) < 0)
1850                 goto free_nc_packet;
1851 
1852         if (skb_linearize(nc_packet->skb) < 0)
1853                 goto free_nc_packet;
1854 
1855         /* Decode the packet */
1856         unicast_packet = batadv_nc_skb_decode_packet(bat_priv, skb, nc_packet);
1857         if (!unicast_packet) {
1858                 batadv_inc_counter(bat_priv, BATADV_CNT_NC_DECODE_FAILED);
1859                 goto free_nc_packet;
1860         }
1861 
1862         /* Mark packet as decoded to do correct recoding when forwarding */
1863         BATADV_SKB_CB(skb)->decoded = true;
1864         batadv_inc_counter(bat_priv, BATADV_CNT_NC_DECODE);
1865         batadv_add_counter(bat_priv, BATADV_CNT_NC_DECODE_BYTES,
1866                            skb->len + ETH_HLEN);
1867         return batadv_recv_unicast_packet(skb, recv_if);
1868 
1869 free_nc_packet:
1870         batadv_nc_packet_free(nc_packet);
1871         return NET_RX_DROP;
1872 }
1873 
1874 /**
1875  * batadv_nc_mesh_free - clean up network coding memory
1876  * @bat_priv: the bat priv with all the soft interface information
1877  */
1878 void batadv_nc_mesh_free(struct batadv_priv *bat_priv)
1879 {
1880         batadv_tvlv_container_unregister(bat_priv, BATADV_TVLV_NC, 1);
1881         batadv_tvlv_handler_unregister(bat_priv, BATADV_TVLV_NC, 1);
1882         cancel_delayed_work_sync(&bat_priv->nc.work);
1883 
1884         batadv_nc_purge_paths(bat_priv, bat_priv->nc.coding_hash, NULL);
1885         batadv_hash_destroy(bat_priv->nc.coding_hash);
1886         batadv_nc_purge_paths(bat_priv, bat_priv->nc.decoding_hash, NULL);
1887         batadv_hash_destroy(bat_priv->nc.decoding_hash);
1888 }
1889 
1890 /**
1891  * batadv_nc_nodes_seq_print_text - print the nc node information
1892  * @seq: seq file to print on
1893  * @offset: not used
1894  *
1895  * Return: always 0
1896  */
1897 int batadv_nc_nodes_seq_print_text(struct seq_file *seq, void *offset)
1898 {
1899         struct net_device *net_dev = (struct net_device *)seq->private;
1900         struct batadv_priv *bat_priv = netdev_priv(net_dev);
1901         struct batadv_hashtable *hash = bat_priv->orig_hash;
1902         struct batadv_hard_iface *primary_if;
1903         struct hlist_head *head;
1904         struct batadv_orig_node *orig_node;
1905         struct batadv_nc_node *nc_node;
1906         int i;
1907 
1908         primary_if = batadv_seq_print_text_primary_if_get(seq);
1909         if (!primary_if)
1910                 goto out;
1911 
1912         /* Traverse list of originators */
1913         for (i = 0; i < hash->size; i++) {
1914                 head = &hash->table[i];
1915 
1916                 /* For each orig_node in this bin */
1917                 rcu_read_lock();
1918                 hlist_for_each_entry_rcu(orig_node, head, hash_entry) {
1919                         /* no need to print the orig node if it does not have
1920                          * network coding neighbors
1921                          */
1922                         if (list_empty(&orig_node->in_coding_list) &&
1923                             list_empty(&orig_node->out_coding_list))
1924                                 continue;
1925 
1926                         seq_printf(seq, "Node:      %pM\n", orig_node->orig);
1927 
1928                         seq_puts(seq, " Ingoing:  ");
1929                         /* For each in_nc_node to this orig_node */
1930                         list_for_each_entry_rcu(nc_node,
1931                                                 &orig_node->in_coding_list,
1932                                                 list)
1933                                 seq_printf(seq, "%pM ",
1934                                            nc_node->addr);
1935                         seq_puts(seq, "\n");
1936 
1937                         seq_puts(seq, " Outgoing: ");
1938                         /* For out_nc_node to this orig_node */
1939                         list_for_each_entry_rcu(nc_node,
1940                                                 &orig_node->out_coding_list,
1941                                                 list)
1942                                 seq_printf(seq, "%pM ",
1943                                            nc_node->addr);
1944                         seq_puts(seq, "\n\n");
1945                 }
1946                 rcu_read_unlock();
1947         }
1948 
1949 out:
1950         if (primary_if)
1951                 batadv_hardif_put(primary_if);
1952         return 0;
1953 }
1954 
1955 /**
1956  * batadv_nc_init_debugfs - create nc folder and related files in debugfs
1957  * @bat_priv: the bat priv with all the soft interface information
1958  *
1959  * Return: 0 on success or negative error number in case of failure
1960  */
1961 int batadv_nc_init_debugfs(struct batadv_priv *bat_priv)
1962 {
1963         struct dentry *nc_dir, *file;
1964 
1965         nc_dir = debugfs_create_dir("nc", bat_priv->debug_dir);
1966         if (!nc_dir)
1967                 goto out;
1968 
1969         file = debugfs_create_u8("min_tq", S_IRUGO | S_IWUSR, nc_dir,
1970                                  &bat_priv->nc.min_tq);
1971         if (!file)
1972                 goto out;
1973 
1974         file = debugfs_create_u32("max_fwd_delay", S_IRUGO | S_IWUSR, nc_dir,
1975                                   &bat_priv->nc.max_fwd_delay);
1976         if (!file)
1977                 goto out;
1978 
1979         file = debugfs_create_u32("max_buffer_time", S_IRUGO | S_IWUSR, nc_dir,
1980                                   &bat_priv->nc.max_buffer_time);
1981         if (!file)
1982                 goto out;
1983 
1984         return 0;
1985 
1986 out:
1987         return -ENOMEM;
1988 }
1989 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp