All of lore.kernel.org
 help / color / mirror / Atom feed
From: Jan Schmidt <list.btrfs@jan-o-sch.net>
To: Jeff Mahoney <jeffm@suse.de>
Cc: Mark Fasheh <mfasheh@suse.de>,
	linux-btrfs@vger.kernel.org, Chris Mason <chris.mason@oracle.com>,
	Josef Bacik <josef@redhat.com>
Subject: Re: [PATCH 0/3] btrfs: extended inode refs
Date: Wed, 11 Apr 2012 15:11:46 +0200	[thread overview]
Message-ID: <4F858312.6090905@jan-o-sch.net> (raw)
In-Reply-To: <4F7E0AF9.7070305@suse.de>

Hi Jeff,

On 05.04.2012 23:13, Jeff Mahoney wrote:
>> As a result, we must use a different addressing scheme. Extended
>> ref keys look like:
> 
>> (inode objectid, BTRFS_INODE_EXTREF_KEY, hash)
> 
>> Where hash is defined as a function of the parent objectid and link
>> name.
> 
> I think this is effective. It will essentially have the same
> properties as a dirent but seeds the hash at objectid instead of ~1.

The objectid is already part of the key. What's the point in seeding it
to crc32 instead of ~1?

>> Right now there is a limitation for extrefs in that we're not
>> handling the possibility of a hash collision. There are two ways I
>> see we can deal with this:
> 
>> We can use a 56-bit hash and keep a generation counter in the lower
>> 8 bits of the offset field.  The cost would be an additional tree
>> search (between offset <hash>00 and <hash>FF) if we don't find
>> exactly the name we were looking for.
> 
>> An alternative solution to dealing with collisions could be to
>> emulate the dir-item insertion code - specifically something like
>> insert_with_overflow() which will stuff multiple items under one
>> key. I tend to prefer the idea of
> 
> I vote for this option.

Having more than one way to deal with hash collisions for keys doesn't
feel right. Let's find out which works best and use it in both places.
If the current insert_with_overflow style is best, please use that for
extrefs as well. If it isn't, can we replace it with something that
works for both?

> The code for insert_with_overflow is already
> well tested

I'm looking forward to seeing tests or references to the archives
discussing this. Do you have a link for me?

> and anything that will generate a collision in dirent
> insertion will generate a collision for the backref insertion. The
> dirent structure is larger than the extref structure, so there should
> always be space to match the dirent leaf so that a failure occurs
> there first.

I agree with that bit.

-Jan

  reply	other threads:[~2012-04-11 13:11 UTC|newest]

Thread overview: 27+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2012-04-05 20:09 Mark Fasheh
2012-04-05 20:09 ` [PATCH 1/3] " Mark Fasheh
2012-04-12 13:08   ` Jan Schmidt
2012-04-24 22:23     ` Mark Fasheh
2012-04-25 10:19       ` Jan Schmidt
2012-04-05 20:09 ` [PATCH 2/3] " Mark Fasheh
2012-04-12 13:08   ` Jan Schmidt
2012-05-03 23:12     ` Mark Fasheh
2012-05-04 11:39       ` David Sterba
2012-04-12 15:53   ` Jan Schmidt
2012-05-01 18:39     ` Mark Fasheh
2012-04-05 20:09 ` [PATCH 3/3] " Mark Fasheh
2012-04-12 17:59   ` Jan Schmidt
2012-04-12 18:38     ` Jan Schmidt
2012-05-08 22:57     ` Mark Fasheh
2012-05-09 17:02       ` Chris Mason
2012-05-10  8:23         ` Jan Schmidt
2012-05-10 13:35           ` Chris Mason
2012-04-05 21:13 ` [PATCH 0/3] " Jeff Mahoney
2012-04-11 13:11   ` Jan Schmidt [this message]
2012-04-11 13:29     ` Jan Schmidt
2012-04-12 16:11     ` Chris Mason
2012-04-12 16:19       ` Mark Fasheh
2012-04-06  1:24 ` Liu Bo
2012-04-06  2:12   ` Liu Bo
2012-05-21 21:46 Mark Fasheh
2012-08-08 18:55 Mark Fasheh

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=4F858312.6090905@jan-o-sch.net \
    --to=list.btrfs@jan-o-sch.net \
    --cc=chris.mason@oracle.com \
    --cc=jeffm@suse.de \
    --cc=josef@redhat.com \
    --cc=linux-btrfs@vger.kernel.org \
    --cc=mfasheh@suse.de \
    --subject='Re: [PATCH 0/3] btrfs: extended inode refs' \
    /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 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.