LKML Archive on lore.kernel.org
help / color / mirror / Atom feed
From: Jeff Layton <jlayton@redhat.com>
To: akpm@osdl.org
Cc: linux-fsdevel@vger.kernel.org, linux-kernel@vger.kernel.org
Subject: [PATCH 0/3] i_ino uniqueness: alternate approach -- hash the inodes
Date: Tue, 16 Jan 2007 13:57:38 -0500	[thread overview]
Message-ID: <200701161857.l0GIvcaA016196@dantu.rdu.redhat.com> (raw)

Since there's been no further comment on these patches, I'm going to resend
them one more time and ask Andrew to commit these to -mm. Once they're in
place there, I'll start working on and sending out follow-on patches to
clean up the other filesystems and ensure that they properly hash their
inodes.

------[snip]-----

Since Joern mentioned that he thought that hashing the inodes might be simpler
and not have a drastic performance impact, I took the liberty of whipping up
some patches that use that approach. They follow in the next set of emails.

To reiterate, the problems are:

1) on filesystems w/o permanent inode numbers, i_ino values can be
larger than 32 bits, which can cause problems for some 32 bit userspace
programs on a 64 bit kernel. We can't do anything for filesystems that have
actual >32-bit inode numbers, but on filesystems that generate i_ino
values on the fly, we should try to have them fit in 32 bits. We could
trivially fix this by making the static counters in new_inode and iunique
32 bits, but...

2) many filesystems call new_inode and assume that the i_ino values they
are given are unique. They are not guaranteed to be so, since the static
counter can wrap. This problem is exacerbated by the fix for #1.

3) after allocating a new inode, some filesystems call iunique to try to
get a unique i_ino value, but they don't actually add their inodes to
the hashtable, and so they're still not guaranteed to be unique if that
counter wraps.

This patch set takes the simpler approach of simply using iunique and
hashing the inodes afterward. Christoph H. previously mentioned that he
thought that this approach may slow down lookups for filesystems that
currently hash their inodes.

The questions are:

1) how much would this slow down lookups for these filesystems?
2) is it enough to justify adding more infrastructure to avoid it?

What might be best is to start with this approach and then only move to using
IDR or some other scheme if these extra inodes in the hashtable prove to be
problematic.

I've done some cursory testing with this patch and the overhead of hashing
and unhashing the inodes with pipefs is pretty low -- just a few seconds of
system time added on to the creation and destruction of 10 million pipes (very
similar to the overhead that the IDR approach would add).

The hard thing to measure is what effect this has on other filesystems. I'm
open to ways to try and gauge this.

Again, I've only converted pipefs as an example. If this approach is
acceptable then I'll start work on patches to convert other filesystems.

Comments and suggestions welcome...

-- Jeff


             reply	other threads:[~2007-01-16 18:57 UTC|newest]

Thread overview: 8+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2007-01-16 18:57 Jeff Layton [this message]
2007-01-24  4:46 ` Andrew Morton
2007-01-24 14:22   ` Jeff Layton
2007-01-24 15:21     ` Eric Dumazet
2007-01-24 16:57       ` Jeff Layton
  -- strict thread matches above, loose matches on Subject: below --
2007-01-08 20:46 Jeff Layton
2007-01-10 20:58 ` Eric Sandeen
2006-12-29 19:10 Jeff Layton

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=200701161857.l0GIvcaA016196@dantu.rdu.redhat.com \
    --to=jlayton@redhat.com \
    --cc=akpm@osdl.org \
    --cc=linux-fsdevel@vger.kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    --subject='Re: [PATCH 0/3] i_ino uniqueness: alternate approach -- hash the inodes' \
    /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

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).