1 // SPDX-License-Identifier: GPL-2.0
2 /* Copyright (C) B.A.T.M.A.N. contributors:
3 *
4 * Linus Lüssing, Marek Lindner
5 */
6
7 #include "bat_v_elp.h"
8 #include "main.h"
9
10 #include <linux/atomic.h>
11 #include <linux/bitops.h>
12 #include <linux/byteorder/generic.h>
13 #include <linux/container_of.h>
14 #include <linux/errno.h>
15 #include <linux/etherdevice.h>
16 #include <linux/ethtool.h>
17 #include <linux/gfp.h>
18 #include <linux/if_ether.h>
19 #include <linux/jiffies.h>
20 #include <linux/kref.h>
21 #include <linux/list.h>
22 #include <linux/minmax.h>
23 #include <linux/netdevice.h>
24 #include <linux/nl80211.h>
25 #include <linux/random.h>
26 #include <linux/rculist.h>
27 #include <linux/rcupdate.h>
28 #include <linux/rtnetlink.h>
29 #include <linux/skbuff.h>
30 #include <linux/slab.h>
31 #include <linux/stddef.h>
32 #include <linux/string.h>
33 #include <linux/types.h>
34 #include <linux/workqueue.h>
35 #include <net/cfg80211.h>
36 #include <uapi/linux/batadv_packet.h>
37
38 #include "bat_v_ogm.h"
39 #include "hard-interface.h"
40 #include "log.h"
41 #include "originator.h"
42 #include "routing.h"
43 #include "send.h"
44
45 /**
46 * struct batadv_v_metric_queue_entry - list of hardif neighbors which require
47 * and metric update
48 */
49 struct batadv_v_metric_queue_entry {
50 /** @hardif_neigh: hardif neighbor scheduled for metric update */
51 struct batadv_hardif_neigh_node *hardif_neigh;
52
53 /** @list: list node for metric_queue */
54 struct list_head list;
55 };
56
57 /**
58 * batadv_v_elp_start_timer() - restart timer for ELP periodic work
59 * @hard_iface: the interface for which the timer has to be reset
60 */
batadv_v_elp_start_timer(struct batadv_hard_iface * hard_iface)61 static void batadv_v_elp_start_timer(struct batadv_hard_iface *hard_iface)
62 {
63 unsigned int msecs;
64
65 msecs = atomic_read(&hard_iface->bat_v.elp_interval) - BATADV_JITTER;
66 msecs += get_random_u32_below(2 * BATADV_JITTER);
67
68 queue_delayed_work(batadv_event_workqueue, &hard_iface->bat_v.elp_wq,
69 msecs_to_jiffies(msecs));
70 }
71
72 /**
73 * batadv_v_elp_get_throughput() - get the throughput towards a neighbour
74 * @neigh: the neighbour for which the throughput has to be obtained
75 * @pthroughput: calculated throughput towards the given neighbour in multiples
76 * of 100kpbs (a value of '1' equals 0.1Mbps, '10' equals 1Mbps, etc).
77 *
78 * Return: true when value behind @pthroughput was set
79 */
batadv_v_elp_get_throughput(struct batadv_hardif_neigh_node * neigh,u32 * pthroughput)80 static bool batadv_v_elp_get_throughput(struct batadv_hardif_neigh_node *neigh,
81 u32 *pthroughput)
82 {
83 struct batadv_hard_iface *hard_iface = neigh->if_incoming;
84 struct net_device *mesh_iface = hard_iface->mesh_iface;
85 struct ethtool_link_ksettings link_settings;
86 struct net_device *real_netdev;
87 struct station_info sinfo;
88 u32 throughput;
89 int ret;
90
91 /* don't query throughput when no longer associated with any
92 * batman-adv interface
93 */
94 if (!mesh_iface)
95 return false;
96
97 /* if the user specified a customised value for this interface, then
98 * return it directly
99 */
100 throughput = atomic_read(&hard_iface->bat_v.throughput_override);
101 if (throughput != 0) {
102 *pthroughput = throughput;
103 return true;
104 }
105
106 /* if this is a wireless device, then ask its throughput through
107 * cfg80211 API
108 */
109 if (batadv_is_wifi_hardif(hard_iface)) {
110 if (!batadv_is_cfg80211_hardif(hard_iface))
111 /* unsupported WiFi driver version */
112 goto default_throughput;
113
114 real_netdev = batadv_get_real_netdev(hard_iface->net_dev);
115 if (!real_netdev)
116 goto default_throughput;
117
118 ret = cfg80211_get_station(real_netdev, neigh->addr, &sinfo);
119
120 if (!ret) {
121 /* free the TID stats immediately */
122 cfg80211_sinfo_release_content(&sinfo);
123 }
124
125 dev_put(real_netdev);
126 if (ret == -ENOENT) {
127 /* Node is not associated anymore! It would be
128 * possible to delete this neighbor. For now set
129 * the throughput metric to 0.
130 */
131 *pthroughput = 0;
132 return true;
133 }
134 if (ret)
135 goto default_throughput;
136
137 if (sinfo.filled & BIT(NL80211_STA_INFO_EXPECTED_THROUGHPUT)) {
138 *pthroughput = sinfo.expected_throughput / 100;
139 return true;
140 }
141
142 /* try to estimate the expected throughput based on reported tx
143 * rates
144 */
145 if (sinfo.filled & BIT(NL80211_STA_INFO_TX_BITRATE)) {
146 *pthroughput = cfg80211_calculate_bitrate(&sinfo.txrate) / 3;
147 return true;
148 }
149
150 goto default_throughput;
151 }
152
153 /* only use rtnl_trylock because the elp worker will be cancelled while
154 * the rntl_lock is held. the cancel_delayed_work_sync() would otherwise
155 * wait forever when the elp work_item was started and it is then also
156 * trying to rtnl_lock
157 */
158 if (!rtnl_trylock())
159 return false;
160
161 /* if not a wifi interface, check if this device provides data via
162 * ethtool (e.g. an Ethernet adapter)
163 */
164 ret = __ethtool_get_link_ksettings(hard_iface->net_dev, &link_settings);
165 rtnl_unlock();
166 if (ret == 0) {
167 /* link characteristics might change over time */
168 if (link_settings.base.duplex == DUPLEX_FULL)
169 hard_iface->bat_v.flags |= BATADV_FULL_DUPLEX;
170 else
171 hard_iface->bat_v.flags &= ~BATADV_FULL_DUPLEX;
172
173 throughput = link_settings.base.speed;
174 if (throughput && throughput != SPEED_UNKNOWN) {
175 *pthroughput = throughput * 10;
176 return true;
177 }
178 }
179
180 default_throughput:
181 if (!(hard_iface->bat_v.flags & BATADV_WARNING_DEFAULT)) {
182 batadv_info(mesh_iface,
183 "WiFi driver or ethtool info does not provide information about link speeds on interface %s, therefore defaulting to hardcoded throughput values of %u.%1u Mbps. Consider overriding the throughput manually or checking your driver.\n",
184 hard_iface->net_dev->name,
185 BATADV_THROUGHPUT_DEFAULT_VALUE / 10,
186 BATADV_THROUGHPUT_DEFAULT_VALUE % 10);
187 hard_iface->bat_v.flags |= BATADV_WARNING_DEFAULT;
188 }
189
190 /* if none of the above cases apply, return the base_throughput */
191 *pthroughput = BATADV_THROUGHPUT_DEFAULT_VALUE;
192 return true;
193 }
194
195 /**
196 * batadv_v_elp_throughput_metric_update() - worker updating the throughput
197 * metric of a single hop neighbour
198 * @neigh: the neighbour to probe
199 */
200 static void
batadv_v_elp_throughput_metric_update(struct batadv_hardif_neigh_node * neigh)201 batadv_v_elp_throughput_metric_update(struct batadv_hardif_neigh_node *neigh)
202 {
203 u32 throughput;
204 bool valid;
205
206 valid = batadv_v_elp_get_throughput(neigh, &throughput);
207 if (!valid)
208 return;
209
210 ewma_throughput_add(&neigh->bat_v.throughput, throughput);
211 }
212
213 /**
214 * batadv_v_elp_wifi_neigh_probe() - send link probing packets to a neighbour
215 * @neigh: the neighbour to probe
216 *
217 * Sends a predefined number of unicast wifi packets to a given neighbour in
218 * order to trigger the throughput estimation on this link by the RC algorithm.
219 * Packets are sent only if there is not enough payload unicast traffic towards
220 * this neighbour..
221 *
222 * Return: True on success and false in case of error during skb preparation.
223 */
224 static bool
batadv_v_elp_wifi_neigh_probe(struct batadv_hardif_neigh_node * neigh)225 batadv_v_elp_wifi_neigh_probe(struct batadv_hardif_neigh_node *neigh)
226 {
227 struct batadv_hard_iface *hard_iface = neigh->if_incoming;
228 struct batadv_priv *bat_priv = netdev_priv(hard_iface->mesh_iface);
229 unsigned long last_tx_diff;
230 struct sk_buff *skb;
231 int probe_len, i;
232 int elp_skb_len;
233
234 /* this probing routine is for Wifi neighbours only */
235 if (!batadv_is_wifi_hardif(hard_iface))
236 return true;
237
238 /* probe the neighbor only if no unicast packets have been sent
239 * to it in the last 100 milliseconds: this is the rate control
240 * algorithm sampling interval (minstrel). In this way, if not
241 * enough traffic has been sent to the neighbor, batman-adv can
242 * generate 2 probe packets and push the RC algorithm to perform
243 * the sampling
244 */
245 last_tx_diff = jiffies_to_msecs(jiffies - neigh->bat_v.last_unicast_tx);
246 if (last_tx_diff <= BATADV_ELP_PROBE_MAX_TX_DIFF)
247 return true;
248
249 probe_len = max_t(int, sizeof(struct batadv_elp_packet),
250 BATADV_ELP_MIN_PROBE_SIZE);
251
252 for (i = 0; i < BATADV_ELP_PROBES_PER_NODE; i++) {
253 elp_skb_len = hard_iface->bat_v.elp_skb->len;
254 skb = skb_copy_expand(hard_iface->bat_v.elp_skb, 0,
255 probe_len - elp_skb_len,
256 GFP_ATOMIC);
257 if (!skb)
258 return false;
259
260 /* Tell the skb to get as big as the allocated space (we want
261 * the packet to be exactly of that size to make the link
262 * throughput estimation effective.
263 */
264 skb_put_zero(skb, probe_len - hard_iface->bat_v.elp_skb->len);
265
266 batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
267 "Sending unicast (probe) ELP packet on interface %s to %pM\n",
268 hard_iface->net_dev->name, neigh->addr);
269
270 batadv_send_skb_packet(skb, hard_iface, neigh->addr);
271 }
272
273 return true;
274 }
275
276 /**
277 * batadv_v_elp_periodic_work() - ELP periodic task per interface
278 * @work: work queue item
279 *
280 * Emits broadcast ELP messages in regular intervals.
281 */
batadv_v_elp_periodic_work(struct work_struct * work)282 static void batadv_v_elp_periodic_work(struct work_struct *work)
283 {
284 struct batadv_v_metric_queue_entry *metric_entry;
285 struct batadv_v_metric_queue_entry *metric_safe;
286 struct batadv_hardif_neigh_node *hardif_neigh;
287 struct batadv_hard_iface *hard_iface;
288 struct batadv_hard_iface_bat_v *bat_v;
289 struct batadv_elp_packet *elp_packet;
290 struct list_head metric_queue;
291 struct batadv_priv *bat_priv;
292 struct sk_buff *skb;
293 u32 elp_interval;
294
295 bat_v = container_of(work, struct batadv_hard_iface_bat_v, elp_wq.work);
296 hard_iface = container_of(bat_v, struct batadv_hard_iface, bat_v);
297 bat_priv = netdev_priv(hard_iface->mesh_iface);
298
299 if (atomic_read(&bat_priv->mesh_state) == BATADV_MESH_DEACTIVATING)
300 goto out;
301
302 /* we are in the process of shutting this interface down */
303 if (hard_iface->if_status == BATADV_IF_NOT_IN_USE ||
304 hard_iface->if_status == BATADV_IF_TO_BE_REMOVED)
305 goto out;
306
307 /* the interface was enabled but may not be ready yet */
308 if (hard_iface->if_status != BATADV_IF_ACTIVE)
309 goto restart_timer;
310
311 skb = skb_copy(hard_iface->bat_v.elp_skb, GFP_ATOMIC);
312 if (!skb)
313 goto restart_timer;
314
315 elp_packet = (struct batadv_elp_packet *)skb->data;
316 elp_packet->seqno = htonl(atomic_read(&hard_iface->bat_v.elp_seqno));
317 elp_interval = atomic_read(&hard_iface->bat_v.elp_interval);
318 elp_packet->elp_interval = htonl(elp_interval);
319
320 batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
321 "Sending broadcast ELP packet on interface %s, seqno %u\n",
322 hard_iface->net_dev->name,
323 atomic_read(&hard_iface->bat_v.elp_seqno));
324
325 batadv_send_broadcast_skb(skb, hard_iface);
326
327 atomic_inc(&hard_iface->bat_v.elp_seqno);
328
329 INIT_LIST_HEAD(&metric_queue);
330
331 /* The throughput metric is updated on each sent packet. This way, if a
332 * node is dead and no longer sends packets, batman-adv is still able to
333 * react timely to its death.
334 *
335 * The throughput metric is updated by following these steps:
336 * 1) if the hard_iface is wifi => send a number of unicast ELPs for
337 * probing/sampling to each neighbor
338 * 2) update the throughput metric value of each neighbor (note that the
339 * value retrieved in this step might be 100ms old because the
340 * probing packets at point 1) could still be in the HW queue)
341 */
342 rcu_read_lock();
343 hlist_for_each_entry_rcu(hardif_neigh, &hard_iface->neigh_list, list) {
344 if (!batadv_v_elp_wifi_neigh_probe(hardif_neigh))
345 /* if something goes wrong while probing, better to stop
346 * sending packets immediately and reschedule the task
347 */
348 break;
349
350 if (!kref_get_unless_zero(&hardif_neigh->refcount))
351 continue;
352
353 /* Reading the estimated throughput from cfg80211 is a task that
354 * may sleep and that is not allowed in an rcu protected
355 * context. Therefore add it to metric_queue and process it
356 * outside rcu protected context.
357 */
358 metric_entry = kzalloc(sizeof(*metric_entry), GFP_ATOMIC);
359 if (!metric_entry) {
360 batadv_hardif_neigh_put(hardif_neigh);
361 continue;
362 }
363
364 metric_entry->hardif_neigh = hardif_neigh;
365 list_add(&metric_entry->list, &metric_queue);
366 }
367 rcu_read_unlock();
368
369 list_for_each_entry_safe(metric_entry, metric_safe, &metric_queue, list) {
370 batadv_v_elp_throughput_metric_update(metric_entry->hardif_neigh);
371
372 batadv_hardif_neigh_put(metric_entry->hardif_neigh);
373 list_del(&metric_entry->list);
374 kfree(metric_entry);
375 }
376
377 restart_timer:
378 batadv_v_elp_start_timer(hard_iface);
379 out:
380 return;
381 }
382
383 /**
384 * batadv_v_elp_iface_enable() - setup the ELP interface private resources
385 * @hard_iface: interface for which the data has to be prepared
386 *
387 * Return: 0 on success or a -ENOMEM in case of failure.
388 */
batadv_v_elp_iface_enable(struct batadv_hard_iface * hard_iface)389 int batadv_v_elp_iface_enable(struct batadv_hard_iface *hard_iface)
390 {
391 static const size_t tvlv_padding = sizeof(__be32);
392 struct batadv_elp_packet *elp_packet;
393 unsigned char *elp_buff;
394 u32 random_seqno;
395 size_t size;
396 int res = -ENOMEM;
397
398 size = ETH_HLEN + NET_IP_ALIGN + BATADV_ELP_HLEN + tvlv_padding;
399 hard_iface->bat_v.elp_skb = dev_alloc_skb(size);
400 if (!hard_iface->bat_v.elp_skb)
401 goto out;
402
403 skb_reserve(hard_iface->bat_v.elp_skb, ETH_HLEN + NET_IP_ALIGN);
404 elp_buff = skb_put_zero(hard_iface->bat_v.elp_skb,
405 BATADV_ELP_HLEN + tvlv_padding);
406 elp_packet = (struct batadv_elp_packet *)elp_buff;
407
408 elp_packet->packet_type = BATADV_ELP;
409 elp_packet->version = BATADV_COMPAT_VERSION;
410
411 /* randomize initial seqno to avoid collision */
412 get_random_bytes(&random_seqno, sizeof(random_seqno));
413 atomic_set(&hard_iface->bat_v.elp_seqno, random_seqno);
414
415 /* assume full-duplex by default */
416 hard_iface->bat_v.flags |= BATADV_FULL_DUPLEX;
417
418 /* warn the user (again) if there is no throughput data is available */
419 hard_iface->bat_v.flags &= ~BATADV_WARNING_DEFAULT;
420
421 if (batadv_is_wifi_hardif(hard_iface))
422 hard_iface->bat_v.flags &= ~BATADV_FULL_DUPLEX;
423
424 INIT_DELAYED_WORK(&hard_iface->bat_v.elp_wq,
425 batadv_v_elp_periodic_work);
426 batadv_v_elp_start_timer(hard_iface);
427 res = 0;
428
429 out:
430 return res;
431 }
432
433 /**
434 * batadv_v_elp_iface_disable() - release ELP interface private resources
435 * @hard_iface: interface for which the resources have to be released
436 */
batadv_v_elp_iface_disable(struct batadv_hard_iface * hard_iface)437 void batadv_v_elp_iface_disable(struct batadv_hard_iface *hard_iface)
438 {
439 cancel_delayed_work_sync(&hard_iface->bat_v.elp_wq);
440
441 dev_kfree_skb(hard_iface->bat_v.elp_skb);
442 hard_iface->bat_v.elp_skb = NULL;
443 }
444
445 /**
446 * batadv_v_elp_iface_activate() - update the ELP buffer belonging to the given
447 * hard-interface
448 * @primary_iface: the new primary interface
449 * @hard_iface: interface holding the to-be-updated buffer
450 */
batadv_v_elp_iface_activate(struct batadv_hard_iface * primary_iface,struct batadv_hard_iface * hard_iface)451 void batadv_v_elp_iface_activate(struct batadv_hard_iface *primary_iface,
452 struct batadv_hard_iface *hard_iface)
453 {
454 struct batadv_elp_packet *elp_packet;
455 struct sk_buff *skb;
456
457 if (!hard_iface->bat_v.elp_skb)
458 return;
459
460 skb = hard_iface->bat_v.elp_skb;
461 elp_packet = (struct batadv_elp_packet *)skb->data;
462 ether_addr_copy(elp_packet->orig,
463 primary_iface->net_dev->dev_addr);
464 }
465
466 /**
467 * batadv_v_elp_primary_iface_set() - change internal data to reflect the new
468 * primary interface
469 * @primary_iface: the new primary interface
470 */
batadv_v_elp_primary_iface_set(struct batadv_hard_iface * primary_iface)471 void batadv_v_elp_primary_iface_set(struct batadv_hard_iface *primary_iface)
472 {
473 struct batadv_hard_iface *hard_iface;
474 struct list_head *iter;
475
476 /* update orig field of every elp iface belonging to this mesh */
477 rcu_read_lock();
478 netdev_for_each_lower_private_rcu(primary_iface->mesh_iface, hard_iface, iter)
479 batadv_v_elp_iface_activate(primary_iface, hard_iface);
480 rcu_read_unlock();
481 }
482
483 /**
484 * batadv_v_elp_neigh_update() - update an ELP neighbour node
485 * @bat_priv: the bat priv with all the mesh interface information
486 * @neigh_addr: the neighbour interface address
487 * @if_incoming: the interface the packet was received through
488 * @elp_packet: the received ELP packet
489 *
490 * Updates the ELP neighbour node state with the data received within the new
491 * ELP packet.
492 */
batadv_v_elp_neigh_update(struct batadv_priv * bat_priv,u8 * neigh_addr,struct batadv_hard_iface * if_incoming,struct batadv_elp_packet * elp_packet)493 static void batadv_v_elp_neigh_update(struct batadv_priv *bat_priv,
494 u8 *neigh_addr,
495 struct batadv_hard_iface *if_incoming,
496 struct batadv_elp_packet *elp_packet)
497
498 {
499 struct batadv_neigh_node *neigh;
500 struct batadv_orig_node *orig_neigh;
501 struct batadv_hardif_neigh_node *hardif_neigh;
502 s32 seqno_diff;
503 s32 elp_latest_seqno;
504
505 orig_neigh = batadv_v_ogm_orig_get(bat_priv, elp_packet->orig);
506 if (!orig_neigh)
507 return;
508
509 neigh = batadv_neigh_node_get_or_create(orig_neigh,
510 if_incoming, neigh_addr);
511 if (!neigh)
512 goto orig_free;
513
514 hardif_neigh = batadv_hardif_neigh_get(if_incoming, neigh_addr);
515 if (!hardif_neigh)
516 goto neigh_free;
517
518 elp_latest_seqno = hardif_neigh->bat_v.elp_latest_seqno;
519 seqno_diff = ntohl(elp_packet->seqno) - elp_latest_seqno;
520
521 /* known or older sequence numbers are ignored. However always adopt
522 * if the router seems to have been restarted.
523 */
524 if (seqno_diff < 1 && seqno_diff > -BATADV_ELP_MAX_AGE)
525 goto hardif_free;
526
527 neigh->last_seen = jiffies;
528 hardif_neigh->last_seen = jiffies;
529 hardif_neigh->bat_v.elp_latest_seqno = ntohl(elp_packet->seqno);
530 hardif_neigh->bat_v.elp_interval = ntohl(elp_packet->elp_interval);
531
532 hardif_free:
533 batadv_hardif_neigh_put(hardif_neigh);
534 neigh_free:
535 batadv_neigh_node_put(neigh);
536 orig_free:
537 batadv_orig_node_put(orig_neigh);
538 }
539
540 /**
541 * batadv_v_elp_packet_recv() - main ELP packet handler
542 * @skb: the received packet
543 * @if_incoming: the interface this packet was received through
544 *
545 * Return: NET_RX_SUCCESS and consumes the skb if the packet was properly
546 * processed or NET_RX_DROP in case of failure.
547 */
batadv_v_elp_packet_recv(struct sk_buff * skb,struct batadv_hard_iface * if_incoming)548 int batadv_v_elp_packet_recv(struct sk_buff *skb,
549 struct batadv_hard_iface *if_incoming)
550 {
551 struct batadv_priv *bat_priv = netdev_priv(if_incoming->mesh_iface);
552 struct batadv_elp_packet *elp_packet;
553 struct batadv_hard_iface *primary_if;
554 struct ethhdr *ethhdr;
555 bool res;
556 int ret = NET_RX_DROP;
557
558 res = batadv_check_management_packet(skb, if_incoming, BATADV_ELP_HLEN);
559 if (!res)
560 goto free_skb;
561
562 ethhdr = eth_hdr(skb);
563 if (batadv_is_my_mac(bat_priv, ethhdr->h_source))
564 goto free_skb;
565
566 /* did we receive a B.A.T.M.A.N. V ELP packet on an interface
567 * that does not have B.A.T.M.A.N. V ELP enabled ?
568 */
569 if (strcmp(bat_priv->algo_ops->name, "BATMAN_V") != 0)
570 goto free_skb;
571
572 elp_packet = (struct batadv_elp_packet *)skb->data;
573
574 batadv_dbg(BATADV_DBG_BATMAN, bat_priv,
575 "Received ELP packet from %pM seqno %u ORIG: %pM\n",
576 ethhdr->h_source, ntohl(elp_packet->seqno),
577 elp_packet->orig);
578
579 primary_if = batadv_primary_if_get_selected(bat_priv);
580 if (!primary_if)
581 goto free_skb;
582
583 batadv_v_elp_neigh_update(bat_priv, ethhdr->h_source, if_incoming,
584 elp_packet);
585
586 ret = NET_RX_SUCCESS;
587 batadv_hardif_put(primary_if);
588
589 free_skb:
590 if (ret == NET_RX_SUCCESS)
591 consume_skb(skb);
592 else
593 kfree_skb(skb);
594
595 return ret;
596 }
597