linux-kernel - Re: [RFC PATCH 0/7] mm: Get rid of vmalloc_sync

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20200511160822.GX16070@bombadil.infradead.org>
Date:   Mon, 11 May 2020 09:08:22 -0700
From:   Matthew Wilcox <willy@...radead.org>
To:     Peter Zijlstra <peterz@...radead.org>
Cc:     Joerg Roedel <jroedel@...e.de>, Joerg Roedel <joro@...tes.org>,
        x86@...nel.org, hpa@...or.com,
        Dave Hansen <dave.hansen@...ux.intel.com>,
        Andy Lutomirski <luto@...nel.org>, rjw@...ysocki.net,
        Arnd Bergmann <arnd@...db.de>,
        Andrew Morton <akpm@...ux-foundation.org>,
        Steven Rostedt <rostedt@...dmis.org>,
        Vlastimil Babka <vbabka@...e.cz>,
        Michal Hocko <mhocko@...nel.org>, linux-kernel@...r.kernel.org,
        linux-acpi@...r.kernel.org, linux-arch@...r.kernel.org,
        linux-mm@...ck.org
Subject: Re: [RFC PATCH 0/7] mm: Get rid of vmalloc_sync_(un)mappings()

On Mon, May 11, 2020 at 08:52:04AM -0700, Matthew Wilcox wrote:
> On Mon, May 11, 2020 at 09:31:34AM +0200, Peter Zijlstra wrote:
> > On Sat, May 09, 2020 at 06:11:57PM -0700, Matthew Wilcox wrote:
> > > Iterating an XArray (whether the entire thing
> > > or with marks) is RCU-safe and faster than iterating a linked list,
> > > so this should solve the problem?
> > 
> > It can hardly be faster if you want all elements -- which is I think the
> > case here. We only call into this if we change an entry, and then we
> > need to propagate that change to all.
> 
> Of course it can be faster.  Iterating an array is faster than iterating
> a linked list because caches.  While an XArray is a segmented array
> (so slower than a plain array), it's plainly going to be faster than
> iterating a linked list.

Quantifying this:

$ ./array-vs-list 
walked sequential array in 0.002039s
walked sequential list in 0.002807s
walked sequential array in 0.002017s
walked shuffled list in 0.102367s
walked shuffled array in 0.012114s

Attached is the source code; above results on a Kaby Lake with
CFLAGS="-O2 -W -Wall -g".

View attachment "array-vs-list.c" of type "text/plain" (3931 bytes)