Difference between revisions of "File systems"

From Ninerpedia
Jump to navigation Jump to search
Line 417: Line 417:
{| class="filesys" style="width:50%"
{| class="filesys" style="width:50%"
|-
|-
| 00
! 00
| colspan="2" rowspan="5" style="border: 1px solid black; padding:0.5ex" | Directory name
| colspan="2" rowspan="5" style="border: 1px solid black; padding:0.5ex" | Directory name
|-
|-
| 02
! 02
|-
|-
| 04
! 04
|-
|-
| 06
! 06
|-
|-
| 08
! 08
|-
|-
| 0A
! 0A
| colspan="2" style="border: 1px solid black; padding:0.5ex" | HFDC: Total number of AUs / SCSI: unused
| colspan="2" style="border: 1px solid black; padding:0.5ex" | HFDC: Total number of AUs / SCSI: unused
|-
|-
| 0C
! 0C
| style="border: 1px solid black; padding:0.5ex; width:50%" | unused  
| style="border: 1px solid black; padding:0.5ex; width:50%" | unused  
| style="border: 1px solid black; padding:0.5ex; width:50%" | "D"
| style="border: 1px solid black; padding:0.5ex; width:50%" | "D"
|-
|-
| 0E
! 0E
| style="border: 1px solid black; padding:0.5ex; width:50%" | "I"
| style="border: 1px solid black; padding:0.5ex; width:50%" | "I"
| style="border: 1px solid black; padding:0.5ex; width:50%" | "R"
| style="border: 1px solid black; padding:0.5ex; width:50%" | "R"
|-
|-
| 10
! 10
| colspan="2" style="border: 1px solid black; padding:0.5ex" | unused
| colspan="2" style="border: 1px solid black; padding:0.5ex" | unused
|-
|-
| 12
! 12
| colspan="2" rowspan="2" style="border: 1px solid black; padding:0.5ex" | Date and time of creation
| colspan="2" rowspan="2" style="border: 1px solid black; padding:0.5ex" | Date and time of creation
|-
|-
| 14
! 14
|-
|-
| 16
! 16
| style="border: 1px solid black; padding:0.5ex" | # of files
| style="border: 1px solid black; padding:0.5ex" | # of files
| style="border: 1px solid black; padding:0.5ex" | # of subdirectories
| style="border: 1px solid black; padding:0.5ex" | # of subdirectories
|-
|-
| 18
! 18
| colspan="2" style="border: 1px solid black; padding:0.5ex" | Pointer to file descriptor index record
| colspan="2" style="border: 1px solid black; padding:0.5ex" | Pointer to file descriptor index record
|-
|-
| 1A
! 1A
| colspan="2" style="border: 1px solid black; padding:0.5ex" | Pointer to the parent directory AU
| colspan="2" style="border: 1px solid black; padding:0.5ex" | Pointer to the parent directory AU
|-
|-
| 1C
! 1C
| colspan="2" rowspan="5" style="border: 1px solid black; padding:0.5ex" | Pointer to subdirectories
| colspan="2" rowspan="5" style="border: 1px solid black; padding:0.5ex" | AU numbers of subdirectories (DDR)
|-
|-
| 1E
! 1E
|-
|-
| 20
! 20
|-
|-
| ...
! ...
|-
|-
| FE
! FE
|-
|-
|}
|}

Revision as of 17:07, 2 November 2011

Floppy Disk File System

Floppy file systems had no notion of subdirectories for most of the time. Disk controllers like the Myarc FDC and HFDC introduced a directory scheme where the root directory may have up to three subdirectories. These subdirectories may have no subdirectories by themselves.

Volume Information Block

00 Volume name. May not contain a dot (".") because this is used as the path separator. Padded with spaces.
02
04
06
08
0A Total number of sectors
0C Sectors per track "D"
0E "S" "K"
10 Protection Tracks per side
12 Number of sides Density Density may have values 0 .. 4 (see below)
14 Directory 1 name Same constraints as for file or volume name
16
18
1A
1C
1E Sector number of FDIR of dir 1 Null if no directory exists. Only on start of AU.
20 Directory 2 name
22
24
26
28
2A Sector number of FDIR of dir 2
2C Directory 3 name
2E
30
32
34
36 Sector number of FDIR of dir 3
38 Allocation bit map Each bit represents a collection of sectors on the disk (see below)
3A
3C
...
FE

Density values:

  • Single (0,1): 125 kBit/s FM
  • Double (2): 250 kBit/s MFM
  • High (3): 500 kBit/s MFM
  • Ultra (4): 1MBit/s MFM

File Descriptor Index Record

The File Descriptor Index Record (FDIR) contains pointers to the File Descriptor Records. The pointers are arranged so that the list of files has a lexicographic order (alphabetic sorting). The FDIR of the root directory is always in sector 1. The FDIRs of the subdirectories are pointed to by the respective fields in sector 0.

The end of the list is marked by the first null pointer.

00 Sector number of first file descriptor record Always sector number, not AU
02 Sector number of second file descriptor record
04 Sector number of third file descriptor record
06 Sector number of fourth file descriptor record
...
FC Sector number of 127th file descriptor record
FE 0

Unlike the FDIRs in the hard disk file system there is no pointer back to the parent directory as the floppy file system does not allow nested subdirectories, and thus the parent is always the root directory.

File Descriptor Records

Each file entry in the diretory is defined by a file descriptor record.

00 File name
02
04
06
08
0A Extended record length
0C File status flags Number of records/sec
0E Number of sectors currently allocated
10 End-of-file offset Logical record length
12 Number of level 3 records allocated
14 Date and time of creation hhhh.hmmm.mmms.ssss (2 seconds resolution)
16 yyyy.yyyM.MMMd.dddd
18 Date and time of last update
1A
1C Data chain pointer blocks
1E
...
FE

The data chain pointers are used to refer to sections on the disk where fragments of the file will be found. There is always at least one data chain pointer; if there are more, the file is fragmented.

Every data chain pointer consists of three bytes with two hex digits each, so we have six hex digits

1 2 3 4 5 6
M2 M1 N1 M3 N3 N2

from where we get the 16-bit numbers

  • M = 0 M3 M2 M1: Sector or AU number of start of chain element
  • N = 0 N3 N2 N1: Highest file sector count (starting at 0) for this chain element

This may sound a bit confusing, therefore I'm adding an example. Here are the pointers for the data chain:

36 10 00, 44 30 00, ac 62 00, 03 b3 00, 17 04 01

Using the mapping from above, we get

M =   0036    0044     02ac     0303      0417
N =   0001    0003     0006     000b      0010

Sectors
    0:0036  2:0044   4:02ac   7:0303   12:0417
    1:0037  3:0045   5:02ad   8:0304   13:0418
                     6:02ae   9:0305   14:0419
                             10:0306   15:041a
                             11:0307   16:041b

This means: The file occupies the sectors >0036 (sector 0), >0037 (sector 1), >0044 (sector 2), ... >041b (sector 16). Note that N does not provide the length of the current chain element but the total number of read sectors after reading this chain element. Counting from 0, and together with the directory entry, we have

The number of sectors which a file occupies on the disk is Nlast+2

Or you may want calculate the intervals as follows:

intv(i).start = Mi
intv(i).end = Mi + Ni - (Ni-1 + 1)

with N-1=-1.

Important comment to sector/AU usage: For disks with capacities up to 720 KiB, the M-value refers to a sector. For disks with higher capacities (1.44 or 2.88 MiB), M-values are AUs. The N-values are always sector counts, even when the M-value points to an AU.

Allocation Bit Map

This map shows which sectors are occupied by files on this file system. The map is located starting at byte 0x38 and reaching to the end of this sector, so its size is 200 bytes. This means that for file systems with more than 1600 sectors, clusters must be formed which serve as allocation units (AU).

Bits are organized in little-endian order. That is, a value of 0x01 declares the AU with the smallest number of a block of 8 to be allocated. On floppy disks with less than 1600 sectors, the allocation map is usually preset with 0x03, reserving sector 0 and sector 1.

AU 7 AU 6 AU 5 AU 4 AU 3 AU 2 AU 1 AU 0

Disks with a capacity of at most 400 KiB have an AU size of 1 sector (all SSSD, SSDD, DSSD, DSDD, with 40 tracks, at most 1440 sectors). Disks with at most 800 KiB space have 2 sectors per AU (720 KiB, 2880 sectors), with 1.4 MiB we have 4 sectors per AU, and the disks with ultra capacity (2.8 MiB) have 8 sectors per AU.

Hard Disk File System

The file system is defined by

  • the Volume Information Block
  • the Directory Descriptor Records
  • the File Descriptor Index Records
  • the File Descriptor Records, and
  • the Allocation Bit Map

Volume Information Block (HFDC)

The Volume information block (VIB) contains information about the complete file system on this volume. It is located in the first sector of the volume. The VIB takes the role both of the volume specifier and of the root directory specifier. Therefore, we find directory information as well as volume information in this block.

00 Volume name
02
04
06
08
0A Total number of allocation units
0C Sectors/Track Reserved AUs / W
0E Step speed / I Red. write current / N
10 Sect/AU -1 Heads -1 BS Write precomp
12 Date and time of creation
14
16 # of files # of subdirectories
18 Sector number of file descriptor index record
1A Sector number of DSK1 emulation file
1C AU numbers of subdirectories (DDR)
1E
20
...
FE

BS = Buffered head stepping (one bit, 0 or 1)

The W,I,N values may be present after initial formatting. Usually they are replaced by the given settings.

Reserved AUs: when multiplied by 64 (0x40), declares the start AU for file contents. For instance, with a value of 0x15, file contents are stored at AUs 0x0540 and higher.

There are 114 slots for pointers to subdirectories (from 0x1c to 0xff, 2 bytes each), so this is the maximum number of subdirectories in a directory.

Volume Information Block (SCSI)

The Volume information block (VIB) contains information about the complete file system on this volume. It is located in the first sector of the volume. The VIB takes the role both of the volume specifier and of the root directory specifier. Therefore, we find directory information as well as volume information in this block.

00 Volume name
02
04
06
08
0A Total number of AUs
0C Reserved Reserved AUs / W
0E Unused / I Unused / N
10 Sectors per AU Unused
12 Date and time of creation
14
16 # of files # of subdirectories
18 Pointer to file descriptor index record
1A Reserved
1C AU numbers of subdirectories (DDR)
1E
20
...
FE

Byte >10 is the same as in the HFDC VIB (first 4 bits, adding 1). Thus, a value of >F0 means 16 sectors per AU and is the maximum number. The other four bits are not used. See above for the meaning of Reserved AUs.

Directory Descriptor Records

Each directory is defined by a directory descriptor record (DDR). It is structured similarly to a VIB.

00 Directory name
02
04
06
08
0A HFDC: Total number of AUs / SCSI: unused
0C unused "D"
0E "I" "R"
10 unused
12 Date and time of creation
14
16 # of files # of subdirectories
18 Pointer to file descriptor index record
1A Pointer to the parent directory AU
1C AU numbers of subdirectories (DDR)
1E
20
...
FE

File Descriptor Index Records

As space in a DDR is limited, the files are referenced outside the DDR, using a File Decriptor Index Record (FDIR). There is one FDIR per directory. The FDIR is also responsible for the ordering of file names in the directory. That is, new files are inserted into the list, preserving alphabetical order.

The end of the list is marked by the first null pointer. Note that the FDIR for hard disks contain pointers to allocation units, not to sectors.

The last entry of the list (position >FE) points back to the containing directory AU. With a sector size of 256 bytes we can have 127 files per directory at most.

00 AU number of first file descriptor record
02 AU number of second file descriptor record
04 AU number of third file descriptor record
06 AU number of fourth file descriptor record
...
FC AU number of 127th file descriptor record
FE AU number of directory descriptor record of this FDIR

File Descriptor Records

Each file is defined by a file descriptor record.

00 File name
02
04
06
08
0A Extended record length
0C File status flags Number of records/sec
0E Number of sectors currently allocated
10 End-of-file offset Logical record length
12 Number of level 3 records allocated
14 Date and time of creation
16
18 Date and time of last update
1A
1C "F" "I"
1E Pointer to previous FDR (AU)
20 Pointer to next FDR (AU)
22 Number of AUs allocated for this FDR
24 Pointer to file descriptor index record
26 Extended information
28 Data chain pointer blocks
2A
...
FE

For hard drives, the data chain pointer blocks are structured differently. We have four bytes per chain element, two for the start AU, and two for the end AU.

(to be verified)

Allocation Bit Map

The allocation bitmap is located in sectors 1 to 31 where each bit represents one allocation unit. That is, we have

31 sector * 256 byte/sector * 8 bit/byte * 1 AU/bit = 63488 AUs = >F800 AUs.

Caution: The bit order in the bytes of the allocation map is big-endian, different to the situation with floppy disks.

AU 0 AU 1 AU 2 AU 3 AU 4 AU 5 AU 6 AU 7


Maximum hard disk size

The allocation bitmap limits the maximum size of a hard drive in terms of allocation units. The maximum number of sectors in an allocation unit is determined by byte >10 in the VIB which leaves only 4 bits for this number (adding 1), so the maximum is 16.

That is, we ultimately have a maximum usable space of

16 sector/AU * 63488 AU * 256 byte/sector = 260046848 byte

that is 248 MiB. Any bigger drive will stay unused beyond this point.