From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-14.2 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,URIBL_BLOCKED,USER_AGENT_SANE_1 autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id C4490C433E0 for ; Mon, 8 Feb 2021 19:01:56 +0000 (UTC) Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.kernel.org (Postfix) with ESMTP id 45BF264E59 for ; Mon, 8 Feb 2021 19:01:56 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 45BF264E59 Authentication-Results: mail.kernel.org; dmarc=fail (p=none dis=none) header.from=gmail.com Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=owner-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix) id 78DD66B0006; Mon, 8 Feb 2021 14:01:55 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 717A56B006C; Mon, 8 Feb 2021 14:01:55 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 605CE6B006E; Mon, 8 Feb 2021 14:01:55 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0053.hostedemail.com [216.40.44.53]) by kanga.kvack.org (Postfix) with ESMTP id 47CCB6B0006 for ; Mon, 8 Feb 2021 14:01:55 -0500 (EST) Received: from smtpin01.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay04.hostedemail.com (Postfix) with ESMTP id F383168A1 for ; Mon, 8 Feb 2021 19:01:54 +0000 (UTC) X-FDA: 77796020190.01.alley70_440e5fb27601 Received: from filter.hostedemail.com (10.5.16.251.rfc1918.com [10.5.16.251]) by smtpin01.hostedemail.com (Postfix) with ESMTP id C182B100581F3 for ; Mon, 8 Feb 2021 19:01:54 +0000 (UTC) X-HE-Tag: alley70_440e5fb27601 X-Filterd-Recvd-Size: 5643 Received: from mail-lj1-f180.google.com (mail-lj1-f180.google.com [209.85.208.180]) by imf40.hostedemail.com (Postfix) with ESMTP for ; Mon, 8 Feb 2021 19:01:54 +0000 (UTC) Received: by mail-lj1-f180.google.com with SMTP id y14so18512541ljn.8 for ; Mon, 08 Feb 2021 11:01:53 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:date:to:cc:subject:message-id:references:mime-version :content-disposition:in-reply-to:user-agent; bh=8pqhdeRC3f5+oXF00/LNR4GyCgSd0C0aI5uiNvoPwIQ=; b=oNU15KazCL+KgVUExu0qk8wT3Ae19v82VIJ906txss4RN00b1Izwrm48c/DDcbFBrP gP2le+VheSKZspNNFTDLshUTqgU6qJUrxQDD0RvotT65wwg3vM3k6pQv6Wvdro6vkhzK g4uvTRLcyZrg+rTjVXEG3OQ/dP0pgj2D3cv3p0IIIz70W/vfS9glJl/H60Vs6H6sq7Nx RvnRdR3knB1Iq0rDvGZipj0ysbf1Y7cVij6u6ms+ooJg1GxJzXc/3cfEJUeXdhSh99te JyuPyHe/hThZ/U5vnHqvGxXflq0hpQV8jwmYq7TkjKthO7oxtgPex164BujoZDWedpBU lJ/A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:date:to:cc:subject:message-id:references :mime-version:content-disposition:in-reply-to:user-agent; bh=8pqhdeRC3f5+oXF00/LNR4GyCgSd0C0aI5uiNvoPwIQ=; b=J5RtqXc2yfdS5V4L+PhIeZdL2ilAI6OoKEKnN9GsVKNleGyf3BWPGyr2xaRsBO9iVM EhBSjI84A0dt8E8CmePq34tkUQggD3PdkKpKdKZElQMI6RBPf/UQETHRbRwNlYuP6Okd t08ZeCVFszm7qsOEsUX3ytZzaLL+doe8OL0JjjUhwmIV/8r9w7G/bwtVDwG+VJtmWLGA o2x9u+4y52zzgUkB9xgHTQZhXH+bQj01g+OJGOtKNRoD91vlVwCbgIUts13myBRausGw PxqWl5U62PGX5jLgj4x28j99mYI0ZTr9vQQAfjqFOwULExVeuv17i7eeClyVt7UkSkVP QRFg== X-Gm-Message-State: AOAM532cxzLNFY7FHjyYGFWXG/wpFPzDouoJh7LQrv6kA89G8N/sFneu PliJFf4+sqPNGqenLhsaaMY= X-Google-Smtp-Source: ABdhPJyVdxzMzjalyUYM8ESVucaFT3SUi9SJB1qRrWnXO/EZJDW0sDX7LqLI/sHiRfbW2x9fm0kKHg== X-Received: by 2002:a2e:81c7:: with SMTP id s7mr6786278ljg.178.1612810912524; Mon, 08 Feb 2021 11:01:52 -0800 (PST) Received: from pc638.lan (h5ef52e3d.seluork.dyn.perspektivbredband.net. [94.245.46.61]) by smtp.gmail.com with ESMTPSA id j5sm2190773lfu.139.2021.02.08.11.01.51 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 08 Feb 2021 11:01:51 -0800 (PST) From: Uladzislau Rezki X-Google-Original-From: Uladzislau Rezki Date: Mon, 8 Feb 2021 20:01:50 +0100 To: Serapheim Dimitropoulos Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, osandov@osandov.com, serapheim@delphix.com Subject: Re: [PATCH] mm/vmalloc: use rb_tree instead of list for vread() lookups Message-ID: <20210208190150.GA22808@pc638.lan> References: <20210208155303.10523-1-serapheim@delphix.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20210208155303.10523-1-serapheim@delphix.com> User-Agent: Mutt/1.10.1 (2018-07-13) X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: On Mon, Feb 08, 2021 at 03:53:03PM +0000, Serapheim Dimitropoulos wrote: > vread() has been linearly searching vmap_area_list for looking up > vmalloc areas to read from. These same areas are also tracked by > a rb_tree (vmap_area_root) which offers logarithmic lookup. > > This patch modifies vread() to use the rb_tree structure instead > of the list and the speedup for heavy /proc/kcore readers can > be pretty significant. Below are the wall clock measurements of > a Python application that leverages the drgn debugging library > to read and interpret data read from /proc/kcore. > > Before the patch: > ----- > $ time sudo sdb -e 'dbuf | head 2500 | wc' > (unsigned long)2500 > > real 0m21.128s > user 0m2.321s > sys 0m19.227s > ----- > > With the patch: > ----- > $ time sudo sdb -e 'dbuf | head 2500 | wc' > (unsigned long)2500 > > real 0m1.870s > user 0m1.628s > sys 0m0.660s > ----- > > Signed-off-by: Serapheim Dimitropoulos > --- > mm/vmalloc.c | 19 ++++++++++++------- > 1 file changed, 12 insertions(+), 7 deletions(-) > > diff --git a/mm/vmalloc.c b/mm/vmalloc.c > index 49ab9b6c001d..86343b879938 100644 > --- a/mm/vmalloc.c > +++ b/mm/vmalloc.c > @@ -2851,6 +2851,7 @@ long vread(char *buf, char *addr, unsigned long count) > { > struct vmap_area *va; > struct vm_struct *vm; > + struct rb_node *node; > char *vaddr, *buf_start = buf; > unsigned long buflen = count; > unsigned long n; > @@ -2860,17 +2861,15 @@ long vread(char *buf, char *addr, unsigned long count) > count = -(unsigned long) addr; > > spin_lock(&vmap_area_lock); > - list_for_each_entry(va, &vmap_area_list, list) { > - if (!count) > - break; > - > + va = __find_vmap_area((unsigned long)addr); > + if (!va) > + goto finished; > + while (count) { > if (!va->vm) > - continue; > + goto next_node; > > vm = va->vm; > vaddr = (char *) vm->addr; > - if (addr >= vaddr + get_vm_area_size(vm)) > - continue; > while (addr < vaddr) { > if (count == 0) > goto finished; > @@ -2889,6 +2888,12 @@ long vread(char *buf, char *addr, unsigned long count) > buf += n; > addr += n; > count -= n; > + > +next_node: > + node = rb_next(&va->rb_node); > + if (!node) > + break; > + va = rb_entry(node, struct vmap_area, rb_node); > You can also improve it. Instead of rb_next() you can directly access to a "next" element via "va->list" making it O(1) complexity. -- Vlad Rezki