linux-kernel - Re: NVFS XFS metadata (was: [PATCH] pmem: export the symbols __copy_user_flushcache and __copy_from_user

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 for Android: free password hash cracker in your pocket

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

Message-ID: <alpine.LRH.2.02.2009220831170.20550@file01.intranet.prod.int.rdu2.redhat.com>
Date:   Tue, 22 Sep 2020 08:39:11 -0400 (EDT)
From:   Mikulas Patocka <mpatocka@...hat.com>
To:     Matthew Wilcox <willy@...radead.org>
cc:     Dan Williams <dan.j.williams@...el.com>,
        Linus Torvalds <torvalds@...ux-foundation.org>,
        Alexander Viro <viro@...iv.linux.org.uk>,
        Andrew Morton <akpm@...ux-foundation.org>,
        Vishal Verma <vishal.l.verma@...el.com>,
        Dave Jiang <dave.jiang@...el.com>,
        Ira Weiny <ira.weiny@...el.com>, Jan Kara <jack@...e.cz>,
        Eric Sandeen <esandeen@...hat.com>,
        Dave Chinner <dchinner@...hat.com>,
        "Kani, Toshi" <toshi.kani@....com>,
        "Norton, Scott J" <scott.norton@....com>,
        "Tadakamadla, Rajesh (DCIG/CDI/HPS Perf)" 
        <rajesh.tadakamadla@....com>,
        Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
        linux-fsdevel <linux-fsdevel@...r.kernel.org>,
        linux-nvdimm <linux-nvdimm@...ts.01.org>
Subject: Re: NVFS XFS metadata (was: [PATCH] pmem: export the symbols
 __copy_user_flushcache and __copy_from_user_flushcache)



On Tue, 22 Sep 2020, Matthew Wilcox wrote:

> On Mon, Sep 21, 2020 at 12:20:42PM -0400, Mikulas Patocka wrote:
> > The same for directories - NVFS hashes the file name and uses radix-tree 
> > to locate a directory page where the directory entry is located. XFS 
> > b+trees would result in much more accesses than the radix-tree.
> 
> What?  Radix trees behave _horribly_ badly when indexed by a hash.
> If you have a 64-bit hash and use 8 bits per level of the tree, you have
> to traverse 8 pointers to get to your destination.  You might as well
> use a linked list!

In NVFS, radix trees are cut off - they have only as much internal levels, 
as is needed to disambiguate the directory entries.

Read this document: http://people.redhat.com/~mpatocka/nvfs/INTERNALS
the section "DIRECTORIES".

Perhaps, I should call it differently than "radix-trees", but I don't 
really know what is the official name for this data structure.

Mikulas