1 // SPDX-License-Identifier: GPL-2.0 2 /* Copyright (C) 2012-2019 B.A.T.M.A.N. contributors: 3 * 4 * Edo Monticelli, Antonio Quartulli 5 * 6 * This program is free software; you can redistribute it and/or 7 * modify it under the terms of version 2 of the GNU General Public 8 * License as published by the Free Software Foundation. 9 * 10 * This program is distributed in the hope that it will be useful, but 11 * WITHOUT ANY WARRANTY; without even the implied warranty of 12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 13 * General Public License for more details. 14 * 15 * You should have received a copy of the GNU General Public License 16 * along with this program; if not, see <http://www.gnu.org/licenses/>. 17 */ 18 19 #include "tp_meter.h" 20 #include "main.h" 21 22 #include <linux/atomic.h> 23 #include <linux/build_bug.h> 24 #include <linux/byteorder/generic.h> 25 #include <linux/cache.h> 26 #include <linux/compiler.h> 27 #include <linux/err.h> 28 #include <linux/etherdevice.h> 29 #include <linux/gfp.h> 30 #include <linux/if_ether.h> 31 #include <linux/init.h> 32 #include <linux/jiffies.h> 33 #include <linux/kernel.h> 34 #include <linux/kref.h> 35 #include <linux/kthread.h> 36 #include <linux/list.h> 37 #include <linux/netdevice.h> 38 #include <linux/param.h> 39 #include <linux/printk.h> 40 #include <linux/random.h> 41 #include <linux/rculist.h> 42 #include <linux/rcupdate.h> 43 #include <linux/sched.h> 44 #include <linux/skbuff.h> 45 #include <linux/slab.h> 46 #include <linux/spinlock.h> 47 #include <linux/stddef.h> 48 #include <linux/string.h> 49 #include <linux/timer.h> 50 #include <linux/wait.h> 51 #include <linux/workqueue.h> 52 #include <uapi/linux/batadv_packet.h> 53 #include <uapi/linux/batman_adv.h> 54 55 #include "hard-interface.h" 56 #include "log.h" 57 #include "netlink.h" 58 #include "originator.h" 59 #include "send.h" 60 61 /** 62 * BATADV_TP_DEF_TEST_LENGTH - Default test length if not specified by the user 63 * in milliseconds 64 */ 65 #define BATADV_TP_DEF_TEST_LENGTH 10000 66 67 /** 68 * BATADV_TP_AWND - Advertised window by the receiver (in bytes) 69 */ 70 #define BATADV_TP_AWND 0x20000000 71 72 /** 73 * BATADV_TP_RECV_TIMEOUT - Receiver activity timeout. If the receiver does not 74 * get anything for such amount of milliseconds, the connection is killed 75 */ 76 #define BATADV_TP_RECV_TIMEOUT 1000 77 78 /** 79 * BATADV_TP_MAX_RTO - Maximum sender timeout. If the sender RTO gets beyond 80 * such amound of milliseconds, the receiver is considered unreachable and the 81 * connection is killed 82 */ 83 #define BATADV_TP_MAX_RTO 30000 84 85 /** 86 * BATADV_TP_FIRST_SEQ - First seqno of each session. The number is rather high 87 * in order to immediately trigger a wrap around (test purposes) 88 */ 89 #define BATADV_TP_FIRST_SEQ ((u32)-1 - 2000) 90 91 /** 92 * BATADV_TP_PLEN - length of the payload (data after the batadv_unicast header) 93 * to simulate 94 */ 95 #define BATADV_TP_PLEN (BATADV_TP_PACKET_LEN - ETH_HLEN - \ 96 sizeof(struct batadv_unicast_packet)) 97 98 static u8 batadv_tp_prerandom[4096] __read_mostly; 99 100 /** 101 * batadv_tp_session_cookie() - generate session cookie based on session ids 102 * @session: TP session identifier 103 * @icmp_uid: icmp pseudo uid of the tp session 104 * 105 * Return: 32 bit tp_meter session cookie 106 */ 107 static u32 batadv_tp_session_cookie(const u8 session[2], u8 icmp_uid) 108 { 109 u32 cookie; 110 111 cookie = icmp_uid << 16; 112 cookie |= session[0] << 8; 113 cookie |= session[1]; 114 115 return cookie; 116 } 117 118 /** 119 * batadv_tp_cwnd() - compute the new cwnd size 120 * @base: base cwnd size value 121 * @increment: the value to add to base to get the new size 122 * @min: minumim cwnd value (usually MSS) 123 * 124 * Return the new cwnd size and ensures it does not exceed the Advertised 125 * Receiver Window size. It is wrap around safe. 126 * For details refer to Section 3.1 of RFC5681 127 * 128 * Return: new congestion window size in bytes 129 */ 130 static u32 batadv_tp_cwnd(u32 base, u32 increment, u32 min) 131 { 132 u32 new_size = base + increment; 133 134 /* check for wrap-around */ 135 if (new_size < base) 136 new_size = (u32)ULONG_MAX; 137 138 new_size = min_t(u32, new_size, BATADV_TP_AWND); 139 140 return max_t(u32, new_size, min); 141 } 142 143 /** 144 * batadv_tp_updated_cwnd() - update the Congestion Windows 145 * @tp_vars: the private data of the current TP meter session 146 * @mss: maximum segment size of transmission 147 * 148 * 1) if the session is in Slow Start, the CWND has to be increased by 1 149 * MSS every unique received ACK 150 * 2) if the session is in Congestion Avoidance, the CWND has to be 151 * increased by MSS * MSS / CWND for every unique received ACK 152 */ 153 static void batadv_tp_update_cwnd(struct batadv_tp_vars *tp_vars, u32 mss) 154 { 155 spin_lock_bh(&tp_vars->cwnd_lock); 156 157 /* slow start... */ 158 if (tp_vars->cwnd <= tp_vars->ss_threshold) { 159 tp_vars->dec_cwnd = 0; 160 tp_vars->cwnd = batadv_tp_cwnd(tp_vars->cwnd, mss, mss); 161 spin_unlock_bh(&tp_vars->cwnd_lock); 162 return; 163 } 164 165 /* increment CWND at least of 1 (section 3.1 of RFC5681) */ 166 tp_vars->dec_cwnd += max_t(u32, 1U << 3, 167 ((mss * mss) << 6) / (tp_vars->cwnd << 3)); 168 if (tp_vars->dec_cwnd < (mss << 3)) { 169 spin_unlock_bh(&tp_vars->cwnd_lock); 170 return; 171 } 172 173 tp_vars->cwnd = batadv_tp_cwnd(tp_vars->cwnd, mss, mss); 174 tp_vars->dec_cwnd = 0; 175 176 spin_unlock_bh(&tp_vars->cwnd_lock); 177 } 178 179 /** 180 * batadv_tp_update_rto() - calculate new retransmission timeout 181 * @tp_vars: the private data of the current TP meter session 182 * @new_rtt: new roundtrip time in msec 183 */ 184 static void batadv_tp_update_rto(struct batadv_tp_vars *tp_vars, 185 u32 new_rtt) 186 { 187 long m = new_rtt; 188 189 /* RTT update 190 * Details in Section 2.2 and 2.3 of RFC6298 191 * 192 * It's tricky to understand. Don't lose hair please. 193 * Inspired by tcp_rtt_estimator() tcp_input.c 194 */ 195 if (tp_vars->srtt != 0) { 196 m -= (tp_vars->srtt >> 3); /* m is now error in rtt est */ 197 tp_vars->srtt += m; /* rtt = 7/8 srtt + 1/8 new */ 198 if (m < 0) 199 m = -m; 200 201 m -= (tp_vars->rttvar >> 2); 202 tp_vars->rttvar += m; /* mdev ~= 3/4 rttvar + 1/4 new */ 203 } else { 204 /* first measure getting in */ 205 tp_vars->srtt = m << 3; /* take the measured time to be srtt */ 206 tp_vars->rttvar = m << 1; /* new_rtt / 2 */ 207 } 208 209 /* rto = srtt + 4 * rttvar. 210 * rttvar is scaled by 4, therefore doesn't need to be multiplied 211 */ 212 tp_vars->rto = (tp_vars->srtt >> 3) + tp_vars->rttvar; 213 } 214 215 /** 216 * batadv_tp_batctl_notify() - send client status result to client 217 * @reason: reason for tp meter session stop 218 * @dst: destination of tp_meter session 219 * @bat_priv: the bat priv with all the soft interface information 220 * @start_time: start of transmission in jiffies 221 * @total_sent: bytes acked to the receiver 222 * @cookie: cookie of tp_meter session 223 */ 224 static void batadv_tp_batctl_notify(enum batadv_tp_meter_reason reason, 225 const u8 *dst, struct batadv_priv *bat_priv, 226 unsigned long start_time, u64 total_sent, 227 u32 cookie) 228 { 229 u32 test_time; 230 u8 result; 231 u32 total_bytes; 232 233 if (!batadv_tp_is_error(reason)) { 234 result = BATADV_TP_REASON_COMPLETE; 235 test_time = jiffies_to_msecs(jiffies - start_time); 236 total_bytes = total_sent; 237 } else { 238 result = reason; 239 test_time = 0; 240 total_bytes = 0; 241 } 242 243 batadv_netlink_tpmeter_notify(bat_priv, dst, result, test_time, 244 total_bytes, cookie); 245 } 246 247 /** 248 * batadv_tp_batctl_error_notify() - send client error result to client 249 * @reason: reason for tp meter session stop 250 * @dst: destination of tp_meter session 251 * @bat_priv: the bat priv with all the soft interface information 252 * @cookie: cookie of tp_meter session 253 */ 254 static void batadv_tp_batctl_error_notify(enum batadv_tp_meter_reason reason, 255 const u8 *dst, 256 struct batadv_priv *bat_priv, 257 u32 cookie) 258 { 259 batadv_tp_batctl_notify(reason, dst, bat_priv, 0, 0, cookie); 260 } 261 262 /** 263 * batadv_tp_list_find() - find a tp_vars object in the global list 264 * @bat_priv: the bat priv with all the soft interface information 265 * @dst: the other endpoint MAC address to look for 266 * 267 * Look for a tp_vars object matching dst as end_point and return it after 268 * having incremented the refcounter. Return NULL is not found 269 * 270 * Return: matching tp_vars or NULL when no tp_vars with @dst was found 271 */ 272 static struct batadv_tp_vars *batadv_tp_list_find(struct batadv_priv *bat_priv, 273 const u8 *dst) 274 { 275 struct batadv_tp_vars *pos, *tp_vars = NULL; 276 277 rcu_read_lock(); 278 hlist_for_each_entry_rcu(pos, &bat_priv->tp_list, list) { 279 if (!batadv_compare_eth(pos->other_end, dst)) 280 continue; 281 282 /* most of the time this function is invoked during the normal 283 * process..it makes sens to pay more when the session is 284 * finished and to speed the process up during the measurement 285 */ 286 if (unlikely(!kref_get_unless_zero(&pos->refcount))) 287 continue; 288 289 tp_vars = pos; 290 break; 291 } 292 rcu_read_unlock(); 293 294 return tp_vars; 295 } 296 297 /** 298 * batadv_tp_list_find_session() - find tp_vars session object in the global 299 * list 300 * @bat_priv: the bat priv with all the soft interface information 301 * @dst: the other endpoint MAC address to look for 302 * @session: session identifier 303 * 304 * Look for a tp_vars object matching dst as end_point, session as tp meter 305 * session and return it after having incremented the refcounter. Return NULL 306 * is not found 307 * 308 * Return: matching tp_vars or NULL when no tp_vars was found 309 */ 310 static struct batadv_tp_vars * 311 batadv_tp_list_find_session(struct batadv_priv *bat_priv, const u8 *dst, 312 const u8 *session) 313 { 314 struct batadv_tp_vars *pos, *tp_vars = NULL; 315 316 rcu_read_lock(); 317 hlist_for_each_entry_rcu(pos, &bat_priv->tp_list, list) { 318 if (!batadv_compare_eth(pos->other_end, dst)) 319 continue; 320 321 if (memcmp(pos->session, session, sizeof(pos->session)) != 0) 322 continue; 323 324 /* most of the time this function is invoked during the normal 325 * process..it makes sense to pay more when the session is 326 * finished and to speed the process up during the measurement 327 */ 328 if (unlikely(!kref_get_unless_zero(&pos->refcount))) 329 continue; 330 331 tp_vars = pos; 332 break; 333 } 334 rcu_read_unlock(); 335 336 return tp_vars; 337 } 338 339 /** 340 * batadv_tp_vars_release() - release batadv_tp_vars from lists and queue for 341 * free after rcu grace period 342 * @ref: kref pointer of the batadv_tp_vars 343 */ 344 static void batadv_tp_vars_release(struct kref *ref) 345 { 346 struct batadv_tp_vars *tp_vars; 347 struct batadv_tp_unacked *un, *safe; 348 349 tp_vars = container_of(ref, struct batadv_tp_vars, refcount); 350 351 /* lock should not be needed because this object is now out of any 352 * context! 353 */ 354 spin_lock_bh(&tp_vars->unacked_lock); 355 list_for_each_entry_safe(un, safe, &tp_vars->unacked_list, list) { 356 list_del(&un->list); 357 kfree(un); 358 } 359 spin_unlock_bh(&tp_vars->unacked_lock); 360 361 kfree_rcu(tp_vars, rcu); 362 } 363 364 /** 365 * batadv_tp_vars_put() - decrement the batadv_tp_vars refcounter and possibly 366 * release it 367 * @tp_vars: the private data of the current TP meter session to be free'd 368 */ 369 static void batadv_tp_vars_put(struct batadv_tp_vars *tp_vars) 370 { 371 kref_put(&tp_vars->refcount, batadv_tp_vars_release); 372 } 373 374 /** 375 * batadv_tp_sender_cleanup() - cleanup sender data and drop and timer 376 * @bat_priv: the bat priv with all the soft interface information 377 * @tp_vars: the private data of the current TP meter session to cleanup 378 */ 379 static void batadv_tp_sender_cleanup(struct batadv_priv *bat_priv, 380 struct batadv_tp_vars *tp_vars) 381 { 382 cancel_delayed_work(&tp_vars->finish_work); 383 384 spin_lock_bh(&tp_vars->bat_priv->tp_list_lock); 385 hlist_del_rcu(&tp_vars->list); 386 spin_unlock_bh(&tp_vars->bat_priv->tp_list_lock); 387 388 /* drop list reference */ 389 batadv_tp_vars_put(tp_vars); 390 391 atomic_dec(&tp_vars->bat_priv->tp_num); 392 393 /* kill the timer and remove its reference */ 394 del_timer_sync(&tp_vars->timer); 395 /* the worker might have rearmed itself therefore we kill it again. Note 396 * that if the worker should run again before invoking the following 397 * del_timer(), it would not re-arm itself once again because the status 398 * is OFF now 399 */ 400 del_timer(&tp_vars->timer); 401 batadv_tp_vars_put(tp_vars); 402 } 403 404 /** 405 * batadv_tp_sender_end() - print info about ended session and inform client 406 * @bat_priv: the bat priv with all the soft interface information 407 * @tp_vars: the private data of the current TP meter session 408 */ 409 static void batadv_tp_sender_end(struct batadv_priv *bat_priv, 410 struct batadv_tp_vars *tp_vars) 411 { 412 u32 session_cookie; 413 414 batadv_dbg(BATADV_DBG_TP_METER, bat_priv, 415 "Test towards %pM finished..shutting down (reason=%d)\n", 416 tp_vars->other_end, tp_vars->reason); 417 418 batadv_dbg(BATADV_DBG_TP_METER, bat_priv, 419 "Last timing stats: SRTT=%ums RTTVAR=%ums RTO=%ums\n", 420 tp_vars->srtt >> 3, tp_vars->rttvar >> 2, tp_vars->rto); 421 422 batadv_dbg(BATADV_DBG_TP_METER, bat_priv, 423 "Final values: cwnd=%u ss_threshold=%u\n", 424 tp_vars->cwnd, tp_vars->ss_threshold); 425 426 session_cookie = batadv_tp_session_cookie(tp_vars->session, 427 tp_vars->icmp_uid); 428 429 batadv_tp_batctl_notify(tp_vars->reason, 430 tp_vars->other_end, 431 bat_priv, 432 tp_vars->start_time, 433 atomic64_read(&tp_vars->tot_sent), 434 session_cookie); 435 } 436 437 /** 438 * batadv_tp_sender_shutdown() - let sender thread/timer stop gracefully 439 * @tp_vars: the private data of the current TP meter session 440 * @reason: reason for tp meter session stop 441 */ 442 static void batadv_tp_sender_shutdown(struct batadv_tp_vars *tp_vars, 443 enum batadv_tp_meter_reason reason) 444 { 445 if (!atomic_dec_and_test(&tp_vars->sending)) 446 return; 447 448 tp_vars->reason = reason; 449 } 450 451 /** 452 * batadv_tp_sender_finish() - stop sender session after test_length was reached 453 * @work: delayed work reference of the related tp_vars 454 */ 455 static void batadv_tp_sender_finish(struct work_struct *work) 456 { 457 struct delayed_work *delayed_work; 458 struct batadv_tp_vars *tp_vars; 459 460 delayed_work = to_delayed_work(work); 461 tp_vars = container_of(delayed_work, struct batadv_tp_vars, 462 finish_work); 463 464 batadv_tp_sender_shutdown(tp_vars, BATADV_TP_REASON_COMPLETE); 465 } 466 467 /** 468 * batadv_tp_reset_sender_timer() - reschedule the sender timer 469 * @tp_vars: the private TP meter data for this session 470 * 471 * Reschedule the timer using tp_vars->rto as delay 472 */ 473 static void batadv_tp_reset_sender_timer(struct batadv_tp_vars *tp_vars) 474 { 475 /* most of the time this function is invoked while normal packet 476 * reception... 477 */ 478 if (unlikely(atomic_read(&tp_vars->sending) == 0)) 479 /* timer ref will be dropped in batadv_tp_sender_cleanup */ 480 return; 481 482 mod_timer(&tp_vars->timer, jiffies + msecs_to_jiffies(tp_vars->rto)); 483 } 484 485 /** 486 * batadv_tp_sender_timeout() - timer that fires in case of packet loss 487 * @t: address to timer_list inside tp_vars 488 * 489 * If fired it means that there was packet loss. 490 * Switch to Slow Start, set the ss_threshold to half of the current cwnd and 491 * reset the cwnd to 3*MSS 492 */ 493 static void batadv_tp_sender_timeout(struct timer_list *t) 494 { 495 struct batadv_tp_vars *tp_vars = from_timer(tp_vars, t, timer); 496 struct batadv_priv *bat_priv = tp_vars->bat_priv; 497 498 if (atomic_read(&tp_vars->sending) == 0) 499 return; 500 501 /* if the user waited long enough...shutdown the test */ 502 if (unlikely(tp_vars->rto >= BATADV_TP_MAX_RTO)) { 503 batadv_tp_sender_shutdown(tp_vars, 504 BATADV_TP_REASON_DST_UNREACHABLE); 505 return; 506 } 507 508 /* RTO exponential backoff 509 * Details in Section 5.5 of RFC6298 510 */ 511 tp_vars->rto <<= 1; 512 513 spin_lock_bh(&tp_vars->cwnd_lock); 514 515 tp_vars->ss_threshold = tp_vars->cwnd >> 1; 516 if (tp_vars->ss_threshold < BATADV_TP_PLEN * 2) 517 tp_vars->ss_threshold = BATADV_TP_PLEN * 2; 518 519 batadv_dbg(BATADV_DBG_TP_METER, bat_priv, 520 "Meter: RTO fired during test towards %pM! cwnd=%u new ss_thr=%u, resetting last_sent to %u\n", 521 tp_vars->other_end, tp_vars->cwnd, tp_vars->ss_threshold, 522 atomic_read(&tp_vars->last_acked)); 523 524 tp_vars->cwnd = BATADV_TP_PLEN * 3; 525 526 spin_unlock_bh(&tp_vars->cwnd_lock); 527 528 /* resend the non-ACKed packets.. */ 529 tp_vars->last_sent = atomic_read(&tp_vars->last_acked); 530 wake_up(&tp_vars->more_bytes); 531 532 batadv_tp_reset_sender_timer(tp_vars); 533 } 534 535 /** 536 * batadv_tp_fill_prerandom() - Fill buffer with prefetched random bytes 537 * @tp_vars: the private TP meter data for this session 538 * @buf: Buffer to fill with bytes 539 * @nbytes: amount of pseudorandom bytes 540 */ 541 static void batadv_tp_fill_prerandom(struct batadv_tp_vars *tp_vars, 542 u8 *buf, size_t nbytes) 543 { 544 u32 local_offset; 545 size_t bytes_inbuf; 546 size_t to_copy; 547 size_t pos = 0; 548 549 spin_lock_bh(&tp_vars->prerandom_lock); 550 local_offset = tp_vars->prerandom_offset; 551 tp_vars->prerandom_offset += nbytes; 552 tp_vars->prerandom_offset %= sizeof(batadv_tp_prerandom); 553 spin_unlock_bh(&tp_vars->prerandom_lock); 554 555 while (nbytes) { 556 local_offset %= sizeof(batadv_tp_prerandom); 557 bytes_inbuf = sizeof(batadv_tp_prerandom) - local_offset; 558 to_copy = min(nbytes, bytes_inbuf); 559 560 memcpy(&buf[pos], &batadv_tp_prerandom[local_offset], to_copy); 561 pos += to_copy; 562 nbytes -= to_copy; 563 local_offset = 0; 564 } 565 } 566 567 /** 568 * batadv_tp_send_msg() - send a single message 569 * @tp_vars: the private TP meter data for this session 570 * @src: source mac address 571 * @orig_node: the originator of the destination 572 * @seqno: sequence number of this packet 573 * @len: length of the entire packet 574 * @session: session identifier 575 * @uid: local ICMP "socket" index 576 * @timestamp: timestamp in jiffies which is replied in ack 577 * 578 * Create and send a single TP Meter message. 579 * 580 * Return: 0 on success, BATADV_TP_REASON_DST_UNREACHABLE if the destination is 581 * not reachable, BATADV_TP_REASON_MEMORY_ERROR if the packet couldn't be 582 * allocated 583 */ 584 static int batadv_tp_send_msg(struct batadv_tp_vars *tp_vars, const u8 *src, 585 struct batadv_orig_node *orig_node, 586 u32 seqno, size_t len, const u8 *session, 587 int uid, u32 timestamp) 588 { 589 struct batadv_icmp_tp_packet *icmp; 590 struct sk_buff *skb; 591 int r; 592 u8 *data; 593 size_t data_len; 594 595 skb = netdev_alloc_skb_ip_align(NULL, len + ETH_HLEN); 596 if (unlikely(!skb)) 597 return BATADV_TP_REASON_MEMORY_ERROR; 598 599 skb_reserve(skb, ETH_HLEN); 600 icmp = skb_put(skb, sizeof(*icmp)); 601 602 /* fill the icmp header */ 603 ether_addr_copy(icmp->dst, orig_node->orig); 604 ether_addr_copy(icmp->orig, src); 605 icmp->version = BATADV_COMPAT_VERSION; 606 icmp->packet_type = BATADV_ICMP; 607 icmp->ttl = BATADV_TTL; 608 icmp->msg_type = BATADV_TP; 609 icmp->uid = uid; 610 611 icmp->subtype = BATADV_TP_MSG; 612 memcpy(icmp->session, session, sizeof(icmp->session)); 613 icmp->seqno = htonl(seqno); 614 icmp->timestamp = htonl(timestamp); 615 616 data_len = len - sizeof(*icmp); 617 data = skb_put(skb, data_len); 618 batadv_tp_fill_prerandom(tp_vars, data, data_len); 619 620 r = batadv_send_skb_to_orig(skb, orig_node, NULL); 621 if (r == NET_XMIT_SUCCESS) 622 return 0; 623 624 return BATADV_TP_REASON_CANT_SEND; 625 } 626 627 /** 628 * batadv_tp_recv_ack() - ACK receiving function 629 * @bat_priv: the bat priv with all the soft interface information 630 * @skb: the buffer containing the received packet 631 * 632 * Process a received TP ACK packet 633 */ 634 static void batadv_tp_recv_ack(struct batadv_priv *bat_priv, 635 const struct sk_buff *skb) 636 { 637 struct batadv_hard_iface *primary_if = NULL; 638 struct batadv_orig_node *orig_node = NULL; 639 const struct batadv_icmp_tp_packet *icmp; 640 struct batadv_tp_vars *tp_vars; 641 size_t packet_len, mss; 642 u32 rtt, recv_ack, cwnd; 643 unsigned char *dev_addr; 644 645 packet_len = BATADV_TP_PLEN; 646 mss = BATADV_TP_PLEN; 647 packet_len += sizeof(struct batadv_unicast_packet); 648 649 icmp = (struct batadv_icmp_tp_packet *)skb->data; 650 651 /* find the tp_vars */ 652 tp_vars = batadv_tp_list_find_session(bat_priv, icmp->orig, 653 icmp->session); 654 if (unlikely(!tp_vars)) 655 return; 656 657 if (unlikely(atomic_read(&tp_vars->sending) == 0)) 658 goto out; 659 660 /* old ACK? silently drop it.. */ 661 if (batadv_seq_before(ntohl(icmp->seqno), 662 (u32)atomic_read(&tp_vars->last_acked))) 663 goto out; 664 665 primary_if = batadv_primary_if_get_selected(bat_priv); 666 if (unlikely(!primary_if)) 667 goto out; 668 669 orig_node = batadv_orig_hash_find(bat_priv, icmp->orig); 670 if (unlikely(!orig_node)) 671 goto out; 672 673 /* update RTO with the new sampled RTT, if any */ 674 rtt = jiffies_to_msecs(jiffies) - ntohl(icmp->timestamp); 675 if (icmp->timestamp && rtt) 676 batadv_tp_update_rto(tp_vars, rtt); 677 678 /* ACK for new data... reset the timer */ 679 batadv_tp_reset_sender_timer(tp_vars); 680 681 recv_ack = ntohl(icmp->seqno); 682 683 /* check if this ACK is a duplicate */ 684 if (atomic_read(&tp_vars->last_acked) == recv_ack) { 685 atomic_inc(&tp_vars->dup_acks); 686 if (atomic_read(&tp_vars->dup_acks) != 3) 687 goto out; 688 689 if (recv_ack >= tp_vars->recover) 690 goto out; 691 692 /* if this is the third duplicate ACK do Fast Retransmit */ 693 batadv_tp_send_msg(tp_vars, primary_if->net_dev->dev_addr, 694 orig_node, recv_ack, packet_len, 695 icmp->session, icmp->uid, 696 jiffies_to_msecs(jiffies)); 697 698 spin_lock_bh(&tp_vars->cwnd_lock); 699 700 /* Fast Recovery */ 701 tp_vars->fast_recovery = true; 702 /* Set recover to the last outstanding seqno when Fast Recovery 703 * is entered. RFC6582, Section 3.2, step 1 704 */ 705 tp_vars->recover = tp_vars->last_sent; 706 tp_vars->ss_threshold = tp_vars->cwnd >> 1; 707 batadv_dbg(BATADV_DBG_TP_METER, bat_priv, 708 "Meter: Fast Recovery, (cur cwnd=%u) ss_thr=%u last_sent=%u recv_ack=%u\n", 709 tp_vars->cwnd, tp_vars->ss_threshold, 710 tp_vars->last_sent, recv_ack); 711 tp_vars->cwnd = batadv_tp_cwnd(tp_vars->ss_threshold, 3 * mss, 712 mss); 713 tp_vars->dec_cwnd = 0; 714 tp_vars->last_sent = recv_ack; 715 716 spin_unlock_bh(&tp_vars->cwnd_lock); 717 } else { 718 /* count the acked data */ 719 atomic64_add(recv_ack - atomic_read(&tp_vars->last_acked), 720 &tp_vars->tot_sent); 721 /* reset the duplicate ACKs counter */ 722 atomic_set(&tp_vars->dup_acks, 0); 723 724 if (tp_vars->fast_recovery) { 725 /* partial ACK */ 726 if (batadv_seq_before(recv_ack, tp_vars->recover)) { 727 /* this is another hole in the window. React 728 * immediately as specified by NewReno (see 729 * Section 3.2 of RFC6582 for details) 730 */ 731 dev_addr = primary_if->net_dev->dev_addr; 732 batadv_tp_send_msg(tp_vars, dev_addr, 733 orig_node, recv_ack, 734 packet_len, icmp->session, 735 icmp->uid, 736 jiffies_to_msecs(jiffies)); 737 tp_vars->cwnd = batadv_tp_cwnd(tp_vars->cwnd, 738 mss, mss); 739 } else { 740 tp_vars->fast_recovery = false; 741 /* set cwnd to the value of ss_threshold at the 742 * moment that Fast Recovery was entered. 743 * RFC6582, Section 3.2, step 3 744 */ 745 cwnd = batadv_tp_cwnd(tp_vars->ss_threshold, 0, 746 mss); 747 tp_vars->cwnd = cwnd; 748 } 749 goto move_twnd; 750 } 751 752 if (recv_ack - atomic_read(&tp_vars->last_acked) >= mss) 753 batadv_tp_update_cwnd(tp_vars, mss); 754 move_twnd: 755 /* move the Transmit Window */ 756 atomic_set(&tp_vars->last_acked, recv_ack); 757 } 758 759 wake_up(&tp_vars->more_bytes); 760 out: 761 if (likely(primary_if)) 762 batadv_hardif_put(primary_if); 763 if (likely(orig_node)) 764 batadv_orig_node_put(orig_node); 765 if (likely(tp_vars)) 766 batadv_tp_vars_put(tp_vars); 767 } 768 769 /** 770 * batadv_tp_avail() - check if congestion window is not full 771 * @tp_vars: the private data of the current TP meter session 772 * @payload_len: size of the payload of a single message 773 * 774 * Return: true when congestion window is not full, false otherwise 775 */ 776 static bool batadv_tp_avail(struct batadv_tp_vars *tp_vars, 777 size_t payload_len) 778 { 779 u32 win_left, win_limit; 780 781 win_limit = atomic_read(&tp_vars->last_acked) + tp_vars->cwnd; 782 win_left = win_limit - tp_vars->last_sent; 783 784 return win_left >= payload_len; 785 } 786 787 /** 788 * batadv_tp_wait_available() - wait until congestion window becomes free or 789 * timeout is reached 790 * @tp_vars: the private data of the current TP meter session 791 * @plen: size of the payload of a single message 792 * 793 * Return: 0 if the condition evaluated to false after the timeout elapsed, 794 * 1 if the condition evaluated to true after the timeout elapsed, the 795 * remaining jiffies (at least 1) if the condition evaluated to true before 796 * the timeout elapsed, or -ERESTARTSYS if it was interrupted by a signal. 797 */ 798 static int batadv_tp_wait_available(struct batadv_tp_vars *tp_vars, size_t plen) 799 { 800 int ret; 801 802 ret = wait_event_interruptible_timeout(tp_vars->more_bytes, 803 batadv_tp_avail(tp_vars, plen), 804 HZ / 10); 805 806 return ret; 807 } 808 809 /** 810 * batadv_tp_send() - main sending thread of a tp meter session 811 * @arg: address of the related tp_vars 812 * 813 * Return: nothing, this function never returns 814 */ 815 static int batadv_tp_send(void *arg) 816 { 817 struct batadv_tp_vars *tp_vars = arg; 818 struct batadv_priv *bat_priv = tp_vars->bat_priv; 819 struct batadv_hard_iface *primary_if = NULL; 820 struct batadv_orig_node *orig_node = NULL; 821 size_t payload_len, packet_len; 822 int err = 0; 823 824 if (unlikely(tp_vars->role != BATADV_TP_SENDER)) { 825 err = BATADV_TP_REASON_DST_UNREACHABLE; 826 tp_vars->reason = err; 827 goto out; 828 } 829 830 orig_node = batadv_orig_hash_find(bat_priv, tp_vars->other_end); 831 if (unlikely(!orig_node)) { 832 err = BATADV_TP_REASON_DST_UNREACHABLE; 833 tp_vars->reason = err; 834 goto out; 835 } 836 837 primary_if = batadv_primary_if_get_selected(bat_priv); 838 if (unlikely(!primary_if)) { 839 err = BATADV_TP_REASON_DST_UNREACHABLE; 840 tp_vars->reason = err; 841 goto out; 842 } 843 844 /* assume that all the hard_interfaces have a correctly 845 * configured MTU, so use the soft_iface MTU as MSS. 846 * This might not be true and in that case the fragmentation 847 * should be used. 848 * Now, try to send the packet as it is 849 */ 850 payload_len = BATADV_TP_PLEN; 851 BUILD_BUG_ON(sizeof(struct batadv_icmp_tp_packet) > BATADV_TP_PLEN); 852 853 batadv_tp_reset_sender_timer(tp_vars); 854 855 /* queue the worker in charge of terminating the test */ 856 queue_delayed_work(batadv_event_workqueue, &tp_vars->finish_work, 857 msecs_to_jiffies(tp_vars->test_length)); 858 859 while (atomic_read(&tp_vars->sending) != 0) { 860 if (unlikely(!batadv_tp_avail(tp_vars, payload_len))) { 861 batadv_tp_wait_available(tp_vars, payload_len); 862 continue; 863 } 864 865 /* to emulate normal unicast traffic, add to the payload len 866 * the size of the unicast header 867 */ 868 packet_len = payload_len + sizeof(struct batadv_unicast_packet); 869 870 err = batadv_tp_send_msg(tp_vars, primary_if->net_dev->dev_addr, 871 orig_node, tp_vars->last_sent, 872 packet_len, 873 tp_vars->session, tp_vars->icmp_uid, 874 jiffies_to_msecs(jiffies)); 875 876 /* something went wrong during the preparation/transmission */ 877 if (unlikely(err && err != BATADV_TP_REASON_CANT_SEND)) { 878 batadv_dbg(BATADV_DBG_TP_METER, bat_priv, 879 "Meter: %s() cannot send packets (%d)\n", 880 __func__, err); 881 /* ensure nobody else tries to stop the thread now */ 882 if (atomic_dec_and_test(&tp_vars->sending)) 883 tp_vars->reason = err; 884 break; 885 } 886 887 /* right-shift the TWND */ 888 if (!err) 889 tp_vars->last_sent += payload_len; 890 891 cond_resched(); 892 } 893 894 out: 895 if (likely(primary_if)) 896 batadv_hardif_put(primary_if); 897 if (likely(orig_node)) 898 batadv_orig_node_put(orig_node); 899 900 batadv_tp_sender_end(bat_priv, tp_vars); 901 batadv_tp_sender_cleanup(bat_priv, tp_vars); 902 903 batadv_tp_vars_put(tp_vars); 904 905 do_exit(0); 906 } 907 908 /** 909 * batadv_tp_start_kthread() - start new thread which manages the tp meter 910 * sender 911 * @tp_vars: the private data of the current TP meter session 912 */ 913 static void batadv_tp_start_kthread(struct batadv_tp_vars *tp_vars) 914 { 915 struct task_struct *kthread; 916 struct batadv_priv *bat_priv = tp_vars->bat_priv; 917 u32 session_cookie; 918 919 kref_get(&tp_vars->refcount); 920 kthread = kthread_create(batadv_tp_send, tp_vars, "kbatadv_tp_meter"); 921 if (IS_ERR(kthread)) { 922 session_cookie = batadv_tp_session_cookie(tp_vars->session, 923 tp_vars->icmp_uid); 924 pr_err("batadv: cannot create tp meter kthread\n"); 925 batadv_tp_batctl_error_notify(BATADV_TP_REASON_MEMORY_ERROR, 926 tp_vars->other_end, 927 bat_priv, session_cookie); 928 929 /* drop reserved reference for kthread */ 930 batadv_tp_vars_put(tp_vars); 931 932 /* cleanup of failed tp meter variables */ 933 batadv_tp_sender_cleanup(bat_priv, tp_vars); 934 return; 935 } 936 937 wake_up_process(kthread); 938 } 939 940 /** 941 * batadv_tp_start() - start a new tp meter session 942 * @bat_priv: the bat priv with all the soft interface information 943 * @dst: the receiver MAC address 944 * @test_length: test length in milliseconds 945 * @cookie: session cookie 946 */ 947 void batadv_tp_start(struct batadv_priv *bat_priv, const u8 *dst, 948 u32 test_length, u32 *cookie) 949 { 950 struct batadv_tp_vars *tp_vars; 951 u8 session_id[2]; 952 u8 icmp_uid; 953 u32 session_cookie; 954 955 get_random_bytes(session_id, sizeof(session_id)); 956 get_random_bytes(&icmp_uid, 1); 957 session_cookie = batadv_tp_session_cookie(session_id, icmp_uid); 958 *cookie = session_cookie; 959 960 /* look for an already existing test towards this node */ 961 spin_lock_bh(&bat_priv->tp_list_lock); 962 tp_vars = batadv_tp_list_find(bat_priv, dst); 963 if (tp_vars) { 964 spin_unlock_bh(&bat_priv->tp_list_lock); 965 batadv_tp_vars_put(tp_vars); 966 batadv_dbg(BATADV_DBG_TP_METER, bat_priv, 967 "Meter: test to or from the same node already ongoing, aborting\n"); 968 batadv_tp_batctl_error_notify(BATADV_TP_REASON_ALREADY_ONGOING, 969 dst, bat_priv, session_cookie); 970 return; 971 } 972 973 if (!atomic_add_unless(&bat_priv->tp_num, 1, BATADV_TP_MAX_NUM)) { 974 spin_unlock_bh(&bat_priv->tp_list_lock); 975 batadv_dbg(BATADV_DBG_TP_METER, bat_priv, 976 "Meter: too many ongoing sessions, aborting (SEND)\n"); 977 batadv_tp_batctl_error_notify(BATADV_TP_REASON_TOO_MANY, dst, 978 bat_priv, session_cookie); 979 return; 980 } 981 982 tp_vars = kmalloc(sizeof(*tp_vars), GFP_ATOMIC); 983 if (!tp_vars) { 984 spin_unlock_bh(&bat_priv->tp_list_lock); 985 batadv_dbg(BATADV_DBG_TP_METER, bat_priv, 986 "Meter: %s cannot allocate list elements\n", 987 __func__); 988 batadv_tp_batctl_error_notify(BATADV_TP_REASON_MEMORY_ERROR, 989 dst, bat_priv, session_cookie); 990 return; 991 } 992 993 /* initialize tp_vars */ 994 ether_addr_copy(tp_vars->other_end, dst); 995 kref_init(&tp_vars->refcount); 996 tp_vars->role = BATADV_TP_SENDER; 997 atomic_set(&tp_vars->sending, 1); 998 memcpy(tp_vars->session, session_id, sizeof(session_id)); 999 tp_vars->icmp_uid = icmp_uid; 1000 1001 tp_vars->last_sent = BATADV_TP_FIRST_SEQ; 1002 atomic_set(&tp_vars->last_acked, BATADV_TP_FIRST_SEQ); 1003 tp_vars->fast_recovery = false; 1004 tp_vars->recover = BATADV_TP_FIRST_SEQ; 1005 1006 /* initialise the CWND to 3*MSS (Section 3.1 in RFC5681). 1007 * For batman-adv the MSS is the size of the payload received by the 1008 * soft_interface, hence its MTU 1009 */ 1010 tp_vars->cwnd = BATADV_TP_PLEN * 3; 1011 /* at the beginning initialise the SS threshold to the biggest possible 1012 * window size, hence the AWND size 1013 */ 1014 tp_vars->ss_threshold = BATADV_TP_AWND; 1015 1016 /* RTO initial value is 3 seconds. 1017 * Details in Section 2.1 of RFC6298 1018 */ 1019 tp_vars->rto = 1000; 1020 tp_vars->srtt = 0; 1021 tp_vars->rttvar = 0; 1022 1023 atomic64_set(&tp_vars->tot_sent, 0); 1024 1025 kref_get(&tp_vars->refcount); 1026 timer_setup(&tp_vars->timer, batadv_tp_sender_timeout, 0); 1027 1028 tp_vars->bat_priv = bat_priv; 1029 tp_vars->start_time = jiffies; 1030 1031 init_waitqueue_head(&tp_vars->more_bytes); 1032 1033 spin_lock_init(&tp_vars->unacked_lock); 1034 INIT_LIST_HEAD(&tp_vars->unacked_list); 1035 1036 spin_lock_init(&tp_vars->cwnd_lock); 1037 1038 tp_vars->prerandom_offset = 0; 1039 spin_lock_init(&tp_vars->prerandom_lock); 1040 1041 kref_get(&tp_vars->refcount); 1042 hlist_add_head_rcu(&tp_vars->list, &bat_priv->tp_list); 1043 spin_unlock_bh(&bat_priv->tp_list_lock); 1044 1045 tp_vars->test_length = test_length; 1046 if (!tp_vars->test_length) 1047 tp_vars->test_length = BATADV_TP_DEF_TEST_LENGTH; 1048 1049 batadv_dbg(BATADV_DBG_TP_METER, bat_priv, 1050 "Meter: starting throughput meter towards %pM (length=%ums)\n", 1051 dst, test_length); 1052 1053 /* init work item for finished tp tests */ 1054 INIT_DELAYED_WORK(&tp_vars->finish_work, batadv_tp_sender_finish); 1055 1056 /* start tp kthread. This way the write() call issued from userspace can 1057 * happily return and avoid to block 1058 */ 1059 batadv_tp_start_kthread(tp_vars); 1060 1061 /* don't return reference to new tp_vars */ 1062 batadv_tp_vars_put(tp_vars); 1063 } 1064 1065 /** 1066 * batadv_tp_stop() - stop currently running tp meter session 1067 * @bat_priv: the bat priv with all the soft interface information 1068 * @dst: the receiver MAC address 1069 * @return_value: reason for tp meter session stop 1070 */ 1071 void batadv_tp_stop(struct batadv_priv *bat_priv, const u8 *dst, 1072 u8 return_value) 1073 { 1074 struct batadv_orig_node *orig_node; 1075 struct batadv_tp_vars *tp_vars; 1076 1077 batadv_dbg(BATADV_DBG_TP_METER, bat_priv, 1078 "Meter: stopping test towards %pM\n", dst); 1079 1080 orig_node = batadv_orig_hash_find(bat_priv, dst); 1081 if (!orig_node) 1082 return; 1083 1084 tp_vars = batadv_tp_list_find(bat_priv, orig_node->orig); 1085 if (!tp_vars) { 1086 batadv_dbg(BATADV_DBG_TP_METER, bat_priv, 1087 "Meter: trying to interrupt an already over connection\n"); 1088 goto out; 1089 } 1090 1091 batadv_tp_sender_shutdown(tp_vars, return_value); 1092 batadv_tp_vars_put(tp_vars); 1093 out: 1094 batadv_orig_node_put(orig_node); 1095 } 1096 1097 /** 1098 * batadv_tp_reset_receiver_timer() - reset the receiver shutdown timer 1099 * @tp_vars: the private data of the current TP meter session 1100 * 1101 * start the receiver shutdown timer or reset it if already started 1102 */ 1103 static void batadv_tp_reset_receiver_timer(struct batadv_tp_vars *tp_vars) 1104 { 1105 mod_timer(&tp_vars->timer, 1106 jiffies + msecs_to_jiffies(BATADV_TP_RECV_TIMEOUT)); 1107 } 1108 1109 /** 1110 * batadv_tp_receiver_shutdown() - stop a tp meter receiver when timeout is 1111 * reached without received ack 1112 * @t: address to timer_list inside tp_vars 1113 */ 1114 static void batadv_tp_receiver_shutdown(struct timer_list *t) 1115 { 1116 struct batadv_tp_vars *tp_vars = from_timer(tp_vars, t, timer); 1117 struct batadv_tp_unacked *un, *safe; 1118 struct batadv_priv *bat_priv; 1119 1120 bat_priv = tp_vars->bat_priv; 1121 1122 /* if there is recent activity rearm the timer */ 1123 if (!batadv_has_timed_out(tp_vars->last_recv_time, 1124 BATADV_TP_RECV_TIMEOUT)) { 1125 /* reset the receiver shutdown timer */ 1126 batadv_tp_reset_receiver_timer(tp_vars); 1127 return; 1128 } 1129 1130 batadv_dbg(BATADV_DBG_TP_METER, bat_priv, 1131 "Shutting down for inactivity (more than %dms) from %pM\n", 1132 BATADV_TP_RECV_TIMEOUT, tp_vars->other_end); 1133 1134 spin_lock_bh(&tp_vars->bat_priv->tp_list_lock); 1135 hlist_del_rcu(&tp_vars->list); 1136 spin_unlock_bh(&tp_vars->bat_priv->tp_list_lock); 1137 1138 /* drop list reference */ 1139 batadv_tp_vars_put(tp_vars); 1140 1141 atomic_dec(&bat_priv->tp_num); 1142 1143 spin_lock_bh(&tp_vars->unacked_lock); 1144 list_for_each_entry_safe(un, safe, &tp_vars->unacked_list, list) { 1145 list_del(&un->list); 1146 kfree(un); 1147 } 1148 spin_unlock_bh(&tp_vars->unacked_lock); 1149 1150 /* drop reference of timer */ 1151 batadv_tp_vars_put(tp_vars); 1152 } 1153 1154 /** 1155 * batadv_tp_send_ack() - send an ACK packet 1156 * @bat_priv: the bat priv with all the soft interface information 1157 * @dst: the mac address of the destination originator 1158 * @seq: the sequence number to ACK 1159 * @timestamp: the timestamp to echo back in the ACK 1160 * @session: session identifier 1161 * @socket_index: local ICMP socket identifier 1162 * 1163 * Return: 0 on success, a positive integer representing the reason of the 1164 * failure otherwise 1165 */ 1166 static int batadv_tp_send_ack(struct batadv_priv *bat_priv, const u8 *dst, 1167 u32 seq, __be32 timestamp, const u8 *session, 1168 int socket_index) 1169 { 1170 struct batadv_hard_iface *primary_if = NULL; 1171 struct batadv_orig_node *orig_node; 1172 struct batadv_icmp_tp_packet *icmp; 1173 struct sk_buff *skb; 1174 int r, ret; 1175 1176 orig_node = batadv_orig_hash_find(bat_priv, dst); 1177 if (unlikely(!orig_node)) { 1178 ret = BATADV_TP_REASON_DST_UNREACHABLE; 1179 goto out; 1180 } 1181 1182 primary_if = batadv_primary_if_get_selected(bat_priv); 1183 if (unlikely(!primary_if)) { 1184 ret = BATADV_TP_REASON_DST_UNREACHABLE; 1185 goto out; 1186 } 1187 1188 skb = netdev_alloc_skb_ip_align(NULL, sizeof(*icmp) + ETH_HLEN); 1189 if (unlikely(!skb)) { 1190 ret = BATADV_TP_REASON_MEMORY_ERROR; 1191 goto out; 1192 } 1193 1194 skb_reserve(skb, ETH_HLEN); 1195 icmp = skb_put(skb, sizeof(*icmp)); 1196 icmp->packet_type = BATADV_ICMP; 1197 icmp->version = BATADV_COMPAT_VERSION; 1198 icmp->ttl = BATADV_TTL; 1199 icmp->msg_type = BATADV_TP; 1200 ether_addr_copy(icmp->dst, orig_node->orig); 1201 ether_addr_copy(icmp->orig, primary_if->net_dev->dev_addr); 1202 icmp->uid = socket_index; 1203 1204 icmp->subtype = BATADV_TP_ACK; 1205 memcpy(icmp->session, session, sizeof(icmp->session)); 1206 icmp->seqno = htonl(seq); 1207 icmp->timestamp = timestamp; 1208 1209 /* send the ack */ 1210 r = batadv_send_skb_to_orig(skb, orig_node, NULL); 1211 if (unlikely(r < 0) || r == NET_XMIT_DROP) { 1212 ret = BATADV_TP_REASON_DST_UNREACHABLE; 1213 goto out; 1214 } 1215 ret = 0; 1216 1217 out: 1218 if (likely(orig_node)) 1219 batadv_orig_node_put(orig_node); 1220 if (likely(primary_if)) 1221 batadv_hardif_put(primary_if); 1222 1223 return ret; 1224 } 1225 1226 /** 1227 * batadv_tp_handle_out_of_order() - store an out of order packet 1228 * @tp_vars: the private data of the current TP meter session 1229 * @skb: the buffer containing the received packet 1230 * 1231 * Store the out of order packet in the unacked list for late processing. This 1232 * packets are kept in this list so that they can be ACKed at once as soon as 1233 * all the previous packets have been received 1234 * 1235 * Return: true if the packed has been successfully processed, false otherwise 1236 */ 1237 static bool batadv_tp_handle_out_of_order(struct batadv_tp_vars *tp_vars, 1238 const struct sk_buff *skb) 1239 { 1240 const struct batadv_icmp_tp_packet *icmp; 1241 struct batadv_tp_unacked *un, *new; 1242 u32 payload_len; 1243 bool added = false; 1244 1245 new = kmalloc(sizeof(*new), GFP_ATOMIC); 1246 if (unlikely(!new)) 1247 return false; 1248 1249 icmp = (struct batadv_icmp_tp_packet *)skb->data; 1250 1251 new->seqno = ntohl(icmp->seqno); 1252 payload_len = skb->len - sizeof(struct batadv_unicast_packet); 1253 new->len = payload_len; 1254 1255 spin_lock_bh(&tp_vars->unacked_lock); 1256 /* if the list is empty immediately attach this new object */ 1257 if (list_empty(&tp_vars->unacked_list)) { 1258 list_add(&new->list, &tp_vars->unacked_list); 1259 goto out; 1260 } 1261 1262 /* otherwise loop over the list and either drop the packet because this 1263 * is a duplicate or store it at the right position. 1264 * 1265 * The iteration is done in the reverse way because it is likely that 1266 * the last received packet (the one being processed now) has a bigger 1267 * seqno than all the others already stored. 1268 */ 1269 list_for_each_entry_reverse(un, &tp_vars->unacked_list, list) { 1270 /* check for duplicates */ 1271 if (new->seqno == un->seqno) { 1272 if (new->len > un->len) 1273 un->len = new->len; 1274 kfree(new); 1275 added = true; 1276 break; 1277 } 1278 1279 /* look for the right position */ 1280 if (batadv_seq_before(new->seqno, un->seqno)) 1281 continue; 1282 1283 /* as soon as an entry having a bigger seqno is found, the new 1284 * one is attached _after_ it. In this way the list is kept in 1285 * ascending order 1286 */ 1287 list_add_tail(&new->list, &un->list); 1288 added = true; 1289 break; 1290 } 1291 1292 /* received packet with smallest seqno out of order; add it to front */ 1293 if (!added) 1294 list_add(&new->list, &tp_vars->unacked_list); 1295 1296 out: 1297 spin_unlock_bh(&tp_vars->unacked_lock); 1298 1299 return true; 1300 } 1301 1302 /** 1303 * batadv_tp_ack_unordered() - update number received bytes in current stream 1304 * without gaps 1305 * @tp_vars: the private data of the current TP meter session 1306 */ 1307 static void batadv_tp_ack_unordered(struct batadv_tp_vars *tp_vars) 1308 { 1309 struct batadv_tp_unacked *un, *safe; 1310 u32 to_ack; 1311 1312 /* go through the unacked packet list and possibly ACK them as 1313 * well 1314 */ 1315 spin_lock_bh(&tp_vars->unacked_lock); 1316 list_for_each_entry_safe(un, safe, &tp_vars->unacked_list, list) { 1317 /* the list is ordered, therefore it is possible to stop as soon 1318 * there is a gap between the last acked seqno and the seqno of 1319 * the packet under inspection 1320 */ 1321 if (batadv_seq_before(tp_vars->last_recv, un->seqno)) 1322 break; 1323 1324 to_ack = un->seqno + un->len - tp_vars->last_recv; 1325 1326 if (batadv_seq_before(tp_vars->last_recv, un->seqno + un->len)) 1327 tp_vars->last_recv += to_ack; 1328 1329 list_del(&un->list); 1330 kfree(un); 1331 } 1332 spin_unlock_bh(&tp_vars->unacked_lock); 1333 } 1334 1335 /** 1336 * batadv_tp_init_recv() - return matching or create new receiver tp_vars 1337 * @bat_priv: the bat priv with all the soft interface information 1338 * @icmp: received icmp tp msg 1339 * 1340 * Return: corresponding tp_vars or NULL on errors 1341 */ 1342 static struct batadv_tp_vars * 1343 batadv_tp_init_recv(struct batadv_priv *bat_priv, 1344 const struct batadv_icmp_tp_packet *icmp) 1345 { 1346 struct batadv_tp_vars *tp_vars; 1347 1348 spin_lock_bh(&bat_priv->tp_list_lock); 1349 tp_vars = batadv_tp_list_find_session(bat_priv, icmp->orig, 1350 icmp->session); 1351 if (tp_vars) 1352 goto out_unlock; 1353 1354 if (!atomic_add_unless(&bat_priv->tp_num, 1, BATADV_TP_MAX_NUM)) { 1355 batadv_dbg(BATADV_DBG_TP_METER, bat_priv, 1356 "Meter: too many ongoing sessions, aborting (RECV)\n"); 1357 goto out_unlock; 1358 } 1359 1360 tp_vars = kmalloc(sizeof(*tp_vars), GFP_ATOMIC); 1361 if (!tp_vars) 1362 goto out_unlock; 1363 1364 ether_addr_copy(tp_vars->other_end, icmp->orig); 1365 tp_vars->role = BATADV_TP_RECEIVER; 1366 memcpy(tp_vars->session, icmp->session, sizeof(tp_vars->session)); 1367 tp_vars->last_recv = BATADV_TP_FIRST_SEQ; 1368 tp_vars->bat_priv = bat_priv; 1369 kref_init(&tp_vars->refcount); 1370 1371 spin_lock_init(&tp_vars->unacked_lock); 1372 INIT_LIST_HEAD(&tp_vars->unacked_list); 1373 1374 kref_get(&tp_vars->refcount); 1375 hlist_add_head_rcu(&tp_vars->list, &bat_priv->tp_list); 1376 1377 kref_get(&tp_vars->refcount); 1378 timer_setup(&tp_vars->timer, batadv_tp_receiver_shutdown, 0); 1379 1380 batadv_tp_reset_receiver_timer(tp_vars); 1381 1382 out_unlock: 1383 spin_unlock_bh(&bat_priv->tp_list_lock); 1384 1385 return tp_vars; 1386 } 1387 1388 /** 1389 * batadv_tp_recv_msg() - process a single data message 1390 * @bat_priv: the bat priv with all the soft interface information 1391 * @skb: the buffer containing the received packet 1392 * 1393 * Process a received TP MSG packet 1394 */ 1395 static void batadv_tp_recv_msg(struct batadv_priv *bat_priv, 1396 const struct sk_buff *skb) 1397 { 1398 const struct batadv_icmp_tp_packet *icmp; 1399 struct batadv_tp_vars *tp_vars; 1400 size_t packet_size; 1401 u32 seqno; 1402 1403 icmp = (struct batadv_icmp_tp_packet *)skb->data; 1404 1405 seqno = ntohl(icmp->seqno); 1406 /* check if this is the first seqno. This means that if the 1407 * first packet is lost, the tp meter does not work anymore! 1408 */ 1409 if (seqno == BATADV_TP_FIRST_SEQ) { 1410 tp_vars = batadv_tp_init_recv(bat_priv, icmp); 1411 if (!tp_vars) { 1412 batadv_dbg(BATADV_DBG_TP_METER, bat_priv, 1413 "Meter: seqno != BATADV_TP_FIRST_SEQ cannot initiate connection\n"); 1414 goto out; 1415 } 1416 } else { 1417 tp_vars = batadv_tp_list_find_session(bat_priv, icmp->orig, 1418 icmp->session); 1419 if (!tp_vars) { 1420 batadv_dbg(BATADV_DBG_TP_METER, bat_priv, 1421 "Unexpected packet from %pM!\n", 1422 icmp->orig); 1423 goto out; 1424 } 1425 } 1426 1427 if (unlikely(tp_vars->role != BATADV_TP_RECEIVER)) { 1428 batadv_dbg(BATADV_DBG_TP_METER, bat_priv, 1429 "Meter: dropping packet: not expected (role=%u)\n", 1430 tp_vars->role); 1431 goto out; 1432 } 1433 1434 tp_vars->last_recv_time = jiffies; 1435 1436 /* if the packet is a duplicate, it may be the case that an ACK has been 1437 * lost. Resend the ACK 1438 */ 1439 if (batadv_seq_before(seqno, tp_vars->last_recv)) 1440 goto send_ack; 1441 1442 /* if the packet is out of order enqueue it */ 1443 if (ntohl(icmp->seqno) != tp_vars->last_recv) { 1444 /* exit immediately (and do not send any ACK) if the packet has 1445 * not been enqueued correctly 1446 */ 1447 if (!batadv_tp_handle_out_of_order(tp_vars, skb)) 1448 goto out; 1449 1450 /* send a duplicate ACK */ 1451 goto send_ack; 1452 } 1453 1454 /* if everything was fine count the ACKed bytes */ 1455 packet_size = skb->len - sizeof(struct batadv_unicast_packet); 1456 tp_vars->last_recv += packet_size; 1457 1458 /* check if this ordered message filled a gap.... */ 1459 batadv_tp_ack_unordered(tp_vars); 1460 1461 send_ack: 1462 /* send the ACK. If the received packet was out of order, the ACK that 1463 * is going to be sent is a duplicate (the sender will count them and 1464 * possibly enter Fast Retransmit as soon as it has reached 3) 1465 */ 1466 batadv_tp_send_ack(bat_priv, icmp->orig, tp_vars->last_recv, 1467 icmp->timestamp, icmp->session, icmp->uid); 1468 out: 1469 if (likely(tp_vars)) 1470 batadv_tp_vars_put(tp_vars); 1471 } 1472 1473 /** 1474 * batadv_tp_meter_recv() - main TP Meter receiving function 1475 * @bat_priv: the bat priv with all the soft interface information 1476 * @skb: the buffer containing the received packet 1477 */ 1478 void batadv_tp_meter_recv(struct batadv_priv *bat_priv, struct sk_buff *skb) 1479 { 1480 struct batadv_icmp_tp_packet *icmp; 1481 1482 icmp = (struct batadv_icmp_tp_packet *)skb->data; 1483 1484 switch (icmp->subtype) { 1485 case BATADV_TP_MSG: 1486 batadv_tp_recv_msg(bat_priv, skb); 1487 break; 1488 case BATADV_TP_ACK: 1489 batadv_tp_recv_ack(bat_priv, skb); 1490 break; 1491 default: 1492 batadv_dbg(BATADV_DBG_TP_METER, bat_priv, 1493 "Received unknown TP Metric packet type %u\n", 1494 icmp->subtype); 1495 } 1496 consume_skb(skb); 1497 } 1498 1499 /** 1500 * batadv_tp_meter_init() - initialize global tp_meter structures 1501 */ 1502 void __init batadv_tp_meter_init(void) 1503 { 1504 get_random_bytes(batadv_tp_prerandom, sizeof(batadv_tp_prerandom)); 1505 } 1506