US5146571A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Remapping defects in a storage system through the use of a tree structure
Assignee: EMC Corp
•
Filing: 1990-02-26
•
Granted: 1992-09-08
•
Expires: 2010-02-26
Abstract
Abstract A method and apparatus are disclosed for mapping a logical address generated by a device seeking access to a storage media into a corresponding physical address to create the appearance that all good addresses consitute a continuous defect free address space in the storage medium. A tree structure is created based upon known defective addresses in the storage medium. The upper levels of the tree are selectively loaded with decisional criteria which are employed to branch downward to an offset value stored in the lowest tree level. The respective offset value is added to the logical address to produce the desired physical address of the storage media for access. The tree is traversed each time an address is presented to map the requested logical address into a physical address corresponding to a location in the storage device for access. The media thus appears to the requesting device to be a continuous defect free address space with defective addresses congregated at the end of the address space, thereby avoiding the need for the requesting device to fragment files due to media defects.
Inventors
- 👤 Donald G. Logan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 14:20
CPC Classifications
G; G11; G11B; G11B20/00; G11B20/10; G11B20/18; G11B20/1883; G11C; G11C29/00; G11C29/70; G11C29/88; G11B2020/10916; G11B2220/00; G11B2220/20
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
304 words
Apparatus for transforming logical addresses produced by a device requesting access to storage media in a disk subsystem into defect free physical addresses corresponding to specific locations on said media so as to create the appearance to said requesting device that said media includes a large, continuous, defect-free address space comprising: means for generating a defect list comprising addresses of defective sectors in said storage media of said disk subsystem; means for restructuring said list to produce a list comprising defect free logical addresses employed as decisional criteria and to produce an offset list containing a plurality of predetermined offset values; means for ordering said list of defect free logical addresses and said offset list into an array having a predetermined organizational structure wherein said array may be traversed in a preselected manner within a predetermined maximum number of traverses; said organizational structure comprising a memory table including a plurality of elements corresponding to elements of a tree structure, said tree structure having a plurality of upper levels and a lower level; means for storing values from said list of defect free logical addresses in selected elements in said memory table corresponding to elements of said upper tree levels; means for storing said predetermined offset values from said offset list in selected elements in said memory table corresponding to elements of said lower tree level; means for traversing selected element in said table corresponding to elements of said upper level tree levels for each logical address produced by said requesting device to arrive at an element in the lower tree level of said table containing a predetermined offset value associated with the respective logical address; and means for adding said predetermined offset value to the respective logical address to produce a defect free physical address corresponding to a sector on said media for access.
Claim 2
Dependent Claim
304 words
Apparatus for transforming logical addresses produced by a device requesting access to storage media in a disk subsystem into defect free physical addresses corresponding to specific locations on said media so as to create the appearance to said requesting device that said media includes a large, continuous, defect-free address space comprising: means for generating a defect list comprising addresses of defective sectors in said storage media of said disk subsystem; means for restructuring said list to produce a list comprising defect free logical addresses employed as decisional criteria and to produce an offset list containing a plurality of predetermined offset values; means for ordering said list of defect free logical addresses and said offset list into an array having a predetermined organizational structure wherein said array may be traversed in a preselected manner within a predetermined maximum number of traverses; said organizational structure comprising a memory table including a plurality of elements corresponding to elements of a tree structure, said tree structure having a plurality of upper levels and a lower level; means for storing values from said list of defect free logical addresses in selected elements in said memory table corresponding to elements of said upper tree levels; means for storing said predetermined offset values from said offset list in selected elements in said memory table corresponding to elements of said lower tree level; means for traversing selected element in said table corresponding to elements of said upper level tree levels for each logical address produced by said requesting device to arrive at an element in the lower tree level of said table containing a predetermined offset value associated with the respective logical address; and means for adding said predetermined offset value to the respective logical address to produce a defect free physical address corresponding to a sector on said media for access.
Claim 3
Dependent Claim
199 words
Apparatus for creating a tree structure for use in transforming logical addresses produced by a device requesting access to a storage media into defect free physical addresses corresponding to specific locations on said media within a predetermined maximum number of transformation steps, so as to create the appearance to said requesting device that said media includes a large continuous defect-free address space, comprising: means for creating a list of defective physical addresses in the storage media; means for producing from said list of defective physical addresses a list of defect free logical addresses and a list of offset values; means for establishing a memory table which is traversable within a predetermined maximum number of steps including a plurality of elements corresponding to elements of a tree structure, said tree structure having a plurality of upper levels and a lower level; means for loading values corresponding to said list of defect free logical addresses into selected elements in said memory table corresponding to elements of said upper levels of said tree structure; and means for loading values corresponding to said offset values into selected elements in said memory table corresponding to elements of said lower level of said tree structure.
Claim 4
Dependent Claim
199 words
Apparatus for creating a tree structure for use in transforming logical addresses produced by a device requesting access to a storage media into defect free physical addresses corresponding to specific locations on said media within a predetermined maximum number of transformation steps, so as to create the appearance to said requesting device that said media includes a large continuous defect-free address space, comprising: means for creating a list of defective physical addresses in the storage media; means for producing from said list of defective physical addresses a list of defect free logical addresses and a list of offset values; means for establishing a memory table which is traversable within a predetermined maximum number of steps including a plurality of elements corresponding to elements of a tree structure, said tree structure having a plurality of upper levels and a lower level; means for loading values corresponding to said list of defect free logical addresses into selected elements in said memory table corresponding to elements of said upper levels of said tree structure; and means for loading values corresponding to said offset values into selected elements in said memory table corresponding to elements of said lower level of said tree structure.
Claim 5
Independent Claim
176 words
A method for creating a tree structure for use in transforming logical addresses produced by a device requesting access to a storage media into defect free physical addresses within a predetermined maximum number of transformation steps, so as to create the appearance to said requesting device that said media includes a large continuous defect-free address space, comprising the steps of: creating a list of defective physical addresses in the storage media; producing from said list of defective physical addresses a list of defect free logical addresses and a list of predetermined offset values; establishing a memory table having a plurality of elements corresponding to elements of a tree structure, said tree structure having a plurality of upper levels and a lower level; loading values corresponding to said defect free logical addresses into selected elements in said memory table corresponding to elements of said upper levels of said tree structure; and loading values corresponding to said predetermined offset values into selected elements in said memory table corresponding to elements of said lower level of said tree structure.
Claim 6
Independent Claim
176 words
A method for creating a tree structure for use in transforming logical addresses produced by a device requesting access to a storage media into defect free physical addresses within a predetermined maximum number of transformation steps, so as to create the appearance to said requesting device that said media includes a large continuous defect-free address space, comprising the steps of: creating a list of defective physical addresses in the storage media; producing from said list of defective physical addresses a list of defect free logical addresses and a list of predetermined offset values; establishing a memory table having a plurality of elements corresponding to elements of a tree structure, said tree structure having a plurality of upper levels and a lower level; loading values corresponding to said defect free logical addresses into selected elements in said memory table corresponding to elements of said upper levels of said tree structure; and loading values corresponding to said predetermined offset values into selected elements in said memory table corresponding to elements of said lower level of said tree structure.
Claim 7
Independent Claim
238 words
A method for transforming logical addresses produced by a device requesting access to storage media having a specified access time into defect free physical addresses from a list of defective physical addresses, so as to create the appearance to said requesting device that the storage media includes a large continuous defect-free address space comprising the steps of: generating from a list of defective physical addresses, a list of defect free logical addresses and a list of corresponding predetermined offset values to be added to a requested logical address; storing said list of defect free logical addresses and said list of corresponding predetermined offset values in a memory table in a predetermined manner such that said memory table is capable of being traversed within a predetermined maximum number of steps, said memory table having a plurality of elements corresponding to elements in a tree structure, said tree structure having a plurality of upper levels and a lower level; receiving a logical address from said requesting device; traversing selected elements in said memory table corresponding to elements of said upper tree levels in response to said received logical address, to arrive at a selected element in said table containing one of said predetermined offset values; and adding said one of said predetermined offset values to said logical address produced by said requesting device to produce a defect free physical address corresponding to a location on said storage media for access.
Claim 8
Independent Claim
238 words
A method for transforming logical addresses produced by a device requesting access to storage media having a specified access time into defect free physical addresses from a list of defective physical addresses, so as to create the appearance to said requesting device that the storage media includes a large continuous defect-free address space comprising the steps of: generating from a list of defective physical addresses, a list of defect free logical addresses and a list of corresponding predetermined offset values to be added to a requested logical address; storing said list of defect free logical addresses and said list of corresponding predetermined offset values in a memory table in a predetermined manner such that said memory table is capable of being traversed within a predetermined maximum number of steps, said memory table having a plurality of elements corresponding to elements in a tree structure, said tree structure having a plurality of upper levels and a lower level; receiving a logical address from said requesting device; traversing selected elements in said memory table corresponding to elements of said upper tree levels in response to said received logical address, to arrive at a selected element in said table containing one of said predetermined offset values; and adding said one of said predetermined offset values to said logical address produced by said requesting device to produce a defect free physical address corresponding to a location on said storage media for access.
Claim 9
Dependent Claim
21 words
The method of claim 4 wherein said receiving, traversing and adding steps occur within the access time of said storage media.
Claim 10
Dependent Claim
62 words
The method of claim 4 wherein said storage step includes the steps of: storing values corresponding to said defect free logical addresses in selected locations of said memory table corresponding to upper levels of said tree structure; and storing values corresponding to said predetermined offset values in selected locations of said memory table corresponding to the lower level of said tree structure.
Claim 11
Dependent Claim
52 words
The method of claim 4 wherein said receiving step includes the step of loading said logical address in a memory register and wherein said adding step includes the step of adding said one of said predetermined offset values to said logical address stored in said memory register to produce said physical address.
Claim 12
Dependent Claim
66 words
The method of claim 4 wherein said traversing step includes the step of comparing each logical address produced by said requesting device to defect free logical addresses stored values at selected locations in said memory table corresponding to said upper tree levels employing a microprocessor to produce a comparison output indication and branching to the next successive tree level based upon the respective comparison output indication.
Claim 13
Dependent Claim
48 words
The method of claim 4 further including prior to said storing step the step of generating a list of defective physical addresses including the step of reading information corresponding to the physical addresses of defective locations on said storage media from a predetermined area on said storage media.
Claim 14
Dependent Claim
33 words
The method of claim 9 further including step of reading the addresses of locations corresponding to additional defective physical addresses on said storage media in addition to said addresses identified on said media.
Claim 15
Dependent Claim
51 words
The method of claim 10 further including the step of sorting the addresses identified on said media corresponding to defective physical addresses and said addresses not identified on said media corresponding to additional defective physical addresses to produce a sorted list of addresses corresponding to defective physical addresses on said media.
Claim 16
Dependent Claim
30 words
The method of claim 11 further including the step of processing said sorted list to produce said list of defect free logical addresses and said list of predetermined offset values.
Claim 17
Independent Claim
231 words
An apparatus for transforming logical addresses produced by a device requesting access to a storage media into defect free physical addresses corresponding to specific defect free locations on said media, so as to create the appearance to said requesting device that said media includes a large, continuous, defect free logical address space comprising: means for generating a list of defective physical addresses in the storage media; means for generating, from said list of defective physical addresses, a list of defect free logical addresses each of which corresponds to the first address of at least one defect free logical address sequence which is accessible by said requesting device, and for also generating a list of corresponding offset values to be added to a requested logical address to produce a modified logical address which corresponds to a defect free physical address; means for comparing said requested logical address with selected addresses from among said list of defect free logical addresses; and means for ordering said list of defect free physical addresses and said list of corresponding offset values into an addressable memory array having a predetermined structure wherein said requested logical address may be compared to selected addresses from among said list of defect free logical addresses to arrive at a corresponding offset value, within a predetermined maximum number of comparisons, to transform said requested logical address into a defect free physical address.
Claim 18
Independent Claim
231 words
An apparatus for transforming logical addresses produced by a device requesting access to a storage media into defect free physical addresses corresponding to specific defect free locations on said media, so as to create the appearance to said requesting device that said media includes a large, continuous, defect free logical address space comprising: means for generating a list of defective physical addresses in the storage media; means for generating, from said list of defective physical addresses, a list of defect free logical addresses each of which corresponds to the first address of at least one defect free logical address sequence which is accessible by said requesting device, and for also generating a list of corresponding offset values to be added to a requested logical address to produce a modified logical address which corresponds to a defect free physical address; means for comparing said requested logical address with selected addresses from among said list of defect free logical addresses; and means for ordering said list of defect free physical addresses and said list of corresponding offset values into an addressable memory array having a predetermined structure wherein said requested logical address may be compared to selected addresses from among said list of defect free logical addresses to arrive at a corresponding offset value, within a predetermined maximum number of comparisons, to transform said requested logical address into a defect free physical address.
Claim 19
Dependent Claim
27 words
The apparatus of claim 13 wherein said predetermined structure includes a binary tree structure organized into a plurality of upper tree levels and a lower tree level.
Claim 20
Dependent Claim
41 words
The apparatus of claim 14 wherein said means for ordering orders said list of defect free logical addresses into said plurality of upper tree levels, and orders said corresponding offset values into the lower tree level of said binary tree structure.
Claim 21
Dependent Claim
36 words
The apparatus of claim 14 wherein said upper levels include a first tree level having one element and each successive level of said upper tree levels has twice the number of elements as the previous level.
Claim 22
Dependent Claim
55 words
The apparatus of claim 14 wherein said means for comparing includes means for comparing each logical address produced by the requesting device to said list of defect free logical addresses to produce comparison output indications, and means for branching to a selected element in the next tree level based upon each successive comparison output indication.
Claim 23
Dependent Claim
36 words
The apparatus of claim 17 wherein said means for branching to a selected element includes means for branching to one of two associated elements in the next tree level based upon the respective comparison output indication.
Claim 24
Dependent Claim
28 words
The apparatus of claim 14 wherein each element in the tree structure corresponds to a register in said memory table of a predetermined number of bytes in width.
Claim 25
Independent Claim
233 words
An apparatus for transforming logical addresses produced by a device requesting access to a storage media into defect free physical addresses corresponding to specific defect free locations on said media, so as to create the appearance to said requesting device that said media includes a large, continuous, defect free logical address space comprising: first processor apparatus operative for generating a list of defective physical addresses in the storage media; second processor apparatus operative for generating, from said list of defective physical addresses, a list of defect free logical addresses each of which corresponds to the first addresses of one or more sequential defect free logical addresses which is accessible by said requesting device, and for also generating a list of corresponding offset values to be added to a requested logical address to produce a modified logical address which corresponds to a defect free physical address; comparator apparatus for comparing said requested logical address with selected addresses from among said list of defect free logical addresses; and control apparatus operative for ordering said list of defect free logical addresses and said list of corresponding offset values into an addressable memory array having a predetermined structure wherein said requested logical address may be compared to selected addresses from among said list of defect free logical addresses to arrive at a corresponding offset value, to transform said requested logical address into a defect free physical address.
Claim 26
Independent Claim
233 words
An apparatus for transforming logical addresses produced by a device requesting access to a storage media into defect free physical addresses corresponding to specific defect free locations on said media, so as to create the appearance to said requesting device that said media includes a large, continuous, defect free logical address space comprising: first processor apparatus operative for generating a list of defective physical addresses in the storage media; second processor apparatus operative for generating, from said list of defective physical addresses, a list of defect free logical addresses each of which corresponds to the first addresses of one or more sequential defect free logical addresses which is accessible by said requesting device, and for also generating a list of corresponding offset values to be added to a requested logical address to produce a modified logical address which corresponds to a defect free physical address; comparator apparatus for comparing said requested logical address with selected addresses from among said list of defect free logical addresses; and control apparatus operative for ordering said list of defect free logical addresses and said list of corresponding offset values into an addressable memory array having a predetermined structure wherein said requested logical address may be compared to selected addresses from among said list of defect free logical addresses to arrive at a corresponding offset value, to transform said requested logical address into a defect free physical address.
References Cited (Backward Citations)
US4086628A
Cited
US4020466A
Cited
US4241420A
Cited
US4434487A
Cited
US4479214A
Cited
US4498146A
Cited
US4656532A
Cited
US4746998A
Cited
US4868789A
Cited
US4805048A
Cited
US4811124A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1995-09-08 | 1996-03-09 | 1996-09-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1999-09-08 | 2000-03-09 | 2000-09-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2003-09-08 | 2004-03-09 | 2004-09-08 | $7700.00 | Window Closed / Lapsed |