# US 2016/0259663 A1 · System and Method for Implementing Reader-Writer Locks Using Hardware Transactional Memory

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

- Number: US 2016/0259663 A1
- Document ID: US20160259663A1
- Status: Published application
- Kind: A1
- Application number: 15/156,110
- Filed: 2016-05-16
- Published: 2016-09-08
- Earliest claimed: 2013-03-05
- Assignees: Oracle International Corporation
- Applicants: Oracle International Corporation
- Inventors: David Dice; Yosef Lev; Yujie Liu; Victor M. Luchangco; Mark S. Moir
- Web page: https://patentgrep.com/patent/US20160259663A1

## CPC

- G06F 9/467: {Transactional memory (G06F9/528 takes precedence)}
- G06F 9/5027: {the resource being a machine, e.g. CPUs, Servers, Terminals}
- G06F 9/528: {by using speculative mechanisms}
- G06F 2209/523: Mode
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Transactional reader-writer locks may leverage available hardware transactional memory (HTM) to simplify the procedures of the reader-writer lock algorithm and to eliminate a requirement for type stable memory An HTM-based reader-writer lock may include an ordered list of client-provided nodes, each of which represents a thread that holds (or desires to acquire) the lock, and a tail pointer. The locking and unlocking procedures invoked by readers and writers may access the tail pointer or particular ones of the nodes in the list using various combinations of transactions and non-transactional accesses to insert nodes into the list or to remove nodes from the list. A reader or writer that owns a node at the head of the list (or a reader whose node is preceded in the list only by other readers' nodes) may access a critical section of code or shared resource.

## Claims

### Claim 1

A method, comprising:
performing by a computer:
beginning execution of a multithreaded application that comprises one or more requests to acquire a shared reader-writer lock, wherein the shared reader-writer lock comprises a tail pointer and an ordered list of zero or more nodes, wherein the shared reader-writer lock controls access to a critical section of code or a shared resource by concurrently executing threads of the application;
a given thread of the application inserting a node in the ordered list of nodes, wherein each node in the ordered list of nodes is owned by a respective thread that holds the shared reader-writer lock or that desires access to the critical section of code or shared resource in a read-only mode or in a write mode, and wherein only one thread can hold the shared reader-writer lock in a write mode at a time;
subsequent to said inserting, the given thread acquiring the shared reader-writer lock in a read-only mode or in a write mode;
subsequent to said acquiring, the given thread releasing the shared reader-writer lock, wherein said releasing comprises removing the inserted node from the ordered list of nodes;
wherein at least one of said inserting or said releasing comprises updating a value of the tail pointer within a hardware transaction or modifying a field of at least one node in the ordered list of nodes within a hardware transaction.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
subsequent to said removing the inserted node, freeing memory that was allocated to the inserted node.

### Claim 3 (depends on 1)

The method of claim 1, wherein said inserting comprises updating the value of the tail pointer to indicate that the inserted node is the last node in the ordered list of nodes.

### Claim 4 (depends on 3)

The method of claim 3,
wherein said updating the value of the tail pointer to indicate that the inserted node is the last node in the ordered list of nodes is performed within a hardware transaction; and
wherein said inserting further comprises:
prior to updating the value of the tail pointer to indicate that the inserted node is the last node in the ordered list of nodes within the hardware transaction, updating the value of the tail pointer to a pre-determined value indicating an intent to acquire the shared reader-writer lock using a non-transactional atomic operation.

### Claim 5 (depends on 1)

The method of claim 1, wherein said releasing comprises:
determining whether another node succeeds the inserted node in the ordered list of nodes; and
updating the value of the tail pointer to identify another node as the last node in the ordered list of nodes or to indicate that no other node succeeds the inserted node in the ordered list of nodes, dependent on said determining.

### Claim 6 (depends on 1)

The method of claim 1, wherein said inserting comprises:
determining whether another node precedes the inserted node in the ordered list of nodes; and
in response to determining that another node precedes the inserted node in the ordered list of nodes, writing a value to a previous-node field of the inserted node indicating that the other node precedes the inserted node in the ordered list of nodes.

### Claim 7 (depends on 1)

The method of claim 1, wherein said inserting further comprises:
initializing, using one or more non-transactional write operations, one or more of: a state field value for the inserted node, a spin field value for the inserted node, or a next-node field value for the inserted node;
wherein the state field value indicates whether the given thread has acquired or desires to acquire the shared reader-writer lock in a read-only mode or in a write mode;
wherein the next-node field value indicates which, if any, node succeeds the inserted node in the ordered list of nodes; and
wherein the spin field value indicates whether the given thread must wait to acquire the shared reader-writer lock.

### Claim 8 (depends on 7)

The method of claim 7, wherein at least one of said inserting or said releasing comprises reading the spin field value for the inserted node using one or more non-transactional read operations or resetting a spin field value for a node that succeeds the inserted node using a non-transactional write operation.

### Claim 9 (depends on 1)

The method of claim 1, wherein said releasing comprises:
determining whether another node succeeds the inserted node in the ordered list of nodes; and
in response to determining no other node succeeds the inserted node in the ordered list of nodes:
determining whether the value of the tail pointer indicates the inserted node; and
in response to determining that the value of the tail pointer indicates the inserted node, setting the value of the tail pointer to a null value;
wherein said determining whether the value of the tail pointer indicates the inserted node and said setting the value of the tail pointer to a null value are performed non-transactionally using a compare-and-swap type operation.

### Claim 10

A system, comprising:
one or more processor cores; and
a memory coupled to the one or more processor cores and storing program instructions that when executed on the one or more processor cores cause the one or more processor cores to perform:
beginning execution of a multithreaded application that comprises one or more requests to acquire a shared reader-writer lock, wherein the shared reader-writer lock comprises a tail pointer and an ordered list of zero or more nodes, wherein the shared reader-writer lock controls access to a critical section of code or a shared resource by concurrently executing threads of the application;
a given thread of the application inserting a node in the ordered list of nodes, wherein each node in the ordered list of nodes is owned by a respective thread that holds the shared reader-writer lock or that desires access to the critical section of code or shared resource in a read-only mode or in a write mode, and wherein only one thread can hold the shared reader-writer lock in a write mode at a time;
subsequent to said inserting, the given thread acquiring the shared reader-writer lock in a read-only mode or in a write mode;
subsequent to said acquiring, the given thread releasing the shared reader-writer lock, wherein said releasing comprises removing the inserted node from the ordered list of nodes;
wherein at least one of said inserting or said releasing comprises updating a value of the tail pointer within a hardware transaction or modifying a field of at least one node in the ordered list of nodes within a hardware transaction.

### Claim 11 (depends on 10)

The system of claim 10, wherein when executed on the one or more processor cores, the program instructions cause the one or more processor cores to perform:
subsequent to said removing the inserted node, freeing memory that was allocated to the inserted node.

### Claim 12 (depends on 10)

The system of claim 10, wherein said inserting comprises updating the value of the tail pointer to indicate that the inserted node is the last node in the ordered list of nodes.

### Claim 13 (depends on 12)

The system of claim 12,
wherein said updating the value of the tail pointer to indicate that the inserted node is the last node in the ordered list of nodes is performed within a hardware transaction; and
wherein said inserting further comprises:
prior to updating the value of the tail pointer to indicate that the inserted node is the last node in the ordered list of nodes within the hardware transaction, updating the value of the tail pointer to a pre-determined value indicating an intent to acquire the shared reader-writer lock using a non-transactional atomic operation.

### Claim 14 (depends on 10)

The system of claim 10, wherein said releasing comprises:
determining whether another node succeeds the inserted node in the ordered list of nodes; and
updating the value of the tail pointer to identify another node as the last node in the ordered list of nodes or to indicate that no other node succeeds the inserted node in the ordered list of nodes, dependent on said determining.

### Claim 15 (depends on 10)

The system of claim 10, wherein said inserting further comprises:
initializing, using one or more non-transactional write operations, one or more of: a state field value for the inserted node, a spin field value for the inserted node, or a next-node field value for the inserted node;
wherein the state field value indicates whether the given thread has acquired or desires to acquire the shared reader-writer lock in a read-only mode or in a write mode;
wherein the next-node field value indicates which, if any, node succeeds the inserted node in the ordered list of nodes; and
wherein the spin field value indicates whether the given thread must wait to acquire the shared reader-writer lock.

### Claim 16

A non-transitory, computer-readable storage medium storing program instructions that when executed on one or more computers cause the one or more computers to perform:
beginning execution of a multithreaded application that comprises one or more requests to acquire a shared reader-writer lock, wherein the shared reader-writer lock comprises a tail pointer and an ordered list of zero or more nodes, wherein the shared reader-writer lock controls access to a critical section of code or a shared resource by concurrently executing threads of the application;
a given thread of the application inserting a node in the ordered list of nodes, wherein each node in the ordered list of nodes is owned by a respective thread that holds the shared reader-writer lock or that desires access to the critical section of code or shared resource in a read-only mode or in a write mode, and wherein only one thread can hold the shared reader-writer lock in a write mode at a time;
subsequent to said inserting, the given thread acquiring the shared reader-writer lock in a read-only mode or in a write mode;
subsequent to said acquiring, the given thread releasing the shared reader-writer lock, wherein said releasing comprises removing the inserted node from the ordered list of nodes;
wherein at least one of said inserting or said releasing comprises updating a value of the tail pointer within a hardware transaction or modifying a field of at least one node in the ordered list of nodes within a hardware transaction.

### Claim 17 (depends on 16)

The non-transitory, computer-readable storage medium of claim 16, wherein when executed on the one or more computers, the program instructions cause the one or more computers to perform:
subsequent to said removing the inserted node, freeing memory that was allocated to the inserted node.

### Claim 18 (depends on 16)

The non-transitory, computer-readable storage medium of claim 16, wherein said inserting comprises updating the value of the tail pointer to indicate that the inserted node is the last node in the ordered list of nodes.

### Claim 19 (depends on 18)

The non-transitory, computer-readable storage medium of claim 18,
wherein said updating the value of the tail pointer to indicate that the inserted node is the last node in the ordered list of nodes is performed within a hardware transaction; and
wherein said inserting further comprises:
prior to updating the value of the tail pointer to indicate that the inserted node is the last node in the ordered list of nodes within the hardware transaction, updating the value of the tail pointer to a pre-determined value indicating an intent to acquire the shared reader-writer lock using a non-transactional atomic operation.

### Claim 20 (depends on 16)

The non-transitory, computer-readable storage medium of claim 16, wherein said releasing comprises:
determining whether another node succeeds the inserted node in the ordered list of nodes; and
updating the value of the tail pointer to identify another node as the last node in the ordered list of nodes or to indicate that no other node succeeds the inserted node in the ordered list of nodes, dependent on said determining.
