Lossless real-time line-rate filtering using PCAP style filters and hardware assisted patricia trees
View Patent ↗A processor performs line-rate filtering using hardware-assisted Patricia trees. A PCAP-style filter is converted into a form that can be inserted into a Patricia tree. The PCAP filter expression is parsed and converted into disjunctive normal form (DNF). Each DNF clause of the filter is inserted into a Patricia tree. The DNF clauses are checked for overlaps and the overlapping clauses are combined when possible.
1. A method, comprising:
defining an operator stack in a memory, the operator stack adapted to store binary logical operators;
defining a value stack in the memory, the value stack adapted to contain pointers to nodes of a filter expression tree;
parsing the filter expression on an element-by-element basis, elements of the filter expression comprising operators and values, wherein for each next element in the filter expression:
if the next element in the filter expression is a value, then adding the value to the value stack; and
if the next element in the filter expression is an operator, then comparing the next element to a top element in the operator stack, and performing an action defined a decision table based upon the next element and the top element;
removing a completed binary tree from the value stack;
defining stacks in a memory corresponding to a left sub-tree stack (L-stack), a right sub-tree stack (R-stack), a result of left sub-tree stack (RL-stack), and a result of right sub-tree stack (RR-stack);
performing a post-order traversal of the nodes of the completed binary tree in which each node of completed binary tree is visited, wherein during the post-order traversal:
if a node is a leaf node, then insert the operation allocated to the leaf node to the L-stack if the leaf node is a left child or insert the operation allocated to the leaf node to the R-stack if the leaf node is a right child; and
if the node is a non-leaf node, then processing the non-leaf node based upon whether the operation contains an OR operation or an AND operation, wherein the processing moves data into the RL-stack or the RR-stack;
processing a root node of the binary tree;
removing the disjunctive normal form of the filter expression from the RL-stack or the RR-stack corresponding to the root node; and
identifying overlapping keys from the disjunctive normal form of the filter expression.
2. The method of claim 1 , further comprising:
if the non-leaf node contains an OR operation and children nodes of the non-leaf node are leaf nodes, then:
moving all nodes from the R-stack and L-stack into the RL-stack if the non-leaf node is a left child; or
moving all nodes from the R-stack and L-stack into the RR-stack if the non-leaf node is a right child.
3. The method of claim 1 , further comprising:
if the non-leaf node contains an OR operation and children nodes of the non-leaf node are not leaf nodes, then:
moving all nodes from the RR-stack and the RL-stack into the RL-stack if the non-leaf node is a left child, or
moving all nodes from the RR-stack and the RL-stack into the RR-stack if the non-leaf node is a right child.
4. The method of claim 1 , further comprising:
if the non-leaf node contains an AND operation and children nodes of the non-leaf node are leaf nodes, then:
combining every node in the R-stack with every node in the L-stack to create a single conjunctive clause.
5. The method of claim 4 , further comprising:
inserting the single conjunctive clause into the RL-stack if the non-leaf node is a left child; or
inserting the single conjunctive clause into the RR-stack if the non-leaf node is a right child.
6. The method of claim 1 , wherein the root node is treated as a left child during the processing.
7. A non-transistory computer-readable storage medium having program instructions stored thereon that, upon execution by a processor within a computer system, cause the computer system to:
define an operator stack in a memory, the operator stack adapted to store binary logical operators;
define a value stack in the memory, the value stack adapted to contain pointers to nodes of a filter expression tree;
parse the filter expression on an element-by-element basis, elements of the filter expression comprising operators and values, wherein for each next element in the filter expression:
if the next element in the filter expression is a value, then add the value to the value stack; and
if the next element in the filter expression is an operator, then compare the next element to a top element in the operator stack, and perform an action defined a decision table based upon the next element and the top element;
remove a completed binary tree from the value stack;
define stacks in a memory corresponding to a left sub-tree stack (L-stack), a right sub-tree stack (R-stack), a result of left sub-tree stack (RL-stack), and a result of right sub-tree stack (RR-stack);
perform a post-order traversal of the nodes of the completed binary tree in which each node of completed binary tree is visited, wherein during the post-order traversal:
if a node is a leaf node, then insert the operation allocated to the leaf node to the L-stack if the leaf node is a left child or insert the operation allocated to the leaf node to the R-stack if the leaf node is a right child; and
if the node is a non-leaf node, then process the non-leaf node based upon whether the operation contains an OR operation or an AND operation, wherein the processing moves data into the RL-stack or the RR-stack;
process a root node of the binary tree;
remove the disjunctive normal form of the filter expression from the RL-stack or the RR-stack corresponding to the root node; and
identify overlapping keys from the disjunctive normal form of the filter expression.
8. The non-transistory computer-readable storage medium of claim 7 , wherein the program instructions, upon execution by the processor, further cause the computer system to:
(a) if the non-leaf node contains an OR operation and children nodes of the non-leaf node are leaf nodes, then:
move all nodes from the R-stack and L-stack into the RL-stack if the non-leaf node is a left child, or
move all nodes from the R-stack and L-stack into the RR-stack if the non-leaf node is a right child;
(b) if the non-leaf node contains an OR operation and children nodes of the non-leaf node are not leaf nodes, then:
move all nodes from the RR-stack and the RL-stack into the RL-stack if the non-leaf node is a left child, or
move all nodes from the RR-stack and the RL-stack into the RR-stack if the non-leaf node is a right child; or
(c) if the non-leaf node contains an AND operation and children nodes of the non-leaf node are leaf nodes, then:
combine every node in the R-stack with every node in the L-stack to create a single conjunctive clause,
insert the single conjunctive clause into the RL-stack if the non-leaf node is a left child, or
insert the single conjunctive clause into the RR-stack if the non-leaf node is a right child.
9. The non-transitory computer-readable storage medium of claim 7 , wherein the program instructions, upon execution by the processor, further cause the computer system to:
remove all NOT operations from nodes of the completed binary tree.