From patchwork Thu Aug 2 23:34:37 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peter Oskolkov X-Patchwork-Id: 953002 X-Patchwork-Delegate: davem@davemloft.net Return-Path: X-Original-To: patchwork-incoming-netdev@ozlabs.org Delivered-To: patchwork-incoming-netdev@ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=vger.kernel.org (client-ip=209.132.180.67; helo=vger.kernel.org; envelope-from=netdev-owner@vger.kernel.org; receiver=) Authentication-Results: ozlabs.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=google.com header.i=@google.com header.b="pzbJe/v2"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 41hRNb4RTNz9s5c for ; Fri, 3 Aug 2018 09:34:55 +1000 (AEST) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1732090AbeHCB2L (ORCPT ); Thu, 2 Aug 2018 21:28:11 -0400 Received: from mail-io0-f201.google.com ([209.85.223.201]:36939 "EHLO mail-io0-f201.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727053AbeHCB2L (ORCPT ); Thu, 2 Aug 2018 21:28:11 -0400 Received: by mail-io0-f201.google.com with SMTP id l5-v6so2825459ioh.4 for ; Thu, 02 Aug 2018 16:34:46 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20161025; h=date:in-reply-to:message-id:mime-version:references:subject:from:to :cc; bh=pWztRfk0KM6ax3oD+E1yf8tb0/ZS2kY2fLFPdKSwh9g=; b=pzbJe/v2JwE1LV6K/jR9oFUxc/cXTdSoK0zf4WSwtkPOLKBW1/qxZtdTffL20mJohR kBd0ivAytT2tf1R1jFAzWCTI0dxmMcT9wzyGIaL6hQvBPOvNbstnLLRLju7GfSCS9DRx GaB5igSuuMzhXmJD7ybUAWWvwjbDHIeANDhYUfoAUANJS3cbPldsf6V2C2PxNsM9AN02 cTHbYyYlTTrxvdydjQWBV03vvF099s5JnXhKFVIL8QSAA3ZfUr5csASBQb3MDMj0fvDL lIG7xK+Fm+WgF5TK8tGFepksgfSanVGB4/5O0377mC5zn7+6AdsTHswSBcpUhxW5CgkV v2bQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:in-reply-to:message-id:mime-version :references:subject:from:to:cc; bh=pWztRfk0KM6ax3oD+E1yf8tb0/ZS2kY2fLFPdKSwh9g=; b=NFkUrao7mCRxBVjhJfgmwHhceF1Lpw2G56L87QeWRtl1iyZGt/qyk22DAPNJCWRaoa cYmIqWlIpbE7K6roZfAT5trXoSKj0MD1L1k0Xe8Je5XsoVkww607xdtr2RdUaULuJeta sPXoGW0JjEdAov0KvODRJtODQ4TCsclqfQcv2CPq3u0d7MvweIGXjPjmzNsarsbO7nxJ dPvCoI5FSLlEn2NztJxIQVMH1ZQwXI+PfmeWetnKvIn7dtWLEIP2qmpYVIf+gXNqF+Ow jA3gBKFdh3o6JevBJNtMt1YtaVldhKDW+/n0vWdRHQwyc5jVLkkzthBHlCBJGm+m7ysE C24Q== X-Gm-Message-State: AOUpUlHE5yiXTih3VKIzHLNKBKw5wYD8Irt60lx1x5WJTC9d480K/KlP Y0lLysUmtR8wYMXgQsvGSO8glrei X-Google-Smtp-Source: AAOMgpeYaoAMYYbQSimvcTdgJEdIQ39l362nZtvazKTWHDMC5ljfU/lhc2YwzuZSuZ0qHFBRaGdDj1Af X-Received: by 2002:a24:5fc8:: with SMTP id r191-v6mr2294922itb.38.1533252885771; Thu, 02 Aug 2018 16:34:45 -0700 (PDT) Date: Thu, 2 Aug 2018 23:34:37 +0000 In-Reply-To: <20180802233439.51643-1-posk@google.com> Message-Id: <20180802233439.51643-2-posk@google.com> Mime-Version: 1.0 References: <20180802233439.51643-1-posk@google.com> X-Mailer: git-send-email 2.18.0.597.ga71716f1ad-goog Subject: [PATCH v2 net-next 1/3] ip: discard IPv4 datagrams with overlapping segments. From: Peter Oskolkov To: David Miller , netdev@vger.kernel.org Cc: Eric Dumazet , Florian Westphal , Peter Oskolkov Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org This behavior is required in IPv6, and there is little need to tolerate overlapping fragments in IPv4. This change simplifies the code and eliminates potential DDoS attack vectors. Tested: ran ip_defrag selftest (not yet available uptream). Suggested-by: David S. Miller Signed-off-by: Peter Oskolkov Signed-off-by: Eric Dumazet Cc: Florian Westphal Acked-by: Stephen Hemminger --- include/uapi/linux/snmp.h | 1 + net/ipv4/ip_fragment.c | 75 ++++++++++----------------------------- net/ipv4/proc.c | 1 + 3 files changed, 21 insertions(+), 56 deletions(-) diff --git a/include/uapi/linux/snmp.h b/include/uapi/linux/snmp.h index e5ebc83827ab..f80135e5feaa 100644 --- a/include/uapi/linux/snmp.h +++ b/include/uapi/linux/snmp.h @@ -56,6 +56,7 @@ enum IPSTATS_MIB_ECT1PKTS, /* InECT1Pkts */ IPSTATS_MIB_ECT0PKTS, /* InECT0Pkts */ IPSTATS_MIB_CEPKTS, /* InCEPkts */ + IPSTATS_MIB_REASM_OVERLAPS, /* ReasmOverlaps */ __IPSTATS_MIB_MAX }; diff --git a/net/ipv4/ip_fragment.c b/net/ipv4/ip_fragment.c index d14d741fb05e..960bf5eab59f 100644 --- a/net/ipv4/ip_fragment.c +++ b/net/ipv4/ip_fragment.c @@ -277,6 +277,7 @@ static int ip_frag_reinit(struct ipq *qp) /* Add new segment to existing queue. */ static int ip_frag_queue(struct ipq *qp, struct sk_buff *skb) { + struct net *net = container_of(qp->q.net, struct net, ipv4.frags); struct sk_buff *prev, *next; struct net_device *dev; unsigned int fragsize; @@ -357,65 +358,23 @@ static int ip_frag_queue(struct ipq *qp, struct sk_buff *skb) } found: - /* We found where to put this one. Check for overlap with - * preceding fragment, and, if needed, align things so that - * any overlaps are eliminated. + /* RFC5722, Section 4, amended by Errata ID : 3089 + * When reassembling an IPv6 datagram, if + * one or more its constituent fragments is determined to be an + * overlapping fragment, the entire datagram (and any constituent + * fragments) MUST be silently discarded. + * + * We do the same here for IPv4. */ - if (prev) { - int i = (prev->ip_defrag_offset + prev->len) - offset; - if (i > 0) { - offset += i; - err = -EINVAL; - if (end <= offset) - goto err; - err = -ENOMEM; - if (!pskb_pull(skb, i)) - goto err; - if (skb->ip_summed != CHECKSUM_UNNECESSARY) - skb->ip_summed = CHECKSUM_NONE; - } - } + /* Is there an overlap with the previous fragment? */ + if (prev && + (prev->ip_defrag_offset + prev->len) > offset) + goto discard_qp; - err = -ENOMEM; - - while (next && next->ip_defrag_offset < end) { - int i = end - next->ip_defrag_offset; /* overlap is 'i' bytes */ - - if (i < next->len) { - int delta = -next->truesize; - - /* Eat head of the next overlapped fragment - * and leave the loop. The next ones cannot overlap. - */ - if (!pskb_pull(next, i)) - goto err; - delta += next->truesize; - if (delta) - add_frag_mem_limit(qp->q.net, delta); - next->ip_defrag_offset += i; - qp->q.meat -= i; - if (next->ip_summed != CHECKSUM_UNNECESSARY) - next->ip_summed = CHECKSUM_NONE; - break; - } else { - struct sk_buff *free_it = next; - - /* Old fragment is completely overridden with - * new one drop it. - */ - next = next->next; - - if (prev) - prev->next = next; - else - qp->q.fragments = next; - - qp->q.meat -= free_it->len; - sub_frag_mem_limit(qp->q.net, free_it->truesize); - kfree_skb(free_it); - } - } + /* Is there an overlap with the next fragment? */ + if (next && next->ip_defrag_offset < end) + goto discard_qp; /* Note : skb->ip_defrag_offset and skb->dev share the same location */ dev = skb->dev; @@ -463,6 +422,10 @@ static int ip_frag_queue(struct ipq *qp, struct sk_buff *skb) skb_dst_drop(skb); return -EINPROGRESS; +discard_qp: + inet_frag_kill(&qp->q); + err = -EINVAL; + __IP_INC_STATS(net, IPSTATS_MIB_REASM_OVERLAPS); err: kfree_skb(skb); return err; diff --git a/net/ipv4/proc.c b/net/ipv4/proc.c index b46e4cf9a55a..70289682a670 100644 --- a/net/ipv4/proc.c +++ b/net/ipv4/proc.c @@ -119,6 +119,7 @@ static const struct snmp_mib snmp4_ipextstats_list[] = { SNMP_MIB_ITEM("InECT1Pkts", IPSTATS_MIB_ECT1PKTS), SNMP_MIB_ITEM("InECT0Pkts", IPSTATS_MIB_ECT0PKTS), SNMP_MIB_ITEM("InCEPkts", IPSTATS_MIB_CEPKTS), + SNMP_MIB_ITEM("ReasmOverlaps", IPSTATS_MIB_REASM_OVERLAPS), SNMP_MIB_SENTINEL }; From patchwork Thu Aug 2 23:34:38 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peter Oskolkov X-Patchwork-Id: 953003 X-Patchwork-Delegate: davem@davemloft.net Return-Path: X-Original-To: patchwork-incoming-netdev@ozlabs.org Delivered-To: patchwork-incoming-netdev@ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=vger.kernel.org (client-ip=209.132.180.67; helo=vger.kernel.org; envelope-from=netdev-owner@vger.kernel.org; receiver=) Authentication-Results: ozlabs.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=google.com header.i=@google.com header.b="Nvv7dUtE"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 41hRNc3kr1z9s4Z for ; Fri, 3 Aug 2018 09:34:56 +1000 (AEST) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1732119AbeHCB2O (ORCPT ); Thu, 2 Aug 2018 21:28:14 -0400 Received: from mail-it0-f74.google.com ([209.85.214.74]:42620 "EHLO mail-it0-f74.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727053AbeHCB2O (ORCPT ); Thu, 2 Aug 2018 21:28:14 -0400 Received: by mail-it0-f74.google.com with SMTP id l138-v6so3819901itb.7 for ; Thu, 02 Aug 2018 16:34:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20161025; h=date:in-reply-to:message-id:mime-version:references:subject:from:to :cc; bh=heTAa9AGMqLlkPizDt3Ram1Oeb91RCGiNJBfxURteDA=; b=Nvv7dUtEAZWP15qxHtnDjhjOSvSn2msU2/aes787Dn+dx7syr6W7ZMpwJwEAv2kuU5 iDfY6uUKVt6jd5CBiy7ax93MTR2oBLSEXG2AZTYNK3LaEfSc7zht2Yk3yFXThSmiu5h7 m+qScpP5QjrXN/Uut2fg0z+l0hrjH1XmJOBe/UJlCBcPP7bOy5PHfrfa9a0blcutLwfV lDWT0CqcM7vRNX/MjZGreEDqw8wSFkiQdX4FSnOK2v61YQ7lLuZ7OeL0VOOOVzyxYDHr OP1C52cRGEhzQiDH6rfyACIASazWCA8Ir17GzjnKvG4Av0e1rc+XSL9qrwSKhrqC9RIB 8QnQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:in-reply-to:message-id:mime-version :references:subject:from:to:cc; bh=heTAa9AGMqLlkPizDt3Ram1Oeb91RCGiNJBfxURteDA=; b=V1Ll95IdU5OCZpmExvULfQPGMY8eix1XxiIDQA75cR2ouKawqlO0x6XWfZGkWiHlD+ 3zOHG4GlwrNMqS9ZFpiu0x5/9Wc3L6s9ea4C2sRt39YnGRuDI88WYN1bluX/nT+wuEya iv2eiFb/7LtqctJIoPr6KkhKxeNhiL4flXQ4EqRPeKTSZLvWiHqxFGLNzD+X+tReVdkm 9QFcGFXmreu4caLUao55YxNdxWf7x+dKDz3CxAgap+niLPad/BVVb7pybqD2B8nJ2FvQ Mwd7sRXNbb4B/RbZ+Rf2ESwyD+OwqUM1GBNb7OuYpnN+UX3W0K1Wf5kUOh84vV7u3TOe 2fHw== X-Gm-Message-State: AOUpUlG3j4W7HjF5dB4YWi8M2rl0QN9cNtH7S4NVMnTOqHkTDk6QX0MB UqaWIfhQqX9SIbgn4Z0bOu+11oDP X-Google-Smtp-Source: AAOMgperJRE8QVH9oHLk4HdCErqs0h3CfecWVonki4MWrSPOg7HlbWev66ODp5ZTCnx9kEpR3h2i8pdE X-Received: by 2002:a24:5687:: with SMTP id o129-v6mr2244666itb.21.1533252888168; Thu, 02 Aug 2018 16:34:48 -0700 (PDT) Date: Thu, 2 Aug 2018 23:34:38 +0000 In-Reply-To: <20180802233439.51643-1-posk@google.com> Message-Id: <20180802233439.51643-3-posk@google.com> Mime-Version: 1.0 References: <20180802233439.51643-1-posk@google.com> X-Mailer: git-send-email 2.18.0.597.ga71716f1ad-goog Subject: [PATCH v2 net-next 2/3] net: modify skb_rbtree_purge to return the truesize of all purged skbs. From: Peter Oskolkov To: David Miller , netdev@vger.kernel.org Cc: Eric Dumazet , Florian Westphal , Peter Oskolkov Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org Tested: see the next patch is the series. Suggested-by: Eric Dumazet Signed-off-by: Peter Oskolkov Signed-off-by: Eric Dumazet Cc: Florian Westphal --- include/linux/skbuff.h | 2 +- net/core/skbuff.c | 6 +++++- 2 files changed, 6 insertions(+), 2 deletions(-) diff --git a/include/linux/skbuff.h b/include/linux/skbuff.h index fd3cb1b247df..47848367c816 100644 --- a/include/linux/skbuff.h +++ b/include/linux/skbuff.h @@ -2585,7 +2585,7 @@ static inline void __skb_queue_purge(struct sk_buff_head *list) kfree_skb(skb); } -void skb_rbtree_purge(struct rb_root *root); +unsigned int skb_rbtree_purge(struct rb_root *root); void *netdev_alloc_frag(unsigned int fragsz); diff --git a/net/core/skbuff.c b/net/core/skbuff.c index 51b0a9126e12..8d574a88125d 100644 --- a/net/core/skbuff.c +++ b/net/core/skbuff.c @@ -2858,23 +2858,27 @@ EXPORT_SYMBOL(skb_queue_purge); /** * skb_rbtree_purge - empty a skb rbtree * @root: root of the rbtree to empty + * Return value: the sum of truesizes of all purged skbs. * * Delete all buffers on an &sk_buff rbtree. Each buffer is removed from * the list and one reference dropped. This function does not take * any lock. Synchronization should be handled by the caller (e.g., TCP * out-of-order queue is protected by the socket lock). */ -void skb_rbtree_purge(struct rb_root *root) +unsigned int skb_rbtree_purge(struct rb_root *root) { struct rb_node *p = rb_first(root); + unsigned int sum = 0; while (p) { struct sk_buff *skb = rb_entry(p, struct sk_buff, rbnode); p = rb_next(p); rb_erase(&skb->rbnode, root); + sum += skb->truesize; kfree_skb(skb); } + return sum; } /** From patchwork Thu Aug 2 23:34:39 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peter Oskolkov X-Patchwork-Id: 953004 X-Patchwork-Delegate: davem@davemloft.net Return-Path: X-Original-To: patchwork-incoming-netdev@ozlabs.org Delivered-To: patchwork-incoming-netdev@ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=vger.kernel.org (client-ip=209.132.180.67; helo=vger.kernel.org; envelope-from=netdev-owner@vger.kernel.org; receiver=) Authentication-Results: ozlabs.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=google.com header.i=@google.com header.b="MbyN3Fvs"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 41hRNd2KRTz9s5c for ; Fri, 3 Aug 2018 09:34:57 +1000 (AEST) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1732138AbeHCB2R (ORCPT ); Thu, 2 Aug 2018 21:28:17 -0400 Received: from mail-vk0-f74.google.com ([209.85.213.74]:53860 "EHLO mail-vk0-f74.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727053AbeHCB2Q (ORCPT ); Thu, 2 Aug 2018 21:28:16 -0400 Received: by mail-vk0-f74.google.com with SMTP id x78-v6so1485068vkd.20 for ; Thu, 02 Aug 2018 16:34:50 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20161025; h=date:in-reply-to:message-id:mime-version:references:subject:from:to :cc; bh=cjcAjkHyx6yluIThz26rPabJCHO2y1elV1cxyCNoXlk=; b=MbyN3Fvs4NEw5O1chlvQWkKQg2xH7VLrEH6czRCLnBFC0D20H9ezjzZXZHDWgJyFcb 5aMCs4phnsVfPitXwJS1hcGNzNYkOsE/DDSc4vT7bJzpHnCvCVOGICd0lPqAhmuyuPf3 RjS4S9LSnogRuR56dwMmZKbJ9EgIqr7n4g+ZC88SKfAjQ6a7603eqBKY4BrkZ69ZZErl e73jDKypr6X/WfsC04iZVUwz2BWFaQ8ksONsTe1Sh3LpOWw339Z5AVXDLd34BN93vPxi QezHHFZVpM4z6QbFPDCXbXY0S7I3QQnkuo/APdISmKZp7Wutq1uMTFKZgqMiRXseFDpt QbCg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:in-reply-to:message-id:mime-version :references:subject:from:to:cc; bh=cjcAjkHyx6yluIThz26rPabJCHO2y1elV1cxyCNoXlk=; b=RMWY1IXbmaQ8XXUCcqUpRliVJs1MSywYdzV6bPygMSCqVRJHgQyvK4Qr8/VQRK3bHb OPEtzPQhgIs5g5Z+BcaQx9T52jXN04UA6hgcm1H2gcq1/fmnzB1Tpv0T9uLIolB7+fBy dIP6AJM5PQTBRJt0X66o1BcuoasNlzEJ40+eDldLi2N2tm4Pd577bUrg01WY2DkoOfht EVT4xi0oZKCC9tBPOh+JMF52BQ18/hsGXsFjbzRUrb1k+VHqC85oP26vP16KzuBK42ip YDqxzOtjRLoFj9YTF+SWdXncLL9egTe0UNzRJRUj4p+v382KI4fzLZRZC+TW1izxZKCR 5BFg== X-Gm-Message-State: AOUpUlHIhWuzwIlypM0NY2UEuQ1Hgo8fXBKCEzhVYnslc+pL9JXujKX3 yVhN0+TFCNjiqBa6WiGDx4csfdF9 X-Google-Smtp-Source: AAOMgpfoQAKaWPdFB4fFKF2Mgo+VpUjPaKQ8/u23Sb6Mo0UBPRgbK07j0f7SHrji/L8IOY9hP/pbqO7q X-Received: by 2002:a9f:2926:: with SMTP id t35-v6mr2231571uat.109.1533252890363; Thu, 02 Aug 2018 16:34:50 -0700 (PDT) Date: Thu, 2 Aug 2018 23:34:39 +0000 In-Reply-To: <20180802233439.51643-1-posk@google.com> Message-Id: <20180802233439.51643-4-posk@google.com> Mime-Version: 1.0 References: <20180802233439.51643-1-posk@google.com> X-Mailer: git-send-email 2.18.0.597.ga71716f1ad-goog Subject: [PATCH v2 net-next 3/3] ip: use rb trees for IP frag queue. From: Peter Oskolkov To: David Miller , netdev@vger.kernel.org Cc: Eric Dumazet , Florian Westphal , Peter Oskolkov Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org Similar to TCP OOO RX queue, it makes sense to use rb trees to store IP fragments, so that OOO fragments are inserted faster. Tested: - a follow-up patch contains a rather comprehensive ip defrag self-test (functional) - ran neper `udp_stream -c -H -F 100 -l 300 -T 20`: netstat --statistics Ip: 282078937 total packets received 0 forwarded 0 incoming packets discarded 946760 incoming packets delivered 18743456 requests sent out 101 fragments dropped after timeout 282077129 reassemblies required 944952 packets reassembled ok 262734239 packet reassembles failed (The numbers/stats above are somewhat better re: reassemblies vs a kernel without this patchset. More comprehensive performance testing TBD). Reported-by: Jann Horn Reported-by: Juha-Matti Tilli Suggested-by: Eric Dumazet Signed-off-by: Peter Oskolkov Signed-off-by: Eric Dumazet Cc: Florian Westphal --- include/linux/skbuff.h | 9 +- include/net/inet_frag.h | 3 +- net/ipv4/inet_fragment.c | 16 ++- net/ipv4/ip_fragment.c | 182 +++++++++++++----------- net/ipv6/netfilter/nf_conntrack_reasm.c | 1 + net/ipv6/reassembly.c | 1 + 6 files changed, 121 insertions(+), 91 deletions(-) diff --git a/include/linux/skbuff.h b/include/linux/skbuff.h index 47848367c816..7ebdf158a795 100644 --- a/include/linux/skbuff.h +++ b/include/linux/skbuff.h @@ -676,13 +676,16 @@ struct sk_buff { * UDP receive path is one user. */ unsigned long dev_scratch; - int ip_defrag_offset; }; }; - struct rb_node rbnode; /* used in netem & tcp stack */ + struct rb_node rbnode; /* used in netem, ip4 defrag, and tcp stack */ struct list_head list; }; - struct sock *sk; + + union { + struct sock *sk; + int ip_defrag_offset; + }; union { ktime_t tstamp; diff --git a/include/net/inet_frag.h b/include/net/inet_frag.h index f4272a29dc44..b86d14528188 100644 --- a/include/net/inet_frag.h +++ b/include/net/inet_frag.h @@ -75,7 +75,8 @@ struct inet_frag_queue { struct timer_list timer; spinlock_t lock; refcount_t refcnt; - struct sk_buff *fragments; + struct sk_buff *fragments; /* Used in IPv6. */ + struct rb_root rb_fragments; /* Used in IPv4. */ struct sk_buff *fragments_tail; ktime_t stamp; int len; diff --git a/net/ipv4/inet_fragment.c b/net/ipv4/inet_fragment.c index ccd140e4082d..6d258a5669e7 100644 --- a/net/ipv4/inet_fragment.c +++ b/net/ipv4/inet_fragment.c @@ -137,12 +137,16 @@ void inet_frag_destroy(struct inet_frag_queue *q) fp = q->fragments; nf = q->net; f = nf->f; - while (fp) { - struct sk_buff *xp = fp->next; - - sum_truesize += fp->truesize; - kfree_skb(fp); - fp = xp; + if (fp) { + do { + struct sk_buff *xp = fp->next; + + sum_truesize += fp->truesize; + kfree_skb(fp); + fp = xp; + } while (fp); + } else { + sum_truesize = skb_rbtree_purge(&q->rb_fragments); } sum = sum_truesize + f->qsize; diff --git a/net/ipv4/ip_fragment.c b/net/ipv4/ip_fragment.c index 960bf5eab59f..ffbf9135fd71 100644 --- a/net/ipv4/ip_fragment.c +++ b/net/ipv4/ip_fragment.c @@ -136,7 +136,7 @@ static void ip_expire(struct timer_list *t) { struct inet_frag_queue *frag = from_timer(frag, t, timer); const struct iphdr *iph; - struct sk_buff *head; + struct sk_buff *head = NULL; struct net *net; struct ipq *qp; int err; @@ -152,14 +152,31 @@ static void ip_expire(struct timer_list *t) ipq_kill(qp); __IP_INC_STATS(net, IPSTATS_MIB_REASMFAILS); - - head = qp->q.fragments; - __IP_INC_STATS(net, IPSTATS_MIB_REASMTIMEOUT); - if (!(qp->q.flags & INET_FRAG_FIRST_IN) || !head) + if (!qp->q.flags & INET_FRAG_FIRST_IN) goto out; + /* sk_buff::dev and sk_buff::rbnode are unionized. So we + * pull the head out of the tree in order to be able to + * deal with head->dev. + */ + if (qp->q.fragments) { + head = qp->q.fragments; + qp->q.fragments = head->next; + } else { + head = skb_rb_first(&qp->q.rb_fragments); + if (!head) + goto out; + rb_erase(&head->rbnode, &qp->q.rb_fragments); + memset(&head->rbnode, 0, sizeof(head->rbnode)); + barrier(); + } + if (head == qp->q.fragments_tail) + qp->q.fragments_tail = NULL; + + sub_frag_mem_limit(qp->q.net, head->truesize); + head->dev = dev_get_by_index_rcu(net, qp->iif); if (!head->dev) goto out; @@ -179,16 +196,16 @@ static void ip_expire(struct timer_list *t) (skb_rtable(head)->rt_type != RTN_LOCAL)) goto out; - skb_get(head); spin_unlock(&qp->q.lock); icmp_send(head, ICMP_TIME_EXCEEDED, ICMP_EXC_FRAGTIME, 0); - kfree_skb(head); goto out_rcu_unlock; out: spin_unlock(&qp->q.lock); out_rcu_unlock: rcu_read_unlock(); + if (head) + kfree_skb(head); ipq_put(qp); } @@ -231,7 +248,7 @@ static int ip_frag_too_far(struct ipq *qp) end = atomic_inc_return(&peer->rid); qp->rid = end; - rc = qp->q.fragments && (end - start) > max; + rc = qp->q.fragments_tail && (end - start) > max; if (rc) { struct net *net; @@ -245,7 +262,6 @@ static int ip_frag_too_far(struct ipq *qp) static int ip_frag_reinit(struct ipq *qp) { - struct sk_buff *fp; unsigned int sum_truesize = 0; if (!mod_timer(&qp->q.timer, jiffies + qp->q.net->timeout)) { @@ -253,20 +269,14 @@ static int ip_frag_reinit(struct ipq *qp) return -ETIMEDOUT; } - fp = qp->q.fragments; - do { - struct sk_buff *xp = fp->next; - - sum_truesize += fp->truesize; - kfree_skb(fp); - fp = xp; - } while (fp); + sum_truesize = skb_rbtree_purge(&qp->q.rb_fragments); sub_frag_mem_limit(qp->q.net, sum_truesize); qp->q.flags = 0; qp->q.len = 0; qp->q.meat = 0; qp->q.fragments = NULL; + qp->q.rb_fragments = RB_ROOT; qp->q.fragments_tail = NULL; qp->iif = 0; qp->ecn = 0; @@ -278,7 +288,8 @@ static int ip_frag_reinit(struct ipq *qp) static int ip_frag_queue(struct ipq *qp, struct sk_buff *skb) { struct net *net = container_of(qp->q.net, struct net, ipv4.frags); - struct sk_buff *prev, *next; + struct rb_node **rbn, *parent; + struct sk_buff *skb1; struct net_device *dev; unsigned int fragsize; int flags, offset; @@ -341,58 +352,58 @@ static int ip_frag_queue(struct ipq *qp, struct sk_buff *skb) if (err) goto err; - /* Find out which fragments are in front and at the back of us - * in the chain of fragments so far. We must know where to put - * this fragment, right? - */ - prev = qp->q.fragments_tail; - if (!prev || prev->ip_defrag_offset < offset) { - next = NULL; - goto found; - } - prev = NULL; - for (next = qp->q.fragments; next != NULL; next = next->next) { - if (next->ip_defrag_offset >= offset) - break; /* bingo! */ - prev = next; - } + /* Note : skb->rbnode and skb->dev share the same location. */ + dev = skb->dev; + /* Makes sure compiler wont do silly aliasing games */ + barrier(); -found: /* RFC5722, Section 4, amended by Errata ID : 3089 * When reassembling an IPv6 datagram, if * one or more its constituent fragments is determined to be an * overlapping fragment, the entire datagram (and any constituent * fragments) MUST be silently discarded. * - * We do the same here for IPv4. + * We do the same here for IPv4 (and increment an snmp counter). */ - /* Is there an overlap with the previous fragment? */ - if (prev && - (prev->ip_defrag_offset + prev->len) > offset) - goto discard_qp; - - /* Is there an overlap with the next fragment? */ - if (next && next->ip_defrag_offset < end) - goto discard_qp; + /* Find out where to put this fragment. */ + skb1 = qp->q.fragments_tail; + if (!skb1) { + /* This is the first fragment we've received. */ + rb_link_node(&skb->rbnode, NULL, &qp->q.rb_fragments.rb_node); + qp->q.fragments_tail = skb; + } else if ((skb1->ip_defrag_offset + skb1->len) < end) { + /* This is the common/special case: skb goes to the end. */ + /* Detect and discard overlaps. */ + if (offset < (skb1->ip_defrag_offset + skb1->len)) + goto discard_qp; + /* Insert after skb1. */ + rb_link_node(&skb->rbnode, &skb1->rbnode, &skb1->rbnode.rb_right); + qp->q.fragments_tail = skb; + } else { + /* Binary search. Note that skb can become the first fragment, but + * not the last (covered above). */ + rbn = &qp->q.rb_fragments.rb_node; + do { + parent = *rbn; + skb1 = rb_to_skb(parent); + if (end <= skb1->ip_defrag_offset) + rbn = &parent->rb_left; + else if (offset >= skb1->ip_defrag_offset + skb1->len) + rbn = &parent->rb_right; + else /* Found an overlap with skb1. */ + goto discard_qp; + } while (*rbn); + /* Here we have parent properly set, and rbn pointing to + * one of its NULL left/right children. Insert skb. */ + rb_link_node(&skb->rbnode, parent, rbn); + } + rb_insert_color(&skb->rbnode, &qp->q.rb_fragments); - /* Note : skb->ip_defrag_offset and skb->dev share the same location */ - dev = skb->dev; if (dev) qp->iif = dev->ifindex; - /* Makes sure compiler wont do silly aliasing games */ - barrier(); skb->ip_defrag_offset = offset; - /* Insert this fragment in the chain of fragments. */ - skb->next = next; - if (!next) - qp->q.fragments_tail = skb; - if (prev) - prev->next = skb; - else - qp->q.fragments = skb; - qp->q.stamp = skb->tstamp; qp->q.meat += skb->len; qp->ecn |= ecn; @@ -414,7 +425,7 @@ static int ip_frag_queue(struct ipq *qp, struct sk_buff *skb) unsigned long orefdst = skb->_skb_refdst; skb->_skb_refdst = 0UL; - err = ip_frag_reasm(qp, prev, dev); + err = ip_frag_reasm(qp, skb, dev); skb->_skb_refdst = orefdst; return err; } @@ -431,15 +442,15 @@ static int ip_frag_queue(struct ipq *qp, struct sk_buff *skb) return err; } - /* Build a new IP datagram from all its fragments. */ - -static int ip_frag_reasm(struct ipq *qp, struct sk_buff *prev, +static int ip_frag_reasm(struct ipq *qp, struct sk_buff *skb, struct net_device *dev) { struct net *net = container_of(qp->q.net, struct net, ipv4.frags); struct iphdr *iph; - struct sk_buff *fp, *head = qp->q.fragments; + struct sk_buff *fp, *head = skb_rb_first(&qp->q.rb_fragments); + struct sk_buff **nextp; /* To build frag_list. */ + struct rb_node *rbn; int len; int ihlen; int err; @@ -453,25 +464,20 @@ static int ip_frag_reasm(struct ipq *qp, struct sk_buff *prev, goto out_fail; } /* Make the one we just received the head. */ - if (prev) { - head = prev->next; - fp = skb_clone(head, GFP_ATOMIC); + if (head != skb) { + fp = skb_clone(skb, GFP_ATOMIC); if (!fp) goto out_nomem; - - fp->next = head->next; - if (!fp->next) + rb_replace_node(&skb->rbnode, &fp->rbnode, &qp->q.rb_fragments); + if (qp->q.fragments_tail == skb) qp->q.fragments_tail = fp; - prev->next = fp; - - skb_morph(head, qp->q.fragments); - head->next = qp->q.fragments->next; - - consume_skb(qp->q.fragments); - qp->q.fragments = head; + skb_morph(skb, head); + rb_replace_node(&head->rbnode, &skb->rbnode, + &qp->q.rb_fragments); + consume_skb(head); + head = skb; } - WARN_ON(!head); WARN_ON(head->ip_defrag_offset != 0); /* Allocate a new buffer for the datagram. */ @@ -496,24 +502,35 @@ static int ip_frag_reasm(struct ipq *qp, struct sk_buff *prev, clone = alloc_skb(0, GFP_ATOMIC); if (!clone) goto out_nomem; - clone->next = head->next; - head->next = clone; skb_shinfo(clone)->frag_list = skb_shinfo(head)->frag_list; skb_frag_list_init(head); for (i = 0; i < skb_shinfo(head)->nr_frags; i++) plen += skb_frag_size(&skb_shinfo(head)->frags[i]); clone->len = clone->data_len = head->data_len - plen; - head->data_len -= clone->len; - head->len -= clone->len; + skb->truesize += clone->truesize; clone->csum = 0; clone->ip_summed = head->ip_summed; add_frag_mem_limit(qp->q.net, clone->truesize); + skb_shinfo(head)->frag_list = clone; + nextp = &clone->next; + } else { + nextp = &skb_shinfo(head)->frag_list; } - skb_shinfo(head)->frag_list = head->next; skb_push(head, head->data - skb_network_header(head)); - for (fp=head->next; fp; fp = fp->next) { + /* Traverse the tree in order, to build frag_list. */ + rbn = rb_next(&head->rbnode); + rb_erase(&head->rbnode, &qp->q.rb_fragments); + while (rbn) { + struct rb_node *rbnext = rb_next(rbn); + fp = rb_to_skb(rbn); + rb_erase(rbn, &qp->q.rb_fragments); + rbn = rbnext; + *nextp = fp; + nextp = &fp->next; + fp->prev = NULL; + memset(&fp->rbnode, 0, sizeof(fp->rbnode)); head->data_len += fp->len; head->len += fp->len; if (head->ip_summed != fp->ip_summed) @@ -524,7 +541,9 @@ static int ip_frag_reasm(struct ipq *qp, struct sk_buff *prev, } sub_frag_mem_limit(qp->q.net, head->truesize); + *nextp = NULL; head->next = NULL; + head->prev = NULL; head->dev = dev; head->tstamp = qp->q.stamp; IPCB(head)->frag_max_size = max(qp->max_df_size, qp->q.max_size); @@ -552,6 +571,7 @@ static int ip_frag_reasm(struct ipq *qp, struct sk_buff *prev, __IP_INC_STATS(net, IPSTATS_MIB_REASMOKS); qp->q.fragments = NULL; + qp->q.rb_fragments = RB_ROOT; qp->q.fragments_tail = NULL; return 0; diff --git a/net/ipv6/netfilter/nf_conntrack_reasm.c b/net/ipv6/netfilter/nf_conntrack_reasm.c index 0610bdab721c..38d69ef516d5 100644 --- a/net/ipv6/netfilter/nf_conntrack_reasm.c +++ b/net/ipv6/netfilter/nf_conntrack_reasm.c @@ -463,6 +463,7 @@ nf_ct_frag6_reasm(struct frag_queue *fq, struct sk_buff *prev, struct net_devic head->csum); fq->q.fragments = NULL; + fq->q.rb_fragments = RB_ROOT; fq->q.fragments_tail = NULL; return true; diff --git a/net/ipv6/reassembly.c b/net/ipv6/reassembly.c index 6edd2ac8ae4b..b4e558ab39fa 100644 --- a/net/ipv6/reassembly.c +++ b/net/ipv6/reassembly.c @@ -405,6 +405,7 @@ static int ip6_frag_reasm(struct frag_queue *fq, struct sk_buff *prev, __IP6_INC_STATS(net, __in6_dev_get(dev), IPSTATS_MIB_REASMOKS); rcu_read_unlock(); fq->q.fragments = NULL; + fq->q.rb_fragments = RB_ROOT; fq->q.fragments_tail = NULL; return 1;