JP2008512797A - Deterministic finite automaton (DFA) processing - Google Patents

Abstract

A processor 110 is provided that scans a deterministic finite automaton (DFA) graph in real time with incoming packet data. The processor has at least one processor core 120 and a DFA module 134 that operates asynchronously with the at least one processor core 120 and stores the packet data stored in the cache coherent memories 130 and 108 in the non-cache memory 118. Scan at least one DFA graph generated.
[Selection] Figure 1B

Description

Related applications

  This application claims the benefit of US Provisional Patent Application No. 60 / 609,211 filed on September 10, 2004 and US Provisional Patent Application No. 60 / 669,672 filed on April 8, 2005. The entire contents of each of the above applications are incorporated herein by reference.

  The Open Systems Interconnection (OSI) reference model defines seven network protocol layers (L1-L7) that are used for communication over transmission media. The upper layer (L4-L7) represents end-to-end communication, and the lower layer (L1-L3) represents local communication.

  Networking application-aware systems (applications automatically control the network) network protocol layers ranging from L3 to L7, for example L7 networks such as Hypertext Transfer Protocol (HTTP) and Simple Mail Transfer Protocol (SMTP) There is a need to process, filter and switch protocol layers and L4 network protocol layers such as Transmission Control Protocol (TCP). In addition to network protocol layer processing, networking application-aware systems include firewall, virtual private network (VPN), secure socket layer (SSL), intrusion detection system (IDS), Internet protocol security (IPSec), antivirus (AV ) And access-based and content-based security through the L4 to L7 network protocol layers, including anti-spam features, also requires that these protocols be secured at wire speed at the same time.

  Network processors are utilized for high throughput L2 and L3 network protocol processing. The L2 and L3 network protocol processing is execution of packet processing for transferring a packet at wire speed. In general, a general-purpose processor is used for processing network protocols from L4 to L7 that require higher-level processing. For example, the Transmission Control Protocol (TCP), an L4 network protocol, includes multiple computationally intensive tasks, including checksum calculation across all payloads in a packet, TCP segment buffer management, and multiple timers that are always retained for each connection. I need. A general purpose processor can perform computationally intensive tasks, but does not have enough performance to process and transfer data at wire speed.

  Furthermore, a content-aware application that examines the contents of a packet (an application that automatically recognizes content) needs to search for an expression that includes both a fixed character string and a character class that is repeated a variable number of times in the data stream. . Multiple search algorithms are used to perform this task in software. One such algorithm is deterministic finite automaton (DFA). However, when using the DFA search algorithm, limitations such as exponential expansion of the graph size due to repetitive patterns and false matches in the data stream arise.

  Because of these limitations, content processing applications require a significant amount of post-processing on the results produced by pattern searching. In the post-processing, it is necessary to identify the matching pattern based on other connection state information such as the connection type and a specific value in the protocol header included in the packet. This also requires certain other types of computationally intensive identification, for example, pattern matching is valid if it is within a certain position range in the data stream, or if another pattern is Only if it follows and is within a certain range from the preceding pattern, or only after or after a certain offset position from the preceding pattern. For example, regular expression matching combines various operators and single characters to allow the construction of complex expressions.

  The present invention aims to improve the speed at which a processor can process a content processing application. The processor includes at least one processor core and a deterministic finite automaton (DFA) module that operates asynchronously with the at least one processor core. The processor stores at least one DFA graph stored in the first memory. And a DFA module that scans using the packet data stored in.

  The DFA module can have a first memory controller, at least one DFA thread engine, and instruction input logic. The processor core can send DFA instructions to the DFA module via an instruction queue of instruction input logic. The DFA instruction can indicate the packet data stored in the second memory for use, and can indicate the DFA graph stored in the first memory for scanning. The DFA module can schedule DFA instructions to the DFA thread engine. The DFA thread engine can fetch the packet data stored in the second memory and issue a memory access instruction according to the fetched packet data.

  For example, the first memory may be a non-cache memory and the second memory may be a cache coherent memory. The DFA thread engine sequentially fetches packet data stored in the cache coherent memory one byte at a time. Next, the DFA thread engine issues a non-cache memory load instruction for each byte of packet data received from the cache coherent memory, and scans the next state of the DFA graph stored in the non-cache memory. The DFA thread engine also writes intermediate and final results to cache coherent memory.

  The foregoing and other objects, features and advantages of the invention will become apparent from the following more detailed description of the preferred embodiment of the invention as illustrated in the accompanying drawings. In the accompanying drawings, the same reference numerals denote the same parts in different drawings. The drawings are not necessarily to scale, emphasis instead being placed on illustrating the principles of the invention.

  Hereinafter, preferred embodiments of the present invention will be described.

  FIG. 1A is a block diagram illustrating a security system 100 that includes a network service processor 110 according to the principles of the present invention. The security system 100 switches a packet received at one Ethernet (registered trademark) port (Gig E) to another Ethernet (registered trademark) port (Gig E), and executes a plurality of security functions on the received packet. It is a stand-alone system that forwards the packet. For example, the security system 100 can be used to perform security processing on a packet received on the wide area network and then transfer the packet to the local area network.

  The network service processor 110 speeds up all packet processing tasks by providing hardware packet processing, buffering, work scheduling, ordering, synchronization, and cache coherence support. The network service processor 110 processes the protocols from the L2 to L7 layers of the open intersystem interconnection network encapsulated in the received packet.

  The network service processor 110 receives a packet from the Ethernet (registered trademark) port (Gig E) via the physical interfaces PHY 104a and 104b, executes L7 to L2 network protocol processing on the received packet, and performs processing. The packet is transferred from the physical interfaces 104 a and 104 b or via the PCI bus 106. Network protocol processing includes network security such as firewall, application firewall, IP security (IPSEC) and / or virtual private network (VPN) including secure socket layer (SSL), intrusion detection system (IDS) and antivirus (AV) Protocol processing may be included.

  A dynamic random access memory (DRAM) controller 133 (FIG. 1B) within network service processor 110 controls access to external DRAM 108 that is coupled to network service processor 110. The DRAM 108 stores data packets received from the PHY interfaces 104 a, 104 b or the PCI expansion (PCI-X) interface 106 for processing by the network service processor 110.

  A low latency memory controller 360 (FIG. 3B) within the network service processor 110 controls the low latency memory (LLM) 118. The LLM 118 can be used in Internet service / security applications that enable fast searches, including regular expression matching required for intrusion detection system (IDS) or antivirus (AV) applications.

  A regular expression is a general method for expressing a character string matching pattern. The minimal element of a regular expression is a single character to be matched. They can also be combined with metacharacter operators that allow the user to express concatenation, selection, Kleene Star, etc. Concatenation is used to generate multiple character matching patterns from a single character (or substring) and selection (|) to generate a pattern that can match any of two or more substrings used. Using a Kleene Star (*) allows a pattern to match zero (0) or more occurrences of that pattern in the string. The combination of each operator and a single character makes it possible to construct complex expressions. For example, the expression (th (is | at) *) matches th, this, that, thisis, thisat, thatis, thatat, etc.

  FIG. 1B is a block diagram of the network service processor 110 shown in FIG. 1A. Network service processor 110 uses at least one processor core 120 to provide high application performance as described in connection with FIG. 1A.

  The packet is received for processing by any one of the GMX / SPX units 122a, 122b via the SPI-4.2 or RGMII interface. The packet can also be received by the PCI interface 124. The GMX / SPX unit (122a, 122b) performs preprocessing of the received packet by checking various fields in the L2 network protocol header included in the received packet, and then the packet is sent to the packet input unit. 126.

  The packet input unit 126 performs further preprocessing of the network protocol headers (L3 and L4) included in the received packet. The pre-processing includes a checksum check for the communication control protocol (TCP) / user datagram protocol (UDP) (L3 network protocol).

  A free pool allocator (FPA) 128 maintains a pointer pool of free memory in the level 2 cache memory 130 and DRAM 108. The packet input unit 126 uses one of the pools of pointers to store received packet data in the level 2 cache memory 130 and uses another pool of pointers to the processor core 120 for work queues. Assign an entry.

  The packet input unit 126 then writes the packet data to the level 2 cache 130 or a buffer in the DRAM 108. This writing format is convenient for higher layer software running on at least one of the processor cores 120 to facilitate subsequent processing by higher layer network protocols.

  The I / O interface 136 manages the overall protocol and arbitration and provides coherent I / O partitioning. The I / O interface 136 includes an I / O bridge (IOB) 138 and a fetch and add unit (FAU) 140. A register in the fetch and add unit 140 is used to hold the length of the output queue used to transfer the processed packet through the packet output unit 146. The I / O bridge 138 includes a buffer queue for storing information transferred between the coherent memory bus 144, the I / O bus 142, the packet input unit 126, and the packet output unit 146.

  The packet order / work module (POW) 148 queues (queues) work for the processor core 120 and schedules it. A work is queued by adding a work queue entry to the queue. For example, a work queue entry is added by the packet input unit 126 for each packet arrival. The timer unit 150 is used for scheduling the work of the processor core 120.

  The processor core 120 requests a work from the POW module 148. The POW module 148 selects a work for one of the processor cores 120 (ie, scheduling) and returns a pointer to the processor core 120 that points to a work queue entry that describes the work.

  The processor core 120 includes an instruction cache 152, a level 1 (L1) data cache 154, and a cryptographic accelerator 156. In one embodiment, the network service processor 110 has 16 superscalar RISC (Reduced Instruction Set Computer) type processor cores 120. In one embodiment, each superscaler RISC processor core 120 is an extension of the MIPS64 version 2 processor core.

  Level 2 (L2) cache memory 130 and DRAM 108 are shared by all of processor core 120 and I / O coprocessor devices. Each processor core 120 is coupled to the level 2 cache memory 130 by a coherent memory bus 144. The coherent memory bus 144 is a communication channel for all memory and I / O transactions between the processor core 120, IOB 138 and L2 cache memory 130 and L2 cache memory controller 131. In one embodiment, the coherent memory bus 144 is adaptable for 16 processor cores 120, supports a fully coherent L1 data cache 154 with write-through, performs advanced buffering, and prioritizes I / O. Can be ranked.

  The L2 cache memory controller 131 holds memory reference coherence. The L2 cache memory controller 131 will block for any FILL request, whether the block is stored in the level 2 cache memory 130 or external DRAM 108, or “in-flight”. Returns the latest copy of. The L2 cache memory controller 131 also stores two tags for the data cache 154 in each processor core 120. The L2 cache memory controller 131 compares the address of the cache block store request with the data-cache tag and the store instruction is from another processor core or from an I / O component via the I / O interface 136. Sometimes, the processor core 120 data-cache tag (both copies) is invalidated.

  The DRAM controller 133 supports up to 16 megabytes of DRAM. The DRAM controller 133 supports a 64-bit or 128-bit interface with the DRAM 108. The DRAM controller 133 supports DDR-I (double data rate) and DDR-II protocols.

  When the packet is processed by the processor core 120, the packet output unit (PKO) 146 reads the packet data from the memory, performs post-processing of the L4 network protocol (for example, generates a TCP / UDP checksum), and the packet Are transferred via the GMX / SPX units 122a and 122b, and the L2 cache 130 / DRAM 108 used by the packet is released.

  The low latency memory controller 360 (FIG. 3B) manages in-flight transactions (load / store) with the LLM 118. Low latency memory (LLM) 118 is shared by all processor cores 120. The LLM 118 is a dynamic random access memory (DRAM), a low delay dynamic random access memory (RLDRAM), a synchronous random access memory (SRAM), a fast cycle random access memory (FCRAM), or any other type of low memory known in the art. It may be a delay memory. RLDRAM provides a memory delay of 30 nanoseconds or less (ie, the time it takes for a memory request initiated by processor 120 to be satisfied). Each processor core 120 is directly coupled to the LLM controller 360 by a low latency memory bus 158. The low-latency memory bus 158 is a communication channel for content-aware application processing between the processor core 120 and the LLM controller 360. The LLM controller 360 is coupled between the processor core 120 and the LLM 118 to control access to the LLM 118.

  The network service processor 110 has an application specific coprocessor that offloads the processor core 120, thereby enabling the network service processor to achieve high throughput. The compression / decompression coprocessor 132 performs dedicated compression and decompression of received packets. The deterministic finite automaton (DFA) module 134 has a dedicated DFA engine 370 (FIG. 3B) and handles pattern and signature matching required for antivirus (AV), intrusion detection system (IDS) and other content processing applications. To accelerate up to 4 Gbps.

  The processing of the content-aware application uses a pattern / expression (data) stored in the LLM 118. The pattern / representation may be in the form of a deterministic finite automaton (DFA). A DFA is a state machine. The input to the DFA state machine is a string of bytes (1 byte = 8 bits) (ie, the alphabet is 1 byte in DFA). Each input byte causes the state machine to transition from one state to the next. States and transition functions can be displayed in a graph 200 as shown in FIG. 2A. However, each graph node (nodes 0-3) is in one state, and different graph arcs interconnecting different nodes represent state transitions for different input bytes. The state includes specific characters associated with the state, such as "A ... Z, a ... z, 0 ... 9,". The current state of the state machine is a node identifier that selects a particular node in the graph. The number of nodes may be in the range from a few nodes to about 128,000 nodes in a small size graph. A large size graph may have up to 1,000,000 nodes, or more.

  In the illustrative example, the DFA graph 200 is designed to search for a target string representation “abc”. Thus, the DFA graph is used to search for input data that exactly matches the string of characters “abc”. This representation is a fixed length representation, from which the number of nodes and hence the depth of the graph is known (ie constant).

  To generate a DFA graph, the above expression is parsed and the compiler generates a root node (ie, node “0”) and adds nodes 1 to 3 to the graph according to the intended expression (ie, target One additional node for each character in the string). With continued reference to this example, an exemplary character input stream includes the string “12abc3”. The input string is searched using the DFA graph and the target string representation “abc” is identified.

  The initial state of the DFA graph is node “0”. Each character or byte is read sequentially, and the DFA remains at node 0 until the first character of the target string representation is read. For example, when the first character “a” in the target character string expression in the input stream is detected, an arc represented by “a” is traced from node 0 to node 1. Next, the next character in the input stream is read and if it is detected that it is something other than the next character in the target string representation (ie, “b”), it is written “not b” , An arc from node 1 back to node 0 is followed. However, when the character “b” is detected as the next character in the input stream, an arc from node 1 to node 2 represented by “b” is traced. Next, the next character of the input stream is read, and if this is any character other than the next character in the target string representation (ie, “c”), node 2 to node denoted “not c” An arc returning to 0 is followed. However, when the character “c” in the input stream is detected at the node 2, the arc from the node 2 to the node 3 represented by “c” is traced. Since the target string representation “abc” is a fixed length representation, node 3 is a terminal node, and as a result of the search, that is, the representation “abc” has been found and the position of this representation in the input stream Is reported.

  In addition, more complex DFA graphs can be similarly generated by analyzing one or more intended expressions in the compiler and generating the appropriate nodes of the graph as required by the intended expression. Thus, a single graph can be used to search for multiple representations that are fixed length, variable length and fixed / variable length combinations.

  FIG. 3A is a block diagram illustrating a reduced instruction set computer type (RISC) processor 120 according to the principles of the present invention. The processor (processor core) 120 includes an integer arithmetic unit 302, an instruction dispatch unit 304, an instruction fetch unit 306, a memory management unit (MMU) 308, a system interface 310, a low delay interface 350, a load / store unit 314, a write buffer 316, and A security accelerator 156 is included. The processor core 120 also has an EJTAG interface 330 that can execute a debugging operation. The system interface 310 controls access to external memory, ie, memory external to the processor 120, such as external (L2) cache memory 130 or main / main memory 108.

  The integer arithmetic unit 302 includes a multiplication unit 326, at least one register file (main register file) 328, and two holding registers 330a and 330b. The holding registers 330a and 330b are used to store data written to the LLM 118 and data read from the LLM 118 using LLM load / store instructions. Holding registers 330a, 330b improve the efficiency of the instruction pipeline by allowing two outstanding loads before decommissioning the pipeline. Although two holding registers are shown, one or more holding registers may be used. Multiplication unit 326 can perform direct multiplication of 64-bit registers. The instruction fetch unit 306 includes an instruction cache (ICache) 152. The load / store unit 314 has a data cache 154. In one embodiment, instruction cache 152 is 32 kilobytes, data cache 154 is 8 kilobytes, and write buffer 316 is 2 kilobytes. The memory management unit 308 includes a translation lookaside buffer (TLB) 340.

  In one embodiment, processor 120 provides cryptographic acceleration for Triple Data Encryption Standard (3DES), Advanced Encryption Standard (AES), Secure Hash Algorithm (SHA-1), Message Digest Algorithm No. 5 (MD5). A cryptographic acceleration module (security accelerator) 156 including The cryptographic acceleration module 156 communicates with the main register file 328 in the arithmetic unit 302 through the transfer. RSA and Diffie-Hellman (DH) algorithms are executed in multiplication unit 326.

  FIG. 3B is a block diagram illustrating the DFA module 134 of FIG. 3A. The DFA module 134 has a low latency DRAM controller 360, at least one DFA thread engine (DTE) 370 (16 are shown), and instruction input logic 380. Instruction input logic 380 includes a DFA instruction queue 382 and a doorbell 384. The DFA instruction queue 382 queues (queues) DFA instructions stored in the L2 / DRAM (130/108), and the doorbell indicates the number of DFA instructions stored in the DFA instruction queue 382. . The core 120 software can issue a doorbell write for each individual DFA instruction, ie, multiple DFA instructions can be accumulated in a single doorbell write. Each DFA instruction says that DFA module 134 needs to start DTE 370, read input data, scan DFA graph 200 stored in LLM 118, and write the result to L2 / DRAM (130/108). Contains information. The format of the DFA instruction will be described later with reference to FIG. 8A.

  The DTE 370 can be used to perform a pattern search. In general, the DTE 370 uses the input packet data to search for a specific representation in the packet data (present in the L2 / DRAM (130/108)) and DFA graph 200 (FIG. 2) (present in the LLM 118). Scan. For example, the network service processor can track up to 1000 TCP input streams simultaneously with each input stream sent to a separate DTE to search for a particular representation. Prior to the scan, the software in core 120 first (i) preloads the DFA graph in LLM 118 via LLM bus 158 and (ii) DFA in L2 / DRAM (130/108). It is necessary to preload instructions and (iii) send DFA instructions to the DFA module 134 via the IOB 142. The DFA instruction indicates a DFA graph 200 that is scanned using input packet data. Thereafter, DFA module 134 fetches and queues DFA instructions and schedules each DFA instruction to one of the 16 available DTEs 370. All DTEs 370 are identical and equivalent so that any DFA instruction can be scheduled to any available DTE 370. Upon receipt of the instruction, the DTE 370 simultaneously (a) fetches packet data from the L2 / DRAM (130/108) via the IOB 142 and (b) for each byte of packet data, The LLM DRAM load instruction is issued so as to shift to the state, and (c) the intermediate and final results are written back to the original L2 / DRAM (130/108) via the IOB 142.

  In general, DTE 370 is a state machine that can be implemented using hardware, software, or a combination of hardware / software. In some embodiments, DTE 370 is implemented in hardware using combinatorial logic. In other embodiments, each DTE 370 is implemented on a different processor. In yet other embodiments, DTE 370 is implemented using a common processor. For example, each DTE 370 may be a separate task (ie, instruction sequence) that executes on a common processor that is adapted to provide a shared multitasking environment. Multitasking is a technology that shares a single processor among multiple independent jobs (ie, DTE 370) in an operating system. Additionally or alternatively, each DTE 370 may be a separate process thread executing on a common processor adapted to provide multithreading capabilities. The difference between multithreading and multitasking is that threads generally share more of their environment with each other than performing tasks under multitasking. For example, multiple threads may share a single address space and global variable set, while each thread can be distinguished by the thread's program counter and stack pointer values.

  FIG. 4A shows the structure of the DFA instruction queue 400 stored in the L2 / DRAM (130/108). Each instruction queue is a linked list of chunks or buffers 402. Each chunk 402 includes at least three DFA instructions 404, and these three instructions constitute an overall chunk size 406. If there is another chunk (eg, 402 '), the next chunk buffer pointer 408 immediately follows the last DFA instruction 404 in the chunk 402.

  To insert a packet into the DFA instruction queue 400, the core 120 software writes the DFA instruction 404 into the DFA instruction queue 400, assigns a chunk if necessary, and then into the DFA doorbell 384, into the DFA instruction queue 400. Write the number of DFA instructions 404 added. The DFA module 134 reads the DFA instruction queue 400 (starting from the tail 410) and upon reaching the last instruction in the chunk (eg 404/404 ′ ″), the next chunk (eg 402 ′ / 402 ″). The next chunk buffer pointer 408 pointing to) is scanned. When the chunk 402 is thus jumped, the DFA module 134 releases the previous chunk (eg, 402/402 ') to the FPA 128 (FIG. 1B).

  The DFA module 134 maintains the tail pointer 410 of the DFA instruction queue 400, and the core 120 software maintains the head pointer 412 of the DFA instruction queue 400. The distance between the tail pointer 410 and the head pointer 412 is equal to both the size of the DFA instruction queue 400 and the outstanding doorbell count. The size of the DFA instruction queue 400 is limited only by the available memory and the in-process doorbell counter, which is 20 bits for the DFA instruction queue 400.

  FIG. 4B shows the next chunk buffer pointer format 450. The next chunk buffer pointer is a 64-bit word and includes a 36-bit address (Addr) field 452. Addr field 452 selects a valid L2 / DRAM (130/108) byte location of the next chunk 400 containing the next DFA instruction 402. The Addr field 452 is a byte address, which is naturally aligned on a 128-byte cache block boundary by setting its least significant 7 bits to zero.

  FIG. 5A shows the structure of the DFA graph 500 stored in the LLM 118. The DFA graph 500 includes N nodes 510a to 510n. Each node 510 in the DFA graph 500 is simply an array of 256 next node pointers 512, each of which is unique to the input byte value. Each next node pointer 512 includes a next node ID 514 that directly specifies the next node / state of the input byte.

  The DFA module 134 supports either an 18-bit next node pointer storage format 516 or a 36-bit next node pointer storage format 518. For an 18-bit pointer, each node 510 requires 18 * 256 bits or 512 bytes of LLM 118 storage. Each next node pointer 516 is a 17-bit next node ID and a 1-bit parity bit. The parity is an even number (ie, P is an XOR (exclusive OR) of all bits in the 17-bit next node ID 514). For a 36-bit pointer, each node 510 requires 36 * 256 bits or approximately 1 kilobyte of LLM 118 storage. Thus, duplication increases the capacity requirements for storage. Each next node pointer 518 is a 20 bit next node ID, a 2 bit type value, a 7 bit SECDED ECC code, and an unused 7 bit set to zero. The DTE 370 automatically corrects all single bit errors using the SECDED ECC code in the 36 bit pointer and detects all double bit errors. The type value indicates the type of the next node, for example, 0 = normal, 1 = marked, 2 = terminal.

DTE 370 supports the following three special node pointer conditions:
1. PERR-the next node pointer contains an error. DTE 370 generates a result word that displays the location of the defective LLM 118. The DTE 370 stops scanning the graph 500.
2. TERM—The next node is a terminal node and the graph traversal should stop. The DTE 370 generates a result word that displays the scanned byte to the end node, the previous node ID, and the next node ID. The DTE 370 stops scanning the graph 500.
3. MARKED-This transition is marked for later analysis by the core 120 software. The DTE 370 generates a result word that displays the scanned byte to the marked node, the previous node ID, and the next node ID. DTE 370 continues scanning graph 500.

  For 18-bit mode, DTE 370 determines special TERM and MARKED conditions by comparing the next node ID. In this case, all transitions that enter the marked node are marked. For 36-bit mode, DTE 370 determines special TERM and MARKED conditions directly from the type field in the next node pointer. In 36-bit mode, individual transitions can be marked rather than individual nodes themselves.

  FIG. 5B reveals all of the possible 17-bit node IDs and how they are classified in 18-bit mode. The end node ID 502 is not backed up by being actually stored in the LLM 118. However, the normal node 504 and the marked node 506 are backed up by storage in the actual LLM 118. The DFA instruction 404 includes the number 503 of terminal nodes that are TSize (FIG. 8A) stored in IWORD3 (FIG. 8A) and the number of marked nodes 507 that are MSize (FIG. 8A) stored in IWORD3. including.

  The DTE 370 generates a result word when an exceptional condition occurs while scanning the graph 500. The next node pointer that is MARKED, TERM or PERR is such an exceptional condition. There are two more exceptional conditions: input data completion and result space exhaustion. While scanning the graph for input bytes may result in multiple exceptional conditions, at most one result word can be generated from a single input byte. For example, when the last input byte encounters a completion condition for input data, it generates a result word. The next node marked with the last input byte may also be encountered, but no second result word is generated. The graph scan stops (in order of preference) at the occurrence of exceptional conditions such as PERR, TERM, input data completion and result space exhaustion, and DTE 370 reports its highest priority condition. For example, referring to the graph of FIG. 2, the next node is the terminal node when node “c” is reached, and DTE 370 stops scanning the graph.

  Each DFA instruction can specify by DTE 370 how data to be processed is stored in L2 / DRAM (direct or gathered). In either case, the DFA module 134 reads bytes from the L2 / DRAM (130/108).

  FIG. 6 shows an exemplary direct mode 600 for acquiring data processed by the DTE 370. The DFA instruction 404 directly specifies the start position and the number of bytes. The DTE 370 that processes the corresponding DFA instruction 404 reads consecutive bytes from the L2 / DRAM (130/108) and processes them.

  FIG. 7A shows an exemplary gather mode 700 for acquiring data processed by the DTE 370. The DFA instruction 404 directly specifies the starting position and size of the list of DFA gather pointers 710. Each entry in the DFA gather pointer 710 list specifies the starting position and the number of bytes that the DTE 370 processes. The entire input byte stream of DTE 370 is a concatenation of bytes specified by each entry in the DFA gather pointer 710 list.

  FIG. 7B shows the format of a 64-bit DFA gather pointer 710. The DFA gather pointer 710 includes a length 712 (number of bytes) and an address field 714 (L2 / DRAM address). The DFA gather pointer 710 is naturally aligned on a 64-bit boundary, but the bytes in the L2 / DRAM pointed to by these pointers may or may not be aligned. In the gather mode 700, the total number of bytes is the sum of the length fields in all DFA gather pointers 710.

  Referring back to FIG. 4A, each DFA instruction 404 provides the information needed by the DFA module 134 to (i) start the DTE 370, (ii) read the input data, and (iii) in the LLM 118 The graph 200 is scanned and (iv) the result is written. The DFA instruction 404 may include multiple instruction words, such as the exemplary DFA instruction format shown in FIG. 8A. Each DFA instruction 404 includes four independent words, 455 ', 455 ", 455" ", 455" "(collectively 455). Each of these words contains 64 bits and is represented by a total of 32 bytes in the level 2 cache memory 130 or DRAM 108. Preferably, each DFA instruction 404 is naturally aligned on a 32-byte boundary. The DFA instruction 404 is processed by the individual DTE 370 for which this instruction is scheduled. The DFA instruction 404 includes a field that identifies both the position of the input byte and the position of the result.

  In operation, the DFA module 134 reads the DFA instruction 404 and input data from the level 2 cache memory 130 or the DRAM 108 and generates a result if the DFA instruction queue 382 has a valid DFA instruction 404 and generates a result. Is written (for example, every byte). The DFA module 134 can also send work queue entries that are scheduled by the POW 148 (FIG. 1B) after termination at any time, so the DFA instruction 404 can also include a field for the work queue pointer.

  More specifically, the first DFA instruction word 455 'includes a start node ID 460 that specifies the particular DFA graph used by that first node. The first word 455 ′ also provides additional information such as a duplicate field 462 that stores a duplicate value corresponding to the number of duplicates of the identified graph stored in the LLM 118. A type value 464 (18 or 36 bits) indicating the type of addressing used may also be provided. An exemplary 64-bit word also includes one or more reserved fields.

  The second DFA instruction word 455 ″ includes a length field 470 that specifies the number of bytes processed by the DFA module 134 and an address field 474 that specifies the location of the processed packet data in the level 2 cache memory 130 or DRAM 108. Including.

  The third DFA instruction word 455 ′ ″ indicates a result address field 482 that identifies the address (eg, an address in the level 2 cache memory 130 or DRAM 108) where any result is written, and the maximum number of results allowed. And a maximum result field 480 for storing values. Further, since the DFA module 134 can optionally send a work queue entry after termination, the DFA instruction 404 includes a work queue processing (WQP) field 490 for one or more work queue pointers.

  FIG. 8B shows the result format 800 of the DFA instruction 404. The DFA result 800 has two or more 64-bit words in L2 / DRAM (130/108). Each word is naturally aligned in the L2 / DRAM (130/108). The DFA module 134 writes these words to the L2 / DRAM (130/108) during and after the processing of the DFA instruction 404. This structure is variable length and contains a DFA instruction 404 that hits a variable number of marked nodes, but the length of the result may be limited by the upper limit of the maximum result in the DFA instruction field.

  As mentioned earlier, a node type can be associated with any one or more of the nodes of the DFA graph by using a type field with a 36-bit pointer 518 (FIG. 5A). . DTE 370 generates a result word when an exceptional condition occurs while scanning the graph. At least one exceptional condition is a terminal node. When DTE 370 reaches the end node, this node indicates that the DFA graph has reached the end, and scanning by DTE 370 stops. Another example of an exceptional condition is a marked node. In contrast to the terminal node, the scanning of the graph does not necessarily stop when the DTE 370 reaches the marked node. However, the output word is written with results identifying the particular marked node for later analysis. Thus, the marked nodes can be used to identify when the corresponding node in the graph is scanned.

  WORD 0 of the DFA result 800 may be written more than once by the DFA module 134. Only the last write to WORD0 contains a valid DFA result 800. The DFA module 134 can write WORD0 multiple times, but bit 16 can only be set for the last write. That is, bit 16 is not set by DFA module 134 until DFA module 134 completes DFA instruction 404. By writing zero to WORD0 result bit 16 before passing DFA instruction 404 to DFA module 134, the software polls WORD0 bit 16 to determine when DFA module 134 has completed DFA instruction 404. be able to. When WORD0 of the DFA result is set, the entire result exists.

  In another example shown in FIG. 2B, the graph of FIG. 2A is expanded to find one or more occurrences of two different strings “abcd” and “abce”. Thus, two additional nodes have been added to the graph of FIG. 2A, ie, nodes 4 and 5 (eg, node 4 for “d” and node 5 for “e”), one node for each string For 4 characters. Since each character string has the same first three characters, the nodes 4 and 5 are connected to the node 3 as shown in the figure. Preferably, all occurrences of any string are identified on a single “path” through the input string.

  An exemplary input string, such as the string “xwabcd454abceabcdfsfk”, passes through the DFA, resulting in three “marked” transitions. The marked transition occurs at the end of the string segment placed in the input string (eg, one at each position where “d” or “e” is present). Thus, the three marked transitions represent that three strings have been found. The first and last marks indicate the transition from node 3 to node 4 and represent the presence and position of the string “abcd” in the input string (ie, DTE byte = 5, leading = 3, next = 4 and DTE Byte = 17, predecessor = 3, next = 4). The center marked node indicates the transition from node 3 to node 5 and represents the presence of the string “abce” in the input string (ie DTE byte = 13, predecessor = 3, next = 5). . Nodes 4 and 5 are marked using an 18-bit pointer, and the arc from node 3 to nodes 4 and 5 is marked using a 36-bit pointer. Thus, by using DFA marking technology in combination with the DFA thread engine, the presence and position of multiple different strings within the same input string can be found in a single pass through the input string. .

  This application is based on US Provisional Patent Application No. 60 / 609,211 filed on September 10, 2004, US Patent Application No. 11 / 024,002 filed on December 28, 2004, April 8, 2005. U.S. Provisional Patent Application No. 60 / 669,603 entitled `` Deterministic Finite Automata (DFA) Instruction '' and U.S. Provisional Patent Application No. 60 / entitled `` Selective Replication of Data Structures '' filed April 8, 2005 Related to 669,655. The entire contents of the above-mentioned applications are hereby incorporated by reference.

  Although the invention has been shown and described in detail in connection with preferred embodiments thereof, those skilled in the art will recognize in form and detail without departing from the scope of the invention as encompassed by the appended claims. It will be understood that various changes may be made.

1 is a block diagram illustrating a network service processing system including a network service processor according to the principles of the present invention. FIG. 1B is a block diagram illustrating the network service processor shown in FIG. 1A. FIG. 3 is a schematic diagram illustrating an exemplary DFA graph. FIG. 3 is a schematic diagram illustrating an exemplary DFA graph. 1 is a block diagram illustrating a reduced instruction set computer (RISC) processor in accordance with the principles of the present invention. FIG. 3B is a block diagram illustrating the DFA module of FIG. 3A. FIG. FIG. 6 illustrates a structure of a DFA instruction queue. It is a figure which shows the command format of the next chunk buffer pointer. FIG. 6 illustrates another embodiment of a typical DFA graph. FIG. 5B shows different possible node IDs of the DFA graph of FIG. 5A. FIG. 6 is a diagram illustrating an example of a direct mode for configuring data processed by a DTE. It is a figure which shows an example of the gather mode for comprising the data processed by DTE. It is a figure which shows the command format of a DFA gather pointer. It is a figure which shows a DFA instruction format. It is a figure which shows a DFA result format.

Explanation of symbols

110 processor 120 processor core 400 DFA module

Claims (18)

At least one processor core;
A deterministic finite automaton (DFA) module operating asynchronously with the at least one processor core, wherein a plurality of at least one DFA graph stored in non-cache memory in response to an instruction from the at least one processor core And a DFA module that scans the nodes using packet data stored in cache coherent memory. The DFA module according to claim 1, wherein
A non-cache memory controller adapted to access a memory storing the DFA graph;
At least one DFA thread engine in communication with the non-cache memory controller;
A network processor having instruction input logic adapted to schedule instructions from the at least one processor core to the at least one DFA thread engine.   The network processor according to claim 2, further comprising an instruction queue, wherein the at least one processor core sends a DFA instruction to the DFA module to the instruction queue.   4. The network processor according to claim 3, wherein the DFA module maintains a pointer to the instruction queue.   The network processor according to claim 3, wherein the DFA instruction directs packet data stored in cache coherent memory for use and directs at least one DFA graph stored in non-cache memory for scanning.   4. The network processor according to claim 3, wherein the DFA module schedules DFA instructions to the at least one DFA thread engine. 7. The at least one DFA thread engine according to claim 6,
Fetching packet data stored in the cache coherent memory;
Issuing a non-cache memory load instruction for each byte of packet data received from the cache coherent memory, and scanning the next state of the DFA graph stored in the non-cache memory;
A network processor that writes intermediate and final results to the cache coherent memory.   8. The network processor according to claim 7, further comprising a result word into which the intermediate and final results are written.   9. The network processor of claim 8, wherein the result word includes an instruction completion field, and this field indicates completion of a DFA instruction if this field is set. The DFA module according to claim 1, wherein
A plurality of DFA thread engines associated with the at least one processor core in a common environment setting, wherein each DFA thread engine scans at least one DFA graph stored in the non-cache memory; Network processor that is adapted.   The network processor according to claim 1, further comprising a node type identifier that identifies a node type of the DFA graph.   12. The network processor of claim 11, wherein the node type identifier is a marked node, and scanning of the marked node does not interfere with graph scanning. A method of scanning a DFA graph using input packet data,
Storing at least one DFA graph in a non-cache coherent memory;
Storing a DFA instruction in a cache coherent memory, wherein the DFA instruction directs the packet data stored in the cache coherent memory for use, and at least one DFA graph stored in the non-cache memory. Directing for scanning; and
Scanning the DFA graph with the stored packet data and writing intermediate and final results to the cache coherent memory.   14. The DFA graph scanning method according to claim 13, wherein at least one processor core sends a DFA instruction to the DFA module.   15. The DFA graph scanning method according to claim 14, wherein a DFA module schedules a DFA instruction to the at least one DFA thread engine. 16. The at least one DFA thread engine according to claim 15, wherein
Fetching packet data stored in the cache coherent memory;
Issuing one non-cache memory load instruction for each byte of packet data fetched from the cache coherent memory;
According to the fetched packet data byte, the next state of the DFA graph stored in the non-cache memory is scanned,
A DFA graph scanning method for writing intermediate and final results to the cache coherent memory.   17. The DFA graph scanning method of claim 16, further comprising providing a node type identifier that identifies an individual node type for each node of the DFA graph, wherein the intermediate and final results are determined from the node type identifier. Means for storing at least one DFA graph in non-cache coherent memory;
Means for storing a DFA instruction in a cache coherent memory, wherein the DFA instruction directs the packet data stored in the cache coherent memory for use and is stored in the non-cache memory; Means for directing for scanning;
A network processor comprising means for scanning the DFA graph using the stored packet data and writing intermediate and final results to the cache coherent memory.

Images