Next Previous Contents

9.2 FAT filesystem internals

FAT filesystem implementation supports (12/16/32 bit) FAT types. It can access booth msdos 8+3 directory slots and VFAT long filename slots. Additional inode attributes (mode, owner, acces flags,...) can also be stored in special file for every directory.

The FAT support is written almost from scratch. None library is used, but some code is taken from GNU parted and Linux Kernel 2.2.X.

All the internal functions returning numbers use negative number to signalize error has occured, functions returning pointers use the NULL value. An ERR_OCCURED() macro is used if situations not covered by these rules.

FAT headers

The simplest and most basic header file is types.h. It just defines fat_debug macro, cluster_t and dirent_t types (aliases for int) and includes general system headers. Every source file imports this header at first.

The next 3 simple headers params.h and error.h/error_chket.h are generated by scripts called in Makefile. They contain declaration of filesystem parameters and error messages.

The very important header file is fat.h. It contains declaration of internal filesystem data fat_fs_data, representation of FAT superblock fat_sb_info and fat_save_fsdata. All the FAT code uses these typedefs to access internal filesystem data.

struct fat_sb_info {
        int length;                                 /* in blocks */

        int cluster_blocks;                         /* sectors/cluster */
        int cluster_bytes;                          /* length of cluster */
        int fats,fat_bits;                          /* number of FATs, FAT bits (12 or 16) */
        block_t fat_start;
        block_t fat_length;                         /* FAT start & length (sec.) */
        block_t dir_start;
        block_t dir_length;
        dirent_t dir_entries;                       /* root dir start & length & entries */
        block_t data_start;                         /* first data sector */
        cluster_t clusters;                         /* number of clusters */
        cluster_t root_cluster;                     /* first cluster of the root directory */
        long fsinfo_offset;                         /* FAT32 fsinfo offset from start of disk */
        cluster_t free_clusters;                    /* -1 if undefined */

        cluster_t prev_free;                        /* previously returned free cluster number */
        long backup_offset;                         /* backup of BOOT sector */

        unsigned short heads,sectors;               /* FAT needs this in boot sector.  */

struct fat_fsdata {
#ifndef NDEBUG
        int magic;
        struct block_access acc;                    /* Bread/Bwrite data */
        struct fat_parameters par;                  /* FAT fs parameters.  */
        struct fat_sb_info sb;                      /* Parsed superblock.  */
        struct fat_cache *cache;                    /* FAT cache.  */
        iconv_t conv_short,conv_long;               /* Conversion tables to UCS4 (using gconv).  */
        iconv_t conv_utf8;                          /* Conversion to UTF8 (for vfat+rights).  */

        cluster_t free_cluster_counter;             /* for fat_freeblocks */

        struct fat_save_fsdata *save_fs;            /* Hard copy, because imported fs will deallocate it.  */

Another important header file is inits.h. It declares raw FAT superblock (BOOT sector and INFO sector) taken from GNU parted. All code that accesses disk in raw mode imports this header.

All other header files are just headers of corresponding FAT modules. There's nothing interesting to say about them.

FAT layers

Miscelaneous modules


Is an implementation of hash-table: a structure containing general pointers (or long integers) indexed by strings. It is a very simple array of link-lists.


Generated by Makefile scripts, contains error table initialisation.


Generated by gener_params.m4, contains FAT fs parameters definition, conversion functions etc...


This source contains only the definition of fs_calls type (function callbacks).

1st layer: partition access abstraction

Filesystem needs to be able to access partition in 2 modes:

  1. RAW mode: Part module calls imported filesystem callbacks giving a file descriptor and unsigned int offset (given in blocks). Filesystem accesses partition by reading from/writing to this opened file, but it has to add the offset at first.
  2. GCONV mode: when the conversion is performed, GConv may use any free blocks to store filesystem data and the filesystem must NOT care about it. Accessing partition is done by calling bread/bwrite functions, thay operate on blocks of size BASIC_BLOCKS (= 512b).

FAT implementation doesn't care about the mode, so a layer with the only standardized interface is used (stored in block.[ch] source files).

block_access type contains all information needed for proper access (int fh; unsigned int start; and struct partition *part;). It is initialised by calling one of init_raw_access, init_gconv_access functions and it is used as first parameter of Bread, Bwrite functions. These functions call either read or bread depending on the initialized mode.

2nd layer: cache for accessing sectors

To prevent reading/writing the whole sector every time Surprise needs to access a record from FAT-table and to support fast write-back cache, cache.[ch] store up to 256 pages (sector) in memory. The pages are indexed by sector number in hash-table, a link-list is used for solving collisions.

The page type fat_cache_record contains number of sector block_t sector, int dirty:1 flag (set if the page was modified and must be written before closed), int last time of last access (to delete Least Recently Used pages), and page data unsigned char a[PAGE_SIZE]. It contains a pointer struct fat_cache_record *next to next page with the same hash in link-list too.

The FAT cache type fat_cache contains an array of pages struct fat_cache_record pages[MAX_CACHE_SIZE (=256) ] and an array of pointers to hash table chains struct fat_cache_record *hash[]. A pointer struct block_access *acc, last access time last and cache size size is also stored.

Cache is initialized by calling fat_cache_init, deallocated by calling fat_cache_done and flushed by fat_cache_write.

Every time the filesystem needs to access (read/write) a page through cache, it calls struct fat_cache_record *fat_cache_get_page(...,block_t sector,...) function. If the page is not already loaded in the cache, this function looks for the oldest page in cache, possibly flushes it and deletes it. A new page is loaded then. A calling code is responsible of setting dirty flag every time the page is modified. FAT cache will automatically update the disc sector when the page is deleted.

The fat_cache_get_page function increments the cache counter last, looks for the page and stores the counter into accessed page. It a page has not been found, fat_cache_find_oldest finds the oldest page, it is flushed and deleted than, and new page is loaded.

3rd layer: code for accessing FAT-table records

access.[ch] defines the most important function cluster_t fat_access(struct fat_fsdata *fs,cluster_t nr,cluster_t new_value,int debug_msg,...). This function gets a pointer to internal filesystem data (pointer to cache is used) and cluster number nr. A current value is read and standardized (12/16/32-bit cariants use another reserved values to signalize EOF, BAD block and USED block -- -1, -2, -3 is used instead). If new_value!=FAT_ACCESS_DONT_WRITE, a new value is stored in FAT. The debug_msg parameter is not important, it just enables printing debug messages. The previous value of the FAT record is always returned.

The 2nd important function fat_find_free finds a free cluster. It is a bit complicated, because a given cluster is tested at first (to prevent file fragmentation) and the block_list of preferred clusters is used after (if set). If none free cluster is found, all the filesystem is searched. Attention! Some clusters are already used, but they haven't been written to FAT yet to enable optimalizations. These clusters are always ordered in one extent struct fat_file_extent *except and they are never used.

Few another functions are defined: block_cluster converts a cluster number to its offset on the partition, block_root does the same for the root directory in non-FAT32 variants, fat_clusters_flush saves the filled INFO sector containing free cluster count, extent_contains_cluster tests whether the whole cluster fits into given extent, date_dos2unix, date_unix2dos convert booth date/time representations.

4th layer: FAT files abstraction

All the FAT files and directories are accessed using file.[ch] module. It can read from/write to all files and directories in all FAT variants (even to ROOT directory in FAT12/16). The files can be read (in blocks of the cluster_size), written and appended. Byte access is not supported and the file size is rounded up to multiple of cluster_size.

An extent type struct fat_file_extent is used (instead struct extent) because we use signed cluster_t type.

The files are identified by their starting cluster (counting from 2). Root directory in non-FAT32 variants starts in virtual cluster 1 and all empty files start in virtual cluster 0.

A struct fat_file is declared as:

struct fat_file {
        struct fat_fsdata *fs;
        int cluster_size,appending:1,dirty:1;
        unsigned char *a;                           /* Data of current cluster.  */

        cluster_t starting;                         /* Starting cluster.  */
        int count,alloc;                            /* Count of extents.  */
        struct fat_file_extent *clust;              /* Address of file clusters.  */

        block_t index;                              /* Index of current cluster.  */
        block_t len;                                /* Total length.  */
        cluster_t cluster;                          /* Storage address of current cluster.  */

        dirent_t dir_entries;                       /* For use in dir.c  */
        dirent_t dir_entry;

The most basic pointers and parameters are stored in attributes fs, cluster_size, appending, dirty, a. When the file is opened, Surprise searches all the file and gathers cluster extents to optimalize memory usage -- even a big file will not use much of memory is it isn't too fragmented. This is stored in attributes starting, count, alloc, clust. The real file length (in clusters), current linear and the corresponding cluster number are stored in attributes index, len, cluster. Two additional attributes dir_entries, dir_entry are left free for next layer.

The file is allocated by calling fat_file_init. If the read_data parameter is set a space for cluster data is allocated and the file could be read/written than. It it is not set, the caller is not allowed to touch file data, but it is able to access file extents. Another flag appending enables code appending given clusters and preallocates an amount of space in clust array. One allocated file can be opened for many concrete files. File is deallocated by calling fat_file_done.

The file is opened by fat_file_open. It gets a starting cluster (real or virtual 0/1) and gathers all file extents. It checks the cluster count by comparing with the real file size length. It uses two static functions: browse_extents (gathers file extents into preallocated bounded buffer and returns the total extent count; it also checks the cluster chain length) and alloc_extents (calls browse_extents for 128-extent buffer, if they don't fit, larger buffer is used and browse_extents is called again). The file is closed by fat_file_close. The allocated file can be opened again...

Two static functions file_read, file_write read the given cluster into file cluster data area (if it was allocated). The caller is responsible to set dirty flag every time the data are changed. These functions take care about the non-FAT32 Root Directory exception: it isn't aligned to clusters and the last cluster must be cutted (else the first cluster will become damaged).

A fat_file_seek functions optionally writes dirty cluster and looks for given cluster in extent array. A new cluster is read. fat_file_next is an abbreviation for seeking to next cluster.

Appending to file is performed by calling fat_file_append_extents. It appends concrete clusters from given extent array. It takes care about allocating all the data if the file was empty before. FAT table is updated. No cluster data is changed, the file position is leaved unchanged. Any free cluster can be appended by calling fat_file_append_free_cluster. It finds a free cluster by calling fat_find_free, appends it, seeks the file to this new last cluster, fills the data by zeros and sets the dirty flag.

5th layer: FAT directory abstraction

The code in dir.[ch] uses the files to implement parsing of MSDOS/VFAT directories. It also contains functions to prepare filenames for directory slots.

A struct fat_dir_entry contains the raw MSDOS directory entry (declared in system headers) and booth short and long filename (if filled). The shortname is stored in ASCII codepage, the longname in Unicode UCS2. The directory code used the last 2 file attributes: dir_entries, dir_entry to store the total count of available directory entries (it is not rounded in non-FAT32 root directory) and number of current 32b long directory entry.

fat_directory_open calls fat_file_open and computes the dir_entries. fat_get_entry seeks file to cluster containing given directory entry and returns a pointer to data of this entry. fat_put_entry does the same with one additional feature: it file would become too long, a new free cluster is appended. get_first_cluster, set_first_cluster access the first cluster attribute of struct fat_dir_entry, because it is represented in 2 different ways (for non-FAT32 and FAT32 variants).

fat_read_next_entry taken from Linux Kernel does the dirty job. It calls fat_get_entry and parses the entries. It skips all empty directory entries, invalid entries and recognizes the long filenames. After a valid entry is found, struct fat_dir_entry is filled. It also takes care abound endianity conversion of UCS2 charset.

The vfat_repair_longname, vfat_valid_shortname, vfat_format_name, vfat_create_shortname functions taken from Linux Kernel do another dirty job: they prepare real filenames to fit the MSDOS 8+3 directory slots:


Repairs longname stored in Unicode16 strings (for invalid characters) and alignes its length to multiple of 13.


Checks whether the 8bit name could be used as shortname (must contain only small letters, no special symbols, name must be up to 8 letters long, extension up to 3). It must NOT containt national characters (>=0x80) to ensure the UCS2 encoding will be used instead.

Now it is hacked to disallow spaces in shortnames, because fsck.msdos doesn't like that.


Fills the 8+3 slot from valid shortname. It allows spaces in shortnames -- they are left.


Given a valid longname, it creates a unique shortname. Makes sure the shortname does not exist.

Every exported directory contains a hash-table of already created shortnames. vfat_find_form function checks a filename for presence. vfat_create_shortname appends random prefixes to shortname if the original one is already present.

Initialization routines

inits.[ch] contains general initialization function and imported filesystem initialization.


It asserts size of BOOT sector and INFO sector equals 512b. An error table is initialized.


Reads a superblock of given filesystem and tests, whether the filesystem could be a valid FAT filesystem (Surprise doesn't trust the Partition Table and checks everythink by itself). It checks the sign in BOOT sector and non-zero values of some important attributes.


is the most important initializator for imported filesystems. It reads the superblock, parses it and fills the internal data structures. The initial value of imported filesystem parameters are also read or guessed (fat_bits cound not be properly detected in all cases).

conversion_init, conversion_done

Opens handles for all charset conversions needed during conversion process: shortname (8-bit codepage) conversion from/to UCS4, longname (UCS2) conversion from/to UCS4 and UCS4 conversion to UTF8 (for vfat+rights).


It clears the internal data structures and reads forced values of imported filesystem parameters (fat_read_super will look at them).


is used for saving BOOT loader code during conversion: the original one is read and stored in memory by imported filesystem. The exported filesystem gets the pointer and stores it in created BOOT sector.

fat_imp_init, fat_imp_done

All the partial functions are called in the right order to prepare the imported filesystem for conversion: structures are allocated, fat_fsdata_init is called, the block layer is initialized, superblock is read, cache layer is initialized, conversion tables are allocated and the original BOOT sector is stored.

The destructor deletes the original BOOT sector, conversion handles and cache. Then it deallocated the internal data structures.


It reads the superblock and returns the imported filesystem parameters.

FAT32 root directory length is set to zero in superblock (because it is an ordinary file), but the user is interested in its real length. The root directory file is opened and its length is stored.

The filesystem containing additional inode attributes (mode, owner, rights,...) is identified by a small hack: character `$' is appended to fat_name attribute (which is really not important).

Hack for storing additional inode attributes

Every ext2 filesystem converted to FAT would lose many datas about files (mode, owner, rights,...). Surprise prevents the user to make a mistake by using the default choice long_name_type==vfat+rights. Ordinary VFAT filesystem is used and the missing information is stored in special text files $#%right.$#@ in every directory.

The functions for opening/closing directories and fat_nextentry, fat_createentry are hacked to call rights.[ch] functions.

struct fat_rights contains a pointer file to opened file containing the directory metadata. It must save the rights_size because the file layer doesn't care about exact file length. It saves the struct fat_entry_info *ei pointer to processed directory too to allow accessing some important attributes. The imported filesystem must save the rights_offset to save the current position (the exported filesystem doesn't need to, the file is appended only and the rights_size attribute is used), the exported filesystem saves the number rights_direntry of directory entry containing the link to special rights file (because the length of this file will be known at the end).

A new layer for implementing byte acces to files is introduced at first: append_text copies the bytes into file body and takes care about swapping clusters, read_text does the same for reading.

fat_rights_init converts the filename $#%right.$#@ to UCS4 to let the comparison and initializes the file. It scans all the directory for imported filesystem and checks the signature. It any error is found, the rights won't be read. A new file is created for exported filesystems (it will be always the first directory entry after . and ..). fat_rights_done seeks to first directory entry for exported filesystems and stores the final file length and starting cluster.

fat_is_rights_file tests whether the given filename is a special reserved filename -- to let Surprise ignore these files for imported filesystems.

fat_rights_write_inode gets the struct entry_info and writes a line to the rights file. Every record is a text line containing the lengths of attributes and filename at first, the attributes will follow and the filename in UTF8 is written last. append_text is called for that.

read_rights_record read the line (reading its length at first, then the attributes and filename). look_for_rights_until scans the directory for given filename until given position (to enable optimalization: look to the next record at first, than to all following records and to the preceding records at last), look_for_rights does the optimalization. fat_rights_read_inode scans for the file and parses the inode attributes.

6th layer: the import and export functions

These functions are divided into 4 groups:

Getting info about imported filesystem

info.[ch] contains one function of general use: converted_name takes struct fat_dir_entry (containing msdos_dir_entry, shortname and longname) and returns the nicest filename in UCS4 (converted from longname if present and from shortname otherwise). The filename is at most 260 character long and the function returns a pointer to static data (to prevent (de)allocating memory for every file).

fat_get_rootdirs does almost the same initialization as fat_imp_init does and scans the root directory for subdirectories. Their names are exported to the caller. append_directory, fat_get_subdirs functions are used to do that. Everyhing is deallocated (like fat_imp_done) than.

fat_get_info browses the directory tree and sums the file lengths rounded to miscelaneous cluster sizes. The temporary functions add_rounded_size, add_file_size, sum_sizes work on the struct fs_info. store_directory_info looks to the list of user specified directories, where to store the information about given directory. browse_subtree is a recursive function counting the sizes. It is called for all levels of nested subdirectories. It calles store_directory_info in 0th level (root directory). fill_root_fsinfo fills other filesystem attributes (number of free blocks, block size, etc...). It checks for a filesystem integrity too. The main function fat_get_info prepares everything, calles store_directory_info and cleanes everything.

Importing a filesystem

import.[ch] introduces a new data type struct fat_entry_info containing internal filesystem information about every opened directory (used booth for imported and exported filesystem).

struct fat_entry_info {
        /* For import and export:  */
        struct fat_file *dir;   /* opened file with the directory */
        struct fat_file *file;  /* opened file with current entry */

        struct fat_rights *rights;      /* vfat+rights attributes */

        /* For import:  */
        cluster_t cluster;      /* first cluster of current entry */
        int extent_index;       /* index of last written extent */

        /* For export:  */
        struct block_list free_clusters;        /* from last fc_createentry */
        struct block_list *free_blocks; 
        struct msdos_dir_entry *Cluster;        /* where to store cluster number of created file/directory */
        TStrHashTable *files_in_dir;            /* already created files */
        struct extent to_fill;                  /* unfilled cluster after fat_putdata */
        int is_duplicated_hardlink:1;           /* special case: fat_put_done must close the directory */

The file dir contains an opened directory, the file file contains opened current file (for reading extents of imported files). It the vfat+rights mode is enabled, the file rights contains an opened file with rights for all files in this directory.

Imported filesystems store an abbreviation for first cluster of current file and index extent_index containing the count of extents already sent to GConv.

Exported filesystems save the pointer to list of free_blocks here. If a free block is needed, the list is converted to free_clusters list needed by other layer functions. An abbreviation to struct msdos_dir_entry *Cluster is stored here too. To prevent creating duplicate shortnames, TStrHashTable *files_in_dir is allocated. GConv cannot know what cluster_size does the filesystem use and it puts unrounded count of blocks in fc_putdata, so the filesystem stores last unfilled cluster position in struct extent to_fill. The next file data will be put here at first, a new cluster is allocated after to_fill is filled. A flag is_duplicated_hardlink is stored to handle correct closing directory.

Directory functions

Directory callback functions booth for imported and exported filesystems are implemented here. Static function close_directory closes all related files, deallocates hash table of created short filenames and the directory data structure; open_directory allocates the memory and opens all related files. It creates a nonempty directory-file for exported filesystems to allow caller read the first cluster. fat_open_rootdir calls open_directory, stores the 1st cluster of FAT32 root directory to the superblock and initializes the rights. fat_open_subdir calls open_directory, stores the 1st cluster to the directory entry in parent directory, puts two dummy directory entries . and .. (by calling static fill_dir_entry) and initializes the rights. fat_close_dir just calls the close_directory.

Reading imported directory entries

fat_nextentry reads directory entries by calling fat_read_next_entry until nonspecial (. and .. and rights file) entry is found. It gets an UCS4 filename by calling converted_name and stores all the attributes into struct fat_entry_info, struct entry_info. The additional inode attributes are read by calling fat_rights_read_inode for vfat+rights filesystem. If the inode is a softlink, the contents are read by calling fat_read_softlink. This static function reopens the file (with data buffer), reads the contents of the file, converts it to UCS4 too and reopens the file again without the data buffer.

Reading extents of imported files

fat_getdata checks EOF by comparing internal extent_index with count of extents of imported file. All the destination struct block_list *list is filled by extents of imported file. The cluster numbers are converted to blocks by block_cluster function. The last cluster is cutted to round the file size to multiple of BASIC_BLOCK (not cluster_bytes).

fat_getdone deallocates the file name and closes the imported file (if the directory entry was not a subdirectory).

Reading free clusters

GConv needs to know the list of free clusters of imported filesystem to save its internal data. All data stored in these clusters will be damaged, but there should be no data (it the imported filesystem is in correct state).

export_signed_blocks browses the FAT (by calling fat_access function) and searches for given value. It collects them into extents stored in struct block_list *list. The blocks between end of filesystem and end of partition are stored at first.

fat_freeblocks just calls export_signed_blocks for value FAT_ACCESS_EMPTY==0.

Checking the possibility of creating exported filesystem

The functions in module check.[ch] get the exported filesystem size, struct fs_info containing miscelaneous sums of sizes of imported filesystem files and checks whether the exported filesystem could be created. It takes care about fat_bits (maximal count of files), cluster_size (rounding imported file sizes up to multiple of cluster_size), etc...

Static functions max_count_bits, min_count_bits return upper and lower bound of total count of clusters for given fat_bits. min_reserved_count returns the minimal count of reserved sectors before 1st copy of FAT table. fat_size gets a partition size, cluster_size, fat_bits and computes the size of 1 copy of FAT table. fatfs_size sums the count of reserved sectors, root directory size for non-FAT32 variants and all copies of FAT table and returns the FAT internal data structures size. All other space is free for exported files. fat_available_clusters calls fatfs_size and returns a total count of clusters for given partition.

approximate_fatdir_size is a heuristic function that computes the amount of space wasted in directories. It gets a count of files and directories and the total length of all filenames and computes the CERTAIN upper bound of wasted clusters. This bound is somewhat big and could be modified later.

static int check_fat_parameters(struct fat_parameters *pars,struct user_partition *part,struct fs_info *info,...) does all the tests. At first it checks whether there would be and available_cluster by calling fat_available_clusters. Than it compares this count with count of exported files and directories. Than it checks whether the file count would not be larged than fat_bits limit. It computes the total exported file size for given cluster_size and compares this value with available clusters count. It denies to create 12/16 FAT filesystem with wrong size (Linux detects the 12/16 fat_bits via filesystem size, so we force this parameter to be correct). If everything is correct, we check 2 additional warnings: it there would be left an unused space after the filesystem (because the fat_bits limit), we return a warning of level 2; if there would be fewer clusters than lower bound, we return warning of level 1 (less important).

modify_fat_parameters is an intelligent function that computes optimal fat_bits, cluster_size values for given filesystem (if they weren't forced by setting force_... flags). It is a recursive function that browses the cluster_sizes in 1st level, the fat_bits in 2nd level and calls check_fat_parameters in 3rd level. Browsing in every level operates in this way: it the parameter is forced, it's value is not changed. If it isn't, we try all the possible values from the smallest (12/16/32 and 512/1024/.../65536). We never accept values returning error. If we find a value without a warning or with warning of level 1, we choose it and stop the job. In another cases we try to minimize the warning level (2). fat_check just checks the current parameter set by calling check_fat_parameters. If any warning/error is found, modify_fat_parameters is called. It stores a correct MBR partition type too by calling mbr_type.

fat_getsize, fat_getsize_struct just call fatfs_size, approximate_fatdir_size and compute the total exported file size for given cluster_size and return the count of blocks.

Exporting a filesystem

Functions in gener.[ch] module create the superblock, reserve the bad blocks, create directory entries, manage appending clusters to exported files, etc...

The filesystem is generated in 5 phases:

  1. The internal data structures struct fat_fsdata, struct fat_sb_info are filled depending on exported filesystem parameters and partition size. The internal filesystem blocks are allocated.
  2. The bad blocks are signed in FAT.
  3. All the directories with directory entries are created, files are filled by exported clusters.
  4. Hardlinks are duplicated (the directory entries have already been created, now we just fill the clusters).
  5. The superblock is stored on the disk and the FAT table is duplicated.

Miscelaneous functions

clusters_extent converts a GConv extent (interval of BASIC_BLOCKs) to FAT extent (interval of clusters). It can round the interval in booth inner/outer way. clusters_extent_list does the same for the struct block_list.

fat_align is a callback aligning GConv extent into maximal subextent aligned to clusters. It just calls clusters_extent and converts the cluster numbers back to blocks.

fill_geometry reads the partition geometry by calling ioctl(HDIO_GETGEO). If the geometry cannot be read, the count of heads and sectors are set to 1.

Managing superblock

fat_boot_sector_generate does the opposite to fat_read_super. It gets a struct fat_fsdata *fs and fills the 1st part of superblock (BOOT sector). If an original superblock is saved, the BOOT loader is copied to the output, else the Surprise BOOT loader is used (it is taken from GNU parted and does nothing except writing a message). fat_info_sector_generate generates the 2nd part of superblock (INFO sector) containing the count of free_clusters.

fat_set_superblocks fills the internal data structures: it copies the fat_bits, cluster_size exported parameters (checked/filles by fat_check) and computes all the sizes, offsets,... It stores the BOOT sector on block 0, its copy on block 6 and the INFO sector on block 1 (for FAT32 variant). It inserts a dummy blocks before the 1st copy of FAT to make the correct alignment (ext2 and other filesystems always use alignemnt to 0, only the silly FAT aligns into `random' sector).

fat_dummy_write writes the zeros into place of superblock, FAT copies and root directory to let GConv know that these blocks are allocated. It writes an identification of FAT too.

fat_duplicate reads the 1st copy of FAT and duplicates it into all other copies. It is done in the end to optimalize the speed of conversion.

fat_write_superblock calls fat_(boot|info)_sector_generate and stores the filled sector in the right place.

Low level generating directory entries

vfat_fill_long_slots taken from Linux Kernel gets UCS2 string rounded to multiple of 13 (finished by 0x000 and filled by 0xffff) and format the VFAT directory slots. It uses the fat_put_entry functions to store them. It converts the endianity of UCS2 too. In the end it creates a final directory entry containing the short filename and inode attributes.

vfat_build_slots builds all needed directory slots. It handles special directory entries . and .. Than it calls vfat_repair_longname to format the UCS2 string and checks the validity of shortname. If it is valid filename, it is formatted to MSDOS 8+3 directory slot by calling vfat_format_name and a lookup to directory hash table is performed. If no error/duplicate has occured, a directory entry is created and the pointer to it is returned. In all other cases a unique shortname is created by calling vfat_create_shortname. If the VFAT mode is enabled, vfat_fill_long_slots is called and the directory entry is returned. If the VFAT is disabled, we just create a directory entry containing to short filename and lose the long filename.

vfat_build_slots_from_UCS4 gets a standard internal UCS4 string and converts it to UCS2 and given 8bit codepage by calling safe_iconv, which replaces all unknown characters by `_'. vfat_build_slots is called than.

The top level callbacks

fat_superblock is an accelerator. It is called if some filesystem parameters are changed, but the partition type, size and offset is not changed. It checks whether the fast conversion (just replacing the superblock) could be performed. FAT filesystem supports replacing these superblock parameters: system_id, volume_name, fat_name. The function read imported and exported parameters and checks whether all important parameters are equal. If they are not, nonzero is returned. In positive case we read the superblock from imported filesystem, modify the parameters and write it to exported filesystem.

fat_mkfs allocates the internal data structures, fills the geometry, makes a hard copy of optionally saved original BOOT loader (because it will be deallocated before we would need to use it), initializes the block layer and cache and conversion tables, calls fat_set_superblock and fat_dummy_write.

fat_fsdone deletes the conversion tables and cache, calls fat_duplicate and fat_write_superblock, deletes the optionally saved BOOT loader and deallocates the internal data structures.

fat_putbadblocks checks all given extents whether they don't touch the filesystem internal structures. It they do, an error is returned, because the filesystem won't be fully functional. All extents are converted to cluster numbers by calling clusters_extent_list(ROUND_OUTER) and the clusters are signed as bad in FAT table.

Managing directory entries

Static function set_inode_attributes formats less important common attributes (date/time) to directory entry, set_inode_mode sets the correct file size and attribute and resets starting cluster, reset_exported_dirdata copies all important parameters from imported struct entry_info *file to exported one (to allow opening directory) and resets to_fill extent (none to fulfill yet).

fat_write_softlink is the opposite of fat_read_softlink. It reopens file using data buffer, computes free_clusters from free_extents, converts softlink from UCS4 to 8bit charset, stores the data and cleans everything.

create_unique_linked_inode takes care about creating correct directory entry and fills all data structures. At first it builds directory slots and entry by calling vfat_build_slots_from_UCS4, than it calls set_inode_(mode|attributes) and reset_exported_dirdata. It the inode is a regular file, file is opened to allow fat_putdata append new clusters. fat_write_softlink is called for softlinks and the additional inode attributes are stored by calling fat_rights_write_inode for vfat+rights filesystems.

fat_createentry just stores the free_blocks and calls create_unique_linked_inode to do the job.

fat_putdone deallocates free_clusters (if they were converted) and closes the opened file (for regular files) -- the changes to FAT are stored in cache layer and the first cluster has already been stored in directory entry. It checks is_duplicate_hardlink flag and calls fat_close_dir if set (it is a hack to deallocate internal memory after hardlinks are duplicated; we need to make the directory stay opened to save the first cluster number after duplication).

Appending new clusters

To optimalize appending clusters to file we remember the last appended clusters extent last and just increment its length if the file is not fragmented. After next fragment is used the previous will be flushed out. append_1_cluster checks the previous extent and increments its length if the appended clusters fits. If it doesn't, the function flushes the previous extent by calling fat_file_append_extents and stores the extent to struct block_list *target. If the output buffer becomes full, it it signalized to the caller to finish immidiately the job. If the appended cluster is correct, new extent is created (negative values are used for flushing, they don't create a new extent). It must be noted that the allocated clusters have not been stored in FAT yet, so searching free clusters would return them as free. A workaround is enabled: fat_find_free function expects a special reserved cluster extent containing clusters that must not be returned as free.

fat_putdata clears the output cluster buffer last and remembers the free_blocks extent. If a previous unfilled cluster to_fill is set, it is filled at first (because files are stored in discrete complete clusters) and the pointer to exported blocks is shifted.

The main cycle browses through all exported blocks: variable i contains index of exported extent and j contains index of block in extent i. At first it repairs extent overflow (moves to next one if the previous has been already read) and breaks if all exported extents have already been read. Then it gets the block index and checks whether it could be used for file (the best way is NOT moving file blocks to speed up the permutation at the end of conversion, but is not always possible):

  1. It must not be INVALID_BLOCK (GConv signalizes that the block is not available and filesystem must find the best position alone).
  2. It must fit the FAT data area.
  3. It must be aligned to clusters.
  4. The exported extent must contain enough blocks to fill the cluster.
  5. The cluster must be free (checked by calling fat_access).
If any of these conditions is not true, a new free cluster is searched by calling clusters_extent_list and fat_find_free. Filesystem prefers allocation of the next cluster to prevent the fragmentation. The output cluster extent buffer last is stored to prevent fat_find_free allocate them. A found cluster is appended by calling append_1_cluster, which implements the output cache. The exported blocks are skipped and the cycle continues.

The output cluster buffer is flushed by calling append_1_cluster(-10) and the exported clusters overflow is checked: it GConv gives the filesystem 5 blocks but the cluster contains 8 blocks, a whole cluster was allocated and 3 more blocks have been skipped in the list. These blocks will be stored into to_fill and will be fulfilled next time or cutted after file will be closed.

Duplicating the hardlinks

FAT doesn't support hardlinks, so all of them must be duplicated. FAT uses struct fat_hardlink_data to store all important data: first cluster of directory containing link to duplicated hardlink, the directory entry of the link (to allow storing file size and first cluster after duplication is perfomed), first cluster starting of original copy (to allow the checks), and original file length.

fat_hardlink_get_exported fills this data structure from given file, fat_hardlink_free_exported deletes it.

fat_hardlink_create does the simillar job as fat_createentry. It stores the free_blocks, duplicates the struct fat_hardlink_data and calls create_unique_linked_inode with file of length 0. Before duplication is perfomed, the file will stay empty.

fat_hardlink_duplicate does another part of the job of fat_createentry. It doesn't create entry, because it has already been created, but prepare the internal data structures to allow the GConv call fat_putdata and fat_putdone. It opens and reads the directory (because all directories have already been closed), seeks to the link directory entry, opens the destination file and sets is_duplicated_hardlink to make fat_putdone deallocate this all.

After the fat_fsdone is called, the filesystem is completely flushed to the disk and the big permutation performed by GConv leaves it in correct state.

Next Previous Contents