25

All the sites I go to look for informations on FAT16 just declaratively state that it can not allocate more than 2 GB. OK. Great. I believe you. But how do you come to that conclusion (other than just testing it)?

Is there some sort of formula one can use to determine how much a FAT16 system can hold?

SangoProductions
  • 361
  • 3
  • 6
  • 21
    There's a reason why FAT16 has a "16" in the name. :-) – Eric Lippert Apr 30 '18 at 14:21
  • 28
    @EricLippert, to be fair, the connection between that 16 and the 2 GiB isn't immediately obvious without knowing how the FS works. – Joey Apr 30 '18 at 14:51
  • 18
    I'm not 100% convinced that this question is actually on-topic for this site. Perhaps it should be moved to retrocomputing.stackexchange.com? – Jules Apr 30 '18 at 16:07
  • 3
    It's worth noting that the 2GB limit was a practical limitation of how MS-DOS and early Windows handled FAT16. It's conceptually possible to exceed 2GB, but not in a Microsoft-compatible manner. – phyrfox Apr 30 '18 at 16:30
  • 1
    @phyrfox I don't know why such an incorrect comment has so many upvotes. **Later Windows support 4GB FAT16 partitions without problem**: [Max. volume size 2 GiB (with 32 KiB clusters) 4 GiB (with 64 KiB clusters) (NT 4, PTS-DOS, EDR-DOS)](https://en.wikipedia.org/wiki/File_Allocation_Table#Final_FAT16). Just plug a 4GB USB stick in and see – phuclv May 01 '18 at 05:46
  • 3
    @LưuVĩnhPhúc The comment is correct. I did say "MS-DOS and early Windows." Modern systems can use more than 2GB in FAT16. A 4GB FAT16 partition won't work in old MS-DOS/Win3.1 systems, for example. And many sources that stated that 2GB was the limit was either because they were written when that limit was a reality, or the time shortly afterwards, where you were advised not to because slightly older systems couldn't handle it. Later systems can handle it just fine, but the 2GB limit was the rule of thumb before about 2000 or so, and next few years after that quoting the old, outdated limits. – phyrfox May 01 '18 at 05:58
  • 1
    @Jules I also don't think this belongs here, but imho it's a better fit on superuser (FAT16 _is_ ancient, but I tend to see it pop up now and then, unfortunately) – Luke May 01 '18 at 15:33

2 Answers2

65

FAT16 uses 16 bits to identify clusters. Thus there are a maximum of 65536 clusters before you run out of identifiers, and some identifiers are reserved for non-file uses. Each file occupies at least one cluster. Larger clusters increases the minimum allocation per file, increasing the overhead of small files.

The cluster size then tells you the maximum identifiable volume. For 32KiB clusters, that is 32 * 1024 * 65536 B = 2GiB.

You could increase the cluster size indefinitely, by increasing the size of your on-disk sectors, but you remain limited to the maximum number of files. You would also run into issues with software that assumed the default sector size (512B)

At the point where there were physical volumes of ~2GiB readily available, processors and OSs were 32bit, so moving to FAT32 was a sensible choice, allowing vastly more files in small clusters

Caleth
  • 10,519
  • 2
  • 23
  • 35
  • 4
    "but increase the overhead for small files" Not sure if that will be clear for everyone, as I'm not sure everyone will understand what's meant by "overhead" in this context. I think an example would help: "For example, a file with one character in it takes up 1 cluster on disk, most of which is completely wasted. Larger cluster sizes means more waste." – Reginald Blue Apr 30 '18 at 14:50
  • 3
    A couple of clarifying notes: 32KiB was the maximum cluster size for various versions of DOS and Windows, But the Windows NT family has supported larger cluster sizes since NT 4.0 (and therefore consumer versions of Windows since XP have also supported it, as they're based on the NT kernel). This allows sizes up to 16GiB, although due to the inefficiency as noted in the answer this is unlikely to be useful. You could *plausibly* use such a system if you wanted to store predominantly large files, especially if they came in multiples of the 256KiB cluster size you would have to use... – Jules Apr 30 '18 at 15:59
  • 5
    ... but then you'd likely hit the next limit, which is a problem for both FAT16 and FAT32: the maximum file size is limited to 1 byte short of 4GiB by the fact that there are only 4 bytes allocated to storing it in directory entries. OTOH, if you happened to have a need to store a large-ish number of files in sizes of around 256KiB up to 2GiB with power-of-two sizes, and total size < 16GiB, FAT16 is potentially the most efficient format for them. – Jules Apr 30 '18 at 16:01
  • @Jules: Only potentially. Remember that there is a per-cluster-overhead. File-systems allowing storing runs are more efficient if there's little fragmentation. – Deduplicator Apr 30 '18 at 19:33
12

There were actually several variants of "FAT16" over the years with different limits but lets consider the version that persisted from "compaq DOS 3.31" through to windows 95.

FAT volumes are divided into clusters. Each cluster is made up of a power of two number of sectors. The number of sectors per cluster on FAT16 is stored as an 8 bit signed number. So the maximum possible sectors per cluster is 64.

Cluster numbers were stored as a 16 bit unsigned value. Limiting total clusters to 65536. Multiply that by the maximum sectors per clusters and you get a limit of 4194304 sectors.

The (logical) sector size of hard drives is 512 bytes. Multiply that by the limit on the number of sectors mentioned above and you get your 2GiB limit. In priciple a medium with larger sector sizes can support a larger FAT16 volume but I don't think this happened in practice.

Windows NT changed the interpretation of the "sectors per cluster" field to be unsigned 8 bit. This allowed a 4GiB FAT16 partition with 512 byte sectors (and theoretically larger on drives with bigger sectors). AIUI windows 98 added support for reading and writing such partitions but it couldn't create them and it's disk utilities couldn't repair them.

It would have certainly been possible to make relatively minor tweaks to the filesystem format to support larger clusters and hence larger volumes. However MS decided to go for the more radical option of moving to a 32-bit cluster index with windows 95 OSR2 producing FAT32.

I belive the reason for going for the more radical option was space efficiency. Given typical filesizes at the time 32kiB clusters were already pretty wasteful and larger ones would have been even move so.

Peter Green
  • 2,125
  • 9
  • 15
  • 4
    I had to think hard at the "maximum possible sectors per cluster is 64", until I got it: 64 is indeed the largest power-of-2 you can represent in a signed byte: 128 isn't possible as the maximum positive signed byte value is 127. – Ralf Kleberhoff May 01 '18 at 10:28
  • 3
    @RalfKleberhoff That does naturally lead to a followup question, though: if you're storing a power of two, why store the number itself rather than the exponent on the two? – Daniel Wagner May 01 '18 at 12:27
  • @DanielWagner I absolutely agree. Especially as back then when FAT16 was created, shifting was definitely a cheaper operation than multiplying. But probably they were just happy to get it running, and not software-engineering it for decades into the future... – Ralf Kleberhoff May 01 '18 at 13:04