fat_size_calculation.tex

   1 %  Copyright 2003,2005,2007 Alain Knaff.
   2
   3 % This documentation is for Mtools which is a collection of tools to
   4 % allow Unix systems to manipulate MS-DOS files.
   5
   6 % Permission is granted to copy, distribute and/or modify this document
   7 % under the terms of the GNU Free Documentation License, Version 1.3 or
   8 % any later version published by the Free Software Foundation; with no
   9 % Invariant Sections, with no Front-Cover Texts, and with no Back-Cover
  10 %Texts.  A copy of the license is included in the section entitled
  11 % ``GNU Free Documentation License''.
  12
  13 \documentclass[a4paper,12pt]{article}
  14
  15 \usepackage[T1]{fontenc}
  16 \usepackage[latin1]{inputenc}
  17 \usepackage{pslatex}
  18 \usepackage[pdfpagemode=None,colorlinks]{hyperref}
  19
  20 \author{Alain Knaff}
  21 \title{How mformat-3.9.10 and above calculates needed FAT size}
  22
  23 \begin{document}
  24
  25 \maketitle
  26
  27 This small document explains the formula used by {\tt mformat.c} to
  28 figure out fat size and number of clusters. Due to the way that
  29 filesystem parameters are stored in the boot sector, we can afford to
  30 have a FAT that is larger than need to be to accomodate the clusters
  31 present on disk, but under no circumstances can we have one that is
  32 too small.
  33
  34 In this discussion, we use the following variable names:
  35
  36 \begin{tabular}{|r|p{12cm}|}
  37
  38 \hline
  39
  40 $fatNybls$&
  41 Number of nubbles (4 bit unit per FAT). This is 3 for FAT12, 4 for
  42 FAT16, and 8 for FAT16\\
  43
  44 \hline
  45
  46 $numClus$&
  47 Number of clusters on the disk\\
  48
  49 \hline
  50
  51 $clusSiz$&
  52 Size of a cluster, expressed in sectors\\
  53
  54 \hline
  55
  56 $secSiz$&
  57 Size of a sector, in bytes. Size of a sector in nybbles is $secSiz$ * 2\\
  58
  59 \hline
  60
  61 $nfats$&
  62 Number of FAT copies, usually two\\
  63
  64 \hline
  65
  66 $remSects$&
  67 ``Remaining sectors'', after number of boot sectors and root directory
  68 have been accounted for\\
  69
  70 \hline
  71
  72 $fatLen$&
  73 Length of the FAT, in sectors\\
  74
  75 \hline
  76
  77
  78 \end{tabular}
  79
  80
  81 Taking into account both data and fat, each cluster takes up the
  82 following number of nybbles (units of 4 bytes):
  83
  84
  85 $$clusSiz * (2*secSiz)  + nfats * fatNybls$$
  86
  87 This accounts for the data of the cluster ($clusSiz * secSiz$),
  88 as well as for the space taken up by its descriptor.
  89
  90 The space taken up by all clusters together, plus the space taken by
  91 descriptors for clusters 0 and 1 ($2*nfats*fatNybls$) should be less
  92 than what is available.
  93
  94 Additional sectors may be lost due to slack (you have to use a full
  95 FAT sector, you also have to use a full cluster in the data
  96 area). Thus, an {\em upper bound} for the number of clusters is as
  97 follows:
  98
  99 $$
 100 numClus \le  {2*remSect*secSiz - 2*nfats*fatNybls \over
 101 2*clusSiz*secSiz + nfats*fatNybls}
 102 $$
 103
 104
 105 $$
 106 numClus \le {(remSect+2*clusSiz)*2*secSiz \over
 107 2*clusSiz*secSiz + nfats*fatNybls} - 2
 108 $$
 109
 110
 111 These will take up at most the following space in one copy of the FAT
 112 (we have to round up, because even a half-full fat sector must be
 113 taken in its entirety)
 114
 115 $$
 116 fatLen \le \left\lceil {  (numClus+2)*fatNybls \over secSiz * 2 } \right\rceil
 117 $$
 118
 119
 120 $$
 121 fatLen \le \left\lceil {
 122 \left( { 2*(remSect+2*clusSiz)*secSiz \over
 123 2*clusSiz*secSiz + nfats*fatNybls} \right) * fatNybls \over
 124 2*secSiz
 125 } \right\rceil
 126 $$
 127
 128
 129 $$
 130 fatLen \le \left\lceil {
 131 (remSect+2*clusSiz)* fatNybls \over
 132 2*clusSiz*secSiz + nfats*fatNybls
 133 } \right\rceil
 134 $$
 135
 136 The space left after FAT sector has been deduced is now {\em less than
 137 or equal} to what would be needed for the data area of the clusters
 138 (including fractional clusters), which is good, as we may have under
 139 no circumstances {\em more} clusters in the data area than in the FAT.
 140 An important point in this calculation is that we based the needed FAT
 141 size on a {\em fractional} number of clusters, rather than a rounded
 142 down amount of clusters. Indeed, using a rounded down number could
 143 have exposed us to a situation where we had an {\em almost enough}
 144 space for one more cluster (i.e. not enough space for data + FAT, but
 145 enough for data alone). This situation, combined with a situation
 146 where the last FAT sector was flush full could have lead to a
 147 situation where $numClus$ would become too large for the FAT to
 148 accomodate. I think this is clearer with an example:
 149 \begin{itemize}
 150 \item $remSect=4127$, $clusSiz=1$, $nfats=1$
 151 \item (Non rounded down) $numClus={(4127+2)*(1024) \over 1032} -
 152 2 =4094.992$
 153 \item Rounded down: 4094 clusters
 154 \item These fit into 16 FAT sectors, exactly
 155 \item ... leaving us 4095 clusters, which is one to many (because
 156 these 4095 clusters would now need 17 FAT clusters)
 157 \end{itemize}
 158
 159 Keeping the fractional part (0.992) allows us to round {\em up} the
 160 needed number of FAT sectors to 17, nicely solving this problem.
 161
 162 The downside of counting the fractional part however is that we quite
 163 often waste a sector in the really common situation where both $nfats$
 164 and $clusSiz$ are even, while $remSect$ is odd. An easy way to address
 165 this is to substract one from $remSect$ before application of the
 166 formula, if this case is detected. Such operation carries no risk, as
 167 the odd final sector cannot be used to make a full cluster.
 168
 169 There is still a case however, where fatLen must be grown manually
 170 after application of the formula: If numClus exceeds the maximum
 171 number of clusters allowable for FAT12 or FAT16), we need to shrink
 172 $numClus$ after application of the formula, and manually make the FAT
 173 larger in order to take up any excess space.
 174
 175 Also note that as we used upper bounds, we may waste a certain number
 176 of sectors, which an exact calculation may not have wasted. However,
 177 normally, we should not lose more than one sector per FAT copy.
 178
 179 N.B. In its document at \url{http://www.microsoft.com/hwdev/download/hardware/fatgen103.pdf},
 180 Microsoft proposes a much simpler formula. However, this formula is
 181 both wrong (i.e. occasionally it produces a smaller FAT than is
 182 needed for the clusters on disk), less generic (only works for sector
 183 sizes equal to 512), and less efficient (in case of FAT32, it may
 184 waste up to 8 sectors!)
 185
 186 The formula is the following (for FAT16):
 187 $$
 188 fatLen \le \left\lceil { remSect \over 256 * clusSiz + nfats} \right\rceil
 189 $$
 190
 191 Note that it doesn't account for the dummy clusters 0 and 1. Thus, if
 192 we have 258 sectors remaining, with a cluster size of 1, and two FAT
 193 copies, the Microsoft formula mistakenly assumes fatLen = 1. This
 194 leaves 258 - 2 = 256 sectors for clusters, which yields 256 clusters.
 195 However, those clusters do not fit into the FAT, as two clusters are
 196 lost (0 and 1). However, to Micro\$ofts' credit, this is not actually
 197 the formula they're using (tested with $remsect=160056$ and
 198 $clusSize=4$), so this seems to be a documentation issue rather than a
 199 genuine bug.
 200
 201 In case of FAT32, Microsoft just halves the denominator. This is
 202 wasteful, as only the $256*clusSiz$ part would need to be halved.
 203
 204 If we assume 16777000, and a cluster size of 8, our formula would give
 205 us:
 206 $$fatLen = \left\lceil (16777000 + 16) * 8 \over 2 * 8 * 512 + 16
 207 \right\rceil = 16352$$
 208 This would leave $16777000-2*16352=16744296$ sectors for the clusters,
 209 i.e. 2093037 clusters. The FAT descriptors for those 2093037 clusters
 210 do indeed fit into our 16352 fat sectors.
 211
 212 Microsoft, on the other hand, would get: $$fatLen = \left\lceil{
 213 16777000 \over (256 * 8 + 2)/2} \right\rceil = 16368$$ This would only
 214 leave $16777000-2*16368=16744264$, i.e. 2093033 clusters, thus wasting
 215 4 clusters. The FAT would be 28 sectors too big, i.e. more than the
 216 mere 8 sectors announced by Microsoft! Unfortunately, I currently
 217 don't have access to any sufficiently recent Windows to check out
 218 whether this really happens in the code, or whether it is only a
 219 documentation issue as well.
 220
 221 Oh, and before somebody points it out: the formula in this document
 222 occassionnally wastes sectors too, although not as much (Example: With
 223 $remsect=685$, $clusSiz=1$ and $nfats=2$ our formula gives $fatLen=3$,
 224 which leaves 679 clusters. However, we could use $fatLen=2$, leaving
 225 681 clusters,
 226
 227 \end{document}