File system for nonvolatile memory6606628Abstract A file system for nonvolatile memory media is disclosed, based on the assumptions that the file system structure is flat (i.e., does not contain directories), and that a relatively small amount of memory space is available. The nonvolatile memory medium is divided into logical blocks of predetermined size, depending on the typical file size expected for each particular implementation. Each of these logical blocks includes a header describing the contents of the block. For example, the block header may comprise a magic number indicating whether the block is a valid file system block or a free block, the name of the file to which the current block belongs, a flag indicating whether the current block is the first or last block of the file, the block number of the next block of the current file, if any, and the length of valid data in the present block. Claims What is claimed is: Description BACKGROUND OF THE INVENTION
#define NVRAM_FILE_FIRST_BLOCK 0x01
#define NVRAM_FILE_LAST_BLOCK 0x02
#define NVRAM_FILE_SECURE_BLOCK 0x04
typedef struct nvram_block_hdr_type {
ushort magic_number;
ushort next_block;
ushort flags; /* a bit-wise OR of the flags
defined above */
ushort length;
char file_name[ MAX_NVRAM_FILELEN] ;
ushort checksum;
} nvram_block_hdr;
For each open file, there is an associated file information structure, as defined below. The first member of this structure indicates the first block for the specified file, the second member indicates the current block being accessed, and the third member provides an offset within this current block. In one embodiment, the "flags" structure member is used to keep track of whether the file is a secure file or not, and whether a client is authorized to access this file. If the file is a secure file, the process must be validated before the file can be accessed, and when the process is validated, the flag indicating that the client can access the file is set. Finally, the "delete on close" flag indicates whether to delete the file when it is closed. As is known to those skilled in the art, this feature is useful for secure files.
#define NVRAM_FILE_SECURE 0x01
#define NVRAM_FILE_ACCESS 0x02
#define NVRAM_FILE_DELETE_ON_CLOSE 0x04
typedef struct nvram_file_info_type {
int first_block; /* # of 1st block for this file */
int curr_block; /* # of current block */
int offset_in_curr_block; /* offset relative to curr block */
char flags; /* bitwise OR of flags defined
above */
} nvram_file_info;
The geometry of the current nvram medium is stored in a structure defined below. In one embodiment, the first member of this "geometry" structure is the memory size of the nvram. The second structure member is the offset to the start of "useful" nvram. In some applications, an initial portion of the nvram medium may be allocated to a different file system, and therefore not usable for the purposes of the present invention. In such situations the offset structure member may be used to indicate the size of the nvram medium memory space allocated for other purposes. Next, the third structure member is the block size for each nvram block, while the fourth member is the number of such blocks present in the current nvram medium. The geometry structure is passed on to all format functions (described below) to enable them to handle each high-level nvram file function appropriately. The format of the geometry structure is shown below.
typedef struct nvram_geometry_type {
int nv_size; /* size of the nvram, in Kbytes */
int nv_start; /* the offset for "useful" nvram */
int blocksize; /* size of each block, in bytes */
int no_blocks /* number of blocks */
} nvram_geometry;
NVRAM File System Manager To provide for seamless implementation of nvram file systems according to aspects of the present invention in a variety of hardware platforms, a common set of software functions (known as the "nvram file system manager") may be provided. FIG. 3 is a block diagram illustrating the software structure of an nvram file system manager 300 according to one embodiment of the present invention. As shown in FIG. 3, file system routines 310 are at the highest level of abstraction, and may be implemented as a function library. In one embodiment, file system routines 310 comprise the following functions: io_open( ) (for opening a file), io_read( ) (for reading data from a file), io_write( ) (for writing data to a file), io_close( ) (for closing a file), io_unlink( ) (for removing files), io_lseek( ) (for moving the read/write file pointer), io_stat( ) (for providing information on files), and init( ) (for initializing the file system). As is known to those skilled in the art, file system routines 310 may be grouped into or implemented as an Application Program Interface ("API") , static library, dynamic link library ("DLL") , or any of a number of other devices known in the literature. Still referring to FIG. 3, file system routines 310 call the format routines 320 to implement the sub-tasks necessary to execute each file system routine 310. In one embodiment, format routines 320 comprise the following functions: find_file_by_name( ) (to find a specified file in the nvram medium, if it exists), read_nvram( ) (to read data from the nvram medium), write_nvram( ) (to write data to the nvram medium), set_offset( ) (to set the current block and offset members of the nvram_file_info structure), create_file( ) (to create a new file), geometry_init( ) (to initialize the nvram file system), erase_file( ) (to erase all the blocks comprising a specified file), get_list_of_files( ) (for providing a directory of files in the nvram medium), close_file( ) (for closing a file), and get_filename( ) (for returning the filename to which a specified block belongs. In one embodiment, the format routines 320 are aware of the layout (or "geometry") of the nvram (e.g., the start address of the nvram, the block size, number of blocks, etc.). This information is used to determine the amount of data to transfer, and from which block or blocks. In turn, format routines 320 invoke d river routines 330 to implement the most elemental subtasks necessary to execute the file system routines 310 and to actually interface with the nvram medium. In one embodiment, driver routines 330 are further subdivided into platform independent routines 335 and platform specific routines 338. Platform independent routines 335 are elementary functions that are common to a wide variety of hardware platforms. In one embodiment, these functions comprise read_stuff( ) (for reading data from the nvram medium), write_stuff( ) (for writing data to the nvram medium), and get_nvsize( ) (to determine the memory size of the nvram medium). Platform specific routines 338 are those elementary functions whose details differ depending on the specific hardware characteristics of each implementation. Typically, a new set of platform specific routines 338 must be developed depending on the hardware configuration of each implementation. In one embodiment, the platform specific routines include nv_getptr( ) (for returning a pointer to the base address of nonvolatile memory), nv_done( ) (for handling the writing of data to the nvram medium), nv_writeenable( ) (to enable further writes to the nvram medium), nv_writedisable( ) (to disable further writes to the nvram medium), nv_init( ) (to initialize the nvram medium), and nv_badptr( ) (to handle a bad block pointer). As is known to those skilled in the art, the platform specific routines 338 may be implemented as Dynamic Link Libraries ("DLLs") which are loaded onto a particular system depending on the hardware platform used in each implementation. Using the above or an equivalent set of functions, embodiments of the present invention provide the required functionality to implement a functional nvram file system manager. Each of the functions in the three function groups listed above is described in detail in the sections that follow. Additional implementation details which are well within the routine programming skill of those skilled the art have are not discussed herein, so as not to overcomplicate the present disclosure. File System Functions The file system functions are the high-level functions invoked to perform normal file-oriented tasks such as open, read, write, erase, etc. Each of these file system function is described more fully below. io_open( ) Open on an existing file involves searching for the block defining the first block of the file. Once the first block is known, the entire file can be accessed by following the "next block pointers" stored in the header. Hence, in one embodiment, when an open call is given, the nvram is scanned in sizes of one block. The block header is read in, and the magic number is tested. A valid magic number indicates a valid block, while an invalid magic number indicates a free block. If the block is a valid block, the file name is compared to the file being opened, and if it matches, the flag indicating if the current block is the first file block associated with this file is tested. If it is not the first block, the scan is continued until either the first block of the specified file is encountered or an error condition occurs. Open on a nonexistent file involves finding a free block (which in one embodiment involves finding the first block with an invalid magic number). This free block header is then modified to write the magic number into the magic number field of the block header, the name of the file to be opened, the flags described above, and other relevant information as required by a particular implementation. From a software standpoint, after verifying the file permissions, the high level io_open( ) function calls the find_file_by_name( ) function with the file name to be opened. If the specified file exists, an nvram_file_info structure is filled in by this function. If the open is for read, and the file does not exist, then the open fails. If the file exists and the open is for write then, the file is truncated to zero length. If the file is opened for write and the file does not exist, a new file is created if at least one free block is available. io_read( ) Read involves reading the data in the blocks associated with the file. When a read command requests an amount of data greater than the data in the present block, the read is continued to the next block associated with this file. The lower-level read_nvram( ) function (described below) is called with a buffer, which fills in the buffer with the required data. io_write( ) The io_write( ) function is substantially similar to io_read( ), with data being written to the current block. If the amount of data to be written is greater than the amount of data that would fit into a block, and if the current block is the last block of the file, a new free block is found and attached to the end of the file, at which point the write operation continues in the newly found block. Similarly to io_read( ) , the write_nvram( ) function is called, except that this time the buffer passed to the function is written into nvram as file data. io_close( ) If the flags associated with the nvram_file_info structure (described earlier) indicate that the "delete on close" flag has been set, then the file is erased by calling the lower level erase_file( ) function. Otherwise, the nvram_file_info structures are freed and the current block is marked as the last block for this file, if this file has been opened for write. io_seek( ) An io_seek( ) function involves traversing the list of blocks until the desired offset is reached. In one embodiment, this function is typically not used, since file operations are performed on a block by block basis. However, the io_seek( ) function may be useful in situations where block synchronization has been lost for some reason. As in previous cases, if the offset is greater than the data in the current block, a jump is made to the next block based on the next pointer stored in the header of the block. The io_seek( ) function calls the lower level set_offset( ) function. init( ) The init( ) function calls the lower level geometry_init( ) function, which is responsible for filling in the geometry information for the current nvram medium. io_unlink( ) The io_unlink( ) function is used to delete files. A delete involves the simple operation of traversing all the blocks comprising the specified file starting from the first block, and overwriting the magic number field in each such block with a value not equal to the magic number. The lower level erase_file( ) function is called. io_stat( ) The io_stat( ) function is normally used to provide information concerning specified files. In one embodiment of the present invention, all the io_stat( ) parameters are set to zero except for the mode and size, which are copied from an attribute structure. In this embodiment, for the directory parameter, the size is set to 1. Nvram Format Functions The nvram format functions are lower-level building blocks called by the high-level file-oriented functions to implement the details of each file-oriented function. These functions are aware of the nvram format from the nvram geometry structure, and are called by the file system functions to manipulate the nvram file system. Each nvram format function according to one embodiment of the present invention is described in more detail in the following sections. int read_nvram (nvram_file_info *file, nvram_geometry *geometry, char *buffer, int buflen) Given the nvram_geometry and nvram_file_info structures, the read_nvram( ) function reads an amount of data equal to buflen from the specified file into a buffer, and returns the amount of data that was read. Since the nvram geometry is known, a read_nvram( ) call is converted into a series of calls for each block comprising the specified file, and the lower level read_stuff( ) function is called (described below), which is a driver function responsible for actual reading of data from the nvram. int write_nvram(nvram_file_info *file, nvram_geometry *geometry, char *buffer, int buflen) The write_nvram( ) function is substantially similar to the read_nvram( ) function, except that the write_stuff( ) driver function is the driver-level function which is called to ultimately write data to the nvram from the buffer. Also, if at end of the specified file, further writes result in a search for a free block which, if available, is added to the list of blocks associated with this file. The nvram_file_info structure is also updated accordingly. int find_file_by_name (char *name, nvram_geometry *geometry, nvram_file_info *file) Given the nvram geometry, this function scans all the blocks in the nvram medium for a specified file having a particular name, and fills in the nvram_file_info structure passed on to it when the specified file is found. It. returns the file size, if the specified file is found. If the file does not exist, the function returns (-1). int set_offset (nvram_file_info file, int offset) The set_offset( ) function, when passed the nvram_file_info structure and an offset into the specified file, sets the current_block and offset_in_curr_block members of the nvram_file_info structure appropriately. int create_file (nvram_geometry *geometry, nvram_file_info *file, char *filename, bool secure) The create_file( ) function is called if a new file with name "filename" needs to be created. The create_file( ) function finds a free block, if any are available, fills in the appropriate header information, and returns. If the secure file parameter is true, then the file block created is set to be a secure block, and if the secure file parameter is not true, the file block created is set to be a non-secure block. int geometry_init (nvram_geometry *geometry) The geometry_init( ) function is called before the nvram driver is started. It is responsible for filling the geometry structure. It calls nv_init( ), and also uses the get_nv_size( ) function to fill in the geometry structure. All of these functions are driver-specific functions. Once the geometry is known, the geometry_init( ) function "sanitizes" the nvram. This step is needed to ensure the consistency and reliability of the nvram file system. For example, if an application accessing the nvram crashes in the middle of writing a file, the geometry_init( ) function is responsible for scanning through the nvram and removing any partial files remaining upon the next system startup. Also, it is possible that some of the file blocks may have been overwritten during a previous bootup. Therefore, once the nvram geometry is known, the geometry_init( ) function scans through all the file blocks in the nvram, deleting any partial files and ensuring that all the blocks of every file are available and that there are no dangling blocks (i.e., blocks not part of any file). int erase_file (nvram_geometry *geometry, nvram_file_info *file) In one embodiment, when the erase_file( ) function is called, all blocks comprising the specified file described by the nvram_file_info parameter are zeroed out. int get_list_of_files(char *buffer nvram_geometry *geometry, int rem_size, int offset, int *size) The get_list of_files( ) function returns a list of all the files present in the nvram. In one embodiment, the entire nvram medium is scanned on a block-by-block basis, and the file name field (encoded in ASCII) from each block header is read in for all valid blocks. In this embodiment, when duplicate file names are read in, they are assumed to be additional blocks of the same file. The complete list of file names (with duplicates deleted) is written into a buffer upon return from the get_list_of_files( ) function. int close_file(nvram file_info *file, nvram_geometry *geometry) The close_file( ) function is called when a file opened for write is called. The last block flag is set, and the header for the last block is written. int get_filename(int block_no, nvram_geometry *geometry, char *filename) Given a specified block number ("block_no") , the get_filename( ) function returns the file name to which the specified block belongs, if any. Driver Functions The file system and nvram format functions discussed above access the nvram medium through the nvram driver interface routines defined below. As discussed in the Interface Design section, below, a platform specific DLL, linked in when an nvram file system manager process starts, is responsible for providing a pointer to the functions below. Each driver function according to one embodiment of the present invention is described in more detail in the following sections. In many cases, implementation details are not provided herein so as not to overcomplicate the present disclosure. Such implementation details are well within the capabilities of those skilled in the art. int read_stuff(int offset, char *buffer, int len) Given a offset and a buffer, the read_stuff( ) function reads "len" data bytes from the nvram medium at "offset" from the beginning of the nvram medium, and writes the results to the specified buffer. The function returns the length of data read. int write_stuff(int offset, char *buffer, int len) The write_stuff( ) function is substantially similar to read_stuff( ), except that "len" data bytes from the specified buffer are written into the nvram medium starting at "offset," and the length of data written is returned. int start_of_usable memory( ) This function returns an offset from the beginning of nvram, indicating the point at which nvram media allocated for other purposes or file systems ends. int get_nv_size( ) The get_nv_size( ) function returns the size of the current nvram medium. int nvram_init( ) In one embodiment, the nvram( ) function simply calls geometry_init( ). bool other_filesystem_exist( ) This function either returns true or false, depending on whether other file systems exist on the current nvram medium. void collect_platform_dependent_values (platform_values *platform_vals, nvram_platform_dll_funcs *nvram_driver_interface_routines) This function collects all the platform dependent routines needed through this call. This is defined by the structure platform_vals. The function also fills in the addresses of platform independent routines in the nvram_driver_interface_routines structure, which is the interface through which nvram driver is accessed to the caller. This is then passed to the nvram file system manager process. This function is described in more detail in the Interface Design section, below. nvtype *nv_getptr(void) This function returns a pointer to the base address of the non-volatile memory. void nv_done(nvtype *ptr) This function handles the writing of data to the nvram memory. void nv_writeenable(nvtype *ptr) This function simply turns the nv_write enable flag on. void nv_writedisable(nvtype *ptr) This function simply turns the nv_write enable flag off. unsigned long nv_init(unsigned long *phy_address) This function discovers the size of the nvram and performs some initialization. The function returns the system address at which the nvram has been mapped. Also, the argument passed is filled in with the actual physical address at which the nvram has been located. This information can be used to convert physical to virtual addresses and vice versa, since in some nvram file system implementations cases the actual physical address may be important. bool nv_badptr(nvtype *ptr) Given a correctly checksummed portion of non-volatile memory, the nv_badptr( ) function examines the data structure components for sanity. If the configuration magic number is set, the function returns zero. Interface Design In one embodiment, the nvram file system provides a posix interface for using the nvram medium. However, the interface for opening and accessing secure files is typically separate, and has been discussed in the API functional description above. FIG. 4 is a block diagram illustrating the interaction of the software components comprising an nvram file system according to one embodiment of the present invention. As shown in FIG. 4, the nvram file system 400 comprises the nvram file system manager process 410, a platform-common DLL 420, and a platform-specific DLL 430. The nvram file system manager process 410 accesses the platform specific functions, through indirect function calls defined in the structure of type nvram_platform_dll_funcs. This structure has a number of function calls, which the process calls through this structure to gain access to the physical nvram medium. The structure with these functions must be provided by the platform-specific DLL 430. When the nvram process 410 starts up, it opens the platform-specific DLL 430 and performs the common dlsym( ) DLL access function known to those skilled in the art on NVRAM_DLL_PLATFORM_INTERFACE_ROUTINES. This should return a pointer to a function which returns a structure of type nvram_platform_dll_funcs with function addresses filled in by the platform specific DLL 430. As long the platform specific DLL provides a way for returning this function, that is all that is needed to provide a fully functional nvram file system. In order to simplify the nvram file system creation process, the platform-common DLL 420 is also provided. In some applications, it is not necessary to use this DLL at all. However, platform-common DLL 420 defines the functions in nvram_platform_dll_funcs that were defined in the previous paragraph. In one embodiment, the platform-common DLL 420 must also deal with platform specific issues. As shown in FIG. 4, it should be noted that the nvram file system manager process 410 accesses the nvram medium through functions defined in nvram_platform_dll_funcs, which are subsequently defined in the platform-common DLL 420. It is however, the duty of the platform-specific DLL 430 to pass the addresses of these routines to the nvram file system manager process 410. In order to accomplish this, the platform-specific DLL 430 must obtain the addresses of these routines from the platform-common DLL 420 and pass them on to the nvram file system manager process 410. Also, the platform-common DLL 420 uses platform specific routines defined in the platform-specific DLL 430. Therefore, the addresses of routines in the platform-specific DLL 430 are also needed. Still referring to FIG. 4, to accomplish the above tasks, as soon as the nvram file system manager process 410 starts, it makes a function call to the function that had been obtained by performing dlsym( ) on NVRAM_DLL_PLATFORM_INTERFACE_ROUTINES. This function call then makes another call to a function called collect_platform_dependent_values( ) in the platform-common DLL 420 with two parameters. The first parameter is a structure of type platform_values, with all the platform-specific function pointers filled in for the receiver's (i.e., the platform-common DLL 420) use. The second parameter is a pointer to a structure of type nvram_platform_dll_funcs. When the platform-common DLL 420 receives the function call, it saves the first parameter and fills in the second parameter with the nvram interface routine function addresses. Upon return, the platform-specific DLL 430 passes the information on to the nvram file system manager process 410. To achieve this, the platform driver must provide such a function. The details of this process are not disclosed herein, so as not to overcomplicate the present disclosure. However, providing such a function should be well within the capabilities of those skilled in the art, and requires only application of routine programming skills. The definition of the nvram_platform_dll_funcs structure and of the platform_values structure are provided below. typedef struct nvram_platform_dll_funcs_{ int (*read_stuff) (int offset, char *buffer, int len); int (*write_stuff) (int offset, char *buffer, int len); int (*get_nv_size)( ); int (*classic_nv_open) (long *size, unsigned char **data); void (*nvram_init) ( ); } nvram_platform_dll_funcs; The above structure contains a pointer to the nvram interface routines discussed in previous sections. typedef struct platform_values { nvtype *(*nv_getptr) ( ); bool (*nv_badptr) (nvtype *ptr); void (*nv_done) (nvtype *ptr); void (*nv_writeenable) (nvtype *ptr); void (*nv_writedisable) (nvtype *ptr); void (*nv_init) (void); int (*getmonvar) (unsigned char **buf); int (*nv_size) ( ); int (*nvwriteflag)( ); } platform_values; The pointer to functions in the above structure are same as pointers to platform specific functions needed by the platform-common DLL 420 to get the work done, along with a few variables shared with it. Crash Recovery If the nvram subsystem crashes, when a system utilizing an embodiment of the nvram file system according to the present invention boots up again, a "sanity check" is made to make sure that the files in the nvram are in a consistent state. The following actions are taken if an inconsistent file is found: If a loose block is found, the block is deleted. If a file is found with any missing blocks, the entire file is deleted (i.e., all the blocks containing the file name in the block header are converted to free blocks by overwriting the magic number field with a value not equal to the magic number). If multiple files exist with the same file name, the first such file is kept and the rest are deleted. If the last block of a file does not have the "last block of file" flag set but has the "next block" set to zero, then the "last block of file" flag is set. Advantages As those skilled in the art will recognize based on the above discussion, file operations according to embodiments of the present invention are simple and provide all the functionality required for typical nvram file system applications. There are several advantages of embodiments of the present invention as compared to traditional file systems. First, unnecessary details associated with disk-based file systems have been eliminated, thus keeping the code simple and easy to maintain. Moreover, at any given time, the file system on the nvram is self-sufficient, such that no vital information is kept in the memory for a long enough time that a system crash would corrupt the file system due to unwritten information. Furthermore, compared to file systems where data is written contiguously, such as flash file systems, the file system design according to aspects of the present invention achieves less fragmentation and allows multiple writes simultaneously. In general, it is difficult to achieve multiple writes on a file system where data is written contiguously, since it is difficult to determine how long the files would be. Also, such a file system storage suffers from more fragmentation. For example, if a contiguous file system had four files stored on it (e.g., files A, B, C, and D, each of size 1 Kbytes), and if files B and D have been deleted, it is not possible to coalesce the remaining free memory together to obtain a contiguous memory area of 2 Kbytes. Therefore, files greater than 1 Kbytes cannot be saved. In contrast, in the file system design proposed according to the present invention, fragmentation is limited at most by the selected block size. For a typical block size of 1 Kbytes with a 32-byte header, the amount of lost space due to the header is less than 4%. Since nvram media are typically used to store small files, this proportion of lost memory space due to headers is generally acceptable. As is known to those skilled in the art, the program code necessary to implement the software components described herein according to aspects of the present invention may all be stored on a computer-readable medium. Depending on each particular application, computer-readable media suitable for this purpose may include, without limitation, floppy diskettes, hard drives, RAM, ROM, EEPROM, nonvolatile RAM, or flash memory. Moreover, the program code necessary to implement the software components described herein according to aspects of the present invention may be executed by any processor or combination of processors known in the art, including, without limitation, microprocessors, microcontrollers, Application Specific Integrated Circuits ("ASICs"), or other types of commercially available hardware or firmware devices suitable for that purpose. While embodiments and applications of this invention have been shown and described, it would be apparent to those skilled in the art having the benefit of the present disclosure that many more modifications than mentioned above are possible without departing from the inventive concepts herein. For example, without limitation, additional data such as a previous block pointer may be included in the header portion of each memory block if so desired. As another example, embodiments of the present invention may be implemented wherein only a portion of an nvram medium uses a file system according to the present invention, and another portions of the nvram medium are organized in some other fashion. The present invention, therefore, is not to be restricted except in the spirit of the appended claims.
|
Same subclass Same class Consider this |
||||||||||