4 ms·

Lessons from Ancient File Systems

115 points by zdw 2y ago

bediger4000 2y ago
This is the type of analysis I always hope for about file systems, but almost never see. Looks like some of these file systems had linked list files, which is an interesting contrast to inode based file systems like the original UFS, or BSD FFS.
- jhallenworld 2y ago
  Perhaps they did it to save RAM since you are buffering the current sector anyway. An alternative is CP/M's extent-based filesystem, where the meta-data is all in the directory entry. But I think space allocation algorithm is more complex for it. I like the OS/8 file allocation scheme: files are always contiguous. Only one growing file can be open for writing and it allocates space out of the contiguous free space (actually it owns all of the free space until the file is closed, where the unused space is then given back). If you run out of disk space, you have to compact the disk, eliminating space taken up by deleted files. I like it because it's illustrates the surprising fact that you can get away with only one file open for writing for most things.
  - Someone 2y ago
    > I like it because it's illustrates the surprising fact that you can get away with only one file open for writing for most things. https://en.wikipedia.org/wiki/CP/M#CP/M_Plus https://en.wikipedia.org/wiki/CP/M#CP/M_Plus: “The last 8-bit version of CP/M was version 3, often called CP/M Plus, released in 1983. Its BDOS was designed by Brown. It incorporated the bank switching memory management of MP/M in a single-user single-task operating system compatible with CP/M 2.2 applications” Note the “single task” part. That excludes a lot from what we nowadays would be included in “most things”. That, I think, is the reason you could get away with that. I also would guess it was more that programmers would either not know what they missed or accepted it as a limitation that kept the OS small.
  - inkyoto 2y ago
    On the modern hardware (i.e. SSD's) files are always «contiguous», thanks to the transparent block remapping in the SSD firmware. Compacting/squeezing was only necessary because magnetic disks were contiguous in their nature and had to be erased and rewritten, which was a time consuming (sometimes very time consuming) and potentially dangerous operation leading to a complete data loss if power flickered. To a certain extent, the compacting is still there and is done in the SSD's (now called «garbage collection»), although it is also transparent to the user and to the operating system.
- jdougan 2y ago
  This might scratch that itch aloso. Beneath Apple DOS: https://mirrors.apple2.org.za/Apple%20II%20Documentation%20Project/Books/Beneath%20Apple%20DOS.pdf https://mirrors.apple2.org.za/Apple%20II%20Documentation%20P...
jftuga 2y ago
Conclusion: "So the big lesson here is to always plan for the future. Listen to the requirements for the current product, but then design with the assumption that you'll be asked to expand the requirements in the future. If you don't, users may be cursing you when the code is released. But who knows? If you do it right, people may still be using your code in 40 years."
- saulpw 2y ago
  Unfortunately, "plan for the future" is too general to be workable; this is how you get architecture astronauts using UUIDs and multiple levels of indirection for a 160KB floppy. The future you can plan for, is specifically 10x more. If you have 160KB floppies, then design as though there might be 1.6MB floppies. You'll have to revisit your design anyway for the emergent complexities of the next order of magnitude, but this will at least give you some breathing room. Designing for 100x more than your system has is overengineering. You have no idea what the needs of the future are, and the design for a 100x system will be detrimental for your current 1x system, and likely sink it. So ironically planning for 100x means you probably won't get there.
  - antonkochubey 2y ago
    Windows XP lived thorough 6 GB (minimum requirement - 1.5 GB, but I don't recall seeing drives less than six gigs at the time) to 2 TB HDD's. That's literally a 333x increase, which NTFS handled just fine. From min requirement it'd be a 1000x increase.
    - akira2501 2y ago
      > That's literally a 333x increase Yet that's only going from 2^32 to 2^40.
    - jeroenhd 2y ago
      Windows XP's default clustering (well, until SP2 at least) "only" allowed for 128GB disks. The cluster size was later increased. The 2TB limit was generally a limit for the BIOS code rather than an OS limit, as NTFS will happily scale beyond 2TB. Windows NT 4 already contained the code necessary to allow for up to 16 exabyte partitions (https://web.archive.org/web/20010208131204/http://support.microsoft.com/support/kb/articles/Q224/5/26.ASP https://web.archive.org/web/20010208131204/http://support.mi...), but the hardware it was running on probably didn't support anything bigger than a few terabytes. Sure, every text file takes up at least 2MB, but with an exabyte disk, you probably don't care about wasting sectors like that.
kristopolous 2y ago
How are the design intentionalities determined? Are they documented somewhere? I'm not disputing anything, I just want to know the provenance in case there's some really great book or code I should be reading.
- pwg 2y ago
  The book "Inside Atari DOS" by Bill Wilkinson (author of Atari DOS) goes into some of the rationale: https://www.atariarchives.org/iad/ https://www.atariarchives.org/iad/
skissane 2y ago
> Instead, it was to support "note" and "point" commands. Atari believed people would use files as a database, and with the sector chaining, it was impossible to jump around in a file without reading it linearly. So a program could "note" its position in a file (sector and offset) and then return there later with the point command. This is where verifying that the file number in the user-supplied sector number matched the entry used when opening the file came in. Without that number, there would be no verification that a "point" would end up in the right file. Interesting to hear this terminology used in the context of 8-bit Atari computers. The terms NOTE and POINT come from IBM mainframes, where there are OS/360 macros by those names. NOTE essentially does an fgetpos and POINT an fsetpos
- jhallenworld 2y ago
  It answers the question of where experienced programmers then got their experience. In the mid 70s, Sigma-7 was another popular 32-bit machine, but I don't know anything about its OS.
mrandish 2y ago
Brings back fond memories of the Amiga DOS floppy disk structure which had some clever things I hadn't seen before (coming from 8-bit ROM-based floppy disk OSes). Such as having each file sector link to the next so if the file allocation table got corrupted, the files on the disk could be recovered by a utility that crawled every sector and rebuilt a new file allocation table. IIRC, it also would occasionally write a backup copy of the file allocation table on another normally unused track as well as parking the disk head away from the track where the directory was after some default period of inactivity. Floppy drives were notorious for occasionally crashing the heads into whatever track they happen to be over if there was a power glitch or software crash - and of course, statistically, they spent most of their time over the directory track, thus greatly increasing to odds of blasting part of the file allocation table. When I moved to PCs I remember being surprised that NTFS didn't seem to do any of this (at least early on) despite being more recent and supposedly advanced.
- obarthel 2y ago
  The Amiga default file system was not quite that sophisticated. As used on floppy disks, it did well by offering more than one option to reconstruct the layout of the file system data structures. For example, the disk data blocks were chained, so that you could follow this chain and find every block belonging to the same file. But you could also follow the chain of the associated file list blocks and obtain the same information. Which disk blocks were still available for allocation was tracked by the bitmap (never documented in the original AmigaDOS Manuals), a series of blocks in which each bit stood for an individual block which was either allocated or not. There is just one bitmap for the entire volume and the Amiga default file system did not care for redundancy. The bitmap does not even use block checksums because you could reconstruct it at any time by following the directory structures (unless the bitmap was corrupted and spread its troubles, which you would never suspect or know). This is what, as a by-product, the Disk-Validator accomplished in the Kickstart 1.x days. The floppy disk version of the Amiga default file system made use of checksums for each of its data structures, with the exception of the bitmap. This made it slow going, but then you quickly learned of defects which the file system reported. Fun fact: the Amiga default file system in the Kickstart 1.x days was particularly and likely needlessly slow during directory scanning. The metadata produced by the scanning API would include the number of data blocks which a file would consist of. The file system could have easily calculated that figure from the file size, but it did something else instead: It visited every single data block, counting their number one at a time. If you ever wondered why it took Workbench so incredibly long to read the contents of a volume or drawer until at last one single icon appeared, this is why. On the other hand, scanning a directory automatically verified that all of the file data in this directory was sound. To the best of my knowledge, the Amiga default file system never paid any attention to the disk head position. The file system was designed for larger mass storage devices (up to 54 MBytes in the Kickstart 1.x version, with 512 bytes per block), not so much for floppy disks. The Amiga disk drive, however, could end up recalibrating the disk head position as needed, which could be mistaken for a return to a parking position, if you will. The Amiga default file system would use write caching, with the lit floppy disk LED indicating that the cache had not yet been pushed to disk. The disk would keep on spinning for some three more seconds after the last write command had been executed. But if you used a third party floppy disk drive which had the LED indicator tied to the read head actuator instead of the spindle motor, you were likely to remove the disk when the buffer had not been flushed yet.

115 points by zdw 2y ago

This is the type of analysis I always hope for about file systems, but almost never see. Looks like some of these file systems had linked list files, which is an interesting contrast to inode based file systems like the original UFS, or BSD FFS.

jhallenworld 2y ago
Perhaps they did it to save RAM since you are buffering the current sector anyway. An alternative is CP/M's extent-based filesystem, where the meta-data is all in the directory entry. But I think space allocation algorithm is more complex for it. I like the OS/8 file allocation scheme: files are always contiguous. Only one growing file can be open for writing and it allocates space out of the contiguous free space (actually it owns all of the free space until the file is closed, where the unused space is then given back). If you run out of disk space, you have to compact the disk, eliminating space taken up by deleted files. I like it because it's illustrates the surprising fact that you can get away with only one file open for writing for most things.
- Someone 2y ago
  > I like it because it's illustrates the surprising fact that you can get away with only one file open for writing for most things. https://en.wikipedia.org/wiki/CP/M#CP/M_Plus https://en.wikipedia.org/wiki/CP/M#CP/M_Plus: “The last 8-bit version of CP/M was version 3, often called CP/M Plus, released in 1983. Its BDOS was designed by Brown. It incorporated the bank switching memory management of MP/M in a single-user single-task operating system compatible with CP/M 2.2 applications” Note the “single task” part. That excludes a lot from what we nowadays would be included in “most things”. That, I think, is the reason you could get away with that. I also would guess it was more that programmers would either not know what they missed or accepted it as a limitation that kept the OS small.
- inkyoto 2y ago
  On the modern hardware (i.e. SSD's) files are always «contiguous», thanks to the transparent block remapping in the SSD firmware. Compacting/squeezing was only necessary because magnetic disks were contiguous in their nature and had to be erased and rewritten, which was a time consuming (sometimes very time consuming) and potentially dangerous operation leading to a complete data loss if power flickered. To a certain extent, the compacting is still there and is done in the SSD's (now called «garbage collection»), although it is also transparent to the user and to the operating system.
jdougan 2y ago
This might scratch that itch aloso. Beneath Apple DOS: https://mirrors.apple2.org.za/Apple%20II%20Documentation%20Project/Books/Beneath%20Apple%20DOS.pdf https://mirrors.apple2.org.za/Apple%20II%20Documentation%20P...

jftuga 2y ago

Conclusion: "So the big lesson here is to always plan for the future. Listen to the requirements for the current product, but then design with the assumption that you'll be asked to expand the requirements in the future. If you don't, users may be cursing you when the code is released. But who knows? If you do it right, people may still be using your code in 40 years."

saulpw 2y ago
Unfortunately, "plan for the future" is too general to be workable; this is how you get architecture astronauts using UUIDs and multiple levels of indirection for a 160KB floppy. The future you can plan for, is specifically 10x more. If you have 160KB floppies, then design as though there might be 1.6MB floppies. You'll have to revisit your design anyway for the emergent complexities of the next order of magnitude, but this will at least give you some breathing room. Designing for 100x more than your system has is overengineering. You have no idea what the needs of the future are, and the design for a 100x system will be detrimental for your current 1x system, and likely sink it. So ironically planning for 100x means you probably won't get there.
- antonkochubey 2y ago
  Windows XP lived thorough 6 GB (minimum requirement - 1.5 GB, but I don't recall seeing drives less than six gigs at the time) to 2 TB HDD's. That's literally a 333x increase, which NTFS handled just fine. From min requirement it'd be a 1000x increase.
  - akira2501 2y ago
    > That's literally a 333x increase Yet that's only going from 2^32 to 2^40.
  - jeroenhd 2y ago
    Windows XP's default clustering (well, until SP2 at least) "only" allowed for 128GB disks. The cluster size was later increased. The 2TB limit was generally a limit for the BIOS code rather than an OS limit, as NTFS will happily scale beyond 2TB. Windows NT 4 already contained the code necessary to allow for up to 16 exabyte partitions (https://web.archive.org/web/20010208131204/http://support.microsoft.com/support/kb/articles/Q224/5/26.ASP https://web.archive.org/web/20010208131204/http://support.mi...), but the hardware it was running on probably didn't support anything bigger than a few terabytes. Sure, every text file takes up at least 2MB, but with an exabyte disk, you probably don't care about wasting sectors like that.

kristopolous 2y ago

How are the design intentionalities determined? Are they documented somewhere? I'm not disputing anything, I just want to know the provenance in case there's some really great book or code I should be reading.

pwg 2y ago
The book "Inside Atari DOS" by Bill Wilkinson (author of Atari DOS) goes into some of the rationale: https://www.atariarchives.org/iad/ https://www.atariarchives.org/iad/

skissane 2y ago

> Instead, it was to support "note" and "point" commands. Atari believed people would use files as a database, and with the sector chaining, it was impossible to jump around in a file without reading it linearly. So a program could "note" its position in a file (sector and offset) and then return there later with the point command. This is where verifying that the file number in the user-supplied sector number matched the entry used when opening the file came in. Without that number, there would be no verification that a "point" would end up in the right file. Interesting to hear this terminology used in the context of 8-bit Atari computers. The terms NOTE and POINT come from IBM mainframes, where there are OS/360 macros by those names. NOTE essentially does an fgetpos and POINT an fsetpos

jhallenworld 2y ago
It answers the question of where experienced programmers then got their experience. In the mid 70s, Sigma-7 was another popular 32-bit machine, but I don't know anything about its OS.

mrandish 2y ago

Brings back fond memories of the Amiga DOS floppy disk structure which had some clever things I hadn't seen before (coming from 8-bit ROM-based floppy disk OSes). Such as having each file sector link to the next so if the file allocation table got corrupted, the files on the disk could be recovered by a utility that crawled every sector and rebuilt a new file allocation table. IIRC, it also would occasionally write a backup copy of the file allocation table on another normally unused track as well as parking the disk head away from the track where the directory was after some default period of inactivity. Floppy drives were notorious for occasionally crashing the heads into whatever track they happen to be over if there was a power glitch or software crash - and of course, statistically, they spent most of their time over the directory track, thus greatly increasing to odds of blasting part of the file allocation table. When I moved to PCs I remember being surprised that NTFS didn't seem to do any of this (at least early on) despite being more recent and supposedly advanced.

obarthel 2y ago
The Amiga default file system was not quite that sophisticated. As used on floppy disks, it did well by offering more than one option to reconstruct the layout of the file system data structures. For example, the disk data blocks were chained, so that you could follow this chain and find every block belonging to the same file. But you could also follow the chain of the associated file list blocks and obtain the same information. Which disk blocks were still available for allocation was tracked by the bitmap (never documented in the original AmigaDOS Manuals), a series of blocks in which each bit stood for an individual block which was either allocated or not. There is just one bitmap for the entire volume and the Amiga default file system did not care for redundancy. The bitmap does not even use block checksums because you could reconstruct it at any time by following the directory structures (unless the bitmap was corrupted and spread its troubles, which you would never suspect or know). This is what, as a by-product, the Disk-Validator accomplished in the Kickstart 1.x days. The floppy disk version of the Amiga default file system made use of checksums for each of its data structures, with the exception of the bitmap. This made it slow going, but then you quickly learned of defects which the file system reported. Fun fact: the Amiga default file system in the Kickstart 1.x days was particularly and likely needlessly slow during directory scanning. The metadata produced by the scanning API would include the number of data blocks which a file would consist of. The file system could have easily calculated that figure from the file size, but it did something else instead: It visited every single data block, counting their number one at a time. If you ever wondered why it took Workbench so incredibly long to read the contents of a volume or drawer until at last one single icon appeared, this is why. On the other hand, scanning a directory automatically verified that all of the file data in this directory was sound. To the best of my knowledge, the Amiga default file system never paid any attention to the disk head position. The file system was designed for larger mass storage devices (up to 54 MBytes in the Kickstart 1.x version, with 512 bytes per block), not so much for floppy disks. The Amiga disk drive, however, could end up recalibrating the disk head position as needed, which could be mistaken for a return to a parking position, if you will. The Amiga default file system would use write caching, with the lit floppy disk LED indicating that the cache had not yet been pushed to disk. The disk would keep on spinning for some three more seconds after the last write command had been executed. But if you used a third party floppy disk drive which had the LED indicator tied to the read head actuator instead of the spindle motor, you were likely to remove the disk when the buffer had not been flushed yet.