Efficient search key processing method

Patent metadata

Field	Value
Publication number	US-9632959-B2
Application number	US-201414326388-A
Country	US
Kind code	B2
Filing date	Jul 8, 2014
Priority date	Jul 8, 2014
Publication date	Apr 25, 2017
Grant date	Apr 25, 2017

Abstract

An efficient search key processing method includes writing a first and a second search key data set to a memory, where the search key data sets are written to memory on a word by word basis. Each of the first and second search key data sets includes a header indicating a common lookup operation to be performed and a string of search keys. The header is immediately followed in memory by a search key. The search keys are located contiguously in the memory. At least one word contains search keys from the first and second search key data sets. The memory is read word by word. A first plurality of lookup command messages are sent based on the search keys included in the first search key data set. A second plurality of lookup command messages are sent based on the search keys included in the second search key data set.

First claim

What is claimed is:

1. A method comprising:
(a) writing a first search key data set and a second search key data set into a memory, wherein the memory is written with search key data sets only on a word by word basis, wherein each of the first and second search key data sets includes a header along with a string of search keys, wherein the header of a search key data set indicates a common lookup operation to be performed using each of the search keys of the search key data set, wherein the header of a search key data set is immediately followed in memory by a search key of the search key data set, wherein the search keys of the search key data set are located contiguously in the memory, and wherein at least one word contains search keys from both the first and second search key data sets;
(b) reading the memory word by word and thereby reading the first search key data set and the second search key data set;
(c) outputting a first plurality of lookup command messages, wherein each respective one of the first plurality of lookup command messages includes a corresponding respective one of the search keys of the first search key data set; and
(d) outputting a second plurality of lookup command messages, wherein each respective one of the second plurality of lookup command messages includes a corresponding respective one of the search keys of the second search key data set.

2. The method of claim 1 , wherein the first plurality of lookup command messages are output in (c) to a transactional memory device, and wherein the second plurality of lookup command messages are output in (d) to the transactional memory device.

3. The method of claim 1 , further comprising:
(e) storing a result data value in a transactional memory device, and wherein the transactional memory device: 1) receives a search key as part of a lookup command message, 2) uses a search key of the lookup command message to identify the result data value; and 3) outputs the result data value.

4. The method of claim 3 , further comprising:
(f) receiving a first plurality of result data values from the transactional memory device, wherein the plurality of result data values are output by the transactional memory device in response to receiving the first plurality of lookup command messages;
(g) writing the first plurality of result data values to the memory;
(h) generating a DMA completion message; and
(i) writing the DMA completion message to a processor.

5. The method of claim 4 , wherein the transactional memory device is a Ternary Content Addressable Memory (TCAM), and wherein the descriptor is generated by the processor in response to an Internet Protocol (IP) lookup instruction.

6. The method of claim 4 , wherein the writing of (g) is perform after n-bits of result data values are received, wherein a bus used to perform the writing of (g) is n-bits wide, and wherein all of the plurality of result data values are written in a single bus transaction.

7. The method of claim 1 , wherein the header includes an indication of a number of search keys in the search key data set.

8. The method of claim 1 , further comprising:
(c1) parsing a key size from a header data; and
(c2) delineating a plurality of search keys included in the search key data according to the key size.

9. The method of claim 1 , wherein the reading of (b) occurs in response to a processor writing a descriptor to a Direct Memory Access (DMA) controller, wherein the DMA controller executes the read of the first and second search key data sets.

10. The method of claim 9 , wherein the descriptor includes: 1) a length of a DMA operation, 2) a read address where a search key data set is stored in the memory, 3) a write address where a result data value will be written, and 4) completion notification information.

11. The method of claim 10 , further comprising:
(j) reading one or more result data values from the memory, wherein the reading of (j) is performed by the processor across a bus.

12. The method of claim 1 , wherein the reading of (b) is performed using n-bits per bus transaction, and wherein a bus used to perform the reading of (b) is n-bits wide.

13. The method of claim 1 , wherein steps (a) through (d) are performed only utilizing combinatory logic.

Assignees

• Netronome Systems Inc

Inventors

• Bouley Rick

Classifications

• G06F13/28 Primary

  using burst mode transfer, e.g. direct memory access {DMA}, cycle steal (G06F13/32 takes precedence) · CPC title

• G06F13/1663

  Access to shared memory · CPC title