 |
Claims  |
|
|
I claim:
1. In a computer system having a random access memory system, a method of
maintaining computer files in the memory system comprising the steps of:
partitioning the memory system into pages of predetermined size;
partitioning each of the pages into data paragraphs of predetermined size,
each data paragraph comprising at least one byte of memory: and
dynamically formatting the memory system into a series of memory blocks of
variable length, responsive to the size of each file stored in the memory
system, each memory block consisting of at least one of the data
paragraphs, located within one or more of said pages; wherein said
dynamically formatting the memory system includes, for each file to be
stored in the memory system;
creating a single memory block object;
storing an indication of the file starting location in the memory block
object;
storing an indication of the file size in the memory block object; and
storing in the memory block object a first pointer to a next one of a
series of nonadjacent memory block objects, so that the memory block
object defines a corresponding block of memory and the tint pointers in
the series of memory block objects together form a first linked list of
memory blocks;
wherein said indication of the file size includes:
a number of complete pages in the memory block (BlockPages);
a number of paragraphs that the memory block extends into the last page
(LastPageLength); and
a number of bytes used in the last paragraph of the memory block
(BytesLastParagraph).
2. In a computer system having a random access memory system, a method of
maintaining computer files in the memory system comprising the steps of:
partitioning the memory system into pages of predetermined size:
partitioning each of the pages into data paragraphs of predetermined size,
each data paragraph comprising at least one byte of memory;
dynamically formatting the memory system into a series of memory blocks of
variable length, responsive to the size of each file stored in the memory
system, each memory block consisting of at least one of the data
paragraphs located within one or more of said pages; and
initially formatting the memory system by creating an initial memory block
object, the initial memory block object indicating a starting location
corresponding to a first end of the memory system space and a size equal
to the size of the memory system.
3. A machine-readable file system memory block data structure encoding data
about a corresponding block of memory in a physical memory system, said
data structure comprising:
a StartPage integer variable indicating an address of a starting page for
the memory block;
a StartOffset integer variable indicating a data paragraph offset into the
starting page to a beginning of the memory block;
a BlockPages integer variable indicating a number of complete pages in the
memory block, so that the StartPage and Blockpages variables together
define an address of a last page of the memory block;
a LastPageLength integer variable for indicating an offset from the last
page address to the end of the memory block;
a BytesLastParagraph integer variable for indicating a number of bytes of a
last paragraph of the memory block;
a Free boolean variable indicating whether or not the memory block is
available;
a NextMemBlock pointer to a second memory block for forming a forward
linked list of a plurality of such memory blocks; and
a PreviousMemBlock pointer to a third memory block for forming a reverse
linked list of a plurality of such memory blocks.
4. A method of initializing a computer file system having a memory block
data structure according to claim 3, the method comprising forming an
initial memory block data structure, and in the initial memory block data
structure:
setting the BlockPages variable equal to the size of the memory system;
setting the StartPage, StartOffset and LastPageLength variables all equal
to 0;
setting the BytesLastParagraph variable equal to a predetermined paragraph
size in bytes;
setting the Free variable to logical TRUE; and
setting both the NextMeMBlock and PreviousMemBlock pointers equal to NULL
for indicating the ends of the forward and reverse linked lists,
respectively.
5. A method of storing a data file in a computer file system the data file
having a predetermined size smaller than an initial memory block size, the
method comprising:
first forming an initial file system memory block data structure encoding
data about a corresponding block of memory in a physical memory system,
the data structure including:
a StartPage integer variable indicating an address of a starting page for
the memory block;
a StartOffset integer variable indicating an offset into the starting page
to a beginning of the memory block;
a BlockPages integer variable indicating a number of complete pages in the
memory block, so that the StartPage and Blockpages variables together
define an address of a last page of the memory block;
a LastPageLength integer variable for indicating an offset from the last
page address to the end of the memory block;
a BytesLastParagraph integer variable for indicating a number of bytes of a
last paragraph of the memory block;
a Free boolean variable indicating whether or not the memory block is
available:
a NextMemBlock pointer to a second memory, block for forming a forward
linked list of a plurality of such memory, blocks: and
a PreviousMemBlock pointer to a third memory block for forming a reverse
linked list of a plurality of such memory blocks;
second, initializing the computer file system, said initializing step
including in the initial memory block data structure;
setting the BlockPages variable equal to the size of the memory system;
setting the StartPage, StartOffset and LastPageLength variables all equal
to 0;
setting the BytesLastParagraph variable equal to a predetermined paragraph
size in bytes;
setting the Free variable to logical TRUE; and
setting both the NextMeMBlock and PreviousMemBlock pointers equal to NULL
for indicating the ends of the forward and reverse linked lists,
respectively: and then storing the data file, said storing step including;
forming a second memory block data structure; and in the initial memory
block data structure,
setting the BlockPages variable equal to the number of complete pages of
the data file;
setting the LastPageLength variable equal to an offset from the last page
address to the end of the data file;
setting the BytesLastParagraph variable equal to a number of bytes of a
last paragraph of the data file;
setting the Free boolean variable to FALSE to indicate the memory block is
not available; and
setting the NextMemBlock pointer to point to the second memory block data
structure.
6. A method according to claim 5 further comprising:
computing a starting address of the second memory block data structure; and
in the second memory block data structure,
setting the StartPage and the StartOffset variables to reflect the second
memory block starting address;
setting the BlockPages variable equal to a number of complete pages
remaining available in the physical memory system;
setting the PreviousMemBlock pointer to point to the initial memory block
dam structure; and
setting the Free boolean variable to TRUB to indicate that the second
memory block is available, thereby dynamically splitting the memory system
into a first block, described by the initial memory block and containing
the data file, and a second block, remaining available and described by
the second memory block data structure.
7. In a file system having a plurality of memory block objects, a method of
dynamically associating data files and corresponding blocks of memory for
file maintenance the method comprising the steps of:
creating a filename object for each data file to be stored in the file
system:
linking each filename object to a next subsequent filename object so that
the filename objects together form a first linked lift:
creating a fileblock object for each block of memory in the file system;
linking each fileblock object to a corresponding memory block object; and
linking each fileblock object to a next subsequent fileblock object so that
the fileblock objects together form a second linked list,
8. A computer file system comprising:
at least one file name object, each file name object including a file name
field and at least one additional field for indicating an attribute of the
named file, the file name field including a string of data comprising a
human-readable name;
a number of memory block objects at least equal to the number of file name
objects, each memory block object including means defining a file starting
location, means defining a file length and a first pointer to a next
memory block object so that the memory block objects together form a first
linked list of memory blocks in the file system;
each memory block object further including a second pointer to a previous
memory block object so that the memory block objects together also form a
second linked list of memory blocks inversely related to the first linked
list:
the file name object further including a pointer to an initial one of the
memory block objects to link the initial memory block object to the file
named in the file name field:
at least one file block object, each file block object including a first
pointer to a next file block object so that the file block objects
together form a linked list of file blocks for associating fragments of a
file; and
each file block object further including a second pointer to a
corresponding one of the memory block objects, thereby linking each file
block object to a corresponding memory block for sequentially associating
memory blocks containing fragments of the named file,
9. A computer file system comprising:
at least one file name object, each file name object including a file name
field and at least one additional field for indicating an attribute of the
named file, the file name field including a string of data comprising a
human-readable name:
a number of memory block objects at least equal to the number of file name
objects, each memory block object including means defining a file starting
location, means defining a file length and a first pointer to a next
memory block object so that the memory block objects together form a first
linked list of memory blocks in the file system;
each memory block object further including a second pointer to a previous
memory block object so that the memory block objects together also form a
second linked list of memory blocks inversely related to the first linked
list;
the file name object further including a pointer to an initial one objects
to link the initial memory block object to the file named in the file name
field wherein:
each of the file name objects includes a pointer to a next file name object
so that the file name objects together form a linked list of file names
for use as a directory to the file system. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
BACKGROUND OF THE INVENTION
This invention pertains to the field of computer data storage, and in
particular to file systems for efficiently maintaining data files stored
in a random access memory. It further pertains to methods of automatic
optimization in a computer file system.
Sector Size
Heretofore, the trend in computer systems data storage has been to compact
data on physical magnetic media in order to enable larger storage volumes.
One example of this trend is the growth of sector size. The first magnetic
media disk drives usually had 128 bytes per sector. Today it is common to
find 512 or 1024 bytes per sector. Recent technological advances allow
4096 bytes per sector. Research is under way that will further increase
the size of a sector.
File system mechanisms
Heretofore, computer operating systems have used a mechanism by which one
or more disk sectors am addressed as a single cluster or block of disk
sectors. Typically, four or more sectors are addressed as a single cluster
or block. For example, MS-DOS will usually combine four contiguous sectors
of a hard disk with a 512 byte sector size into a single 2048 byte
cluster. Under UNIX a cluster is called a disk block and a common size for
a single disk block is 4096 bytes. In this application, I define a cluster
as any one or more associated disk sectors.
When a file is stored, is occupies one or more clusters. On average, the
last cluster used will be only half full. The remainder of the cluster is
unused and is not available for storage. The unused portion of the cluster
is wasted storage space.
A large cluster size is usually selected to enhance system disk access
performance. The larger the block of data that can be extracted or written
during a given operation, the fewer operations are required to perform a
given task. The majority of time delays in a disk system is associated
with the protocols involved in the operation performed. Increasing the
size of a transfer operation reduces the number of operations that need be
accomplished to transfer a file of a given size, and therefore the time
required.
An operating system defines a cluster size and then maps the sectors of a
disk into the clusters. The definition of cluster size allows the
operating system to address disks of differing sector size and provides a
universal mapping mechanism. For example, a 2048 byte cluster may have
four 512 byte sectors or two 1024 byte sectors depending on the sector
size of the disk. In the ideal situation, a cluster will map to a single
sector so no sectors are left unused. For example, a 4096 byte disk
cluster (block) under UNIX could map one-to-one with a disk that has a
4096 byte sector.
In an idealized file structure in which a cluster maps to a single sector,
it can be demonstrated that the larger the sector size, the more unused
physical media, mechanical or electronic. When a data file is stored, the
last sector of the file is usually only partially filled. In fact, it is
extremely rare for the last sector to be completely full. The file length
must be an exact multiple of the sector size if there is to be no wasted
storage space.
Heretofore, disk oriented file systems have required the central processing
unit to perform multiple table look-ups, address computation and data
transfers. This need is mandated by the fixed length of the storage media
compounded by the mechanical characteristics of the disk drive. When a
file operation is initiated, the central processing unit must obtain the
absolute address of the file by accessing a look up table which may reside
in main memory or on the disk itself. After obtaining a block address, the
central processing unit must issue a command for the block of disk space
to be accessed. This action must be repeated for each block of disk space
regardless of sequencing. The operations are performed in a loop that
repeats itself until the operation is completed.
Heretofore, semiconductor data storage media has been accessed in a manner
that emulates a spinning media disk drive. File systems were designed to
minimize the impact of the mechanical limitations of spinning media and to
address the media in an economical manner. The paradigm used to address
spinning media has been applied to semiconductor storage. To this end,
recent memory product announcements have been made that provide block
erase capability in spinning media sector size blocks. A reevaluation of
the paradigm in light of the capabilities of semiconductor media shows
that the paradigm is no longer valid.
Heretofore, flash memory storage file systems, such as Microsoft's Flash
File System, have address the issue of wasted storage space by
implementing a singly linked list wherein a status byte signifies whether
an entry is a file or a directory. When a file is requested, the list is
searched from the head until the file is found or the end of the list is
reached. For directory entries, child and sibling pointers are maintained.
Entries are added to the list sequentially.
When a file is deleted by the user, the entry for the file cannot be
deleted as the linked list would be broken. The file system cannot
maintain a "current position" for the user. File data is interleaved with
the directory information and is thus not centrally located nor easily
accessed. Finally, any and all modifications of the file system structure
require that a copy of the file system, including data, must be made, the
modifications made to the copy and the new file structure and data
re-stored in flash ram. Sometimes this copy is made and operated upon on
floppy disk, a very slow interface.
U.S. Pat. No. 4,791,564 to Takai discloses a random access memory file
apparatus for a personal computer with an external memory file. This
patent discloses providing an external memory file comprising random
access memory, in addition to the user system RAM. Files are transferred
from a floppy disk into the external memory file for use by the CPU in a
random access fashion. After modification in the memory file RAM, the
files are written back into the floppy disk in the usual serial access
format. The external memory file RAM also is used to provide a printer
spooler. In the memory file RAM, the first sector comprises an address
map. Subsequent sectors may contain essentially data only, on
contradistinction to the conventional floppy disk formatting in which
directory information such as file names and attributes are interspersed
at the beginning of the corresponding data.
U.S. Pat. No. 4,792,896 to Maclean et al discloses a storage controller
emulator which is used to provide transparent resource sharing in a
computer system. This patent teaches a microprocessor controlled mass
storage controller which acts as an interface for mass storage device
shared by a plurality of otherwise stand-alone microcomputer systems. The
mass storage controller provides a common interface to each of the
microcomputer systems which emulates the standard interface expected with
respect to an internal floppy disk drive for example. This allows multiple
users to share data without modifying their microcomputer system software
or hardware. It further allows for standard single user software to be
used without modification in a shared resource network environment.
Maclean et al disclose hardware to accomplish the described functionality,
but do not address the file system itself.
U.S. Pat. No. 4,896,262 to Wayama et al discloses a system for providing
semiconductor mass memory in a computer system. It discloses emulation
hardware for converting data and address information between a magnetic
disk memory format and a semiconductor memory format, so the data may be
transferred between a computer and a semiconductor storage device at
relatively high data transfer rates without modifying the computer system
which is configured in a magnetic disk access mode. The disclosure also
provides for synchronization of data transfer, error correction, and
multi-port access for use in a multi-computer system previously configured
in a magnetic disk access mode. In the same vein, U.S. Pat. No. 4,456,971
to Fukuda et al is directed to a semiconductor RAM that is accessible in
magnetic disk storage format. These patents essentially are directed to
hardware for converting address data and translating command signals for
emulating a magnetic disk memory.
Another recent patent directed to solid state emulation of rotating media
memory devices is U.S. Pat. No. 4,958,315 to Balch. In this system,
emulation is accomplished by multiplexing an offset memory address during
each bit time. Nonvolatile memory arrays translate the memory address to
an offset address that is proportional to the odd modular track length of
the multiple or single head track. An emulation address controller is used
to generate timing and initial addresses. In the Fukuda et al patent
discussed above, an address synthesizer is coupled to track and sector
address registers and also to a counter for synthesizing a RAM address
signal.
The need remains for a more efficient file system to speed file transfer
operations and for optimal use of memory space. The need also remains for
automatically reorganizing a file system to recapture newly available
memory space, and for automatically reassembling fragments in the file
system.
SUMMARY OF THE INVENTION
The invention includes a series of novel file system data structures for
creating and maintaining a computer file system. It further includes
methods of automatically optimizing the file system to maximize data file
storage in a memory. Another aspect of the invention comprises an improved
file system for fast and efficient file transfer operations. The improved
file system includes a plurality of linked lists of data objects to
maintain file name, directory, storage locations and free and used memory
blocks.
The preferred embodiment of the invention includes program code that is
operating system and platform independent, and a method for storing the
file system on a memory subsystem. The program code provides a mechanism
by which encoded data may be read from the random access memory subsystem
and used to construct several linked lists of program objects. The
preferred embodiment of the invention uses object oriented programming
techniques to maximize performance and minimize required storage space.
In one embodiment of the invention, a file system program is added to an
operating system and is run on the central processing unit in the
conventional manner. Alternatively, program execution may be divided
between the central processing unit and a second processing unit coupled
to the memory subsystem.
Another aspect of the invention is to store file directory information in
variable length program objects whose length is determined by the number
of file entries and sub-directories associated with the file directory.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 demonstrates the ability of the invention to more effectively use
available memory subsystem for data storage.
FIG. 2 is a pseudo code example of a MemBlock program object.
FIG. 3 illustrates the initial MemBlock multiply linked list with no files
stored.
FIG. 4 illustrates the MemBlock multiply linked list with a single file of
72,345 bytes length stored.
FIG. 5 is a pseudo code example of a function used to create new memory
block program objects.
FIG. 6 is a pseudo code example of a function used to set the state of a
MemBlock to free. Note that the function examines neighboring MemBlock
program objects to see if they are in the free state and if so, combines
them. This combining is a part of the automatic optimization process.
FIG. 7 is a pseudo code example of a function used to combine neighboring
MemBlock program objects.
FIG. 8 is a pseudo code example of a function used to inquire the size in
paragraphs of the block of memory associated with a MemBlock.
FIG. 9 shows the data structures used in file maintenance.
FIG. 10 illustrates the internal directory structure with forward and
reverse links.
FIG. 11 illustrates the internal file structure where files are associated
with a directory by linking the FileName program object to the Directory
program object. Also illustrated is the linking of FileBlock program
objects with the FileName program object.
FIG. 12 illustrates how FileBlock program objects relate to MemBlock
program objects.
FIG. 13 shows the links found in a simplified view of the file system
wherein only the root directory has any associated files and only one
other directory has child directories.
FIG. 14 is a pseudo code example of a function used to create a new
FileBlock program object.
FIG. 15 is a pseudo code example of a function used to free a FileBlock
program object. Note that in this case, free is not a state but a removal.
FIG. 16 illustrates how the file system will automatically perform leading
edge file system optimization.
FIG. 17 illustrates how the file system will automatically perform trailing
edge file system optimization.
FIG. 18 is a pseudo code example of a function used to write information to
the memory space associated with a single MemBlock program object. The
function implements both leading and trailing edge file system
optimization. The function is an internal lower-level function and is not
available to application programmers.
FIG. 19 is a pseudo code example of a function used to write a file to the
data port. This is the function that will be used by application
programmers to store files on the data port. The function implements a
portion of the automatic optimization process.
FIG. 20 shows an example of how the boot record and file system header
would be mapped to data port memory.
FIG. 21 illustrates the two parts of the file system header. The first part
is for MemBlock program objects and the second for FileBlock program
objects that represent the entire file system structure.
FIG. 22 is a table of some high-level file system functions categorized by
class of function.
FIG. 23 is a pseudo code listing of the create file function as it would be
implemented using an example.
FIG. 24 illustrates the relationship between the free and optional used
lists composed of MemList program objects and the multiply linked list of
MemBlocks.
FIG. 25 is a pseudo code listing of a program used to generate the free and
optional used lists.
FIG. 26 illustrates the free and used lists implemented using MemBlock data
structures and how those structures relate to the double linked list of
MemBlocks.
FIG. 27 illustrates the division of labor when data port local intelligence
is used to maintain the low level file system information. The operating
system need only maintain an abbreviated copy of the file system
information with index values that are interpreted by data port
intelligence.
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT
For convenience sake, let us equate a memory subsystem's data paragraph to
a disk sector and let us assume that a data paragraph contains eight bytes
of data. Using this definition, the memory subsystem could be said to have
an eight byte sector. If a sector size of 8 bytes and is compared to a 512
byte sector in storing a file of 518 bytes, the device with a 512 byte
sector will waste 506 bytes of the second sector while the invention with
an 8 byte sector will waste 6 bytes of the 65th sector as illustrated in
FIG. 1. Note also that many more file lengths will be a multiple of 8 than
of 512. Because the invention uses very small data paragraphs, less
physical media is unused by the operating system.
Memory Maintenance
Memory subsystem block status and use are controlled and indicated by using
a MemBlock data structure as illustrated in FIG. 2. 16 bit unsigned
integers (Ulnt 16) are used to indicate page and offset information. If we
assume that the memory subsystem uses an eight byte data paragraph and
that a page consists of 65,536 (64 KB) data paragraphs, then a single page
represents 524,288 bytes of storage (512 KB). 65,536 available pages
provides the invention the ability to construct a 32 GB (34,359,738,368
bytes) file system. If 32 bit unsigned integers are used to indicate page
and offset information, then a page would consist of 4,294,967,296
paragraphs which could store 34,359,738,368 bytes (32 GB). Because there
are 4,294,967,296 (4 G) pages, the file system would be able to address
147,573,952,583,676,412,928 bytes (147,573,952 TB or 147,473,952,583 GB).
To compute the size of the file system, the following equations are used:
Paragraph=2.sup.y bytesPage=2.sup.n paragraphs=2.sup.n * 2.sup.y bytes
System=2.sup.n
pages=2.sup.n * 2.sup.n * 2.sup.y bytes
File System Size in bytes=2.sup.2n+y
Therefore, a 16 bit file system addressing scheme with 8 byte paragraphs
would address
2.sup.16 * 2.sup.16 * 2.sup.3 =2.sup.35
bytes. A 32 bit file system addressing scheme with 8 byte paragraphs would
address
2.sup.32 * 2.sup.32 *2.sup.3 =2.sup.67
bytes. Note that by changing the paragraph size or the size of the
addressing scheme indicators, the total file system size changes. A
paragraph may consist of one or more system words.
Refer again to FIG. 2. The StartPage variable indicates the starting page
address for the memory block. The StartOffset variable indicates how far
into the page the block begins. The BlockPages variable indicates the
number of complete pages contained in the memory block. The LastPageLength
variable indicates how far into the last page the memory block extends.
BlockPages and LastPageLength are measured as offsets from the starting
address and are thus relative rather than absolute address indicators. The
BytesLastParagraph variable indicates how many bytes of the last paragraph
are used. The NextBlock variable is a pointer to the next memory block in
the doubly linked list. The PreviousBlock variable is a pointer to the
previous memory block in the doubly linked list.
Initially, when the memory subsystem is first formatted, a single MemBlock
structure indicates that the entire memory subsystem is available. For
example, if the memory subsystem contains 64-MB of available storage, then
the contents of the sole MemBlock structure would be as illustrated in
FIG. 3. BlockPages would be set to 128, (64M/512K), and LastPageLength set
to zero. Free would be set to TRUE and IndexNumber set to 0. Both
*NextBlock and *PreviousBlock are set to NULL to indicate that there is no
MemBlock structures in either direction. When a search of the MemBlock
doubly linked list is accomplished, the presence of the NULL pointer
indicates the end of the list in the desired search direction.
If a file whose length is 72,345 bytes is stored, the resultant multiply
linked list of MemBlock structures would appear as in FIG. 4. The file
would occupy 9044 data paragraphs of the first page with 1 byte of the
last paragraph used.
Memory Maintenance Operations
A. Creating and Splitting Blocks of Memory
When the memory subsystem storage is initially formatted, a single MemBlock
program object is created that indicates the entire storage capability of
the memory subsystem. Because no data has yet been stored, the MemBlock
indicates that the memory area is free. When a file is created and then
saved, the file will be written to the address indicated by first free
MemBlock. When the file is written, one of three things will occur. (1) If
the file to be saved is larger than available storage, the write will fail
and the user notified of insufficient storage, as in current file system.
(2) If the file is the same size as the memory block indicated in the
MemBlock program object, the MemBlock will be marked as not free. (3) If
the file is smaller than the indicated storage capacity, then a new
MemBlock program object must be created to indicate the free storage while
the existing MemBlock program object is used to indicate the used portion
of the storage area.
Refer to FIG. 5 which is a pseudo code example of a function SplitMemBlock
used to create and initialize a new MemBlock program object. The function
SplitMemBlock is passed the address of the MemBlock to divide along with
the number of pages and the length of the last page to be assigned to the
existing MemBlock. A new MemBlock program object is created and its
starting address computed. The original MemBlock is altered to indicate
the new number of pages and last page length. The newly created MemBlock
is assigned the remainder of the available storage by computing the number
of complete pages and remainder as BlockPages and LastPageLength
respectively.
Next, the multiply linked list is updated by inserting the newly created
MemBlock program object between the original MemBlock and any following
MemBlock. Next, a call to a function FreeMemBlock is made to mark the new
MemBlock as free. Finally the function returns a pointer to the new
MemBlock program object.
B. Function FreeMemBlock
Refer to FIG. 6. When a MemBlock program object indicates a portion of
storage that does not contain data, it needs to be marked as free. The
function FreeMemBlock is used to accomplish this task. The pointer to the
MemBlock to be marked free is passed to the function. The function makes
use of the multiply linked list of MemBlock program objects to check
neighboring MemBlock program objects to see if they are marked as free. If
they are, they are combined into a single MemBlock program object and the
resultant MemBlock program object is marked as free.
C. Function CombineMemBlocks
Refer to FIG. 7. To combine two MemBlock program objects into a single
MemBlock program object, the function CombineMemBlocks is called, passing
it the pointers to the two MemBlocks to be combined. The program first
verifies that the two MemBlocks are indeed neighbors and can be combined.
If not, an error code is set and the function returns a NULL pointer to
the calling program indicating an error has occurred. If the two MemBlocks
are neighbors, they are ordered and then the combined length of storage
memory indicated by the two MemBlocks is computed.
In computing the new length, the LastPageLengths of each MemBlock are
added. The result is divided by the size of a page to determine if the
combined length is greater than a single page. The result of the division
is stored in a temporary variable which will now equal either one to
indicate a result equal to or greater than a page or a zero to indicate
that the result was smaller than a page. The temporary variable is added
to the sum of the two MemBlock's BlockPages variables and the result
assigned to the first MemBlock. The LastPageLength of the first MemBlock
is then set to the combined length divided modulo the page size. Modulo
dividing the combined length insures that if the combined length was
larger than a full page, the result will be the remainder after removing
the page size from the combined memory. Recall that the portion of the
combined length equal to a page would be added as a page in the BlockPages
variable.
D. Function GetMemBlockLength
Function GetMemBlockLength determined the size of storage memory
represented by the MemBlock program object. Refer to FIG. 8, a pseudo code
example to illustrate the function GetMemBlockLength is passed a pointer
to the MemBlock of interest and the length in paragraphs of the storage
memory represented is computed and returned to the calling program.
File Maintenance
File maintenance is accomplished using several data structures. Please
refer to FIG. 9.
A. FileBlock Data Structure
The first data structure defined in FIG. 9 is called a FileBlock. The
FileBlock data structure stores an index into the linked list of memory
blocks. When initialized, the MemBlockPtr pointer is determined by
accessing the MemBlock whose position in the multiply linked list of
MemBlocks is indicated by the index. The pointer to the MemBlock is then
stored. The index variable is used only during initialization and when the
file system data structures are stored in the data port during a
synchronization operation. If the file is fragmented, the NextFileBlock
pointer references the FileBlock data structure containing the next memory
block information. The last FileBlock data structure associated with a
file has a NULL pointer value for NextFileBlock. When this structure is
stored during synchronization, only the index value need be written to the
storage media.
B. FileName Data Structure
The FileName data structure in FIG. 9 is used to maintain FileBlocks and
associated MemBlocks and associate them with the name of a file. The file
name is stored in a variable length character array. A pointer to the
first FileBlock is stored in the FileBlockPtr variable upon initialization
and a linked list of FileBlocks constructed. File access permissions for
the owner, group and the system are stored in a Permissions variable.
(Permissions are typically read-only and read-write for the owner, group
and system.)
The Attributes variable stores information about the file status, such as,
is it a hidden file, a system file, an executable file, an open file or
has it been backed up since the last modification. The date and time of
the last time the file was modified is stored in the Modified variable.
Note that the data actually stored in the FileName data structure will
depend upon the operating system under which the invention is implemented.
Alterations, additions and deletions to and of these variables must occur
to provide the operating system with the data that it expects.
The optional NumBlocks variable indicates how many FileBlocks are used to
store the file. The NumBlocks variable is not needed by any operations and
is included only as a convenience to simplify the a search for fragmented
files. The FileBlockPtr pointer indicates the address of the first
FileBlock. The NextFileName pointer points to the FileName data structure
for the next file residing in the directory thereby forming a linked list
of files associated with the directory. The FileSize variable is optional
and stores the size in bytes of the file. The size of the file is easily
computed, therefore, this variable is a convenience used only when a user
wishes to find out the size of the file.
C. Directory Data Structure
The Directory data structure is used to store directory information. The
name of the directory is stored in the DirName variable length character
array. NumFiles indicates how many files are located in the linked list of
| | |
