Method and system for maximizing data files stored in a random access memory of a computer file system and optimization therefor

• US 5,479,656 A
• Filed: 05/13/1992
• Issued: 12/26/1995
• Est. Priority Date: 05/13/1992
• Status: Expired due to Term

• Current Assignee: Jolin Data Solution LLC (Intellectual Ventures LLC)
• Original Assignee: Joseph H. Rawlings III
• Inventors: Rawlings, Joseph H. III
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US07/882,430
• Time in Patent Office: 1,322 Days
• Field of Search: 395/600, 395/400, 395/425, 364/DIG. 1, 364/DIG. 2
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1008 in individual solid state devices G06F11/1004 takes precedence
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/0658 Controller construction arrangements
• CPC Class Codes: G06F 3/0674 Disk device
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A computer file system mechanism to use data port storage efficiently wherein lost or unused storage space is minimized and use of available storage maximized. The data port file system may be used as an augmentation of existing file system mechanisms or in complete replacement thereof. The data port file system may be implemented such that the information required to maintain the file system is always updated to the data port or such that the information required to maintain the file system is always located in system memory during computer operations. The data port file system may be implemented such that both methods are used.

Claims

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.