LEAN File System specification

This document describes version 0.2 of LEAN (Lean yet Effective Allocation and Naming), a new free, simple, portable, personal, fully featured file system for embedded tasks. The third number in the version number identifies changes made to this document (e.g. wording) that do not change the file system format.

The LEAN file system is in the alpha (unstable) development stage: this document supersedes any previous version of the LEAN file system specification with no care for backward compatibility.

Since this is a new file system, and some aspects are still to be defined, suggestions or corrections are welcome, for either the file system or this document. Please contact the author sending e-mail at: salvois at users.sourceforge.net. The author wishes to thank who have submitted comments and criticism in order to improve the LEAN file system.

Overview

The mission of the LEAN file system is to provide a new free, simple, portable, personal file system alternative to the proprietary (and in part patented) Microsoft FAT file system, primarly intended for media exchange and for use with embedded devices, and to expand the file system functionality of the FreeDOS-32 free modular operating system.

LEAN is a recursive backronym for Lean yet Effective Allocation and Naming, based on the ironical contrary of FAT, as an English word.

Design choices

The LEAN file system is somewhat conceptually inspired from the Linux Second Extended file system (EXT2), but it is much simpler. Although developed independently, some design choices of the last version of LEAN resemble those of the QNX file system.

LEAN aims to be the simplest file system providing the most common and useful file system features. Any design choices have gone in the direction of the greatest simplicity rather than performance. It is said that programmers like the FAT file system for its simplicity. LEAN aims to be much simpler yet to perform better.

Limits

The LEAN file system may be used on small media (as small as a floppy) as well as on bigger media. The basic allocation unit is a sector, that is a block of the hosting block device. Depending on the sector size, a file system volume may be large up to 2 TiB (assuming 512-byte sectors) or up to 16 TiB (assuming 4096-byte sectors). In fact, sectors are addressed using 32-bit numbers. The total number of files, the size of a file and the number of files per directory are only limited by the free volume space.

Allocation

The volume status is stored in a superblock at the beginning of the hosting block device, as well as in a superblock backup in another location. Free sectors are tracked by a bitmap, that is evenly distributed across the file system.

File metadata are stored in inode structures, located in the first sector of each file, like a header. An inode structure stores the attributes of a file and the information to access any other sector of a file. Each file is uniquely identified by an inode number, that is the address of its first sector.

File allocation is extent-based, that is each file is composed by several chunks, called extents, each made up of one or more of contiguous sectors. Extent addressing is direct for the first extents of a file (in order to maximize performance on small files), storing the extent specirfications in the inode structure itself, whereas it is indirect for subsequent extents, using a doubly-linked list of level-1 indirect sectors.

File names

Directories are files which store an unordered list of directory entries. The LEAN file system provides case sensitive international long file names, encoded in Unicode UTF-8. The length of a file name is limited to 2032 bytes or by the sector size, whichever comes first. Both hard links and symbolic links are available.

Resume

The following table summarizes the features of the LEAN file system:

Reference implementation

A reference implementation, written in the D programming language, is about to be completed.

Future plans

Converting LEAN to 64-bit sector addressing is being considered. That would break the 2 TiB limit (with 512-byte sectors) at the price of some extra disk space. If 64-bit numbers are used for both sector numbers and extent sizes, an indirect sector would contain up to 28 extent specifications vs. 60 (with 512-byte sectors), and the inode structure would be 224 bytes (storing 8 extent specifications) vs. 128. If 32-bit numbers are retained for extent sizes, an indirect sector could store up to 38 extent specifications (with 512-byte sectors) and the inode structure would be 192 bytes. Alignment issues should be considered, though (64-bit and 32-bit numbers would be interleaved in an array). Each directory entry would have a header of 12 bytes instead of 8. Feedback and suggestions are welcome.

File system format

This section describes the architecture of the LEAN file system as stored in a hosting block device.

Definitions

The following terms and conventions will be used throughout this specification:

• must, must not, should, should not, may: these words are to be interpreted as described in RFC 2119;
• driver: a file system driver, or any other part of the operating system, or any application implementing this specification to access a LEAN file system;
• disk: a block device hosting a LEAN file system. This wording is used for simplicity, although that device does not need to be an actual disk memory (e.g. disk partition, memory card, RAM disk);
• sector: a disk block. The disk must be an array of contiguous sectors, numbered starting from zero. The sector size must be 512, 1024, 2048 or 4096 bytes;
• volume: a self contained LEAN file system on a disk;
• superblock: a structure containing fundamental information about a volume;
• bitmap: a structure tracking free sectors of a volume;
• band: a portion of the disk made up of several contiguous sectors. Each band stores a part of the bitmap, in order to take advantage of locality in space;
• data area: part of a volume storing files and directories;
• directory: a special file storing a list of directory entries;
• directory entry: a structure containing a file name and location;
• inode structure: a structure containing fundamental information about a file. The inode structure of a file is stored in the first sector of the file;
• inode number: the sector number of the first sector of a file, that is the sector containing the inode structure of the file. The inode number must uniquely identify a file on a volume;
• extent: a contiguous addressable portion of a file, specified by a starting sector and a size;
• The D programming language syntax is used for code snippets and structure formats (briefly, byte, short, int, long mean, respectively, 8-, 16-, 32- and 64-bit signed integers, while ubyte, ushort, uint, ulong are unsigned, char is an unsigned byte of a UTF-8 string, enums are scoped);
• Hex numbers are prefixed with 0x;
• Unless otherwise stated, all numbers must be stored in little endian format (least significant byte first);
• The following types are provided:

  // The address of a sector.
  typedef uint Sector;
  
  // An extent specification.
  struct Extent
  {
  	Sector start;
  	Sector size;
  }
  
  // A 128-bit globally unique identifier (GUID).
  struct Guid
  {
  	uint     data1;
  	ushort   data2;
  	ushort   data3;
  	ubyte[8] data4;
  }
  

Partition identifier

On the i386 platform, each file system is identified by an 8-bit number in an entry of an MBR partition table. The value 0xEA (after LEAN) has been proposed as it seems unassigned.

For GUID partition tables the following GUID is provided to identify a LEAN data partition:

bb5a91b0-977e-11db-b606-0800200c9a66

Structure identification and checksum

Several structures of LEAN include fields to make the file system more robust.

Sensitive structures store a checksum field in their first 32 bits. The checksum is computed on any data following the checksum field itself, up to the end of the sensitive structure. The sensitive structure must be cast to an array of 32-bit unsigned integers, then each element of this array must be summed, rotating the sum one bit to right at every iteration. The size of the sensitive structure must be a multiple of 4 bytes. The checksum must be recomputed at least every time a sensitive structure is written back to disk.

The following function shows how to calculate the checksum. The data parameter is a pointer to the sensitive structure, including the checksum field in its first 4 bytes. The size parameter is the size in bytes of the structure pointed by data, including the 4 bytes for the checksum field. It must be a multiple of 4 bytes. The function skips the first 4 bytes when computing the checksum.

uint computeChecksum(void* data, size_t size)
{
	uint res = 0;
	uint* d = cast(uint*) data;
	assert((size & (uint.sizeof - 1)) == 0);
	size /= uint.sizeof;
	for (uint k = 1; k < size; k++) res = (res << 31) + (res >> 1) + d[k];
	return res;
}

A sensitive structure also contains a magic field storing a 32-bit constant signature identifying the structure. This can be used as a first test to validate a sensitive structure.

A field specifying the address of the sector storing the structure itself is sometimes provided. This is another robustness measure against repair utilities, in case they are scanning a disk for sensitive data structure, and an image file containing a LEAN file system is stored on that disk.

Figure 1: Layout of a LEAN volume.

Bands

To improve locality in space and to help dinamically change the size of a volume, the disk is logically subdivided into bands, made up of several contiguous sectors. Bands are equally sized, perhaps except the last one, and must be made up of a power of two worth of sectors. A volume contains at least one band. Bands are numbered starting from 0, where sector 0 is the first sector of band 0.

Each band contains a portion of the bitmap representing the allocation state of the sectors of that band. That is, each bitmap portion represents the state of closely located sectors. The bitmap portion for each band must start at the first sector of the band. Band 0 is an exception in that it contains sectors reserved for the boot loader and the superblock, thus a specific field is used to tell where the bitmap of band 0 starts.

The superblock

The superblock is a structure containing fundamental information about a LEAN volume. Its name comes from the Linux EXT2 file system, and it is used to differentiate it from the boot sector, that on i386 is sector 0, containing the code of the boot loader.

A driver must use the superblock to know how to access every other information on the volume. Thus, the superblock must be stored in a well known location. The superblock must be stored in the first 512 bytes (regardless the sector size) of one of any sector in the range 1 to 32, inclusive. This range should allow to scan for a superblock taking advantage of track buffering from the disk driver, while being flexible enough to overcome the limits of a fixed location. This leaves up to 16 KiB for the boot loader if the sector size is 512 bytes. A driver must use the magic and checksum fields of the superblock to identify a valid superblock.

A copy of the superblock must be present in a different location for backup purposes. A driver must ensure that the content of the backup copy is always exactly the same as the superblock. The location of the superblock backup is stored in the superblock to allow a driver update the backup copy. The backup copy of the superblock should be placed in the last sector of the first band, in order to help drivers locate it in the event the primary copy gets lost or corrupted (being band sizes constrained to powers of two). The magic, checksum and backupSuper fields must be used in this case.

Sectors before the superblock are reserved for a boot loader, they must not be used by a LEAN driver, and their content is undefined. The superblock may be shifted forward, up to the limit specified above, if more sectors are needed to store a boot loader. Sector 0 is always reserved.

In the FAT file system the boot sector embeds, besides the boot loader, volume status information. Thus, if a boot sector containing apparently valid FAT information is used on a LEAN volume, FAT drivers may erroneously detect the volume as FAT. Implementors and/or users may remove FAT related information from the boot sector (for example, zeroing every byte but the actual boot code), or try FAT detection at the end of the autodetection process. The LEAN design avoids storage of volume information in the boot sector for several reasons: platform independence, to use a compact, free format, where the fields are properly aligned and ordered, for robustness against a damaged sector 0, and to make room for boot loader code.

The format of the superblock is the following:

The bitmap

The bitmap is a non-contiguous data structure, made up of sectors that, as a whole, form an array of bits, each of them indicating the allocated/unallocated state of each sector of a volume. The bitmap is not contiguous because its sectors are subdivided into bands, instead of being stored in a single chunk in a fixed location.

The total number of sectors in a volume is specified by the sectorsCount field of the superblock. Thus, the bitmap as a whole must contain sectorsCount bits, one for each sector. The number of sectors required to store the bitmap (that is, the total bitmap size) is given by ceil(sectorsCount / (bytesPerSector * 8)), where ceil rounds up, and bytesPerSector is the size in bytes of a sector (a quantity that drivers may want to precalculate for several purposes). Any bits after the first sectorsCount are unspecified. Each band must store a portion of the bitmap, according to the band size in sectors, that is the size of each bitmap portion must be sectorsPerBand / (bytesPerSector * 8) sectors, where sectorsPerBand can be easily computed from the superblock. The size of each bitmap portion will result an integral number of sectors due to the constraints specified for logSectorsPerBand.

A bit of the bitmap must be set to '1' if its corresponding sector is used/allocated, whereas it must be set to '0' if its corresponding sector is free/unallocated. Sector 0 is identified by bit 0 (the LSB) of the first byte of the bitmap, sector 1 by bit 1 of the first byte, sector 7 by bit 7 (the MSB) of the first byte, sector 8 by bit 0 of the second byte, and so on.

The sectors occupied by the superblock, the superblock backup, the bitmap itself and any reserved sectors containing boot loader code are not free for data storage, thus must be marked as allocated in the bitmap.

The following code snippet shows how to locate a bit for the sector specified by sector.

/* The following input values and precalcs are assumed:
 *	Sector sector = the sector to locate the bitmap entry for
 *	Superblock sb = a structure containing the superblock
 *	Sector sectorsPerBand = 1 << sb.logSectorsPerBand
 *	uint bytesPerSector = 1 << sb.logBytesPerSector
 */
Sector band = sector >> sb.logSectorsPerBand;
Sector sectorInBand = sector & (sectorsPerBand - cast(Sector) 1);
Sector bitmapSector = (sectorInBand >> (3 + sb.logBytesPerSector)) + (band << sb.logSectorsPerBand);
if (band == 0) bitmapSector += sb.bitmapStart;
uint bitOfSector = sectorInBand & (bytesPerSector * 8 - 1);

Figure 2: File Allocation in LEAN.

The data area and file allocation

The data area is made up of any sector not used by the bitmap, the superblock, the superblock backup and sectors reserved for boot code. It is in general not contiguous due to the band-based layout of the bitmap. It stores actual file system contents: files, directories and their related book keeping (that is the list of their allocated sectors).

Besides being unused, each sector in the data area can be either a data sector or an indirect sector. The former contains actual data, the latter contains book keeping. Data sectors are grouped together to form extents when they are contiguous. An extent is specified by a start and a size in sectors.

Each file is stored in one or more extents, thus a file allocation can be described as an array of extent specifications. The first sector of a file stores the inode structure of the file. Actual file data must begin right after the inode structure. This introduces an offset when converting between file data position and data sectors. The inode structure and indirect sectors are used to know what extents belong to a file. This is done in two ways: direct addressing and indirect addressing.

Direct addressing

To speed up file access on small files, a limited number of extent specifications is stored in the inode structure itself. A driver must use this information to directly access any of the first extents of the file in constant time. The constant EXTENTS_PER_INODE, currently defined to 7, specifies how many extent specifications are saved into the inode structure.

Indirect addressing

If a file needs more than EXTENTS_PER_INODE extents, indirect addressing is used for subsequent extents. An indirect sector is a sector storing an array of extent specifications instead of file data. The number of extent specifications per indirect sectors depends on the sector size (60 extent specifications can be saved in a 512-byte sector). Indirect sectors are linked together to form a doubly-linked list in order to support arbitrary file lengths. The following is the layout of an indirect sector:

Rationale

The extent-based approach allows efficient and simple access to the file system. It is efficient because, once the driver knows an extent specification, it can access any sector of that extent in constant time. It is also simple because, for each extent, only an offset must be added to its starting sector to find any other sector.

This works best if the file is not badly fragmented, that is unless the file is made up of several extents. Being the first EXTENTS_PER_INODE extent specifications saved in the inode structure, it is expected that most small files would need no indirect sectors, thus any sector can be accessed in constant time with no additional reads. Large files can benefit from this too, if they are mostly contiguous, although this is not as likely.

Indirect sectors store a much greater amount of extent specifications than the inode structure, thus it is expected that with a few indirect sectors a file is completely specified. For example a file made up of 200 fragments would require 4 indirect sectors, assuming a sector size of 512 bytes. They may be buffered for faster operation. The number of indirect sectors, if any are present, is determined only by the count of fragments, not by the file size (at least not directly).

This approach has been chosen in order to advantage random access on small files (e.g. configuration files), but sequential access for bigger files (e.g. multimedia files), as well as keeping the file system implementation as simple as possible.

Allocation strategies

In order to use the file system as efficiently as possible, drivers may implement allocation strategies when creating or extending files. This specification does not define or mandate such allocation strategies, but a few suggestions are presented.

When extending a file, a driver should try to grow its last extent. The last extent of a file can be easily found using the extentsCount and/or lastIndirect fields of the inode structure. The following algorithm may be used:

if the sector right after the end of the last extent is free
{
	grow the last extent increasing its size by 1;
}
else
{
	find a free sector as close as possible to the last extent;
	if a new indirect sector is needed
	{
		write the indirect sector in that free sector;
		find a free sector as close as possible to the indirect sector just written;
	}
	create a new extent starting at that free sector and with size 1;
}

To improve locality in space between directories and their files, and to help reduce fragmentation, a driver may use the following algorithm when creating a new file. It assumes that most files will have a single hard link, thus a single parent directory:

locate the band where the parent directory of the new file ends;
if the new file is not a directory
{
	find a free sector as close as possible to the end of the parent directory;
}
else
{
	generate a band number different from the one of the parent directory;
	find a free sector in that band;
}
create the new file in that sector and store there its inode structure;

To help implementing these algorithms, a driver may provide a parameter to the procedure searching for free sectors, specifying a suggested sector where to start to search from.

The inode structure

All metadata of a file are stored in a structure called inode structure. File metadata include file size, attributes and time stamps, as well as the means to access directly- and indirectly-addressable extents of a file.

The inode structure must be stored in the first 128 bytes of the first data sector of a file. The address of that first data sector must be used as inode number, that is a serial number to uniquely identify the file in a volume. It is not supposed to uniquely identify the file on the whole system: the operating system or a driver may use the inode number together with some way to identify the volume (for example, its GUID or an opaque identifier) to uniquely identify the file system-wise.

Putting the inode structure in a file data sector lets avoid a separate inode table, allowing an arbitrary number of files per volume and simplifying inode management, at the price of some disk space (expecially for very small files that would otherwise fit in a single sector or zero-length files).

The format of the inode structure is the following:

Figure 3: Directory format in LEAN.

Directories

A directory is a file containing an unordered list of directory entries. Each directory entry is a structure which binds a file name with an inode structure, thus each directory entry is a hard link to a file. Directory entries do not store file metadata, except what specified below.

A directory entry is a variable length structure, containing a fixed length header (8 bytes long) and a variable length part containing the file name. The size of the whole structure must be a multiple of 8 bytes, that is the size of the fixed length header. This helps to reuse space from deleted directory entries. A directory entry must be completely contained in a single sector, in order to ease memory management in drivers. This limits file name lengths to 504 bytes if the sector size is 512 bytes.

File name storage must be case sensitive in order to simplify name comparison, avoiding case folding to upper or lower case, that is not trivial in Unicode. Drivers may implement case insensitive file name matching in an unspecified way. In environments lacking support for long file names, or requiring short file name aliases, a driver may fabricate short file names on the fly, that is, without having them physically stored in the directory. The algorithm used to fabricate short file names is unspecified, but a proposed procedure is shown below.

This is the format of a directory entry:

The following table shows the possible values for the type field of a directory entry. A value of zero must indicate that the directory entry is empty (available, or deleted). A file may be undeleted by setting type back to the corresponding value in the inode structure, until its sectors are physically overwritten (the magic and checksum fields should be checked for robustness in this case). Note that these values are mutually exclusive enumerated values, they are not single bits that can be combined.

"." and ".." entries

The two special entries "." (dot) and ".." (dotdot) must be the first entries of every directory. The former must be a hard link to the directory itself, the latter must a hard link to the parent directory. In the root directory, which has no parent, ".." must be a hard link to itself, too.

A driver may use fictitious "." and ".." entries ignoring the actual entries in the directory, for example to assign ".." to the parent directory of a mount point. If showing "." and ".." to the user is a concern, a driver may choose to make them hidden entries, for example those of the root directory.

Looking up a directory

This algorithm must be used to search an entry in a directory, using appropriate file name matching criteria:

while not EOF
{
	read an 8-byte directory header;
	if (DirEntry.type != FileType.NONE)
	{
		read the file name, that is guaranteed to fit in the same sector;
		compare against the required file name;
		if the required entry is found return this directory entry;
	}
	advance using the information provided in recLen;
}
return "file not found";

Deleting an entry

To delete a hard link to a file, a driver must set the type field of the directory entry to zero (that is FileType.NONE) and decrease the linksCount field of its inode structure. The space occupied by the deleted directory entry (recLen * 8 bytes) is made available for reuse (see the 3rd entry in figure 3). If some degree of security is needed, a driver may zero all bytes of a directory entry, except recLen.

If the linksCount of the inode structure of the file reaches zero, the sectors of the file (both data and indirect) must be deleted. To do this, drivers must set the corresponding bits in the bitmap to '0'. This is efficient and allows to recover data, until physically overwritten. If some degree of security is needed, a driver may also zero or fill with garbage the actual content of the deleted sectors.

Creating an entry

This procedure must be used to create a new hard link to a file.

Scan the directory for one or more contiguous available directory entries, enough to store the new directory entry. This is because available entries are not coalesced together. The required size of the directory entry, in 8 bytes units, must be computed as recLen = (8 + nameLen + 7) >> 3. Available directory entries must be identified for having type == FileType.NONE (see above).

If enough space to store the new directory entry is found, the new directory entry should be stored in that place, otherwise the new directory entry must be appended to the directory, thus extending it. The new directory entry must not span across different sectors. If the new directory entry is shorter than the free space found, a driver must fabricate and append a new directory entry header (with type equal to FileType.NONE) to keep the link with the next directory entry consistent (see the 6th entry in figure 3).

Fabricating a short file name

In environments lacking support for long file names, or requiring short file name aliases, a driver may fabricate short file names. Fabricated short file names are not supposed to be stored on the file system as new hard links, but rather generated on the fly to the user when they are needed. How to fabricate short file names in such cases is unspecified. The following is an algorithm that drivers may use if appropriate:

• find the last dot, if any, in the file name, and assume it to be the separator between the name prefix and the name extension;
• remove any invalid character from the original file name;
• convert the resulting name to the required character set, if any;
• truncate the name prefix and the name extension to the required lengths;
• take the offset where the directory entry starts inside the directory containing it, and divide that offset by 8 (all directory entries are multiple of 8 bytes);
• append this number to the name prefix, to make sure it is unique in the directory (hex numbers may be used to shorten the numeric tail), truncating the name prefix further, if required, to fit a short file name.

Symbolic links

A symbolic link (symlink, soft link) is a special file storing the pathname of another file. Its file type must be FileType.LNK.

The string representing the pathname must be encoded in Unicode UTF-8 and must not be null terminated. The length of this string must be equal to the file size of the symbolic link.

The represented pathname may be either absolute or relative. A driver or other appropriate parts of an implementation should provide the means to follow the symbolic link. In a system where pathnames may include a drive or device specification, the pathname stored by the symbolic link may contain a drive or device specification too. The way the implementation behaves in the event the drive or device referred by the symbolic link change (for example a removable or network drive, or when the volume is used in a system not supporting drive or device specifications) is implementation specific.

The meaning of attributes for symbolic links is unspecified. A driver may apply their regular meaning to the symbolic link itself (for example, a hidden symbolic link may be not showed in a directory listing, whether the target is hidden or not, or the permissions of a symbolic link may refer to what can be done with the target when accessed via the symbolic link), or may use any conventions normally used by the system for symbolic links.