EP0557736A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
A method and system for file system management using a flash-erasable, programmable, read-only memory
Assignee: Microsoft Corp
•
Filing: 1993-01-29
•
Granted: —
•
Expires: 2013-01-29
Abstract
Abstract The present invention relates to a manager for a computer memory comprising: a block allocation routine, the memory divided into blocks of memory locations, each block having an allocation table and a data region divided into data areas, each allocation table having entries corresponding to region data areas, the block allocation routine for selecting a block in which to store data; a data area allocation routine for selecting a data area within the data region for the selected block in which to store data, for selecting an allocation table entry to correspond to the selected data area, and for setting the selected allocation table entry to correspond to the selected data area and to an allocated state; and a storage routine for storing data in the selected data area.
Inventors
- 👤 William J. Krueger
- 👤 Sriram Rajagopalan
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-09 21:30
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/14; G06F11/1402; G06F11/1415; G06F11/1435; G06F12/00; G06F12/02; G06F12/0223; G06F12/023; G06F12/0238; G06F12/0246; G06F16/00; G06F16/10; G06F16/90; G06F16/901; G06F16/9017; G06F2212/00; G06F2212/72; G06F2212/7205; Y; Y10; Y10S; Y10S707/00; Y10S707/99951; Y10S707/99956
Claims Analysis
Total Claims: 41
Claim 1
Independent Claim
124 words
A manager for a computer memory comprising: a block allocation routine, the memory divided into blocks of memory locations, each block having an allocation table and a data region divided into data areas, each allocation table having entries corresponding to region data areas, the block allocation routine for selecting a block in which to store data; a data area allocation routine for selecting a data area within the data region for the selected block in which to store data, for selecting an allocation table entry to correspond to the selected data area, and for setting the selected allocation table entry to correspond to the selected data area and to an allocated state; and a storage routine for storing data in the selected data area.
Claim 2
Dependent Claim
52 words
The manager for a computer memory of claim 1 further comprising: a data area deallocation routine for setting an allocation table entry that is in the allocated state to a deallocated state; and a block reclamation routine for reclaiming data areas corresponding to allocation table entries that are in that deallocated state.
Claim 3
Dependent Claim
42 words
The manager for a computer memory of claim 1 further comprising: an initialization routine, each block having header information, the initialization routine for gathering information from the headers and from the allocation tables and storing the gathered information in a memory cache.
Claim 4
Dependent Claim
76 words
A write-once, multiple-read memory device, the memory device having one or more logical blocks, comprising: a data region in each block, the data region logically divided into data region areas for storing data; and a block structure stored in each block, the block structure having a header and an allocation table, the header containing block-specific information, the allocation table having entries corresponding to data region areas and containing information relating to the corresponding data region areas.
Claim 5
Dependent Claim
22 words
The memory device of claim 4 wherein the header contains a logical block number, a block status, and a block erase count.
Claim 6
Dependent Claim
37 words
The memory device of claim 4 wherein an allocation table entry contains a pointer to the corresponding data region area, a length indicating the length of the corresponding data region area, and an allocation table entry status.
Claim 7
Dependent Claim
16 words
The memory device of claim 4 wherein the memory device is a block-erasable, programmable, read-only memory.
Claim 8
Independent Claim
48 words
A method of memory management in a block-eraseable, programmable, read-only memory, the memory comprising a plurality of blocks, method comprising the steps of: storing block header information in each block; storing an allocation table in each block; and storing data in a data storage area in each block.
Claim 9
Dependent Claim
23 words
The method of claim 8 wherein the block header information includes a logical block number, a block status, and a block erase count.
Claim 10
Dependent Claim
56 words
The method of claim 8 wherein the allocation table contains entries corresponding to portions of the data storage area, the entries containing a pointer to the corresponding portion of the data storage area, a length indicating the length of the corresponding portion of the data storage area, and a status indicating the status of the entry.
Claim 11
Independent Claim
68 words
A method of reclaiming deallocated space in a block-eraseable, programmable, read-only memory, the memory having blocks, the method comprising the steps of: identifying data regions as deallocated or allocated in a block to be reclaimed; erasing a spare block; and copying allocated data regions from the block to be reclaimed to the spare block whereby a memory area corresponding to the deallocated data region is reclaimed for allocation.
Claim 12
Dependent Claim
20 words
The method of claim 11 wherein the allocated data regions are copied into contiguous memory locations in the spare block.
Claim 13
Independent Claim
101 words
A method of addressing a data region in a computer memory device, the memory divided into blocks, each block having a physical block number, the method comprising the steps of: storing an allocation table in each block, the allocation table having entries that indicate an offset of a data region within the block and that have an entry index; storing a logical block number in each block; identifying a data region by logical block number and allocation table entry index; and generating an address to the identified data region based on the logical block number and the allocation table entry index.
Claim 14
Dependent Claim
83 words
The method of claim 13 wherein the step of generating an address includes the steps of: determining the physical block number from the logical block number, each block having a corresponding start address; retrieving the offset from the allocation table entry in the determined physical block number that is indexed by the allocation table entry index; and adding the retrieved offset to the start address of the block with the determined physical block number to generate the address of the identified data region.
Claim 15
Dependent Claim
18 words
The method of claim 13 or 14 wherein the computer memory device is a block-erasable, programmable, read-only memory.
Claim 16
Independent Claim
74 words
A method of identifying a block in a computer memory device, each block having a physical block number, the method comprising the steps of: storing a logical block number in each block; generating a mapping from each logical block number to the physical block number in which the logical block number is stored; receiving a logical block number; and translating the received logical block number to a physical block number using the generated mapping.
Claim 17
Dependent Claim
28 words
The method of claim 16 including the step of when reclaiming a block, copying the logical block number from the block to be reclaimed to the reclaimed block.
Claim 18
Independent Claim
18 words
The method of claims 16 or 17 wherein the computer memory device is a block-erasable, programmable, read-only memory.
Claim 19
Independent Claim
87 words
A method of maintaining an erase count of a block in a block-erasable, programmable, read-only memory, the memory having a plurality of blocks, the method comprising the steps of: storing an erase count in each block, the erase count indicating the number of times the block has been erased; when copying a first block to a second block, retaining the erase count of the second block; and when erasing a block, incrementing the erase count before erasure and storing the incremented erase count in the erased block.
Claim 20
Independent Claim
74 words
A method of allocating a block in a block-eraseable, programmable, read-only memory for the storage of data, the method comprising the steps of: maintaining an erase count for each block, the erase count indicating the number of times the block has been erased; selecting blocks with enough space to store the data; and identifying the selected block based on the erase count for the storage of data to effect the allocation of the block.
Claim 21
Independent Claim
58 words
A method of leveling block erasures in a block-erasable, programmable, read-only memory, the method comprising the steps of: identifying a first block that has been erased; identifying a second block that has been erased a fewer number of times than the first block; and swapping the data in the first block with the data in the second block.
Claim 22
Dependent Claim
163 words
A computer file storage system for organizing files based on a hierarchical directory structure, the directory structure having a plurality of directory entries, the system comprising: a computer, the computer having a memory for storing directory entries; means for allocating a portion of the memory for storing a directory entry, the directory entry having a primary pointer, a secondary pointer, and a sibling pointer, the pointers initially being set to a predefined value; means for setting the sibling pointer of a directory entry to point to another directory entry at the same level in the directory structure to form a linked list of sibling directory entries; means for setting the primary pointer of a directory entry to point to another directory entry at the next level lower in the directory structure; and means for setting the secondary pointer of a superseded directory entry to point to a superseding directory entry, the superseding directory entry to contain updated data for the superseded directory entry.
Claim 23
Dependent Claim
53 words
The computer file storage system of claim 22 further comprising: means for setting the primary pointer of the superseding directory entry equal to the primary pointer of the superseded directory entry; and means for setting the sibling pointer of the superseding directory entry equal to the sibling pointer of the superseded directory entry.
Claim 24
Dependent Claim
52 words
The computer file storage system of claim 22 further comprising: means for allocating a portion of the memory for storing a file entry, the file entry to contain information relating to an associated file; and means for setting the primary pointer of a directory entry to point to the allocated file entry.
Claim 25
Dependent Claim
92 words
The computer file storage system of claim 24 wherein the allocated file entry contains a primary pointer, a secondary pointer, and a sibling pointer initially being set to a predefined value, including: means for setting the sibling pointer of a file entry to point to another file or directory entry to form a linked list of file or directory entries; and means for setting the secondary pointer of a superseded file entry to point to a superseding file entry, the superseding file entry to contain updated data for the superseded file entry.
Claim 26
Dependent Claim
53 words
The computer file storage system of claim 25 further comprising: means for setting the primary pointer of the superseding file entry equal to the primary pointer of the superseded file entry; and means for setting the sibling pointer of the superseding file entry equal to the sibling pointer of the superseded file entry.
Claim 27
Dependent Claim
55 words
The computer file storage system of claim 24 further comprising: means for allocating a portion of the memory for storing a file information entry, the file information entry to contain information relating to a file extent; and means for setting the primary pointer of a file entry to point to the allocated file information entry.
Claim 28
Dependent Claim
101 words
The computer file storage system of claim 27 wherein the file information entry contains a primary pointer and secondary pointer initially being set to a predefined value, further comprising: means for setting the primary pointer of the file information entry to point to another file information entry associated with the same file to form a linked list of file information entries for that same file; and means for setting the secondary pointer of a superseded file information entry to point to a superseding file information entry, the superseding file information entry to contain updated data for the superseded file information entry.
Claim 29
Dependent Claim
33 words
The computer file storage system of claim 28 further comprising: means for setting the primary pointer of the superseding file information entry equal to the primary pointer of the superseded file information entry.
Claim 30
Dependent Claim
121 words
A computer file storage system for storing files, the system comprising: a computer, the computer having a memory for storing the files; means for allocating a portion of the memory for storing a file entry, the file entry to contain information relating to an associated file and containing a primary pointer, a secondary pointer, and a sibling pointer initially being set to a predefined value; means for setting the sibling pointer of a file entry to point to another file entry to form a linked list of file entries; and means for setting the secondary pointer of a superseded file entry to point to a superseding file entry, the superseding file entry to contain updated data for the superseded file entry.
Claim 31
Dependent Claim
53 words
The computer file storage system of claim 30 further comprising: means for setting the primary pointer of the superseding file entry equal to the primary pointer of the superseded file entry; and means for setting the sibling pointer of the superseding directory entry equal to the sibling pointer of the superseded directory entry.
Claim 32
Dependent Claim
147 words
The computer file storage system of claim 30 wherein the file information entry contains a primary pointer and secondary pointer initially being set to a predefined value, including: means for allocating a portion of the memory for storing a file information entry, the file information entry to contain information relating to a file extent of a file; means for setting the primary painter of a file entry to point to the allocated file information entry; means for setting the primary pointer of a file information entry to point to another file information entry associated with the same file to form a linked list of file information entries for the same file; and means for setting the secondary pointer of a superseded file information entry to point to a superseding file information entry, the superseding file information entry to contain updated data for the superseded file information entry.
Claim 33
Dependent Claim
33 words
The computer file storage system of claim 32 further comprising: means for setting the primary pointer of the superseding file information entry equal to the primary pointer of the superseded file information entry.
Claim 34
Independent Claim
98 words
A method of updating data stored on a computer memory device with new data, the memory device containing records of data, each record having a secondary pointer, initially having a predefined value, the method comprising the steps of: locating a record that contains data to be updated; allocating a record to contain the new data; writing the new data to the allocated record; and setting the secondary pointer in the located record to point to the allocated record to indicate that the new data in the allocated record is an update of the data in the located record.
Claim 35
Dependent Claim
34 words
The method of claim 34 wherein the step of setting the secondary pointer includes setting a flag in the located record to indicate that the secondary pointer has been changed from the predefined value.
Claim 36
Independent Claim
180 words
A method for error recovery in a computer system with a write-once, multiple-read memory device, the memory device having one or more logical blocks, the method comprising the steps of: (a) defining a data region for each block, the data region logically divided into data region areas for storing data; (b) defining a block structure for each block, the block structure having a header and an allocation table, the header containing block-specific information, the allocation table having entries corresponding to data region areas and containing information relating to the corresponding data region areas; (c) allocating an allocation table entry; (d) allocating a data region area to store data; (e) writing data relating to the allocated data region area to the allocated allocation table entry; (f) writing data to the allocated data region area; (g) detecting an error while writing to the data region area; and (h) upon detecting the error, setting the allocation table entry to a deallocated state and repeating steps (c), (d), (e), and (f) until no error is detected while writing data to the data region area.
Claim 37
Independent Claim
195 words
A method for error recovery in a computer system with a write-once, multiple-read memory device, the memory device having one or more logical blocks, the method comprising the steps of: (a) defining a data region for each block, the data region logically divided into data region areas for storing data; (b) defining a block structure for each block, the block structure having a header and an allocation table, the header containing block-specific information, the allocation table having entries corresponding to data region areas and containing information relating to the corresponding data region areas; (c) allocating an allocation table entry; (d) allocating a data region area to store data; (e) writing data relating to the allocated data region area to the allocated allocation table entry; (f) writing data to the allocated data region area; (g) setting the allocated allocation table entry to an allocated state; (h) detecting an error while setting the allocated allocation table entry to the allocated state; and (i) upon detecting the error, setting the allocation table entry to a null state and repeating steps (c), (e), and (g) until no error is detected while writing data to an allocated allocation table entry.
Claim 38
Independent Claim
96 words
A method for error recovery in a computer system with a write-once, multiple-read memory device, the memory device having one or more logical blocks that are erasable, the method comprising the steps of: defining a block header data structure for a block, the block header data structure containing the state of the block; writing data to the block header data structure; and upon detecting an error while writing to the block header data structure, setting the block to a queued for erasure state whereby the block is not used for storing data until it is erased.
Claim 39
Independent Claim
81 words
A method for error recovery in a computer system with a write-once, multiple-read memory device, the memory device having one or more logical blocks that are erasable, the method comprising the steps of: defining a block header data structure for a block, the block header data structure containing the state of the block; erasing the block; and upon detecting an error while erasing the block, setting the block to a retired state whereby the block is not used for storing data.
Claim 40
Independent Claim
110 words
A method in a computer memory manager for specifying that a specified memory device is not block-erasable, the computer memory manager for managing a block-erasable, write-once, multiple-read memory device, wherein the memory manager maintains a count of spare blocks, wherein the memory manager compacts data in a specified block by copying the data to a spare block, erasing the specified block, and setting the specified block to be a spare block, the method comprising the step of setting the count of spare blocks to 0 so that the memory manager does not compact data in a block because of the unavailability of a spare block in the specified memory device.
Claim 41
Independent Claim
76 words
A method in a computer memory manager for specifying that a specified write-once, multiple-read memory device is not block-erasable, the memory manager for managing a block-eraseable, write-once, multiple-read memory device, wherein the memory manager maintains a count of spare blocks, a spare block for use in compacting data in a block, the method comprising the step of setting the count of spare blocks to 0 to suppress the erasure of a block by the memory manager.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.