Reiser4 + seekdir()

Reiser4 + seekdir()

[Artem B. Bityuckiy]

Hello,

I was investigating Riser4 readdir() handling. As the result I've 
realized the following:

1. repeatable readdir() calls should work well.
2. seekdir()/telldir() mustn't work. (because per_file readdir_pos 
stores only the _last_ f_pos->{key, entry_no, position} mapping, so the 
mapping will be lost on the next readdir(), and the previous seekdir() 
will be lost too).

But probably I don't quite well understand what's going on. Here is the 
list of things which makes me doubt.

1. There are two types of directory plugins: HASHED_DIR_PLUGIN_ID and 
SEEKABLE_HASHED_DIR_PLUGIN_ID. The latter is claimed as "hashed 
directory for which seekdir/telldir are guaranteed to work". I don't 
understand how can it work. Could somebody please point me the code 
which implements seekdir() (seekdir is actually 
lseek(fd,saved_position,SEEK_SET) in glibc) ? For me it looks like both 
must not support telldir()/seekdir() ...

2. Why you store {entry_no, position, key} in readdir_pos instead of 
just storing the full name string ? In that case you would not need 
adjust_dir_pos() at all ...

Please, comment on this. Thanks.

-- 
Best Regards,
Artem B. Bityuckiy,
St.-Petersburg, Russia.

Re: Reiser4 + seekdir()

[Vladimir Saveliev]

Hello

On Mon, 2005-06-27 at 13:28, Artem B. Bityuckiy wrote:
> Hello,
> 
> I was investigating Riser4 readdir() handling. As the result I've 
> realized the following:
> 
> 1. repeatable readdir() calls should work well.
> 2. seekdir()/telldir() mustn't work. (because per_file readdir_pos 
> stores only the _last_ f_pos->{key, entry_no, position} mapping, so the 
> mapping will be lost on the next readdir(), and the previous seekdir() 
> will be lost too).
> 
> But probably I don't quite well understand what's going on. Here is the 
> list of things which makes me doubt.
> 
> 1. There are two types of directory plugins: HASHED_DIR_PLUGIN_ID and 
> SEEKABLE_HASHED_DIR_PLUGIN_ID. The latter is claimed as "hashed 
> directory for which seekdir/telldir are guaranteed to work". I don't 
> understand how can it work. 

Location within a directory in reiser4 is logical number of entry within
the directory.

> Could somebody please point me the code 
> which implements seekdir() (seekdir is actually 
> lseek(fd,saved_position,SEEK_SET) in glibc) ? For me it looks like both 
> must not support telldir()/seekdir() ...
> 
fs/reiser4/plugin/dir/dir.c:seek_dir()

You may also want to read a comment before
fs/reiser4/plugin/dir/dir.c:readdir_common and comment named  "STATELESS
READDIR" in the fs/reiser4/plugin/dir/dir.c.

> 2. Why you store {entry_no, position, key} in readdir_pos instead of 
> just storing the full name string ? In that case you would not need 
> adjust_dir_pos() at all ...
> 

we can not return entry key to telldir, on seekdir we have to be able to
position within a directory by off_t - therefore, we need adjust_dir_pos
anyway.

Re: Reiser4 + seekdir()

[Artem B. Bityuckiy]

> Location within a directory in reiser4 is logical number of entry within
> the directory.
Yes, I know. It does not absolutely correctly handle the way when 
dirents were deleted before and after the saved position.

Well, Nikita kindly answered my questions in IRC (unfortunately there 
are few Namesys people there).
According to him, seekdir() doesn't have to work correctly if the 
previous N direntries were deleted (it only tries). Indeed, even 
classical FSes (where directory is a file with the plain list of 
direntries) may shrink directories. I thought Reiser4 pretends to work 
correctly even in case of deletions.

> fs/reiser4/plugin/dir/dir.c:seek_dir()
> 
> You may also want to read a comment before
> fs/reiser4/plugin/dir/dir.c:readdir_common and comment named  "STATELESS
> READDIR" in the fs/reiser4/plugin/dir/dir.c.
Yes, I read it of course. It is really confusing. What it should mention 
is that

> we can not return entry key to telldir, on seekdir we have to be able to
> position within a directory by off_t - therefore, we need adjust_dir_pos
> anyway.
Yes, thanks, I've realized this as well.

Could you please explain the real difference between 
SEEKABLE_HASHED_DIR_PLUGIN_ID and LAST_DIR_ID plugins. Both seems to 
support seeks. Both seems to call adjust_dir_pos(). Only key assignment 
is simpler in case of SEEKABLE_HASHED_DIR_PLUGIN_ID. This confused me 
very much.

Thanks.

-- 
Best Regards,
Artem B. Bityuckiy,
St.-Petersburg, Russia.

Re: Reiser4 + seekdir()

[Vladimir Saveliev]

Hello

On Mon, 2005-06-27 at 16:09, Artem B. Bityuckiy wrote:
> > Location within a directory in reiser4 is logical number of entry within
> > the directory.
> Yes, I know. It does not absolutely correctly handle the way when 
> dirents were deleted before and after the saved position.
> 
> Well, Nikita kindly answered my questions in IRC (unfortunately there 
> are few Namesys people there).

for some reasons IRC server decided to not allow us to connect.

> According to him, seekdir() doesn't have to work correctly if the 
> previous N direntries were deleted (it only tries). Indeed, even 
> classical FSes (where directory is a file with the plain list of 
> direntries) may shrink directories. I thought Reiser4 pretends to work 
> correctly even in case of deletions.
> 
> > fs/reiser4/plugin/dir/dir.c:seek_dir()
> > 
> > You may also want to read a comment before
> > fs/reiser4/plugin/dir/dir.c:readdir_common and comment named  "STATELESS
> > READDIR" in the fs/reiser4/plugin/dir/dir.c.
> Yes, I read it of course. It is really confusing. What it should mention 
> is that
> 
> > we can not return entry key to telldir, on seekdir we have to be able to
> > position within a directory by off_t - therefore, we need adjust_dir_pos
> > anyway.
> Yes, thanks, I've realized this as well.
> 
> Could you please explain the real difference between 
> SEEKABLE_HASHED_DIR_PLUGIN_ID and LAST_DIR_ID plugins. 

I guess between SEEKABLE_HASHED_DIR_PLUGIN_ID and HASHED_DIR_PLUGIN_ID?

> Both seems to 
> support seeks. Both seems to call adjust_dir_pos(). Only key assignment 
> is simpler in case of SEEKABLE_HASHED_DIR_PLUGIN_ID. This confused me 
> very much.
> 
SEEKABLE_HASHED_DIR_PLUGIN_ID should actually be able to handle
seekdir/telldir/nfs perfectly: the only part of entry key which depends
of filename is 31 bit hash. Then it can be used to interact with
tell/seekdir. The only problem is hash collistions.

HASHED_DIR_PLUGIN_ID composes entry key in more complicated manner. It
has lexicographic component (15 chars) + 64 bit hash or next 8 chars of
name. It can also involve fibration plugin to group names withint a
directory somehow: for instance *.c files first, then *.h, than *.o.

The cost of solving hash collision problem is all the crap about
positions within a directory.
 
> Thanks.

Re: Reiser4 + seekdir()

[Artem B. Bityuckiy]

Vladimir,

thanks for answer.

Vladimir Saveliev wrote:
> for some reasons IRC server decided to not allow us to connect.
Well, switching to another server may help.

> I guess between SEEKABLE_HASHED_DIR_PLUGIN_ID and HASHED_DIR_PLUGIN_ID?
yes, pardon.

> SEEKABLE_HASHED_DIR_PLUGIN_ID should actually be able to handle
> seekdir/telldir/nfs perfectly: the only part of entry key which depends
> of filename is 31 bit hash. Then it can be used to interact with
> tell/seekdir. The only problem is hash collistions.
Ok. But anyway, actually readdir() uses the direntry sequential number 
as the 32-bit cookie for seek(). So, I don't see how 31-bit hash helps 
here. If you would use the hash value as the seek()/readdir() opaque 
cookie, I could have understood this.

> HASHED_DIR_PLUGIN_ID composes entry key in more complicated manner. It
> has lexicographic component (15 chars) + 64 bit hash or next 8 chars of
> name. It can also involve fibration plugin to group names withint a
> directory somehow: for instance *.c files first, then *.h, than *.o.
Yes, sure. Again, the direntry sequential number is used for 
readdir()/seek() etc. The same as in case of  SEEKABLE_HASHED_DIR_PLUGIN_ID.

So, both are seekable. In both cases the mechanism is the same. Whh one 
is SEEKABLE, another is not ?

-- 
Best Regards,
Artem B. Bityuckiy,
St.-Petersburg, Russia.

Re: Reiser4 + seekdir()

[Vladimir Saveliev]

Hello

On Mon, 2005-06-27 at 16:57, Artem B. Bityuckiy wrote:
> Vladimir,
> 
> thanks for answer.
> 
> Vladimir Saveliev wrote:
> > for some reasons IRC server decided to not allow us to connect.
> Well, switching to another server may help.
> 
> > I guess between SEEKABLE_HASHED_DIR_PLUGIN_ID and HASHED_DIR_PLUGIN_ID?
> yes, pardon.
> 
> > SEEKABLE_HASHED_DIR_PLUGIN_ID should actually be able to handle
> > seekdir/telldir/nfs perfectly: the only part of entry key which depends
> > of filename is 31 bit hash. Then it can be used to interact with
> > tell/seekdir. The only problem is hash collistions.
> Ok. But anyway, actually readdir() uses the direntry sequential number 
> as the 32-bit cookie for seek(). So, I don't see how 31-bit hash helps 
> here. If you would use the hash value as the seek()/readdir() opaque 
> cookie, I could have understood this.

You are right. SEEKABLE directories have to use hash instead of
sequential number.

> > HASHED_DIR_PLUGIN_ID composes entry key in more complicated manner. It
> > has lexicographic component (15 chars) + 64 bit hash or next 8 chars of
> > name. It can also involve fibration plugin to group names withint a
> > directory somehow: for instance *.c files first, then *.h, than *.o.
> Yes, sure. Again, the direntry sequential number is used for 
> readdir()/seek() etc. The same as in case of  SEEKABLE_HASHED_DIR_PLUGIN_ID.
> 
> So, both are seekable. In both cases the mechanism is the same. Whh one 
> is SEEKABLE, another is not ?

I think from the beginning HASHED_DIR_PLUGIN_ID was not supposed to be
seekable. It changed later, HASHED_DIR_PLUGIN_ID became both seekable
and default in reiser4.

Re: Reiser4 + seekdir()

[Artem B. Bityuckiy]

Vladimir Saveliev wrote:
> I think from the beginning HASHED_DIR_PLUGIN_ID was not supposed to be
> seekable. It changed later, HASHED_DIR_PLUGIN_ID became both seekable
> and default in reiser4.
Well, this what I suspected... Would be nice to rename the plugins and 
add more comments..

Thanks.

-- 
Best Regards,
Artem B. Bityuckiy,
St.-Petersburg, Russia.

Re: Reiser4 + seekdir()

[Hans Reiser]

Artem B. Bityuckiy wrote:

>> Location within a directory in reiser4 is logical number of entry within
>> the directory.
>
> Yes, I know. It does not absolutely correctly handle the way when
> dirents were deleted before and after the saved position.
>
> Well, Nikita kindly answered my questions in IRC (unfortunately there
> are few Namesys people there).
> According to him, seekdir() doesn't have to work correctly if the
> previous N direntries were deleted (it only tries). Indeed, even
> classical FSes (where directory is a file with the plain list of
> direntries) may shrink directories. I thought Reiser4 pretends to work
> correctly even in case of deletions.
>
>> fs/reiser4/plugin/dir/dir.c:seek_dir()
>>
>> You may also want to read a comment before
>> fs/reiser4/plugin/dir/dir.c:readdir_common and comment named  "STATELESS
>> READDIR" in the fs/reiser4/plugin/dir/dir.c.
>
> Yes, I read it of course. It is really confusing. What it should
> mention is that
>
>> we can not return entry key to telldir, on seekdir we have to be able to
>> position within a directory by off_t - therefore, we need adjust_dir_pos
>> anyway.
>
> Yes, thanks, I've realized this as well.
>
> Could you please explain the real difference between
> SEEKABLE_HASHED_DIR_PLUGIN_ID and LAST_DIR_ID plugins. Both seems to
> support seeks. Both seems to call adjust_dir_pos(). Only key
> assignment is simpler in case of SEEKABLE_HASHED_DIR_PLUGIN_ID. This
> confused me very much.
>
> Thanks.
>
We do accept patch contributions consisting of comments only.;-)  
Thanks for your patience.

Hans

Re: Reiser4 + seekdir()

[Hans Reiser]

Artem B. Bityuckiy wrote:

> Vladimir Saveliev wrote:
>
>> I think from the beginning HASHED_DIR_PLUGIN_ID was not supposed to be
>> seekable. It changed later, HASHED_DIR_PLUGIN_ID became both seekable
>> and default in reiser4.
>
> Well, this what I suspected... Would be nice to rename the plugins and
> add more comments..
>
> Thanks.
>
thanks Artem.  If you are generous enough to help us with those comments
and renames, I'll take a patch to do it.  If you are too busy though,
vs, can you fix it?

Hans

Re: Reiser4 + seekdir()

[Artem B. Bityuckiy]

Hans Reiser wrote:
> thanks Artem.  If you are generous enough to help us with those comments
> and renames, I'll take a patch to do it.  If you are too busy though,
> vs, can you fix it?

Hans,

I may prepare and send a patch once I've realized what is the purpose 
and function of these two direntry plugins.


SEEKABLE_HASHED_DIR_PLUGIN_ID and

The HASHED_DIR_PLUGIN_ID plugin's destination is clear - it is general 
purpose plugin which should be used in 99% cases except something 
special is needed. The plugin implies the dentries are roughly 
alphabetically sorted and go in the same order as stat-data. Fine

SEEKABLE_HASHED_DIR_PLUGIN_ID - dunno, it it the same as the 
HASHED_DIR_PLUGIN_ID plugin, but the key assignment algorithm is much 
simpler. What's the purpose of this plugin? I understand that it used to 
be mostly seekable while the first one was not seekable when the 
adjust_dir_pos() feature did not exist. But at the moment, what for is it ?

-- 
Best Regards,
Artem B. Bityuckiy,
St.-Petersburg, Russia.

Re: Reiser4 + seekdir()

[Vladimir Saveliev]

Hello

On Wed, 2005-06-29 at 10:51, Artem B. Bityuckiy wrote:
> Hans Reiser wrote:
> > thanks Artem.  If you are generous enough to help us with those comments
> > and renames, I'll take a patch to do it.  If you are too busy though,
> > vs, can you fix it?
> 
> Hans,
> 
> I may prepare and send a patch once I've realized what is the purpose 
> and function of these two direntry plugins.
> 
> 
> SEEKABLE_HASHED_DIR_PLUGIN_ID and
> 
> The HASHED_DIR_PLUGIN_ID plugin's destination is clear - it is general 
> purpose plugin which should be used in 99% cases except something 
> special is needed. The plugin implies the dentries are roughly 
> alphabetically sorted and go in the same order as stat-data. Fine
> 
> SEEKABLE_HASHED_DIR_PLUGIN_ID - dunno, it it the same as the 
> HASHED_DIR_PLUGIN_ID plugin, but the key assignment algorithm is much 
> simpler. What's the purpose of this plugin? I understand that it used to 
> be mostly seekable while the first one was not seekable when the 
> adjust_dir_pos() feature did not exist. But at the moment, what for is it ?

Existence of various plugins assumes that user is able to choose
whatever is suitable for him. Or create his own plugin if none of
existing ones satisfies him.
If user cares a lot about using telldir/seekdir he is supposed to choose
SEEKABLE_HASHED_DIR_PLUGIN_ID.

Re: Reiser4 + seekdir()

[Artem B. Bityuckiy]

Vladimir Saveliev wrote:
> Existence of various plugins assumes that user is able to choose
> whatever is suitable for him. Or create his own plugin if none of
> existing ones satisfies him.
> If user cares a lot about using telldir/seekdir he is supposed to choose
> SEEKABLE_HASHED_DIR_PLUGIN_ID.
Hmm...

May be I don't understand the difference, but the two plugins are *both* 
seekable. Furthermore, AFAICS, it is implemented the same way in both 
cases. So, why user may prefer SEEKABLE_HASHED_DIR_PLUGIN_ID?

-- 
Best Regards,
Artem B. Bityuckiy,
St.-Petersburg, Russia.

Re: Reiser4 + seekdir()

[Vladimir Saveliev]

Hello

On Wed, 2005-06-29 at 14:29, Artem B. Bityuckiy wrote:
> Vladimir Saveliev wrote:
> > Existence of various plugins assumes that user is able to choose
> > whatever is suitable for him. Or create his own plugin if none of
> > existing ones satisfies him.
> > If user cares a lot about using telldir/seekdir he is supposed to choose
> > SEEKABLE_HASHED_DIR_PLUGIN_ID.
> Hmm...
> 
> May be I don't understand the difference, but the two plugins are *both* 
> seekable.

HASHED_DIR_PLUGIN_ID's seekableness is a hack, imho. I would prefer if
it just did not support llseek operation.
Name of marco itself is confusing. Names are sorted lexicographically
with fibration, hash is onlyh involved for names longer than 23 chars.

>  Furthermore, AFAICS, it is implemented the same way in both 
> cases. 

It is wrong. SEEKABLE_HASHED_DIR_PLUGIN_ID should return 32 bit hash
value as a position within a direcotry instead of logical number of
entry in it.

> So, why user may prefer SEEKABLE_HASHED_DIR_PLUGIN_ID?

It user wants seekdir/telldir to work properly and does not care about
hash collisions and SEEKABLE_HASHED_DIR_PLUGIN_ID is implemented
properly - this plugin can be used.

Well, I do not know whether it ever will be used.

Re: Reiser4 + seekdir()

[Valdis.Kletnieks]

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

On Wed, 29 Jun 2005 14:22:05 +0400, Vladimir Saveliev said:
 
> Existence of various plugins assumes that user is able to choose
> whatever is suitable for him. Or create his own plugin if none of
> existing ones satisfies him.
> If user cares a lot about using telldir/seekdir he is supposed to choose
> SEEKABLE_HASHED_DIR_PLUGIN_ID.

Is that "the user", or "the person building the kernel"?


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

Re: Reiser4 + seekdir()

[Vladimir Saveliev]

On Wed, 2005-06-29 at 22:11, Valdis.Kletnieks@vt.edu wrote:
> On Wed, 29 Jun 2005 14:22:05 +0400, Vladimir Saveliev said:
>  
> > Existence of various plugins assumes that user is able to choose
> > whatever is suitable for him. Or create his own plugin if none of
> > existing ones satisfies him.
> > If user cares a lot about using telldir/seekdir he is supposed to choose
> > SEEKABLE_HASHED_DIR_PLUGIN_ID.
> 
> Is that "the user", or "the person building the kernel"?
> 

User. 
In theory, I think, it is supposed to be like that:
user designes his application. He has some requirements to directories
he stores data in. If he is reading reiserfs mailing lists he should be
aware of reiser4 plugins and implement his application so that if
reiser4 is available - he chooses for his directory a plugin with
properties which match his requirements more.
So far, I think you can choose directory plugin on mkfs time.