From: "J. Bruce Fields" <bfields@fieldses.org>
To: Richard Weinberger <richard@nod.at>
Cc: linux-mtd@lists.infradead.org, david@sigma-star.at,
tytso@mit.edu, dedekind1@gmail.com, adrian.hunter@intel.com,
linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org,
adilger.kernel@dilger.ca, akpm@linux-foundation.org,
linux-ext4@vger.kernel.org
Subject: Re: [PATCH 3/6] ubifs: Use 64bit readdir cookies
Date: Thu, 29 Dec 2016 10:34:07 -0500 [thread overview]
Message-ID: <20161229153407.GA29149@fieldses.org> (raw)
In-Reply-To: <bf60916c-e0f2-387c-ce21-325ad8977539@nod.at>
On Thu, Dec 29, 2016 at 10:19:27AM +0100, Richard Weinberger wrote:
> Bruce,
>
> On 29.12.2016 03:58, J. Bruce Fields wrote:
> > On Thu, Dec 01, 2016 at 11:02:18PM +0100, Richard Weinberger wrote:
> >> This is the first step to support proper telldir/seekdir()
> >> in UBIFS.
> >> Let's report 64bit cookies in readdir(). The cookie is a combination
> >> of the entry key plus the double hash value.
> >
> > Would it be possible to explain what that means in a little detail, for
> > a ubifs-ignoramus?
> >
> > I'm just curious how it meets the requirements for nfs exports.
>
> Traditionally UBIFS had 32bit readdir() cookies, ctx->pos was a 32bit
> integer.
> This integer is the 32bit key out the UBIFS index tree.
>
> In ->lookup(), UBIFS computes the r5 hash of the requested file name
> which will be used as search key. Since the chance is high to face a hash
> collision in the 32bit space, UBIFS also does a string compare
> to find the correct directory entry for the given file name.
>
> For NFS, and fscrypt, UBIFS has to offer a way to lookup a directory
> entry by a given cookie without knowing the file name.
> So, UBIFS has no chance to detect or handle a hash collision.
>
> To deal with that UBIFS uses a similar trick as ext4 does, it stores
> another unique identifier of the file name which can be used as cookie.
> While ext4 stores two 32bit hash values, therefore the name double hash,
> which will be combined to a single 64bit cookie, UBIFS stores additionally
> a 32bit random number which will be generated upon directory entry creation.
> Using the 32bit hash value and the 32bit nonce it can provide a 64bit
> cookie.
>
> Lookup via cookie works like a regular lookup but instead of comparing
> strings it compares the nonce values.
>
> That way UBIFS can provide a 64bit readdir() cookie which is required for NFS3.
Sounds good. And if a matching entry isn't found (as in the case of a
concurrent unlink), what happens? The answer must be the same as for
ext4, but I've forgotten the details.... I guess it must find the next
highest cookie (thinking of the cookie as a 64-bit integer of some kind)
that exists in the directory. And that must be the same order that
readdir normally returns entries in.
--b.
next prev parent reply other threads:[~2016-12-29 15:34 UTC|newest]
Thread overview: 23+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-12-01 22:02 [PATCH 0/6] UBIFS NFS export support Richard Weinberger
2016-12-01 22:02 ` [PATCH 1/6] ext4: Move is_32bit_api() to generic code Richard Weinberger
2016-12-12 22:18 ` Richard Weinberger
2016-12-12 22:29 ` Andreas Dilger
2016-12-01 22:02 ` [PATCH 2/6] ubifs: Provide a custom llseek for directories Richard Weinberger
2016-12-01 22:02 ` [PATCH 3/6] ubifs: Use 64bit readdir cookies Richard Weinberger
2016-12-29 2:58 ` J. Bruce Fields
2016-12-29 9:19 ` Richard Weinberger
2016-12-29 15:34 ` J. Bruce Fields [this message]
2016-12-29 15:49 ` Richard Weinberger
2016-12-29 16:15 ` J. Bruce Fields
2016-12-29 16:36 ` Richard Weinberger
2016-12-29 16:59 ` J. Bruce Fields
2016-12-29 17:05 ` Richard Weinberger
2017-01-03 19:52 ` J. Bruce Fields
2016-12-01 22:02 ` [PATCH 4/6] ubifs: Maintain a parent pointer Richard Weinberger
2016-12-02 9:28 ` Marcus Folkesson
2016-12-02 10:36 ` Richard Weinberger
2016-12-01 22:02 ` [PATCH 5/6] ubifs: Implement export_operations Richard Weinberger
2016-12-01 22:02 ` [PATCH 6/6] ubifs: Wire up NFS support Richard Weinberger
2016-12-29 2:56 ` J. Bruce Fields
2016-12-29 8:48 ` Richard Weinberger
-- strict thread matches above, loose matches on Subject: below --
2017-05-21 20:20 [PATCH 0/6] UBIFS NFS export support v2 Richard Weinberger
2017-05-21 20:20 ` [PATCH 3/6] ubifs: Use 64bit readdir cookies Richard Weinberger
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20161229153407.GA29149@fieldses.org \
--to=bfields@fieldses.org \
--cc=adilger.kernel@dilger.ca \
--cc=adrian.hunter@intel.com \
--cc=akpm@linux-foundation.org \
--cc=david@sigma-star.at \
--cc=dedekind1@gmail.com \
--cc=linux-ext4@vger.kernel.org \
--cc=linux-fsdevel@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-mtd@lists.infradead.org \
--cc=richard@nod.at \
--cc=tytso@mit.edu \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).