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