File system for non-volatile computer memory

Details File system for non-volatile computer memory File system for non-volatile computer memory

1999-04-26

2001-08-28

Yoo, Do Hyun (Department: 2187)

Electrical computers and digital processing systems: memory

Storage accessing and control

Specific memory composition

C711S001000, C711S100000, C707S793000, C707S793000, C707S793000, C707S793000, C707S793000, C707S793000, C714S015000

Reexamination Certificate

active

06282605

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to a file system for non-volatile computer memories. More particularly it relates to a system for ascertaning the physical locations of files in random access memories such as flash memories that have attributes similar to those of disk drives and the like. The invention uses an improved B-tree structure to identify the physical memory locations corresponding to logical addresses supplied by application programs that access the memory locations.
The invention is particularly applicable to memory, such as flash memory, in which data is written in blocks of various sizes and in which erasure of data to recover memory space for rewriting of data is constrained to relatively large zones of contiguous locations.
BACKGROUND OF THE INVENTION
Prior file systems for flash memories have used a multi-level paging structure to convert logical addresses to physical memory addresses. Each level in the structure corresponds to predetermined bit positions in the logical address space. For example, the root page, which is usually kept in the working random access memory, may contain entries corresponding to the first eight bits of the logical addresses. These entries contain pointers to pages in the second level, each of which contains entries corresponding to the second set of eight bits. The latter entries, in turn, point to pages in the third level, whose entries point to the physical memory locations. The second and third level pages are kept in the flash memory and retrieved as need when locations in the memory are to be accessed.
PROBLEMS RELATED TO THAT
These systems suffer from a number of disadvantages. First, there must be one entry in the page tables for each possible logical address. Second, the page tables do not directly represent the common case, in which large blocks of data are written sequentially; in order to perform large sequential transfers, software must detect sequential runs in the page tables and optimize the transfers as a separate step. Third, in order to maintain the page tables on flash memory, extra levels of indirection are required, and updates to the indexing structure are accomplished by clearing bits in place. This update-in-place operation makes page tables as used in the prior art unsuitable for some kinds of mass storage media.
The difficulties with the prior approaches are related to reliability. First, updating the map entries efficiently and consistently, in the face of power failures and other arbitrary system upsets, requires a multi-step process involving multiple updates to the same location. For some memory technologies, this process greatly increases the bit error rate. In other cases, the memory technology requires block error-correction codes. These codes make it impractical to do bit-level updates within an existing block. For other memory technologies, updating a bit requires rewriting the entire block; if power is interrupted while the block is being written, the result of the write is indeterminant.
In any case, the use of bit updates precludes the use of common block error-detection codes over the mapping table pages. Because of the nature of the data structures involved, a single bit error can cause catastrophic loss of data, with no easy way to recover the information.
SUMMARY OF THE INVENTION
A file system incorporating the invention includes a B-tree directory structure that is used to find the physical flash memory addresses corresponding to the logical addresses used by the application programs and operating system running on a computer. This B-tree is enhanced relative to a normal B-tree by improving the key structure, and by arranging never to update any existing portion of the B-tree; instead, a new partial tree is written as needed. The resulting file system is particularly suitable for flash memory, but is also suitable for RAM, EEPROM, and magnetic storage devices.
A B-tree is similar to a binary tree except that at each level it will, in general, have at least two entries at each node. To avoid confusion with terminology used in other arrangements we use the term “bucket” to denote the group of entries at each node.
The tree structure begins with a root bucket, which contains entries corresponding to a plurality of keys, i.e., logical addresses. Each entry contain in addition to a key, the physical memory address corresponding to the key. For keys that are not contained in the root bucket, there are pointers to buckets in the next level of the tree structure. These pointers are interleaved with key entries. Thus, if a key value is between the key values of two adjacent key entries, a pointer positioned between the two entries directs the search to a bucket at the next level. The search continues in the same manner in the second bucket. That is, if the key is contained in that bucket, the entry containing the key provides the physical memory address. Otherwise, a pointer, positioned between the recorded keys that bracket the search key, points to a bucket at the next level of the tree structure.
The number of levels in the tree structure depends on the number of entries allowed in each bucket and also on the total number of keys, i.e., logical memory block addresses.
Further in accordance with the invention, each recorded key preferably contains not only the logical address of the beginning of a block of data, but also the length of the block. Thus, each entry in the tree contains the following information:
A. a logical sector address “L”;
B. a corresponding physical memory address “P”;
C. a sector count “N”;
We use the term “BN-tree” to denote this structure.
The tree structure thus represents a mapping of logical sectors L . . . (L+N−1) to physical sectors P . . . (P+N−1). This improves the efficiency of storage, since file systems normally write data sequentially and individual mappings of a sequence of memory locations can therefore be combined in a single BN-tree entry. This also improves the efficiency of large data transfers, since they require fewer (as few as 1) searches for physical memory locations, and data can be read sequentially from a longer stretch of physical memory locations into the system data buffers with a high-speed transfer loop.
The records in each BN-tree bucket are sorted in ascending order of the logical sector address L. However, the comparison technique used when searching for given logical addresses is somewhat different from that used in a conventional B-tree. In order to obtain consistent results from the BN-tree searches, the comparison routine compares the tree entries against input keys, i.e. logical addresses provided by the application programs, as follows:
A. If a canadate tree key entry (L
x
N
x
) is identical to the input key (L
r
N
r
),
the keys are EQUAL and the entry provides the required physical address;
B. If the last sector mapped by the tree entry (L
r
+N
r
−1) is below the first sector of the input entry, then the tree entry is LESS THAN the input entry; and
C. otherwise, the last sector mapped by the tree entry (L
x
+N
x
−1) is above the first sector of the input entry, but the input key is not equal to the tree entry; so the tree entry is GREATER THAN the input key entry.
If case B holds, the range of numbers L through L+N−1 for the tree entry is known not to overlap any of the numbers given by the input entry. If case C holds, the tree entry might overlap the input entry.
This algorithm defines a strict ordering when comparing the tree entries against the input key. It guarantees that the search will find either an identical record, or will position the search at the least record, i.e., key, record that is GREATER THAN the input key. This comparison routine, unlike most comparison routines is not symmetric. Specifically, it is traditional for comparison routines to return −1 to mean less than, zero to mean equal, +1 to mean greater than. If the routine is symmetric, compare (A, B)== compare (B, A). The comparison routine defined above, however, sho

Affiliated with

Also associated with

Rating

File system for non-volatile computer memory does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with File system for non-volatile computer memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and File system for non-volatile computer memory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2480822