Cluster-based cache memory allocation

• US 6,606,682 B1
• Filed: 04/19/2000
• Issued: 08/12/2003
• Est. Priority Date: 04/19/2000
• Status: Expired due to Fees

• Current Assignee: Western Digital Corporation
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: Wilkins, Virgil V., Castro, Ralph H., Dang, Quoc N., Ng, Tsun Y.
• Primary Examiner(s): Sparks, Donald
• Assistant Examiner(s): Peugh, Brian R.
• Application Number:
  US09/552,407
• Time in Patent Office: 1,210 Days
• Field of Search: 711/113, 711/118, 711/202, 710/22
• US Class Current: 711/113
• CPC Class Codes: G06F 12/0873 Mapping of cache memory to specific storage devices or parts thereof
• CPC Class Codes: G06F 2212/312 In storage controller
• CPC Class Codes: G06F 2212/313 In storage device

Abstract

The present invention relates to a disk drive including a cache memory having a plurality of sequentially-ordered memory clusters for caching disk data stored in sectors (not shown) on disks of a disk assembly. The disk sectors are identified by logical block addresses (LBAs). A cache control system of the disk drive comprises a cluster control block memory, having a plurality of cluster control blocks (CCB), and a tag memory 22, having a plurality of tag records, that are embedded within the cache control system. Each CCB includes a cluster segment record with an entry for associating the CCB with a particular memory cluster and for forming variable length segments of the memory clusters without regard to the sequential order of the memory clusters. Each tag record assigns a segment to a continuous range of LBAs and defines the CCBs forming the segment. Each segment of the memory clusters is for caching data from a contiguous range of the logical block addresses.

Claims

1. A disk drive, comprising:

a cache memory having a plurality of sequentially-ordered memory clusters for caching disk data of disk sectors identified by logical block addresses; and

a cache control system having

a plurality of cluster control blocks, each cluster control block having a cluster segment record for associating the cluster control block with a particular memory cluster and for forming variable length segments of the memory clusters without regard to the sequential order of the memory clusters;

a tag memory having a plurality of tag records, each tag record for assigning a segment to a contiguous range of logical block addesses and for defining the cluster control blocks forming the segment, each tag record defining a length for the assigned segment by pointing to a first cluster control block and to a last cluster control block for the segment, and each segment of the memory clusters for caching disk data of the assigned contiguous rge of logical block addresses.

2. A disk drive, comprising:

a cache memory having a plurality of sequentially-ordered memory clusters for caching disk data of disk sectors identified by logical block adresses; and

a cache control system having

a plurality of cluster control blocks, each cluster control block having a cluster segment record for associating the cluster control block with a particular memory cluster and for forming variable length segments of the memory clusters without regard to the sequential order of the memory clusters;

a tag memory having a plurality of tag records, each tag record for assigning a segment to a contiguous range of logical block addresses and for defining the cluster control blocks forming the segment, each tag record defining a length for the assigned segmient by pointing to a first cluster control block and indicating a count of cluster control blocks for the segment, and each segment of the memory clusters for caching disk data of the assigned contiguous range of logical block addresses.

3. A disk drive, comprising:

a cache memory having a plurality of sequentially-ordered memory clusters for caching disk data of disk sectors identified by logical block addresses;

a cache control system having

a plurality of cluster control blocks, each cluster control block having a cluster segment record for associating the cluster control block with a particular memory cluster and for forming variable length segments of the memory clusters without regard to the sequential order of the memory clusters;

a tag memory having a plurality of tag records, each tag record for assigning a segment to a contiguous range of logical block adresses and for defining the cluster control blocks forming the segment, and each segment of the memory clusters for caching disk data of the assigned contiguous range of logical block addresses; and

a free list for identifying cluster control blocks not associated with a tag memory record and forming a segment of the identified cluster control blocks, wherein each tag record for an assigned segment points to a first cluster control block, a last cluster control block and indicates a count of the disk sectors cached for the segment, and wherein a length of an original assigned segment may be increased by removing a segment of cluster control blocks from the free list segment, changing the orginal segment'"'"'s last cluster control block to point to a first cluster control block of the removed segment, and changing the tag record to point to the last cluster control block of the removed segment.

4. A cache control system for caching disk data of disk sectors identified by logical block addresses using a cache memory having a plurality of sequentially-ordered memory clusters, comprising:

a plurality of cluster control blocks, each cluster control block having a cluster segment record for associating the cluster control block with a particular memory cluster and for forming variable length segments of the memory clusters without regard to the sequential order of the memory clusters; and

a tag memory having a pluality of tag records, each tag record for assignug a segment to a contiguous range of logical block addresses and for defining the cluster control blocks forming the segment, each tag record defining a length for the assigned segment by pointing to a first cluster control block and to a last cluster control block for the segment, and each segment of the memory clusters for caching disk data of the assigned contiguous range of logical block addresses.

5. A cache control sysem for caching disk data of disk sectors identified by logical block addresses using a cache memory having a plurality of sequentially-ordered memory clusters, comprising:

a plurality of cluster control blocks, each cluster control block haning a cluster segment record for associating the cluster control block with a particular memory cluster and for forming variable length segments of the memory clusters without regard to the sequential order of the memory clusters; and

a tag memory having a plurality of tag records, each tag record for assigning a segment to a contiguous range of logical block addresses and for defining the cluster control blocks forming the segment, each tag record defining a length for the assigned segment by pointing to a first cluster control block and indicating a count of cluster control blocks for the segment, and each segment of the memory clusters for caching disk data of the assigned contiguous range of logical block addresses.

6. A cache control sim for caching disk data of disk sectors identified by logical block addresses using a cache memory having a plurality of seqmentially-ordered memory clusters, comprising:

a plurality of cluster control blocks, each cluster control block having a cluster segment record for associating the cluster control block with a particular memory cluster and for forming variable length segments of the memory clusters without regard to the sequential order of the memory clusters;

a tag memory having a plurality of tag records, each tag record for assigning a segment to a contiguous range of logical block addresses and for defining the cluster control blocks forming the segment, and each segment of the memory clusters for caching disk data of the assigned contiguous range of logical block addresses; and

a free list for identifying cluster control blocks not associated with a tag memory record and forming a segment of the identified cluster control blocks, wherein each tag record for an assigned segment points to a first cluster control block, a last cluster control block, and wherein a length of an original assigned segment may be increased by removing a segment of cluster control blocks from the free list segment, changing the original segment'"'"'s last cluster control block to point to a first cluster control block of the removed scgment, and changing the tag record to point to the last cluster contol block of the removed segment.