CN115865843B

CN115865843B - Rule storage method, message processing method, device, electronic equipment and medium

Info

Publication number: CN115865843B
Application number: CN202211336843.XA
Authority: CN
Inventors: 胡卓; 罗彬�
Original assignee: New H3C Semiconductor Technology Co Ltd
Current assignee: New H3C Semiconductor Technology Co Ltd
Priority date: 2022-10-28
Filing date: 2022-10-28
Publication date: 2024-11-19
Anticipated expiration: 2042-10-28
Also published as: CN115865843A

Abstract

The embodiment of the present application provides a rule storage method, a message processing method, an apparatus, an electronic device and a medium, which relates to the field of communication technology. The method is applied to an electronic device, and a RAM is provided in the electronic device. The method comprises: obtaining a rule to be stored, wherein the rule to be stored comprises a matching domain, and the matching domain comprises target rule data, and the target rule data is a key value and a mask in the matching domain; converting the target rule data into at least one check block, and storing the target rule data in the RAM in the form of a check block; wherein the types of the check blocks include a mask type and a non-mask type, and the rule data in the check block of the mask type comprises a key value and a mask, and the rule data in the check block of the non-mask type comprises a key value with a continuous effective bit, and the effective bit is a bit with a mask value of 1. The storage space of the RAM can be saved.

Description

Rule storage method, message processing method, device, electronic equipment and medium

Technical Field

The present invention relates to the field of communications technologies, and in particular, to a rule storage method, a message processing method, a device, an electronic apparatus, and a medium.

Background

Access control lists (Access Control Lists, ACLs) are widely used in electronic devices such as routers and switches. An ACL comprises a set of rules for identifying messages, which are judgment sentences for describing the matching condition of a message, for example, the matching condition can be the source address, the destination address, the port number, etc. of the message. The electronic device can match the received message according to the rule in the ACL, and process the matched message according to a preset strategy. The electronic device can implement traffic such as message filtering, routing, network security, and quality of service (Quality of Service, qoS) through ACLs.

The rules in the ACL may be stored through a random access memory (Random Access Memory, RAM) at present, the matching field of each rule may be converted into two parts, key (key value) and mask (mask), the matching field of each rule is stored in the form of key and mask, key represents a specific value of each field in the rule, key may be referred to as prefix, mask represents which values in the key need to be matched, i.e. is used to indicate the valid bits in the key. As the size of rules included in ACLs increases, a significant amount of memory space in RAM will be consumed.

Disclosure of Invention

The embodiment of the invention aims to provide a rule storage method, a message processing device, electronic equipment and a medium, so as to reduce occupation of storage space of a RAM. The specific technical scheme is as follows:

In a first aspect, the present application provides a rule storage method, where the method is applied to an electronic device, and a RAM is disposed in the electronic device, and the method includes:

Acquiring a rule to be stored, wherein the rule to be stored comprises a matching domain, the matching domain comprises target rule data, and the target rule data is a key value and a mask in the matching domain;

Converting the target rule data into at least one check block, and storing the target rule data in the RAM in the form of the check block;

The types of the check blocks comprise a mask type and a non-mask type, the rule data in the check blocks of the mask type comprise key values and masks, the rule data in the check blocks of the non-mask type comprise key values with continuous effective bits, and the effective bits are bits with mask values of 1.

In one possible implementation manner, the converting the target rule data into at least one check block includes:

Taking the first effective bit of the target rule data as the current start bit, and converting the rule data of the continuous first number of bits into a check block based on the coding conditions satisfied by the rule data of the continuous first number of bits starting from the current start bit; the first number is smaller than or equal to the CPU bit width of the electronic equipment and is larger than the preset number, and the preset number is the number of bits used for storing key values in the check block of the mask type;

Searching a first effective bit from bits which are not converted into check blocks in the target rule data, taking the searched effective bit as the current starting bit, returning to the coding condition which is met based on the rule data of the continuous first number of bits starting from the current starting bit, and converting the rule data of the continuous first number of bits into one check block until the rule data of the effective bit included in the target rule data are converted into the check blocks.

In one possible implementation manner, the converting the rule data of the consecutive first number of bits into a check block based on the encoding condition satisfied by the rule data of the consecutive first number of bits starting from the current start bit includes:

Judging whether the rule data of the continuous first number of bits meets the coding condition of a non-mask type or not;

If yes, converting a key value in the rule data with the continuous first number of bits into a check block with the non-mask type;

If the first number is not satisfied, determining that the first number is the preset number, and converting the key value and the mask in the rule data with the continuous first number of bits into the check block with the mask type.

In one possible implementation, the non-mask type includes a full data type, a first length type, and a second length type;

The encoding conditions of the all-data type include: the current start bit is the first bit of one byte included in the target rule data; and in the mask of the target rule data, the values of the bits of the continuous CPU bit width from the current start bit are all 1, and the first quantity is the CPU bit width;

The encoding conditions of the first length type include: the current start bit is the first bit of one byte included in the target rule data; and in the mask of the target rule data, starting from the current start bit, the values of the first number of bits are all 1, and the first number is smaller than the difference value between the CPU bit width and the number of bits occupied by the check block type field;

the encoding conditions of the second length type include: the current start bit is not the first bit of one byte included in the target rule data; and in the mask of the target rule data, starting from the current start bit, the values of the first number of bits are all 1, wherein the first number is smaller than the difference value between the CPU bit width and the bit number occupied by the check block type field and the bit number occupied by the start bit field;

the determining whether the rule data of the consecutive first number of bits satisfies a non-mask type encoding condition includes:

If the continuous first number of bits of rule data meets any one of the encoding conditions of the full data type, the first length type and the second length type, determining that the encoding condition of the non-mask type is met; otherwise, it is determined that the encoding condition of the non-mask type is not satisfied.

In one possible implementation, the converting the key value in the rule data of the consecutive first number of bits into the check block of the non-mask type includes:

If the rule data of the continuous first number of bits meets the coding condition of the all-data type, converting a key value in the rule data of the continuous first number of bits into a check block of the all-data type;

If the continuous first-number-bit rule data meets the coding conditions of the first length type and does not meet the coding conditions of the full data type, converting a key value in the continuous first-number-bit rule data into a check block of the first length type;

And if the rule data of the continuous first number of bits meets the coding condition of the second length type, converting the rule data of the continuous first number of bits into a check block of the second length type.

In one possible implementation, the check block of the all-data type is used to store a key value in the rule data of the consecutive first number of bits;

The lowest three bits of the check block of the first length type are used for storing type codes of the first length type, and the last three bits from the highest bit to the fourth last bit are used for storing: the key value and one 0 in the rule data of the first number of bits, and the value of the unoccupied bit is default set to be 1;

the highest three bits in the check block of the second length type are used for storing the offset of the current start bit in the byte, the lowest three bits are used for storing the type code of the second length type, and the rest bits are sequentially used for storing: the key value and one 0 in the rule data of the continuous first number of bits, and the unoccupied bit position defaults to 1;

The highest three bits in the check block of the mask type are used for storing the offset of the current start bit in the byte, the lowest three bits are used for storing the type code of the mask type, and the rest bits are sequentially used for storing: key values and masks in the sequential first number of bits of rule data.

In one possible implementation, the method further includes:

If the target rule data comprises rule data of a range type, and the maximum value and the minimum value of the rule data of the range type are smaller than 2 ¹³, converting the rule data of the range type into a check block of a first range type;

If the minimum value of the rule data of the range type is more than or equal to 2 ¹³ or the maximum value of the rule data of the range type is more than or equal to 2 ¹³, converting the rule data of the range type into a check block of a second range type and a check block of a third range type;

Wherein the highest 13 bits of the check block of the first range type are used for storing the maximum value, the next 13 bits are used for storing the minimum value, the next 2 bits are used for storing a first subtype code, the lowest 3 bits are used for storing the code of the range type, and the first subtype code is used for indicating that the check block comprises a matching range;

The highest 26 bits of the second range type check block are used for storing the minimum value, the next two bits are used for storing a second subtype code, the lowest 3 bits are used for storing the range type code, and the second subtype code is used for indicating that the check block comprises the minimum value of a matching range;

the highest 26 bits of the check block of the third range type are used for storing the maximum value, the next two bits are used for storing a third subtype code, the lowest 3 bits are used for storing the code of the range type, and the third subtype code is used for indicating that the check block comprises the maximum value of a matching range.

In one possible implementation, each check block stored in the RAM includes a byte offset field before each check block, where the byte offset field before each check block is used to indicate a byte offset of a start bit of rule data in the check block in target rule data.

In one possible implementation manner, the acquiring the rule to be stored includes:

Acquiring a global rule set and a common rule of a plurality of rules included in the global rule set;

Generating a pending rule corresponding to each rule included in the global rule set based on the public rule, and taking each pending rule as the rule to be stored; for each bit, if one rule is the same as the value of the common rule corresponding to the rule in the bit, the value of the pending rule corresponding to the rule in the bit is a wildcard, otherwise, the value of the pending rule corresponding to the rule in the bit is the same as the value of the rule in the bit.

In a second aspect, the present application provides a method for processing a message, where the method is applied to an electronic device, where a random access memory RAM is provided in the electronic device, and target rule data in a matching domain of each rule in a specified rule table of the RAM is stored in a form of a check block, where a type of the check block includes a mask type and a non-mask type, rule data in the check block of the mask type includes a key value and a mask, and rule data in the check block of the non-mask type includes a key value with continuous effective bits, and the effective bits are bits with a mask value of 1; characterized in that the method comprises:

Extracting a searching key value from a message to be processed;

determining rules to be matched in the specified rule table based on the search key value;

Determining the length of data to be matched according to the type of each check block aiming at each check block included in the rule to be matched;

extracting data to be matched according to the length of the data to be matched from the same initial bit in the searching key value according to the initial bit of the rule data included in the check block, and matching the data to be matched with the rule data included in the check block;

If the searching key value is successfully matched with all check blocks in the rule to be matched, determining that the searching key value is successfully matched with the rule to be matched;

and processing the message to be processed based on the matching result of the searching key value and the rule to be matched.

In a possible implementation manner, a linear table is also stored in the RAM, and the linear table includes a plurality of base addresses, and the base addresses are used for locating the block rule table; the determining the rule to be matched in the specified rule table based on the search key value comprises the following steps:

Taking bits in a preset range in the search key value as a search index, and determining a target base address pointed by the search index in the linear table;

based on the target base address positioning block rule table, taking the positioned block rule table as the appointed rule table;

And taking the rule included in the specified rule table as a rule to be matched.

In one possible implementation manner, the electronic device is further provided with a ternary content addressable memory TCAM, a public rule table is stored in the TCAM, and a main rule table and a block rule table are stored in the RAM:

the block rule table stores a plurality of rules with the same common rule;

The main rule table at least comprises two fields, namely a split position set and a base address, wherein the rules in the block rule table belong to a subtree determined by the split position set, the split position set is used for positioning the position of the rule corresponding to the key value in the block rule table, the base address is used for positioning the block rule table, and the value of a non-wildcard bit in the common rule is the same as the value of the same bit of all rules in the block rule table pointed by the base address;

the public rule table stores public rules, and indexes of the public rule table and the main rule table corresponding to the same block rule table are the same;

The determining the rule to be matched in the specified rule table based on the search key value comprises the following steps:

Matching in the public rule table by using the searching key value to obtain a main index of a target table item in the main rule table;

based on a base address and a positioning block rule table included in the target table item pointed by the main index, taking the block rule table obtained by positioning as the appointed rule table;

Determining a secondary index of a rule to be matched in the appointed rule table based on the searching key value and a splitting position set included in the target table item pointed by the main index;

And taking the rule pointed by the secondary index as the rule to be matched.

In one possible implementation, the common rule table, the master rule table, and the block rule table are generated by:

constructing a rule decision tree based on balance bits of all rules in a global rule set, wherein the balance bits are the bit with the smallest difference value between the number of the rules with the value of 0 and the number of the rules with the value of 1 in all the bits;

traversing upwards from each leaf node of the rule decision tree according to breadth first to obtain the deepest rule subtree corresponding to each leaf node, wherein the deepest rule subtree is the deepest rule subtree in the rule subtree with the number of the balance bits smaller than or equal to the preset splitting bit depth;

the common rule table, the main rule table, and the block rule table are generated based on each deepest rule sub-tree.

In one possible implementation manner, the generating the public rule table, the main rule table and the block rule table based on each deepest rule subtree includes:

generating a block rule table based on rule sets included in each deepest rule subtree;

Generating a split position set based on balance bits included in each deepest rule subtree;

Generating a main rule table based on a splitting position set corresponding to each deepest rule subtree and a base address of the block rule table;

and generating the public rule table based on the table entry index in the main rule table corresponding to each deepest rule subtree and the public rule of the rule set included in each deepest rule subtree.

In one possible implementation manner, the step of constructing a rule decision tree based on balance bits of each rule in the global rule set includes:

taking a global rule set as a rule set to be split, wherein the global rule set is contained in a root node of a rule decision tree;

determining balance bits of each rule in the rule set to be split;

Adding the rule with the value of 0 in the balance bit in the rule set to be split into a first side child node, and adding the rule with the value of 1 in the balance bit in the rule set to be split into a second side child node;

And for each sub-node obtained by splitting, if the sub-node comprises a plurality of rules, taking a rule set included in the sub-node as a rule set to be split, and re-executing the step of determining the balance bit of each rule in the rule set to be split until each sub-node obtained by splitting comprises one rule, thereby obtaining the rule decision tree.

In one possible implementation manner, the processing the to-be-processed message based on the matching result of the search key value and the to-be-matched rule includes:

if the rule to be matched is one, and the searching key value is successfully matched with the rule to be matched, processing the message to be processed according to an action domain corresponding to the rule to be matched;

and if the number of the rules to be matched is multiple, processing the message to be processed according to an action domain corresponding to one rule to be matched which is successfully matched with the searching key value.

In one possible implementation manner, the determining the length of the data to be matched according to the type of the check block includes:

if the type of the check block is the mask type, determining that the length of the data to be matched is the length of the preset number of bits;

If the type of the check block is the full data type, determining that the length of the data to be matched is the CPU bit width of the electronic equipment;

If the type of the check block is the first length type or the second length type, searching a first bit with a value of 0 from the lowest bit to the highest bit of the rule data included in the check block, and determining the length of the data to be matched as the length from the highest bit to the searched bit;

And if the type of the check block is the range type, determining that the length of the data to be matched is the fixed length of the range type field.

In a possible implementation manner, the matching the data to be matched with the rule data included in the check block includes:

If the type of the check block is the mask type, performing AND operation on the key value and the mask in the check block, comparing a result obtained after the AND operation with the data to be matched, and if the result is completely consistent, successfully matching;

If the type of the check block is the full data type, comparing the data to be matched with all rule data in the check block, and if the data to be matched are completely consistent, successfully matching;

If the type of the check block is the first length type or the second length type, extracting rule data according to the length of the data to be matched from the highest bit of the rule data included in the check block, comparing the extracted rule data with the data to be matched, and if the rule data are completely consistent, successfully matching;

If the type of the check block is a range type, a matching range is obtained from the check block, and if the data to be matched belongs to the matching range, the matching is successful.

In a third aspect, the present application provides a rule storage apparatus applied to an electronic device in which a RAM is provided, the apparatus comprising:

The system comprises an acquisition module, a storage module and a storage module, wherein the acquisition module is used for acquiring a rule to be stored, the rule to be stored comprises a matching domain, the matching domain comprises target rule data, and the target rule data is a key value and a mask in the matching domain;

the conversion module is used for converting the target rule data into at least one check block;

the storage module is used for storing the target rule data in the RAM in the form of a check block;

In one possible implementation manner, the conversion module is specifically configured to:

In one possible implementation, the conversion module is further configured to:

In a fourth aspect, the present application provides a packet processing apparatus, where the apparatus is applied to an electronic device, where a random access memory RAM is provided in the electronic device, where target rule data in a matching domain of each rule in a specified rule table of the RAM is stored in a form of a check block, where a type of the check block includes a mask type and a non-mask type, where rule data in the mask type check block includes a key value and a mask, and rule data in the non-mask type check block includes a key value with a continuous effective bit, where the effective bit is a bit with a mask value of 1; characterized in that the device comprises:

The extraction module is used for extracting the search key value from the message to be processed;

The determining module is used for determining rules to be matched in the specified rule table based on the searching key value; determining the length of data to be matched according to the type of each check block aiming at each check block included in the rule to be matched;

the matching module is used for extracting data to be matched according to the length of the data to be matched from the same initial bit in the searching key value according to the initial bit of the rule data included in the check block, and matching the data to be matched with the rule data included in the check block; if the searching key value is successfully matched with all check blocks in the rule to be matched, determining that the searching key value is successfully matched with the rule to be matched;

And the processing module is used for processing the message to be processed based on the matching result of the searching key value and the rule to be matched.

In a possible implementation manner, a linear table is also stored in the RAM, and the linear table includes a plurality of base addresses, and the base addresses are used for locating the block rule table; the determining module is specifically configured to:

the block rule table stores a plurality of rules with the same common rule;

the determining module is specifically configured to:

And taking the rule pointed by the secondary index as the rule to be matched.

In a fifth aspect, an embodiment of the present application provides an electronic device, including a processor, a communication interface, a memory, and a communication bus, where the processor, the communication interface, and the memory complete communication with each other through the communication bus;

A memory for storing a computer program;

A processor configured to implement the method steps of the first or second aspect when executing a program stored on a memory.

In a sixth aspect, embodiments of the present application provide a computer readable storage medium having a computer program stored therein, which when executed by a processor, implements the method steps of the first or second aspects.

In a seventh aspect, embodiments of the present application also provide a computer program product comprising instructions which, when run on a computer, cause the computer to perform the method steps of the first or second aspects described above.

By adopting the technical scheme, the electronic equipment can convert the target data in the matching domain of the rule to be stored into at least one check block, the target rule data is stored in the RAM in the form of the check block, the type of the check block comprises a mask type and a non-mask type, the rule data in the check block of the mask type comprises a key value and a mask, and the rule data in the check block of the non-mask type comprises a key value with continuous effective bit positions. It can be seen that the non-mask type check block does not include the mask in the rule data, so that it is unnecessary to store all masks in the rule to be stored, and occupation of the RAM storage space can be reduced.

Of course, it is not necessary for any one product or method of practicing the invention to achieve all of the advantages set forth above at the same time.

Drawings

In order to more clearly illustrate the embodiments of the invention or the technical solutions in the prior art, the drawings used in the embodiments or the description of the prior art will be briefly described below, and it is obvious that the drawings in the following description are only some embodiments of the invention, and other embodiments may be obtained according to these drawings to those skilled in the art.

FIG. 1 is a flowchart of a rule storage method according to an embodiment of the present application;

FIG. 2 is a flowchart of another rule storage method according to an embodiment of the present application;

FIG. 3a is a schematic diagram of a data structure of a check block according to an embodiment of the present application;

FIG. 3b is a schematic diagram of a data structure of another check block according to an embodiment of the present application;

FIG. 3c is a schematic diagram of a data structure of a check block according to another embodiment of the present application;

FIG. 4 is an exemplary schematic diagram of a storage manner of rule data according to an embodiment of the present application;

FIG. 5a is a schematic diagram of a data structure of a range type check block according to an embodiment of the present application;

FIG. 5b is a schematic diagram of a data structure of another range type check block according to an embodiment of the present application;

FIG. 5c is a schematic diagram of a data structure of a range type check block according to another embodiment of the present application;

FIG. 6 is an exemplary diagram of a method for encoding rules to be stored as check blocks according to an embodiment of the present application;

FIG. 7 is a flowchart of a message processing method according to an embodiment of the present application;

FIG. 8 is a schematic diagram of correspondence between a common rule table, a master rule table, and a block rule table according to an embodiment of the present application;

FIG. 9 is a flowchart of another message processing method according to an embodiment of the present application;

FIG. 10 is a flowchart of a method for generating a common rule table, a master rule table and a block rule table according to an embodiment of the present application;

FIG. 11 is a schematic diagram of a rule set provided by an embodiment of the present application;

FIG. 12 is a schematic diagram of a rule decision tree provided by an embodiment of the present application;

FIG. 13 is a flowchart of a method for constructing a rule decision tree according to an embodiment of the present application;

fig. 14 is a schematic structural diagram of a rule storage apparatus according to an embodiment of the present application;

fig. 15 is a schematic structural diagram of a message processing apparatus according to an embodiment of the present application;

Fig. 16 is a schematic structural diagram of an electronic device according to an embodiment of the present application.

Detailed Description

The following description of the embodiments of the present application will be made clearly and completely with reference to the accompanying drawings, in which it is apparent that the embodiments described are only some embodiments of the present application, but not all embodiments. Based on the embodiments of the present application, all other embodiments obtained by the person skilled in the art based on the present application are included in the scope of protection of the present application.

The tables used for classifying and forwarding the messages, such as an ACL, a flow table, a routing table and the like, comprise a series of rules used for identifying the messages, are widely applied to electronic equipment, such as routers, switches and the like, and take the ACL as an example, the electronic equipment can match the received messages according to the rules in the ACL and process the matched messages according to a preset strategy. The electronic device can implement traffic such as message filtering, routing, network security, and quality of service (Quality of Service, qoS) through ACLs.

The ACL includes a matching field and an action field, the matching field includes a plurality of matching fields, and the types of the matching fields may be prefix type, scope type, precision type or generic type, for example, as shown in table 1, N rules are exemplarily shown in table 1, and the matching field of each rule includes a source IP address, a destination IP address, a source port, a destination port and a protocol, that is, a message quintuple. The "×" in table 1 is the wild card.

TABLE 1

In storing the above-described respective types of matching fields in the matching field using the RAM, the electronic device converts the respective matching fields included in each rule into the form of keys and masks, and a key value (value) is used to indicate a key-specific value.

The prefix type field comprises a prefix value and a prefix length, wherein key is the prefix value, the first L bits of the mask are 1, and the remaining bits are 0, wherein L is the prefix length. For example, 10.0.8.3/24, 10.1.6.20/16, 10.0.3.8/24, 10.1.0.0/16, and 10.1.8.15/24 in Table 1 are prefix-like fields, 10.1.0.0/16 is taken as an example, the converted key is 00001010000000010000000000000000 in 2 scale, and mask is 11111111111111110000000000000000 in 2 scale.

The scope type field refers to a field including a scope, and if the information to be matched belongs to the scope, the matching is successful. For example, each of 0 to 1024 and 0 to 2048 in table 1 is a range class field. For the scope class field, both key and mask are 0. Since the specific range value in the range class field can be directly stored when the range class field in the rule is stored in the following embodiment of the application, the range class field does not need to be equivalently represented as a prefix value.

The exact class field refers to the field that needs to be exactly matched, e.g., 22 and 80 in table 1 are both exact class fields. For the precision class field, the key is a precision value and the mask is all 1. For example, 80 corresponds to a key of 1010000 and a mask of 1111111.

The wild-type field refers to a field in which all bits of the entire field are wild-type, for example, "x" in table 1 is the wild-type field. For the wild-type field, the key and mask are all 0.

When the RAM is used for storing the rules in the related technology, the RAM only supports two storage states of 0 and 1 and can not store the wildcards, so that the key and the mask of each rule need to be stored, the bit widths of the key and the mask in the same rule are the same, the occupied RAM storage space is higher, the access bandwidth is higher, and the searching efficiency is low.

In order to reduce occupation of RAM storage space, an embodiment of the present application provides a rule storage method, where the rule storage method is applied to an electronic device, and the electronic device is provided with a RAM, as shown in fig. 1, and the method includes:

S101, acquiring a rule to be stored, wherein the rule to be stored comprises a matching domain, the matching domain comprises target rule data, and the target rule data is a key value and a mask in the matching domain.

In combination with the above description, a matching field of a rule may include a plurality of matching fields, the matching fields are converted into a key and mask form, the key of each matching field included in the matching field is spliced in turn, and correspondingly, the mask of each matching field is spliced in turn, so that rule data included in the matching field can be obtained.

For example, if a rule matching field includes a source IP address field, a destination IP address field, a source port field, a destination port field, and a protocol field, these fields may be converted into a key and a mask, respectively, the keys of the source IP address field, the destination IP address field, the source port field, the destination port field, and the protocol field are sequentially spliced, and the masks of the source IP address field, the destination IP address field, the source port field, the destination port field, and the protocol field are sequentially spliced, and the rule data in the rule matching field includes the spliced key and the spliced mask.

S102, converting the target rule data into at least one check block, and storing the target rule data in the RAM in the form of the check block.

The types of the check blocks comprise a mask type and a non-mask type, the rule data in the check blocks of the mask type comprise key values and masks, the rule data in the check blocks of the non-mask type comprise key values with continuous effective bits, and the effective bits are bits with the mask value of 1. For example, if the key of the rule data is 00010 and the mask is 11100, the valid bit is the first 3 bits.

As an example, if the target rule data in the matching field of the rule to be stored is converted into 5 compressed blocks, when the matching field of the rule is stored in the RAM, the 5 check blocks may be stored without storing all keys and masks in the target rule data, so as to achieve the purpose of compressed storage.

By adopting the method, the electronic equipment can convert the target data in the matching domain of the rule to be stored into at least one check block, the target rule data is stored in the RAM in the form of the check block, the type of the check block comprises a mask type and a non-mask type, the rule data in the check block of the mask type comprises a key value and a mask, and the rule data in the check block of the non-mask type comprises a key value with continuous effective bit positions. It can be seen that the non-mask type check block does not include the mask in the rule data, so that it is unnecessary to store all masks in the rule to be stored, and occupation of the RAM storage space can be reduced.

In some embodiments of the present application, the step of obtaining the rule to be stored specifically includes:

a global rule set and common rules of a plurality of rules included in the global rule set are obtained. Generating a pending rule corresponding to each rule included in the global rule set based on the public rule, and taking each pending rule as a rule to be stored; for each bit, if one rule is the same as the value of the common rule corresponding to the rule in the bit, the value of the pending rule corresponding to the rule in the bit is a wildcard, otherwise, the value of the pending rule corresponding to the rule in the bit is the same as the value of the rule in the bit.

Alternatively, the rules in the global rule set may be divided into a plurality of block rule tables, each block rule table includes a plurality of rules having the same common rule, and the electronic device may generate, for each block rule table, a pending rule corresponding to each rule included in the block rule table.

Wherein each rule in the global rule set is represented in the form of a key and mask.

In embodiments of the present application, the electronic device may convert each rule in the global rule set to a binary form and then generate the pending rule based on the rule represented in the binary form.

The electronic device may convert each rule in the global rule set into a binary form by:

And (3) representing I as any bit in the rule, wherein the bit I of each rule has the following relationship with the key and the mask:

r [ I ] =0, representing mask [ I ] =1, key [ I ] =0;

r [ I ] =1, representing mask [ I ] =1, key [ I ] =1;

r [ I ] =, representing mask [ I ] =0, key [ I ] =0 or key [ I ] =1.

As shown in table 2, table 2 shows that the four rules R0 to R3 are expressed in binary form, and the common rule of R0 to R3 is 10×0.

TABLE 2

R0	100010
		R1	100111
R2	100101
		R3	100001
Public rule Head	100***

For each bit I in the global rule set, a solved rule (resolved) may be generated as follows.

Resolved [ I ] = R [ I ] if R [ I ] has determined correctness; if R [ I ] does not determine correctness, resolved =.

The bits for which correctness has been determined are the valid bits in the common rule, so the solved rule is the same as the common rule.

Further, the value of each bit of each rule in the global rule set may be traversed, generating a pending rule unresolved:

If R < I > is equal to resolved < I >, unresolved < I > =;

If R [ I ] is not equal to resolved [ I ], unresolved [ I ] = R [ I ].

As shown in table 3, R is one rule in the global rule set, resolved is the common rule corresponding to R.

At bit P0, R is the same as resolved, and R1 has determined correctness, then R1 = resolved = 1, unresolved=;

at bit P1, R is the same as resolved, R2 has determined correctness, then R1 = resolved = 0, unresolved=;

In the P2 bit, R is the same as resolved, and R3 has determined correctness, then R1 = resolved =, unresolved =;

At bit P3, R is the same as resolved, R4 has determined correctness, then R1 = resolved = 0, unresolved=;

At bit P4, R is different from resolved, and if no correctness is determined by R [5], R [1] = unresolved=0, reserved=;

at bit P5, R is the same as resolved, R [6] has determined correctness, then R [1] = resolved =, unresolved=;

At bit P6, R is different from resolved, and if no correctness is determined by R [7], then R [1] = unresolved=0, reserved=;

At bit P7, R is different from resolved in value, and if no correctness is determined for R [8], R [1] =unresolved=1, and reserved=.

TABLE 3 Table 3

From table 3, a pending rule unresolved= 0 x 01 can be obtained, and the pending rule can be used as the rule to be stored.

It should be noted that the rule to be stored may also be represented in the form of keys and masks.

After acquiring the rule to be stored, as shown in fig. 2, in S102, the target data is converted into at least one check block, which may be specifically implemented as S201 to S202.

S201, taking the first effective bit of the target rule data as the current start bit, and converting the rule data of the continuous first number of bits into a check block based on the coding conditions satisfied by the rule data of the continuous first number of bits starting from the current start bit.

The first number is smaller than or equal to the CPU bit width of the electronic equipment and larger than the preset number. The preset number is the number of bits in the check block of the mask type for storing the key value.

In the embodiment of the application, the sizes of all the check blocks are the same and are all CPU bit widths. For example, if the CPU bit width is 64 bits, the check block size is 64 bits, and the first number is 64 or less. If the CPU bit width is 32 bits, the check block size is 32 bits, and the first number is less than or equal to 32.

The number of bits for storing the key value in the check block of the preset number of mask types may be set based on the check block size. The fixed part of bits in the check block of the mask type are used to store the offset of the start bit inside the byte, the fixed other part of bits are used to store the type code, the remaining bits other than the two fixed bits are used to store the key value and the mask, and the number of bits used to store the key value is the same as the number of bits used to store the mask. The preset number is a value obtained by subtracting the number of the two fixed bits from the bit width of the check block and dividing by 2.

For example, if the CPU bit width is 32, the length of the check block is 32, where 3 bits are used to store the offset, 2 bits are used to store the type code, 13 bits of the remaining 26 bits are used to store the key value, and the other 13 bits are used to store the mask, the preset number may be 13.

It will be appreciated that if the rule data is represented in binary form, the first valid bit is the first bit whose value is not a wild card, e.g., the start bit of the rule to be stored in table 3 is P4.

Wherein, S201 may be specifically implemented as:

It is determined whether the consecutive first number of bits of rule data satisfies a non-mask type encoding condition. If yes, converting the key value in the rule data with the continuous first number of bits into a check block with a non-mask type; if the first number is not satisfied, determining that the first number is a preset number, and converting the key value and the mask in the rule data with the continuous first number of bits into a check block with the mask type.

In the check block of the mask type, a key value of the rule data and the mask are required to be stored at the same time, for example, if the key included in the rule data to be stored is 0001011111011111 and the mask is 0001010101010101, it can be seen that from 0 th bit to 3 rd bit in the mask are all 0, the current start bit can be determined to be the 4 th bit, and the value 1011111011111 from the 4 th bit to the 16 th bit in the key value and the value from the 4 th bit to the 16 th bit in the mask can be stored in one mask type check block.

Since the key and mask are stored in the check block of the mask type, the encoding condition of the mask type is not limited to the key and mask. The top three bits in the check block of the mask type are used for storing the offset of the current start bit inside the byte, the bottom three bits are used for storing the type code of the mask type, and the rest bits are used for storing in sequence: the key value and mask in the rule data are consecutive a first number of bits.

Taking the CPU bit width of 32 as an example, the structure of the check block of the mask type is shown in fig. 3a, wherein 2-0 bits are the check block type field, and the type code is stored.

28-16 Bits are used to store keys and 15-3 bits are used to store masks.

31-29 Bits are the start bit field, storing the offset of the start bit inside the byte.

S202, searching a first effective bit from bits which are not converted into check blocks in the target rule data, and returning to S201 by taking the searched effective bit as a current starting bit until the rule data of the effective bit included in the target rule data are converted into the check blocks.

By adopting the method, the first effective bit of the target rule is used as the current initial bit, the rule data of the continuous first number of bits is converted into a check block based on the coding conditions met by the rule data of the continuous first number of bits, and after the check block is generated, the initial bit of the next check block is still the effective bit, namely the middle non-effective bit is not needed to be stored, so that the memory space can be saved. In addition, the electronic device preferentially judges whether the rule data of the continuous first number of bits meets the encoding condition of the non-mask type, namely preferentially generates the check block of the non-mask type, and generates the check block of the mask type only when the rule data of the continuous first number of bits does not meet the encoding condition of the non-mask type. This allows the target rule data to be converted into a non-mask type of check block as much as possible, and since no mask is required to be stored in the non-mask type of check block, memory space can be saved. Under the condition that the encoding condition of the non-mask type is not met, the method can be converted into the check block of the mask type, and the accuracy of the generated check block can be ensured, so that the non-mask type and the mask type are combined, and the storage space of the RAM is saved on the basis of ensuring the accuracy of the storage of the rule to be stored.

The following describes encoding conditions of a non-mask type, wherein the non-mask type includes a full data type, a first length type, and a second length type.

The encoding conditions for the full data type include: the current start bit is the first bit of one byte included in the target rule data; and in the mask of the target rule data, the values of bits of the continuous CPU bit width from the current start bit are all 1, and the first quantity is CPU bit width.

The full data type means that all bits in one check block are used to store the rule data, and since all bits are used to store the rule data, the check block of the full data type does not include a check block type field and a start bit field. Therefore, the utilization rate of the check block of the full data type can be improved, and the memory space is saved.

Since the check block of the full data type does not include the check block type field, an additional storage structure is required to store the type code of the full data type, for example, 1 designated bit in the byte offset field before the check block of the full data type may be occupied to store the type code of the full data type, for example, if the value of the designated bit is 1, it indicates that the subsequent check block is the full data type check block, and if the value of the designated bit is 0, it indicates that the subsequent check block is not the full data type check block. Or the electronic device can also store the position information of each full data type check block corresponding to each rule in a separate storage area in the RAM.

Since the start bit field is not present in the check block, it is not possible to identify which bit in one byte of the target rule data the first bit stored in the check block is. Therefore, one encoding condition of the full data type is that the current start bit is the first bit of one byte included in the target rule data, i.e., the complete byte is stored in the default full data type. For example, if the CPU bit width is 32 bits, one check block may store a key value of 4 bytes.

One way to determine whether the start bit meets the encoding condition is to subtract 1 from the sequence number of the start bit in the rule to be stored and then divide by 8, if so, the start bit is the first bit of a byte. For example, key of rule to be stored is 000000001111 … …, mask is 000000001111 … …, the rule to be stored may also be expressed as 1111 … …, and then the start bit may be determined to be 9 th bit, 9-1 may be divided by 8, and since 1 byte includes 8 bits, it may be seen that the start bit is the first bit of the 2 nd byte in the rule to be stored.

Furthermore, another encoding condition for the full data type is: in the mask of the rule to be stored, the values of the bits of the continuous CPU bit width from the current start bit are all 1. That is, the bits with the width of the continuous CPU bits are the bits to be matched, so that the value of the bits which are not required to be matched can be prevented from being stored in the check block of the all-data type, the effect of compressing the rule to be stored is further achieved, and the memory space is saved.

The encoding conditions of the first length type include: the current start bit is the first bit position of one byte included in the target rule data; and in the mask of the target rule data, the values of the continuous first number of bits from the current start bit are all 1, the first number is smaller than the difference value between the CPU bit width and the bit number occupied by the check block type field, and the first number is larger than the preset number.

The check block type field is used to indicate the type of the check block, and the check block type field may occupy 3 bits. It will be appreciated that the number of bits in the first length type of parity block used to store the regular data is the difference between the CPU bit width and the number of bits occupied by the parity block type field. If the CPU bit width is 32, the number of bits in the check block for storing the rule data is 28. The first length type may also be referred to as a 28-bit longest match type.

As an example, the structure of the check block of the first length type is shown in fig. 3b, where 2-0 bits are type encoded and 31-3 bits are used for part of the key values in the target rule data, which may be referred to as the longest match data.

Since the start bit field is not present in the first length type of check block either, the condition that the current start bit is the first bit of one byte is also satisfied.

In the mask of the target rule data, the value of the consecutive first number of bit positions from the current start bit is1, that is, in the target rule data, there are consecutive first number of valid bits from the current start bit. For example, if the key value of the target storage rule data is 111110000011111 and the corresponding mask is 111111110000000, then the first 8 consecutive bits in the rule data may be determined to be all valid bits.

In one embodiment, the electronic device may look up the first subsequent bit B of 0 from the mask starting from the current start bit a. Further, it may be determined that the values of the bits (which may be referred to as bits C) from the start bit a to the previous bit of the searched bit position B in the mask are all 1, and the number of bits included in the start bit a to the bit C is the first number.

Taking a 32-bit CPU as an example, if the number of bits included in the start bits a to C is less than 28, the number of bits included in the start bits a to C is taken as the first number.

If the number of bits included in the start bit a to the bit position C is greater than 28, then 28 is taken as the first number.

The encoding conditions of the second length type include: the current start bit is not the first bit of one byte included in the target rule data; and in the mask of the target rule data, the values of the continuous first number of bits from the current start bit are all 1, and the first number is smaller than the difference value between the CPU bit width and the bit number occupied by the check block type field and the bit number occupied by the start bit field.

The initial bit field is used for storing the offset of the current initial bit in one byte, the initial bit can occupy 3 bits, the check block type can also occupy 3 bits, and the bit number used for storing the rule data in the check block of the second length type is the difference value between the CPU bit width and the bit number occupied by the check block type field and the bit number occupied by the initial bit field. For example, if the CPU bit width is 32, 32-3-3=26, since one bit value among the 26 bits is used to separate valid data from non-valid data in the rule data, the bits for storing the rule data among the 26 bits are 25 bits at most, and thus the second length type may also be referred to as a 25-bit longest match type.

As an example, the structure of the second length type of check block is shown in fig. 3c, where 2-0bit is a check block type field, and a type code is stored, and 28-3bit is used to store a part of key values in the target rule data, where the part of key values may be called as longest match data, 31-29bit is a start bit field, and an offset of the start bit inside the byte is stored.

Since the start bit field is included in the second length type of check block, the first bit of the rule data stored in the check block may not be the first bit within one byte.

The coding conditions of the second length type differ from the coding conditions of the first length type only in that: whether the current start bit is the first bit of a byte included in the target rule data, and other conditions are the same, and will not be described here again.

Based on the above non-mask type encoding condition, determining whether the rule data of the consecutive first number of bits satisfies the non-mask type encoding condition may be specifically implemented as:

if the rule data of the continuous first number of bits meets any one of the encoding conditions of the full data type, the first length type and the second length type, determining that the encoding condition of the non-mask type is met; otherwise, it is determined that the encoding condition of the non-mask type is not satisfied.

By adopting the method, whether the continuous first number of bits of rule data from the current start bit meets the coding conditions of the full data type, the first length type and the second length type can be judged, so that the most suitable coding mode can be selected from the rule data to compress and store the target rule data, and under the condition that any one of the coding conditions of the full data type, the first length type and the second length type is met, masks corresponding to the bits are not needed to be stored, and the storage space can be saved.

Based on the encoding conditions of the full data type, the first length type, and the second length type described in the above embodiments, an implementation manner of converting the key value in the rule data of the consecutive first number of bits into the check block of the non-mask type may specifically include the following three cases:

And 1, if the rule data with the continuous first number of bits meets the coding condition of the full data type, converting the key value in the rule data with the continuous first number of bits into a check block with the full data type. Accordingly, a check block of the all data type is used to store key values in the rule data for a consecutive first number of bits.

And 2, if the continuous first-number-bit rule data meets the coding condition of the first length type and does not meet the coding condition of the full data type, converting the key value in the continuous first-number-bit rule data into a check block of the first length type.

Accordingly, the lowest three bits of the check block of the first length type are used to store the type code of the first length type, and the last to last bits are used in order to store: the key value in the first number of bits of rule data and a 0, the value of the unoccupied bit defaults to 1.

It can be understood that, since all bits in the check block of the full data type can be used to store rule data, the utilization rate of the check block of the full data type is the highest, so that the check block of the full data type is preferentially used for storage under the condition that the coding conditions of the full data type and the first length type are satisfied at the same time, and the storage resource of the RAM can be more fully utilized.

The structure of the check block of the first length type may be referred to in fig. 3b, and the longest match data portion in fig. 3b is stored in the manner shown in fig. 4.

The first number is the number of bits with the mask value of 1 in the rule data to be encoded, and the first number is denoted as P, and then the key values of the P bit positions from the current start bit in the target rule data can be sequentially filled in the first P bit positions in fig. 4. Then 0 is filled in the P+1st bit and 1 is filled in all the following bits.

In fig. 4, the first P bit positions are valid data, and data after 0 are all data which is not concerned.

And 3, if the rule data with the continuous first number of bits meets the coding condition of the second length type, converting the rule data with the continuous first number of bits into a check block with the second length type.

Correspondingly, the highest three bits in the check block of the second length type are used for storing the offset of the current start bit in the byte, the lowest three bits are used for storing the type code of the second length type, and the rest bits are sequentially used for storing: the key value and one 0 in the rule data of the first number of bits are consecutive, and the unoccupied bit position is default to 1.

The structure of the second length type check block may refer to fig. 3c, and the storage manner of the longest match data portion in fig. 3c may also be the storage manner as shown in fig. 4.

The first number is the number of bits with the mask value of 1 in the rule data to be encoded, and the first number is denoted as P, and the first P bits in fig. 4 may be sequentially filled with key values of P bits from the current start bit in the target rule data. Then 0 is filled in the P+1st bit and 1 is filled in all the following bits.

The offset of the current start bit inside the byte is the remainder of the division of the value of the current start bit in the target rule data by 8, e.g., S is 12, then the offset inside the byte is 4.

Therefore, in all three cases, the mask for storing the target rule data is not needed, so that the memory space can be saved, and the resource utilization rate of the RAM can be improved.

In the embodiment of the present application, the target rule data further includes rule data of a range type, the rule data of the range type is not converted into a key and mask form, the rule data of the range type specifically includes a value of a range type field in the matching domain, and in the embodiment of the present application, the encoding mode of the rule data of the range type is:

If the target rule data comprises rule data of a range type, and the maximum value and the minimum value of the rule data of the range type are smaller than 2 ¹³, converting the rule data of the range type into a check block of a first range type; if the minimum value of the rule data of the range type is more than or equal to 2 ¹³ or the maximum value of the rule data of the range type is more than or equal to 2 ¹³, converting the rule data of the range type into a check block of the second range type and a check block of the third range type.

Wherein the highest 13 bits of the check block of the first range type are used to store the maximum value, the next 13 bits are used to store the minimum value, the next 2 bits are used to store the code of the first subtype, and the lowest 3 bits are used to store the code of the range type, the first subtype code is used to indicate that the check block includes a matching range.

If the maximum value and the minimum value of the rule data of the range type are smaller than 2 ¹³, the storage space of one check block is enough to store the maximum value and the minimum value simultaneously, as shown in fig. 5a, wherein 31-19 bits are used for storing the maximum value (Max), 28-16 bits are used for storing the minimum value (Min), 5-4 bits are sub, the sub value is coded by the first subtype, 3 bits are temporarily unoccupied, and 2-0 bits are check block types, and are particularly used for storing the type codes of the range type.

The highest 26 bits of the check block of the second range type are used to store the minimum value, the next two bits are used to store the code of the second subtype, the lowest 3 bits are used to store the code of the range type, and the second subtype code is used to indicate that the check block includes the minimum value of a matching range.

The highest 26 bits of the check block of the third range type are used to store the maximum value, the next two bits are used to store the third subtype code, the lowest 3 bits are used to store the range type code, and the third subtype code is used to indicate that the check block includes a maximum value of the matching range.

If the minimum value (Min) of the rule data of the range type is 2 ¹³ or more, or the maximum value (Max) is 2 ¹³ or more, the maximum value (Max) and the minimum value (Min) of the rule data of the range type may be stored respectively using two check blocks.

As shown in fig. 5b, 31-6 bits are used for storing the minimum value (Min), 5-4 bits are sub, sub is coded with a second subtype, 3 bits are temporarily unoccupied, and 2-0 bits are check block types, specifically used for storing type codes of range types.

As shown in fig. 5c, 31-6 bits are used for storing the maximum value (Max) 5-4 bits as sub, the sub value is the third subtype code, 3 bits are temporarily unoccupied, and 2-0 bits are check block types, specifically used for storing the range type code.

In the embodiment of the application, the rule data of the range type is not required to be divided into a plurality of sub-ranges, and each sub-range is converted into a prefix field, so that the expansion caused by the rule data of the range type can be avoided, and the storage space is further saved.

In order to determine the location of the rule data stored in the check blocks in the target storage rule, each check block stored in the RAM is preceded by a byte offset field, the byte offset field preceding each check block being used to indicate the byte offset of the start bit of the rule data in that check block in the target rule data.

For example, the byte offset is 3, which indicates that the start bit in the check block is the third bit in one byte in the target rule data of the rule to be stored.

As shown in fig. 6, fig. 6 is an exemplary schematic diagram of a rule storage method according to an embodiment of the present application, starting from the lowest bit, searching for the first bit S0 that is not.

13 Bits from S0 satisfy the encoding condition of the mask type, and 17 bits from S0 satisfy the encoding condition of the 25-bit longest match type, which is the second length type in the above embodiment.

At this time, according to the longest matching principle, a 25-bit longest matching type with a longer coding length can be selected, and the key values of 17 bits after S0 are stored into a check block of a second length type. S0/8 before the check block is the byte offset of the check block in the rule to be stored. Where S0/8 refers to the quotient of S0 divided by 8.

And continuing to search for a second bit S1 which is not the same, wherein 13 bits from S1 meet the coding condition of the mask type, and 4 bits after S1 meet partial conditions in the 25-bit longest matching type, but the first number N=4 is smaller than the preset number 13, so that the condition that the first number is larger than the preset number is not met, and the value of 13 bits after S1 can be stored in a check block of the mask type. S1/8 before the check block is the byte offset of the check block in the rule to be stored. Where S1/8 refers to the quotient of S1 divided by 8.

Based on the same inventive concept, the embodiment of the application also provides a message processing method, which is applied to electronic equipment, wherein RAM is arranged in the electronic equipment, target rule data in a matching domain of each rule in a specified rule table of the RAM is stored in a form of check blocks, the types of the check blocks comprise mask types and non-mask types, the rule data in the check blocks of the mask types comprise key values and masks, the rule data in the check blocks of the non-mask types comprise key values with continuous effective bits, and the effective bits are bits with the mask values of 1. Each rule in the specified rule table in the RAM may be specifically stored according to the rule storage method described in the above embodiment.

As shown in fig. 7, the message processing method includes:

s701, extracting a search key value from a message to be processed.

In the embodiment of the application, after the electronic equipment acquires the message to be processed, key information forming the key can be extracted from the header of the message to be processed, and the key is searched by utilizing the extracted key information, namely, the key value is searched.

For example, in table 1, if each rule matching field includes a message quintuple, the electronic device may extract the quintuple from the message to be processed, and arrange the extracted quintuple according to the sequence of the source IP address, the destination IP address, the source port, the destination port, and the protocol, to obtain the lookup key value.

In the embodiment of the present application, the order of each field in the lookup key is not limited, so long as the order of each field in the lookup key is guaranteed to be consistent with the order of each field in the rule, for example, the rule includes 4 fields, i.e., source IP, destination IP, source port, destination port, and the order of the 4 fields is: source IP, destination IP, source port, destination port; the order of finding the fields in the key is also: source IP, destination IP, source port, destination port.

S702, determining rules to be matched in a specified rule table based on the search key value.

S703, determining the length of the data to be matched according to the type of each check block in the rule to be matched.

In the embodiment of the application, the RAM may store a rule to be matched, which may include a plurality of check blocks, and the electronic device may determine, based on a type of each check block, a data length to be matched, where the data length to be matched is a number of bits to be matched in the check block. For example, if there is 8 bits of regular data in the check block to be matched, the data to be matched is 8 bits long.

S704, extracting data to be matched according to the length of the data to be matched from the same initial bit in the search key value according to the initial bit of the rule data included in the check block, and matching the data to be matched with the rule data included in the check block.

It will be appreciated that a rule may be stored as a plurality of check blocks, each check block including a portion of the data in the rule, a start bit of a rule included in a check block referring to: the first bit included in the check block is a bit occupied in the target rule data of the entire rule.

For example, if the target rule data of a rule includes 30 bits, and one check block stores 8 th to 16 th bits of data in the target rule data of the rule, the start bit of the check block is the 8 th bit.

Accordingly, when matching the lookup key with the rule, data may be extracted from the 8 th bit position of the lookup key, that is, the data to be matched is the 8 th to 16 th bit data in the lookup key.

And S705, if the searching key value is successfully matched with all check blocks in the rule to be matched, determining that the searching key value is successfully matched with the rule to be matched.

Each rule to be matched comprises at least one check block, and the message to be processed can be determined to be matched with the rule to be matched only if the key value is searched and all check blocks are successfully matched.

By adopting the method, the rules are stored in the mode of check blocks in the embodiment of the application, the types of the check blocks comprise a mask type and a non-mask type, the rule data in the check blocks of the mask type comprise key values and masks, and the rule data in the check blocks of the non-mask type comprise key values with continuous effective bits. Therefore, the check blocks of the non-mask type do not comprise masks of rules, so that all masks of one rule do not need to be stored, and subsequently when the rule in the RAM is matched, data to be matched in the search key value can be matched with the check blocks in the rule to be matched, the rule data in the rule to be matched can be stored in the form of the check blocks, and the matching of the search key value can be realized, so that the occupation of the storage space of the RAM can be saved.

In addition, when the rule in the RAM is matched, the data to be matched in the search key value can be matched with the check block in the rule to be matched, and the non-mask type check block does not comprise a mask, so that the data size is small, the bandwidth of the electronic equipment when the electronic equipment accesses the RAM can be reduced, and the search efficiency is improved.

The embodiment of the application can be applied to the following two scenes.

And (3) storing all rules in the global rule set by using the RAM in the scene I.

In the scene, each rule in the global rule set can be converted into a key and mask form, each rule is further used as a rule to be stored, target rule data in each rule to be stored is converted into a check block, and the check block is stored in the RAM, so that compared with the key and mask for storing each rule, the memory space can be saved.

Alternatively, a plurality of block rule tables may be stored in the RAM, the plurality of rules in each block rule table having the same common rule. The RAM may also store a linear table comprising a plurality of base addresses for locating the rule table.

The bits of the rules included in each block rule table within the preset range have the same value, for example, the mask of the first 8 bits of each rule in one block rule table is 1, and the keys are the same.

The bits in the preset range may be the first 8 bits of the source IP address of each rule, or the first 8 bits of the destination IP address, or a section of bits corresponding to other fields, which is not limited.

The electronic device may use, for each block rule table, a key of bits in a preset range in the block rule table as a base address, where the base address is used to locate the block rule table. The base addresses in the linear table may be arranged in a certain order, for example, in order from small to large.

In scenario one, the above S702 may be specifically implemented as: taking bits in a preset range in the search key value as a search index, and determining a target base address pointed by the search index in the linear table; positioning a block rule table based on a target base address, wherein the positioned block rule table is used as a specified rule table; and taking the rule included in the specified rule table as the rule to be matched.

For example, if the preset range is the first 8 bits of the whole rule, the first 8 bits of the search key value can be extracted as the search index.

Because the base addresses in the linear table are arranged in sequence, the target base address pointed by the search index can be quickly positioned based on the search index, then the target base address is utilized to position the rule table, and the positioned block rule table is further used as the index to be matched. The method is equivalent to carrying out coarse-granularity screening on the rules in the RAM, so that the search key value is not required to be matched with all the rules in the RAM one by one, but only the rules in the block rule table corresponding to the target base address are required to be matched, the matching time can be saved, and the processing efficiency is improved.

Alternatively, there may be a plurality of the above-mentioned preset ranges, for example, the values of bits in the first preset range of bits in a plurality of rules in a block rule table are the same, and the values of bits in the second preset range are the same. And there may be cases where the values of bits of the plurality of rules in the two block rules tables are all the same within the first preset range.

For example, the first preset range may be the first 8 bits of the source IP address and the second preset range may be the first 8 bits of the destination IP address.

For the above situation, a plurality of linear tables may be set in the RAM, where each linear table corresponds to a preset range, and further when coarse-granularity screening is performed on the lookup key value, multi-level screening may be performed, for example, first extracting a value of a bit in a first preset range from the lookup key value, as a first index, and locating a rule table based on a first target base address pointed by the first index in the first linear table, where a plurality of block rule tables may be located, and for convenience of description, the plurality of block rule tables are referred to as a set a.

Further, the value of the bit in the second preset range is extracted from the search key value, the value is used as a second index, the rule table is located in the set A based on the second target base address pointed by the second index in the second linear table, the second level screening is completed, and the located block rule table is used as the appointed rule table. Therefore, the number of the positioned specified rule tables is smaller, the number of the rules to be matched which need to be matched subsequently is smaller, and the processing efficiency can be further improved.

It should be noted that, in the embodiment of the present application, the number of preset ranges and the number of linear tables are not limited, and may be flexibly set based on the rule amount in the global rule set.

As an alternative implementation manner, after the rule in the specified rule table is used as the rule to be matched, when the rule to be matched is matched one by one according to the flow shown in fig. 7, the bit in the preset range in the rule to be matched can not be matched any more, so that repeated matching of the bit in the preset range can be avoided, and the processing efficiency is improved.

And storing the ACL by using the TCAM and the RAM.

In the second scenario, the electronic device is further provided with a TCAM, a public rule table is stored in the TCAM, a main rule table and a block rule table are stored in the RAM, and a plurality of rules with the same public rule are stored in the block rule table. The main rule table at least comprises two fields of a split position set and a base address, the rules in the block rule table belong to a subtree determined by the split position set, the split position set is used for positioning the position of the rule corresponding to the search key value in the block rule table, the base address is used for positioning the rule table, and the value of a non-wild card bit in the common rule is the same as the value of the same bit of all rules in the block rule table pointed by the base address. The common rule table stores common rules, and the common rule table has the same index as the corresponding same block rule table in the main rule table.

The rules in the block rule table may be stored in the form of check blocks according to the rule storage method described in the above embodiment.

In the embodiment of the application, one or more public rule tables, one or more main rule tables and one or more block rule tables can be stored in the electronic equipment. The public rule table and the main rule table are in one-to-one correspondence, and for the table items of the public rule table and the table items of the main rule table with the same index, the public rule table and the table items of the main rule table correspond to the same block rule table, one table item in the main rule table corresponds to one block rule table, and when the main rule table comprises a plurality of table items, the main rule table corresponds to a plurality of block rule tables. Taking a common rule table and a master rule table as an example, the correspondence relationship among the common rule table, the master rule table and the block rule table is shown in fig. 8. Wherein the index is used to indicate the position of an entry in the table.

The common rule table is built in the TCAM, and the common rule table may also be called a TCAM table, where an entry in the TCAM table is a common rule of a plurality of rules in a block rule table, such as Head 0-n in fig. 8. In the embodiment of the application, a plurality of rules in a block rule table form a rule block.

A TCAM table has a corresponding master rule table stored in RAM, such as L0-Ln in FIG. 8. The master rule table may be a linear table, or other form of RAM-supported table, which may also be referred to as a master (main) table. A list item in the main list stores a split position set (split bits) of a rule block and a base address of a lower list, wherein the lower list is a block rule list for storing the rule block, and the offset of each rule block corresponding list item in the main list is the same as the offset of the rule block corresponding list item in the TCAM list. The offset here is the index, such as the primary index in fig. 8.

A rule block includes a plurality of rules constituting a block rule table and stored in RAM, and rules 0 to 3 in fig. 8 constitute a rule block stored in block rule table 0 in RAM. The Block rule table may be a linear table, or other form of RAM-supported table, and may also be referred to as a Block (Block) table, such as Block table 0, block table n in fig. 8. The base address and split position set of a block table are stored in an entry in the main table. The split position set is composed of a plurality of bits, and if the number of bits included in the split position set is S, the size of the Block table is to the power of 2S, that is, the Block table includes the square bar rule of 2S. For example, s=2, the power 2 of 2=4, then the Block table includes 4 rules. Under the condition that the electronic device knows the splitting position set of one rule block, the electronic device extracts the values of the S bits of each rule in the rule block to form an offset (offset) of each rule, wherein the offset is the index of the rule in a block table, such as the secondary index in fig. 8.

It should be noted that, to facilitate TCAM storage, the electronic device may convert the rules in the global rule set into a key and mask form, and then convert the rules represented in the key and mask form into a binary form. The conversion method has been described in the above embodiments, and will not be described here again.

As shown in fig. 9, S702, the determining the rule to be matched in the specified rule table based on the search key value, may be specifically implemented as:

s7021, matching is carried out in a public rule table by using the search key value, and a main index of a target table item in the main rule table is obtained.

The electronic device may use the search key value to match in the public rule table to obtain an index of the table item where the matched public rule is located, where the index is the index of the target table item in the main rule table. In the embodiment of the application, the matching of the search key value and the public rule can be understood as follows: the search key value is the same as the value of the common rule in the same bit, or the value of the common rule in the same bit is.

S7022, based on the base address and the positioning block rule table included in the target table item pointed by the main index, the block rule table obtained by positioning is used as the appointed rule table.

The public rule table corresponds to the main rule table one by one, and the indexes of the public rule table and the same block rule table corresponding to the main rule table are the same. After the electronic equipment obtains the main index from the TCAM, the electronic equipment reads the target table item corresponding to the main index in the main rule table to obtain the base address and the splitting position set of the block rule table, further locates the block rule table at the base address, and takes the block rule table as the appointed rule table.

S7023, determining a secondary index of the rule to be matched in the specified rule table based on the search key value and the split position set included in the target table item pointed by the primary index.

As described in step S7022, the electronic device reads the target entry corresponding to the main index in the main rule table, and may obtain the base address and the split position set of the block rule table. The electronic equipment extracts the value of each bit shown in the target split position set from the search key value, and the extracted value of each bit forms a secondary index, wherein the secondary index is the offset of the matched rule in the positioned block rule table. The rule matched in the positioned block rule table is the rule to be matched.

The execution order of step S7022 and step S7023 is not limited in the embodiment of the present application.

S7024, the rule pointed by the secondary index is used as the rule to be matched.

In the embodiment of the application, N TCAM tables can be stored in the electronic equipment, and N is more than or equal to 1. For each TCAM table, the electronic device may obtain a rule to be matched based on the TCAM table, a main table corresponding to the TCAM table, and a Block table corresponding to the TCAM table. Thus, the electronic device may obtain at most N rules to be matched in the N TCAM tables.

It can be understood that after the rule to be matched is obtained, the rule to be matched needs to be checked, that is, the search key value is matched with the check block of the rule to be matched through the method flow shown in fig. 7.

In some embodiments of the present application, if the rule to be matched is one and the key value is found to be successfully matched with the rule to be matched, the message to be processed is processed according to the action domain corresponding to the rule to be matched; if the searching key value is not matched with the rule to be matched, the electronic equipment refuses to process the message to be processed by using the rule to be matched.

If the number of the rules to be matched is multiple, matching the searching key value with each rule to be matched, and processing the message to be processed according to an action domain corresponding to one rule to be matched successfully matched with the searching key value.

If there are multiple rules to be matched successfully matched with the searching key value, one rule to be matched with the highest priority can be selected, and then the message to be processed is processed.

Because the rules in the specified rule table are stored in the form of the check blocks and all rule data of each rule are not stored, the check process only needs to match the search key value with the check block corresponding to the rule to be matched, integrity check is not needed, the access bandwidth to the RAM can be reduced, and the message processing efficiency is improved. In addition, the electronic equipment is provided with the TCAM and the RAM, the electronic equipment stores the common rule of the plurality of rules in the TCAM and stores the specific rule in the RAM, so that the requirement on the capacity of the TCAM can be reduced. The electronic equipment uses the public rules stored in the TCAM with higher searching performance to exclude most rules, and subsequently uses the rule check block to be matched stored in the RAM to match with the searching key value, so that the larger-scale rule searching can be realized by using the TCAM with smaller capacity and the RAM, and the cost and the power consumption of message processing are saved.

In some embodiments, for each block rule table, the common rule corresponding to that block rule table may be generated by:

And if the value of one bit of all the rules stored in the block rule table is 1, setting the value of the bit of the public rule corresponding to the block rule table to be 1.

And if the value of one bit of all rules stored in the block rule table is 0, setting the value of the bit of the public rule corresponding to the block rule table to be 0.

And if the one-bit value of all rules stored in the block rule table is not all 1 and/or the one-bit value of all rules stored in the block rule table is not all 0, setting the one-bit value of the common rule corresponding to the block rule table as a wild card.

As shown in Table 4, 4 rules, rules 0-3, are shown in Table 4 as included in a block rule table. At the bit P3, the values of the rules 0-3 are all 0, and the electronic equipment sets the value of the bit P0 of the public rule to 0; at the bit P7, the values of the rules 0-3 are all 1, and the electronic equipment sets the value of the bit P1 of the public rule to be 1; at other bits, rules 0-3 do not satisfy both cases, then the electronic device sets the values of these bits of the common rule to x.

TABLE 4 Table 4

Public rules

*

0

*

1

Rule 0

*

1

*

0

*

0

1

Rule 1

*

0

*

1

Rule 2

*

0

1

*

0

1

Rule 3

*

0

*

0

1

Bit position

P0

P1

P2

P3

P4

P5

P6

P7

In the embodiment of the application, the bit width of the public rule is the same as the bit width of the rule, and when all bits of the public rule are set, the generation of the public rule is completed. And storing the generated public rule in a TCAM, and establishing a table entry of a corresponding main rule table and a block rule table storing all rules corresponding to the public rule in a RAM.

In the technical scheme provided by the embodiment of the application, the electronic equipment extracts the public rule of all rules in each block rule table, namely, one public rule can represent a plurality of rules, the public rule is stored in the TCAM, the requirement on the TCAM capacity is reduced, larger-scale rule searching can be realized by using the TCAM with smaller capacity, and the cost and the power consumption of message processing are saved.

In some embodiments, the present application further provides a method for generating a public rule table, a main rule table and a block rule table, as shown in fig. 10, fig. 10 is a first flowchart of the method for generating a public rule table, a main rule table and a block rule table, which may include the following steps:

S1001, constructing a rule decision tree based on balance bits of all rules in the global rule set, wherein the balance bits are one bit with the smallest difference value between the number of the rules with the value of 0 and the number of the rules with the value of 1 in all the bits.

In the embodiment of the application, the electronic equipment takes all rules with a matching domain and an action domain as a global rule set, considers the whole rule, determines the balance bit of the rules in the global rule set, and has the minimum difference between the number of the rules with the value of 0 and the number of the rules with the value of 1 at the balance bit.

For example, the rule set in the electronic device includes 5 rules R1 to R5 as shown in fig. 11, and as can be seen from fig. 11, at the bit P2, the rule number of 0 is 2, the rule number of 1 is 2, the difference between the rule number of 1 and the rule number of 2 is 2-2=0, which is the bit having the smallest difference between the rule number of 0 and the rule number of 1, and thus, the bit P2 can be determined as the balanced bit.

The electronic device builds a rule decision tree based on the balance bits of each rule in the global rule set. Wherein, the rule decision tree can be implemented by adopting a decision tree in the form of a binary tree. The rule decision tree management rule set in the form of binary tree is adopted, so that the technical scheme provided by the embodiment of the application is more universal and is irrelevant to specific application. In the embodiment of the application, the electronic equipment can also adopt other forms of rule decision trees, and the rule decision tree is not limited.

S1002, traversing the rule decision tree from each leaf node to the top according to breadth first to obtain the deepest rule subtree corresponding to each leaf node, wherein the deepest rule subtree is the deepest rule subtree in the rule subtrees with balance bit less than or equal to preset splitting bit depth.

The method comprises the steps that a maximum split bit number, namely a preset split bit depth, is preset in the electronic equipment, and the preset split bit depth is the maximum value of the bit number included in a split position set. The size of the preset number can be set according to actual requirements.

After a rule decision tree is built, aiming at each leaf node of the rule decision tree, the electronic equipment traverses the leaf node upwards according to breadth first, and when traversing to a certain node of the rule decision tree, takes the node as a root node to form a subtree; if the electronic equipment judges that the subtree is the deepest subtree with the number of the balance bit less than or equal to the preset splitting bit depth, the subtree is used as the deepest rule subtree, and upward traversal is stopped; otherwise, the node is used as a starting point, and the upward traversal is continued.

When all the leaf nodes of the rule decision tree belong to a deepest rule subtree, the electronic device stops executing the above step S1002.

Step S1003, based on each deepest rule subtree, generates a common rule table, a main rule table, and a block rule table.

In the embodiment of the present application, after the electronic device finishes executing step S1002, one or more deepest rule subtrees are obtained, and a block rule table is generated based on rule sets included in each deepest rule subtree; generating a split position set based on balance bits included in each deepest rule subtree; generating a main rule table based on the splitting position set corresponding to each deepest rule subtree and the base address of the block rule table; and generating a public rule table based on the table entry index in the main rule table corresponding to each deepest rule subtree and the public rule of the rule set included in each deepest rule subtree.

Wherein all rules included in a deepest rule subtree form a block rule table, i.e. a rule block. For a deepest rule subtree, the electronic device generates a block rule table from a rule set included in the deepest rule subtree; generating a set of split positions from balance bits comprised by nodes other than the root node of the deepest rule subtree; generating an entry in a main rule table by the splitting position set corresponding to the deepest rule subtree and the base address of the block rule table; and generating an item in a public rule table by the public rule of the rule set included in the deepest rule subtree, wherein the index of the item in the public rule table corresponding to the deepest rule subtree is the same as the index of the item in the main rule table corresponding to the deepest rule subtree. Generating a main rule table by table entries in the main rule table corresponding to all deepest rule subtrees included in a rule decision tree; and generating a public rule table by table entries in the public rule table corresponding to all deepest rule subtrees included in the rule decision tree.

For example, the preset splitting bit depth is 3, such as a rule decision tree shown in fig. 12, where R0-R3 represent rules included in leaf nodes, and P0-P6 represent balanced bit included in the nodes. The electronic device traverses from the leaf node R0 to the node P2 according to the breadth priority, takes P2 as a root node to form a subtree, wherein the subtree comprises rules R0 and R1, the number of balanced bit bits in the subtree is 0,0<3, continues to traverse upwards from the node P2 as a starting point, traverses to the bit P1, takes P1 as the root node to form a subtree, and the subtree comprises balanced bit bits: p2 and P3, the corresponding rules are: the rule R0-R3, at this time, the subtree includes the balanced bit number 2,2<3, if the node P1 is used as the starting point, go on traversing upwards, the formed subtree includes the balanced bit number necessarily greater than 3, therefore, the subtree formed by the node P1 is used as the deepest rule subtree including the balanced bit number not greater than 3, the splitting position set of the deepest rule subtree is { P2, P3}, the rule R0-R3 is stored into a block rule table 1, and an entry 1 in the main rule table is generated based on the splitting position set { P2, P3} and the base address of the block rule table 1; based on the index of table item 1 in the master rule table and the common rules of rules R0-R3, an table item 2 in the common rule table is generated.

In the embodiment of the present application, the electronic device generates the public rule table, the master rule table and the block rule table by adopting the steps S1001 to S1003. To avoid the problem of rule duplication storage, a balanced bit is recorded only once in all split position sets of a rule decision tree. Thus, the capacity of the TCAM and the capacity of the RAM can be effectively utilized, and the cost is saved.

According to the technical scheme provided by the embodiment of the application, the electronic equipment can extract more public information of the rule by utilizing the rule decision tree, so that the difficulty of searching the rule is reduced while the cost is saved, and the searching efficiency is improved.

In some embodiments, as shown in fig. 13, the step S1001 may be refined as the following steps:

In step S1301, the global rule set is used as the rule set to be split, and the global rule set is included in the root node of the rule decision tree.

In step S1302, a balance bit of each rule in the rule set to be split is determined. The manner in which the balance bit is determined in step S1302 can be seen from the relevant description of the section of step S1001.

In step S1303, a rule with a value of 0 in the balance bit in the rule set to be split is added to the first side child node, and a rule with a value of 1 in the balance bit in the rule set to be split is added to the second side child node.

Taking a rule decision tree in the form of a binary tree as an example, the first side is left, the second side is right, or the first side is right, and the second side is left. Taking the first side as the left and the second side as the right as an example, the description will be given with reference to fig. 11. The electronic equipment determines that the balance bit is P2, divides rules R2 and R5 with the value of 0 of the bit P2 into a rule set 1, and adds the rule set 1 to the left child node of the rule decision tree; the rules R1 and R4 with the bit P2 value of 1 are divided into a rule set 2, and the rule set 2 is added to the right child node of the rule decision tree. At this point, splitting one rule set into two rule sets is completed.

In the embodiment of the present application, there is a case where the value of the balance bit is "x", as in fig. 11, the value of the rule R3 in the balance bit P2 is "x", and in this case, the electronic device does not perform any processing on the rule, and may also add the rule into the discard rule set, so as to facilitate subsequent processing. This is not limited.

In step S1304, for each split sub-node, if the sub-node includes multiple rules, step S1302 is re-executed with the rule set included in the sub-node as the rule set to be split until each split sub-node includes one rule, thereby obtaining a rule decision tree.

In the embodiment of the present application, the electronic device circularly executes steps S1302 to S1304, and the condition for ending the cycle is: the child node obtained by splitting comprises a rule. A rule decision tree in the form of a binary tree manages a rule set, one leaf node of the rule decision tree comprising one rule. As shown in fig. 12, a rule decision tree structure includes only one rule in each of the 4 leaf nodes R0-R3.

In the embodiment of the present application, the electronic device adopts the steps S1301-S1304 to construct a rule decision tree, and then the rule decision tree can generate a public rule table, a main rule table and a plurality of block rule tables. According to the technical scheme provided by the embodiment of the application, the electronic equipment can extract more public information of the rule by utilizing the rule decision tree, so that the difficulty of searching the rule is reduced while the cost is saved, and the searching efficiency is improved.

In some embodiments, the electronic device may also divide the global rule set into a plurality of rule sets, where each rule set includes a plurality of rules stored as a block rule table, and extract a common rule of the block rule table and a corresponding split position set to generate a corresponding common rule table and a main rule table.

Based on the storage structure of each type of check block described in the foregoing embodiment, in the embodiment corresponding to fig. 7, the implementation manner of determining the length of the data to be matched according to the type of the check block specifically includes the following cases:

And 1, if the type of the check block is a mask type, determining that the length of the data to be matched is the length of a preset number of bit positions.

For example, taking a CPU bit width of 32 bits as an example, see FIG. 3a, where key and mask each occupy 13 bits, and thus the preset number is 13.

And 2, if the type of the check block is the full data type, determining that the length of the data to be matched is the CPU bit width of the electronic equipment.

Since all bits in the check block of the all-data type are used to store the regular data, the data length to be matched is the check block size, i.e., the CPU bit width.

And 3, if the type of the check block is the first length type or the second length type, searching a first bit position with a value of 0 from the lowest bit of the rule data included in the check block to the direction of the highest bit, and determining that the length of the data to be matched is from the highest bit to the searched bit.

In this case, only the valid data needs to be matched, referring to fig. 4, fig. 4 is a schematic diagram of a storage structure of the regular data portion in the first length type and the second length type, and the data before the bit with the value of 0 is the valid data, so the bit length before the bit with the value of 0 is the data length to be matched.

And 4, if the type of the check block is the range type, determining that the length of the data to be matched is the fixed length of the range type field.

If the type of the check block is a range type, the value of the sub field in the check block can be further obtained, and if the value is a first subtype code, the corresponding fixed length is 13 bits; if the value is not the first subtype code, the corresponding fixed length is 26 bits.

Furthermore, matching the data to be matched with the rule data included in the check block may be specifically implemented as:

and if the type of the check block is the mask type, performing AND operation on the key value and the mask in the check block, comparing a result obtained after the AND operation with data to be matched, and if the result is completely consistent with the data to be matched, successfully matching.

For a mask type of parity block, the electronic device may obtain a byte offset from a byte offset field in the parity block, and in combination with the value of a start bit field in the parity block, may determine a start bit of the regular data included in the parity block. For example, if the determined start bit is the 7 th bit of the 1 st byte and the length of the data to be matched is 13 bits, the 13bit data to be matched can be extracted from the 7 th bit of the 1 st byte of the search key value, and the 13bit key and the 13bit mask in the check block are subjected to AND operation, and then the result of AND operation is compared with the 13bit data to be matched, and if the result is completely consistent, the matching is successful.

If the type of the check block is the full data type, the data to be matched is compared with all rule data in the check block, and if the data to be matched is completely consistent with all rule data in the check block, the matching is successful.

For a full data type of parity block, the electronic device may obtain the byte offset from the byte offset field in the parity block, thereby determining the start bit of the regular data included in the parity block. For example, if the determined start bit is the 3 rd byte, the data to be matched of 32 bits is extracted from the 3 rd byte of the search key value, and is compared with the 32bit rule data in the check block, and if the data are completely consistent, the matching is successful.

If the type of the check block is the first length type or the second length type, extracting rule data according to the length of the data to be matched from the highest bit of the rule data included in the check block, comparing the extracted rule data with the data to be matched, and if the extracted rule data are completely consistent, successfully matching.

If the type of the check block is the range type, a matching range is obtained from the check block, and if the data to be matched belongs to the matching range, the matching is successful.

By adopting the method, the rule data in the check blocks can be matched with the rule data to be matched according to the types of the check blocks, and the check blocks are encoded in a compressed mode, so that the access bandwidth can be reduced, and the matching speed can be improved. According to experiments, the method provided by the embodiment of the application can compress 40 bytes of ACL to one half of the original ACL, and can compress 80 bytes of ACL to one fourth of the original ACL, thereby greatly saving storage space.

Based on the same inventive concept, an embodiment of the present application provides a rule storage apparatus applied to an electronic device, in which a RAM is provided, as shown in fig. 14, the apparatus including:

An obtaining module 1401, configured to obtain a rule to be stored, where the rule to be stored includes a matching domain, the matching domain includes target rule data, and the target rule data is a key value and a mask in the matching domain;

A conversion module 1402, configured to convert the target rule data into at least one check block;

A storage module 1403 for storing the target rule data in the form of a check block in the RAM;

In one implementation, the conversion module 1402 is specifically configured to:

In one implementation, the non-mask type includes a full data type, a first length type, and a second length type;

In one implementation, the check block of the all-data type is used to store a key value in the rule data of the consecutive first number of bits;

In one implementation, the conversion module 1402 is further configured to:

In one implementation, each check block stored in RAM is preceded by a byte offset field, the byte offset field preceding each check block being used to indicate the byte offset of the start bit of the rule data in that check block in the target rule data.

In one implementation, the obtaining module 1401 is specifically configured to:

Based on the same inventive concept, the embodiment of the application also provides a message processing method, the device is applied to electronic equipment, random access memory RAM is arranged in the electronic equipment, target rule data in a matching domain of each rule in a specified rule table of the RAM is stored in a form of a check block, the type of the check block comprises a mask type and a non-mask type, rule data in the mask type check block comprises a key value and a mask, rule data in the non-mask type check block comprises a key value with continuous effective bits, and the effective bits are bits with the mask value of 1; as shown in fig. 15, the apparatus includes:

an extraction module 1501, configured to extract a lookup key value from a message to be processed;

A determining module 1502, configured to determine a rule to be matched in the specified rule table based on the lookup key value; determining the length of data to be matched according to the type of each check block aiming at each check block included in the rule to be matched;

a matching module 1503, configured to extract data to be matched according to the length of the data to be matched from the same start bit in the search key value according to the start bit of the rule data included in the check block, and match the data to be matched with the rule data included in the check block; if the searching key value is successfully matched with all check blocks in the rule to be matched, determining that the searching key value is successfully matched with the rule to be matched;

And a processing module 1504, configured to process the to-be-processed packet based on a matching result of the search key value and the to-be-matched rule.

In one implementation, a linear table is also stored in the RAM, the linear table including a plurality of base addresses, the base addresses being used to locate the rule table; the determining module 1502 is specifically configured to:

Positioning a block rule table based on a target base address, wherein the positioned block rule table is used as a specified rule table;

and taking the rule included in the specified rule table as the rule to be matched.

In one implementation, the electronic device is further provided with a ternary content addressable memory TCAM, wherein a public rule table is stored in the TCAM, a main rule table and a block rule table are stored in the RAM,

The block rules table stores therein a plurality of rules having the same common rule,

the determining module 1502 is specifically configured to:

And taking the rule pointed by the secondary index as the rule to be matched.

In one implementation, the apparatus further comprises a generation module;

A generation module for generating a public rule table, a main rule table and a block rule table by:

In one implementation, the generating module is specifically configured to:

determining balance bits of each rule in the rule set to be split;

In one implementation, the processing module 1504 is specifically configured to:

In one implementation, the determining module 1502 is specifically configured to:

In one implementation, the matching module 1503 is specifically configured to:

The embodiment of the present invention also provides an electronic device, as shown in fig. 16, including a processor 1601, a communication interface 1602, a memory 1603, and a communication bus 1604, where the processor 1601, the communication interface 1602, and the memory 1603 perform communication with each other through the communication bus 1604,

A memory 1603 for storing a computer program;

the processor 1601 is configured to implement the steps of the rule storing method or the message processing method when executing the program stored in the memory 1603.

The communication bus mentioned above for the electronic device may be a peripheral component interconnect standard (PERIPHERAL COMPONENT INTERCONNECT, PCI) bus or an extended industry standard architecture (Extended Industry Standard Architecture, EISA) bus, etc. The communication bus may be classified as an address bus, a data bus, a control bus, or the like. For ease of illustration, the figures are shown with only one bold line, but not with only one bus or one type of bus.

The communication interface is used for communication between the electronic device and other devices.

The Memory may include random access Memory (Random Access Memory, RAM) or may include Non-Volatile Memory (NVM), such as at least one disk Memory. Optionally, the memory may also be at least one memory device located remotely from the aforementioned processor.

The processor may be a general-purpose processor, including a central processing unit (Central Processing Unit, CPU), a network processor (Network Processor, NP), etc.; but may also be a digital signal Processor (DIGITAL SIGNAL Processor, DSP), application SPECIFIC INTEGRATED Circuit (ASIC), field-Programmable gate array (Field-Programmable GATE ARRAY, FPGA) or other Programmable logic device, discrete gate or transistor logic device, discrete hardware components.

In yet another embodiment of the present invention, a computer readable storage medium is provided, in which a computer program is stored, the computer program implementing the steps of the rule storing method or the message processing method when being executed by a processor.

In yet another embodiment of the present invention, a computer program product containing instructions is provided, which when run on a computer, causes the computer to perform the steps of the rule storage method or the message processing method of the above embodiments.

In the above embodiments, it may be implemented in whole or in part by software, hardware, firmware, or any combination thereof. When implemented in software, may be implemented in whole or in part in the form of a computer program product. The computer program product includes one or more computer instructions. When loaded and executed on a computer, produces a flow or function in accordance with embodiments of the present invention, in whole or in part. The computer may be a general purpose computer, a special purpose computer, a computer network, or other programmable apparatus. The computer instructions may be stored in or transmitted from one computer-readable storage medium to another, for example, by wired (e.g., coaxial cable, optical fiber, digital Subscriber Line (DSL)), or wireless (e.g., infrared, wireless, microwave, etc.). The computer readable storage medium may be any available medium that can be accessed by a computer or a data storage device such as a server, data center, etc. that contains an integration of one or more available media. The usable medium may be a magnetic medium (e.g., floppy disk, hard disk, tape), an optical medium (e.g., DVD), or a semiconductor medium (e.g., solid state disk Solid STATE DISK (SSD)), etc.

It is noted that relational terms such as first and second, and the like are used solely to distinguish one entity or action from another entity or action without necessarily requiring or implying any actual such relationship or order between such entities or actions. Moreover, the terms "comprises," "comprising," or any other variation thereof, are intended to cover a non-exclusive inclusion, such that a process, method, article, or apparatus that comprises a list of elements does not include only those elements but may include other elements not expressly listed or inherent to such process, method, article, or apparatus. Without further limitation, an element defined by the phrase "comprising one … …" does not exclude the presence of other like elements in a process, method, article, or apparatus that comprises the element.

In this specification, each embodiment is described in a related manner, and identical and similar parts of each embodiment are all referred to each other, and each embodiment mainly describes differences from other embodiments. In particular, for system embodiments, since they are substantially similar to method embodiments, the description is relatively simple, as relevant to see a section of the description of method embodiments.

The foregoing description is only of the preferred embodiments of the present invention and is not intended to limit the scope of the present invention. Any modification, equivalent replacement, improvement, etc. made within the spirit and principle of the present invention are included in the protection scope of the present invention.

Claims

1. A rule storage method, characterized in that the method is applied to an electronic device, wherein the electronic device is provided with a RAM, and the method comprises:

Acquire a rule to be stored, wherein the rule to be stored includes a matching domain, wherein the matching domain includes target rule data, and the target rule data is a key value and a mask in the matching domain;

The types of the check blocks include mask type and non-mask type, the rule data in the check blocks of the mask type include a key value and a mask, the rule data in the check blocks of the non-mask type include a key value with continuous validity bits, excluding a mask, and the validity bit is a bit with a mask value of 1;

The converting the target rule data into at least one check block comprises:

Taking the first valid bit of the target rule data as the current starting bit, based on the encoding conditions satisfied by the rule data of a first number of consecutive bits starting from the current starting bit, converting the rule data of a first number of consecutive bits into a check block; the first number is less than or equal to the CPU bit width of the electronic device and greater than a preset number, and the preset number is the number of bits used to store the key value in the check block of the mask type;

The first valid bit is searched from the bits in the target rule data that have not yet been converted into the check block, the found valid bit is used as the current starting bit, the encoding condition satisfied by the rule data based on the first number of consecutive bits starting from the current starting bit is returned, and the step of converting the first number of consecutive bits of rule data into a check block is performed until all the rule data with valid bits included in the target rule data are converted into check blocks.

2. The method according to claim 1, characterized in that the step of converting the first number of consecutive regular data bits starting from the current start bit into a check block based on the encoding condition satisfied by the first number of consecutive regular data bits starting from the current start bit comprises:

Determining whether the first number of consecutive bits of regular data meet a non-mask type encoding condition;

If satisfied, converting the key value in the first number of consecutive bits of rule data into the non-mask type check block;

If not, the first number is determined to be the preset number, and the key value and mask in the rule data of the continuous first number of bits are converted into a check block of the mask type.

3. The method according to claim 2, characterized in that the non-mask type includes a full data type, a first length type, and a second length type;

The encoding conditions of the full data type include: the current starting bit is the first bit of a byte included in the target rule data; and in the mask of the target rule data, the values of consecutive CPU bit width bits starting from the current starting bit are all 1, and the first number is the CPU bit width;

The encoding condition of the first length type includes: the current start bit is the first bit of a byte included in the target rule data; and in the mask of the target rule data, the values of the first number of bits starting from the current start bit are all 1, and the first number is less than the difference between the CPU bit width and the number of bits occupied by the check block type field;

The encoding condition of the second length type includes: the current start bit is not the first bit of a byte included in the target rule data; and in the mask of the target rule data, the values of the first number of bits starting from the current start bit are all 1, and the first number is less than the difference between the CPU bit width and the number of bits occupied by the check block type field and the number of bits occupied by the start bit field;

The determining whether the first number of consecutive regular data bits meets a non-mask type encoding condition includes:

If the regular data of the first number of consecutive bits meets any one of the encoding conditions of the full data type, the first length type and the second length type, it is determined that the encoding condition of the non-mask type is met; otherwise, it is determined that the encoding condition of the non-mask type is not met.

4. The method according to claim 3, characterized in that the step of converting the key value in the first number of consecutive bits of regular data into the non-mask type check block comprises:

If the first number of consecutive digits of regular data meet the encoding condition of the full data type, converting the key value in the first number of consecutive digits of regular data into a check block of the full data type;

If the first number of consecutive regular data bits meet the encoding condition of the first length type and do not meet the encoding condition of the full data type, converting the key value in the first number of consecutive regular data bits into a check block of the first length type;

If the first number of consecutive regular data bits meet the encoding condition of the second length type, the first number of consecutive regular data bits are converted into a check block of the second length type.

5. The method according to claim 4, characterized in that

The check block of all data types is used to store the key value in the rule data of the continuous first number of bits;

The lowest three bits of the check block of the first length type are used to store the type code of the first length type, and the bits from the highest bit to the fourth to last bit are used to store: the key value in the rule data of the first number of bits and a 0, and the value of the unoccupied bit is set to 1 by default;

The highest three bits in the check block of the second length type are used to store the offset of the current start bit within the byte, the lowest three bits are used to store the type code of the second length type, and the remaining bits are used to store in sequence: the key value in the rule data of the continuous first number of bits and a 0, and the unoccupied bits are set to 1 by default;

The highest three bits in the check block of the mask type are used to store the offset of the current starting bit within the byte, the lowest three bits are used to store the type code of the mask type, and the remaining bits are used to store in sequence: the key value and mask in the rule data of the continuous first number of bits.

6. The method according to any one of claims 1 to 5, characterized in that the method further comprises:

If the target rule data includes range-type rule data, and the maximum value and the minimum value of the range-type rule data are both less than 2 ¹³ , converting the range-type rule data into a check block of the first range type;

If the minimum value of the range-type rule data is greater than or equal to 2 ¹³ , or the maximum value is greater than or equal to 2 ¹³ , converting the range-type rule data into a second range-type check block and a third range-type check block;

The highest 13 bits of the check block of the first range type are used to store the maximum value, the following 13 bits are used to store the minimum value, the following 2 bits are used to store the first subtype code, and the lowest 3 bits are used to store the code of the range type, and the first subtype code is used to indicate that the check block includes a matching range;

The highest 26 bits of the second range type check block are used to store the minimum value, the following two bits are used to store the second subtype code, and the lowest 3 bits are used to store the code of the range type, and the second subtype code is used to indicate that the check block includes a minimum value of a matching range;

The highest 26 bits of the third range type check block are used to store the maximum value, the following two bits are used to store the third subtype code, and the lowest 3 bits are used to store the range type code, and the third subtype code is used to indicate that the check block includes a maximum value of a matching range.

7. The method according to claim 6 is characterized in that each check block stored in the RAM includes a byte offset field before it, and the byte offset field before each check block is used to indicate the byte offset of the starting bit of the rule data in the check block in the target rule data.

8. The method according to claim 1, characterized in that the obtaining of the rules to be stored comprises:

Acquire a global rule set and common rules of a plurality of rules included in the global rule set;

Based on the common rules, pending rules corresponding to each rule included in the global rule set are generated, and each pending rule is used as the rule to be stored; for each bit, if a rule has the same value in the bit as the common rule corresponding to the rule, then the value of the pending rule corresponding to the rule in the bit is a wildcard, otherwise the value of the pending rule corresponding to the rule in the bit is the same as the value of the rule in the bit.

9. A message processing method, characterized in that the method is applied to an electronic device, wherein a random access memory RAM is provided in the electronic device, and the target rule data in the matching domain of each rule in the specified rule table of the RAM is stored in the form of a check block, and the types of the check block include a mask type and a non-mask type, and the rule data in the check block of the mask type includes a key value and a mask, and the rule data in the check block of the non-mask type includes a key value with continuous effective bits, and does not include a mask, and the effective bit is a bit with a mask value of 1; characterized in that the method comprises:

Extract and search key values from the message to be processed;

Determine the to-be-matched rule in the specified rule table based on the search key value;

For each check block included in the to-be-matched rule, determining the length of the to-be-matched data according to the type of the check block;

According to the starting position of the rule data included in the check block, starting from the same starting position in the search key value, extracting the data to be matched according to the length of the data to be matched, and matching the data to be matched with the rule data included in the check block;

If the search key value successfully matches all the check blocks in the to-be-matched rule, it is determined that the search key value successfully matches the to-be-matched rule;

Based on the matching result between the search key value and the rule to be matched, the message to be processed is processed.

10. The method according to claim 9, characterized in that the RAM further stores a linear table, the linear table includes a plurality of base addresses, and the base addresses are used to locate the block rule table; the step of determining the to-be-matched rule in the specified rule table based on the search key value comprises:

Using bits within a preset range in the search key value as a search index, and determining a target base address pointed to by the search index in the linear table;

Locating a block rule table based on the target base address, and using the located block rule table as the designated rule table;

The rules included in the specified rule table are used as rules to be matched.

11. The method according to claim 9, characterized in that the electronic device is further provided with a ternary content addressable memory TCAM, the TCAM stores a common rule table, and the RAM stores a main rule table and a block rule table:

The block rule table stores a plurality of rules having the same common rule;

The main rule table includes at least two fields: a split position set and a base address. The rules in the block rule table belong to a subtree determined by the split position set. The split position set is used to locate the position of the rule corresponding to the key value in the block rule table. The base address is used to locate the block rule table. The value of the non-wildcard bit in the common rule is the same as the value of the same bit of all rules in the block rule table pointed to by the base address.

The common rule table stores common rules, and the common rule table has the same index as the main rule table corresponding to the same block rule table;

The determining the to-be-matched rule in the specified rule table based on the search key value includes:

Using the search key value to perform a match in the common rule table, obtaining a primary index of a target entry in the main rule table;

Locate a block rule table based on a base address included in the target table entry pointed to by the primary index, and use the located block rule table as the designated rule table;

Determine a secondary index of a to-be-matched rule in the specified rule table based on the search key value and a split position set included in the target table entry pointed to by the primary index;

The rule pointed to by the secondary index is used as the rule to be matched.

12. The method according to claim 11, characterized in that the common rule table, the main rule table and the block rule table are generated by:

Construct a rule decision tree based on the balance bit of each rule in the global rule set, where the balance bit is the bit with the smallest difference between the number of rules with a value of 0 and the number of rules with a value of 1;

Starting from each leaf node of the rule decision tree, traverse upward in breadth-first order to obtain the deepest rule subtree corresponding to each leaf node, wherein the deepest rule subtree is the deepest rule subtree among the rule subtrees whose number of balance bits is less than or equal to the preset splitting bit depth;

Based on each deepest rule subtree, the common rule table, the main rule table and the block rule table are generated.

13. The method according to claim 12, characterized in that the generating the common rule table, the main rule table and the block rule table based on each deepest rule subtree comprises:

Based on the rule sets included in each deepest rule subtree, a block rule table is generated respectively;

Based on the balance bits included in each deepest rule subtree, a split position set is generated respectively;

Generate the main rule table based on the split position set corresponding to each deepest rule subtree and the base address of the block rule table;

The common rule table is generated based on the table entry index in the main rule table corresponding to each deepest rule subtree and the common rules of the rule set included in each deepest rule subtree.

14. The method according to claim 12, characterized in that the step of constructing a rule decision tree based on the balance position of each rule in the global rule set comprises:

Using a global rule set as a rule set to be split, wherein the global rule set is included in a root node of a rule decision tree;

Determine the balance position of each rule in the rule set to be split;

Add the rule whose balance bit value is 0 in the to-be-split rule set to the first side child node, and add the rule whose balance bit value is 1 in the to-be-split rule set to the second side child node;

For each child node obtained by splitting, if the child node includes multiple rules, the rule set included in the child node is used as the rule set to be split, and the step of determining the balance position of each rule in the rule set to be split is re-executed until each child node obtained by splitting includes one rule, thereby obtaining the rule decision tree.

15. The method according to any one of claims 9 to 11, characterized in that the processing of the message to be processed based on the matching result between the search key value and the rule to be matched comprises:

If there is one rule to be matched, and the search key value successfully matches the rule to be matched, the message to be processed is processed according to the action field corresponding to the rule to be matched;

If there are multiple rules to be matched, the message to be processed is processed according to the action field corresponding to a rule to be matched that successfully matches the search key value.

16. The method according to claim 9, wherein determining the length of the data to be matched according to the type of the check block comprises:

If the type of the check block is the mask type, determining that the length of the data to be matched is a length of a preset number of bits; the preset number is the number of bits used to store the key value in the check block of the mask type;

The non-mask type includes a full data type, a first length type, and a second length type;

If the type of the check block is the full data type, determining that the length of the data to be matched is the CPU bit width of the electronic device;

If the type of the check block is the first length type or the second length type, search for the first bit whose value is 0 from the lowest bit of the rule data included in the check block toward the highest bit, and determine that the length of the data to be matched is the length from the highest bit to the bit found;

If the type of the check block is a range type, the length of the data to be matched is determined to be a fixed length of the range type field.

17. The method according to claim 9, characterized in that the step of matching the data to be matched with the rule data included in the verification block comprises:

If the type of the check block is the mask type, the key value in the check block and the mask are ANDed, and the result obtained after the ANDed operation is compared with the data to be matched. If they are completely consistent, the match is successful;

If the type of the check block is the full data type, the data to be matched is compared with all the rule data in the check block. If they are completely consistent, the match is successful;

If the type of the check block is the first length type or the second length type, starting from the highest bit of the rule data included in the check block, extract the rule data according to the length of the data to be matched, and compare the extracted rule data with the data to be matched. If they are completely consistent, the match is successful;

If the type of the check block is a range type, a matching range is obtained from the check block, and if the data to be matched belongs to the matching range, the match is successful.

18. A rule storage device, characterized in that the device is applied to an electronic device, the electronic device is provided with a RAM, and the device comprises:

An acquisition module, used for acquiring rules to be stored, wherein the rules to be stored include a matching domain, wherein the matching domain includes target rule data, and the target rule data is a key value and a mask in the matching domain;

A conversion module, used for converting the target rule data into at least one check block;

A storage module, used for storing the target rule data in the RAM in the form of a check block;

The conversion module is specifically used for:

The first valid bit is searched from the bits in the target rule data that have not been converted into the check block, the found valid bit is used as the current starting bit, the encoding condition satisfied by the rule data based on the first number of consecutive bits starting from the current starting bit is returned, and the step of converting the first number of consecutive bits of rule data into a check block is performed until all the rule data with valid bits included in the target rule data are converted into check blocks.

19. The device according to claim 18, characterized in that the conversion module is further used for:

20. The device according to claim 18 is characterized in that each check block stored in the RAM includes a byte offset field before it, and the byte offset field before each check block is used to indicate the byte offset of the starting bit of the rule data in the check block in the target rule data.

21. A message processing device, characterized in that the device is applied to an electronic device, wherein a random access memory RAM is provided in the electronic device, and the target rule data in the matching domain of each rule in the specified rule table of the RAM is stored in the form of a check block, and the types of the check block include a mask type and a non-mask type, and the rule data in the check block of the mask type includes a key value and a mask, and the rule data in the check block of the non-mask type includes a key value with continuous effective bits, and does not include a mask, and the effective bit is a bit with a mask value of 1; characterized in that the device comprises:

An extraction module is used to extract and search key values from the message to be processed;

A determination module, configured to determine the to-be-matched rule in the specified rule table based on the search key value; and for each check block included in the to-be-matched rule, determine the length of the to-be-matched data according to the type of the check block;

A matching module, configured to extract the data to be matched according to the length of the data to be matched, starting from the same starting position in the search key value according to the starting position of the rule data included in the check block, and match the data to be matched with the rule data included in the check block; if the search key value successfully matches all the check blocks in the rule to be matched, it is determined that the search key value successfully matches the rule to be matched;

A processing module is used to process the message to be processed based on the matching result between the search key value and the rule to be matched.

22. The device according to claim 21, characterized in that the RAM further stores a linear table, the linear table includes a plurality of base addresses, and the base addresses are used to locate the block rule table; the determination module is specifically used to:

The rules included in the specified rule table are used as rules to be matched.

23. The device according to claim 21, characterized in that the electronic device is further provided with a ternary content addressable memory TCAM, the TCAM stores a public rule table, and the RAM stores a main rule table and a block rule table:

The block rule table stores a plurality of rules having the same common rule;

The determining module is specifically used for:

The rule pointed to by the secondary index is used as the rule to be matched.

24. An electronic device, characterized in that it comprises a processor, a communication interface, a memory and a communication bus, wherein the processor, the communication interface and the memory communicate with each other via the communication bus;

Memory, used to store computer programs;

A processor, for implementing the method steps described in any one of claims 1-8 or 9-17 when executing a program stored in a memory.

25. A computer-readable storage medium, characterized in that a computer program is stored in the computer-readable storage medium, and when the computer program is executed by a processor, the method steps described in any one of claims 1-8 or 9-17 are implemented.