GIET_VM / FAT32 File System

The fat32.c​ and fat32.h​ files define the GIET_VM File System, that respect the FAT32 standard.

1) General Principles

This implementation supports only block devices with block_size = 512 bytes.

The max size for a single file is 4 Gbytes.

From the software point of view, a cluster is the smallest storage allocation unit on the block device : any file (or directory) occupies at least one cluster, and a given cluster cannot be shared by 2 different files.

This implementation supports only cluster size = 4 Kbytes (i.e. 8 contiguous blocks on block device).

The FAT region on the block device is an array of 32 bits words defining the linked list of clusters allocated to a given file in the DATA region of the block device. The DATA region is actually an array of 4 Kbytes buffers (i.e. an array of clusters). Each slot in the FAT array contains a cluster index, that is the index of the next allocated cluster for a given file. The cluster index in the FAT array is also the cluster index in the DATA region array. The cluster index value cannot be larger than 0x0FFFFFFF (i.e. 256 M). The max addressable storage capacity in the DATA region on the block device is therefore (256 M * 4 Kbytes) = 1 Tbytes. We use the variable cluster to name the cluster index.

This implementation defines four data structures:

• The File-Cache and Fat-Cache are dynamically allocated memory caches, implemented in the distributed kernel heap. There is actually one independent cache per file (called File_Cache), and one cache for the FAT itself (called Fat_Cache). The cache size is not fixed: it is dynamically increased from the kernel heap as required by the read / write access to the files or to the FAT itself. The memory allocated to a given cache_file is only released when the file is closed by all tasks using it.

• The Inode-Tree is an internal representation of the FAT. It is a sub-tree of the File System tree. Each node define a file or a directory, and contains a pointer on the associated File-Cache. This Inode-Tree is dynamically increased (from the distributed kernel heap) when a new file or a directory is accessed. The memory allocated to the Inode-Tree is only released in case of system crash.

• The File-Descriptor-Array is a statically defined array of file descriptors. According to the UNIX semantic, a private file descriptor is allocated to each task requiring to open the file, and contains mainly the current file pointer (called offset). The max number of file descriptors is defined by the GIET_OPEN_FILES_MAX global variable (in the get_config.h file).

• The global Fat-Descriptor contains general information such as the FAT region lba and size, the DATA region lba and size, pointers on the Fat-Cache or Inode-Tree, the File-Descriptor-Array, and the locks protecting the FAT shared structures. It contains also a single block buffer (512 bytes) used in the initialization phase, and for FS_INFO sector update.

To support various block device peripheral, this FAT32 implementation defines a generic function to transparently access various physical block devices, using the driver specified in the hard_config.h file. Five drivers are presently supported ( IOC_BDV / IOC_HBA / IOC_SDC / IOC_SPI / IOC_RDK ).

WARNING 1: A node name (file or directory) cannot be larger than 31 characters.

WARNING 2: There is no rescue mechanism (at the moment) in case of heap overflow: The system crash with a nice error message on the kernel terminal if the heap defined in the mapping is too small...

2) Cache Structure & Write Policy

The Fat_Cache and the File_Cache have the same organisation. Each cache contains an integer number of clusters, as the cluster is the smallest unit of data that can be loaded from the block device to a cache. To reduce the access time, this set of clusters is organized as a 64-Tree: each node has one single parent and (up to) 64 children. The leaf nodes are the cluster descriptors.

WARNING: To access a given cluster in a given file, we use the cluster_id variable, that is the index of cluster inside the file. This cluster_id variable is different from the cluster variable, that is used to index both the FAT and the DATA region on block device.

The cluster_id variable must be split in pieces of 6 bits, that are used to access the proper children at a given level in the 64-Tree. The depth (number of levels) of the 64-Tree depends on the file size :

File Size	levels
up to 256 Kbytes	1
from 256 Kbytes to 16 Mbytes	2
from 16 Mbytes to 1 Gbytes	3
larger than 1 Gbytes	4

For the File_Cache, the GIET_VM implements a Write-Back policy. In case of write, the data are always modified in the cache. In case of miss, new clusters are allocated to the target file, the cache is updated from the block device, and the data are modified in the cache, but not on the block device. The modified clusters are written on the block device only when the file is closed, using the dirty flag implemented in each cluster descriptor.

For the Fat_Cache, the GIET_VM implements a Write-Through policy. When the FAT content is modified (i.e. when new clusters are allocated to an existing file, or when a new file (or directory) is created, the modifications are written in the fat_cache (that must be updated in case of miss), and are immediately reported to the block device, for each modified cluster.

4) Extern Functions

The following functions implement the FAT related system calls.

int _fat_init( unsigned int kernel_mode )

This function initializes the FAT structures. It is called twice, by the boot-loader, and by the kernel_init.

• in boot mode (kernel_mode == 0), it initialises only the statically defined Fat-Descriptor, using informations found in the boot sector and FS-INFO sector, that are loaded in the FAT descriptor 512 bytes buffer. In this mode, it is used by the boot code to load the kernel.elf file, and the various application.elf files,

into memory by accessing directly to the block device.

• in kernel mode (kernel_mode != 0), it uses the distributed kernel heap to initialises the dynamically allocated structures such as the Inode-Tree, the Fat-Cache, and the File-Cache for the root directory.

It returns 0 if success / It returns -1 if failure.

int _fat_open( char* pathname , unsigned int flags )

This function implements the giet_fat_open() system call. The semantic is similar to the UNIX open() function, but only the O_CREATE and O_RDONLY flags are supported. The UNIX access rights are not supported. If the file does not exist in the specified directory, it is created, and the Inode-Tree, the Fat-Cache and the FAT region on device are updated. If the specified directory does not exist, an error is returned. It allocates a file descriptor to the calling task, for the file identified by "pathname". If several tasks try to open the same file, each task obtains a private file descriptor and the reference count is updated. A node name (file or directory) cannot be larger than 31 characters.

• pathname : define both the specified directory and the file name.
• flags : O_CREATE and O_RDONLY can be ored.

It returns the file descriptor index if success. It returns a negative value if error:

• -1 : "fat not initialised"
• -2 : "path to parent not found"
• -3 : "one name in path too long"
• -4 : "file not found"
• -5 : "Cannot update parent directory"
• -6 : "Cannot update DATA region"
• -7 : "Cannot update FAT region"
• -8 : "Cannot update FS_INFO sector"
• -9 : "file descriptor array full"

int _fat_close( unsigned int fd_id )

This function implements the "giet_fat_close()" system call. The semantic is similar to the UNIX "close()" function. It decrements the inode reference count, and release the fd_id entry in the file descriptors array. If the reference count is zero, it writes all dirty clusters on block device, and releases the memory allocated to the file_cache: The cache 64-Tree infrastructure (depending on file size) is kept, but all buffers and all buffer descriptors are released.

• fd_id : file descriptor index

It returns 0 if success. It returns a negative value if error:

• -1 : "FAT not initialised"
• -2 : "Illegal file descriptor"
• -3 : "Cannot update DATA region for closed file"
• -4 : "Cannot release memory"

int _fat_file_info( unsigned int fd_id , unsigned int* size , unsigned int* offset )

This function implements the giet_fat_file_info() system call. It returns the size and the current offset value for a file identified by the "fd_id" argument.

• fd_id : file descriptor index
• size : pointer on the size (return buffer)
• offset : pointer on the offset (return buffer)

It returns 0 if success. It returns a negative value if error:

• -1 : "FAT not initialised"
• -2 : "Illegal file descriptor"
• -3 : "File not open"

int _fat_read( unsigned int fd_id , void* buffer , unsigned int count )

This function implements the "giet_fat_read()" system call. It access the File-Cache associated to the file identified by the file descriptor, and transfers "count" bytes from the cache to the user buffer, starting from the current file offset. In case of miss in the File_Cache, it loads all involved clusters into the cache.

• fd_id : file descriptor index
• buffer : pointer on the memory buffer
• count : number of bytes

It returns the number of bytes actually transfered if success. It returns 0 if (offset + count > file_size). It returns a negative value if error:

• -1 : "FAT not initialised"
• -2 : "Illegal file descriptor"
• -3 : "File not open"
• -4 : "Cannot load file from device"

int _fat_write( unsigned int fd_id , void* buffer , unsigned int count )

This function implements the "giet_fat_write()" system call. It access the File-Cache associated to the file identified by the file descriptor, and transfers count bytes from the user buffer, to the cache, starting from the current file offset. It loads all involved clusters into cache if required. If (offset + count) is larger than the current file size, it increases the file size. It allocates new clusters if required, and updates the Fat-Cache and the FAT region on block device. As it implements a Write-Back policy, the DATA region on block device is not updated, but the modified clusters are marked dirty.

• fd_id : file descriptor index
• buffer : pointer on the memory buffer
• count : number of bytes

It returns the number of bytes actually transfered if success. It returns a negative value if error.

• -1 : "FAT not initialised"
• -2 : "Illegal file descriptor"
• -3 : "File not open"
• -4 : "File not writable"
• -5 : "No free clusters"
• -6 : "Cannot update parent directory entry"
• -7 : "Cannot access File-Cache"

int _fat_lseek( unsigned int fd_id , unsigned int offset , unsigned int whence )

This function implements the "giet_fat_lseek()" system call. It repositions the offset in the file defined by the file descriptor, according to the offset and whence arguments. The accepted values for the whence argument are SEEK_SET and SEEK_CUR:

• SEEK_SET => new_offset = offset
• SEEK_CUR => new_offset = current_offset + offset

Arguments:

• fd_id : file descriptor index
• offset : pointer on the memory buffer
• count : number of bytes

It returns new offset value (bytes) if success. It returns a negative value if error:

• -1 : "FAT not initialised"
• -2 : "Illegal file descriptor"
• -3 : "File not open"
• -4 : "Illegal whence argument"

int _fat_mkdir( char* pathname )

This function implements the giet_fat_mkdir() system call, that has the same semantic as the UNIX mkdir() function. It creates a new directory in the File System as specified by the pathname argument. The FAT region is updated. The Inode-Tree is updated.

• pathname : complete pathname

It returns 0 if success. It returns a negative value if error:

• -1 : "Fat not initialised"
• -2 : "Path to parent not found"
• -3 : "One name in path too long"
• -4 : "Directory already exist"
• -5 : "No free cluster"
• -6 : "Cannot update parent directory"
• -7 : "Cannot update parent DATA region"
• -8 : "Cannot update FAT region"
• -9 : "Cannot update FS-INFO"
• -10 : "Cannot update directory DATA region"

int _fat_remove( char* pathname , unsigned int should_be_dir )

This function implements the giet_fat_unlink() system call, that has the same semantic as the UNIX unlink() function. It removes the file identified by the pathname argument from the File System. An error is returned if the number of references (number of open file descriptors) is not zero. All clusters allocated to this file in the DATA region are released. The FAT region is updated on the block device and the Fat-Cache is updated. The memory allocated to the File_Cache is released. The Inode-Tree is updated.

• pathname : directory complete pathname

It returns 0 if success. It returns a negative value if error:

• -1 : "FAT not initialised"
• -2 : "File/Directory? not found"
• -3 : "Name too long in path"
• -4 : "Has the wrong type"
• -5 : "File still open"
• -6 : "Cannot scan directory"
• -7 : "Directory not empty"
• -8 : "Cannot remove file/dir from FS"

int _fat_rename( char* old_path , new_path )

This function implements the giet_fat_rename() system call. It moves an existing file or directory from one node (defined by "old_path" argument) to another node (defined by "new_path" argument) in the FS tree. The type (file/directory) and content are not modified. If the new_path file/dir exist, it is removed from the file system, but only if the remove condition is respected (directory empty / file not referenced). The removed entry is only removed after the new entry is actually created.

• old_path : old path-name (from root).
• new_path : new path-name (from root).

It returns 0 if success. It returns a negative value if error:

• -1 : "FAT not initialised"
• -2 : "old_path not found"
• -3 : "new_path not found"
• -4 : "cannot scan to_remove directory"
• -5 : "to_remove directory not empty"
• -6 : "to_remove file still referenced"
• -7 : "cannot add new node to new_parent directory"
• -8 : "cannot update new_parent directory on device"
• -9 : "cannot remove old node from old_parent directory"
• -10 : "cannot update old_parent directory on device"
• -11 : "cannot remove to_remove node from FS"

int _fat_list( char* pathname )

This function implements the giet_fat_list() system call. It displays the content of a directory identified by the pathname argument. It returns 0 if success. It returns a negative value if error:

• -1 : "FAT not initialised
• -2 : "Directory not found"
• -3 : "Name in path too long
• -4 : "Not a directory"
• -5 : "Cannot access directory"

int _fat_read_no_cache( char* pathname , unsigned int buffer_vbase , unsigned int buffer_size )

This functiond load a file identified by the pathname argument into the memory buffer defined by the buffer_vbase / buffer_size arguments. It is intended to be called by the boot-loader, as it uses neither the dynamically allocated FAT structures (Inode-Tree, Fat_Cache or File-Cache), nor the File-Descriptor-Array. It uses only the 4096 bytes buffer defined in the FAT descriptor.

• pathname : file complete pathname
• buffer_vbase : memory buffer virtual address
• buffer_size : buffer size (bytes)

It returns 0 if success. It returns a negative value if error.

• -1 : "FAT not initialised"
• -2 : "File not found"
• -3 : "Buffer too small"
• -4 : "Cannot access block device"
• -5 : "Cannot access FAT on block device"

5) Internal functions

The following functions can be used to implement new system calls if required.

int _fat_ioc_access( unsigned int use_irq , unsigned int to_mem , unsigned int lba , unsigned int buf_vaddr , unsigned int count )

This function transfer one or several blocks between the block device and a memory buffer by calling the relevant driver.

• use_irq : boolean (use descheduling mode if supported by the IOC driver)
• to_mem : boolean (from block device to memory if non zero)
• lba : logical block address on block device
• buf_vaddr : memory buffer virtual address
• count : number of blocks to be transferred

It returns 0 if success / It returns -1 if failure.