From: "J. Bruce Fields" Subject: Re: [PATCH 1/6] statx: Add a system call to make enhanced file info available Date: Sun, 8 May 2016 22:46:17 -0400 Message-ID: <20160509024617.GA4646@fieldses.org> References: <20160429125736.23636.47874.stgit@warthog.procyon.org.uk> <20160429125743.23636.85219.stgit@warthog.procyon.org.uk> <20160504225601.GZ26977@dastard> <20160506182923.GB13350@fieldses.org> <20160509014543.GS18496@dastard> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Cc: David Howells , linux-fsdevel@vger.kernel.org, linux-afs@vger.kernel.org, linux-nfs@vger.kernel.org, samba-technical@lists.samba.org, linux-kernel@vger.kernel.org, linux-ext4@vger.kernel.org To: Dave Chinner Return-path: Content-Disposition: inline In-Reply-To: <20160509014543.GS18496@dastard> Sender: linux-kernel-owner@vger.kernel.org List-Id: linux-ext4.vger.kernel.org On Mon, May 09, 2016 at 11:45:43AM +1000, Dave Chinner wrote: > [ OT, but I'll reply anyway :P ] > > On Fri, May 06, 2016 at 02:29:23PM -0400, J. Bruce Fields wrote: > > On Thu, May 05, 2016 at 08:56:02AM +1000, Dave Chinner wrote: > > > In the latest XFS filesystem format, we randomise the generation > > > value during every inode allocation to make it hard to guess the > > > handle of adjacent inodes from an existing ino+gen pair, or even > > > from life time to life time of the same inode. > > > > The one thing I wonder about is whether that increases the probability > > of a filehandle collision (where you accidentally generate the same > > filehandle for two different files). > > Not possible - inode number is still different between the two > files. i.e. ino+gen makes the handle unique, not gen. > > > If the generation number is a 32-bit counter per inode number (is that > > actually the way filesystems work?), then it takes 2^32 reuses of the > > inode number to hit the same filehandle. > > 4 billion unlink/create operations that hit the same inode number > are going to take some time. I suspect someone will notice the load > generated by an attmept to brute force this sort of thing ;) > > > If you choose it randomly then > > you expect a collision after about 2^16 reuses. > > I'm pretty sure that a random search will need to, on average, > search half the keyspace before a match is found (i.e. 2^31 > attempts, not 2^16). Yeah, but I was wondering whether you could somehow get into the situation where clients between then are caching N distinct filehandles with the same inode number. Then a collision becomes likely around 2^16, by the usual birthday paradox rule-of-thumb. Uh, but now that I think of it that's irrelevant. At most one of those filehandles actually refers to a still-existing file. Any attempt to use the other 2^16-1 should return -ESTALE. So collisions among that set don't matter, it's only collisions involving the existing file that are interesting. So, nevermind, I can't see a practical way to hit a problem here.... --b.