Efficient Management of Linked-Lists Traversed by Multiple Processes
A network device, such as a switch, implements enhanced linked-list processing features. The processing features facilitate packet manipulation actions performed, e.g., by hardware or software processes. Hardware processes may run for egress ports, for example, to traverse the linked-lists to apply the packet manipulation actions on packets before sending packets out of the ports.
1 . A system comprising:
a memory configured to store:
a linked list comprising a current list entry and a subsequent list entry;
the current list entry comprising:
a pointer to the subsequent list entry; and
a next tracking field configured to store a next tracking value expected in the subsequent list entry;
the subsequent list entry comprising:
a subsequent tracking field configured to store a subsequent tracking value for the subsequent list entry; and
processing logic in communication with the memory, the processing logic configured to:
read the next tracking value;
follow the pointer and read the subsequent tracking field;
determine whether a match exists between the next tracking value the subsequent tracking value; and
determine whether to process the subsequent list entry according to whether the match exists.
2 . The system of claim 1 , further comprising:
management logic in communication with the memory, the management logic configured to:
determine to delete the subsequent list entry; and
in response to determining to delete the subsequent list entry, change the subsequent list entry value to a different value.
3 . The system of claim 2 , where the management logic is configured to change the subsequent list entry value by incrementing the value.
4 . The system of claim 2 , where the management logic is configured to change the subsequent list entry value by determining a hash value, and replacing the subsequent list entry value with the hash value.
5 . The system of claim 4 , where the management logic is configured to:
determine the hash value over selected fields in the subsequent list entry; and
change the hash value if it is identical to the subsequent list entry value.
6 . The system of claim 1 , where the processing logic is configured to:
determine to process the subsequent list entry when the match exists between the next tracking value the subsequent tracking value.
7 . The system of claim 1 , where the processing logic is configured to:
determine to stop processing the linked list when the match does not exist between the next tracking value the subsequent tracking value.
8 . The system of claim 2 , where the management logic comprises a software linked-list manager.
9 . The system of claim 1 , where the processing logic comprises a hardware list processor.
10 . The system of claim 1 , where:
the processing logic comprises a hardware implemented list processor; and
the system further comprises a software linked-list manager that executes asynchronously with respect to the processing logic.
11 . The system of claim 10 , where the hardware implemented list processor comprises a hardware state machine.
12 . The system of claim 1 , where the processing logic comprises:
processing logic associated with an egress port in a switch device.
13 . The system of claim 12 , where the processing logic is configured to process the current list entry to replicate a packet for transmission out the egress port.
14 . The system of claim 13 , where the current list entry comprises a data element that specifies a packet processing action for the packet.
15 . A system comprising:
a memory configured to store:
a linked list comprising a current list entry;
the current list entry comprising:
a current tracking field configured to store a current tracking value expected in the current list entry;
processing logic in communication with the memory, the processing logic configured to:
read and store the current tracking value as an original tracking value, when the processing logic first begins to process the current list entry;
suspend operation;
resume operation and re-read the current tracking field to obtain a current tracking value; and
determine whether to continue processing the linked-list depending on whether a match exists between the current tracking value and the original tracking value.
16 . The system of claim 15 , where the processing logic is configured to:
stop processing the linked-list when the match does not exist.
17 . The system of claim 15 , where the processing logic comprises:
processing logic associated with an egress port in a switch device.
18 . The system of claim 17 , where the processing logic is configured to process the current list entry to replicate a packet for transmission out the egress port.
19 . The system of claim 18 , where the current list entry comprises a data element that specifies a packet processing action for the processing logic to execute for the packet.
20 . A system comprising:
a shared memory configured to store:
a linked list comprising a current list entry and a subsequent list entry;
the current list entry comprising:
a current tracking value;
a pointer to the subsequent list entry; and
a next tracking field configured to store a next tracking value expected in the subsequent list entry;
the subsequent list entry comprising:
a subsequent tracking field configured to store a subsequent tracking value for the subsequent list entry;
management logic in communication with the shared memory, the management logic configured to:
modify the subsequent tracking field the subsequent list entry, when the management logic determines to delete the subsequent list entry; and
processing logic in communication with the shared memory, the processing logic configured to:
before moving ahead to process the subsequent list entry, determine whether a match exists between the next tracking value the subsequent tracking value; and
forego processing the subsequent list entry when no match exists;
store the current tracking value in a context memory as an original tracking value for the current list entry; and
when resuming after suspension, obtain a re-read tracking value from the current list entry, and terminate processing of the linked list when the re-read tracking value does not match the original tracking value.