Cluster-based cache memory allocation

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.

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.

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.