User:Bellezzasolo/CFS

From OSDev Wiki
Jump to: navigation, search
Filesystems
Virtual Filesystems

VFS

Disk Filesystems
CD/DVD Filesystems
Network Filesystems
Flash Filesystems

Chai File System (CFS)

Contents

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
CFS64.jpg

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
Personal tools
Namespaces
Variants
Actions
Navigation
About
Toolbox