# US 2020/0265091 A1 · Scalable Range Locks

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

- Number: US 2020/0265091 A1
- Document ID: US20200265091A1
- Status: Published application
- Kind: A1
- Application number: 16/407,007
- Filed: 2019-05-08
- Published: 2020-08-20
- Earliest claimed: 2019-02-15
- Assignees: Oracle International Corporation
- Applicants: Oracle International Corporation
- Inventors: Alex Kogan; David Dice; Shady Alaaeldin Mohamed Abdelkader Rabie Issa
- Web page: https://patentgrep.com/patent/US20200265091A1

## CPC

- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06F 11/3006: {where the computing system is distributed, e.g. networked systems, clusters, multiprocessor systems (multiprogramming arrangements G06F9/46; allocation of resources G06F9/50)}
- G06F 16/1774: {Locking methods, e.g. locking methods for file systems allowing shared and concurrent access to files}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A computer comprising one or more processors and memory may implement multiple threads performing mutually exclusive lock acquisition operations on disjoint ranges of a shared resource each using atomic compare and swap (CAS) operations. A linked list of currently locked ranges is maintained and, upon entry to a lock acquisition operation, a thread waits for all locked ranges overlapping the desired range to be released then inserts a descriptor for the desired range into the linked list using a single CAS operation. To release a locked range, a thread executes a single fetch and add (FAA) operation. The operation may be extended to support simultaneous exclusive and non-exclusive access by allowing overlapping ranges to be locked for non-exclusive access and by performing an additional validation after locking to provide conflict resolution should a conflict be detected.

## Claims

### Claim 1

A method, comprising:
performing, by a computer comprising one or more processors and memory implementing a plurality of threads, a lock acquisition operation on a first range of elements of a shared resource, comprising:
verifying that no currently locked ranges of elements of the shared resource overlap the first range, comprising:
scanning a linked list of descriptors of currently locked ranges to identify locked ranges of elements overlapping the first range, wherein the descriptors for the currently locked ranges each comprise a link to a next descriptor; and
waiting for each of the identified overlapping locked ranges of elements to be released; and
executing, subsequent to the verifying, an atomic operation to insert a descriptor for the first range into the linked list of descriptors of currently locked ranges to acquire a lock of the first range of elements of the shared resource, wherein the atomic operation comprises determining that no ranges overlapping the first range have been added to the linked list of descriptors;
wherein the lock acquisition operation executes on a particular thread of the plurality of threads, and wherein the performing of the lock acquisition operation does not exclude access to the linked list of descriptors by other threads of the plurality of threads.

### Claim 2 (depends on 1)

The method of claim 1, wherein the atomic operation comprises performing an atomic compare and swap operation on the link to a next descriptor of a descriptor of a currently locked range.

### Claim 3 (depends on 1)

The method of claim 1, wherein the lock acquisition operation on the first range of elements acquires a non-exclusive lock, wherein the descriptor for the first range comprises an indicator of a non-exclusive lock, and wherein the identified locked ranges of elements overlapping the first range exclude currently locked ranges comprising respective descriptors indicating non-exclusive locks.

### Claim 4 (depends on 3)

The method of claim 3, the performing of the lock acquisition operation on the first range of elements further comprising:
verifying, subsequent to the inserting, that no currently locked ranges comprising respective descriptors indicating an exclusive lock overlap the first range, comprising:
scanning the linked list of descriptors of currently locked ranges comprising respective descriptors indicating exclusive locks to identify locked ranges of elements overlapping the first range; and
waiting for each of the identified overlapping exclusively locked ranges of elements to be released.

### Claim 5 (depends on 1)

The method of claim 1, further comprising:
performing, by the computer, a release operation on a particular currently locked range of elements of a shared resource, comprising:
performing, on a descriptor of the particular currently locked range, an atomic fetch and add operation on the link to the next descriptor to update a particular bit of the next descriptor to indicate the particular currently locked range has been released.

### Claim 6 (depends on 1)

The method of claim 1, further comprising:
performing, by the computer, a lock acquisition operation on a second range of elements of a shared resource, comprising:
determining that a head pointer for the linked list of descriptors indicates that the linked list is empty; and
inserting a descriptor for the second range into the empty linked list of descriptors to lock the second range of elements of the shared resource via a fast insertion, comprising:
writing the head pointer to the address of the descriptor for the second range; and
setting an indicator of fast insertion for the linked list of descriptors.

### Claim 7 (depends on 6)

The method of claim 6, the performing of the lock acquisition operation on the first range of elements further comprising clearing the indicator of fast insertion for the linked list of descriptors.

### Claim 8

One or more non-transitory computer-accessible storage media storing program instructions that when executed on or across one or more processors implementing a plurality of threads cause the one or more processors to perform a lock acquisition operation on a first range of elements of a shared resource, comprising:
verifying that no currently locked ranges of elements of the shared resource overlap the first range, comprising:
scanning a linked list of descriptors of currently locked ranges to identify locked ranges of elements overlapping the first range, wherein the descriptors for the currently locked ranges each comprise a link to a next descriptor; and
waiting for each of the identified overlapping locked ranges of elements to be released; and
executing, subsequent to the verifying, an atomic operation to insert a descriptor for the first range into the linked list of descriptors of currently locked ranges to acquire a lock of the first range of elements of the shared resource, wherein the atomic operation comprises determining that no ranges overlapping the first range have been added to the linked list of descriptors;
wherein the lock acquisition operation executes on a particular thread of the plurality of threads, and wherein the performing of the lock acquisition operation does not exclude access to the linked list of descriptors by other threads of the plurality of threads.

### Claim 9 (depends on 8)

The one or more non-transitory computer-accessible storage media of claim 8, wherein the atomic operation comprises performing an atomic compare and swap operation on the link to a next descriptor of a descriptor of a currently locked range.

### Claim 10 (depends on 8)

The one or more non-transitory computer-accessible storage media of claim 8, wherein the lock acquisition operation on the first range of elements acquires a non-exclusive lock, wherein the descriptor for the first range comprises an indicator of a non-exclusive lock, and wherein the identified locked ranges of elements overlapping the first range exclude currently locked ranges comprising respective descriptors indicating non-exclusive locks.

### Claim 11 (depends on 10)

The one or more non-transitory computer-accessible storage media of claim 10, the performing of the lock acquisition operation on the first range of elements further comprising:
verifying, subsequent to the inserting, that no currently locked ranges comprising respective descriptors indicating exclusive locks overlap the first range, comprising:
scanning the linked list of descriptors of currently locked ranges comprising respective descriptors indicating exclusive locks to identify locked ranges of elements overlapping the first range; and
waiting for each of the identified overlapping exclusively locked ranges of elements to be released.

### Claim 12 (depends on 8)

The one or more non-transitory computer-accessible storage media of claim 8 further storing program instructions that when executed on or across one or more processors cause the one or more processors to perform a release operation on a particular currently locked range of elements of a shared resource, comprising:
performing, on a descriptor of the particular currently locked range, an atomic fetch and add operation on the link to the next descriptor to update a particular bit of the next descriptor to indicate the particular currently locked range has been released.

### Claim 13 (depends on 8)

The one or more non-transitory computer-accessible storage media of claim 8 further storing program instructions that when executed on or across one or more processors cause the one or more processors to perform a second lock acquisition operation on a second range of elements of a shared resource, comprising:
determining that a head pointer for the linked list of descriptors indicates that the linked list is empty; and
inserting a descriptor for the second range into the empty linked list of descriptors to lock the second range of elements of the shared resource via a fast insertion, comprising:
writing the head pointer to the address of the descriptor for the second range; and
setting an indicator of fast insertion for the linked list of descriptors.

### Claim 14 (depends on 13)

The one or more non-transitory computer-accessible storage media of claim 13, the performing of the lock acquisition operation on the first range of elements further comprising clearing the indicator of fast insertion for the linked list of descriptors.

### Claim 15

A system, comprising:
one or more processors implementing a plurality of threads and a memory, the memory comprising program instructions executable by the one or more processors to perform a lock acquisition operation on a first range of elements of a shared resource, the lock acquisition operation on the first range of elements configured to:
scan a linked list of descriptors of currently locked ranges to identify locked ranges of elements overlapping the first range, wherein the descriptors for the currently locked ranges each comprise a link to a next descriptor;
wait for each of the identified overlapping locked ranges of elements to be released; and
execute, subsequent to waiting for each of the identified overlapping locked ranges of elements to be released, an atomic operation to insert a descriptor for the first range into the linked list of descriptors of currently locked ranges to lock the first range of elements of the shared resource, wherein the atomic operation comprises determining that no ranges overlapping the first range have been added to the linked list of descriptors;
wherein the lock acquisition operation executes on a particular thread of the plurality of threads, and wherein the performing of the lock acquisition operation does not exclude access to the linked list of descriptors by other threads of the plurality of threads.

### Claim 16 (depends on 15)

The system of claim 15, wherein the atomic operation comprises an atomic compare and swap operation on the link to a next descriptor of a descriptor of a currently locked range.

### Claim 17 (depends on 15)

The system of claim 15, wherein the lock acquisition operation on the first range of elements acquires a non-exclusive lock, wherein the descriptor for the first range comprises an indicator of a non-exclusive lock, and wherein the identified locked ranges of elements overlapping the first range exclude currently locked ranges comprising respective descriptors indicating non-exclusive locks.

### Claim 18 (depends on 15)

The system of claim 15, the lock acquisition operation on the first range of elements further configured to:
scan the linked list of descriptors of currently locked ranges comprising respective descriptors indicating exclusive locks to identify locked ranges of elements overlapping the first range; and
wait for each of the identified overlapping exclusively locked ranges of elements to be released.

### Claim 19 (depends on 19)

The system of claim 19, the memory further comprising program instructions executable by the one or more processors to perform a release operation on a particular currently locked range of elements of a shared resource, the release operation configured to:
perform, on a descriptor of the particular currently locked range, an atomic fetch and add operation on the link to the next descriptor to update a particular bit of the next descriptor to indicate the particular currently locked range has been released.

### Claim 20 (depends on 15)

The system of claim 15, the memory further comprising program instructions executable by the one or more processors to perform a lock acquisition operation on a second range of elements of a shared resource, the lock acquisition operation on the second range of elements configured to:
determine that a head pointer for the linked list of descriptors indicates that the linked list is empty; and
insert a descriptor for the second range into the empty linked list of descriptors to lock the second range of elements of the shared resource via a fast insertion, wherein to insert the descriptor the lock acquisition operation on the second range of elements configured to:
write the head pointer to the address of the descriptor for the second range; and
set an indicator of fast insertion for the linked list of descriptors.
