FAT32 superiority over ext2 :-)

FAT32 superiority over ext2 :-)

[Albert D. Cahalan]

By dumb luck (?), FAT32 is compatible with the phase-tree algorithm
as seen in Tux2. This means it offers full data integrity.
Yep, it whips your typical journalling filesystem. Look at what
we have in the superblock (boot sector):

    __u32  fat32_length;  /* sectors/FAT */
    __u16  flags;         /* bit 8: fat mirroring, low 4: active fat */
    __u8   version[2];    /* major, minor filesystem version */
    __u32  root_cluster;  /* first cluster in root directory */
    __u16  info_sector;   /* filesystem info sector */

All in one atomic write, one can...

1. change the active FAT
2. change the root directory
3. change the free space count

That's enough to atomically move from one phase to the next.
You create new directories in the free space, and make FAT
changes to an inactive FAT copy. Then you write the superblock
to atomically transition to the next phase.

Re: FAT32 superiority over ext2 :-)

[Daniel Phillips]

On Monday 25 June 2001 00:54, Albert D. Cahalan wrote:
> By dumb luck (?), FAT32 is compatible with the phase-tree algorithm
> as seen in Tux2. This means it offers full data integrity.
> Yep, it whips your typical journalling filesystem. Look at what
> we have in the superblock (boot sector):
>
>     __u32  fat32_length;  /* sectors/FAT */
>     __u16  flags;         /* bit 8: fat mirroring, low 4: active fat */
>     __u8   version[2];    /* major, minor filesystem version */
>     __u32  root_cluster;  /* first cluster in root directory */
>     __u16  info_sector;   /* filesystem info sector */
>
> All in one atomic write, one can...
>
> 1. change the active FAT
> 2. change the root directory
> 3. change the free space count
>
> That's enough to atomically move from one phase to the next.
> You create new directories in the free space, and make FAT
> changes to an inactive FAT copy. Then you write the superblock
> to atomically transition to the next phase.

Yes, FAT is what inspired me to go develop the algorithm.  However, two 
words: 'lost clusters'.  Now that may just be an implemenation detail ;-)

--
Daniel

Re: FAT32 superiority over ext2 :-)

[Albert D. Cahalan]

Daniel Phillips writes:
> On Monday 25 June 2001 00:54, Albert D. Cahalan wrote:

>> By dumb luck (?), FAT32 is compatible with the phase-tree algorithm
>> as seen in Tux2. This means it offers full data integrity.
>> Yep, it whips your typical journalling filesystem. Look at what
>> we have in the superblock (boot sector):
>>
>>     __u32  fat32_length;  /* sectors/FAT */
>>     __u16  flags;         /* bit 8: fat mirroring, low 4: active fat */
>>     __u8   version[2];    /* major, minor filesystem version */
>>     __u32  root_cluster;  /* first cluster in root directory */
>>     __u16  info_sector;   /* filesystem info sector */
>>
>> All in one atomic write, one can...
>>
>> 1. change the active FAT
>> 2. change the root directory
>> 3. change the free space count
>>
>> That's enough to atomically move from one phase to the next.
>> You create new directories in the free space, and make FAT
>> changes to an inactive FAT copy. Then you write the superblock
>> to atomically transition to the next phase.
>
> Yes, FAT is what inspired me to go develop the algorithm.  However, two
> words: 'lost clusters'.  Now that may just be an implemenation detail ;-)

What lost clusters?

Set bit 8 of "flags" (A_BF_BPBExtFlags to Microsoft) to disable
FAT mirroring. Then the low 4 bits are a 0-based value that
indicates which copy of the FAT should be used.

Assume we have 2 copies of the FAT, as is (was?) common. I'll call
them X and Y. When we mount the filesystem, we disable FAT mirroring
and mark FAT X active.

Now we can make changes to FAT Y without affecting filesystem
integrity. Windows will not use FAT Y. As is usual with the
phase-tree algorithm, we use free space to create a new structure
beside the old one.

Time for a phase change:

We have FAT Y, currently inactive, updated on disk.
FAT X is active; it describes the current on-disk state.
We have a new root directory on disk, sitting in free space.
We have a new filesystem info sector on disk, sitting in free space.

We write one single sector, then:

FAT X becomes inactive, and will not be used by Windows.
FAT Y becomes active; it describes the new on-disk state.
The old root directory is marked free in FAT Y. Good!
The old filesystem info sector is marked free in FAT Y. Good!

Once the superblock goes to disk, FAT X may be written to.

Re: FAT32 superiority over ext2 :-)

[Daniel Phillips]

On Monday 25 June 2001 01:49, Albert D. Cahalan wrote:
> Daniel Phillips writes:
> > On Monday 25 June 2001 00:54, Albert D. Cahalan wrote:
> >> By dumb luck (?), FAT32 is compatible with the phase-tree algorithm
> >> as seen in Tux2. This means it offers full data integrity.
> >> Yep, it whips your typical journalling filesystem. Look at what
> >> we have in the superblock (boot sector):
> >>
> >>     __u32  fat32_length;  /* sectors/FAT */
> >>     __u16  flags;         /* bit 8: fat mirroring, low 4: active fat */
> >>     __u8   version[2];    /* major, minor filesystem version */
> >>     __u32  root_cluster;  /* first cluster in root directory */
> >>     __u16  info_sector;   /* filesystem info sector */
> >>
> >> All in one atomic write, one can...
> >>
> >> 1. change the active FAT
> >> 2. change the root directory
> >> 3. change the free space count
> >>
> >> That's enough to atomically move from one phase to the next.
> >> You create new directories in the free space, and make FAT
> >> changes to an inactive FAT copy. Then you write the superblock
> >> to atomically transition to the next phase.
> >
> > Yes, FAT is what inspired me to go develop the algorithm.  However, two
> > words: 'lost clusters'.  Now that may just be an implemenation detail ;-)
>
> What lost clusters?
>
> Set bit 8 of "flags" (A_BF_BPBExtFlags to Microsoft) to disable
> FAT mirroring. Then the low 4 bits are a 0-based value that
> indicates which copy of the FAT should be used.
>
> Assume we have 2 copies of the FAT, as is (was?) common. I'll call
> them X and Y. When we mount the filesystem, we disable FAT mirroring
> and mark FAT X active.
>
> Now we can make changes to FAT Y without affecting filesystem
> integrity. Windows will not use FAT Y. As is usual with the
> phase-tree algorithm, we use free space to create a new structure
> beside the old one.
>
> Time for a phase change:
>
> We have FAT Y, currently inactive, updated on disk.
> FAT X is active; it describes the current on-disk state.
> We have a new root directory on disk, sitting in free space.
> We have a new filesystem info sector on disk, sitting in free space.
>
> We write one single sector, then:
>
> FAT X becomes inactive, and will not be used by Windows.
> FAT Y becomes active; it describes the new on-disk state.
> The old root directory is marked free in FAT Y. Good!
> The old filesystem info sector is marked free in FAT Y. Good!
>
> Once the superblock goes to disk, FAT X may be written to.

When can we expect the patch?

--
Daniel

Re: FAT32 superiority over ext2 :-)

[Juri Haberland]

In article <0106250203070J.00430@starship> you wrote:
> On Monday 25 June 2001 01:49, Albert D. Cahalan wrote:
>> Daniel Phillips writes:
>> > On Monday 25 June 2001 00:54, Albert D. Cahalan wrote:
>> >> By dumb luck (?), FAT32 is compatible with the phase-tree algorithm
>> >> as seen in Tux2. This means it offers full data integrity.
>> >> Yep, it whips your typical journalling filesystem. Look at what
>> >> we have in the superblock (boot sector):
>> >>
>> >>     __u32  fat32_length;  /* sectors/FAT */
>> >>     __u16  flags;         /* bit 8: fat mirroring, low 4: active fat */
>> >>     __u8   version[2];    /* major, minor filesystem version */
>> >>     __u32  root_cluster;  /* first cluster in root directory */
>> >>     __u16  info_sector;   /* filesystem info sector */
>> >>
>> >> All in one atomic write, one can...
>> >>
>> >> 1. change the active FAT
>> >> 2. change the root directory
>> >> 3. change the free space count
>> >>
>> >> That's enough to atomically move from one phase to the next.
>> >> You create new directories in the free space, and make FAT
>> >> changes to an inactive FAT copy. Then you write the superblock
>> >> to atomically transition to the next phase.

[--snip--]

> When can we expect the patch?

Don't! Blasphemy!!!

Juri ;-) 

-- 
Juri Haberland  <juri@koschikode.com>