# US 10,740,028 B1 · Methods and apparatus for LRU buffer management in performing parallel IO operations

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,740,028 B1
- Document ID: US10740028B1
- Status: Granted
- Kind: B1
- Application number: 15/690,807
- Filed: 2017-08-30
- Granted: 2020-08-11
- Earliest claimed: 2017-08-30
- Assignees: DataCore Software Corporation
- Applicants: DataCore Software Corporation
- Inventors: Ziya Aral; Nicholas C. Connolly; Robert Bassett; Roni J. Putra
- Web page: https://patentgrep.com/patent/US10740028B1

## CPC

- G06F 3/0656: {Data buffering arrangements}
- G06F 3/0613: {in relation to throughput}
- G06F 3/0659: {Command handling arrangements, e.g. command buffers, queues, command scheduling}
- G06F 3/0664: {at device level, e.g. emulation of a storage device or system}
- G06F 3/067: {Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

An LRU buffer configuration for performing parallel IO operations is disclosed. In one example, the LRU buffer configuration is a doubly linked list of segments. Each segment is also a doubly linked list of buffers. The LRU buffer configuration includes a head portion and a tail portion, each including several slots (pointers to segments) respectively accessible in parallel by a number of CPUs in a multicore platform. Thus, for example, a free buffer may be obtained for a calling application on a given CPU by selecting a head slot corresponding to the given CPU, identifying the segment pointed to by the selected head slot, locking that segment, and removing the buffer from the list of buffers in that segment. Buffers may similarly be returned according to slots and corresponding segments and buffers at the tail portion.

## Claims

### Claim 1

A method for LRU buffer management in performing parallel IO operations, the method comprising:
requesting a free buffer from a single LRU buffer list in response to an IO request, the single LRU buffer list including a head portion, the head portion including a plurality of head slots respectively accessible in parallel;
selecting a first head slot from the plurality of head slots included in the head portion of the single LRU buffer list; and
obtaining the free buffer from the first head slot.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
identifying a first segment corresponding to the first head slot, the first segment including a list of buffers;
obtaining the free buffer from the first head slot by identifying a head buffer within the list of buffers included in the first segment and removing the head buffer as the free buffer.

### Claim 3 (depends on 1)

The method of claim 1, wherein the single LRU buffer list is accessible in parallel by a plurality of CPUs that are included on a multicore platform, the plurality of CPUs being respectively associated with the plurality of head slots, such that a first CPU is associated to the first head slot, a second CPU is associated to a second head slot, through a number N of CPUs and N corresponding head slots.

### Claim 4 (depends on 3)

The method of claim 3, wherein the single LRU buffer list includes a tail portion, the tail portion including a plurality of tail slots respectively accessible in parallel.

### Claim 5 (depends on 4)

The method of claim 4, further comprising:
returning the free buffer to the single LRU buffer list at a first tail slot of the plurality of tail slots, the first tail slot being associated with the first CPU.

### Claim 6 (depends on 5)

The method of claim 5, further comprising:
identifying a second segment corresponding to the first tail slot, the second segment including a list of buffers;
returning the free buffer at the first tail slot by pushing the free buffer to a tail of the list of buffers in the second segment.

### Claim 7

A non-transitory computer readable medium storing program code for performing parallel IO operations, the program code being executable to perform operations comprising:
requesting a free buffer from a single LRU buffer list in response to an IO request, the single LRU buffer list including a head portion, the head portion including a plurality of head slots respectively accessible in parallel;
selecting a first head slot from the plurality of head slots included in the head portion of the single LRU buffer list; and
obtaining the free buffer from the first head slot.

### Claim 8 (depends on 7)

The computer readable medium of claim 7, wherein the operations further comprise:
identifying a first segment corresponding to the first head slot, the first segment including a list of buffers;
obtaining the free buffer from the first head slot by identifying a head buffer within the list of buffers included in the first segment and removing the head buffer as the free buffer.

### Claim 9 (depends on 7)

The computer readable medium of claim 7, wherein the single LRU buffer list is accessible in parallel by a plurality of CPUs that are included on a multicore platform, the plurality of CPUs being respectively associated with the plurality of head slots, such that a first CPU is associated to the first head slot, a second CPU is associated to a second head slot, through a number N of CPUs and N corresponding head slots.

### Claim 10 (depends on 9)

The computer readable medium of claim 9, wherein the single LRU buffer list includes a tail portion, the tail portion including a plurality of tail slots respectively accessible in parallel.

### Claim 11 (depends on 10)

The computer readable medium of claim 10, wherein the operations further comprise:
returning the free buffer to the single LRU buffer list at a first tail slot of the plurality of tail slots, the first tail slot being associated with the first CPU.

### Claim 12 (depends on 11)

The computer readable medium of claim 11, wherein the operations further comprise:
identifying a second segment corresponding to the first tail slot, the second segment including a list of buffers;
returning the free buffer at the first tail slot by pushing the free buffer to a tail of the list of buffers in the second segment.

### Claim 13

An apparatus for LRU buffer management in performing parallel IO operations, the apparatus comprising:
a processor; and
a memory, the memory storing program code executable by the processor to perform operations comprising:
requesting a free buffer from a single LRU buffer list in response to an IO request, the single LRU buffer list including a head portion, the head portion including a plurality of head slots respectively accessible in parallel;
selecting a first head slot from the plurality of head slots included in the head portion of the single LRU buffer list; and
obtaining the free buffer from the first head slot.

### Claim 14 (depends on 13)

The apparatus of claim 13, wherein the operations further comprise:
identifying a first segment corresponding to the first head slot, the first segment including a list of buffers;
obtaining the free buffer from the first head slot by identifying a head buffer within the list of buffers included in the first segment and removing the head buffer as the free buffer.

### Claim 15 (depends on 13)

The apparatus of claim 13, wherein the single LRU buffer list is accessible in parallel by a plurality of CPUs that are included on a multicore platform, the plurality of CPUs being respectively associated with the plurality of head slots, such that a first CPU is associated to the first head slot, a second CPU is associated to a second head slot, through a number N of CPUs and N corresponding head slots.

### Claim 16 (depends on 15)

The apparatus of claim 15, wherein the single LRU buffer list includes a tail portion, the tail portion including a plurality of tail slots respectively accessible in parallel.

### Claim 17 (depends on 16)

The apparatus of claim 16, wherein the operations further comprise:
returning the free buffer to the single LRU buffer list at a first tail slot of the plurality of tail slots, the first tail slot being associated with the first CPU.

### Claim 18 (depends on 17)

The apparatus of claim 17, wherein the operations further comprise:
identifying a second segment corresponding to the first tail slot, the second segment including a list of buffers;
returning the free buffer at the first tail slot by pushing the free buffer to a tail of the list of buffers in the second segment.