From patchwork Wed Aug 16 02:12:17 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chris Mi X-Patchwork-Id: 9903147 X-Patchwork-Delegate: snitzer@redhat.com Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id B787E60244 for ; Wed, 16 Aug 2017 07:35:13 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id A19F628982 for ; Wed, 16 Aug 2017 07:35:13 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 9293728996; Wed, 16 Aug 2017 07:35:13 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-6.9 required=2.0 tests=BAYES_00, RCVD_IN_DNSWL_HI, UNPARSEABLE_RELAY autolearn=unavailable version=3.3.1 Received: from mx1.redhat.com (mx1.redhat.com [209.132.183.28]) (using TLSv1.2 with cipher DHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.wl.linuxfoundation.org (Postfix) with ESMTPS id 05DB628982 for ; Wed, 16 Aug 2017 07:35:12 +0000 (UTC) Received: from smtp.corp.redhat.com (int-mx04.intmail.prod.int.phx2.redhat.com [10.5.11.14]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id 8FB7F6B366; Wed, 16 Aug 2017 07:35:11 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mx1.redhat.com 8FB7F6B366 Authentication-Results: ext-mx04.extmail.prod.ext.phx2.redhat.com; dmarc=fail (p=none dis=none) header.from=mellanox.com Authentication-Results: ext-mx04.extmail.prod.ext.phx2.redhat.com; spf=fail smtp.mailfrom=dm-devel-bounces@redhat.com DKIM-Filter: OpenDKIM Filter v2.11.0 mx1.redhat.com 8FB7F6B366 Received: from colo-mx.corp.redhat.com (colo-mx02.intmail.prod.int.phx2.redhat.com [10.5.11.21]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 683177E0A6; Wed, 16 Aug 2017 07:35:11 +0000 (UTC) Received: from lists01.pubmisc.prod.ext.phx2.redhat.com (lists01.pubmisc.prod.ext.phx2.redhat.com [10.5.19.33]) by colo-mx.corp.redhat.com (Postfix) with ESMTP id 1EA813FC72; Wed, 16 Aug 2017 07:35:08 +0000 (UTC) Received: from smtp.corp.redhat.com (int-mx04.intmail.prod.int.phx2.redhat.com [10.5.11.14]) by lists01.pubmisc.prod.ext.phx2.redhat.com (8.13.8/8.13.8) with ESMTP id v7G2M1Zl006294 for ; Tue, 15 Aug 2017 22:22:01 -0400 Received: by smtp.corp.redhat.com (Postfix) id 8947C18E41; Wed, 16 Aug 2017 02:22:01 +0000 (UTC) Delivered-To: dm-devel@redhat.com Received: from mx1.redhat.com (ext-mx05.extmail.prod.ext.phx2.redhat.com [10.5.110.29]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 836B318536 for ; Wed, 16 Aug 2017 02:21:59 +0000 (UTC) Received: from mellanox.co.il (mail-il-dmz.mellanox.com [193.47.165.129]) by mx1.redhat.com (Postfix) with ESMTP id C03961291 for ; Wed, 16 Aug 2017 02:21:56 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mx1.redhat.com C03961291 Authentication-Results: ext-mx05.extmail.prod.ext.phx2.redhat.com; dmarc=pass (p=none dis=none) header.from=mellanox.com Authentication-Results: ext-mx05.extmail.prod.ext.phx2.redhat.com; spf=pass smtp.mailfrom=chrism@mellanox.com DKIM-Filter: OpenDKIM Filter v2.11.0 mx1.redhat.com C03961291 Received: from Internal Mail-Server by MTLPINE1 (envelope-from chrism@mellanox.com) with ESMTPS (AES256-SHA encrypted); 16 Aug 2017 05:15:13 +0300 Received: from bjglab-18.mtbc.labs.mlnx (bjglab-18.mtbc.labs.mlnx [10.200.0.168]) by labmailer.mlnx (8.13.8/8.13.8) with ESMTP id v7G2CRAt029514; Wed, 16 Aug 2017 05:14:18 +0300 From: Chris Mi To: netdev@vger.kernel.org Date: Tue, 15 Aug 2017 22:12:17 -0400 Message-Id: <1502849538-14284-3-git-send-email-chrism@mellanox.com> In-Reply-To: <1502849538-14284-1-git-send-email-chrism@mellanox.com> References: <1502849538-14284-1-git-send-email-chrism@mellanox.com> X-Greylist: Delayed for 00:08:21 by milter-greylist-4.5.16 (mx1.redhat.com [10.5.110.29]); Wed, 16 Aug 2017 02:21:58 +0000 (UTC) X-Greylist: inspected by milter-greylist-4.5.16 (mx1.redhat.com [10.5.110.29]); Wed, 16 Aug 2017 02:21:58 +0000 (UTC) for IP:'193.47.165.129' DOMAIN:'mail-il-dmz.mellanox.com' HELO:'mellanox.co.il' FROM:'chrism@mellanox.com' RCPT:'' X-RedHat-Spam-Score: -0.002 (RP_MATCHES_RCVD, SPF_HELO_PASS, SPF_PASS, UNPARSEABLE_RELAY) 193.47.165.129 mail-il-dmz.mellanox.com 193.47.165.129 mail-il-dmz.mellanox.com X-Scanned-By: MIMEDefang 2.78 on 10.5.110.29 X-Scanned-By: MIMEDefang 2.79 on 10.5.11.14 X-loop: dm-devel@redhat.com X-Mailman-Approved-At: Wed, 16 Aug 2017 03:35:06 -0400 Cc: lucho@ionkov.net, sergey.senozhatsky.work@gmail.com, snitzer@redhat.com, wsa@the-dreams.de, markb@mellanox.com, tom.leiming@gmail.com, zhi.a.wang@intel.com, nsekhar@ti.com, dri-devel@lists.freedesktop.org, bfields@fieldses.org, linux-sctp@vger.kernel.org, paulus@samba.org, jinpu.wang@profitbricks.com, pshelar@ovn.org, sumit.semwal@linaro.org, AlexBin.Xie@amd.com, david1.zhou@amd.com, linux-samsung-soc@vger.kernel.org, maximlevitsky@gmail.com, sudarsana.kalluru@qlogic.com, marek.vasut@gmail.com, linux-atm-general@lists.sourceforge.net, dtwlin@gmail.com, michel.daenzer@amd.com, dledford@redhat.com, tpmdd-devel@lists.sourceforge.net, stern@rowland.harvard.edu, longman@redhat.com, niranjana.vishwanathapura@intel.com, philipp.reisner@linbit.com, shli@kernel.org, linux@roeck-us.net, ohad@wizery.com, pmladek@suse.com, dick.kennedy@broadcom.com, linux-pm@vger.kernel.org, geliangtang@gmail.com, sparmaintainer@unisys.com, giometti@enneenne.com, acme@kernel.org, inki.dae@samsung.com, alex.williamson@redhat.com, rppt@linux.vnet.ibm.com, teigland@redhat.com, viro@zeniv.linux.org.uk, anna.schumaker@netapp.com, weiyj.lk@gmail.com, chrism@mellanox.com, marcos.souza.org@gmail.com, mike.marciniszyn@intel.com, elder@kernel.org, nbd-general@lists.sourceforge.net, nhorman@tuxdriver.com, nicolai.haehnle@amd.com, david.binder@unisys.com, gregkh@linuxfoundation.org, linux-usb@vger.kernel.org, anil.gurumurthy@qlogic.com, linux-kernel@vger.kernel.org, varun@chelsio.com, majd@mellanox.com, devesh.sharma@broadcom.com, sameer.wadgaonkar@unisys.com, bhaktipriya96@gmail.com, alexander.deucher@amd.com, shaun.tancheff@seagate.com, akpm@linux-foundation.org, matan@mellanox.com, jlbec@evilplan.org, kraxel@redhat.com, Jason@zx2c4.com, timothy.sell@unisys.com, airlied@linux.ie, linux-wireless@vger.kernel.org, pantelis.antoniou@konsulko.com, sudeep.dutt@intel.com, neilb@suse.com, edumazet@google.com, target-devel@vger.kernel.org, linux-i2c@vger.kernel.org, daniel.vetter@intel.com, jsarha@ti.com, osandov@fb.com, agk@redhat.com, drbd-dev@lists.linbit.com, boris.brezillon@free-electrons.com, thellstrom@vmware.com, dave@stgolabs.net, paul@paul-moore.com, leon@kernel.org, sainath.grandhi@intel.com, gustavo.padovan@collabora.co.uk, james.smart@broadcom.com, jonathanh@nvidia.com, selvin.xavier@broadcom.com, kgene@kernel.org, linux-graphics-maintainer@vmware.com, andresx7@gmail.com, 3chas3@gmail.com, airlied@redhat.com, sean.hefty@intel.com, virtualization@lists.linux-foundation.org, hal.rosenstock@gmail.com, tj@kernel.org, mszeredi@redhat.com, hannes@stressinduktion.org, felipe.balbi@linux.intel.com, pali.rohar@gmail.com, tpmdd@selhorst.net, linuxppc-dev@lists.ozlabs.org, jani.nikula@linux.intel.com, greybus-dev@lists.linaro.org, nishants@marvell.com, swise@chelsio.com, yuval.shaia@oracle.com, xiyou.wangcong@gmail.com, evan.quan@amd.com, lars.ellenberg@linbit.com, linux-arm-kernel@lists.infradead.org, dwindsor@gmail.com, linux-raid@vger.kernel.org, bryan.thompson@unisys.com, ying.xue@windriver.com, Felix.Kuehling@amd.com, oneukum@suse.com, fw@strlen.de, davem@davemloft.net, minchan@kernel.org, kyungmin.park@samsung.com, monis@mellanox.com, ebiederm@xmission.com, sre@kernel.org, don.hiatt@intel.com, leo.liu@amd.com, jens.wiklander@linaro.org, hans.westgaard.ry@oracle.com, alexander.shishkin@linux.intel.com, dennis.dalessandro@intel.com, jasowang@redhat.com, joonas.lahtinen@linux.intel.com, jiangshanlai@gmail.com, ast@kernel.org, fbarrat@linux.vnet.ibm.com, mhocko@kernel.org, alexandre.bounine@idt.com, linux-mtd@lists.infradead.org, amd-gfx@lists.freedesktop.org, cgroups@vger.kernel.org, jlayton@poochiereds.net, frowand.list@gmail.com, elena.reshetova@intel.com, f.fainelli@gmail.com, jejb@linux.vnet.ibm.com, daniel@iogearbox.net, linux-rdma@vger.kernel.org, p.shailesh@samsung.com, ath10k@lists.infradead.org, jgunthorpe@obsidianresearch.com, ccaulfie@redhat.com, stefanr@s5r6.in-berlin.de, Monk.Liu@amd.com, dgilbert@interlog.com, ira.weiny@intel.com, david.kershner@unisys.com, adobriyan@gmail.com, jon.maloy@ericsson.com, keescook@chromium.org, arnd@arndb.de, intel-gfx@lists.freedesktop.org, jhs@mojatatu.com, zhenyuw@linux.intel.com, v9fs-developer@lists.sourceforge.net, rmk+kernel@armlinux.org.uk, seanpaul@chromium.org, nab@linux-iscsi.org, tomi.valkeinen@ti.com, Jerry.Zhang@amd.com, eparis@parisplace.org, nicolas.dichtel@6wind.com, chris@chris-wilson.co.uk, mporter@kernel.crashing.org, rogerq@ti.com, linux-nfs@vger.kernel.org, martin.petersen@oracle.com, linux-ppp@vger.kernel.org, dm-devel@redhat.com, sw0312.kim@samsung.com, fujita.tomonori@lab.ntt.co.jp, iommu@lists.linux-foundation.org, roman.kapl@sysgo.com, ngupta@vflare.org, andrew.donnellan@au1.ibm.com, cyrille.pitchen@wedev4u.fr, thierry.reding@gmail.com, colin.king@canonical.com, computersforpeace@gmail.com, logang@deltatee.com, christian.koenig@amd.com, ocfs2-devel@oss.oracle.com, rlove@rlove.org, jack@suse.cz, kvm@vger.kernel.org, mst@redhat.com, peterz@infradead.org, sboyd@codeaurora.org, bigeasy@linutronix.de, trond.myklebust@primarydata.com, linux-remoteproc@vger.kernel.org, amitkarwar@gmail.com, bjorn.andersson@linaro.org, dhowells@redhat.com, linux-mm@kvack.org, ray.huang@amd.com, jiri@resnulli.us, peterhuewe@gmx.de, linux1394-devel@lists.sourceforge.net, lee.jones@linaro.org, john@johnmccutchan.com, devel@driverdev.osuosl.org, stephen@networkplumber.org, mario.kleiner.de@gmail.com, manfred@colorfullife.com, oakad@yahoo.com, linux-scsi@vger.kernel.org, mawilcox@microsoft.com, mfasheh@versity.com, richard@nod.at, joro@8bytes.org, jiangyilism@gmail.com, elfring@users.sourceforge.net, cluster-devel@redhat.com, javier@osg.samsung.com, jarkko.sakkinen@linux.intel.com, mingo@redhat.com, vdavydov.dev@gmail.com, kvalo@qca.qualcomm.com, tipc-discussion@lists.sourceforge.net, ogerlitz@mellanox.com, ishkamiel@gmail.com, devicetree@vger.kernel.org, lizefan@huawei.com, huxm@marvell.com, mchehab@kernel.org, johan@kernel.org, aditr@vmware.com, linux-block@vger.kernel.org, robh+dt@kernel.org, Kai.Makisara@kolumbus.fi, rminnich@sandia.gov, linux-tegra@vger.kernel.org, dsa@cumulusnetworks.com, intel-gvt-dev@lists.freedesktop.org, jy0922.shim@samsung.com, axboe@kernel.dk, gbhat@marvell.com, tomas.winkler@intel.com, dedekind1@gmail.com, jbacik@fb.com, jarno@ovn.org, vyasevich@gmail.com, krzk@kernel.org, syeh@vmware.com, jiri@mellanox.com, afd@ti.com, ashutosh.dixit@intel.com, yishaih@mellanox.com, rjw@rjwysocki.net, hannes@cmpxchg.org, Bart.VanAssche@sandisk.com, johannes@sipsolutions.net, dwmw2@infradead.org, dasaratharaman.chandramouli@intel.com Subject: [dm-devel] [patch net-next 2/3] net/sched: Change cls_flower to use IDR X-BeenThere: dm-devel@redhat.com X-Mailman-Version: 2.1.12 Precedence: junk List-Id: device-mapper development List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Sender: dm-devel-bounces@redhat.com Errors-To: dm-devel-bounces@redhat.com X-Scanned-By: MIMEDefang 2.79 on 10.5.11.14 X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-4.5.16 (mx1.redhat.com [10.5.110.28]); Wed, 16 Aug 2017 07:35:12 +0000 (UTC) X-Virus-Scanned: ClamAV using ClamSMTP Currently, all filters with the same priority are linked in a doubly linked list. Every filter should have a unique handle. To make the handle unique, we need to iterate the list every time to see if the handle exists or not when inserting a new filter. It is time-consuming. For example, it takes about 5m3.169s to insert 64K rules. This patch changes cls_flower to use IDR. With this patch, it takes about 0m1.127s to insert 64K rules. The improvement is huge. But please note that in this testing, all filters share the same action. If every filter has a unique action, that is another bottleneck. Follow-up patch in this patchset addresses that. Signed-off-by: Chris Mi Signed-off-by: Jiri Pirko --- net/sched/cls_flower.c | 55 +++++++++++++++++++++----------------------------- 1 file changed, 23 insertions(+), 32 deletions(-) diff --git a/net/sched/cls_flower.c b/net/sched/cls_flower.c index 052e902..071f0ef 100644 --- a/net/sched/cls_flower.c +++ b/net/sched/cls_flower.c @@ -68,7 +68,6 @@ struct cls_fl_head { struct rhashtable ht; struct fl_flow_mask mask; struct flow_dissector dissector; - u32 hgen; bool mask_assigned; struct list_head filters; struct rhashtable_params ht_params; @@ -76,6 +75,7 @@ struct cls_fl_head { struct work_struct work; struct rcu_head rcu; }; + struct idr handle_idr; }; struct cls_fl_filter { @@ -210,6 +210,7 @@ static int fl_init(struct tcf_proto *tp) INIT_LIST_HEAD_RCU(&head->filters); rcu_assign_pointer(tp->root, head); + idr_init(&head->handle_idr); return 0; } @@ -295,6 +296,9 @@ static void fl_hw_update_stats(struct tcf_proto *tp, struct cls_fl_filter *f) static void __fl_delete(struct tcf_proto *tp, struct cls_fl_filter *f) { + struct cls_fl_head *head = rtnl_dereference(tp->root); + + idr_remove(&head->handle_idr, f->handle); list_del_rcu(&f->list); if (!tc_skip_hw(f->flags)) fl_hw_destroy_filter(tp, f); @@ -327,6 +331,7 @@ static void fl_destroy(struct tcf_proto *tp) list_for_each_entry_safe(f, next, &head->filters, list) __fl_delete(tp, f); + idr_destroy(&head->handle_idr); __module_get(THIS_MODULE); call_rcu(&head->rcu, fl_destroy_rcu); @@ -335,12 +340,8 @@ static void fl_destroy(struct tcf_proto *tp) static void *fl_get(struct tcf_proto *tp, u32 handle) { struct cls_fl_head *head = rtnl_dereference(tp->root); - struct cls_fl_filter *f; - list_for_each_entry(f, &head->filters, list) - if (f->handle == handle) - return f; - return NULL; + return idr_find(&head->handle_idr, handle); } static const struct nla_policy fl_policy[TCA_FLOWER_MAX + 1] = { @@ -859,27 +860,6 @@ static int fl_set_parms(struct net *net, struct tcf_proto *tp, return 0; } -static u32 fl_grab_new_handle(struct tcf_proto *tp, - struct cls_fl_head *head) -{ - unsigned int i = 0x80000000; - u32 handle; - - do { - if (++head->hgen == 0x7FFFFFFF) - head->hgen = 1; - } while (--i > 0 && fl_get(tp, head->hgen)); - - if (unlikely(i == 0)) { - pr_err("Insufficient number of handles\n"); - handle = 0; - } else { - handle = head->hgen; - } - - return handle; -} - static int fl_change(struct net *net, struct sk_buff *in_skb, struct tcf_proto *tp, unsigned long base, u32 handle, struct nlattr **tca, @@ -890,6 +870,7 @@ static int fl_change(struct net *net, struct sk_buff *in_skb, struct cls_fl_filter *fnew; struct nlattr **tb; struct fl_flow_mask mask = {}; + unsigned long idr_index; int err; if (!tca[TCA_OPTIONS]) @@ -920,13 +901,21 @@ static int fl_change(struct net *net, struct sk_buff *in_skb, goto errout; if (!handle) { - handle = fl_grab_new_handle(tp, head); - if (!handle) { - err = -EINVAL; + err = idr_alloc(&head->handle_idr, fnew, &idr_index, + 1, 0x80000000, GFP_KERNEL); + if (err) goto errout; - } + fnew->handle = idr_index; + } + + /* user specifies a handle and it doesn't exist */ + if (handle && !fold) { + err = idr_alloc(&head->handle_idr, fnew, &idr_index, + handle, handle + 1, GFP_KERNEL); + if (err) + goto errout; + fnew->handle = idr_index; } - fnew->handle = handle; if (tb[TCA_FLOWER_FLAGS]) { fnew->flags = nla_get_u32(tb[TCA_FLOWER_FLAGS]); @@ -980,6 +969,8 @@ static int fl_change(struct net *net, struct sk_buff *in_skb, *arg = fnew; if (fold) { + fnew->handle = handle; + idr_replace(&head->handle_idr, fnew, fnew->handle); list_replace_rcu(&fold->list, &fnew->list); tcf_unbind_filter(tp, &fold->res); call_rcu(&fold->rcu, fl_destroy_filter);