1.. BSD LICENSE 2 Copyright(c) 2010-2015 Intel Corporation. All rights reserved. 3 All rights reserved. 4 5 Redistribution and use in source and binary forms, with or without 6 modification, are permitted provided that the following conditions 7 are met: 8 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 14 distribution. 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. 18 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. 30 31Packet Classification and Access Control 32======================================== 33 34The DPDK provides an Access Control library that gives the ability 35to classify an input packet based on a set of classification rules. 36 37The ACL library is used to perform an N-tuple search over a set of rules with multiple categories 38and find the best match (highest priority) for each category. 39The library API provides the following basic operations: 40 41* Create a new Access Control (AC) context. 42 43* Add rules into the context. 44 45* For all rules in the context, build the runtime structures necessary to perform packet classification. 46 47* Perform input packet classifications. 48 49* Destroy an AC context and its runtime structures and free the associated memory. 50 51Overview 52-------- 53 54Rule definition 55~~~~~~~~~~~~~~~ 56 57The current implementation allows the user for each AC context to specify its own rule (set of fields) 58over which packet classification will be performed. 59Though there are few restrictions on the rule fields layout: 60 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. 63 64This 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. 65 66To define each field inside an AC rule, the following structure is used: 67 68.. code-block:: c 69 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. */ 76 }; 77 78* type 79 The field type is one of three choices: 80 81 * _MASK - for fields such as IP addresses that have a value and a mask defining the number of relevant bits. 82 83 * _RANGE - for fields such as ports that have a lower and upper value for the field. 84 85 * _BITMASK - for fields such as protocol identifiers that have a value and a bit mask. 86 87* size 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. 93 94* field_index 95 A zero-based value that represents the position of the field inside the rule; 0 to N-1 for N fields. 96 97* input_index 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. 100 101* offset 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. 104 105For example, to define classification for the following IPv4 5-tuple structure: 106 107.. code-block:: c 108 109 struct ipv4_5tuple { 110 uint8_t proto; 111 uint32_t ip_src; 112 uint32_t ip_dst; 113 uint16_t port_src; 114 uint16_t port_dst; 115 }; 116 117The following array of field definitions can be used: 118 119.. code-block:: c 120 121 struct rte_acl_field_def ipv4_defs[5] = { 122 /* first input field - always one byte long. */ 123 { 124 .type = RTE_ACL_FIELD_TYPE_BITMASK, 125 .size = sizeof (uint8_t), 126 .field_index = 0, 127 .input_index = 0, 128 .offset = offsetof (struct ipv4_5tuple, proto), 129 }, 130 131 /* next input field (IPv4 source address) - 4 consecutive bytes. */ 132 { 133 .type = RTE_ACL_FIELD_TYPE_MASK, 134 .size = sizeof (uint32_t), 135 .field_index = 1, 136 .input_index = 1, 137 .offset = offsetof (struct ipv4_5tuple, ip_src), 138 }, 139 140 /* next input field (IPv4 destination address) - 4 consecutive bytes. */ 141 { 142 .type = RTE_ACL_FIELD_TYPE_MASK, 143 .size = sizeof (uint32_t), 144 .field_index = 2, 145 .input_index = 2, 146 .offset = offsetof (struct ipv4_5tuple, ip_dst), 147 }, 148 149 /* 150 * Next 2 fields (src & dst ports) form 4 consecutive bytes. 151 * They share the same input index. 152 */ 153 { 154 .type = RTE_ACL_FIELD_TYPE_RANGE, 155 .size = sizeof (uint16_t), 156 .field_index = 3, 157 .input_index = 3, 158 .offset = offsetof (struct ipv4_5tuple, port_src), 159 }, 160 161 { 162 .type = RTE_ACL_FIELD_TYPE_RANGE, 163 .size = sizeof (uint16_t), 164 .field_index = 4, 165 .input_index = 3, 166 .offset = offsetof (struct ipv4_5tuple, port_dst), 167 }, 168 }; 169 170A typical example of such an IPv4 5-tuple rule is a follows: 171 172:: 173 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 176 177Any IPv4 packets with protocol ID 17 (UDP), source address 192.168.1.[0-255], destination address 192.168.2.31, 178source port [0-65535] and destination port 1234 matches the above rule. 179 180To define classification for the IPv6 2-tuple: <protocol, IPv6 source address> over the following IPv6 header structure: 181 182.. code-block:: c 183 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__)); 192 193The following array of field definitions can be used: 194 195.. code-block:: c 196 197 struct struct rte_acl_field_def ipv6_2tuple_defs[5] = { 198 { 199 .type = RTE_ACL_FIELD_TYPE_BITMASK, 200 .size = sizeof (uint8_t), 201 .field_index = 0, 202 .input_index = 0, 203 .offset = offsetof (struct ipv6_hdr, proto), 204 }, 205 206 { 207 .type = RTE_ACL_FIELD_TYPE_MASK, 208 .size = sizeof (uint32_t), 209 .field_index = 1, 210 .input_index = 1, 211 .offset = offsetof (struct ipv6_hdr, src_addr[0]), 212 }, 213 214 { 215 .type = RTE_ACL_FIELD_TYPE_MASK, 216 .size = sizeof (uint32_t), 217 .field_index = 2, 218 .input_index = 2, 219 .offset = offsetof (struct ipv6_hdr, src_addr[4]), 220 }, 221 222 { 223 .type = RTE_ACL_FIELD_TYPE_MASK, 224 .size = sizeof (uint32_t), 225 .field_index = 3, 226 .input_index = 3, 227 .offset = offsetof (struct ipv6_hdr, src_addr[8]), 228 }, 229 230 { 231 .type = RTE_ACL_FIELD_TYPE_MASK, 232 .size = sizeof (uint32_t), 233 .field_index = 4, 234 .input_index = 4, 235 .offset = offsetof (struct ipv6_hdr, src_addr[12]), 236 }, 237 }; 238 239A typical example of such an IPv6 2-tuple rule is a follows: 240 241:: 242 243 source addr/mask protocol/mask 244 2001:db8:1234:0000:0000:0000:0000:0000/48 6/0xff 245 246Any 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. 248 249When creating a set of rules, for each rule, additional information must be supplied also: 250 251* **priority**: A weight to measure the priority of the rules (higher is better). 252 If the input tuple matches more than one rule, then the rule with the higher priority is returned. 253 Note that if the input tuple matches more than one rule and these rules have equal priority, 254 it is undefined which rule is returned as a match. 255 It is recommended to assign a unique priority for each rule. 256 257* **category_mask**: Each rule uses a bit mask value to select the relevant category(s) for the rule. 258 When a lookup is performed, the result for each category is returned. 259 This effectively provides a "parallel lookup" by enabling a single search to return multiple results if, 260 for example, there were four different sets of ACL rules, one for access control, one for routing, and so on. 261 Each set could be assigned its own category and by combining them into a single database, 262 one lookup returns a result for each of the four sets. 263 264* **userdata**: A user-defined field that could be any value except zero. 265 For each category, a successful match returns the userdata field of the highest priority matched rule. 266 267.. note:: 268 269 When adding new rules into an ACL context, all fields must be in host byte order (LSB). 270 When the search is performed for an input tuple, all fields in that tuple must be in network byte order (MSB). 271 272RT memory size limit 273~~~~~~~~~~~~~~~~~~~~ 274 275Build phase (rte_acl_build()) creates for a given set of rules internal structure for further run-time traversal. 276With current implementation it is a set of multi-bit tries (with stride == 8). 277Depending on the rules set, that could consume significant amount of memory. 278In attempt to conserve some space ACL build process tries to split the given 279rule-set into several non-intersecting subsets and construct a separate trie 280for each of them. 281Depending on the rule-set, it might reduce RT memory requirements but might 282increase classification time. 283There is a possibility at build-time to specify maximum memory limit for internal RT structures for given AC context. 284It could be done via **max_size** field of the **rte_acl_config** strucure. 285Setting it to the value greater than zero, instructs rte_acl_build() to: 286 287* attempt to minimise number of tries in the RT table, but 288* make sure that size of RT table wouldn't exceed given value. 289 290Setting it to zero makes rte_acl_build() to use the default behaviour: 291try to minimise size of the RT structures, but doesn't expose any hard limit on it. 292 293That gives the user the ability to decisions about performance/space trade-off. 294For example: 295 296.. code-block:: c 297 298 struct rte_acl_ctx * acx; 299 struct rte_acl_config cfg; 300 int ret; 301 302 /* 303 * assuming that acx points to already created and 304 * populated with rules AC context and cfg filled properly. 305 */ 306 307 /* try to build AC context, with RT strcutures less then 8MB. */ 308 cfg.max_size = 0x800000; 309 ret = rte_acl_build(acx, &cfg); 310 311 /* 312 * RT strcutures can't fit into 8MB for given context. 313 * Try to build without exposing any hard limit. 314 */ 315 if (ret == -ERANGE) { 316 cfg.max_size = 0; 317 ret = rte_acl_build(acx, &cfg); 318 } 319 320 321 322Classification methods 323~~~~~~~~~~~~~~~~~~~~~~ 324 325After 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. 326There are several implementations of classify algorithm: 327 328* **RTE_ACL_CLASSIFY_SCALAR**: generic implementation, doesn't require any specific HW support. 329 330* **RTE_ACL_CLASSIFY_SSE**: vector implementation, can process up to 8 flows in parallel. Requires SSE 4.1 support. 331 332* **RTE_ACL_CLASSIFY_AVX2**: vector implementation, can process up to 16 flows in parallel. Requires AVX2 support. 333 334It is purely a runtime decision which method to choose, there is no build-time difference. 335All 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. 336At 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. 337 338Application Programming Interface (API) Usage 339--------------------------------------------- 340 341.. note:: 342 343 For more details about the Access Control API, please refer to the *DPDK API Reference*. 344 345The following example demonstrates IPv4, 5-tuple classification for rules defined above 346with multiple categories in more detail. 347 348Classify with Multiple Categories 349~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 350 351.. code-block:: c 352 353 struct rte_acl_ctx * acx; 354 struct rte_acl_config cfg; 355 int ret; 356 357 /* define a structure for the rule with up to 5 fields. */ 358 359 RTE_ACL_RULE_DEF(acl_ipv4_rule, RTE_DIM(ipv4_defs)); 360 361 /* AC context creation parameters. */ 362 363 struct rte_acl_param prm = { 364 .name = "ACL_example", 365 .socket_id = SOCKET_ID_ANY, 366 .rule_size = RTE_ACL_RULE_SZ(RTE_DIM(ipv4_defs)), 367 368 /* number of fields per rule. */ 369 370 .max_rule_num = 8, /* maximum number of rules in the AC context. */ 371 }; 372 373 struct acl_ipv4_rule acl_rules[] = { 374 375 /* matches all packets traveling to 192.168.0.0/16, applies for categories: 0,1 */ 376 { 377 .data = {.userdata = 1, .category_mask = 3, .priority = 1}, 378 379 /* destination IPv4 */ 380 .field[2] = {.value.u32 = IPv4(192,168,0,0),. mask_range.u32 = 16,}, 381 382 /* source port */ 383 .field[3] = {.value.u16 = 0, .mask_range.u16 = 0xffff,}, 384 385 /* destination port */ 386 .field[4] = {.value.u16 = 0, .mask_range.u16 = 0xffff,}, 387 }, 388 389 /* matches all packets traveling to 192.168.1.0/24, applies for categories: 0 */ 390 { 391 .data = {.userdata = 2, .category_mask = 1, .priority = 2}, 392 393 /* destination IPv4 */ 394 .field[2] = {.value.u32 = IPv4(192,168,1,0),. mask_range.u32 = 24,}, 395 396 /* source port */ 397 .field[3] = {.value.u16 = 0, .mask_range.u16 = 0xffff,}, 398 399 /* destination port */ 400 .field[4] = {.value.u16 = 0, .mask_range.u16 = 0xffff,}, 401 }, 402 403 /* matches all packets traveling from 10.1.1.1, applies for categories: 1 */ 404 { 405 .data = {.userdata = 3, .category_mask = 2, .priority = 3}, 406 407 /* source IPv4 */ 408 .field[1] = {.value.u32 = IPv4(10,1,1,1),. mask_range.u32 = 32,}, 409 410 /* source port */ 411 .field[3] = {.value.u16 = 0, .mask_range.u16 = 0xffff,}, 412 413 /* destination port */ 414 .field[4] = {.value.u16 = 0, .mask_range.u16 = 0xffff,}, 415 }, 416 417 }; 418 419 420 /* create an empty AC context */ 421 422 if ((acx = rte_acl_create(&prm)) == NULL) { 423 424 /* handle context create failure. */ 425 426 } 427 428 /* add rules to the context */ 429 430 ret = rte_acl_add_rules(acx, acl_rules, RTE_DIM(acl_rules)); 431 if (ret != 0) { 432 /* handle error at adding ACL rules. */ 433 } 434 435 /* prepare AC build config. */ 436 437 cfg.num_categories = 2; 438 cfg.num_fields = RTE_DIM(ipv4_defs); 439 440 memcpy(cfg.defs, ipv4_defs, sizeof (ipv4_defs)); 441 442 /* build the runtime structures for added rules, with 2 categories. */ 443 444 ret = rte_acl_build(acx, &cfg); 445 if (ret != 0) { 446 /* handle error at build runtime structures for ACL context. */ 447 } 448 449For a tuple with source IP address: 10.1.1.1 and destination IP address: 192.168.1.15, 450once the following lines are executed: 451 452.. code-block:: c 453 454 uint32_t results[4]; /* make classify for 4 categories. */ 455 456 rte_acl_classify(acx, data, results, 1, 4); 457 458then the results[] array contains: 459 460.. code-block:: c 461 462 results[4] = {2, 3, 0, 0}; 463 464* For category 0, both rules 1 and 2 match, but rule 2 has higher priority, 465 therefore results[0] contains the userdata for rule 2. 466 467* For category 1, both rules 1 and 3 match, but rule 3 has higher priority, 468 therefore results[1] contains the userdata for rule 3. 469 470* For categories 2 and 3, there are no matches, so results[2] and results[3] contain zero, 471 which indicates that no matches were found for those categories. 472 473For a tuple with source IP address: 192.168.1.1 and destination IP address: 192.168.2.11, 474once the following lines are executed: 475 476.. code-block:: c 477 478 uint32_t results[4]; /* make classify by 4 categories. */ 479 480 rte_acl_classify(acx, data, results, 1, 4); 481 482the results[] array contains: 483 484.. code-block:: c 485 486 results[4] = {1, 1, 0, 0}; 487 488* For categories 0 and 1, only rule 1 matches. 489 490* For categories 2 and 3, there are no matches. 491 492For a tuple with source IP address: 10.1.1.1 and destination IP address: 201.212.111.12, 493once the following lines are executed: 494 495.. code-block:: c 496 497 uint32_t results[4]; /* make classify by 4 categories. */ 498 rte_acl_classify(acx, data, results, 1, 4); 499 500the results[] array contains: 501 502.. code-block:: c 503 504 results[4] = {0, 3, 0, 0}; 505 506* For category 1, only rule 3 matches. 507 508* For categories 0, 2 and 3, there are no matches. 509