2 Copyright(c) 2010-2015 Intel Corporation. All rights reserved.
5 Redistribution and use in source and binary forms, with or without
6 modification, are permitted provided that the following conditions
9 * Redistributions of source code must retain the above copyright
10 notice, this list of conditions and the following disclaimer.
11 * Redistributions in binary form must reproduce the above copyright
12 notice, this list of conditions and the following disclaimer in
13 the documentation and/or other materials provided with the
15 * Neither the name of Intel Corporation nor the names of its
16 contributors may be used to endorse or promote products derived
17 from this software without specific prior written permission.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 Packet Classification and Access Control
32 ========================================
34 The DPDK provides an Access Control library that gives the ability
35 to classify an input packet based on a set of classification rules.
37 The ACL library is used to perform an N-tuple search over a set of rules with multiple categories
38 and find the best match (highest priority) for each category.
39 The library API provides the following basic operations:
41 * Create a new Access Control (AC) context.
43 * Add rules into the context.
45 * For all rules in the context, build the runtime structures necessary to perform packet classification.
47 * Perform input packet classifications.
49 * Destroy an AC context and its runtime structures and free the associated memory.
57 The current implementation allows the user for each AC context to specify its own rule (set of fields)
58 over which packet classification will be performed.
59 Though there are few restrictions on the rule fields layout:
61 * First field in the rule definition has to be one byte long.
62 * All subsequent fields has to be grouped into sets of 4 consecutive bytes.
64 This is done mainly for performance reasons - search function processes the first input byte as part of the flow setup and then the inner loop of the search function is unrolled to process four input bytes at a time.
66 To define each field inside an AC rule, the following structure is used:
70 struct rte_acl_field_def {
71 uint8_t type; /*< type - ACL_FIELD_TYPE. */
72 uint8_t size; /*< size of field 1,2,4, or 8. */
73 uint8_t field_index; /*< index of field inside the rule. */
74 uint8_t input_index; /*< 0-N input index. */
75 uint32_t offset; /*< offset to start of field. */
79 The field type is one of three choices:
81 * _MASK - for fields such as IP addresses that have a value and a mask defining the number of relevant bits.
83 * _RANGE - for fields such as ports that have a lower and upper value for the field.
85 * _BITMASK - for fields such as protocol identifiers that have a value and a bit mask.
88 The size parameter defines the length of the field in bytes. Allowable values are 1, 2, 4, or 8 bytes.
89 Note that due to the grouping of input bytes, 1 or 2 byte fields must be defined as consecutive fields
90 that make up 4 consecutive input bytes.
91 Also, it is best to define fields of 8 or more bytes as 4 byte fields so that
92 the build processes can eliminate fields that are all wild.
95 A zero-based value that represents the position of the field inside the rule; 0 to N-1 for N fields.
98 As mentioned above, all input fields, except the very first one, must be in groups of 4 consecutive bytes.
99 The input index specifies to which input group that field belongs to.
102 The offset field defines the offset for the field.
103 This is the offset from the beginning of the buffer parameter for the search.
105 For example, to define classification for the following IPv4 5-tuple structure:
117 The following array of field definitions can be used:
121 struct rte_acl_field_def ipv4_defs[5] = {
122 /* first input field - always one byte long. */
124 .type = RTE_ACL_FIELD_TYPE_BITMASK,
125 .size = sizeof (uint8_t),
128 .offset = offsetof (struct ipv4_5tuple, proto),
131 /* next input field (IPv4 source address) - 4 consecutive bytes. */
133 .type = RTE_ACL_FIELD_TYPE_MASK,
134 .size = sizeof (uint32_t),
137 .offset = offsetof (struct ipv4_5tuple, ip_src),
140 /* next input field (IPv4 destination address) - 4 consecutive bytes. */
142 .type = RTE_ACL_FIELD_TYPE_MASK,
143 .size = sizeof (uint32_t),
146 .offset = offsetof (struct ipv4_5tuple, ip_dst),
150 * Next 2 fields (src & dst ports) form 4 consecutive bytes.
151 * They share the same input index.
154 .type = RTE_ACL_FIELD_TYPE_RANGE,
155 .size = sizeof (uint16_t),
158 .offset = offsetof (struct ipv4_5tuple, port_src),
162 .type = RTE_ACL_FIELD_TYPE_RANGE,
163 .size = sizeof (uint16_t),
166 .offset = offsetof (struct ipv4_5tuple, port_dst),
170 A typical example of such an IPv4 5-tuple rule is a follows:
174 source addr/mask destination addr/mask source ports dest ports protocol/mask
175 192.168.1.0/24 192.168.2.31/32 0:65535 1234:1234 17/0xff
177 Any IPv4 packets with protocol ID 17 (UDP), source address 192.168.1.[0-255], destination address 192.168.2.31,
178 source port [0-65535] and destination port 1234 matches the above rule.
180 To define classification for the IPv6 2-tuple: <protocol, IPv6 source address> over the following IPv6 header structure:
184 struct struct ipv6_hdr {
185 uint32_t vtc_flow; /* IP version, traffic class & flow label. */
186 uint16_t payload_len; /* IP packet length - includes sizeof(ip_header). */
187 uint8_t proto; /* Protocol, next header. */
188 uint8_t hop_limits; /* Hop limits. */
189 uint8_t src_addr[16]; /* IP address of source host. */
190 uint8_t dst_addr[16]; /* IP address of destination host(s). */
191 } __attribute__((__packed__));
193 The following array of field definitions can be used:
197 struct struct rte_acl_field_def ipv6_2tuple_defs[5] = {
199 .type = RTE_ACL_FIELD_TYPE_BITMASK,
200 .size = sizeof (uint8_t),
203 .offset = offsetof (struct ipv6_hdr, proto),
207 .type = RTE_ACL_FIELD_TYPE_MASK,
208 .size = sizeof (uint32_t),
211 .offset = offsetof (struct ipv6_hdr, src_addr[0]),
215 .type = RTE_ACL_FIELD_TYPE_MASK,
216 .size = sizeof (uint32_t),
219 .offset = offsetof (struct ipv6_hdr, src_addr[4]),
223 .type = RTE_ACL_FIELD_TYPE_MASK,
224 .size = sizeof (uint32_t),
227 .offset = offsetof (struct ipv6_hdr, src_addr[8]),
231 .type = RTE_ACL_FIELD_TYPE_MASK,
232 .size = sizeof (uint32_t),
235 .offset = offsetof (struct ipv6_hdr, src_addr[12]),
239 A typical example of such an IPv6 2-tuple rule is a follows:
243 source addr/mask protocol/mask
244 2001:db8:1234:0000:0000:0000:0000:0000/48 6/0xff
246 Any IPv6 packets with protocol ID 6 (TCP), and source address inside the range
247 [2001:db8:1234:0000:0000:0000:0000:0000 - 2001:db8:1234:ffff:ffff:ffff:ffff:ffff] matches the above rule.
249 In the following example the last element of the search key is 8-bit long.
250 So it is a case where the 4 consecutive bytes of an input field are not fully occupied.
251 The structure for the classification is:
259 uint8_t tos; /*< This is partially using a 32-bit input element */
262 The following array of field definitions can be used:
266 struct rte_acl_field_def ipv4_defs[4] = {
267 /* first input field - always one byte long. */
269 .type = RTE_ACL_FIELD_TYPE_BITMASK,
270 .size = sizeof (uint8_t),
273 .offset = offsetof (struct acl_key, ip_proto),
276 /* next input field (IPv4 source address) - 4 consecutive bytes. */
278 .type = RTE_ACL_FIELD_TYPE_MASK,
279 .size = sizeof (uint32_t),
282 .offset = offsetof (struct acl_key, ip_src),
285 /* next input field (IPv4 destination address) - 4 consecutive bytes. */
287 .type = RTE_ACL_FIELD_TYPE_MASK,
288 .size = sizeof (uint32_t),
291 .offset = offsetof (struct acl_key, ip_dst),
295 * Next element of search key (Type of Service) is indeed 1 byte long.
296 * Anyway we need to allocate all the 4 consecutive bytes for it.
299 .type = RTE_ACL_FIELD_TYPE_BITMASK,
300 .size = sizeof (uint32_t), /* All the 4 consecutive bytes are allocated */
303 .offset = offsetof (struct acl_key, tos),
307 A typical example of such an IPv4 4-tuple rule is as follows:
311 source addr/mask destination addr/mask tos/mask protocol/mask
312 192.168.1.0/24 192.168.2.31/32 1/0xff 6/0xff
314 Any IPv4 packets with protocol ID 6 (TCP), source address 192.168.1.[0-255], destination address 192.168.2.31,
315 ToS 1 matches the above rule.
317 When creating a set of rules, for each rule, additional information must be supplied also:
319 * **priority**: A weight to measure the priority of the rules (higher is better).
320 If the input tuple matches more than one rule, then the rule with the higher priority is returned.
321 Note that if the input tuple matches more than one rule and these rules have equal priority,
322 it is undefined which rule is returned as a match.
323 It is recommended to assign a unique priority for each rule.
325 * **category_mask**: Each rule uses a bit mask value to select the relevant category(s) for the rule.
326 When a lookup is performed, the result for each category is returned.
327 This effectively provides a "parallel lookup" by enabling a single search to return multiple results if,
328 for example, there were four different sets of ACL rules, one for access control, one for routing, and so on.
329 Each set could be assigned its own category and by combining them into a single database,
330 one lookup returns a result for each of the four sets.
332 * **userdata**: A user-defined value.
333 For each category, a successful match returns the userdata field of the highest priority matched rule.
334 When no rules match, returned value is zero.
338 When adding new rules into an ACL context, all fields must be in host byte order (LSB).
339 When the search is performed for an input tuple, all fields in that tuple must be in network byte order (MSB).
344 Build phase (rte_acl_build()) creates for a given set of rules internal structure for further run-time traversal.
345 With current implementation it is a set of multi-bit tries (with stride == 8).
346 Depending on the rules set, that could consume significant amount of memory.
347 In attempt to conserve some space ACL build process tries to split the given
348 rule-set into several non-intersecting subsets and construct a separate trie
350 Depending on the rule-set, it might reduce RT memory requirements but might
351 increase classification time.
352 There is a possibility at build-time to specify maximum memory limit for internal RT structures for given AC context.
353 It could be done via **max_size** field of the **rte_acl_config** structure.
354 Setting it to the value greater than zero, instructs rte_acl_build() to:
356 * attempt to minimize number of tries in the RT table, but
357 * make sure that size of RT table wouldn't exceed given value.
359 Setting it to zero makes rte_acl_build() to use the default behavior:
360 try to minimize size of the RT structures, but doesn't expose any hard limit on it.
362 That gives the user the ability to decisions about performance/space trade-off.
367 struct rte_acl_ctx * acx;
368 struct rte_acl_config cfg;
372 * assuming that acx points to already created and
373 * populated with rules AC context and cfg filled properly.
376 /* try to build AC context, with RT structures less then 8MB. */
377 cfg.max_size = 0x800000;
378 ret = rte_acl_build(acx, &cfg);
381 * RT structures can't fit into 8MB for given context.
382 * Try to build without exposing any hard limit.
384 if (ret == -ERANGE) {
386 ret = rte_acl_build(acx, &cfg);
391 Classification methods
392 ~~~~~~~~~~~~~~~~~~~~~~
394 After rte_acl_build() over given AC context has finished successfully, it can be used to perform classification - search for a rule with highest priority over the input data.
395 There are several implementations of classify algorithm:
397 * **RTE_ACL_CLASSIFY_SCALAR**: generic implementation, doesn't require any specific HW support.
399 * **RTE_ACL_CLASSIFY_SSE**: vector implementation, can process up to 8 flows in parallel. Requires SSE 4.1 support.
401 * **RTE_ACL_CLASSIFY_AVX2**: vector implementation, can process up to 16 flows in parallel. Requires AVX2 support.
403 It is purely a runtime decision which method to choose, there is no build-time difference.
404 All implementations operates over the same internal RT structures and use similar principles. The main difference is that vector implementations can manually exploit IA SIMD instructions and process several input data flows in parallel.
405 At startup ACL library determines the highest available classify method for the given platform and sets it as default one. Though the user has an ability to override the default classifier function for a given ACL context or perform particular search using non-default classify method. In that case it is user responsibility to make sure that given platform supports selected classify implementation.
407 Application Programming Interface (API) Usage
408 ---------------------------------------------
412 For more details about the Access Control API, please refer to the *DPDK API Reference*.
414 The following example demonstrates IPv4, 5-tuple classification for rules defined above
415 with multiple categories in more detail.
417 Classify with Multiple Categories
418 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
422 struct rte_acl_ctx * acx;
423 struct rte_acl_config cfg;
426 /* define a structure for the rule with up to 5 fields. */
428 RTE_ACL_RULE_DEF(acl_ipv4_rule, RTE_DIM(ipv4_defs));
430 /* AC context creation parameters. */
432 struct rte_acl_param prm = {
433 .name = "ACL_example",
434 .socket_id = SOCKET_ID_ANY,
435 .rule_size = RTE_ACL_RULE_SZ(RTE_DIM(ipv4_defs)),
437 /* number of fields per rule. */
439 .max_rule_num = 8, /* maximum number of rules in the AC context. */
442 struct acl_ipv4_rule acl_rules[] = {
444 /* matches all packets traveling to 192.168.0.0/16, applies for categories: 0,1 */
446 .data = {.userdata = 1, .category_mask = 3, .priority = 1},
448 /* destination IPv4 */
449 .field[2] = {.value.u32 = IPv4(192,168,0,0),. mask_range.u32 = 16,},
452 .field[3] = {.value.u16 = 0, .mask_range.u16 = 0xffff,},
454 /* destination port */
455 .field[4] = {.value.u16 = 0, .mask_range.u16 = 0xffff,},
458 /* matches all packets traveling to 192.168.1.0/24, applies for categories: 0 */
460 .data = {.userdata = 2, .category_mask = 1, .priority = 2},
462 /* destination IPv4 */
463 .field[2] = {.value.u32 = IPv4(192,168,1,0),. mask_range.u32 = 24,},
466 .field[3] = {.value.u16 = 0, .mask_range.u16 = 0xffff,},
468 /* destination port */
469 .field[4] = {.value.u16 = 0, .mask_range.u16 = 0xffff,},
472 /* matches all packets traveling from 10.1.1.1, applies for categories: 1 */
474 .data = {.userdata = 3, .category_mask = 2, .priority = 3},
477 .field[1] = {.value.u32 = IPv4(10,1,1,1),. mask_range.u32 = 32,},
480 .field[3] = {.value.u16 = 0, .mask_range.u16 = 0xffff,},
482 /* destination port */
483 .field[4] = {.value.u16 = 0, .mask_range.u16 = 0xffff,},
489 /* create an empty AC context */
491 if ((acx = rte_acl_create(&prm)) == NULL) {
493 /* handle context create failure. */
497 /* add rules to the context */
499 ret = rte_acl_add_rules(acx, acl_rules, RTE_DIM(acl_rules));
501 /* handle error at adding ACL rules. */
504 /* prepare AC build config. */
506 cfg.num_categories = 2;
507 cfg.num_fields = RTE_DIM(ipv4_defs);
509 memcpy(cfg.defs, ipv4_defs, sizeof (ipv4_defs));
511 /* build the runtime structures for added rules, with 2 categories. */
513 ret = rte_acl_build(acx, &cfg);
515 /* handle error at build runtime structures for ACL context. */
518 For a tuple with source IP address: 10.1.1.1 and destination IP address: 192.168.1.15,
519 once the following lines are executed:
523 uint32_t results[4]; /* make classify for 4 categories. */
525 rte_acl_classify(acx, data, results, 1, 4);
527 then the results[] array contains:
531 results[4] = {2, 3, 0, 0};
533 * For category 0, both rules 1 and 2 match, but rule 2 has higher priority,
534 therefore results[0] contains the userdata for rule 2.
536 * For category 1, both rules 1 and 3 match, but rule 3 has higher priority,
537 therefore results[1] contains the userdata for rule 3.
539 * For categories 2 and 3, there are no matches, so results[2] and results[3] contain zero,
540 which indicates that no matches were found for those categories.
542 For a tuple with source IP address: 192.168.1.1 and destination IP address: 192.168.2.11,
543 once the following lines are executed:
547 uint32_t results[4]; /* make classify by 4 categories. */
549 rte_acl_classify(acx, data, results, 1, 4);
551 the results[] array contains:
555 results[4] = {1, 1, 0, 0};
557 * For categories 0 and 1, only rule 1 matches.
559 * For categories 2 and 3, there are no matches.
561 For a tuple with source IP address: 10.1.1.1 and destination IP address: 201.212.111.12,
562 once the following lines are executed:
566 uint32_t results[4]; /* make classify by 4 categories. */
567 rte_acl_classify(acx, data, results, 1, 4);
569 the results[] array contains:
573 results[4] = {0, 3, 0, 0};
575 * For category 1, only rule 3 matches.
577 * For categories 0, 2 and 3, there are no matches.