Lock-free method of transmitting hierarchical collections through shared memory

Patent metadata

Field	Value
Publication number	US-11422872-B2
Application number	US-202016886692-A
Country	US
Kind code	B2
Filing date	May 28, 2020
Priority date	May 28, 2020
Publication date	Aug 23, 2022
Grant date	Aug 23, 2022

Abstract

Systems and methods for creating a new entry in a hierarchical state data structure with object entries is disclosed. The method includes allocating a shared memory buffer for a new entry in a shared memory. A request to create the new entry for a child object in a hierarchical state data structure in the shared memory is received. The new entry is to span at least one shared memory buffer uniquely identifiable in a location of the shared memory. The child object is a logical representation of a state of a system. In response to a request for an allocation of a shared memory buffer within a region of the shared memory for the new entry, a location identifier corresponding to a location of a parent entry holding a parent object to the child object in the hierarchical state data structure of an allocated region is received. The child object is created in the shared memory buffer for the new entry, and the new entry is available for concurrent access by one or more readers of the shared memory.

First claim

What is claimed is:

1. A non-transitory computer-readable medium storing executable instructions to cause one or more processing units to perform a method to allocate a shared memory buffer for a new entry in a shared memory, the method comprising:
receiving, by a writer manager, a request to create the new entry in the shared memory for a first child object in a hierarchical state data structure in the shared memory,
wherein:
the new entry in the shared memory comprises one or more shared memory buffers,
the new entry in the shared memory is at a uniquely identifiable location in the shared memory,
the first child object in the hierarchical state data structure in the shared memory is a logical representation of a state of a system, and
in response to a request for an allocation of a shared memory buffer within a region of the shared memory for the new entry in the shared memory, receiving a first location identifier corresponding to a location of a parent entry holding a parent object to the first child object in the hierarchical state data structure of an allocated region of the shared memory; and

creating the first child object in the hierarchical state data structure in the allocated shared memory buffer for the new entry in the shared memory,
wherein:
the new entry in the shared memory is available for concurrent access to one or more readers of the shared memory.

2. The non-transitory computer-readable medium of claim 1 , wherein the allocated shared memory buffer remains allocated to the new entry in the shared memory until a number of references to the first child object in the hierarchical state data structure in the allocated shared memory buffer reaches a threshold number of references.

3. The non-transitory computer-readable medium of claim 1 , further comprising storing the first location identifier corresponding to the location of the parent entry in a notification of a notification queue in the shared memory, wherein storing the first location identifier corresponding to the location of the parent entry in the notification of the notification queue in the shared memory alerts the one or more readers of the shared memory of a possible change in a state represented by the hierarchical state data structure in the allocated shared memory buffer.

4. The non-transitory computer-readable medium of claim 3 , further comprising:
setting an advertised flag in a metadata field of the new entry in the shared memory indicting the new entry in the shared memory is ready for reading by the one or more readers of the shared memory;
in response to receiving a request to delete the first child object in the hierarchical state data structure in the allocated shared memory buffer:
resetting the advertised flag in the metadata field of the new entry in the shared memory to indicate the new entry in the shared memory is not ready for reading by the one or more readers of the shared memory; and
storing the first location identifier corresponding to the location of the parent entry in another notification of the notification queue in the shared memory to alert the one or more readers of the shared memory of a possible change in a state represented by the hierarchical state data structure in the allocated shared memory buffer.

5. The non-transitory computer-readable medium of claim 1 , further comprising in response to a successful allocation of the allocated region of the shared memory, incrementing a version number in a metadata field indicative of the allocated shared memory buffer and in response to deallocation of the allocated shared memory buffer from the shared memory, incrementing the version number in the metadata field indicative of the allocated shared memory buffer being deallocated.

6. The non-transitory computer-readable medium of claim 1 , wherein one or more parent objects of the hierarchical state data structure of the allocated region of the shared memory are added to the hierarchical state data structure of the allocated region of the shared memory before one or more corresponding child objects are added to the hierarchical state data structure of the allocated region of the shared memory and the one or more corresponding child objects are removed from the hierarchical state data structure of the allocated region of the shared memory before a parent object of a removed child object is removed from the hierarchical state data structure of the allocated region of the shared memory.

7. The non-transitory computer-readable medium of claim 1 , wherein entries of objects of the hierarchical state data structure in the shared memory correspond to states of a routing table of a network switch or a network router.

8. The non-transitory computer-readable medium of claim 1 , further comprising:
receiving a request for updating an existing entry of a second child object of the hierarchical state data structure in the shared memory, wherein the existing entry of the second child object of the hierarchical state data structure in the shared memory has a valid state and includes an original value representing an attribute state of the system;
setting a lookaside flag in a metadata field of the existing entry of the second child object of the hierarchical state data structure in the shared memory indicative of an invalid state of the existing entry of the second child object of the hierarchical state data structure in the shared memory;
modifying the original value of the existing entry of the second child object of the hierarchical state data structure in the shared memory to an updated value; and
resetting the lookaside flag in the metadata field of the existing entry of the second child object of the hierarchical state data structure in the shared memory indicative of a valid state of the existing entry of the second child object of the hierarchical state data structure in the shared memory.

9. The non-transitory computer-readable medium of claim 8 , further comprising prior to setting the lookaside flag in the metadata field of the existing entry of the second child object of the hierarchical state data structure in the shared memory, storing the updated value in a temporary buffer in the shared memory to make the updated value available to the one or more readers of the shared memory while the existing entry of the second child object of the hierarchical state data structure in the shared memory has an invalid state.

10. The non-transitory computer-readable medium of claim 9 , further comprising storing a second location identifier in a notification of a notification queue in the shared memory, wherein the second location identifier in the notification of the notification queue in the shared memory alerts the one or more readers of the shared memory of a possible change in a state represented by the hierarchical state data structure in the allocated shared memory buffer.

11. A non-transitory computer-readable medium storing executable instructions to cause one or more processing units to perform a method of processing an entry of an object in a shared memory comprising:
reading a first notification from a notification queue of the shared memory, wherein the first notification from the notification queue of the shared memory represents a change made by a writer manager to a state change in a first state of the entry of the object in a hierarchical state data structure in the shared memory, and wherein the entry of the object in the hierarchical state data structure in the shared memory is a logical representation of a first state of a system;
based on a location identifier of the first notification from the notification queue of the shared memory, locating an entry status corresponding to

Assignees

• Arista Networks Inc

Inventors

• Neilson Christopher Elisha
• Ritchie Duncan Stuart
• Sapa Sebastian

Classifications

• G06F9/544 Primary

  Buffers; Shared memory; Pipes · CPC title

• G06F9/5022

  Mechanisms to release resources · CPC title

• G06F12/0833

  in combination with broadcast means (e.g. for invalidation or updating) · CPC title

• G06F9/542

  Event management; Broadcasting; Multicasting; Notifications · CPC title

• G06F9/546

  Message passing systems or structures, e.g. queues · CPC title