Htree directory index for Ext2, updated

Htree directory index for Ext2, updated

[Daniel Phillips]

An updated version of the htree directory index patch for Ext2 is available
at:

   nl.linux.org/~phillips/htree/htree-2.4.18-2

This update fixes a corruption-causing bug.

After learning to my horror that gnu patch will, if a patch was made to be 
applied with option -p0, sometimes apply patches to your 'clean' tree (the 
one with the ---'s) instead of the target tree (the one with the +++'s) I 
decided to switch to -p1, and that is how this patch is to be applied.

Changes:

  - Off-by-one bug in second level index block splitting identified
    by Ted using his prototype Htree extensions to e2fsck, isolated using
    same, and fixed by Chris Li (Ted, Chris)

  - Added a missing static, allowing htree to be applied to
    Ext2 and Ext3 simultaneously, withload symbol conflicts (Me)

News:

  - Htree has been ported to Ext3 by Chris Li, patch to be available soon.
    (Chris, do you need a place to post it?)

In progress:

  - Port to Ext3 (Chris)
  - e2fsprogs extensions (Ted)
  - Tuning/testing/finalizing of hash function
  - Delete coalescing

To do:

  - Highmem support (currently buggy)
  - telldir cookie(s)
  - Hash attack resistance
  - Source cleanup
  - Port to 2.5

-- 
Daniel

Re: Htree directory index for Ext2, updated

[Albert D. Cahalan]

> After learning to my horror that gnu patch will, if a patch was made to be 
> applied with option -p0, sometimes apply patches to your 'clean' tree (the 
> one with the ---'s) instead of the target tree (the one with the +++'s) I 
> decided to switch to -p1, and that is how this patch is to be applied.

The worst thing is that gnu patch will make
this decision on a per-file basis, so you
can't then back out the changes with -R.

Do like this:

diff -Naurd old new

IMPORTANT: the directory names should have
the same number of characters in them.
Do not try something like:

diff -Naurd bad idea
diff -Naurd doomed 2fail

Don't use "linux" for a name. Don't use
anything Linus might use. Pick your own
equal-length directory names, and don't
distribute tarballs containing them.
This prevents source-destroying disasters.

Then to apply:

(cd my-linux && bzip2 -dc ../foo.bz2 | patch -p1 -s -E)

Re: Htree directory index for Ext2, updated

[Daniel Phillips]

On Friday 17 May 2002 06:22, Albert D. Cahalan wrote:
> > After learning to my horror that gnu patch will, if a patch was made to be 
> > applied with option -p0, sometimes apply patches to your 'clean' tree (the 
> > one with the ---'s) instead of the target tree (the one with the +++'s) I 
> > decided to switch to -p1, and that is how this patch is to be applied.
> 
> The worst thing is that gnu patch will make
> this decision on a per-file basis, so you
> can't then back out the changes with -R.
> 
> Do like this:
> 
> diff -Naurd old new
> 
> IMPORTANT: the directory names should have
> the same number of characters in them.

Why is that?

> Do not try something like:
> 
> diff -Naurd bad idea
> diff -Naurd doomed 2fail
> 
> Don't use "linux" for a name. Don't use
> anything Linus might use. Pick your own
> equal-length directory names, and don't
> distribute tarballs containing them.
> This prevents source-destroying disasters.

I think you're saying that patch is broken by design.  And what's the standard 
argument for not fixing it?

-- 
Daniel

Re: Htree directory index for Ext2, updated

[Albert D. Cahalan]

Daniel Phillips writes:
> On Friday 17 May 2002 06:22, Albert D. Cahalan wrote:
>> Daniel Phillips writes:

>>> After learning to my horror that gnu patch will,
>>> if a patch was made to be applied with option -p0,
>>> sometimes apply patches to your 'clean' tree
>>> (the one with the ---'s) instead of the target
>>> tree (the one with the +++'s) I decided to switch
>>> to -p1, and that is how this patch is to be applied.
>>
>> The worst thing is that gnu patch will make
>> this decision on a per-file basis, so you
>> can't then back out the changes with -R.
>>
>> Do like this:
>>
>> diff -Naurd old new
>>
>> IMPORTANT: the directory names should have
>> the same number of characters in them.
>
> Why is that?

File selection uses a really crazy algorithm.
If you set POSIXLY_CORRECT in your environment,
it gets a bit better, but you don't get the
rejection files then. As a patch creator, you
should not assume that POSIXLY_CORRECT is
set or not.

----------- the insanity -------------

Ignoring RCS/ClearCase/SCCS, the algorithm is
claimed to be:

patch takes an ordered list of candidate file names
...
old, new, index   [index is from "Index:" line]
...
If some of the named files exist, patch selects
the first name if conforming to POSIX, and the
"best" [*] name otherwise.
...
If no named files exist ... some names are given,
patch is not conforming to POSIX, and the patch
appears to create a file, patch selects the "best" [*]
name requiring the creation of the fewest directories.
...
else ask the user

The "best" name:

patch first takes all the names with the fewest path
name components; of those, it then takes all the
names with the shortest basename; of those, it then
takes all the shortest names; finally, it takes the
first remaining name.

Given this complexity, do you trust the man page?
Follow my advice if you want to play it safe.

---------------------------------------

>> Do not try something like:
>>
>> diff -Naurd bad idea
>> diff -Naurd doomed 2fail
>>
>> Don't use "linux" for a name. Don't use
>> anything Linus might use. Pick your own
>> equal-length directory names, and don't
>> distribute tarballs containing them.
>> This prevents source-destroying disasters.
>
> I think you're saying that patch is broken by design.
> And what's the standard argument for not fixing it?

Half of the badness is POSIX mandated. As for
the other half... well, you should produce
patches that work with the existing tools.
Since good patches work with the existing
tools, there is no need to fix anything. :-/

Note who wrote patch. Note who wrote perl.
Any questions? (such behavior is nice for
a UI, for example a web browser URL parser,
but not for automated tools)

Re: Htree directory index for Ext2, updated

[Russell King]

On Fri, May 17, 2002 at 07:18:23AM +0200, Daniel Phillips wrote:
> I think you're saying that patch is broken by design.  And what's the
> standard argument for not fixing it?

There are a set of guidelines for generating patches given in the patch
2.5 manpage.  I would suggest people go and read them.  The section is
marked: "NOTES FOR PATCH SENDERS"

-- 
Russell King (rmk@arm.linux.org.uk)                The developer of ARM Linux
             http://www.arm.linux.org.uk/personal/aboutme.html

Re: Htree directory index for Ext2, updated

[Daniel Phillips]

On Friday 17 May 2002 09:43, Russell King wrote:
> On Fri, May 17, 2002 at 07:18:23AM +0200, Daniel Phillips wrote:
> > I think you're saying that patch is broken by design.  And what's the
> > standard argument for not fixing it?
> 
> There are a set of guidelines for generating patches given in the patch
> 2.5 manpage.  I would suggest people go and read them.  The section is
> marked: "NOTES FOR PATCH SENDERS"

I will go as far as agreeing that this is a standard argument.

-- 
Daniel

Re: Htree directory index for Ext2, updated

[Daniel Phillips]

On Friday 17 May 2002 09:36, Albert D. Cahalan wrote:
> ----------- the insanity -------------
> 
> Ignoring RCS/ClearCase/SCCS, the algorithm is
> claimed to be:
> 
> patch takes an ordered list of candidate file names
> ...
> old, new, index   [index is from "Index:" line]
> ...
> If some of the named files exist, patch selects
> the first name if conforming to POSIX,

This is amazingly stupid.  The naive user would always expect the
file prefixed with '+++' to be selected, whether or not it exists.

> and the "best" [*] name otherwise.

Which is about the only way to make the selection process even
less sensible.

> [...]
> Half of the badness is POSIX mandated. As for
> the other half... well, you should produce
> patches that work with the existing tools.

Patch is severely broken in its current form, not only for the
reasons you stated, but also because of its inability to handle
renaming in any sane way.  I want a patch --sane option.

-- 
Daniel

Re: Htree directory index for Ext2, updated

[Andreas Dilger]

On May 18, 2002  03:21 +0200, Daniel Phillips wrote:
> Patch is severely broken in its current form, not only for the
> reasons you stated, but also because of its inability to handle
> renaming in any sane way.  I want a patch --sane option.

I bet BitKeeper gets it right... ;-) ;-) ;-)

Cheers, Andreas
--
Andreas Dilger
http://www-mddsp.enel.ucalgary.ca/People/adilger/
http://sourceforge.net/projects/ext2resize/

Re: Htree directory index for Ext2, updated

[Daniel Phillips]

On Saturday 18 May 2002 07:34, Andreas Dilger wrote:
> On May 18, 2002  03:21 +0200, Daniel Phillips wrote:
> > Patch is severely broken in its current form, not only for the
> > reasons you stated, but also because of its inability to handle
> > renaming in any sane way.  I want a patch --sane option.
> 
> I bet BitKeeper gets it right... ;-) ;-) ;-)

Funny you should mention that, since Bitkeeper has embarrassed itself pretty
badly with respect to patches, so far.

  - Somebody decided to add another level on top of the linux root directory
    in their source directory.  I can't import patches into that.

  - I can apply patches to bitkeeper repository using the normal 'patch',
    but Bitkeeper gets its revenge later, as each bk edit command starts
    off by throwing away the patch.

Given the hype, I expected more.  I want a tool to save work for me, not
create new work.  I don't think I'll be using Bitkeeper as a substitute for
patch any time soon.

-- 
Daniel

Re: Htree directory index for Ext2, updated

[Kai Germaschewski]

On Sat, 18 May 2002, Daniel Phillips wrote:

>   - Somebody decided to add another level on top of the linux root directory
>     in their source directory.  I can't import patches into that.
> 
>   - I can apply patches to bitkeeper repository using the normal 'patch',
>     but Bitkeeper gets its revenge later, as each bk edit command starts
>     off by throwing away the patch.

Hmmh, that's always worked for me. Actually I always apply patches by hand
(not with bk import), and as my "patch" knows about SCCS, it automatically
checks out files as needed. After that they are in "bk edit"  status, so
another bk edit just won't do anything.

So for me, it plays just well together.

(patch 2.5.4)

--Kai

Re: Htree directory index for Ext2, updated

[Andreas Dilger]

On May 18, 2002  07:44 +0200, Daniel Phillips wrote:
> On Saturday 18 May 2002 07:34, Andreas Dilger wrote:
> > On May 18, 2002  03:21 +0200, Daniel Phillips wrote:
> > > Patch is severely broken in its current form, not only for the
> > > reasons you stated, but also because of its inability to handle
> > > renaming in any sane way.  I want a patch --sane option.
> > 
> > I bet BitKeeper gets it right... ;-) ;-) ;-)
> 
> Funny you should mention that, since Bitkeeper has embarrassed itself pretty
> badly with respect to patches, so far.
> 
>   - Somebody decided to add another level on top of the linux root directory
>     in their source directory.  I can't import patches into that.

Hmm, I'm not sure what you are referring to here.

>   - I can apply patches to bitkeeper repository using the normal 'patch',
>     but Bitkeeper gets its revenge later, as each bk edit command starts
>     off by throwing away the patch.

This is also strange, as when I use patch to apply a patch to files not
checked out, patch asks me if I should check them out in write mode
(which I do, of course).

Of course, if you are using patch to apply changes to a BK tree it isn't
really BK in the end.  What I was referring to was importing a changeset
would probably get the target files correct 100% of the time, unlike the
situation you are describing with patch.

Cheers, Andreas
--
Andreas Dilger
http://www-mddsp.enel.ucalgary.ca/People/adilger/
http://sourceforge.net/projects/ext2resize/

Re: Htree directory index for Ext2, updated

[Daniel Phillips]

On Saturday 18 May 2002 07:58, Andreas Dilger wrote:
> On May 18, 2002  07:44 +0200, Daniel Phillips wrote:
> > Funny you should mention that, since Bitkeeper has embarrassed itself pretty
> > badly with respect to patches, so far.
> > 
> >   - Somebody decided to add another level on top of the linux root directory
> >     in their source directory.  I can't import patches into that.
> 
> Hmm, I'm not sure what you are referring to here.

I cloned a repository that is arranged like:

  somedir
    |
    |--linux
    |    |
    |    The usual stuff
    |
     `---other things

Bitkeeper wants the destination for the import to be 'somedir', and cannot figure
out how to apply a patch that looks like, +++ src/include/linux/someheader.h, for
instance.

-- 
Daniel

Re: Htree directory index for Ext2, updated

[Daniel Phillips]

On Saturday 18 May 2002 07:58, Andreas Dilger wrote:
> On May 18, 2002  07:44 +0200, Daniel Phillips wrote:
> >   - I can apply patches to bitkeeper repository using the normal 'patch',
> >     but Bitkeeper gets its revenge later, as each bk edit command starts
> >     off by throwing away the patch.
> 
> This is also strange, as when I use patch to apply a patch to files not
> checked out, patch asks me if I should check them out in write mode
> (which I do, of course).
> 
> Of course, if you are using patch to apply changes to a BK tree it isn't
> really BK in the end.  What I was referring to was importing a changeset
> would probably get the target files correct 100% of the time, unlike the
> situation you are describing with patch.

The solution to this appears to be to apply the patch with -g1.  With -g0,
strange things happen, as described above.

-- 
Daniel

Re: Htree directory index for Ext2, updated

[Andreas Dilger]

On May 18, 2002  08:13 +0200, Daniel Phillips wrote:
> I cloned a repository that is arranged like:
> 
>   somedir
>     |
>     |--linux
>     |    |
>     |    The usual stuff
>     |
>      `---other things
> 
> Bitkeeper wants the destination for the import to be 'somedir', and
> cannot figure out how to apply a patch that looks like:
> +++ src/include/linux/someheader.h, for instance.

And that is bad in what way?  If you try to apply that patch from
'somedir' you expect patch/BK to have ESP to know it should apply
under 'linux'.  If 'patch' will apply such a diff, then it is just
a sign of the problems you were complaining about - that it uses
heuristics to guess which file to modify, and they are not 100% right.

Of course, if you are really talking about a patch, and not a BK
changeset, then the problem lies solely with 'patch' and 'diff'
and has nothing to do with BK at all.

Cheers, Andreas
--
Andreas Dilger
http://www-mddsp.enel.ucalgary.ca/People/adilger/
http://sourceforge.net/projects/ext2resize/

Re: Htree directory index for Ext2, updated

[Daniel Phillips]

On Saturday 18 May 2002 19:26, Andreas Dilger wrote:
> On May 18, 2002  08:13 +0200, Daniel Phillips wrote:
> > I cloned a repository that is arranged like:
> > 
> >   somedir
> >     |
> >     |--linux
> >     |    |
> >     |    The usual stuff
> >     |
> >      `---other things
> > 
> > Bitkeeper wants the destination for the import to be 'somedir', and
> > cannot figure out how to apply a patch that looks like:
> > +++ src/include/linux/someheader.h, for instance.
> 
> And that is bad in what way?

It is bad in that there is no way to import the patch into BitKeeper.

> If you try to apply that patch from
> 'somedir' you expect patch/BK to have ESP to know it should apply
> under 'linux'.  If 'patch' will apply such a diff, then it is just
> a sign of the problems you were complaining about - that it uses
> heuristics to guess which file to modify, and they are not 100% right.
> 
> Of course, if you are really talking about a patch, and not a BK
> changeset, then the problem lies solely with 'patch' and 'diff'
> and has nothing to do with BK at all.

It looks like a hole in BitKeeper.  How do you suggest I apply my
perfectly normal patch?

-- 
Daniel

Re: Htree directory index for Ext2, updated

[Andreas Dilger]

On May 22, 2002  11:43 +0200, Daniel Phillips wrote:
> On Saturday 18 May 2002 19:26, Andreas Dilger wrote:
> > On May 18, 2002  08:13 +0200, Daniel Phillips wrote:
> > > I cloned a repository that is arranged like:
> > > 
> > >   somedir
> > >     |
> > >     |--linux
> > >     |    |
> > >     |    The usual stuff
> > >     |
> > >      `---other things
> > > 
> > > Bitkeeper wants the destination for the import to be 'somedir', and
> > > cannot figure out how to apply a patch that looks like:
> > > +++ src/include/linux/someheader.h, for instance.
> > 
> > And that is bad in what way?
> 
> It is bad in that there is no way to import the patch into BitKeeper.
> 
> It looks like a hole in BitKeeper.  How do you suggest I apply my
> perfectly normal patch?

cd somedir/linux; patch -p1 < foo.diff; bk citool

Cheers, Andreas
--
Andreas Dilger
http://www-mddsp.enel.ucalgary.ca/People/adilger/
http://sourceforge.net/projects/ext2resize/

Re: Htree directory index for Ext2, updated

[Larry McVoy]

On Wed, May 22, 2002 at 04:23:54AM -0600, Andreas Dilger wrote:
> On May 22, 2002  11:43 +0200, Daniel Phillips wrote:
> > On Saturday 18 May 2002 19:26, Andreas Dilger wrote:
> > > On May 18, 2002  08:13 +0200, Daniel Phillips wrote:
> > > > I cloned a repository that is arranged like:
> > > > 
> > > >   somedir
> > > >     |
> > > >     |--linux
> > > >     |    |
> > > >     |    The usual stuff
> > > >     |
> > > >      `---other things
> > > > 
> > > > Bitkeeper wants the destination for the import to be 'somedir', and
> > > > cannot figure out how to apply a patch that looks like:
> > > > +++ src/include/linux/someheader.h, for instance.
> > > 
> > > And that is bad in what way?
> > 
> > It is bad in that there is no way to import the patch into BitKeeper.
> > 
> > It looks like a hole in BitKeeper.  How do you suggest I apply my
> > perfectly normal patch?
> 
> cd somedir/linux; patch -p1 < foo.diff; bk citool

bk import -tpatch foo.diff somedir/linux

also works, does the same thing, but handles renames.  Not needed for
simple patches but you might get in the habit of using it anyway so
the odd rename is caught.

Cheers,
-- 
---
Larry McVoy            	 lm at bitmover.com           http://www.bitmover.com/lm