[syslinux] [PATCH 1/5] fat: fix minfatsize for large FAT32
Pete Batard
pete at akeo.ie
Thu Feb 25 16:59:02 PST 2016
Hi Ady,
Your insightful post prompted me to to a little bit more digging as to
how the Ridgecrop algorithm computed its FAT size, with the result of my
investigations presented below.
NB: For those who don't want to go through this whole part, there's a
TL;DR near the end.
For reference, the computation of the FAT size all done in the
GetFATSizeSectors(), the code of which is at [1] (Rufus' version hasn't
been altered from Ridegcrop's). When this code is ran against the same
disk and same parameters as we've been using for our example, and with
some debugging of the variables enabled, you'll see the following output:
-----------------------------------------------------------------------
DskSize = 195369519, ReservedSecCnt = 32, SecPerClus = 64, NumFATs=2,
BytesPerSect = 512
Numerator = 4 * (195369519 - 32) = 781477948
Denominator = (64 * 512) + (4 * 2) = 32776
FatSz = (781477948 / 32776) + 1 = 23843
-----------------------------------------------------------------------
Now, the algorithm mentions that this computation is based on a formula
by Rune Moeller Barnkob from [2], but that page no longer exists.
Digging around seems to provides a copy of the same content at [3]
however (where we find that the original page dealt with FAT16), with
the part of interest to us being the one with the computation, starting at:
-----------------------------------------------------------------------
Assume:
To is the total amount of sectors,
Fo is the amount of free sectors for data
Fs is the size of one FAT in sectors
Cs is the cluster size
Ss is the sector size
Rs is the reserved sectors before the FAT's
Re is the entries in the root-directory
Ds is the size of a entry (=32 bytes)
(...)
-----------------------------------------------------------------------
Now, even though this is a FAT16 computation, I think I was able to work
out how Tom Thornhill of Ridgecrop got his FAT32 equivalent, which was
probably as follows:
-----------------------------------------------------------------------
Assume:
To is the total amount of sectors,
Fo is the amount of free sectors for data
Fs is the size of one FAT in sectors
Cs is the cluster size
Ss is the sector size
Rs is the reserved sectors before the FAT's
Re is the entries in the root-directory
Fe is the FAT element size
Nf is the number of FATs
The size of the FAT must equal the free amount of sectors divided by the
cluster size in sectors multiplied by the FAT element size divided by
the sector size (the rounding up can be done later).
Fo * Fe
Fs = -------
Cs * Ss
The free amount of sectors must be the total amount minus the FAT's and
the Reserved Sectors. We'll assume the Root Directory takes no space,
which is something that Ady mentioned and is safe to do anyway, as this
will maximize the amount of free sectors we consider in our computation.
Fo = To - (Nf * Fs) - Rs
If we solve that:
Fe * ( To - (Nf * Fs) - Rs )
Fs = ----------------------------
Cs * Ss
Fs * (Cs * Ss) = (Fe * To) - (Fe * Nf * Fs) - (Fe * Rs)
(Fs * Cs * Ss) + (Fs * Fe * Nf) = (Fe * To) - (Fe * Rs)
Fs * ( (Cs * Ss) + (Fe * Nf)) = Fe * (To - Rs)
Fe * (To - Rs)
Fs = ---------------------
(Cs * Ss) + (Fe * Nf)
We end up with the Numerator and Denominator used by GetFATSizeSectors():
Numerator = FatElementSize * (DskSize - ReservedSecCnt)
Denominator = (SecPerClus * BytesPerSect) + (FatElementSize * NumFATs)
Then +1 is added to the FAT Size for rounding.
-----------------------------------------------------------------------
However, as Ady demonstrated, this computation doesn't actually work
because it leaves unaddressable sectors.
So let us instead try to follow Ady's post, to derive a proper
algorithm. First, let me quote the relevant part:
On 2016.02.25 20:49, Ady via Syslinux wrote:
> _ Bytes per Sector: 512
> _ FAT Entries per Sector: 128
> _ Reserved Sectors: 32
> _ Volume's Total Sectors: 195'369'519
> _ Sectors per Cluster: 64
> _ Amount of FATs: 2
> _ Root Directory Sectors: 0 (please keep reading)
> Sectors per FAT: 23843
>
> With this Sectors_per_FAT value, the corresponding
>
> Maximum FAT entries:
> 23843 * 128 = 3'051'904
>
> Since the first 2 FAT entries are reserved, then the corresponding
>
> Maximum Amount of Clusters:
> 3'051'904 - 2 = 3'051'902
>
> The amount of Sectors in the Data Area corresponding to such amount of
> Clusters is:
>
> Maximum Amount of "Allocatable Sectors" (please allow me to use such
> uncommon expression, for brevity):
> 3'051'902 * 64 = 195'321'728
>
> So we have, for 23843 Sectors_per_FAT in our example:
> 32 + 23843 * 2 + 195'321'728 = 195'369'446 Sectors
>
> When comparing this value with the 195'369'519 Volume's Total Sectors:
> 195'369'519 - 195'369'446 = 73 Sectors
>
> This means that with 23843 Sectors_per_FAT in our FAT32 volume, we
> would have 73 unused / unusable sectors.
I'm going to use the same variable names as previously, with just an
additional intermediate one added:
------------------------------------------------------------------------
Assume:
To is the total amount of sectors,
Fo is the amount of free sectors for data
Fs is the size of one FAT in sectors
Cs is the cluster size
Ss is the sector size
Rs is the reserved sectors before the FAT's
Re is the entries in the root-directory
Fe is the FAT element size
Nf is the number of FATs
MaxFE is the maximum number of FAT entries
As with the post above, we'll start with that last variable, since it is
the one that is crucial to getting our computation right:
MaxFatEn = Fs * Ss / Fe
Now, if we follow Ady's post to compute the total number of sectors
addressable, we want to have that number greater than the number of
sectors reported for the volume, hence:
(MaxFatEn - Nf) * Cs + Nf * Fs + Rs >= To
Let's replace MaxFatEn:
((Fs * Ss / Fe) - Nf) * Cs + Nf * Fs + Rs >= To
Now of course, we want to isolate the FAT Size (Fs) since that's what
we're after:
(Fs * Ss * Cs / Fe) - (Nf * Cs) + (Fs * Nf) + Rs >= To
Fs * (Ss * Cs / Fe + Nf) >= To - Rs + (Nf * Cs)
Fs >= (To - Rs + Nf * Cs) / (Ss * Cs / Fe + Nf)
Thus we can finally get a formula for Fs that satisfies the above:
Fs = (To - Rs + Nf * Cs) / ((Ss * Cs / Fe) + Nf) + 1
------------------------------------------------------------------------
That's quite different from the earlier formula.
However, it *does* yield the expected result of 23844, instead of 23843:
------------------------------------------------------------------------
DskSize = 195369519, ReservedSecCnt = 32, SecPerClus = 64, NumFATs=2,
BytesPerSect = 512
Numerator = 195369519 * 32 + 2 * 64 = 195369615
Denominator = 64 * 512 / 4 * 2 = 8194
FatSz = (195369615 / 8194) + 1 = 23844
------------------------------------------------------------------------
*TL;DR*: The Ridgecrop Fat Size computation algorithm is wrong, and,
whether justified or not, the existing Syslinux check does catch FATs
that are missing addressable sectors.
I have now tested the new computation against a 320GB and 1TB drive, and
found that the original minfatsize check of Syslinux is no longer an issue.
This being said, and to address Ady's subsequent point:
While I can now address the issue in Rufus (and will contact Tom
Thornhill of Ridgecrop to let him know about both the issue & fix), I
suspect there are users out there who are using and will continue to use
fat32format.exe with the bad computation algorithm, as well as other
developers who might lift the existing Large FAT32 format code without
realizing that doing so will break Syslinux installation. So it may
still be worth relaxing the check especially if, as Ady pointed out, not
having all sectors addressable doesn't make a disk any less valid.
Regards,
/Pete
[1]
https://github.com/pbatard/rufus/blob/ade5639c0047ee813f71a8bfef8b1cc7be551009/src/format.c#L349-L377
[2] http://hjem.get2net.dk/rune_moeller_barnkob/filesystems/fat.html
[3] http://pierrelib.pagesperso-orange.fr/filesystems/fat16.html
More information about the Syslinux
mailing list