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