[PATCH 3/6] ubifs: Use 64bit readdir cookies

[J. Bruce Fields]

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.