GIET_VM / FAT32 File System

The fat32.c​ and fat32.h​ files define the GIET_VM File System.

1) General Principles

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

The max size for a single file is 4 Gbytes -1.

From the application 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 File-Cache is only released when the file is closed by all threads that have a reference on 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. A private file descriptor is allocated to each thread 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 and 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 for the File-Caches...

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-File. 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-Caches, 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 if required, 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 last reference is closed, using the dirty flag implemented in each buffer 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

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

This function transfers one or several blocks between the block device and a memory buffer by calling the relevant driver. The <use_irq> boolean argument forces the descheduling mode if supported by the IOC driver. The <to_mem> boolean argument defines the transfer direction (from block device to memory if non zero). The <lba> argument is the first block address on the block device. The <buf_vaddr> argument is the memory buffer virtual address. The <count> argument is the number of blocks to be transferred.

It returns 0 on success, or a negative value on failure.

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. The <kernel_mode> argument defines the initialization mode:

• in boot mode (kernel_mode == 0), it initializes only the statically defined Fat-Descriptor, using informations found in the BOOT sector, that is 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 initialize the dynamically allocated structures such as the Inode-Tree, the Fat-Cache, and the File-Cache for the root directory.

Returns GIET_FAT32_OK on success. Returns a negative value on error.

int _fat_open( char* pathname , unsigned int flags )

This function implements the giet_fat_open() system call. It allocates a file descriptor to the calling task, for the file identified by the <pathname> argument. The semantic is similar to the UNIX open() function, but only the O_CREAT, O_RDONLY and O_TRUNCATE <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. If several tasks try to open the same file, each task obtains a private file descriptor and the reference count is updated. WARNING : A node name (file or directory) cannot be larger than 31 characters.

Returns a file descriptor index on success. Returns a negative value on error.

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 for the file identified by the <fd_id> argument. 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.

Returns GIET_FAT32_OK on success. Returns a negative value on error.

int _fat_file_info( unsigned int fd_id , fat_file_info_t* info )

This function implements the giet_fat_file_info() system call. It returns in the <info> argument, the size, offset, and is_dir attributes for a file identified by the <fd_id> argument.

Returns GIET_FAT32_OK on success. Returns a negative value on error.

int _fat_read( unsigned int fd_id , unsigned int vaddr , unsigned int count, unsigned int extend, unsigned int offset , unsigned int modes )

This function implements the giet_fat_read() system call. It accesses the File_Cache associated to the file identified by the <fd_id> argument, and transfers <count> bytes from the cache to the buffer defined by the <vaddr> argument, starting from the current file offset. The <modes> argument define the special access modes: If FAT_PADDR_MODE is set, the <extend> argument defines the physical address extension. If FAT_FORCED_OFFSET is set, the <offset> argument define the actual file offset. In case of miss in the File_Cache, it loads all involved clusters into the cache.

Returns the number of bytes actually transferred. Returns a negative value on error.

int _fat_write( unsigned int fd_id , unsigned int vaddr , unsigned int count , unsigned int extend , unsigned int modes )

This function implements the giet_fat_write() system call. It accesses the File_Cache associated to the file identified by the <fd_id> argument, and transfers <count> bytes from the buffer defined by the <vaddr> argument to the cache, starting from the current file offset. The <modes> argument define the special access modes: If FAT_PADDR_MODE is set, the <extend> argument defines the physical address extension. It loads all involved clusters into cache if required. If (offset + count) is larger than the current file size, the file size is increased. It allocates new clusters if required, and updates the Fat-Cache. The FAT region and the FS-INFO sector are updated 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.

Returns number of bytes actually written on success. Returns a negative value on error.

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 descriptor defined by the <fd_id> argument, according to the <offset> and <whence> arguments. The accepted values for the <whence> argument are SEEK_SET / SEEK_CUR / SEEK_END :

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

Returns new seek value (in bytes) on success. Returns a negative value on error

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 and the FS_INFO sector on block device are updated. The Inode-Tree is updated.

Returns GIET_FAT32_OK on success. Returns a negative value on error.

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 or directory identified by the <pathname> argument from the File System. An error is returned if the number of references (number of open file descriptors, or number of entries for a directory) is not zero. All clusters allocated to this file in the DATA region are released and the Fat-Cache is updated.. The FAT region and the FS-INFO sector are updated on the block device. The memory allocated to the File_Cache is released. The Inode-Tree is updated.

Returns GIET_FAT32_OK on success. Returns a negative value on error.

int _fat_rename( char* old_path , new_path )

This function implements the giet_fat_rename() system call. It moves an existing file or directory in the FS tree, from one node, defined by the <old_path> argument to another node, defined by the <new_path> argument. 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.

Returns GIET_FAT32_OK on success. Returns a negative value on error.

int _fat_opendir( char* pathname )

This function implements the giet_fat_opendir() system call. The semantic is similar to the UNIX opendir() function. If the directory specified by the <pathname> argument does not exist, an error is returned. It allocates a file descriptor to the calling task. If several tasks try to open the same directory, each task obtains a private file descriptor. A node name cannot be larger than 31 characters.

Returns a file descriptor for the directory index on success. Returns a negative value on error.

int _fat_closedir( unsigned int fd_id )

This function implements the giet_fat_closedir() system call. Same behavior as _fat_close(), no check for directory.

Returns GIET_FAT32_OK on success. Returns a negative value on error.

int _fat_readdir( unsigned int fd_id, fat_dirent_t* entry )

This function implements the giet_fat_readdir() system call. It reads one directory entry from the directory identified by the <fd_id> argument provided by giet_fat_opendir(). It returns the following attributes in the <entry> argument : cluster , size , is_dir , and name.

Returns GIET_FAT32_OK on success. Returns a negative value on error.

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

This function load a file identified by the <pathname> argument into the memory buffer defined by the <buffer_vbase> and <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 512 bytes buffer defined in the FAT descriptor.

Returns GIET_FAT32_OK on success. Returns negative value on error.

int _get_file_cache_buffer( fat_node_t* indoor , unsigned int cluster_id , unsigned int writable , fat_cache_desc_t desc )

This function returns in the <desc> argument a pointer on a buffer descriptor contained in a File_Cache. It can be used for a file or for a directory. The searched buffer is identified by the <inode> argument. The <cluster_id> argument is the buffer index in the File-Cache. The <writable> argument define the behaviour in case of miss in the File-Cache:

• if [all clusters (from 0 to cluster_id) are already allocated in FAT] it scan the FAT to find the cluster index on device, and load the missing cluster in the File-Cache, marked as dirty if writable is set.
• if [not writable and all clusters (from 0 to cluster_id) not allocated] it returns an error.
• if [writable and all clusters (from 0 to cluster_id) not allocated], it allocates in FAT the required cluster, it updates the size in the inode and dentry (for a file), and load the missing cluster in the File-Cache, marked as dirty.

This function is called by the _sys_fat_mmap() function, and by other FAT functions. It does not take the FAT lock, that must be taken by the caller.

It returns GIET_FAT32_OK on success, and returns a negative value on error.

int _get_fat_cache_buffer( unsigned int cluster_id , fat_cache_desc desc )

This function returns in the <desc> argument a pointer on a buffer descriptor contained in the Fat_Cache. The <cluster_id> argument is the buffer index in the FAT_Cache. In case of miss, a 4 Kbytes buffer and a buffer descriptor are allocated from the local heap, and the missing cluster is loaded in the Fat_Cache.

It returns GIET_FAT32_OK on success, and returns a negative value on error.

5) Internal functions

void _display_cluster_list()

This debug function displays the list of clusters allocated to one file or directory.

void _display_fat_descriptor()

This debug function displays the FAT descriptor content.

void _get_name_from_long( unsigned char* buffer , char* name )

This function extract a (partial) name from a LFN directory entry.

void _get_name_from_short( unsigned char* buffer , char* name )

This function extract a <name> from a NORMAL directory entry.

unsigned int _get_levels_from_size( unsigned int size )

This function returns the number of levels of a File-Cache from the <size> of the file.

unsigned int _get_name_from_path( char* pathname , char* name , unsigned int* nb_read )

This function analyses the <pathname> argument, from the character defined by the <nb_read> argument. It copies the found name in the <name> buffer (without '/'), and updates the <nb_read"> argument.

It returns 0 on success. It returns 1 if one name length > NAME_MAX_SIZE characters.

unsigned int _get_last_name( char* pathname , char* name )

This function scan the <pathname> argument, and copies in the <name> buffer the last name in the <pathname>.

It returns 0 on success.It returns 1 if one name length > NAME_MAX_SIZE characters.

unsigned int _get_fat_entry( unsigned int cluster , unsigned int* value )

This function accesses the Fat-Cache and returns in the <value> argument the content of the FAT slot identified by the <cluster> argument. It loads the missing cluster from block device in the Fat-Cache in case of miss.

It returns 0 on success. It returns 1 on error.

unsigned int _set_fat_entry( unsigned int cluster , unsigned int value )

This function writes a new <value> in the Fat-Cache, in the slot identified by the <cluster> argument. It loads the missing cluster from block device in the Fat-Cache in case of miss.

It returns 0 on success, It returns 1 on error.

void _add_inode_in_tree( fat_inode_t* child , fat_inode_t* parent )

This function introduces the inode identified by the <child> argument as a new child for the <parent> inode in the Inode-Tree. All checking are supposed to be done by the caller. Nor the File-Cache, neither the block device are modified.

void _remove_inode_from_tree( fat_inode_t* inode )

This function removes one inode identified by the <inode> argument from the Inode-Tree. All checking are supposed to be done by the caller. Nor the File-Cache, neither the block device are modified.

unsigned int _update_device_from_cache( unsigned int levels , fat_cache_node_t* root , char* string )

This recursive function scan one File-Cache (or the Fat-Cache) from root to leaves, to writes all dirty clusters to block device, and reset the dirty bits. The cache is identified by the <root> an <levels> arguments. The <string> argument is only used for debug.

It returns 0 on success. It returns 1 on error.

unsigned int _update_fs_info()

This function accesses directly the FS_INFO block on the block device, to update the "first_free_cluster" and "free_clusters_number" values, using only the Fat-Descriptor single block buffer.

It return 0 on success. It return 1 on error.

unsigned int _read_entry( unsigned int offset , unsigned int size , unsigned char* buffer , unsigned int little_indian )

This function read a data field (one to four bytes) from an unsigned char[] <buffer>, taking endianness into account. The analysed field is defined by the <offset> and <size> arguments.

unsigned int _cluster_to_lba( unsigned int cluster )

This function returns the lba (logic block address in DATA region) from the <cluster> index. Exit if the cluster value is smaller than 2.

unsigned int _get_nb_entries( fat_inode_t* inode , unsigned int* nb_entries )

This function returns in the <nb_entries> argument the number of entries contained in a directory identified by the <inode> pointer.

It returns 0 on success. It returns 1 on error.

unsigned int _get_child_from_parent( fat_inode_t* parent , char* name , fat_inode_t inode )

This function search in the directory identified by the <parent> inode pointer a child (file or directory) identified by its <name>. It returns in the <inode> argument the searched child inode pointer. If the searched name is not found in the Inode-Tree, the function accesses the File-cache associated to the parent directory. If the child exists on block device, the Inode-Tree is updated, and a success code is returned. If the file/dir does not exist on block device, a error code is returned.

It returns 0 if inode found. It returns 1 if inode not found. It returns 2 in case of error in cache access.

unsigned int _get_inode_from_path( char* pathname , fat_inode_t inode )

For a file (or a directory) identified by the <pathname> argument, this function returns in the <inode> argument the inode pointer associated to the searched file (or directory), with code (0). If the searched file (or directory) is not found, but the parent directory is found, it returns in the <inode> argument the pointer on the parent inode, with code (1). Code (2) and code (3) are error codes. Both the Inode-Tree and the involved Cache-Files are updated from the block device in case of miss on one inode during the search. Neither the Fat-Cache, nor the block device are updated.

It returns 0 if searched inode found It returns 1 if searched inode not found but parent directory found. It returns 2 if searched inode not found and parent directory not found. It returns 3 if one name too long

unsigned int _is_ancestor( fat_inode_t* a , fat_inode_t* b )

This function checks if inode <a> is an ancestor of inode <b>.

It returns 1 if it is true.

unsigned int _get_sfn_name( char* name , unsigned int* length , unsigned int* nb_lfn, char* sfn , unsigned char* checksum )

This function returns in the <length> and <nb_lfn> arguments the name length and the number of LFN entries required to store the <name> string. It returns in the <sfn> argument a legal SFN name extracted from the <name> string (upper case and 8-3 format). It returns in the <checksum> argument the SFN checksum.

• Short name (less than 13 characters) require 1 LFN entry.
• Medium names (from 14 to 26 characters require 2 LFN entries.
• Large names (up to 31 characters) require 3 LFN entries.

It returns 0 on success. It returns 1 if the name length is larger than 31 characters.

unsigned int _update_dir_entry( fat_inode_t* inode )

For a node identified by the <inode> argument, this function updates the "size" and "cluster" values in the parent directory entry File-Cache. It set the dirty bit in the modified buffer of the parent directory File-Cache.

It returns 0 on success. It returns 1 if error.

unsigned int _add_dir_entry( fat_inode_t* child , fat_inode_t* parent )

This function add a new <child> entry in the Cache-File of the <parent> directory. It accesses the File_Cache associated to the parent directory, and scan the clusters allocated to this directory to find the NO_MORE entry, that will be the first modified entry in the directory. Regarding the name storage, it uses LFN entries for all names, but computes a legal (upper case / 8-3) SFN name that will be stored in the NORMAL entry. It writes 1, 2, or 3 LFN entries (depending on the child name actual length), writes one NORMAL entry, and writes the new NO_MORE entry. It updates the dentry field in the child inode. It set the dirty bit for all modified File-Cache buffers. The block device is not modified by this function.

It returns 0 on success. It returns 1 in case of error.

unsigned int _remove_dir_entry( fat_inode_t* inode )

This function invalidates all dir_entries associated to the <inode> argument from its parent directory. It set the dirty bit for all modified buffers in parent directory Cache-File. The inode itself is not modified by this function. The block device is not modified by this function.

It returns 0 on success. It returns 1 in case of error.

void _add_special_directories( fat_inode_t* child , fat_inode_t* parent )

This function adds the special entries "." and ".." in the File-Cache of the directory identified by the <child> argument. The parent directory is defined by the <parent> argument. The child directory File-Cache is supposed to be empty. We use two NORMAL entries for these "." and ".." entries. The block device is not modified by this function.

unsigned int _clusters_release( fat_node_t* inode )

This function releases all clusters allocated to a file or directory identified by the <inode> argument, until the end of the FAT linked list. It calls _get_fat_entry() and _set_fat_entry() functions to scan the FAT, and to update the clusters chaining. The FAT region and the FS-INFO sector on block device are updated.

It returns 0 on success. It returns 1 on error.

unsigned int _cluster_allocate( fat_inode_t* inode , unsigned int* cluster )

This function allocates one cluster in FAT to a file (or directory) identified by the <inode> pointer. The allocated cluster index is returned in the <cluster> argument. It allocates also the associated buffers and buffer descriptors in Cache-File. It calls _get_fat_entry() and _set_fat_entry() functions to update the clusters chaining in the Cache-Fat. The FAT region and the FS-INFO sector on block device are updated.

It returns 0 on success. It returns 1 on error.

void _release_cache_memory( fat_cache_node_t* root , unsigned int levels )

This recursive function scans one File-Cache (or Fat-Cache) from root to leaves. All memory allocated for 4KB buffers, and buffer descriptors (in leaves) is released, along with the 64-Tree structure (root node is kept). The released cache is identified by the <root> and <levels> arguments. It should not contain any dirty clusters.

fat_cache_node_t* _allocate_one_cache_node( fat_cache_node_t* first_child )

This function allocates and initializes a new cache node. Its first child can be specified (used when adding a cache level). The 63 other children are set to NULL.

It returns a pointer to the new Fat-Cache node.

fat_inode_t* _allocate_one_inode( char* name , unsigned int is_dir , unsigned int cluster , unsigned int size , unsigned int count , unsigned int dentry , unsigned int cache_allocate )

This function allocates and initializes a new inode, using the values defined by the <name>, <is_dir>, <cluster>, <size>, <count>, and <dentry> arguments. If the <cache_allocate> argument is true, an empty cache is allocated.

It returns a pointer on the new inode.

void _allocate_one_buffer( fat_inode_t* inode , unsigned int cluster_id , unsigned int cluster )

This function allocates a 4 Kbytes buffer and the associated cluster descriptor from the heap[x,y] defined by the calling thread, for the file (or directory) identified by the <inode> argument. It updates the Cache_File slot identified by the <cluster_id> argument. The File-Cache slot must be empty. It updates the buffer descriptor, using the <cluster> argument, that is the cluster index in FAT. The buffer descriptor dirty bit is set. It traverses the 64-tree Cache-file from top to bottom to find the last level.

unsigned int _allocate_one_cluster( unsigned int* cluster ) ==

This function allocates one free cluster from the FAT and returns the cluster index in the <cluster> argument. It updates the FAT slot, and the two FAT descriptor variables "first_free_cluster" and "free_clusters_number".

It returns 0 on success. It returns 1 on error.

unsigned int _remove_node_from_fs( fat_inode_t* inode )

This function remove from the file system a file or a directory identified by the <inode> argument. The remove conditions must be checked by the caller. The relevant lock(s) must have been taken by te caller.

It returns 0 on success. It returns 1 on error.

unsigned int _file_info_no_cache( char* pathname , unsigned int* file_cluster , unsigned int* file_size )

This function returns in the <file_cluster> and <file_size> arguments the cluster index and the size for a file identified by the <pathname> argument, scanning directly the block device DATA region. It is intended to be called only by the _fat_load_no_cache() function, as it does not use the dynamically allocated File-Caches, but uses only the 4 Kbytes _fat_buffer_data.

It returns 0 on success. It returns 1 on error.

unsigned int _next_cluster_no_cache( unsigned int cluster , unsigned int* next )

This function scan directly the FAT region on the block device, and returns in the <next> argument the value stored in the fat slot identified by the <cluster> argument. It is intended to be called only by the _fat_load_no_cache() function, as it does not use the dynamically allocated Fat-Cache, but uses only the 4 Kbytes _fat_buffer_fat.

It returns 0 on success. It returns 1 on error.

int get_length( int offset , int length )

This function returns the the size (bytes) of a FAT field, identified by an <offset,length> mnemonic defined in the fat32.h file.

int get_offset( int offset , int length )

This function returns the the offset (bytes) of a FAT field, identified by an <offset,length> mnemonic defined in the fat32.h file.