[CFD] disk format fixing

[CFD] disk format fixing

[Jiro SEKIBA]

Hi,

It's been almost a year that nilfs2 has been merged into mainline kernel
since 2.6.30, which is released in Jun 2009.  Yet, it still shows warnings
that "The NILFS on-disk format may change at any time".

It still remains controversial argument, like directory indexing
or atime support, xattr support and so on.  However, I'd like to
make the target clear that when the above message can be taken away.

By fixing disk format, we might go forward to contribute more useful
disk utilities like GNU pared.  Some of those user land utilities require
just reading super block (or blocks) to identify what the filesystem is
in the specified partition.  Therefore it would be good starting point to
declare superblock format which ensure that upper/lower compatibilities.

In addition to superblock format, over all disk format must be fixed
somehow everybody thinks "it's ok".

There are many features in ToDo list of nilfs web site
http://www.nilfs.org/en/current_status.html.  I can not tell
which features should be in the nilfs2 before disk format fix as a
modern mature filesystem, but I can tell not all of those are required :).

Which of those do you guys think are the mandatory for modern filesystem
and which may require disk format change?  We might able to find 
consensus among the list before any modifying/fixing disk format.

Thanks,

Regards,
-- 
Jiro SEKIBA <jir-hfpbi5WX9J54Eiagz67IpQ@public.gmane.org>
--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [CFD] disk format fixing

[Jay Carlson]

On May 3, 2010, at 11:54 AM, Jiro SEKIBA wrote:

> By fixing disk format, we might go forward to contribute more useful
> disk utilities like GNU pared.  Some of those user land utilities require
> just reading super block (or blocks) to identify what the filesystem is
> in the specified partition.  Therefore it would be good starting point to
> declare superblock format which ensure that upper/lower compatibilities.

Low-end consumer flash (like USB thumb drives or MMC) often uses a simple zone-based FTL with bad block replacement.  I am told really cheap ones allocate zones with 1000 flash blocks with 24 held as replacements for failing blocks and wear leveling.

If I understand nilfs, its superblock is both fixed location and "hot": it is written fairly frequently (on every fsync?)  On cheap flash, it will wear out the flash block it lives on in 25 write lifetimes or less.  

I don't know if this is a serious danger, or worth much effort to fix.  The best we could do is extend the filesystem lifetime to 1024 write lifetimes (if we perfectly spread writes across the zone.)  

Some approaches to this would require modification of the superblock; for instance, having the main superblock point to a per-mount "session" superblock (placed randomly somewhere before s_first_data_block).

ext2 supports the sb=n option at mount to specify the superblock's offset from start of device.  If nilfs supported this, userspace mount tools could choose their own policy for moving the superblock around.

(For example, they could write the offset into a non-standard block 0, or stash it in s_volume_name; they could also scan a region looking for the most recent mount time, and so on.  These are cheap hacks.)

Again, I don't know if this is even a problem or worth addressing, but it's the only possible nilfs write pattern incompatible with cheap flash memory that I could think of.

Jay


--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [CFD] disk format fixing

[Reinoud Zandijk]

On Mon, May 03, 2010 at 03:35:03PM -0400, Jay Carlson wrote:
> On May 3, 2010, at 11:54 AM, Jiro SEKIBA wrote:
> Low-end consumer flash (like USB thumb drives or MMC) often uses a simple
> zone-based FTL with bad block replacement.  I am told really cheap ones
> allocate zones with 1000 flash blocks with 24 held as replacements for
> failing blocks and wear leveling.
> 
> If I understand nilfs, its superblock is both fixed location and "hot": it
> is written fairly frequently (on every fsync?)  On cheap flash, it will wear
> out the flash block it lives on in 25 write lifetimes or less.  

I'd opt for NOT writing out the super block but on unmount or when the
roll-forward chain is disturbed by the garbage collector.i

Another option is to never update it; it should at most take a few secs to
locate the latest segsum by just scanning trough the segement summaries;
especially now the segment summaries have the checkpoint number incorporated.
If on mount all first segment summaries are read (say 4000 to 8000 sectors)
its clear wich is the newest and then follow that chain until you reach the
end... and you can mount. I agree its not optimal but i dont see a reason as
to why it shouldn't work :) It is also backwards compatible since older
implementations can will search for the last super root; they only will need
to read more.

With regards,
Reinoud

--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [CFD] disk format fixing

[Ryusuke Konishi]

On Tue, 4 May 2010 14:02:22 +0200, Reinoud Zandijk wrote:
> On Mon, May 03, 2010 at 03:35:03PM -0400, Jay Carlson wrote:
> > On May 3, 2010, at 11:54 AM, Jiro SEKIBA wrote:
> > Low-end consumer flash (like USB thumb drives or MMC) often uses a simple
> > zone-based FTL with bad block replacement.  I am told really cheap ones
> > allocate zones with 1000 flash blocks with 24 held as replacements for
> > failing blocks and wear leveling.
> > 
> > If I understand nilfs, its superblock is both fixed location and "hot": it
> > is written fairly frequently (on every fsync?)  On cheap flash, it will wear
> > out the flash block it lives on in 25 write lifetimes or less.  
> 
> I'd opt for NOT writing out the super block but on unmount or when the
> roll-forward chain is disturbed by the garbage collector.i
> 
> Another option is to never update it; it should at most take a few secs to
> locate the latest segsum by just scanning trough the segement summaries;
> especially now the segment summaries have the checkpoint number incorporated.
>
> If on mount all first segment summaries are read (say 4000 to 8000 sectors)
> its clear wich is the newest and then follow that chain until you reach the
> end... and you can mount. I agree its not optimal but i dont see a reason as
> to why it shouldn't work :)

I was just thinking the same thing.

The reason nilfs frequently updates super blocks is for maintaining a
pointer to recent logs.  And, the new checkpoint number field allows
it to find them by scanning through summary headers of each segments.

This may be expensive for hard drives, but may be acceptable for flash
devices.  I think it's worth adding a new mount option (or a flag) for
this.

The super blocks also maintain free blocks count, but it's computable.

> It is also backwards compatible since older
> implementations can will search for the last super root; they only will need
> to read more.

You mean forward compatibility?

I think older implementations have potential to select wrong super
root due to the garbage collector.  This issue seems a key of this
approach.

Even though we can make super blocks written out on unmount as before,
an unclean shutdown and subsequent boot with an old implementation may
lead to a fatal result.

Without this issue, it looks pretty good.

With regards,
Ryusuke Konishi
--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [CFD] disk format fixing

[Jiro SEKIBA]

Hi,

OK, it looks like a flag should be introduced for older flash device 
not to write super block whenever checkpoint is created, but maintain
it less frequently or even not writing at all until unmount.

In any cases, at least super block disk format is not modified.

At Tue, 04 May 2010 23:01:35 +0900 (JST),
Ryusuke Konishi wrote:
> 
> On Tue, 4 May 2010 14:02:22 +0200, Reinoud Zandijk wrote:
> > On Mon, May 03, 2010 at 03:35:03PM -0400, Jay Carlson wrote:
> > > On May 3, 2010, at 11:54 AM, Jiro SEKIBA wrote:
> > > Low-end consumer flash (like USB thumb drives or MMC) often uses a simple
> > > zone-based FTL with bad block replacement.  I am told really cheap ones
> > > allocate zones with 1000 flash blocks with 24 held as replacements for
> > > failing blocks and wear leveling.
> > > 
> > > If I understand nilfs, its superblock is both fixed location and "hot": it
> > > is written fairly frequently (on every fsync?)  On cheap flash, it will wear
> > > out the flash block it lives on in 25 write lifetimes or less.  
> > 
> > I'd opt for NOT writing out the super block but on unmount or when the
> > roll-forward chain is disturbed by the garbage collector.i
> > 
> > Another option is to never update it; it should at most take a few secs to
> > locate the latest segsum by just scanning trough the segement summaries;
> > especially now the segment summaries have the checkpoint number incorporated.
> >
> > If on mount all first segment summaries are read (say 4000 to 8000 sectors)
> > its clear wich is the newest and then follow that chain until you reach the
> > end... and you can mount. I agree its not optimal but i dont see a reason as
> > to why it shouldn't work :)
> 
> I was just thinking the same thing.
> 
> The reason nilfs frequently updates super blocks is for maintaining a
> pointer to recent logs.  And, the new checkpoint number field allows
> it to find them by scanning through summary headers of each segments.
> 
> This may be expensive for hard drives, but may be acceptable for flash
> devices.  I think it's worth adding a new mount option (or a flag) for
> this.

This leads that boot loader is required to take care of searching
valid super root by the scanning all the segments, unlike just 
roll forwarding the log.

From boot loader (grub2) point of view, any access to the filesystem
requires "mount" operation, which means leading two files (initrd and kernel)
requires at least two mount operations.  That means in case of unclean unmount,
it requires to scan whole disks twice.

So I opt to write super block less frequently, to maintain super root
pointer so that roll forwarding likely finds correct super root.

Or maybe specifying frequency as mount option, say like write back
per 100 check points.

thanks,

regards,

> The super blocks also maintain free blocks count, but it's computable.
> 
> > It is also backwards compatible since older
> > implementations can will search for the last super root; they only will need
> > to read more.
> 
> You mean forward compatibility?
> 
> I think older implementations have potential to select wrong super
> root due to the garbage collector.  This issue seems a key of this
> approach.
>
> Even though we can make super blocks written out on unmount as before,
> an unclean shutdown and subsequent boot with an old implementation may
> lead to a fatal result.
> 
> Without this issue, it looks pretty good.
> 
> With regards,
> Ryusuke Konishi
> --
> To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
> the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 
> 
> 




-- 
Jiro SEKIBA <jir-hfpbi5WX9J54Eiagz67IpQ@public.gmane.org>
--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [CFD] disk format fixing

[Ryusuke Konishi]

On Thu, 06 May 2010 00:10:53 +0900, Jiro SEKIBA wrote:
> Hi,
> 
> OK, it looks like a flag should be introduced for older flash device 
> not to write super block whenever checkpoint is created, but maintain
> it less frequently or even not writing at all until unmount.
> 
> In any cases, at least super block disk format is not modified.
> 
> At Tue, 04 May 2010 23:01:35 +0900 (JST),
> Ryusuke Konishi wrote:
> > 
> > On Tue, 4 May 2010 14:02:22 +0200, Reinoud Zandijk wrote:
> > > On Mon, May 03, 2010 at 03:35:03PM -0400, Jay Carlson wrote:
> > > > On May 3, 2010, at 11:54 AM, Jiro SEKIBA wrote:
> > > > Low-end consumer flash (like USB thumb drives or MMC) often uses a simple
> > > > zone-based FTL with bad block replacement.  I am told really cheap ones
> > > > allocate zones with 1000 flash blocks with 24 held as replacements for
> > > > failing blocks and wear leveling.
> > > > 
> > > > If I understand nilfs, its superblock is both fixed location and "hot": it
> > > > is written fairly frequently (on every fsync?)  On cheap flash, it will wear
> > > > out the flash block it lives on in 25 write lifetimes or less.  
> > > 
> > > I'd opt for NOT writing out the super block but on unmount or when the
> > > roll-forward chain is disturbed by the garbage collector.i
> > > 
> > > Another option is to never update it; it should at most take a few secs to
> > > locate the latest segsum by just scanning trough the segement summaries;
> > > especially now the segment summaries have the checkpoint number incorporated.
> > >
> > > If on mount all first segment summaries are read (say 4000 to 8000 sectors)
> > > its clear wich is the newest and then follow that chain until you reach the
> > > end... and you can mount. I agree its not optimal but i dont see a reason as
> > > to why it shouldn't work :)
> > 
> > I was just thinking the same thing.
> > 
> > The reason nilfs frequently updates super blocks is for maintaining a
> > pointer to recent logs.  And, the new checkpoint number field allows
> > it to find them by scanning through summary headers of each segments.
> > 
> > This may be expensive for hard drives, but may be acceptable for flash
> > devices.  I think it's worth adding a new mount option (or a flag) for
> > this.
> 
> This leads that boot loader is required to take care of searching
> valid super root by the scanning all the segments, unlike just 
> roll forwarding the log.
> 
> From boot loader (grub2) point of view, any access to the filesystem
> requires "mount" operation, which means leading two files (initrd and kernel)
> requires at least two mount operations.  That means in case of unclean unmount,
> it requires to scan whole disks twice.
> 
> So I opt to write super block less frequently, to maintain super root
> pointer so that roll forwarding likely finds correct super root.
> 
> Or maybe specifying frequency as mount option, say like write back
> per 100 check points.
> 
> thanks,
> 
> regards,

As an alternative, I'm thinking to add a new state flag which
indicates segments are allocated physically continuously from
the super root to which super blocks point.

The aim of this flag is allowing nilfs to find out the latest segment
with bisection search.

Envisioned changes are as follows:

* add the new flag (for example, NILFS_INORDER_FS) for sbp->s_state.

* set the flag if a new mount options is specified (for example
  "-o bisect-root").

* Do not update super block when the filesystem is unmounted, and keep
  the state: s_state.NILFS_INORDER_FS = 1, s_state.NILFS_VALID_FS = 0.

* Stop periodic update of super blocks if the flag is set.

* If s_state.NILFS_VALID_FS = 0 && s_state.NILFS_INORDER_FS = 1 when
  the filesystem is mounted, then do bisect search to find out the
  latest segment.

* If a new segment is allocated discontinuously and a new super root
  is created, then write out super blocks to catch up the position.

* If GC breaks the series of physically continous segments, then
  update super blocks to catch up the latest super root position.

* Add a new option to cleanerd to pass the "-o bisect-root" mode
  and let it select the rotational GC algorithm (current default).

* If the "-o bisect-root" option is not specified, then use a
  conventional algorithm and drop the NILFS_INORDER_FS flag.

This doesn't break forward compatibility, because the "next segment
chain" is still maintained and older implementations will ignore the
NILFS_INORDER_FS flag.  Older implementations and the current grub2
module can find the latest super root though they incur penalty for
mount time.

Another drawback of this approach is that it depends on garbage
collection algorithm, but at least at present, this seems not to
matter.

How does that sound?

Thanks,
Ryusuke Konishi
--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [CFD] disk format fixing

[Jiro SEKIBA]

Hi,

At Thu, 06 May 2010 03:23:27 +0900 (JST),
Ryusuke Konishi wrote:
> 
> On Thu, 06 May 2010 00:10:53 +0900, Jiro SEKIBA wrote:
> > Hi,
> > 
> > OK, it looks like a flag should be introduced for older flash device 
> > not to write super block whenever checkpoint is created, but maintain
> > it less frequently or even not writing at all until unmount.
> > 
> > In any cases, at least super block disk format is not modified.
> > 
> > At Tue, 04 May 2010 23:01:35 +0900 (JST),
> > Ryusuke Konishi wrote:
> > > 
> > > On Tue, 4 May 2010 14:02:22 +0200, Reinoud Zandijk wrote:
> > > > On Mon, May 03, 2010 at 03:35:03PM -0400, Jay Carlson wrote:
> > > > > On May 3, 2010, at 11:54 AM, Jiro SEKIBA wrote:
> > > > > Low-end consumer flash (like USB thumb drives or MMC) often uses a simple
> > > > > zone-based FTL with bad block replacement.  I am told really cheap ones
> > > > > allocate zones with 1000 flash blocks with 24 held as replacements for
> > > > > failing blocks and wear leveling.
> > > > > 
> > > > > If I understand nilfs, its superblock is both fixed location and "hot": it
> > > > > is written fairly frequently (on every fsync?)  On cheap flash, it will wear
> > > > > out the flash block it lives on in 25 write lifetimes or less.  
> > > > 
> > > > I'd opt for NOT writing out the super block but on unmount or when the
> > > > roll-forward chain is disturbed by the garbage collector.i
> > > > 
> > > > Another option is to never update it; it should at most take a few secs to
> > > > locate the latest segsum by just scanning trough the segement summaries;
> > > > especially now the segment summaries have the checkpoint number incorporated.
> > > >
> > > > If on mount all first segment summaries are read (say 4000 to 8000 sectors)
> > > > its clear wich is the newest and then follow that chain until you reach the
> > > > end... and you can mount. I agree its not optimal but i dont see a reason as
> > > > to why it shouldn't work :)
> > > 
> > > I was just thinking the same thing.
> > > 
> > > The reason nilfs frequently updates super blocks is for maintaining a
> > > pointer to recent logs.  And, the new checkpoint number field allows
> > > it to find them by scanning through summary headers of each segments.
> > > 
> > > This may be expensive for hard drives, but may be acceptable for flash
> > > devices.  I think it's worth adding a new mount option (or a flag) for
> > > this.
> > 
> > This leads that boot loader is required to take care of searching
> > valid super root by the scanning all the segments, unlike just 
> > roll forwarding the log.
> > 
> > From boot loader (grub2) point of view, any access to the filesystem
> > requires "mount" operation, which means leading two files (initrd and kernel)
> > requires at least two mount operations.  That means in case of unclean unmount,
> > it requires to scan whole disks twice.
> > 
> > So I opt to write super block less frequently, to maintain super root
> > pointer so that roll forwarding likely finds correct super root.
> > 
> > Or maybe specifying frequency as mount option, say like write back
> > per 100 check points.
> > 
> > thanks,
> > 
> > regards,
> 
> As an alternative, I'm thinking to add a new state flag which
> indicates segments are allocated physically continuously from
> the super root to which super blocks point.
>
>
> The aim of this flag is allowing nilfs to find out the latest segment
> with bisection search.
> 
> Envisioned changes are as follows:
> 
> * add the new flag (for example, NILFS_INORDER_FS) for sbp->s_state.
> 
> * set the flag if a new mount options is specified (for example
>   "-o bisect-root").
> 
> * Do not update super block when the filesystem is unmounted, and keep
>   the state: s_state.NILFS_INORDER_FS = 1, s_state.NILFS_VALID_FS = 0.
> 
> * Stop periodic update of super blocks if the flag is set.
> 
> * If s_state.NILFS_VALID_FS = 0 && s_state.NILFS_INORDER_FS = 1 when
>   the filesystem is mounted, then do bisect search to find out the
>   latest segment.

Here are the question, to do bisect search, you need to know the end of
the segments to divide physically continuous blocks.  Which is the
end of the block for bisect?  Is this going to be the physical partition end?

> * If a new segment is allocated discontinuously and a new super root
>   is created, then write out super blocks to catch up the position.
> 
> * If GC breaks the series of physically continous segments, then
>   update super blocks to catch up the latest super root position.
> 
> * Add a new option to cleanerd to pass the "-o bisect-root" mode
>   and let it select the rotational GC algorithm (current default).
> 
> * If the "-o bisect-root" option is not specified, then use a
>   conventional algorithm and drop the NILFS_INORDER_FS flag.

I prefer option name like "-o async_sb" or "-o no_sync_sb" or so.
Because users would rather curious how to udpate super block than
how to find the latest log.

> This doesn't break forward compatibility, because the "next segment
> chain" is still maintained and older implementations will ignore the
> NILFS_INORDER_FS flag.  Older implementations and the current grub2
> module can find the latest super root though they incur penalty for
> mount time.
> 
> Another drawback of this approach is that it depends on garbage
> collection algorithm, but at least at present, this seems not to
> matter.
> 
> How does that sound?

It would be much better than scanning whole segments from
boot loader point of view.

> Thanks,
> Ryusuke Konishi
> --
> To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
> the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 
> 
> 


-- 
Jiro SEKIBA <jir-hfpbi5WX9J54Eiagz67IpQ@public.gmane.org>
--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [CFD] disk format fixing

[Ryusuke Konishi]

On Mon, 10 May 2010 01:45:35 +0900, Jiro SEKIBA wrote:
> > As an alternative, I'm thinking to add a new state flag which
> > indicates segments are allocated physically continuously from
> > the super root to which super blocks point.
> >
> >
> > The aim of this flag is allowing nilfs to find out the latest segment
> > with bisection search.
> > 
> > Envisioned changes are as follows:
> > 
> > * add the new flag (for example, NILFS_INORDER_FS) for sbp->s_state.
> > 
> > * set the flag if a new mount options is specified (for example
> >   "-o bisect-root").
> > 
> > * Do not update super block when the filesystem is unmounted, and keep
> >   the state: s_state.NILFS_INORDER_FS = 1, s_state.NILFS_VALID_FS = 0.
> > 
> > * Stop periodic update of super blocks if the flag is set.
> > 
> > * If s_state.NILFS_VALID_FS = 0 && s_state.NILFS_INORDER_FS = 1 when
> >   the filesystem is mounted, then do bisect search to find out the
> >   latest segment.
> 
> Here are the question, to do bisect search, you need to know the end of
> the segments to divide physically continuous blocks.  Which is the
> end of the block for bisect?  Is this going to be the physical partition end?

The end position is the segment immediately in front of the current
segment since disk space is typically used like a circular buffer.

> > * If a new segment is allocated discontinuously and a new super root
> >   is created, then write out super blocks to catch up the position.
> > 
> > * If GC breaks the series of physically continous segments, then
> >   update super blocks to catch up the latest super root position.
> > 
> > * Add a new option to cleanerd to pass the "-o bisect-root" mode
> >   and let it select the rotational GC algorithm (current default).
> > 
> > * If the "-o bisect-root" option is not specified, then use a
> >   conventional algorithm and drop the NILFS_INORDER_FS flag.
> 
> I prefer option name like "-o async_sb" or "-o no_sync_sb" or so.
> Because users would rather curious how to udpate super block than
> how to find the latest log.

Thanks for the comment.  In a narrow sense, "no_sync_sb" is difficult
in this approach, so "few_sync_sb" or "async_sb" sounds better to me.
Anyway, I agree with your point.
 
> > This doesn't break forward compatibility, because the "next segment
> > chain" is still maintained and older implementations will ignore the
> > NILFS_INORDER_FS flag.  Older implementations and the current grub2
> > module can find the latest super root though they incur penalty for
> > mount time.
> > 
> > Another drawback of this approach is that it depends on garbage
> > collection algorithm, but at least at present, this seems not to
> > matter.
> > 
> > How does that sound?
> 
> It would be much better than scanning whole segments from
> boot loader point of view.

Yes, I believe it doesn't complicate boot loader so much.

Thanks,
Ryusuke Konishi
--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [CFD] disk format fixing

[Jiro SEKIBA]

At Mon, 10 May 2010 03:29:22 +0900 (JST),
Ryusuke Konishi wrote:
> 
> On Mon, 10 May 2010 01:45:35 +0900, Jiro SEKIBA wrote:
> > > As an alternative, I'm thinking to add a new state flag which
> > > indicates segments are allocated physically continuously from
> > > the super root to which super blocks point.
> > >
> > >
> > > The aim of this flag is allowing nilfs to find out the latest segment
> > > with bisection search.
> > > 
> > > Envisioned changes are as follows:
> > > 
> > > * add the new flag (for example, NILFS_INORDER_FS) for sbp->s_state.
> > > 
> > > * set the flag if a new mount options is specified (for example
> > >   "-o bisect-root").
> > > 
> > > * Do not update super block when the filesystem is unmounted, and keep
> > >   the state: s_state.NILFS_INORDER_FS = 1, s_state.NILFS_VALID_FS = 0.
> > > 
> > > * Stop periodic update of super blocks if the flag is set.
> > > 
> > > * If s_state.NILFS_VALID_FS = 0 && s_state.NILFS_INORDER_FS = 1 when
> > >   the filesystem is mounted, then do bisect search to find out the
> > >   latest segment.
> > 
> > Here are the question, to do bisect search, you need to know the end of
> > the segments to divide physically continuous blocks.  Which is the
> > end of the block for bisect?  Is this going to be the physical partition end?
> 
> The end position is the segment immediately in front of the current
> segment since disk space is typically used like a circular buffer.

Ah, I got it.  The continuous log is the one to make bisect search possible,
yet roll forwarding can reach the latest log.

I think, roll forwarding may be enough for boot loader,
for it still reach correct log.
And once correctly mounted, super block will be corrected.

Thanks!

regards,

> > > * If a new segment is allocated discontinuously and a new super root
> > >   is created, then write out super blocks to catch up the position.
> > > 
> > > * If GC breaks the series of physically continous segments, then
> > >   update super blocks to catch up the latest super root position.
> > > 
> > > * Add a new option to cleanerd to pass the "-o bisect-root" mode
> > >   and let it select the rotational GC algorithm (current default).
> > > 
> > > * If the "-o bisect-root" option is not specified, then use a
> > >   conventional algorithm and drop the NILFS_INORDER_FS flag.
> > 
> > I prefer option name like "-o async_sb" or "-o no_sync_sb" or so.
> > Because users would rather curious how to udpate super block than
> > how to find the latest log.
> 
> Thanks for the comment.  In a narrow sense, "no_sync_sb" is difficult
> in this approach, so "few_sync_sb" or "async_sb" sounds better to me.
> Anyway, I agree with your point.
>  
> > > This doesn't break forward compatibility, because the "next segment
> > > chain" is still maintained and older implementations will ignore the
> > > NILFS_INORDER_FS flag.  Older implementations and the current grub2
> > > module can find the latest super root though they incur penalty for
> > > mount time.
> > > 
> > > Another drawback of this approach is that it depends on garbage
> > > collection algorithm, but at least at present, this seems not to
> > > matter.
> > > 
> > > How does that sound?
> > 
> > It would be much better than scanning whole segments from
> > boot loader point of view.
> 
> Yes, I believe it doesn't complicate boot loader so much.
> 
> Thanks,
> Ryusuke Konishi
> --
> To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
> the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 
> 
> 


-- 
Jiro SEKIBA <jir-hfpbi5WX9J54Eiagz67IpQ@public.gmane.org>
--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [CFD] disk format fixing

[Reinoud Zandijk]

Hi,

On Tue, May 04, 2010 at 12:54:21AM +0900, Jiro SEKIBA wrote:
> It still remains controversial argument, like directory indexing or atime
> support, xattr support and so on.  However, I'd like to make the target
> clear that when the above message can be taken away.

I'd opt for not getting into directory indexing; that can easily be
implemented at run-time as i showed to with code in the NetBSD implementation.
The speed increase is really fenominal (can be 500+ times) and doesn't need
much memory space and doesn't involve a disc layout change.

With regards,
Reinoud


--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [CFD] disk format fixing

[Jiro SEKIBA]

Hi,


> > It still remains controversial argument, like directory indexing or atime
> > support, xattr support and so on.  However, I'd like to make the target
> > clear that when the above message can be taken away.
> 
> I'd opt for not getting into directory indexing; that can easily be
> implemented at run-time as i showed to with code in the NetBSD implementation.
> The speed increase is really fenominal (can be 500+ times) and doesn't need
> much memory space and doesn't involve a disc layout change.

I agree with you that no getting into directory index, at least this time.
Howerver, I don't agree (or disagree) with your on memory indexing idea yet.

nilfs has there own btree functionality, therefore it is goot to be used for 
directory indexing if nilfs has it.  So even ext3 htree format preserve
both backward/forward compatibility and is well tested code base,
maintaining both htree and btree code is not the best idea.

thanks,

regards,
-- 
Jiro SEKIBA <jir-hfpbi5WX9J54Eiagz67IpQ@public.gmane.org>
--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [CFD] disk format fixing

[Ryusuke Konishi]

On Tue, 04 May 2010 00:54:21 +0900, Jiro SEKIBA wrote:
> Hi,
> 
> It's been almost a year that nilfs2 has been merged into mainline kernel
> since 2.6.30, which is released in Jun 2009.  Yet, it still shows warnings
> that "The NILFS on-disk format may change at any time".
> 
> It still remains controversial argument, like directory indexing
> or atime support, xattr support and so on.  However, I'd like to
> make the target clear that when the above message can be taken away.
> 
> By fixing disk format, we might go forward to contribute more useful
> disk utilities like GNU pared.  Some of those user land utilities require
> just reading super block (or blocks) to identify what the filesystem is
> in the specified partition.  Therefore it would be good starting point to
> declare superblock format which ensure that upper/lower compatibilities.
> 
> In addition to superblock format, over all disk format must be fixed
> somehow everybody thinks "it's ok".

Thank you for this proposal.

I think the warning should be removed much earlier, but at least, it's
preferable that the decision is based on some consensus.

Sekiba-san, could you become the facilitator of this discussion?

I think we should take a step-by-step approach.

I agree freezing superblock format is a good milestone for it.

Preferably, it should be included for 2.6.35.

With regards,
Ryusuke Konishi
--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [CFD] disk format fixing

[Jiro SEKIBA]

Hi,

I'd like to summarize the comments so far for disk fomat fix.
Please correct it if it's wrong or missing something.


I've started this thread to fix disk format of nilfs2 at the point
everybody thinks it's ok, strip "experimental", encourage developing
user land tools and different implementation like on NetBSD.

So far, we have been talking disk format from two aspects,
spuer block and rest of disk.  That's simply because most of user land tools
care only super block and rest of disk are much more controversial
than super block.  I'd like to summarize from those aspects.

- Super block format

Super blocks are frequently updated hotspot of nilfs2.  This is not good
for low-end flash device for wearing point of view.  To address this problem,
suggested introducing new mount option that makes less updates super blocks.

At this point, super block format itself is unchanged, still oloder
nilfs implementation can find correct latest log in case of unclean mount.

- Rest of disk

* directory indexing
There is long term controversial discussion about directory indexing.
One is on memory indexing, the other is on disk indexing.  We have not
reached a resolution, but at least agreed "unchange for now".
So, disk format point of view, it'll be fixed for nilfs2.
However it is a subject to change for future nilfs2 or nilfs3 or so.

~~

There are more missing features that should be in a modern filesystem,
like xattr or posix acls, check ToDo list in following url:
http://www.nilfs.org/en/current_status.html

You may not have to know disk format but if you feel functions which 
are not in nilfs2, but mandatory to support, please state so.
Then we can start that the how those functions can be implmented in nilfs2
from disk format point of view.  Otherwise, any functions that requires disk
format change will be not supported in near future or forever "experimental".

thanks,

regards,
-- 
Jiro SEKIBA <jir-hfpbi5WX9J54Eiagz67IpQ@public.gmane.org>
--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [CFD] disk format fixing

[Ryusuke Konishi]

Hi,
On Sun, 16 May 2010 23:42:31 +0900, Jiro SEKIBA wrote:
> Hi,
> 
> I'd like to summarize the comments so far for disk fomat fix.
> Please correct it if it's wrong or missing something.
> 
> 
> I've started this thread to fix disk format of nilfs2 at the point
> everybody thinks it's ok, strip "experimental", encourage developing
> user land tools and different implementation like on NetBSD.
> 
> So far, we have been talking disk format from two aspects,
> spuer block and rest of disk.  That's simply because most of user land tools
> care only super block and rest of disk are much more controversial
> than super block.  I'd like to summarize from those aspects.
> 
> - Super block format
> 
> Super blocks are frequently updated hotspot of nilfs2.  This is not good
> for low-end flash device for wearing point of view.  To address this problem,
> suggested introducing new mount option that makes less updates super blocks.
> 
> At this point, super block format itself is unchanged, still oloder
> nilfs implementation can find correct latest log in case of unclean mount.
> 
> - Rest of disk
> 
> * directory indexing
> There is long term controversial discussion about directory indexing.
> One is on memory indexing, the other is on disk indexing.  We have not
> reached a resolution, but at least agreed "unchange for now".
> So, disk format point of view, it'll be fixed for nilfs2.
> However it is a subject to change for future nilfs2 or nilfs3 or so.
> ~~
> 
> There are more missing features that should be in a modern filesystem,
> like xattr or posix acls, check ToDo list in following url:
> http://www.nilfs.org/en/current_status.html
> 
> You may not have to know disk format but if you feel functions which 
> are not in nilfs2, but mandatory to support, please state so.
> Then we can start that the how those functions can be implmented in nilfs2
> from disk format point of view.  Otherwise, any functions that requires disk
> format change will be not supported in near future or forever "experimental".
> 
> thanks,
> 
> regards,
> -- 
> Jiro SEKIBA <jir-hfpbi5WX9J54Eiagz67IpQ@public.gmane.org>

I believe part of the features like xattr (posix ACL) or atime can be
implemented later without breaking disk format compatibility (for both
forward and backward compatibility).

This sort of extension should be allowed, I think, even after the
"experimental" flag is dropped.  So, it doesn't mean fully-freezing
the disk format.  Am I on the right track?

On the other hand, the change I proposed for minimizing frequency of
super block updates may impose performance penalty or restrictions on
older implementations.  Also, it may have impact on user land tools
and the boot loader.  So, I think this one should be addressed before
dropping the "experimental" flag.

I have an idea to decrease the number of blocks written to disk also
for osync writes.  This will require adding a flag on segment headers
and a new recovery method, so let me confirm the impact.  Or, I will
insert check code preliminarily to properly reject unclean status by a
newer implementation.

Thanks,
Ryusuke Konishi
--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [CFD] disk format fixing

[Jiro SEKIBA]

Hi

At Mon, 17 May 2010 02:25:40 +0900 (JST),
Ryusuke Konishi wrote:
> 
> Hi,
> On Sun, 16 May 2010 23:42:31 +0900, Jiro SEKIBA wrote:
> > Hi,
> > 
> > I'd like to summarize the comments so far for disk fomat fix.
> > Please correct it if it's wrong or missing something.
> > 
> > 
> > I've started this thread to fix disk format of nilfs2 at the point
> > everybody thinks it's ok, strip "experimental", encourage developing
> > user land tools and different implementation like on NetBSD.
> > 
> > So far, we have been talking disk format from two aspects,
> > spuer block and rest of disk.  That's simply because most of user land tools
> > care only super block and rest of disk are much more controversial
> > than super block.  I'd like to summarize from those aspects.
> > 
> > - Super block format
> > 
> > Super blocks are frequently updated hotspot of nilfs2.  This is not good
> > for low-end flash device for wearing point of view.  To address this problem,
> > suggested introducing new mount option that makes less updates super blocks.
> > 
> > At this point, super block format itself is unchanged, still oloder
> > nilfs implementation can find correct latest log in case of unclean mount.
> > 
> > - Rest of disk
> > 
> > * directory indexing
> > There is long term controversial discussion about directory indexing.
> > One is on memory indexing, the other is on disk indexing.  We have not
> > reached a resolution, but at least agreed "unchange for now".
> > So, disk format point of view, it'll be fixed for nilfs2.
> > However it is a subject to change for future nilfs2 or nilfs3 or so.
> > ~~
> > 
> > There are more missing features that should be in a modern filesystem,
> > like xattr or posix acls, check ToDo list in following url:
> > http://www.nilfs.org/en/current_status.html
> > 
> > You may not have to know disk format but if you feel functions which 
> > are not in nilfs2, but mandatory to support, please state so.
> > Then we can start that the how those functions can be implmented in nilfs2
> > from disk format point of view.  Otherwise, any functions that requires disk
> > format change will be not supported in near future or forever "experimental".
> > 
> > thanks,
> > 
> > regards,
> > -- 
> > Jiro SEKIBA <jir-hfpbi5WX9J54Eiagz67IpQ@public.gmane.org>
> 
> I believe part of the features like xattr (posix ACL) or atime can be
> implemented later without breaking disk format compatibility (for both
> forward and backward compatibility).
> 
> This sort of extension should be allowed, I think, even after the
> "experimental" flag is dropped.  So, it doesn't mean fully-freezing
> the disk format.  Am I on the right track?

Sure, it is.  Here, I'd like to fix disk format.  Any functions
that does not break compatibility should be implemented any time.
However, if functionality requires disk format changes breaking
compatibility, it should be implemented before fixing disk format.

I think it is worth to list up functions before fixing disk format,
thinking about importance of the functionality, implementation,
and if it's important and required disk format change,
we have to decide breaking compatibility to implement those functions
before eliminating "Experimental".

thanks

regards,

> On the other hand, the change I proposed for minimizing frequency of
> super block updates may impose performance penalty or restrictions on
> older implementations.  Also, it may have impact on user land tools
> and the boot loader.  So, I think this one should be addressed before
> dropping the "experimental" flag.
>
> I have an idea to decrease the number of blocks written to disk also
> for osync writes.  This will require adding a flag on segment headers
> and a new recovery method, so let me confirm the impact.  Or, I will
> insert check code preliminarily to properly reject unclean status by a
> newer implementation.
> 
> Thanks,
> Ryusuke Konishi
> --
> To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
> the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 
> 
> 


-- 
Jiro SEKIBA <jir-hfpbi5WX9J54Eiagz67IpQ@public.gmane.org>
--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html