RKFS -A new filesystem for Linux Operating System

from R.K.Raja (rajkanna_hcl@yahoo.com)

RKFS is the acronym for 'RK Filesystem'. It is a file system that has been designed and implemented from the scratch for small devices (the devices with less capacity). The main goal is to provide a simple but yet powerful file system that provides all the features as MinixFS and Ext2FS but for small devices. It is the only file system that has been designed and implemented, keeping the characteristics of small devices in mind. It shares many properties with the traditional UNIX file systems. It has the concept of blocks, inodes and directories. It is highly robust and provides excellent performance as Ext2 & Minix file systems.

RKFS is known to work on 2.4.x linux kernels.

A feature wise comparison of RKFS, MinixFS & Ext2FS is given below. This clearly shows one what RKFS is for.

Filesystem creation benchmarks

Feature	RKFS	MinixFS	Ext2FS
Filesystem creation	Simple & Fastest	Simpe & less faster than RKFS	Simpe & less faster than RKFS
The benchmark was done on a 1.4 MB floppy disk	1 secs	2 secs	5 secs

Total metadata blocks used internally

Feature	RKFS	MinixFS	Ext2FS
Total metadata blocks used/reserved on a newly created FS on a device with 1440 blocks	3 blocks ( 1 block for boot sector, 1 block for superblock, 1 block for inode table for root inode )	19 blocks	28 blocks ( 1 block for boot sector, 1 block for superblock, 1 block for group descriptor, 1 block for block bitmap block, 1 block for inode bitmap block, 23 blocks for inode table )

Total free blocks available on a newly created FS

Feature	RKFS	MinixFS	Ext2FS
Total free blocks (available to user to store data on a newly created FS on device with 1440 blocks )	1436	1420	1399

Total free inodes available on a newly created FS

Feature	RKFS	MinixFS	Ext2FS
Total free inodes ( available to the user on a newly created FS on a device with 1440 blocks )	1436 ( This means user could create 1436 empty files! )	479 ( This means user could create only 479 files, even if the files are empty! )	173 ( This means user could create only 173 files, even if they are just 0 bytes file!! )

Inode block allocation strategy

Feature	RKFS	MinixFS	Ext2FS
Inode block allocation strategy	Dynamic ( Inode blocks are allocated on demand )	Fixed allocation ( Inode blocks are allocated at the time of filesystem creation  )	Fixed allocation ( Inode blocks are allocated at the time of filesystem creation )

Inode block de-allocation strategy

Feature	RKFS	MinixFS	Ext2FS
Inode block de-allocation strategy	Dynamic  ( This means when all the inode in an inode block are freed, then that inode blocks will also be freed )	No de-allocation strategy ( This means that once the inode blocks are allocated during filesystem creation, they cannot be freed for  ever! )	No de-allocation strategy ( This means that once the inode blocks are allocated during filesystem creation, they cannot be freed for   ever! )

Comparison of other standard features

Feature	RKFS	MinixFS	Ext2FS
Support for all standard unix file types (like directories, regular files, device files, hard & soft links )	YES	YES	YES
Max FS size	65 MB	65 MB	2 TB
Max file size	65 MB	65 MB	2 GB
Max filename length	252 characters	30 characters	255 characters
Total direct data blocks in inode	39 ( This means a file of size 39K would  be accessed more faster than a file with sizes greater than 39K )	7	12
Blocks reserved for superuser	NO	NO	YES ( default 5 % )
User land program (mkfs)	YES	YES	YES
User land program (dumpfs)	YES	NO	YES
User land program (debugfs)	NO ( Not really required )	NO	YES
User land program (fsck)	NO (Under construction )	YES	YES
Access / Change / Delete time support	NO ( all the three are same! )	YES	YES
Variable blocksize support	NO ( Not really required for small devices )	NO	YES
Block sync read/write performance	Same as MinixFS	Better	A bit advanced ( because of clusterred block allocation strategy )
Block async read/write performance	Same as MinixFS	Better	A bit advanced ( because of the clusterred block allocation strategy )
Extensible	YES	YES	YES

Filesystem layout comparison

Ext2FS Layout

Boot Sector

Block Group1

Block Group2

.....

Block GroupN

Number of blocks in each group = 8192

Super Block

Group Descriptors

Block Bitmap Block

Inode Bitmap Block

Inode Table Block1

.....

Inode Table BlockN

Data Block1

.....

Data BlockN

MinixFS Layout

Super Block

Inode Bitmap Block

Zone (Block) Bitmap Block

Inode Table Block1

.....

Inode Table BlockN

Data Block1

.....

Data BlockN

RKFS Layout

Boot Sector

Block Group1

Block Group2

.....

Block GroupN

Block size = 1K
Number of blocks in each group = 1440

Super Block

Inode Table Block (Required for root inode )

Remaining blocks in the group are used for Inode table Blocks and  Data blocks (Inode Table Blocks are allocated  / de-allocated dynamically)

RKFS use cases

Since RKFS has been designed and implemented keeping the characteristics of small
devices in mind, it would be an ideal candidate when we:

• have space constraints
• need to store information’s that cannot fit into devices/partitions created with other file systems
• need to create more number of smaller files

RKFS in action

Total free blocks available on a newly created filesystem

RKFS

[root@localhost rkfs]# ./mkrkfs -v /dev/fd0
rkfs (1.0), for intel based linux, 30/01/2002
Creating rkfs filesystem on the device /dev/fd0
Device /dev/fd0 has 1440 blocks.
Filesystem created.

[root@localhost rkfs]# mount -t rkfs /dev/fd0 /mnt

[root@localhost rkfs]# cd /mnt

[root@localhost /mnt]# df -k .
Filesystem           1k-blocks      Used Available Use% Mounted on
/dev/fd0                  1440         4      1436   1% /mnt

Ext2FS

[root@localhost /root]# mke2fs -v -m 0 /dev/fd0
mke2fs 1.19, 13-Jul-2000 for EXT2 FS 0.5b, 95/08/09
Filesystem label=
OS type: Linux
Block size=1024 (log=0)
Fragment size=1024 (log=0)
184 inodes, 1440 blocks
0 blocks (0.00%) reserved for the super user
First data block=1
1 block group
8192 blocks per group, 8192 fragments per group
184 inodes per group

Writing inode tables: done
Writing superblocks and filesystem accounting information: done

[root@localhost /root]# mount /dev/fd0 /mnt

[root@localhost /root]# cd /mnt

[root@localhost /mnt]# df -k .
Filesystem           1k-blocks      Used Available Use% Mounted on
/dev/fd0                  1412        13      1399   1% /mnt

Total number of free inodes available on a newly created filesystem

RKFS

[root@localhost /mnt]# stat -f .
  File: "."
    ID: 0        0        Namelen: 252     Type: UNKNOWN (0x713)
Blocks: Total: 1440       Free: 1436       Available: 1436       Size: 1024
Inodes: Total: 0          Free: 1436

EXT2FS

[root@localhost /mnt]# stat -f .
  File: "."
    ID: 0        0        Namelen: 255     Type: EXT2
Blocks: Total: 1412       Free: 1399       Available: 1399       Size: 1024
Inodes: Total: 184        Free: 173

Dynamic Inode block allocation / de-allocation

RKFS

[root@localhost /mnt]# stat -f .
  File: "."
    ID: 0        0        Namelen: 252     Type: UNKNOWN (0x713)
Blocks: Total: 1440       Free: 1436       Available: 1436       Size: 1024
Inodes: Total: 0          Free: 1436
[root@localhost /mnt]#

[root@localhost /mnt]# /tmp/test.sh
Creating 175 empty files... Done.

[root@localhost /mnt]# ls
file0    file116  file134  file152  file170  file31  file5   file68  file86
file1    file117  file135  file153  file171  file32  file50  file69  file87
file10   file118  file136  file154  file172  file33  file51  file7   file88
file100  file119  file137  file155  file173  file34  file52  file70  file89
file101  file12   file138  file156  file174  file35  file53  file71  file9
file102  file120  file139  file157  file18   file36  file54  file72  file90
file103  file121  file14   file158  file19   file37  file55  file73  file91
file104  file122  file140  file159  file2    file38  file56  file74  file92
file105  file123  file141  file16   file20   file39  file57  file75  file93
file106  file124  file142  file160  file21   file4   file58  file76  file94
file107  file125  file143  file161  file22   file40  file59  file77  file95
file108  file126  file144  file162  file23   file41  file6   file78  file96
file109  file127  file145  file163  file24   file42  file60  file79  file97
file11   file128  file146  file164  file25   file43  file61  file8   file98
file110  file129  file147  file165  file26   file44  file62  file80  file99
file111  file13   file148  file166  file27   file45  file63  file81
file112  file130  file149  file167  file28   file46  file64  file82
file113  file131  file15   file168  file29   file47  file65  file83
file114  file132  file150  file169  file3    file48  file66  file84
file115  file133  file151  file17   file30   file49  file67  file85
[root@localhost /mnt]#

[root@localhost /mnt]# stat -f .
  File: "."
    ID: 0        0        Namelen: 252     Type: UNKNOWN (0x713)
Blocks: Total: 1440       Free: 1418       Available: 1418       Size: 1024
Inodes: Total: 0          Free: 1261
[root@localhost /mnt]#

root@localhost /mnt]# /opt1/rkfs/dumprkfs /dev/fd0
Device /dev/fd0 has 1440 blocks.

***Superblock at offset: 0

Filesystem ID: 1811
Filesystem Ver: 100
Used blocks:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
17 18 19 20 21
Used inodes:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96
97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112
113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128
129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144
145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160
161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176
177 178
Inode table map:
        Index: 0, Block: 2, Count: 10
        Index: 1, Block: 4, Count: 10
        Index: 2, Block: 5, Count: 10
        Index: 3, Block: 6, Count: 10
        Index: 4, Block: 7, Count: 10
        Index: 5, Block: 8, Count: 10
        Index: 6, Block: 9, Count: 10
        Index: 7, Block: 10, Count: 10
        Index: 8, Block: 11, Count: 10
        Index: 9, Block: 12, Count: 10
        Index: 10, Block: 13, Count: 10
        Index: 11, Block: 15, Count: 10
        Index: 12, Block: 16, Count: 10
        Index: 13, Block: 17, Count: 10
        Index: 14, Block: 18, Count: 10
        Index: 15, Block: 19, Count: 10
        Index: 16, Block: 20, Count: 10
        Index: 17, Block: 21, Count: 9
Super block state: Valid
Total blocks: 1440
[root@localhost /mnt]#

[root@localhost /mnt]# df -k .
Filesystem           1k-blocks      Used Available Use% Mounted on
/dev/fd0                  1440        22      1418   2% /mnt
[root@localhost /mnt]#

[root@localhost /mnt]# rm -rf fil*

[root@localhost /mnt]# stat -f .
  File: "."
    ID: 0        0        Namelen: 252     Type: UNKNOWN (0x713)
Blocks: Total: 1440       Free: 1435       Available: 1435       Size: 1024
Inodes: Total: 0          Free: 1435

[root@localhost /mnt]# df -k .
Filesystem           1k-blocks      Used Available Use% Mounted on
/dev/fd0                  1440         5      1435   1% /mnt
[root@localhost /mnt]#

[root@localhost /mnt]# /opt1/rkfs/dumprkfs /dev/fd0
Device /dev/fd0 has 1440 blocks.

***Superblock at offset: 0

Filesystem ID: 1811
Filesystem Ver: 100
Used blocks:
0 1 2 3 14
Used inodes:
0 1 2 3
Inode table map:
        Index: 0, Block: 2, Count: 4
Super block state: Valid
Total blocks: 1440
[root@localhost /mnt]#

EXT2FS

[root@localhost /mnt]# stat -f .
  File: "."
    ID: 0        0        Namelen: 255     Type: EXT2
Blocks: Total: 1412       Free: 1399       Available: 1399       Size: 1024
Inodes: Total: 184        Free: 173
[root@localhost /mnt]#

[root@localhost /mnt]# /tmp/test.sh
touch: creating `/mnt/file173': No space left on device
touch: creating `/mnt/file174': No space left on device

[root@localhost /mnt]# ls
file0    file116  file134  file152  file170  file33  file51  file7   file88
file1    file117  file135  file153  file171  file34  file52  file70  file89
file10   file118  file136  file154  file172  file35  file53  file71  file9
file100  file119  file137  file155  file18   file36  file54  file72  file90
file101  file12   file138  file156  file19   file37  file55  file73  file91
file102  file120  file139  file157  file2    file38  file56  file74  file92
file103  file121  file14   file158  file20   file39  file57  file75  file93
file104  file122  file140  file159  file21   file4   file58  file76  file94
file105  file123  file141  file16   file22   file40  file59  file77  file95
file106  file124  file142  file160  file23   file41  file6   file78  file96
file107  file125  file143  file161  file24   file42  file60  file79  file97
file108  file126  file144  file162  file25   file43  file61  file8   file98
file109  file127  file145  file163  file26   file44  file62  file80  file99
file11   file128  file146  file164  file27   file45  file63  file81  lost+found
file110  file129  file147  file165  file28   file46  file64  file82
file111  file13   file148  file166  file29   file47  file65  file83
file112  file130  file149  file167  file3    file48  file66  file84
file113  file131  file15   file168  file30   file49  file67  file85
file114  file132  file150  file169  file31   file5   file68  file86
file115  file133  file151  file17   file32   file50  file69  file87
[root@localhost /mnt]#

[root@localhost /mnt]# stat -f .
  File: "."
    ID: 0        0        Namelen: 255     Type: EXT2
Blocks: Total: 1412       Free: 1397       Available: 1397       Size: 1024
Inodes: Total: 184        Free: 0
[root@localhost /mnt]#

[root@localhost /mnt]# df -k .
Filesystem           1k-blocks      Used Available Use% Mounted on
/dev/fd0                  1412        15      1397   2% /mnt
[root@localhost /mnt]#

[root@localhost /mnt]#rm -rf file*

[root@localhost /mnt]# df -k .
Filesystem           1k-blocks      Used Available Use% Mounted on
/dev/fd0                  1412        15      1397   2% /mnt

[root@localhost /mnt]# stat -f .
  File: "."
    ID: 0        0        Namelen: 255     Type: EXT2
Blocks: Total: 1412       Free: 1397       Available: 1397       Size: 1024
Inodes: Total: 184        Free: 173
[root@localhost /mnt]#

Space optimization (meta-data blocks design strategy)

RKFS

[root@localhost /mnt]# ls -al /root/test_file
-rw-r--r--    1 root     root      1433600 Apr 30 19:37 /root/test_file
[root@localhost /mnt]#

[root@localhost /mnt]# cp /root/test_file .

[root@localhost /mnt]# sync

[root@localhost /mnt]# stat -f .
  File: "."
    ID: 0        0        Namelen: 252     Type: UNKNOWN (0x713)
Blocks: Total: 1440       Free: 32         Available: 32         Size: 1024
Inodes: Total: 0          Free: 32

[root@localhost /mnt]# df -k .
Filesystem           1k-blocks      Used Available Use% Mounted on
/dev/fd0                  1440      1408        32  98% /mnt

[root@localhost /mnt]# cksum /root/test_file
1632482245 1433600 /root/test_file
[root@localhost /mnt]# cksum ./test_file
1632482245 1433600 ./test_file

EXT2FS

[root@localhost /mnt]# ls -al /root/test_file
-rw-r--r--    1 root     root      1433600 Apr 30 19:37 /root/test_file
[root@localhost /mnt]#

[root@localhost /mnt]# cp /root/test_file .
cp: writing `./test_file': No space left on device

RKFS data structures

RKFS inode

• 100 bytes long
• Inodes per block = 1024 / 100 = 10
• 39 direct blocks
• No support for triple indirection
• Disk version

struct rkfs_inode {
    __u16  i_uid;
   __u16  i_gid;
   __u16  i_mode;
   __u16  i_links_count;
   __u32  i_time;
   __u32  i_size;
   __u16  i_blocks;
   __u16  i_block[RKFS_N_BLOCKS];
};

• In-core version (attached to VFS inode)

struct rkfs_inode_info {
    __u16 i_block[41];
};

RKFS directory-entries

• Directory-entry size = 256 bytes
• Directory-entries per block = 1024 / 256 = 4 (at max )
• Max filename length = 252 characters

struct rkfs_dir_entry {
    __u16 de_inode;
   __u16 de_name_len;
    char  de_name[RKFS_MAX_FILENAME_LEN];
};

Hard and Soft links in RKFS

• Maximum links = 32000
• Support both hard and symbolic link
• No support for fast symbolic link ( wish list )

RKFS superblock

• Size = 944 bytes ( 1 complete block required )
• Block bitmap and Inode bitmap are part of superblock
• Inode table map is also part of superblock
• Block map size = 1440 / 8 / 2 = 90
• Inode map size = Block map size
• Inode table map size = 1440 / 10 (inodes per block) = 144

struct rkfs_super_block {
    __u16 s_fsid;
    __u16 s_fsver;
    __u16 s_block_map[RKFS_BLOCK_MAP_SIZE];
   __u16 s_inode_map[RKFS_INODE_MAP_SIZE];
   __u16 s_itable_map[RKFS_INODE_TABLES_MAP_SIZE][2];
   __u16 s_state;
   __u16 s_total_blocks;
};

Send your comments to: R.K.Raja (rajkanna_hcl@yahoo.com, rajark_hcl@yahoo.co.in)

This project is hosted at SourceForge.net