User:Bellezzasolo/CFS

Filesystems
Virtual Filesystems
VFS
Disk Filesystems
FAT 12/16/32, VFAT, ExFAT Ext 2/3/4 LEAN HPFS NTFS HFS HFS+ MFS ReiserFS FFS (Amiga) FFS (BSD)/UFS BeFS BFS XFS SFS ZDSFS ZFS USTAR
CD/DVD Filesystems
ISO 9660 Joliet UDF
Network Filesystems
NFS RFS AFS
Flash Filesystems
JFFS2 YAFFS

Chai File System (CFS)

CFS64

Introduction

CFS64 is my file system (Bellezzasolo's). It uses 64 bit addressing, which is the 64. It currently has a (slightly buggy) Win32 formatter and a grub module.
It is currently at version 1.01
I intend to create CFS64 2.0. As a result, these fields will be changing. I intend to improve the data structures used for access performance. Furthermore, Journaling is planned. I am also considering multiple-disk volumes.
Note: all fields are little-endian

Github repository: CFS64

Features

• User security
• Flags
• Inode style tables
• Runtime-variable size
• Tree-based

Limitations

There are few limitations. Here are the only ones:

• One is the 64 bit addressing, which will (one day) be changed in CFS128; but for now it's plenty
• File and Directory Name lengths.

If you spot any more, add them here

Structure

CFS64 is structured in the follwing way:

• MASTER Table - logical sector 0 of the partition. Bootloader and essential data
• Cluster Availability Table - a bit representing every cluster on the partition, in logical order
• FS Table - CAT for fs entries. i.e. cluster is partially used, not wholly.
• Entries - unordered entries, which point to respective parts. Will need defragmenting from time to time. No dedicated zone for file data, so no limits.

For error checking multiple copies of the tables can be kept

Detail

MASTER Table

Name	Offset (from the start of the MASTER Table)	Length (in bytes)	Meaning
Jump	0	2	A jump to the bootloader if bootable, 0 otherwise. Normally disassembles to JMP SHORT (0x)3F
Creation Date	2	8	The creation time and date, encoded in TeraTime. TeraTime is Unix time, except the epoch is 1st Jan 2011
Creator ID	10	4	The creator's ID. This is normally 0, but could be set to a range of values for future use
Disk Size (Clusters)	14	8	The number of clusters on the partition. Need I say any more?
Bytes per Cluster	22	2	The number of bytes in a cluster. Could be the same as the disk, but then again might not be :)
Number of Tables	24	1	The number of Copies of the tables. 1 if no backup, another number for backups. 0 is invalid
Major Version	25	2	The major FS version. Can be any 2 byte value
Minor Version	27	1	The minor FS version. Is the .xy after the major version. Can only be between 0 and 99 inclusive
FS Table Pointer	28	8	The first cluster of the FS Table. This is a Cluster Availability Table for FS entries.
Root Table Pointer	36	8	The cluster where the root directory's file entry resides. It will be at offset 0
FS ID	44	8	The FS string. Only "CFS64 " is acceptable
Volume Label	52	11	The volume label. 11 characters only (ASCII)
Disks in Volume	63	2	The number of partitions making up this logical volume. Add one to this value. TFS64 2.0+
Disk index	65	2	The unique identifier of this disk within the volume. TFS64 2.0+
Bootloader	67 (or 0x43)	443	The bootloader. Duh! :)
Boot Signature	510	2	The old 0xAA55

Cluster Availability Table (CAT)

This is just an array of bits. Each bit represents a cluster on the partition. If it's set to 1, the custer is used. Otherwise it's free. The bit's offset from the start of the CAT is the cluster at that offset from the start of the partition. FS data is included (even itself!).

Offset (bytes)	Clusters
0	0-7
1	8-15
10000	80000-80007
10001	80008-80015

And in each byte:

Byte n
Bit	7	6	5	4	3	2	1	0
Cluster	n*8 + 7	n*8 + 6	n*8 + 5	n*8 + 4	n*8 + 3	n*8 + 2	n*8 + 1	n*8 + 0

FS Pointer

A FSPointer is a structure that addresses filesystem objects.

Name	Offset	Size	Meaning
Cluster	0	8	The cluster on the disk of this object
Byte	8	2	The byte offset within the cluster of the object

FSPointerEx

A FSPointer is a structure that addresses filesystem objects. The Ex version is designed to handle multiple disks.

Name	Offset	Size	Meaning
Disk	0	2	The disk identifier for the disk on which described FS object resides.
Cluster	2	8	The cluster on the disk of this object
Byte	10	2	The byte offset within the cluster of the object

File Entry

A file entry describes a filesystem object such as a directory or a file.

Name	Offset	Size	Meaning
Type	0	1	The type of entry this is. 0xD1 - Directory, 0xF1 - file
Checksum	1	1	A CRC32 checksum of the file entry
File Name	2	482	The UTF-16 filename of the object. 241 characters.
Size	484	8	The size of the object - bytes for a file, entries for a directory.
Attributes	492	10	An FSPointer to attributes inode
Entries	502	10	An FSPointer to respective inode (file or directory)

Directory Inode

The directory inodes are pointed to by a directory entry. They are similar to Ext inodes in function. The structure is as follows:

Name	Offset	Size	Meaning
Type	0	1	A type field. 0xD0 = Directory inode
Checksum	1	1	A CRC32 checksum of the inode.
Entries	2	490	Array of 49 FSPointers, point to file entries of directory contents
Backlink	492	10	FSPointer back to previous element (either inode or entry)
Next Inode	502	10	FSPointer to next inode if needed (cluster is zero if unused)

DirectoryEx Inode

The Ex version supports CFS64 2.0 features. The structure is as follows:

Name	Offset	Size	Meaning
Type	0	1	A type field. 0xD2 = DirectoryEx inode
Checksum	1	1	A CRC32 checksum of the inode.
Entries	2	480	Array of 40 FSPointerExs, point to file entries of directory contents
Reference Count	4	482	Reference count for this inode - traditional hard links
Reserved	2	486	Reserved for future use. Set to 0
Backlink	488	12	FSPointerEx back to previous element (either inode or entry)
Next Inode	500	12	FSPointerEx to next inode if needed (cluster is zero if unused)

File Inode

The file entry is pointeed to by the file table like an Ext inode. The structure is as follows:

Name	Offset	Size	Meaning
Type	0	1	0xF0 = File Inode
Checksum	1	1	A CRC32 checksum of the inode
Clusters	2	488	An array of 61 cluster addresses.
Backlink	490	10	An FSPointer to the previous inode in this chain (or the file entry if the first inode)
Next	500	10	An FSPointer to the next inode. CLuster is 0 if this is the last inode.
Reserved	510	2	Reserved, must be 0

Atttributes Inode

This contains file metadata, including timestamps and security.

Name	Offset	Size	Meaning
Type	0	1	0xA0 for an attributes inode
Checksum	1	2	A CRC32 checksum of the inode
Owner	2	16	The UUID of the owner.
Created	18	8	Teratime creation timestamp
Modified	26	8	Teratime last modification timestamp
Accessed	34	8	Teratime last accessed timestamp
Flags	42	1	File flags - see later for description
Security Entries	43	432	An array of 24 security entries - see next table
Security Inode	475	10	An FSPointer to a security inode, if more entries are required.
Extended Attributes	485	10	An FSPointer to the xattr inode, if present
Backlink	495	10	Points back to file entry
Reference Count	505	4	CFS64 2.0+ - used to keep track of hard links to a file.
Reserved	509	3	Padding bytes, must be 0. May be used in future versions.

Security Entry

Name	Offset	Size	Meaning
UUID	0	16	The UUID of the user or group this relates to
Group	16	1	1 if the UUID is a group, 0 if a user.
Permissions	17	1	Bit 0: r, Bit 1: w, Bit 2: x. Unix-style permissions. other bits reserved.

Security Inode

More security entries if required

Name	Offset	Size	Meaning
Type	0	1	0x50 For Security inode
Checksum	1	1	CRC32 checksum of inode
Entries	2	486	27 security entries
Backlink	488	10	FSPointer to previous inode
Next	498	10	FSPointer to next inode - cluster is 0 if this is the last.
Reserved	508	4	Reserved, may be used in future. Must be 0 for now.

xattr Entry

Name	Offset	Size	Meaning
Type	0	1	0xA8 for xattr table
Checksum	1	2	CRC32 Checksum of the inode
Name	2	256	256 chars for the name (UTF-8). Not UTF-16 as this is internal - the name of the attribute.
Data	258	224	224 Bytes of the xattr data - format is dependent on name.
Inode	482	10	FSPointer to the next inode, if required for the xattr. Cluster is 0 if unused.
Backlink	492	10	Backlink to previous xattr entry, or attributes inode.
Next Entry	502	10	The next xattr: THIS IS A DIFFERENT ATTRIBUTE. The next inode is in the inode field.

xattr Inode

Name	Offset	Size	Meaning
Type	0	1	0xAF for xattr inode
Checksum	1	2	CRC32 Checksum of the inode
Data	2	490	490 bytes of xattr data.
Backlink	492	10	FSPointer to previous inode or entry
Next	502	10	Points to next inode. Cluster is 0 if this is the last inode.

CF64 v2.0 features

Overview

CFS64 v2.0 adds support for some additional features. In particular, it supports journaling, virtual volumes spread across multiple partitions, and support for hard links and symbolic links. Data storage now supports extents and indexes. In particular, it does this in a manner compatible with CFS64 v1, by making use of the xattr mechanism regularly. A non-bootable CFS64 v1 partition can be mounted as v2 without any changes. If a CFS64 v2 partition doesn't use the new inode structures, it could be mounted as a read only v1 disk. Indeed, harder links will function correctly in CFS64 v1 read-only mode.

Multiple Disk Metadata

Metadata regarding multiple disk volumes is stored as xattr's on the root directory. Each disk will have its own root directory, merged into one under the virtual volume. As the root directory exists, the xattr list of disks "DiskVolumeSet" can be stored. This consists of a flat list of the disks, with length as described in the MASTER table.

Name	Offset	Size	Meaning
Disk Index	0	2	The unique index for the disk within this volume
Disk ID	2	16	The UUID of the disk

Hard Links - detail

Hard links are implemented by pointing a directory entry to the file entry for the file/directory to be hard linked. This differs from traditional hard links, which point to the inode. Should the traditional mode be used, the extended inode must be used. The side effect of native hard links (harder links) is that, should the file have its name changed, this will be reflected in the original directory, and also the linked directories. Note that this means consistency checks should be made - the driver should check that there is not a name conflict in any directory. Although there is no limitation of the FS against files with the same name, this is dangerous territory.

Journaling

CFS64 stores a journal file as an xattr ("FileSystemJournal") of the root directory. The structure is as follows:

Header

Name	Offset	Size	Meaning
Mode & flags	0	1	The journaling mode. 0 = disabled, 1 = metadata-only, 2 = complete
Checksum	1	1	A CRC32 checksum of the header
Entries	2	8	The number of transactions recorded in the journal.

Entry

Name	Offset	Size	Meaning
Type	0	1	The type of write. 0 = availability bitmap, 1 = file system structure, 2 = block write.
Checksum	1	1	A CRC32 checksum of the entry - disregard if invalid. Transaction was not completed.
Address	2	8/10	The address of the write. If type=0, this is the block represented. If type=1, this is FSPointer. If type=2, this is block address.
Data	10/12	1/512/4096	The data to be written. Type=0, bit0=CAT value, bit1=FSTable value. Rest reserved. Type=1, this is file system data structure. Type=2, this is the block value.

C structures

 typedef uint64_t teratime;
 typedef uint16_t wchar_t;
 typedef uint16_t char16_t;

//MASTER table
struct CFS64_Master {
	uint8_t bldrjmp[2];		//JMP +0x40 (0x42)
	teratime creation;
	uint32_t creator;
	uint64_t disksize;		//Clusters
	uint16_t bytespercluster;
	uint8_t tablecopies;
	uint16_t majorversion;
	uint8_t minorversion;
	uint64_t FStabpointer;
	uint64_t roottablepointer;
	char FSID[8];			//CFS64
	char16_t vollabel[11];
	uint8_t bootloader[436];
	uint16_t bootsig;		//0xAA55
}__attribute__ ((packed));

enum CreatorID {
	CREATOR_ID_CHAIOS,
	CREATOR_ID_WINFORMATTER,	//us
	CREATOR_ID_LINUX,
	CREATOR_ID_HANDCODED = 0xCAFEBABE,
	CREATOR_ID_THIRD_PARTY = 0xDEADBEEF,
	CREATOR_ID_INCOMPATIBLE = 0xFFFFFFFF
};

//File tables
struct FSPointer {
	uint64_t Cluster;
	uint16_t byte;
}__attribute__ ((packed));

struct CFS64_FileEntry {
	uint8_t type;		//0xF1 for file, 0xD1 for directory,... 0 for free
	uint8_t checksum;
	wchar_t fileName[241];
	uint64_t size;
	struct FSPointer attrbiutes;
	struct FSPointer entries;
}__attribute__ ((packed));

enum FileEntryType {
	SecurityInode = 0x50,
	DirectoryInode = 0xD0,
	DirectoryEntry = 0xD1,
	AttributeInode = 0xA0,
	ExtendedAttributeHeader = 0xA8,
	ExtendedAttributeInode = 0xAF,
	FileInode = 0xF0,
	FileEntry = 0xF1
};

struct CFS64_FileInode {
	uint8_t type;		//0xF1 for directory
	uint8_t checksum;
	uint64_t clusters[61];
	struct FSPointer backlink;
	struct FSPointer nextInode;
	uint16_t reserved;
}__attribute__ ((packed));

struct CFS64_DirInode {
	uint8_t type;		//0xD1 for directory
	uint8_t checksum;
	struct FSPointer entries[49];
	struct FSPointer backlink;
	struct FSPointer nextInode;
}__attribute__ ((packed));

//Now attributes

struct UUID {
    uint32_t Data1;
    uint16_t Data2;
    uint16_t Data3;
    uint8_t Data4[ 8 ];
}__attribute__ ((packed));

struct CFS64_SecurityEntry {
	struct UUID userID;
	uint8_t isgroup;
	struct {
		uint8_t canRead : 1;
		uint8_t canWrite : 1;
		uint8_t canExecute : 1;
	}permissions;
}__attribute__ ((packed));

struct CFS64_Flags {
	uint8_t DeleteOnly : 1;
	uint8_t Hidden : 1;
	uint8_t ContentsHidden : 1;
	uint8_t NonPrivelegedRead : 1;
	uint8_t ModifyOnly : 1;
	uint8_t NonPrivilegedWrite : 1;
	uint8_t NonPrivilegedExecute : 1;
	uint8_t SystemFile : 1;
}__attribute__ ((packed));

struct CFS64_Attributes {
	uint8_t type;
	uint8_t checksum;
	struct UUID ownerID;
	teratime created;
	teratime modified;
	teratime accessed;
	struct CFS64_Flags flags;
	struct CFS64_SecurityEntry securityentry[24];
	struct FSPointer securityInode;
	struct FSPointer xattr;
	struct FSPointer backlink;
	uint8_t reserved[7];
}__attribute__ ((packed));

struct CFS64_Security {
	uint8_t type;
	uint8_t checksum;
	struct CFS64_SecurityEntry entries[27];
	struct FSPointer backlink;
	struct FSPointer nextentry;
	uint32_t reserved;
}__attribute__ ((packed));

struct CFS64_xattr_entry {
	uint8_t type;
	uint8_t checksum;
	char name[256];		//type of attribute, so we don't need unicode
	uint8_t data[224];
	struct FSPointer inode;
	struct FSPointer backlink;
	struct FSPointer nextentry;
}__attribute__ ((packed));

struct CFS64_xattr_inode {
	uint8_t type;
	uint8_t checksum;
	uint8_t data[490];
	struct FSPointer backlink;
	struct FSPointer nextentry;
}__attribute__ ((packed));

Inodes

The "Inode entries" referenced to before are pointers to clusters. For directory inodes these reference both cluster and byte, and therefore are 10 bytes long (64bit cluster and 16 bit byte references). File inodes only need cluster references, and therefore the entries are 8 bytes long.

Indirection

Inodes point to other inodes as a doubly linked list, with backlinks and forward links. This means no size limits like ext2 - but seek times are greater. The structure is optimized for sequential reading.

Unused Inodes

Unused inodes are set to 0.

Special Fields

Here are decriptions of the bit-flags fields:

Flags

Flags are the general attributes, such as read-only, hidden and similar.

7	6	5	4	3	2	1	0
SF	NX	NW	MO	NR	CH	HI	DO

Meanings:

• DO: Delete Only (Read only field modify protect)
• HI: Hidden
• CH: Contents Hidden (dir-only)
• NR: Non-Privileged Read - read ability for people without permissions
• MO: Modify Only (Read-only deletion protect)
• NW: Non-Privileged Write - write version of NR
• NX: Non-Privileged Execute - execute version of NW
• SF: System File - ultimate protection. Cannot be changed under ChaiOS (my, Bellezzasolo's OS). Drivers should be installed to a special directory.

Flags that apply to all users

• DO
• HI
• CH
• MO
• SF

Other flag's behaviour

The NR,NW and NX flags only apply to non-privileged users, i.e those who don't have their permissions bit set.

Project Status

Implemented for grub, however in active development. Here are the components required and their status:

• Formatter - Buggy (Win32)
• Grub module - Slightly buggy
• Driver - Not Started. Waiting for HDD and formatter