packet_classif_access_ctrl.rst revision 97f17497
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
249In the following example the last element of the search key is 8-bit long.
250So it is a case where the 4 consecutive bytes of an input field are not fully occupied.
251The structure for the classification is:
252
253.. code-block:: c
254
255    struct acl_key {
256        uint8_t ip_proto;
257        uint32_t ip_src;
258        uint32_t ip_dst;
259        uint8_t tos;      /*< This is partially using a 32-bit input element */
260    };
261
262The following array of field definitions can be used:
263
264.. code-block:: c
265
266    struct rte_acl_field_def ipv4_defs[4] = {
267        /* first input field - always one byte long. */
268        {
269            .type = RTE_ACL_FIELD_TYPE_BITMASK,
270            .size = sizeof (uint8_t),
271            .field_index = 0,
272            .input_index = 0,
273            .offset = offsetof (struct acl_key, ip_proto),
274        },
275
276        /* next input field (IPv4 source address) - 4 consecutive bytes. */
277        {
278            .type = RTE_ACL_FIELD_TYPE_MASK,
279            .size = sizeof (uint32_t),
280            .field_index = 1,
281            .input_index = 1,
282           .offset = offsetof (struct acl_key, ip_src),
283        },
284
285        /* next input field (IPv4 destination address) - 4 consecutive bytes. */
286        {
287            .type = RTE_ACL_FIELD_TYPE_MASK,
288            .size = sizeof (uint32_t),
289            .field_index = 2,
290            .input_index = 2,
291           .offset = offsetof (struct acl_key, ip_dst),
292        },
293
294        /*
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.
297         */
298        {
299            .type = RTE_ACL_FIELD_TYPE_BITMASK,
300            .size = sizeof (uint32_t), /* All the 4 consecutive bytes are allocated */
301            .field_index = 3,
302            .input_index = 3,
303            .offset = offsetof (struct acl_key, tos),
304        },
305    };
306
307A typical example of such an IPv4 4-tuple rule is as follows:
308
309::
310
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
313
314Any IPv4 packets with protocol ID 6 (TCP), source address 192.168.1.[0-255], destination address 192.168.2.31,
315ToS 1 matches the above rule.
316
317When creating a set of rules, for each rule, additional information must be supplied also:
318
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.
324
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.
331
332*   **userdata**: A user-defined field that could be any value except zero.
333    For each category, a successful match returns the userdata field of the highest priority matched rule.
334
335.. note::
336
337    When adding new rules into an ACL context, all fields must be in host byte order (LSB).
338    When the search is performed for an input tuple, all fields in that tuple must be in network byte order (MSB).
339
340RT memory size limit
341~~~~~~~~~~~~~~~~~~~~
342
343Build phase (rte_acl_build()) creates for a given set of rules internal structure for further run-time traversal.
344With current implementation it is a set of multi-bit tries (with stride == 8).
345Depending on the rules set, that could consume significant amount of memory.
346In attempt to conserve some space ACL build process tries to split the given
347rule-set into several non-intersecting subsets and construct a separate trie
348for each of them.
349Depending on the rule-set, it might reduce RT memory requirements but might
350increase classification time.
351There is a possibility at build-time to specify maximum memory limit for internal RT structures for given AC context.
352It could be done via **max_size** field of the **rte_acl_config** structure.
353Setting it to the value greater than zero, instructs rte_acl_build() to:
354
355*   attempt to minimize number of tries in the RT table, but
356*   make sure that size of RT table wouldn't exceed given value.
357
358Setting it to zero makes rte_acl_build() to use the default behavior:
359try to minimize size of the RT structures, but doesn't expose any hard limit on it.
360
361That gives the user the ability to decisions about performance/space trade-off.
362For example:
363
364.. code-block:: c
365
366    struct rte_acl_ctx * acx;
367    struct rte_acl_config cfg;
368    int ret;
369
370    /*
371     * assuming that acx points to already created and
372     * populated with rules AC context and cfg filled properly.
373     */
374
375     /* try to build AC context, with RT structures less then 8MB. */
376     cfg.max_size = 0x800000;
377     ret = rte_acl_build(acx, &cfg);
378
379     /*
380      * RT structures can't fit into 8MB for given context.
381      * Try to build without exposing any hard limit.
382      */
383     if (ret == -ERANGE) {
384        cfg.max_size = 0;
385        ret = rte_acl_build(acx, &cfg);
386     }
387
388
389
390Classification methods
391~~~~~~~~~~~~~~~~~~~~~~
392
393After 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.
394There are several implementations of classify algorithm:
395
396*   **RTE_ACL_CLASSIFY_SCALAR**: generic implementation, doesn't require any specific HW support.
397
398*   **RTE_ACL_CLASSIFY_SSE**: vector implementation, can process up to 8 flows in parallel. Requires SSE 4.1 support.
399
400*   **RTE_ACL_CLASSIFY_AVX2**: vector implementation, can process up to 16 flows in parallel. Requires AVX2 support.
401
402It is purely a runtime decision which method to choose, there is no build-time difference.
403All 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.
404At 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.
405
406Application Programming Interface (API) Usage
407---------------------------------------------
408
409.. note::
410
411    For more details about the Access Control API, please refer to the *DPDK API Reference*.
412
413The following example demonstrates IPv4, 5-tuple classification for rules defined above
414with multiple categories in more detail.
415
416Classify with Multiple Categories
417~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
418
419.. code-block:: c
420
421    struct rte_acl_ctx * acx;
422    struct rte_acl_config cfg;
423    int ret;
424
425    /* define a structure for the rule with up to 5 fields. */
426
427    RTE_ACL_RULE_DEF(acl_ipv4_rule, RTE_DIM(ipv4_defs));
428
429    /* AC context creation parameters. */
430
431    struct rte_acl_param prm = {
432        .name = "ACL_example",
433        .socket_id = SOCKET_ID_ANY,
434        .rule_size = RTE_ACL_RULE_SZ(RTE_DIM(ipv4_defs)),
435
436        /* number of fields per rule. */
437
438        .max_rule_num = 8, /* maximum number of rules in the AC context. */
439    };
440
441    struct acl_ipv4_rule acl_rules[] = {
442
443        /* matches all packets traveling to 192.168.0.0/16, applies for categories: 0,1 */
444        {
445            .data = {.userdata = 1, .category_mask = 3, .priority = 1},
446
447            /* destination IPv4 */
448            .field[2] = {.value.u32 = IPv4(192,168,0,0),. mask_range.u32 = 16,},
449
450            /* source port */
451            .field[3] = {.value.u16 = 0, .mask_range.u16 = 0xffff,},
452
453            /* destination port */
454           .field[4] = {.value.u16 = 0, .mask_range.u16 = 0xffff,},
455        },
456
457        /* matches all packets traveling to 192.168.1.0/24, applies for categories: 0 */
458        {
459            .data = {.userdata = 2, .category_mask = 1, .priority = 2},
460
461            /* destination IPv4 */
462            .field[2] = {.value.u32 = IPv4(192,168,1,0),. mask_range.u32 = 24,},
463
464            /* source port */
465            .field[3] = {.value.u16 = 0, .mask_range.u16 = 0xffff,},
466
467            /* destination port */
468            .field[4] = {.value.u16 = 0, .mask_range.u16 = 0xffff,},
469        },
470
471        /* matches all packets traveling from 10.1.1.1, applies for categories: 1 */
472        {
473            .data = {.userdata = 3, .category_mask = 2, .priority = 3},
474
475            /* source IPv4 */
476            .field[1] = {.value.u32 = IPv4(10,1,1,1),. mask_range.u32 = 32,},
477
478            /* source port */
479            .field[3] = {.value.u16 = 0, .mask_range.u16 = 0xffff,},
480
481            /* destination port */
482            .field[4] = {.value.u16 = 0, .mask_range.u16 = 0xffff,},
483        },
484
485    };
486
487
488    /* create an empty AC context  */
489
490    if ((acx = rte_acl_create(&prm)) == NULL) {
491
492        /* handle context create failure. */
493
494    }
495
496    /* add rules to the context */
497
498    ret = rte_acl_add_rules(acx, acl_rules, RTE_DIM(acl_rules));
499    if (ret != 0) {
500       /* handle error at adding ACL rules. */
501    }
502
503    /* prepare AC build config. */
504
505    cfg.num_categories = 2;
506    cfg.num_fields = RTE_DIM(ipv4_defs);
507
508    memcpy(cfg.defs, ipv4_defs, sizeof (ipv4_defs));
509
510    /* build the runtime structures for added rules, with 2 categories. */
511
512    ret = rte_acl_build(acx, &cfg);
513    if (ret != 0) {
514       /* handle error at build runtime structures for ACL context. */
515    }
516
517For a tuple with source IP address: 10.1.1.1 and destination IP address: 192.168.1.15,
518once the following lines are executed:
519
520.. code-block:: c
521
522    uint32_t results[4]; /* make classify for 4 categories. */
523
524    rte_acl_classify(acx, data, results, 1, 4);
525
526then the results[] array contains:
527
528.. code-block:: c
529
530    results[4] = {2, 3, 0, 0};
531
532*   For category 0, both rules 1 and 2 match, but rule 2 has higher priority,
533    therefore results[0] contains the userdata for rule 2.
534
535*   For category 1, both rules 1 and 3 match, but rule 3 has higher priority,
536    therefore results[1] contains the userdata for rule 3.
537
538*   For categories 2 and 3, there are no matches, so results[2] and results[3] contain zero,
539    which indicates that no matches were found for those categories.
540
541For a tuple with source IP address: 192.168.1.1 and destination IP address: 192.168.2.11,
542once the following lines are executed:
543
544.. code-block:: c
545
546    uint32_t results[4]; /* make classify by 4 categories. */
547
548    rte_acl_classify(acx, data, results, 1, 4);
549
550the results[] array contains:
551
552.. code-block:: c
553
554    results[4] = {1, 1, 0, 0};
555
556*   For categories 0 and 1, only rule 1 matches.
557
558*   For categories 2 and 3, there are no matches.
559
560For a tuple with source IP address: 10.1.1.1 and destination IP address: 201.212.111.12,
561once the following lines are executed:
562
563.. code-block:: c
564
565    uint32_t results[4]; /* make classify by 4 categories. */
566    rte_acl_classify(acx, data, results, 1, 4);
567
568the results[] array contains:
569
570.. code-block:: c
571
572    results[4] = {0, 3, 0, 0};
573
574*   For category 1, only rule 3 matches.
575
576*   For categories 0, 2 and 3, there are no matches.
577