aboutsummaryrefslogtreecommitdiffstats
path: root/net/batman-adv/network-coding.c
diff options
context:
space:
mode:
Diffstat (limited to 'net/batman-adv/network-coding.c')
-rw-r--r--net/batman-adv/network-coding.c414
1 files changed, 414 insertions, 0 deletions
diff --git a/net/batman-adv/network-coding.c b/net/batman-adv/network-coding.c
index 9c2d54bdd2ce..ff4985d84726 100644
--- a/net/batman-adv/network-coding.c
+++ b/net/batman-adv/network-coding.c
@@ -17,8 +17,12 @@
17 * 02110-1301, USA 17 * 02110-1301, USA
18 */ 18 */
19 19
20#include <linux/debugfs.h>
21
20#include "main.h" 22#include "main.h"
21#include "network-coding.h" 23#include "network-coding.h"
24#include "originator.h"
25#include "hard-interface.h"
22 26
23static void batadv_nc_worker(struct work_struct *work); 27static void batadv_nc_worker(struct work_struct *work);
24 28
@@ -51,6 +55,151 @@ int batadv_nc_init(struct batadv_priv *bat_priv)
51void batadv_nc_init_bat_priv(struct batadv_priv *bat_priv) 55void batadv_nc_init_bat_priv(struct batadv_priv *bat_priv)
52{ 56{
53 atomic_set(&bat_priv->network_coding, 1); 57 atomic_set(&bat_priv->network_coding, 1);
58 bat_priv->nc.min_tq = 200;
59}
60
61/**
62 * batadv_nc_init_orig - initialise the nc fields of an orig_node
63 * @orig_node: the orig_node which is going to be initialised
64 */
65void batadv_nc_init_orig(struct batadv_orig_node *orig_node)
66{
67 INIT_LIST_HEAD(&orig_node->in_coding_list);
68 INIT_LIST_HEAD(&orig_node->out_coding_list);
69 spin_lock_init(&orig_node->in_coding_list_lock);
70 spin_lock_init(&orig_node->out_coding_list_lock);
71}
72
73/**
74 * batadv_nc_node_free_rcu - rcu callback to free an nc node and remove
75 * its refcount on the orig_node
76 * @rcu: rcu pointer of the nc node
77 */
78static void batadv_nc_node_free_rcu(struct rcu_head *rcu)
79{
80 struct batadv_nc_node *nc_node;
81
82 nc_node = container_of(rcu, struct batadv_nc_node, rcu);
83 batadv_orig_node_free_ref(nc_node->orig_node);
84 kfree(nc_node);
85}
86
87/**
88 * batadv_nc_node_free_ref - decrements the nc node refcounter and possibly
89 * frees it
90 * @nc_node: the nc node to free
91 */
92static void batadv_nc_node_free_ref(struct batadv_nc_node *nc_node)
93{
94 if (atomic_dec_and_test(&nc_node->refcount))
95 call_rcu(&nc_node->rcu, batadv_nc_node_free_rcu);
96}
97
98/**
99 * batadv_nc_to_purge_nc_node - checks whether an nc node has to be purged
100 * @bat_priv: the bat priv with all the soft interface information
101 * @nc_node: the nc node to check
102 *
103 * Returns true if the entry has to be purged now, false otherwise
104 */
105static bool batadv_nc_to_purge_nc_node(struct batadv_priv *bat_priv,
106 struct batadv_nc_node *nc_node)
107{
108 if (atomic_read(&bat_priv->mesh_state) != BATADV_MESH_ACTIVE)
109 return true;
110
111 return batadv_has_timed_out(nc_node->last_seen, BATADV_NC_NODE_TIMEOUT);
112}
113
114/**
115 * batadv_nc_purge_orig_nc_nodes - go through list of nc nodes and purge stale
116 * entries
117 * @bat_priv: the bat priv with all the soft interface information
118 * @list: list of nc nodes
119 * @lock: nc node list lock
120 * @to_purge: function in charge to decide whether an entry has to be purged or
121 * not. This function takes the nc node as argument and has to return
122 * a boolean value: true if the entry has to be deleted, false
123 * otherwise
124 */
125static void
126batadv_nc_purge_orig_nc_nodes(struct batadv_priv *bat_priv,
127 struct list_head *list,
128 spinlock_t *lock,
129 bool (*to_purge)(struct batadv_priv *,
130 struct batadv_nc_node *))
131{
132 struct batadv_nc_node *nc_node, *nc_node_tmp;
133
134 /* For each nc_node in list */
135 spin_lock_bh(lock);
136 list_for_each_entry_safe(nc_node, nc_node_tmp, list, list) {
137 /* if an helper function has been passed as parameter,
138 * ask it if the entry has to be purged or not
139 */
140 if (to_purge && !to_purge(bat_priv, nc_node))
141 continue;
142
143 batadv_dbg(BATADV_DBG_NC, bat_priv,
144 "Removing nc_node %pM -> %pM\n",
145 nc_node->addr, nc_node->orig_node->orig);
146 list_del_rcu(&nc_node->list);
147 batadv_nc_node_free_ref(nc_node);
148 }
149 spin_unlock_bh(lock);
150}
151
152/**
153 * batadv_nc_purge_orig - purges all nc node data attached of the given
154 * originator
155 * @bat_priv: the bat priv with all the soft interface information
156 * @orig_node: orig_node with the nc node entries to be purged
157 * @to_purge: function in charge to decide whether an entry has to be purged or
158 * not. This function takes the nc node as argument and has to return
159 * a boolean value: true is the entry has to be deleted, false
160 * otherwise
161 */
162void batadv_nc_purge_orig(struct batadv_priv *bat_priv,
163 struct batadv_orig_node *orig_node,
164 bool (*to_purge)(struct batadv_priv *,
165 struct batadv_nc_node *))
166{
167 /* Check ingoing nc_node's of this orig_node */
168 batadv_nc_purge_orig_nc_nodes(bat_priv, &orig_node->in_coding_list,
169 &orig_node->in_coding_list_lock,
170 to_purge);
171
172 /* Check outgoing nc_node's of this orig_node */
173 batadv_nc_purge_orig_nc_nodes(bat_priv, &orig_node->out_coding_list,
174 &orig_node->out_coding_list_lock,
175 to_purge);
176}
177
178/**
179 * batadv_nc_purge_orig_hash - traverse entire originator hash to check if they
180 * have timed out nc nodes
181 * @bat_priv: the bat priv with all the soft interface information
182 */
183static void batadv_nc_purge_orig_hash(struct batadv_priv *bat_priv)
184{
185 struct batadv_hashtable *hash = bat_priv->orig_hash;
186 struct hlist_head *head;
187 struct batadv_orig_node *orig_node;
188 uint32_t i;
189
190 if (!hash)
191 return;
192
193 /* For each orig_node */
194 for (i = 0; i < hash->size; i++) {
195 head = &hash->table[i];
196
197 rcu_read_lock();
198 hlist_for_each_entry_rcu(orig_node, head, hash_entry)
199 batadv_nc_purge_orig(bat_priv, orig_node,
200 batadv_nc_to_purge_nc_node);
201 rcu_read_unlock();
202 }
54} 203}
55 204
56/** 205/**
@@ -67,11 +216,197 @@ static void batadv_nc_worker(struct work_struct *work)
67 priv_nc = container_of(delayed_work, struct batadv_priv_nc, work); 216 priv_nc = container_of(delayed_work, struct batadv_priv_nc, work);
68 bat_priv = container_of(priv_nc, struct batadv_priv, nc); 217 bat_priv = container_of(priv_nc, struct batadv_priv, nc);
69 218
219 batadv_nc_purge_orig_hash(bat_priv);
220
70 /* Schedule a new check */ 221 /* Schedule a new check */
71 batadv_nc_start_timer(bat_priv); 222 batadv_nc_start_timer(bat_priv);
72} 223}
73 224
74/** 225/**
226 * batadv_can_nc_with_orig - checks whether the given orig node is suitable for
227 * coding or not
228 * @bat_priv: the bat priv with all the soft interface information
229 * @orig_node: neighboring orig node which may be used as nc candidate
230 * @ogm_packet: incoming ogm packet also used for the checks
231 *
232 * Returns true if:
233 * 1) The OGM must have the most recent sequence number.
234 * 2) The TTL must be decremented by one and only one.
235 * 3) The OGM must be received from the first hop from orig_node.
236 * 4) The TQ value of the OGM must be above bat_priv->nc.min_tq.
237 */
238static bool batadv_can_nc_with_orig(struct batadv_priv *bat_priv,
239 struct batadv_orig_node *orig_node,
240 struct batadv_ogm_packet *ogm_packet)
241{
242 if (orig_node->last_real_seqno != ogm_packet->seqno)
243 return false;
244 if (orig_node->last_ttl != ogm_packet->header.ttl + 1)
245 return false;
246 if (!batadv_compare_eth(ogm_packet->orig, ogm_packet->prev_sender))
247 return false;
248 if (ogm_packet->tq < bat_priv->nc.min_tq)
249 return false;
250
251 return true;
252}
253
254/**
255 * batadv_nc_find_nc_node - search for an existing nc node and return it
256 * @orig_node: orig node originating the ogm packet
257 * @orig_neigh_node: neighboring orig node from which we received the ogm packet
258 * (can be equal to orig_node)
259 * @in_coding: traverse incoming or outgoing network coding list
260 *
261 * Returns the nc_node if found, NULL otherwise.
262 */
263static struct batadv_nc_node
264*batadv_nc_find_nc_node(struct batadv_orig_node *orig_node,
265 struct batadv_orig_node *orig_neigh_node,
266 bool in_coding)
267{
268 struct batadv_nc_node *nc_node, *nc_node_out = NULL;
269 struct list_head *list;
270
271 if (in_coding)
272 list = &orig_neigh_node->in_coding_list;
273 else
274 list = &orig_neigh_node->out_coding_list;
275
276 /* Traverse list of nc_nodes to orig_node */
277 rcu_read_lock();
278 list_for_each_entry_rcu(nc_node, list, list) {
279 if (!batadv_compare_eth(nc_node->addr, orig_node->orig))
280 continue;
281
282 if (!atomic_inc_not_zero(&nc_node->refcount))
283 continue;
284
285 /* Found a match */
286 nc_node_out = nc_node;
287 break;
288 }
289 rcu_read_unlock();
290
291 return nc_node_out;
292}
293
294/**
295 * batadv_nc_get_nc_node - retrieves an nc node or creates the entry if it was
296 * not found
297 * @bat_priv: the bat priv with all the soft interface information
298 * @orig_node: orig node originating the ogm packet
299 * @orig_neigh_node: neighboring orig node from which we received the ogm packet
300 * (can be equal to orig_node)
301 * @in_coding: traverse incoming or outgoing network coding list
302 *
303 * Returns the nc_node if found or created, NULL in case of an error.
304 */
305static struct batadv_nc_node
306*batadv_nc_get_nc_node(struct batadv_priv *bat_priv,
307 struct batadv_orig_node *orig_node,
308 struct batadv_orig_node *orig_neigh_node,
309 bool in_coding)
310{
311 struct batadv_nc_node *nc_node;
312 spinlock_t *lock; /* Used to lock list selected by "int in_coding" */
313 struct list_head *list;
314
315 /* Check if nc_node is already added */
316 nc_node = batadv_nc_find_nc_node(orig_node, orig_neigh_node, in_coding);
317
318 /* Node found */
319 if (nc_node)
320 return nc_node;
321
322 nc_node = kzalloc(sizeof(*nc_node), GFP_ATOMIC);
323 if (!nc_node)
324 return NULL;
325
326 if (!atomic_inc_not_zero(&orig_neigh_node->refcount))
327 goto free;
328
329 /* Initialize nc_node */
330 INIT_LIST_HEAD(&nc_node->list);
331 memcpy(nc_node->addr, orig_node->orig, ETH_ALEN);
332 nc_node->orig_node = orig_neigh_node;
333 atomic_set(&nc_node->refcount, 2);
334
335 /* Select ingoing or outgoing coding node */
336 if (in_coding) {
337 lock = &orig_neigh_node->in_coding_list_lock;
338 list = &orig_neigh_node->in_coding_list;
339 } else {
340 lock = &orig_neigh_node->out_coding_list_lock;
341 list = &orig_neigh_node->out_coding_list;
342 }
343
344 batadv_dbg(BATADV_DBG_NC, bat_priv, "Adding nc_node %pM -> %pM\n",
345 nc_node->addr, nc_node->orig_node->orig);
346
347 /* Add nc_node to orig_node */
348 spin_lock_bh(lock);
349 list_add_tail_rcu(&nc_node->list, list);
350 spin_unlock_bh(lock);
351
352 return nc_node;
353
354free:
355 kfree(nc_node);
356 return NULL;
357}
358
359/**
360 * batadv_nc_update_nc_node - updates stored incoming and outgoing nc node structs
361 * (best called on incoming OGMs)
362 * @bat_priv: the bat priv with all the soft interface information
363 * @orig_node: orig node originating the ogm packet
364 * @orig_neigh_node: neighboring orig node from which we received the ogm packet
365 * (can be equal to orig_node)
366 * @ogm_packet: incoming ogm packet
367 * @is_single_hop_neigh: orig_node is a single hop neighbor
368 */
369void batadv_nc_update_nc_node(struct batadv_priv *bat_priv,
370 struct batadv_orig_node *orig_node,
371 struct batadv_orig_node *orig_neigh_node,
372 struct batadv_ogm_packet *ogm_packet,
373 int is_single_hop_neigh)
374{
375 struct batadv_nc_node *in_nc_node = NULL, *out_nc_node = NULL;
376
377 /* Check if network coding is enabled */
378 if (!atomic_read(&bat_priv->network_coding))
379 goto out;
380
381 /* accept ogms from 'good' neighbors and single hop neighbors */
382 if (!batadv_can_nc_with_orig(bat_priv, orig_node, ogm_packet) &&
383 !is_single_hop_neigh)
384 goto out;
385
386 /* Add orig_node as in_nc_node on hop */
387 in_nc_node = batadv_nc_get_nc_node(bat_priv, orig_node,
388 orig_neigh_node, true);
389 if (!in_nc_node)
390 goto out;
391
392 in_nc_node->last_seen = jiffies;
393
394 /* Add hop as out_nc_node on orig_node */
395 out_nc_node = batadv_nc_get_nc_node(bat_priv, orig_neigh_node,
396 orig_node, false);
397 if (!out_nc_node)
398 goto out;
399
400 out_nc_node->last_seen = jiffies;
401
402out:
403 if (in_nc_node)
404 batadv_nc_node_free_ref(in_nc_node);
405 if (out_nc_node)
406 batadv_nc_node_free_ref(out_nc_node);
407}
408
409/**
75 * batadv_nc_free - clean up network coding memory 410 * batadv_nc_free - clean up network coding memory
76 * @bat_priv: the bat priv with all the soft interface information 411 * @bat_priv: the bat priv with all the soft interface information
77 */ 412 */
@@ -79,3 +414,82 @@ void batadv_nc_free(struct batadv_priv *bat_priv)
79{ 414{
80 cancel_delayed_work_sync(&bat_priv->nc.work); 415 cancel_delayed_work_sync(&bat_priv->nc.work);
81} 416}
417
418/**
419 * batadv_nc_nodes_seq_print_text - print the nc node information
420 * @seq: seq file to print on
421 * @offset: not used
422 */
423int batadv_nc_nodes_seq_print_text(struct seq_file *seq, void *offset)
424{
425 struct net_device *net_dev = (struct net_device *)seq->private;
426 struct batadv_priv *bat_priv = netdev_priv(net_dev);
427 struct batadv_hashtable *hash = bat_priv->orig_hash;
428 struct batadv_hard_iface *primary_if;
429 struct hlist_head *head;
430 struct batadv_orig_node *orig_node;
431 struct batadv_nc_node *nc_node;
432 int i;
433
434 primary_if = batadv_seq_print_text_primary_if_get(seq);
435 if (!primary_if)
436 goto out;
437
438 /* Traverse list of originators */
439 for (i = 0; i < hash->size; i++) {
440 head = &hash->table[i];
441
442 /* For each orig_node in this bin */
443 rcu_read_lock();
444 hlist_for_each_entry_rcu(orig_node, head, hash_entry) {
445 seq_printf(seq, "Node: %pM\n", orig_node->orig);
446
447 seq_printf(seq, " Ingoing: ");
448 /* For each in_nc_node to this orig_node */
449 list_for_each_entry_rcu(nc_node,
450 &orig_node->in_coding_list,
451 list)
452 seq_printf(seq, "%pM ",
453 nc_node->addr);
454 seq_printf(seq, "\n");
455
456 seq_printf(seq, " Outgoing: ");
457 /* For out_nc_node to this orig_node */
458 list_for_each_entry_rcu(nc_node,
459 &orig_node->out_coding_list,
460 list)
461 seq_printf(seq, "%pM ",
462 nc_node->addr);
463 seq_printf(seq, "\n\n");
464 }
465 rcu_read_unlock();
466 }
467
468out:
469 if (primary_if)
470 batadv_hardif_free_ref(primary_if);
471 return 0;
472}
473
474/**
475 * batadv_nc_init_debugfs - create nc folder and related files in debugfs
476 * @bat_priv: the bat priv with all the soft interface information
477 */
478int batadv_nc_init_debugfs(struct batadv_priv *bat_priv)
479{
480 struct dentry *nc_dir, *file;
481
482 nc_dir = debugfs_create_dir("nc", bat_priv->debug_dir);
483 if (!nc_dir)
484 goto out;
485
486 file = debugfs_create_u8("min_tq", S_IRUGO | S_IWUSR, nc_dir,
487 &bat_priv->nc.min_tq);
488 if (!file)
489 goto out;
490
491 return 0;
492
493out:
494 return -ENOMEM;
495}