Lockless processing of command operations in multiprocessor systems
View Patent ↗A beltway mechanism that takes advantage of atomic locking mechanisms supported by certain classes of hardware processors to handle the tasks that require atomic access to data structures while also reducing the overhead associated with these atomic locking mechanisms. The beltway mechanisms described herein can be used to control access to software and hardware facilities in an efficient manner.
1. An apparatus comprising
N processors, where N is greater than 1;
a work order module operative to provide work queue entries to the N processors, wherein the work queue entries correspond to respective tasks, and to provide, to a given processor of the N processors, exclusive access to one or more shared data structures for work queue entries including atomic tags;
a memory operative to store one or more instances of a beltway data structure, each instance of a beltway data structure comprising N circular buffers for corresponding ones of the N processors, wherein the N circular buffers each comprise a plurality of entries; the memory further operative to store processor-readable instructions for a beltway producer function and a beltway consumer process;
wherein the beltway producer function includes instructions operative to cause the N processors, when executing the beltway producer function, to
add entries to corresponding ones of the circular buffers of an identified instance of a beltway data structure;
conditionally submit work queue entries to the work order module including an atomic tag associated with the identified instance of the beltway data structure; and
wherein the beltway consumer process includes instructions operative to cause a processor of the N processors, responsive to a work queue entry identifying the beltway consumer process and an atomic tag corresponding to the instance of a beltway data structure, to:
identify the instance of the beltway data structure based on one or more attributes of the work queue entry;
read entries from the circular buffers of the identified instance of the beltway data structure; and
call a consumer function associated with the identified instance of the beltway data structure to process the read entries.
2. The apparatus of claim 1 wherein the work order module is operative to
maintain a queue of work entries, one or more of the work entries including an atomic tag; and
schedule work entries in the queue for the N processors such that only a single processor of the N processors is provided a work entry labeled with a given atomic tag.
3. The apparatus of claim 1 wherein submitting work queue entries to the work order module is conditioned on whether a previous work queue entry for a consumer process for the identified instance of the beltway data structure is currently maintained by the work order module.
4. The apparatus of claim 1 wherein the beltway consumer process further comprises instructions operative to cause a processor of the N processors to arbitrate among the circular buffers in a round robin arbitration scheme.
5. The apparatus of claim 4 wherein the beltway consumer process further comprises instructions operative to cause a processor of the N processors to read up to a limited number of entries in a given circular buffer before proceeding to a next circular buffer during the round robin arbitration scheme.
6. The apparatus of claim 1 wherein entries of the beltway data structure are associated with time stamps each corresponding to a time when a given entry is added, and wherein the beltway consumer process further comprises instructions operative to cause a processor of the N processors to select entries across the circular buffers of the beltway data structure based on the time stamps.
7. The apparatus of claim 1 further comprising an output port, and wherein the consumer function is operative to write data onto the output port.
8. The apparatus of claim 1 further comprising hardware timer logic, and wherein the consumer function is operative to access and send commands to the hardware tinier logic.
9. The apparatus of claim 1 further comprising hardware compression logic, and wherein the consumer function is operative to access and send commands to the hardware compression logic.
10. The apparatus of claim 1 wherein the consumer function is operative to exclusively access a first hardware resource.
11. The apparatus of claim 10 wherein the first hardware resource comprises one or more registers.
12. The apparatus of claim 1 wherein the consumer function is operative to exclusively access a plurality of hardware resources.
13. The apparatus of claim 1 further comprising one or more network interfaces; and wherein the memory is further operative to define a hierarchical partition configuration, the hierarchical partition configuration comprising a plurality of partitions, the memory further operative to buffer packets received at the one or more network interfaces;
wherein the N processors, to schedule packets for transmission according to the hierarchical partition configuration, are each operative to:
receive, from the work order module, an indication of a first work entry, wherein the first work entry is associated with a packet to be processed and includes a tag identifying a partition of the plurality of partitions,
forward the packet corresponding to the first work entry to a parent partition of the identified partition by modifying the first work entry to include a tag of the parent partition,
resubmit the first modified work entry to the work order module, and
call, if the partition associated with the tag is a root partition, the beltway producer function to add an entry to an instance of the beltway data structure associated with a network interface to schedule a packet for transmission from the network interface.
14. The apparatus according to claim 13 , wherein the plurality of processors are further operative to
add tokens to a token bucket associated with the partition associated with the tag based on a target rate associated with the partition and a last token update time;
conditionally forward the packet to the parent partition based on a size of the packet and a current number of tokens in the token bucket of the partition associated with the tag; and
deduct, responsive to forwarding the packet, tokens from the token bucket of the partition associated with the tag.
15. The apparatus according to claim 14 wherein the plurality of processors are further operative to
place the packet on a partition queue if a number of tokens in the token bucket of the partition associated with the tag is insufficient to transmit the packet; and
compute a delay time based on the target rate of the partition and the size of the packet;
call the beltway producer function with a command operative to set a timer for the delay time, wherein the timer, when triggered, is operative to return the work entry identifying the partition associated with the tag to the corresponding processor.
16. A method comprising
maintaining a queue of work queue entries in a work order module, one or more of the work queue entries including a tag, wherein the work order module is operative to schedule work queue entries in the queue for N processors, wherein N is greater than 1, such that only a single processor of the N processors is provided a work queue entry labeled with a given tag;
storing, in a memory, one or more instances of a beltway data structure, each instance of a beltway data structure comprising N circular buffers (rings) for corresponding ones of the N processors, wherein the N circular buffers each comprise a plurality of entries;
executing a beltway producer function operative to
add entries to corresponding ones of the circular buffers of an identified instance of a beltway data structure;
conditionally submit work queue entries to the work order module including a tag associated with the identified instance of the beltway data structure; and
executing, responsive to a work queue entry identifying a beltway consumer process and a tag corresponding to the instance of a beltway data structure, a beltway consumer process on a select processor of the N processors, the beltway consumer process operative to:
identify the instance of the beltway data structure based on one or more attributes of the work queue entry;
read entries from the circular buffers of the identified instance of the beltway data structure; and
call a consumer function associated with the identified instance of the beltway data structure to process the read entries.
17. The method of claim 16 wherein submitting work queue entries to the work order module is conditioned on whether a previous work queue entry for a consumer process for the identified instance of the beltway data structure is currently maintained by the work order module.
18. The method of claim 16 wherein the beltway consumer process is further operative to cause a processor of the N processors to arbitrate among the circular buffers in a round robin arbitration scheme.
19. The method of claim 18 wherein the beltway consumer process is further operative to cause a processor of the N processors to read up to a limited number of entries in a given circular buffer before proceeding to a next circular buffer during the round robin arbitration scheme.
20. The method of claim 16 wherein entries of the beltway data structure are associated with time stamps each corresponding to a time when a given entry is added, and wherein the beltway consumer process is further operative to cause a processor of the N processors to select entries across the circular buffers of the beltway data structure based on the time stamps.