// SPDX-License-Identifier: GPL-2.0/* Multipath TCP * * Copyright (c) 2017 - 2019, Intel Corporation. */ #define pr_fmt(fmt) "MPTCP: " fmt #include <linux/kernel.h>#include <linux/module.h>#include <linux/netdevice.h>#include <linux/sched/signal.h>#include <linux/atomic.h>#include <net/aligned_data.h>#include <net/rps.h>#include <net/sock.h>#include <net/inet_common.h>#include <net/inet_hashtables.h>#include <net/protocol.h>#include <net/tcp_states.h>#if IS_ENABLED(CONFIG_MPTCP_IPV6)#include <net/transp_v6.h>#endif#include <net/mptcp.h>#include <net/hotdata.h>#include <net/xfrm.h>#include <asm/ioctls.h>#include "protocol.h"#include "mib.h" static unsigned int mptcp_inq_hint(const struct sock *sk); #define CREATE_TRACE_POINTS#include <trace/events/mptcp.h> #if IS_ENABLED(CONFIG_MPTCP_IPV6)struct mptcp6_sock { struct mptcp_sock msk; struct ipv6_pinfo np;};#endif enum { MPTCP_CMSG_TS = BIT(0), MPTCP_CMSG_INQ = BIT(1),}; static struct percpu_counter mptcp_sockets_allocated ____cacheline_aligned_in_smp; static void __mptcp_destroy_sock(struct sock *sk);static void mptcp_check_send_data_fin(struct sock *sk); DEFINE_PER_CPU(struct mptcp_delegated_action, mptcp_delegated_actions) = { .bh_lock = INIT_LOCAL_LOCK(bh_lock),};static struct net_device *mptcp_napi_dev; /* Returns end sequence number of the receiver's advertised window */static u64 mptcp_wnd_end(const struct mptcp_sock *msk){ return READ_ONCE(msk->wnd_end);} static const struct proto_ops *mptcp_fallback_tcp_ops(const struct sock *sk){ unsigned short family = READ_ONCE(sk->sk_family); #if IS_ENABLED(CONFIG_MPTCP_IPV6) if (family == AF_INET6) return &inet6_stream_ops;#endif WARN_ON_ONCE(family != AF_INET); return &inet_stream_ops;} bool __mptcp_try_fallback(struct mptcp_sock *msk, int fb_mib){ struct net *net = sock_net((struct sock *)msk); if (__mptcp_check_fallback(msk)) return true; /* The caller possibly is not holding the msk socket lock, but * in the fallback case only the current subflow is touching * the OoO queue. */ if (!RB_EMPTY_ROOT(&msk->out_of_order_queue)) return false; spin_lock_bh(&msk->fallback_lock); if (!msk->allow_infinite_fallback) { spin_unlock_bh(&msk->fallback_lock); return false; } msk->allow_subflows = false; set_bit(MPTCP_FALLBACK_DONE, &msk->flags); clear_bit(MPTCP_RTX_ENABLED, &msk->flags); __MPTCP_INC_STATS(net, fb_mib); spin_unlock_bh(&msk->fallback_lock); return true;} static int __mptcp_socket_create(struct mptcp_sock *msk){ struct mptcp_subflow_context *subflow; struct sock *sk = (struct sock *)msk; struct socket *ssock; int err; err = mptcp_subflow_create_socket(sk, sk->sk_family, &ssock); if (err) return err; msk->scaling_ratio = tcp_sk(ssock->sk)->scaling_ratio; WRITE_ONCE(msk->first, ssock->sk); subflow = mptcp_subflow_ctx(ssock->sk); list_add(&subflow->node, &msk->conn_list); sock_hold(ssock->sk); subflow->request_mptcp = 1; subflow->subflow_id = msk->subflow_id++; /* This is the first subflow, always with id 0 */ WRITE_ONCE(subflow->local_id, 0); mptcp_sock_graft(msk->first, sk->sk_socket); iput(SOCK_INODE(ssock)); return 0;} /* If the MPC handshake is not started, returns the first subflow, * eventually allocating it. */struct sock *__mptcp_nmpc_sk(struct mptcp_sock *msk){ struct sock *sk = (struct sock *)msk; int ret; if (!((1 << sk->sk_state) & (TCPF_CLOSE | TCPF_LISTEN))) return ERR_PTR(-EINVAL); if (!msk->first) { ret = __mptcp_socket_create(msk); if (ret) return ERR_PTR(ret); } return msk->first;} static void mptcp_drop(struct sock *sk, struct sk_buff *skb){ /* The skb forward memory was already transferred to sk by * mptcp_borrow_fwdmem(), even before setting the destructor. */ if (!skb->destructor) sk_mem_reclaim(sk); sk_drops_skbadd(sk, skb); __kfree_skb(skb);} static bool __mptcp_try_coalesce(struct sock *sk, struct sk_buff *to, struct sk_buff *from, bool *fragstolen, int *delta){ int limit = READ_ONCE(sk->sk_rcvbuf); if (unlikely(MPTCP_SKB_CB(to)->cant_coalesce) || MPTCP_SKB_CB(from)->offset || ((to->len + from->len) > (limit >> 3)) || !skb_try_coalesce(to, from, fragstolen, delta)) return false; pr_debug("colesced seq %llx into %llx new len %d new end seq %llx\n", MPTCP_SKB_CB(from)->map_seq, MPTCP_SKB_CB(to)->map_seq, to->len, MPTCP_SKB_CB(from)->end_seq); MPTCP_SKB_CB(to)->end_seq = MPTCP_SKB_CB(from)->end_seq; return true;} static bool mptcp_try_coalesce(struct sock *sk, struct sk_buff *to, struct sk_buff *from){ bool fragstolen; int delta; if (!__mptcp_try_coalesce(sk, to, from, &fragstolen, &delta)) return false; /* note the fwd memory can reach a negative value after accounting * for the delta, but the later skb free will restore a non * negative one */ atomic_add(delta, &sk->sk_rmem_alloc); sk_mem_charge(sk, delta); kfree_skb_partial(from, fragstolen); return true;} static bool mptcp_ooo_try_coalesce(struct mptcp_sock *msk, struct sk_buff *to, struct sk_buff *from){ if (MPTCP_SKB_CB(from)->map_seq != MPTCP_SKB_CB(to)->end_seq) return false; return mptcp_try_coalesce((struct sock *)msk, to, from);} /* "inspired" by tcp_rcvbuf_grow(), main difference: * - mptcp does not maintain a msk-level window clamp * - returns true when the receive buffer is actually updated */static bool mptcp_rcvbuf_grow(struct sock *sk, u32 newval){ struct mptcp_sock *msk = mptcp_sk(sk); const struct net *net = sock_net(sk); u32 rcvwin, rcvbuf, cap, oldval; u64 grow; oldval = msk->rcvq_space.space; msk->rcvq_space.space = newval; if (!READ_ONCE(net->ipv4.sysctl_tcp_moderate_rcvbuf) || (sk->sk_userlocks & SOCK_RCVBUF_LOCK)) return false; /* DRS is always one RTT late. */ rcvwin = newval << 1; /* slow start: allow the sender to double its rate. */ grow = (u64)rcvwin * (newval - oldval); do_div(grow, oldval); rcvwin += grow << 1; cap = READ_ONCE(net->ipv4.sysctl_tcp_rmem[2]); rcvbuf = min_t(u32, mptcp_space_from_win(sk, rcvwin), cap); if (rcvbuf > sk->sk_rcvbuf) { WRITE_ONCE(sk->sk_rcvbuf, rcvbuf); return true; } return false;} /* "Inspired" from the TCP version; main difference: stop as soon as the MPTCP * socket is under memory limit. */static void mptcp_prune_ofo_queue(struct sock *sk, const struct sk_buff *in_skb){ struct mptcp_sock *msk = mptcp_sk(sk); struct rb_node *node, *prev; bool pruned = false; u64 mem; if (RB_EMPTY_ROOT(&msk->out_of_order_queue)) return; node = &msk->ooo_last_skb->rbnode; do { struct sk_buff *skb = rb_to_skb(node); /* Stop pruning if the incoming skb would land in OoO tail. */ if (after64(MPTCP_SKB_CB(in_skb)->map_seq, MPTCP_SKB_CB(skb)->map_seq)) break; pruned = true; prev = rb_prev(node); rb_erase(node, &msk->out_of_order_queue); mptcp_drop(sk, skb); msk->ooo_last_skb = rb_to_skb(prev); mem = (unsigned int)sk_rmem_alloc_get(sk); if (mem <= sk->sk_rcvbuf) break; node = prev; } while (node); if (pruned) MPTCP_INC_STATS(sock_net(sk), MPTCP_MIB_OFOPRUNED);} /* The stack can't drop packets for fallback socket at the msk level, or the * stream will break. */static bool mptcp_can_ingest(const struct sock *sk){ return likely(sk_rmem_alloc_get(sk) <= READ_ONCE(sk->sk_rcvbuf)) || __mptcp_check_fallback(mptcp_sk(sk));} static bool mptcp_try_rmem_schedule(struct sock *sk, const struct sk_buff *skb){ if (!mptcp_can_ingest(sk)) { mptcp_prune_ofo_queue(sk, skb); return mptcp_can_ingest(sk); } return true;} /* "inspired" by tcp_data_queue_ofo(), main differences: * - use mptcp seqs * - don't cope with sacks */static void mptcp_data_queue_ofo(struct mptcp_sock *msk, struct sk_buff *skb){ struct sock *sk = (struct sock *)msk; struct rb_node **p, *parent; u64 seq, end_seq, max_seq; struct sk_buff *skb1; seq = MPTCP_SKB_CB(skb)->map_seq; end_seq = MPTCP_SKB_CB(skb)->end_seq; max_seq = atomic64_read(&msk->rcv_wnd_sent); pr_debug("msk=%p seq=%llx limit=%llx empty=%d\n", msk, seq, max_seq, RB_EMPTY_ROOT(&msk->out_of_order_queue)); if (after64(end_seq, max_seq)) { /* out of window */ mptcp_drop(sk, skb); pr_debug("oow by %lld, rcv_wnd_sent %llu\n", (unsigned long long)end_seq - (unsigned long)max_seq, (unsigned long long)atomic64_read(&msk->rcv_wnd_sent)); MPTCP_INC_STATS(sock_net(sk), MPTCP_MIB_NODSSWINDOW); return; } if (!mptcp_try_rmem_schedule(sk, skb)) { MPTCP_INC_STATS(sock_net(sk), MPTCP_MIB_RCVPRUNED); mptcp_drop(sk, skb); return; } p = &msk->out_of_order_queue.rb_node; MPTCP_INC_STATS(sock_net(sk), MPTCP_MIB_OFOQUEUE); if (RB_EMPTY_ROOT(&msk->out_of_order_queue)) { rb_link_node(&skb->rbnode, NULL, p); rb_insert_color(&skb->rbnode, &msk->out_of_order_queue); msk->ooo_last_skb = skb; goto end; } /* with 2 subflows, adding at end of ooo queue is quite likely * Use of ooo_last_skb avoids the O(Log(N)) rbtree lookup. */ if (mptcp_ooo_try_coalesce(msk, msk->ooo_last_skb, skb)) { MPTCP_INC_STATS(sock_net(sk), MPTCP_MIB_OFOMERGE); MPTCP_INC_STATS(sock_net(sk), MPTCP_MIB_OFOQUEUETAIL); return; } /* Can avoid an rbtree lookup if we are adding skb after ooo_last_skb */ if (!before64(seq, MPTCP_SKB_CB(msk->ooo_last_skb)->end_seq)) { MPTCP_INC_STATS(sock_net(sk), MPTCP_MIB_OFOQUEUETAIL); parent = &msk->ooo_last_skb->rbnode; p = &parent->rb_right; goto insert; } /* Find place to insert this segment. Handle overlaps on the way. */ parent = NULL; while (*p) { parent = *p; skb1 = rb_to_skb(parent); if (before64(seq, MPTCP_SKB_CB(skb1)->map_seq)) { p = &parent->rb_left; continue; } if (before64(seq, MPTCP_SKB_CB(skb1)->end_seq)) { if (!after64(end_seq, MPTCP_SKB_CB(skb1)->end_seq)) { /* All the bits are present. Drop. */ mptcp_drop(sk, skb); MPTCP_INC_STATS(sock_net(sk), MPTCP_MIB_DUPDATA); return; } if (after64(seq, MPTCP_SKB_CB(skb1)->map_seq)) { /* partial overlap: * | skb | * | skb1 | * continue traversing */ } else { /* skb's seq == skb1's seq and skb covers skb1. * Replace skb1 with skb. */ rb_replace_node(&skb1->rbnode, &skb->rbnode, &msk->out_of_order_queue); mptcp_drop(sk, skb1); MPTCP_INC_STATS(sock_net(sk), MPTCP_MIB_DUPDATA); goto merge_right; } } else if (mptcp_ooo_try_coalesce(msk, skb1, skb)) { MPTCP_INC_STATS(sock_net(sk), MPTCP_MIB_OFOMERGE); return; } p = &parent->rb_right; } insert: /* Insert segment into RB tree. */ rb_link_node(&skb->rbnode, parent, p); rb_insert_color(&skb->rbnode, &msk->out_of_order_queue); merge_right: /* Remove other segments covered by skb. */ while ((skb1 = skb_rb_next(skb)) != NULL) { if (before64(end_seq, MPTCP_SKB_CB(skb1)->end_seq)) break; rb_erase(&skb1->rbnode, &msk->out_of_order_queue); mptcp_drop(sk, skb1); MPTCP_INC_STATS(sock_net(sk), MPTCP_MIB_DUPDATA); } /* If there is no skb after us, we are the last_skb ! */ if (!skb1) msk->ooo_last_skb = skb; end: skb_condense(skb); skb_set_owner_r(skb, sk);} static void mptcp_init_skb(struct sock *ssk, struct sk_buff *skb, int offset, int copy_len){ struct mptcp_subflow_context *subflow = mptcp_subflow_ctx(ssk); bool has_rxtstamp = TCP_SKB_CB(skb)->has_rxtstamp; /* the skb map_seq accounts for the skb offset: * mptcp_subflow_get_mapped_dsn() is based on the current tp->copied_seq * value */ MPTCP_SKB_CB(skb)->map_seq = mptcp_subflow_get_mapped_dsn(subflow); MPTCP_SKB_CB(skb)->end_seq = MPTCP_SKB_CB(skb)->map_seq + copy_len; MPTCP_SKB_CB(skb)->offset = offset; MPTCP_SKB_CB(skb)->has_rxtstamp = has_rxtstamp; MPTCP_SKB_CB(skb)->cant_coalesce = 0; __skb_unlink(skb, &ssk->sk_receive_queue); skb_ext_reset(skb); skb_dst_drop(skb);} static bool __mptcp_move_skb(struct sock *sk, struct sk_buff *skb){ u64 copy_len = MPTCP_SKB_CB(skb)->end_seq - MPTCP_SKB_CB(skb)->map_seq; struct mptcp_sock *msk = mptcp_sk(sk); struct sk_buff *tail; mptcp_borrow_fwdmem(sk, skb); if (MPTCP_SKB_CB(skb)->map_seq == msk->ack_seq) { /* in sequence */insert: if (!mptcp_try_rmem_schedule(sk, skb)) { MPTCP_INC_STATS(sock_net(sk), MPTCP_MIB_RCVPRUNED); mptcp_drop(sk, skb); return false; } msk->bytes_received += copy_len; WRITE_ONCE(msk->ack_seq, msk->ack_seq + copy_len); tail = skb_peek_tail(&sk->sk_receive_queue); if (tail && mptcp_try_coalesce(sk, tail, skb)) return true; skb_set_owner_r(skb, sk); __skb_queue_tail(&sk->sk_receive_queue, skb); return true; } else if (after64(MPTCP_SKB_CB(skb)->map_seq, msk->ack_seq)) { mptcp_data_queue_ofo(msk, skb); return false; } /* Partial packet */ if (after64(MPTCP_SKB_CB(skb)->end_seq, msk->ack_seq)) { copy_len = MPTCP_SKB_CB(skb)->end_seq - msk->ack_seq; MPTCP_SKB_CB(skb)->offset += msk->ack_seq - MPTCP_SKB_CB(skb)->map_seq; MPTCP_SKB_CB(skb)->map_seq += msk->ack_seq - MPTCP_SKB_CB(skb)->map_seq; goto insert; } /* Completely old data */ MPTCP_INC_STATS(sock_net(sk), MPTCP_MIB_DUPDATA); mptcp_drop(sk, skb); return false;} static void mptcp_stop_rtx_timer(struct sock *sk){ sk_stop_timer(sk, &sk->mptcp_retransmit_timer); mptcp_sk(sk)->timer_ival = 0;} Lines 1–500 of 4892. Load more
// SPDX-License-Identifier: GPL-2.0 /* Multipath TCP * * Copyright (c) 2017 - 2019, Intel Corporation. */ #define pr_fmt(fmt) "MPTCP: " fmt #include <linux/kernel.h> #include <linux/module.h> #include <linux/netdevice.h> #include <linux/sched/signal.h> #include <linux/atomic.h> #include <net/aligned_data.h> #include <net/rps.h> #include <net/sock.h> #include <net/inet_common.h> #include <net/inet_hashtables.h> #include <net/protocol.h> #include <net/tcp_states.h> #if IS_ENABLED(CONFIG_MPTCP_IPV6) #include <net/transp_v6.h> #endif #include <net/mptcp.h> #include <net/hotdata.h> #include <net/xfrm.h> #include <asm/ioctls.h> #include "protocol.h" #include "mib.h" static unsigned int mptcp_inq_hint(const struct sock *sk); #define CREATE_TRACE_POINTS #include <trace/events/mptcp.h> #if IS_ENABLED(CONFIG_MPTCP_IPV6) struct mptcp6_sock { struct mptcp_sock msk; struct ipv6_pinfo np; }; #endif enum { MPTCP_CMSG_TS = BIT(0), MPTCP_CMSG_INQ = BIT(1), }; static struct percpu_counter mptcp_sockets_allocated ____cacheline_aligned_in_smp; static void __mptcp_destroy_sock(struct sock *sk); static void mptcp_check_send_data_fin(struct sock *sk); DEFINE_PER_CPU(struct mptcp_delegated_action, mptcp_delegated_actions) = { .bh_lock = INIT_LOCAL_LOCK(bh_lock), }; static struct net_device *mptcp_napi_dev; /* Returns end sequence number of the receiver's advertised window */ static u64 mptcp_wnd_end(const struct mptcp_sock *msk) { return READ_ONCE(msk->wnd_end); } static const struct proto_ops *mptcp_fallback_tcp_ops(const struct sock *sk) { unsigned short family = READ_ONCE(sk->sk_family); #if IS_ENABLED(CONFIG_MPTCP_IPV6) if (family == AF_INET6) return &inet6_stream_ops; #endif WARN_ON_ONCE(family != AF_INET); return &inet_stream_ops; } bool __mptcp_try_fallback(struct mptcp_sock *msk, int fb_mib) { struct net *net = sock_net((struct sock *)msk); if (__mptcp_check_fallback(msk)) return true; /* The caller possibly is not holding the msk socket lock, but * in the fallback case only the current subflow is touching * the OoO queue. */ if (!RB_EMPTY_ROOT(&msk->out_of_order_queue)) return false; spin_lock_bh(&msk->fallback_lock); if (!msk->allow_infinite_fallback) { spin_unlock_bh(&msk->fallback_lock); return false; } msk->allow_subflows = false; set_bit(MPTCP_FALLBACK_DONE, &msk->flags); clear_bit(MPTCP_RTX_ENABLED, &msk->flags); __MPTCP_INC_STATS(net, fb_mib); spin_unlock_bh(&msk->fallback_lock); return true; } static int __mptcp_socket_create(struct mptcp_sock *msk) { struct mptcp_subflow_context *subflow; struct sock *sk = (struct sock *)msk; struct socket *ssock; int err; err = mptcp_subflow_create_socket(sk, sk->sk_family, &ssock); if (err) return err; msk->scaling_ratio = tcp_sk(ssock->sk)->scaling_ratio; WRITE_ONCE(msk->first, ssock->sk); subflow = mptcp_subflow_ctx(ssock->sk); list_add(&subflow->node, &msk->conn_list); sock_hold(ssock->sk); subflow->request_mptcp = 1; subflow->subflow_id = msk->subflow_id++; /* This is the first subflow, always with id 0 */ WRITE_ONCE(subflow->local_id, 0); mptcp_sock_graft(msk->first, sk->sk_socket); iput(SOCK_INODE(ssock)); return 0; } /* If the MPC handshake is not started, returns the first subflow, * eventually allocating it. */ struct sock *__mptcp_nmpc_sk(struct mptcp_sock *msk) { struct sock *sk = (struct sock *)msk; int ret; if (!((1 << sk->sk_state) & (TCPF_CLOSE | TCPF_LISTEN))) return ERR_PTR(-EINVAL); if (!msk->first) { ret = __mptcp_socket_create(msk); if (ret) return ERR_PTR(ret); } return msk->first; } static void mptcp_drop(struct sock *sk, struct sk_buff *skb) { /* The skb forward memory was already transferred to sk by * mptcp_borrow_fwdmem(), even before setting the destructor. */ if (!skb->destructor) sk_mem_reclaim(sk); sk_drops_skbadd(sk, skb); __kfree_skb(skb); } static bool __mptcp_try_coalesce(struct sock *sk, struct sk_buff *to, struct sk_buff *from, bool *fragstolen, int *delta) { int limit = READ_ONCE(sk->sk_rcvbuf); if (unlikely(MPTCP_SKB_CB(to)->cant_coalesce) || MPTCP_SKB_CB(from)->offset || ((to->len + from->len) > (limit >> 3)) || !skb_try_coalesce(to, from, fragstolen, delta)) return false; pr_debug("colesced seq %llx into %llx new len %d new end seq %llx\n", MPTCP_SKB_CB(from)->map_seq, MPTCP_SKB_CB(to)->map_seq, to->len, MPTCP_SKB_CB(from)->end_seq); MPTCP_SKB_CB(to)->end_seq = MPTCP_SKB_CB(from)->end_seq; return true; } static bool mptcp_try_coalesce(struct sock *sk, struct sk_buff *to, struct sk_buff *from) { bool fragstolen; int delta; if (!__mptcp_try_coalesce(sk, to, from, &fragstolen, &delta)) return false; /* note the fwd memory can reach a negative value after accounting * for the delta, but the later skb free will restore a non * negative one */ atomic_add(delta, &sk->sk_rmem_alloc); sk_mem_charge(sk, delta); kfree_skb_partial(from, fragstolen); return true; } static bool mptcp_ooo_try_coalesce(struct mptcp_sock *msk, struct sk_buff *to, struct sk_buff *from) { if (MPTCP_SKB_CB(from)->map_seq != MPTCP_SKB_CB(to)->end_seq) return false; return mptcp_try_coalesce((struct sock *)msk, to, from); } /* "inspired" by tcp_rcvbuf_grow(), main difference: * - mptcp does not maintain a msk-level window clamp * - returns true when the receive buffer is actually updated */ static bool mptcp_rcvbuf_grow(struct sock *sk, u32 newval) { struct mptcp_sock *msk = mptcp_sk(sk); const struct net *net = sock_net(sk); u32 rcvwin, rcvbuf, cap, oldval; u64 grow; oldval = msk->rcvq_space.space; msk->rcvq_space.space = newval; if (!READ_ONCE(net->ipv4.sysctl_tcp_moderate_rcvbuf) || (sk->sk_userlocks & SOCK_RCVBUF_LOCK)) return false; /* DRS is always one RTT late. */ rcvwin = newval << 1; /* slow start: allow the sender to double its rate. */ grow = (u64)rcvwin * (newval - oldval); do_div(grow, oldval); rcvwin += grow << 1; cap = READ_ONCE(net->ipv4.sysctl_tcp_rmem[2]); rcvbuf = min_t(u32, mptcp_space_from_win(sk, rcvwin), cap); if (rcvbuf > sk->sk_rcvbuf) { WRITE_ONCE(sk->sk_rcvbuf, rcvbuf); return true; } return false; } /* "Inspired" from the TCP version; main difference: stop as soon as the MPTCP * socket is under memory limit. */ static void mptcp_prune_ofo_queue(struct sock *sk, const struct sk_buff *in_skb) { struct mptcp_sock *msk = mptcp_sk(sk); struct rb_node *node, *prev; bool pruned = false; u64 mem; if (RB_EMPTY_ROOT(&msk->out_of_order_queue)) return; node = &msk->ooo_last_skb->rbnode; do { struct sk_buff *skb = rb_to_skb(node); /* Stop pruning if the incoming skb would land in OoO tail. */ if (after64(MPTCP_SKB_CB(in_skb)->map_seq, MPTCP_SKB_CB(skb)->map_seq)) break; pruned = true; prev = rb_prev(node); rb_erase(node, &msk->out_of_order_queue); mptcp_drop(sk, skb); msk->ooo_last_skb = rb_to_skb(prev); mem = (unsigned int)sk_rmem_alloc_get(sk); if (mem <= sk->sk_rcvbuf) break; node = prev; } while (node); if (pruned) MPTCP_INC_STATS(sock_net(sk), MPTCP_MIB_OFOPRUNED); } /* The stack can't drop packets for fallback socket at the msk level, or the * stream will break. */ static bool mptcp_can_ingest(const struct sock *sk) { return likely(sk_rmem_alloc_get(sk) <= READ_ONCE(sk->sk_rcvbuf)) || __mptcp_check_fallback(mptcp_sk(sk)); } static bool mptcp_try_rmem_schedule(struct sock *sk, const struct sk_buff *skb) { if (!mptcp_can_ingest(sk)) { mptcp_prune_ofo_queue(sk, skb); return mptcp_can_ingest(sk); } return true; } /* "inspired" by tcp_data_queue_ofo(), main differences: * - use mptcp seqs * - don't cope with sacks */ static void mptcp_data_queue_ofo(struct mptcp_sock *msk, struct sk_buff *skb) { struct sock *sk = (struct sock *)msk; struct rb_node **p, *parent; u64 seq, end_seq, max_seq; struct sk_buff *skb1; seq = MPTCP_SKB_CB(skb)->map_seq; end_seq = MPTCP_SKB_CB(skb)->end_seq; max_seq = atomic64_read(&msk->rcv_wnd_sent); pr_debug("msk=%p seq=%llx limit=%llx empty=%d\n", msk, seq, max_seq, RB_EMPTY_ROOT(&msk->out_of_order_queue)); if (after64(end_seq, max_seq)) { /* out of window */ mptcp_drop(sk, skb); pr_debug("oow by %lld, rcv_wnd_sent %llu\n", (unsigned long long)end_seq - (unsigned long)max_seq, (unsigned long long)atomic64_read(&msk->rcv_wnd_sent)); MPTCP_INC_STATS(sock_net(sk), MPTCP_MIB_NODSSWINDOW); return; } if (!mptcp_try_rmem_schedule(sk, skb)) { MPTCP_INC_STATS(sock_net(sk), MPTCP_MIB_RCVPRUNED); mptcp_drop(sk, skb); return; } p = &msk->out_of_order_queue.rb_node; MPTCP_INC_STATS(sock_net(sk), MPTCP_MIB_OFOQUEUE); if (RB_EMPTY_ROOT(&msk->out_of_order_queue)) { rb_link_node(&skb->rbnode, NULL, p); rb_insert_color(&skb->rbnode, &msk->out_of_order_queue); msk->ooo_last_skb = skb; goto end; } /* with 2 subflows, adding at end of ooo queue is quite likely * Use of ooo_last_skb avoids the O(Log(N)) rbtree lookup. */ if (mptcp_ooo_try_coalesce(msk, msk->ooo_last_skb, skb)) { MPTCP_INC_STATS(sock_net(sk), MPTCP_MIB_OFOMERGE); MPTCP_INC_STATS(sock_net(sk), MPTCP_MIB_OFOQUEUETAIL); return; } /* Can avoid an rbtree lookup if we are adding skb after ooo_last_skb */ if (!before64(seq, MPTCP_SKB_CB(msk->ooo_last_skb)->end_seq)) { MPTCP_INC_STATS(sock_net(sk), MPTCP_MIB_OFOQUEUETAIL); parent = &msk->ooo_last_skb->rbnode; p = &parent->rb_right; goto insert; } /* Find place to insert this segment. Handle overlaps on the way. */ parent = NULL; while (*p) { parent = *p; skb1 = rb_to_skb(parent); if (before64(seq, MPTCP_SKB_CB(skb1)->map_seq)) { p = &parent->rb_left; continue; } if (before64(seq, MPTCP_SKB_CB(skb1)->end_seq)) { if (!after64(end_seq, MPTCP_SKB_CB(skb1)->end_seq)) { /* All the bits are present. Drop. */ mptcp_drop(sk, skb); MPTCP_INC_STATS(sock_net(sk), MPTCP_MIB_DUPDATA); return; } if (after64(seq, MPTCP_SKB_CB(skb1)->map_seq)) { /* partial overlap: * | skb | * | skb1 | * continue traversing */ } else { /* skb's seq == skb1's seq and skb covers skb1. * Replace skb1 with skb. */ rb_replace_node(&skb1->rbnode, &skb->rbnode, &msk->out_of_order_queue); mptcp_drop(sk, skb1); MPTCP_INC_STATS(sock_net(sk), MPTCP_MIB_DUPDATA); goto merge_right; } } else if (mptcp_ooo_try_coalesce(msk, skb1, skb)) { MPTCP_INC_STATS(sock_net(sk), MPTCP_MIB_OFOMERGE); return; } p = &parent->rb_right; } insert: /* Insert segment into RB tree. */ rb_link_node(&skb->rbnode, parent, p); rb_insert_color(&skb->rbnode, &msk->out_of_order_queue); merge_right: /* Remove other segments covered by skb. */ while ((skb1 = skb_rb_next(skb)) != NULL) { if (before64(end_seq, MPTCP_SKB_CB(skb1)->end_seq)) break; rb_erase(&skb1->rbnode, &msk->out_of_order_queue); mptcp_drop(sk, skb1); MPTCP_INC_STATS(sock_net(sk), MPTCP_MIB_DUPDATA); } /* If there is no skb after us, we are the last_skb ! */ if (!skb1) msk->ooo_last_skb = skb; end: skb_condense(skb); skb_set_owner_r(skb, sk); } static void mptcp_init_skb(struct sock *ssk, struct sk_buff *skb, int offset, int copy_len) { struct mptcp_subflow_context *subflow = mptcp_subflow_ctx(ssk); bool has_rxtstamp = TCP_SKB_CB(skb)->has_rxtstamp; /* the skb map_seq accounts for the skb offset: * mptcp_subflow_get_mapped_dsn() is based on the current tp->copied_seq * value */ MPTCP_SKB_CB(skb)->map_seq = mptcp_subflow_get_mapped_dsn(subflow); MPTCP_SKB_CB(skb)->end_seq = MPTCP_SKB_CB(skb)->map_seq + copy_len; MPTCP_SKB_CB(skb)->offset = offset; MPTCP_SKB_CB(skb)->has_rxtstamp = has_rxtstamp; MPTCP_SKB_CB(skb)->cant_coalesce = 0; __skb_unlink(skb, &ssk->sk_receive_queue); skb_ext_reset(skb); skb_dst_drop(skb); } static bool __mptcp_move_skb(struct sock *sk, struct sk_buff *skb) { u64 copy_len = MPTCP_SKB_CB(skb)->end_seq - MPTCP_SKB_CB(skb)->map_seq; struct mptcp_sock *msk = mptcp_sk(sk); struct sk_buff *tail; mptcp_borrow_fwdmem(sk, skb); if (MPTCP_SKB_CB(skb)->map_seq == msk->ack_seq) { /* in sequence */ insert: if (!mptcp_try_rmem_schedule(sk, skb)) { MPTCP_INC_STATS(sock_net(sk), MPTCP_MIB_RCVPRUNED); mptcp_drop(sk, skb); return false; } msk->bytes_received += copy_len; WRITE_ONCE(msk->ack_seq, msk->ack_seq + copy_len); tail = skb_peek_tail(&sk->sk_receive_queue); if (tail && mptcp_try_coalesce(sk, tail, skb)) return true; skb_set_owner_r(skb, sk); __skb_queue_tail(&sk->sk_receive_queue, skb); return true; } else if (after64(MPTCP_SKB_CB(skb)->map_seq, msk->ack_seq)) { mptcp_data_queue_ofo(msk, skb); return false; } /* Partial packet */ if (after64(MPTCP_SKB_CB(skb)->end_seq, msk->ack_seq)) { copy_len = MPTCP_SKB_CB(skb)->end_seq - msk->ack_seq; MPTCP_SKB_CB(skb)->offset += msk->ack_seq - MPTCP_SKB_CB(skb)->map_seq; MPTCP_SKB_CB(skb)->map_seq += msk->ack_seq - MPTCP_SKB_CB(skb)->map_seq; goto insert; } /* Completely old data */ MPTCP_INC_STATS(sock_net(sk), MPTCP_MIB_DUPDATA); mptcp_drop(sk, skb); return false; } static void mptcp_stop_rtx_timer(struct sock *sk) { sk_stop_timer(sk, &sk->mptcp_retransmit_timer); mptcp_sk(sk)->timer_ival = 0; }