CACHE FLUSHING UTILIZING LINKED LISTS

摘要

Methods and structure for utilizing linked lists to flush a cache. One exemplary embodiment includes a memory, an interface, and an Input/Output (I/O) processor. The memory implements a cache divided into cache lines, and the interface receives I/O directed to a block address of a storage device. The I/O processor determines a remainder by dividing the block address by the number of cache lines, and selects a cache line for storing the I/O based on the remainder. The I/O processor determines a quotient by dividing the block address by the number of cache lines, and associates the quotient with the selected cache line. Additionally, the I/O processor populates a linked list by inserting entries that each point to a different cache line associated with the same quotient, and flushes the cache lines to the storage device in block address order by traversing the entries of the linked list.

主权项

1. A system comprising:
a memory implementing a cache divided into multiple cache lines; an interface operable to receive Input/Output (I/O) directed to a block address of a storage device; and an I/O processor operable to determine a remainder by dividing the block address by the number of cache lines, and to select a cache line for storing the I/O based on the remainder, the I/O processor further operable to determine a quotient by dividing the block address by the number of cache lines, and to associate the quotient with the selected cache line, the I/O processor further operable to populate a linked list by inserting entries into the linked list that each point to a different cache line associated with the same quotient, and to flush the cache lines to the storage device in block address order by traversing the entries of the linked list.