Reiserfs/emacs incompatibility/bug ?

Reiserfs/emacs incompatibility/bug ?

[arthur.chereau]

Hi,

I've noted a strange behavior of emacs when used with the Reiserfs filesystem.
This doesn't seem to happen with the other filesystems, so it may be related to Reiserfs.

If you use emacs, here are how to reproduce this:

The "backup-by-copying" option tells emacs to make a backup file by copying the
original file, thus preserving the original file's metadata. Let's have the following
.emacs:
$ cat .emacs
(setq backup-by-copying t)
$

The correct bahavior is:
$ emacs test
$ ls -i test*
2971971 test
$ emacs test
$ ls -i test*
2971971 test 2971972 test~
$ emacs test
$ ls -i test*
2971971 test 2971973 test~

This is what is observed on an ext2 fs, for instance.

Now let's do the same on a reiserfs filesystem:
$ emacs test
$ ls -i test*
1505188 test
$ emacs test
$ ls -i test*
1505190 test 1505189 test~
$ emacs test
$ ls -i test*
1505191 test 1505189 test~

Here the backup file metadata are preserved, instead of the original file ones.

When not setting the backup-by-copying option, the file metadata are sometimes reset to
644, which can be annoying for scripts.
I couldn't find a way to reproduce that behavior at 100%.

This happens with the latest emacs from cvs on a reiseirfs 3 filesystem.
This never happens with an emacs-like tool like jed.

RMS doesn't think it's a bug in emacs as it works on other filesystems.

So maybe emacs handles moves/renames in way that:
- reveals a bug in reiserfs
- doesn't work well with reiserfs and emacs developpers are not aware of that

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

Faites un voeu et puis Voila ! www.voila.fr

fsck mode halfway between --fix-fixable and --rebuild-tree ?

[Matthias Urlichs]

Hi,

yesterday I had a small problem with reiserfsck --fix-fixable --
apparently two of the tree nodes were wrongly linked.

The only way to fix this, at the moment, seems to be --rebuild-tree, which
is overkill since it scans _everything_, and thus reconnected the stuff I
deleted last week back into /lost+found.  It also takes too long.  :-/

A good way to avoid this problem would be a scan mode which behaves like
--rebuild-tree, but which scans only those nodes reachable through the
existing tree instead of "everything".

Comments?

-- 
Matthias Urlichs     |     noris network AG     |     http://smurf.noris.de/

Re: Reiserfs/emacs incompatibility/bug ?

[Matthias Andree]

"arthur.chereau" <arthur.chereau@voila.fr> writes:

> If you use emacs, here are how to reproduce this:
>
> The "backup-by-copying" option tells emacs to make a backup file by copying the
> original file, thus preserving the original file's metadata. Let's have the following
> .emacs:
> $ cat .emacs
> (setq backup-by-copying t)
> $
>
> The correct bahavior is:
> $ emacs test
> $ ls -i test*
> 2971971 test
> $ emacs test
> $ ls -i test*
> 2971971 test 2971972 test~
> $ emacs test
> $ ls -i test*
> 2971971 test 2971973 test~
>
> This is what is observed on an ext2 fs, for instance.
>
> Now let's do the same on a reiserfs filesystem:
> $ emacs test
> $ ls -i test*
> 1505188 test
> $ emacs test
> $ ls -i test*
> 1505190 test 1505189 test~
> $ emacs test
> $ ls -i test*
> 1505191 test 1505189 test~
>
> Here the backup file metadata are preserved, instead of the original file ones.

Did you look at the file contents? (Modify the file and look at the SHA1
or MD5 digests.)

-- 
Matthias Andree

Re: fsck mode halfway between --fix-fixable and --rebuild-tree ?

[Oleg Drokin]

Hello!

On Sun, Sep 29, 2002 at 05:23:35PM +0200, Matthias Urlichs wrote:

> The only way to fix this, at the moment, seems to be --rebuild-tree, which
> is overkill since it scans _everything_, and thus reconnected the stuff I
> deleted last week back into /lost+found.  It also takes too long.  :-/

No, it does not behave like this. It may take long time though, anyway.

> A good way to avoid this problem would be a scan mode which behaves like
> --rebuild-tree, but which scans only those nodes reachable through the
> existing tree instead of "everything".

--rebuild-tree does exactly what you suggested this new mode should do.

In order ot get full partition scan you need to run reiserfsck with 
--rebuild-tree -S options sequence.

Bye,
    Oleg

Re: fsck mode halfway between --fix-fixable and --rebuild-tree ?

[Hans Reiser]

Oleg Drokin wrote:

>Hello!
>
>On Sun, Sep 29, 2002 at 05:23:35PM +0200, Matthias Urlichs wrote:
>
>  
>
>>The only way to fix this, at the moment, seems to be --rebuild-tree, which
>>is overkill since it scans _everything_, and thus reconnected the stuff I
>>deleted last week back into /lost+found.  It also takes too long.  :-/
>>    
>>
>
>No, it does not behave like this. It may take long time though, anyway.
>
Let's be more clear.  You must use the -S option to get it to behave in 
the way you do not want.  Don't use -S, and it does what you want it to do.

>
>  
>
>>A good way to avoid this problem would be a scan mode which behaves like
>>--rebuild-tree, but which scans only those nodes reachable through the
>>existing tree instead of "everything".
>>    
>>
>
>--rebuild-tree does exactly what you suggested this new mode should do.
>
>In order ot get full partition scan you need to run reiserfsck with 
>--rebuild-tree -S options sequence.
>
>Bye,
>    Oleg
>
>
>  
>

Re: fsck mode halfway between --fix-fixable and --rebuild-tree ?

[Oleg Drokin]

Hello!

On Mon, Sep 30, 2002 at 03:12:11PM +0400, Hans Reiser wrote:

> Let's be more clear.  You must use the -S option to get it to behave in 
> the way you do not want.  Don't use -S, and it does what you want it to do.

In fact I want to stress that -S switch is not recommended to use by any
means on real filesystems. If you are really sure you need -S switch,
do a snapshot of the partition and run reiserfsck on that snapshot just to
prevent possible data loss/data corruption.

Bye,
    Oleg

Re: fsck mode halfway between --fix-fixable and --rebuild-tree ?

[Matthias Urlichs]

Hans Reiser:
> >
> >>The only way to fix this, at the moment, seems to be --rebuild-tree, which
> >>is overkill since it scans _everything_, and thus reconnected the stuff I
> >>deleted last week back into /lost+found.  It also takes too long.  :-/
> >
> >No, it does not behave like this. It may take long time though, anyway.
> >
> Let's be more clear.  You must use the -S option to get it to behave in 
> the way you do not want.  Don't use -S, and it does what you want it to do.
> 
When I tried this, reiserfsck with -S scanned the whole disk, as expected.

Reiserfsck without -S said it would scan roughly half of my disk. That led
me to conclude that whatever it does, it doesn't just use the blocks which
are actually used for the tree at the moment.

How does reiserfsck determine which blocks contain leaf nodes, anyway?

-- 
Matthias Urlichs     |     noris network AG     |     http://smurf.noris.de/

Re: fsck mode halfway between --fix-fixable and --rebuild-tree ?

[Oleg Drokin]

Hello!

On Mon, Sep 30, 2002 at 01:17:44PM +0200, Matthias Urlichs wrote:

> When I tried this, reiserfsck with -S scanned the whole disk, as expected.
> Reiserfsck without -S said it would scan roughly half of my disk. That led

Yes. It scans all the blocks that are marked as "used" in bitmap.

> me to conclude that whatever it does, it doesn't just use the blocks which
> are actually used for the tree at the moment.

How can it know? It must find all the lost blocks too.

> How does reiserfsck determine which blocks contain leaf nodes, anyway?

If it finds tree node header in some block, it thinks this is a tree node
and adds it into the tree.

Bye,
    Oleg

Re: fsck mode halfway between --fix-fixable and --rebuild-tree ?

[Vitaly Fertman]

On Monday 30 September 2002 15:17, Matthias Urlichs wrote:
> Hans Reiser:
> > >>The only way to fix this, at the moment, seems to be --rebuild-tree,
> > >> which is overkill since it scans _everything_, and thus reconnected
> > >> the stuff I deleted last week back into /lost+found.  It also takes
> > >> too long.  :-/
> > >
> > >No, it does not behave like this. It may take long time though, anyway.
> >
> > Let's be more clear.  You must use the -S option to get it to behave in
> > the way you do not want.  Don't use -S, and it does what you want it to
> > do.
>
> When I tried this, reiserfsck with -S scanned the whole disk, as expected.
>
> Reiserfsck without -S said it would scan roughly half of my disk. That led
> me to conclude that whatever it does, it doesn't just use the blocks which
> are actually used for the tree at the moment.

It loading the bitmap from the disk and sais how many blocks will be scanned.
Regarding -S option, the man page sais:

--scan-whole-partition, -S
This option causes --rebuild-tree to scan the whole partition, not only
used space on the partition.

So, without -S option only used space is scanned, with -S option all blocks are.

> How does reiserfsck determine which blocks contain leaf nodes, anyway?

By analizing the content on pass0. If a block looks like a leaf (probably 
slightly corrupted) it will be inserted into a new tree on pass1 (or only 
not corrupted or recovered items from it on pass2 in the case of corruption). 
If it does not look like a leaf or there is no way to recover data from it, 
the block is skipped on pass0.

-- 

Thanks,
Vitaly Fertman

Re: fsck mode halfway between --fix-fixable and --rebuild-tree ?

[Matthias Urlichs]

Hi,

Oleg Drokin:
> > When I tried this, reiserfsck with -S scanned the whole disk, as expected.
> > Reiserfsck without -S said it would scan roughly half of my disk. That led
> 
> Yes. It scans all the blocks that are marked as "used" in bitmap.
> 
That's not what I meant when I proposed this new option. The method 
which I proposed would walk the existing tree, both "downwards" and
"sideways", to find all reachable blocks with nodes, and then do the
existing rebuild-tree algorithm on the result.

> > me to conclude that whatever it does, it doesn't just use the blocks which
> > are actually used for the tree at the moment.
> 
> How can it know? It must find all the lost blocks too.
> 
... and how can it know that the bitmap represents reality?

Blocks have three pointers which point to them (left neighbour, right
neighbour, and parent).  (That's my understanding of the way people
usually lay out their B-trees, anyway; apologies if yours is radically
different.) I'd like to assume that blocks don't easily get lost when
there are so many ways to find them. Three pointers look safer than a
single bit, anyway.

This method would be a nice compromise between not fixing a problem,
depending on suspect information, and/or reconnecting every file which
I've deleted during the last year.

-- 
Matthias Urlichs     |     noris network AG     |     http://smurf.noris.de/

Re: fsck mode halfway between --fix-fixable and --rebuild-tree ?

[Hans Reiser]

Matthias Urlichs wrote:

>Hi,
>
>Oleg Drokin:
>  
>
>>>When I tried this, reiserfsck with -S scanned the whole disk, as expected.
>>>Reiserfsck without -S said it would scan roughly half of my disk. That led
>>>      
>>>
>>Yes. It scans all the blocks that are marked as "used" in bitmap.
>>
>>    
>>
>That's not what I meant when I proposed this new option. The method 
>which I proposed would walk the existing tree, both "downwards" and
>"sideways", to find all reachable blocks with nodes, and then do the
>existing rebuild-tree algorithm on the result.
>
>  
>
>>>me to conclude that whatever it does, it doesn't just use the blocks which
>>>are actually used for the tree at the moment.
>>>      
>>>
>>How can it know? It must find all the lost blocks too.
>>
>>    
>>
>... and how can it know that the bitmap represents reality?
>
>Blocks have three pointers which point to them (left neighbour, right
>neighbour, and parent).  (That's my understanding of the way people
>usually lay out their B-trees, anyway; apologies if yours is radically
>different.)
>
Is this the way they do it on disk?  We just have a link from parent to 
child.  Maintaining on disk links to siblings would hurt performance as 
the links would require updating.

> I'd like to assume that blocks don't easily get lost when
>there are so many ways to find them. Three pointers look safer than a
>single bit, anyway.
>
>This method would be a nice compromise between not fixing a problem,
>depending on suspect information, and/or reconnecting every file which
>I've deleted during the last year.
>
>  
>

Re: fsck mode halfway between --fix-fixable and --rebuild-tree ?

[Vitaly Fertman]

On Monday 30 September 2002 17:08, Matthias Urlichs wrote:
> Hi,
>
> Oleg Drokin:
> > > When I tried this, reiserfsck with -S scanned the whole disk, as
> > > expected. Reiserfsck without -S said it would scan roughly half of my
> > > disk. That led
> >
> > Yes. It scans all the blocks that are marked as "used" in bitmap.
>
> That's not what I meant when I proposed this new option. The method
> which I proposed would walk the existing tree, both "downwards" and
> "sideways", to find all reachable blocks with nodes, and then do the
> existing rebuild-tree algorithm on the result.

There are more internal nodes in the tree than bitmap blocks. Internal 
nodes could be corrupted also. So we won't get the proper set of used 
blocks by walking the existing tree. And a wrong pointer may connect 
some of your old data back also. 

If corruptions could be fixed without rebuilding the tree, fix-fixable 
does it and it also extends the existing set of used blocks even if 
rebuild-tree will be required later by those blocks which were reachable. 
If rebuild-tree is required, bitmap will be used. 

> > > me to conclude that whatever it does, it doesn't just use the blocks
> > > which are actually used for the tree at the moment.
> >
> > How can it know? It must find all the lost blocks too.
>
> ... and how can it know that the bitmap represents reality?
>
> Blocks have three pointers which point to them (left neighbour, right
> neighbour, and parent).  (That's my understanding of the way people
> usually lay out their B-trees, anyway; apologies if yours is radically
> different.) I'd like to assume that blocks don't easily get lost when
> there are so many ways to find them. Three pointers look safer than a
> single bit, anyway.
>
> This method would be a nice compromise between not fixing a problem,
> depending on suspect information, and/or reconnecting every file which
> I've deleted during the last year.

-- 

Thanks,
Vitaly Fertman

Re: fsck mode halfway between --fix-fixable and --rebuild-tree ?

[Matthias Urlichs]

Hi,

Hans Reiser:

> Is this the way they do it on disk?  We just have a link from parent to 
> child.  Maintaining on disk links to siblings would hurt performance as 
> the links would require updating.
> 
OK -- if you don't have side pointers, that makes my idea somewhat ;-)
less reliable. It might still be a good idea though.

-- 
Matthias Urlichs     |     noris network AG     |     http://smurf.noris.de/

Re: fsck mode halfway between --fix-fixable and --rebuild-tree ?

[Valdis.Kletnieks]

[-- Attachment #1: Type: text/plain, Size: 440 bytes --]

On Mon, 30 Sep 2002 19:36:41 +0200, Matthias Urlichs said:

> OK -- if you don't have side pointers, that makes my idea somewhat ;-)
> less reliable. It might still be a good idea though.

Somehow, the idea of having the phrases "somewhat less reliable" and "good
idea" in the same context regarding a tool like fsck makes me curl up like a
breaded prawn. ;)
-- 
				Valdis Kletnieks
				Computer Systems Senior Engineer
				Virginia Tech


[-- Attachment #2: Type: application/pgp-signature, Size: 226 bytes --]

Re: fsck mode halfway between --fix-fixable and --rebuild-tree ?

[Nikita Danilov]

Hans Reiser writes:
 > Matthias Urlichs wrote:
 > 
 > >Hi,
 > >
 > >Oleg Drokin:
 > >  
 > >
 > >>>When I tried this, reiserfsck with -S scanned the whole disk, as expected.
 > >>>Reiserfsck without -S said it would scan roughly half of my disk. That led
 > >>>      
 > >>>
 > >>Yes. It scans all the blocks that are marked as "used" in bitmap.
 > >>
 > >>    
 > >>
 > >That's not what I meant when I proposed this new option. The method 
 > >which I proposed would walk the existing tree, both "downwards" and
 > >"sideways", to find all reachable blocks with nodes, and then do the
 > >existing rebuild-tree algorithm on the result.
 > >
 > >  
 > >
 > >>>me to conclude that whatever it does, it doesn't just use the blocks which
 > >>>are actually used for the tree at the moment.
 > >>>      
 > >>>
 > >>How can it know? It must find all the lost blocks too.
 > >>
 > >>    
 > >>
 > >... and how can it know that the bitmap represents reality?
 > >
 > >Blocks have three pointers which point to them (left neighbour, right
 > >neighbour, and parent).  (That's my understanding of the way people
 > >usually lay out their B-trees, anyway; apologies if yours is radically
 > >different.)
 > >
 > Is this the way they do it on disk?  We just have a link from parent to 
 > child.  Maintaining on disk links to siblings would hurt performance as 
 > the links would require updating.

Actually, B-link trees (B-trees with sibling pointers) don't require any
additional io for sibling pointers maintenance. Just draw a picture of
what is going on during insertion of new node or node deletion and you
will see. B-link disadvantages are extra space required in a node to
store the sibling pointer and unfriendliness to the "wandered logging".

 > 
 > > I'd like to assume that blocks don't easily get lost when
 > >there are so many ways to find them. Three pointers look safer than a
 > >single bit, anyway.
 > >
 > >This method would be a nice compromise between not fixing a problem,
 > >depending on suspect information, and/or reconnecting every file which
 > >I've deleted during the last year.
 > >
 > >  
 > >
 > 

Nikita.

 > 
 > 

Re: fsck mode halfway between --fix-fixable and --rebuild-tree ?

[Matthias Urlichs]

Hi,

Nikita Danilov:
> Actually, B-link trees (B-trees with sibling pointers) don't require any
> additional io for sibling pointers maintenance. Just draw a picture of
> what is going on during insertion of new node or node deletion and you
> will see. B-link disadvantages are extra space required in a node to
> store the sibling pointer and unfriendliness to the "wandered logging".
> 
Would a wandering log really store the updated blocks themselves, or just
_log_ them?  In the latter case I don't see the difference between a
wandering log and the static log we have now; the former case looks like
it'd have to write at least three times as much log data (not only the
leaf block, but going all the way back to the root) even without taking
sibling blocks into account.

-- 
Matthias Urlichs     |     noris network AG     |     http://smurf.noris.de/

Re: fsck mode halfway between --fix-fixable and --rebuild-tree ?

[Nikita Danilov]

Matthias Urlichs writes:
 > Hi,
 > 
 > Nikita Danilov:
 > > Actually, B-link trees (B-trees with sibling pointers) don't require any
 > > additional io for sibling pointers maintenance. Just draw a picture of
 > > what is going on during insertion of new node or node deletion and you
 > > will see. B-link disadvantages are extra space required in a node to
 > > store the sibling pointer and unfriendliness to the "wandered logging".
 > > 
 > Would a wandering log really store the updated blocks themselves, or just
 > _log_ them?  In the latter case I don't see the difference between a
 > wandering log and the static log we have now; the former case looks like
 > it'd have to write at least three times as much log data (not only the
 > leaf block, but going all the way back to the root) even without taking
 > sibling blocks into account.

Wandered logs in particular and reiser4 transaction design in general
are exposed at the http://www.namesys.com/txn-doc.html. Take a look.

 > 
 > -- 
 > Matthias Urlichs     |     noris network AG     |     http://smurf.noris.de/

Nikita.

Re: fsck mode halfway between --fix-fixable and --rebuild-tree ?

[Hans Reiser]

Nikita Danilov wrote:

>Hans Reiser writes:
> > Matthias Urlichs wrote:
> > 
> > >Hi,
> > >
> > >Oleg Drokin:
> > >  
> > >
> > >>>When I tried this, reiserfsck with -S scanned the whole disk, as expected.
> > >>>Reiserfsck without -S said it would scan roughly half of my disk. That led
> > >>>      
> > >>>
> > >>Yes. It scans all the blocks that are marked as "used" in bitmap.
> > >>
> > >>    
> > >>
> > >That's not what I meant when I proposed this new option. The method 
> > >which I proposed would walk the existing tree, both "downwards" and
> > >"sideways", to find all reachable blocks with nodes, and then do the
> > >existing rebuild-tree algorithm on the result.
> > >
> > >  
> > >
> > >>>me to conclude that whatever it does, it doesn't just use the blocks which
> > >>>are actually used for the tree at the moment.
> > >>>      
> > >>>
> > >>How can it know? It must find all the lost blocks too.
> > >>
> > >>    
> > >>
> > >... and how can it know that the bitmap represents reality?
> > >
> > >Blocks have three pointers which point to them (left neighbour, right
> > >neighbour, and parent).  (That's my understanding of the way people
> > >usually lay out their B-trees, anyway; apologies if yours is radically
> > >different.)
> > >
> > Is this the way they do it on disk?  We just have a link from parent to 
> > child.  Maintaining on disk links to siblings would hurt performance as 
> > the links would require updating.
>
>Actually, B-link trees (B-trees with sibling pointers) don't require any
>additional io for sibling pointers maintenance. Just draw a picture of
>what is going on during insertion of new node or node deletion and you
>will see. 
>
They have constraints we do not desire.  Also, I think they link in only 
one direction.  Am I right?

>B-link disadvantages are extra space required in a node to
>store the sibling pointer and unfriendliness to the "wandered logging".
>
> > 
> > > I'd like to assume that blocks don't easily get lost when
> > >there are so many ways to find them. Three pointers look safer than a
> > >single bit, anyway.
> > >
> > >This method would be a nice compromise between not fixing a problem,
> > >depending on suspect information, and/or reconnecting every file which
> > >I've deleted during the last year.
> > >
> > >  
> > >
> > 
>
>Nikita.
>
> > 
> > 
>
>
>  
>

Re: fsck mode halfway between --fix-fixable and --rebuild-tree ?

[Hans Reiser]

Nikita Danilov wrote:

>Matthias Urlichs writes:
> > Hi,
> > 
> > Nikita Danilov:
> > > Actually, B-link trees (B-trees with sibling pointers) don't require any
> > > additional io for sibling pointers maintenance. Just draw a picture of
> > > what is going on during insertion of new node or node deletion and you
> > > will see. B-link disadvantages are extra space required in a node to
> > > store the sibling pointer and unfriendliness to the "wandered logging".
> > > 
> > Would a wandering log really store the updated blocks themselves, or just
> > _log_ them?  In the latter case I don't see the difference between a
> > wandering log and the static log we have now; the former case looks like
> > it'd have to write at least three times as much log data (not only the
> > leaf block, but going all the way back to the root) even without taking
> > sibling blocks into account.
>
>Wandered logs in particular and reiser4 transaction design in general
>are exposed at the http://www.namesys.com/txn-doc.html. Take a look.
>
> > 
> > -- 
> > Matthias Urlichs     |     noris network AG     |     http://smurf.noris.de/
>
>Nikita.
>
>
>  
>
zam and I just came to the conclusion yesterday that that paper was 
hopelessly outdated and needs a complete rewrite after Halloween....

Re: fsck mode halfway between --fix-fixable and --rebuild-tree ?

[Nikita Danilov]

Hans Reiser writes:
 > Nikita Danilov wrote:
 > 
 > >Hans Reiser writes:
 > > > Matthias Urlichs wrote:
 > > > 
 > > > >Hi,
 > > > >
 > > > >Oleg Drokin:
 > > > >  
 > > > >
 > > > >>>When I tried this, reiserfsck with -S scanned the whole disk, as expected.
 > > > >>>Reiserfsck without -S said it would scan roughly half of my disk. That led
 > > > >>>      
 > > > >>>
 > > > >>Yes. It scans all the blocks that are marked as "used" in bitmap.
 > > > >>
 > > > >>    
 > > > >>
 > > > >That's not what I meant when I proposed this new option. The method 
 > > > >which I proposed would walk the existing tree, both "downwards" and
 > > > >"sideways", to find all reachable blocks with nodes, and then do the
 > > > >existing rebuild-tree algorithm on the result.
 > > > >
 > > > >  
 > > > >
 > > > >>>me to conclude that whatever it does, it doesn't just use the blocks which
 > > > >>>are actually used for the tree at the moment.
 > > > >>>      
 > > > >>>
 > > > >>How can it know? It must find all the lost blocks too.
 > > > >>
 > > > >>    
 > > > >>
 > > > >... and how can it know that the bitmap represents reality?
 > > > >
 > > > >Blocks have three pointers which point to them (left neighbour, right
 > > > >neighbour, and parent).  (That's my understanding of the way people
 > > > >usually lay out their B-trees, anyway; apologies if yours is radically
 > > > >different.)
 > > > >
 > > > Is this the way they do it on disk?  We just have a link from parent to 
 > > > child.  Maintaining on disk links to siblings would hurt performance as 
 > > > the links would require updating.
 > >
 > >Actually, B-link trees (B-trees with sibling pointers) don't require any
 > >additional io for sibling pointers maintenance. Just draw a picture of
 > >what is going on during insertion of new node or node deletion and you
 > >will see. 
 > >
 > They have constraints we do not desire.  Also, I think they link in only 
 > one direction.  Am I right?

Yes, I should have mentioned this. As for constraints, I don't
know. Database people usually claim that B-link is most scalable for their
workloads, which are highly parallel and without hot spots.

 > 
 > >B-link disadvantages are extra space required in a node to
 > >store the sibling pointer and unfriendliness to the "wandered logging".
 > >
 > > > 
 > > > > I'd like to assume that blocks don't easily get lost when
 > > > >there are so many ways to find them. Three pointers look safer than a
 > > > >single bit, anyway.
 > > > >
 > > > >This method would be a nice compromise between not fixing a problem,
 > > > >depending on suspect information, and/or reconnecting every file which
 > > > >I've deleted during the last year.
 > > > >
 > > > >  
 > > > >
 > > > 
 > >

Nikita.

 > >
 > > > 
 > > > 
 > >
 > >
 > >  
 > >
 > 
 > 
 > 

Re: fsck mode halfway between --fix-fixable and --rebuild-tree ?

[Matthias Urlichs]

Hi,

Hans Reiser:
> >Actually, B-link trees (B-trees with sibling pointers) don't require any
> >additional io for sibling pointers maintenance. Just draw a picture of
> >what is going on during insertion of new node or node deletion and you
> >will see. 
> >
> They have constraints we do not desire.  Also, I think they link in only 
> one direction.  Am I right?
> 
Whether you use just a forward-pointing link or also a back-pointing link
(or nothing at all) is up to you. Personally I like sibling and parent
links because it is very easy to walk the tree iteratively (just follow
the "next" or "prev" pointer when you're done with a node). Trees which
only use downward-pointing links need to be walked recursively.

On the other hand, you're a multitasking file system, therefore you need
locking, therefore side pointers won't be of much use to you for anything
(except additional redundancy for error recovery).

-- 
Matthias Urlichs     |     noris network AG     |     http://smurf.noris.de/

Re: fsck mode halfway between --fix-fixable and --rebuild-tree ?

[Hans Reiser]

Matthias Urlichs wrote:

>Hi,
>
>Hans Reiser:
>  
>
>>>Actually, B-link trees (B-trees with sibling pointers) don't require any
>>>additional io for sibling pointers maintenance. Just draw a picture of
>>>what is going on during insertion of new node or node deletion and you
>>>will see. 
>>>
>>>      
>>>
>>They have constraints we do not desire.  Also, I think they link in only 
>>one direction.  Am I right?
>>
>>    
>>
>Whether you use just a forward-pointing link or also a back-pointing link
>(or nothing at all) is up to you. Personally I like sibling and parent
>links because it is very easy to walk the tree iteratively (just follow
>the "next" or "prev" pointer when you're done with a node). Trees which
>only use downward-pointing links need to be walked recursively.
>
>On the other hand, you're a multitasking file system, therefore you need
>locking, therefore side pointers won't be of much use to you for anything
>(except additional redundancy for error recovery).
>
>  
>
Oh, it is not nearly so simple an argument.... Please read the b-link 
literature.  It is at least interesting, even if we did something else.

Re: fsck mode halfway between --fix-fixable and --rebuild-tree ?

[Matthias Urlichs]

Hi,

One other idea I've had yesterday to speed up --rebuild-tree on a big
full disk...

Reiserfsck starts with a bitmap of blocks which might hold B-tree nodes.
The idea is to walk through the existing tree and clear those bits in the
bitmap which actually belong to some file -- those cannot hold metadata.

For extra safety, only consider fiels which haven't been modified for
<insert_date_here>. Abort if you find a tree block which points to
a block whose bit is not set -- either because it never was set in the
first place (then you probably should use -S), or because it points into
a file (then you should set the date back, or use the original mode).

Thoughts? Price?  ;-) 

-- 
Matthias Urlichs     |     noris network AG     |     http://smurf.noris.de/

Re: fsck mode halfway between --fix-fixable and --rebuild-tree ?

[Vitaly Fertman]

On Wednesday 02 October 2002 12:13, Matthias Urlichs wrote:
> Hi,
>
> One other idea I've had yesterday to speed up --rebuild-tree on a big
> full disk...
>
> Reiserfsck starts with a bitmap of blocks which might hold B-tree nodes.
> The idea is to walk through the existing tree and clear those bits in the
> bitmap which actually belong to some file -- those cannot hold metadata.

You forget that pointers can be broken and an unformatted pointer from 
a leaf can point to another leaf or internal node. It is also possible 
to have a block pointed many times by either unformatted or internal 
pointers.

> For extra safety, only consider fiels which haven't been modified for
> <insert_date_here>. Abort if you find a tree block which points to
> a block whose bit is not set -- either because it never was set in the
> first place (then you probably should use -S), or because it points into

And after abort you should probably set all bits back in bitmap, right? 
Actually if the problem is in bad pointers or in bitmap only you can fix 
everything with --fix-fixable. If there is a more complicated problem, 
like broken set of items or similar, you are going to abort, right? So you 
just can run --check and figure out if it is possible to solve a problem 
with fix-fixable.

> a file (then you should set the date back, or use the original mode).
> Thoughts? Price?  ;-)

Actually, I am going to implement a bit different algorithm in reiser4fsck,
which will probably satisfy your wishes. Before rebuilding the tree I am 
going to walk the whole tree and cut the corrupted subtrees out, and then 
rebuild only "used" part of the partition which is not in the tree yet.
So if some part of the tree looks correct, I am not going to rebuild it at 
all, if some part of the tree does not, I do not consider its pointers as 
reliable to change a bitmap.

-- 

Thanks,
Vitaly Fertman

Re: fsck mode halfway between --fix-fixable and --rebuild-tree ?

[Matthias Urlichs]

Hi,

Vitaly Fertman:
> Actually, I am going to implement a bit different algorithm in reiser4fsck,
> which will probably satisfy your wishes. [ description ]

That looks like it'd work nicely. Thanks. What's the timeline for 4.0?

-- 
Matthias Urlichs     |     noris network AG     |     http://smurf.noris.de/