Importance

Loading Importance Indicators...

Abstract

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.

Loading the Abstract Image...

First Claim