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: 28+ 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 ` 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: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
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
2017-04-28 8:31 ` Hyunchul Lee
2017-04-28 9:09 ` 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 an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.