Commit | Line | Data |
---|---|---|
d353d8d4 MH |
1 | /* Copyright (C) 2012-2013 B.A.T.M.A.N. contributors: |
2 | * | |
3 | * Martin Hundebøll, Jeppe Ledet-Pedersen | |
4 | * | |
5 | * This program is free software; you can redistribute it and/or | |
6 | * modify it under the terms of version 2 of the GNU General Public | |
7 | * License as published by the Free Software Foundation. | |
8 | * | |
9 | * This program is distributed in the hope that it will be useful, but | |
10 | * WITHOUT ANY WARRANTY; without even the implied warranty of | |
11 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
12 | * General Public License for more details. | |
13 | * | |
14 | * You should have received a copy of the GNU General Public License | |
15 | * along with this program; if not, write to the Free Software | |
16 | * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA | |
17 | * 02110-1301, USA | |
18 | */ | |
19 | ||
d56b1705 MH |
20 | #include <linux/debugfs.h> |
21 | ||
d353d8d4 MH |
22 | #include "main.h" |
23 | #include "network-coding.h" | |
d56b1705 MH |
24 | #include "originator.h" |
25 | #include "hard-interface.h" | |
d353d8d4 MH |
26 | |
27 | static void batadv_nc_worker(struct work_struct *work); | |
28 | ||
29 | /** | |
30 | * batadv_nc_start_timer - initialise the nc periodic worker | |
31 | * @bat_priv: the bat priv with all the soft interface information | |
32 | */ | |
33 | static void batadv_nc_start_timer(struct batadv_priv *bat_priv) | |
34 | { | |
35 | queue_delayed_work(batadv_event_workqueue, &bat_priv->nc.work, | |
36 | msecs_to_jiffies(10)); | |
37 | } | |
38 | ||
39 | /** | |
40 | * batadv_nc_init - initialise coding hash table and start house keeping | |
41 | * @bat_priv: the bat priv with all the soft interface information | |
42 | */ | |
43 | int batadv_nc_init(struct batadv_priv *bat_priv) | |
44 | { | |
45 | INIT_DELAYED_WORK(&bat_priv->nc.work, batadv_nc_worker); | |
46 | batadv_nc_start_timer(bat_priv); | |
47 | ||
48 | return 0; | |
49 | } | |
50 | ||
51 | /** | |
52 | * batadv_nc_init_bat_priv - initialise the nc specific bat_priv variables | |
53 | * @bat_priv: the bat priv with all the soft interface information | |
54 | */ | |
55 | void batadv_nc_init_bat_priv(struct batadv_priv *bat_priv) | |
56 | { | |
57 | atomic_set(&bat_priv->network_coding, 1); | |
d56b1705 MH |
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 | */ | |
65 | void 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 | */ | |
78 | static 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 | */ | |
92 | static 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 | */ | |
105 | static 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 | */ | |
125 | static void | |
126 | batadv_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 | */ | |
162 | void 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 | */ | |
183 | static 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 | } | |
d353d8d4 MH |
203 | } |
204 | ||
205 | /** | |
206 | * batadv_nc_worker - periodic task for house keeping related to network coding | |
207 | * @work: kernel work struct | |
208 | */ | |
209 | static void batadv_nc_worker(struct work_struct *work) | |
210 | { | |
211 | struct delayed_work *delayed_work; | |
212 | struct batadv_priv_nc *priv_nc; | |
213 | struct batadv_priv *bat_priv; | |
214 | ||
215 | delayed_work = container_of(work, struct delayed_work, work); | |
216 | priv_nc = container_of(delayed_work, struct batadv_priv_nc, work); | |
217 | bat_priv = container_of(priv_nc, struct batadv_priv, nc); | |
218 | ||
d56b1705 MH |
219 | batadv_nc_purge_orig_hash(bat_priv); |
220 | ||
d353d8d4 MH |
221 | /* Schedule a new check */ |
222 | batadv_nc_start_timer(bat_priv); | |
223 | } | |
224 | ||
d56b1705 MH |
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 | */ | |
238 | static 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 | */ | |
263 | static 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 | */ | |
305 | static 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 | ||
354 | free: | |
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 | */ | |
369 | void 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 | ||
402 | out: | |
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 | ||
d353d8d4 MH |
409 | /** |
410 | * batadv_nc_free - clean up network coding memory | |
411 | * @bat_priv: the bat priv with all the soft interface information | |
412 | */ | |
413 | void batadv_nc_free(struct batadv_priv *bat_priv) | |
414 | { | |
415 | cancel_delayed_work_sync(&bat_priv->nc.work); | |
416 | } | |
d56b1705 MH |
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 | */ | |
423 | int 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 | ||
468 | out: | |
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 | */ | |
478 | int 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 | ||
493 | out: | |
494 | return -ENOMEM; | |
495 | } |