diff options
Diffstat (limited to 'match.c')
| -rw-r--r-- | match.c | 284 |
1 files changed, 284 insertions, 0 deletions
@@ -0,0 +1,284 @@ +/* PIPAPO - PIle PAcket POlicies + * + * match.c - Equivalent match implementation for kernel + * + * Author: Stefano Brivio <sbrivio@redhat.com> + * License: GPLv2 + */ + +#include <stdio.h> +#include <stdint.h> +#include <stdlib.h> +#include <string.h> + +#include "pipapo.h" +#include "util.h" +#include "set.h" +#include "match.h" + +#ifdef MATCH_AVX2 +#include "avx2.h" +#endif + +/** + * match_init() - Initialise equivalent of matching data representation + * @s: Set data + * @layout: Set layout + * + * This conceptually corresponds to the creation of in-kernel matching data. + * + * Return: 0 on success, NULL on failure + */ +struct kernel_set *kernel_init(struct set *s, struct desc_spec **layout) +{ + struct kernel_set *ks; + struct field *f; + int i; + + ks = calloc(sizeof(*ks), 1); + if (!ks) + return NULL; + + for_each_field(f, s, layout) { + ks->offset[i] = f->offset; + ks->groups[i] = f->groups; + ks->bsize[i] = f->bsize; +#ifdef MATCH_AVX2 + ks->lt[i] = aligned_alloc(32, f->groups * f->bsize * BUCKETS); +#else + ks->lt[i] = malloc(f->groups * f->bsize * BUCKETS); +#endif + memcpy(ks->lt[i], f->lt, f->groups * f->bsize * BUCKETS); + +#ifdef MATCH_CTZL + ks->mt[i] = aligned_alloc(8, f->rules * sizeof(*ks->mt[i])); +#else + ks->mt[i] = malloc(f->rules * sizeof(*ks->mt[i])); +#endif + memcpy(ks->mt[i], f->mt, f->rules * sizeof(*ks->mt[i])); + + if (f->bsize > ks->max_bsize) + ks->max_bsize = f->bsize; + } + ks->groups[i] = 0; + +#ifdef MATCH_AVX2 + ks->map[0] = aligned_alloc(32, round_up(ks->max_bsize, 32)); + ks->map[1] = aligned_alloc(32, round_up(ks->max_bsize, 32)); + memset(ks->map[0], 0, ks->max_bsize); + memset(ks->map[1], 0, ks->max_bsize); +#else + ks->map[0] = calloc(ks->max_bsize, 1); + ks->map[1] = calloc(ks->max_bsize, 1); +#endif + + return ks; +} + +#if defined(VERBOSE) && !defined(MATCH_UNROLLED) && !defined(MATCH_AVX2) +/** + * show_match() - Show bucket and bitmap result for a single matching step + * @res: Resulting bitmap to be displayed + * @group_lt: Pointer to lookup table row for current bit group + * @v: Value of packet bytes for current group + * @bsize: Lookup bucket size, in bytes + * + * For documentation purposes only: this shows algorithm step 4.3 in detail. + */ +static void show_match(uint8_t *res, uint8_t *group_lt, int v, int bsize) +{ + uint8_t *bucket = group_lt + v * bsize; + int i; + + fprintf(stdout, " bucket: "); + for (i = 0; i < bsize; i++) + fprintf(stdout, "%02x ", bucket[i]); + fprintf(stdout, "(value: %i)\n", v); + + fprintf(stdout, " result: "); + for (i = 0; i < bsize; i++) + fprintf(stdout, "%02x ", res[i]); + fprintf(stdout, "\n\n"); +} +#else +#define show_match(...) do { } while (0) +#endif + +#ifdef VERBOSE +/** + * show_field() - Show field packet bytes and initial bitmap for given field + * @f: Index of current field in set + * @pkt: Packet bytes for this field + * @init: Initial bitmap + * @bsize: Lookup bucket size, in bytes + * + * For documentation purposes only: this shows algorithm steps 4.1 and 4.2. + */ +static void show_field(int f, uint8_t *pkt, int len, uint8_t *init, int bsize) +{ + int i; + + fprintf(stdout, "\nField %i, packet bytes:", f); + for (i = 0; i < len; i++) + fprintf(stdout, " %02x", pkt[i]); + + fprintf(stdout, ", initial bitmap:"); + for (i = 0; i < bsize; i++) + fprintf(stdout, " %02x", init[i]); + fprintf(stdout, "\n\n"); +} +#else +#define show_field(...) do { } while (0) +#endif + +/* Provide explicitly unrolled versions for lookup steps: the compiler doesn't + * know that only some group sizes make sense. This speeds up non-AVX2 matching. + */ +#define MATCH_REPEAT_4(x) \ + andmem(map[idx], lt + (x + 0 + (*pkt_p >> 4)) * ks->bsize[f], \ + ks->bsize[f]); \ + andmem(map[idx], lt + (x + 16 + (*pkt_p & 0x0f)) * ks->bsize[f], \ + ks->bsize[f]); \ + pkt_p++; \ + andmem(map[idx], lt + (x + 32 + (*pkt_p >> 4)) * ks->bsize[f], \ + ks->bsize[f]); \ + andmem(map[idx], lt + (x + 48 + (*pkt_p & 0x0f)) * ks->bsize[f], \ + ks->bsize[f]); \ + pkt_p++; + +#define MATCH_REPEAT_8(x) \ + MATCH_REPEAT_4(x) \ + MATCH_REPEAT_4(x + 64) + +#define MATCH_REPEAT_12 \ + MATCH_REPEAT_8(0) \ + MATCH_REPEAT_4(128) + +#define MATCH_REPEAT_32 \ + MATCH_REPEAT_8(0) \ + MATCH_REPEAT_8(128) \ + MATCH_REPEAT_8(256) \ + MATCH_REPEAT_8(384) + +/** + * match() - Equivalent of in-kernel matching implementation + * @ks: Kernel representation of set data + * @packet: Packet bytes + * + * This conceptually corresponds to the in-kernel matching function, and it + * implements algorithm steps 4.1 to 4.5. + * + * Return: matched key if any, 0 otherwise + */ +uint32_t match(struct kernel_set *ks, uint8_t *packet) +{ + int f, g, b, match = 0, offset, idx = ks->map_idx; + uint8_t *pkt_p, *lt, v, **map = ks->map; + + (void)g; + (void)v; + (void)offset; + (void)match; + +#ifndef MATCH_AVX2 + /* AVX2 implementation loads all matching buckets first, so an explicit + * initial all-ones bitmap isn't needed. + */ + memset(map[idx], 0xff, ks->max_bsize); +#endif + + /* Go through each set field */ + for (f = 0; ks->groups[f]; f++) { + lt = ks->lt[f]; + pkt_p = packet + ks->offset[f]; + + show_field(f, pkt_p, ks->groups[f] / 2, map[idx], ks->bsize[f]); + + /* For each 4-bit group, select lookup table bucket depending on + * packet bytes value, AND bucket values (steps 4.1 - 4.3). + */ +#ifdef MATCH_UNROLLED + if (ks->groups[f] == 4) { + MATCH_REPEAT_4(0); + } else if (ks->groups[f] == 8) { + MATCH_REPEAT_8(0); + } else if (ks->groups[f] == 12) { + MATCH_REPEAT_12; + } else if (ks->groups[f] == 32) { + MATCH_REPEAT_32; + } +#elif defined(MATCH_AVX2) + match = avx2_lookup(map[idx], lt, pkt_p, ks->groups[f], + ks->bsize[f], f == 0, !ks->groups[f + 1]); + if (match < 0) { + ks->map_idx = idx; + return 0; + } +#else /* !MATCH_UNROLLED && !MATCH_AVX2 */ + for (g = 0; g < ks->groups[f]; g++) { + if (g % 2) { + v = *pkt_p & 0x0f; + pkt_p++; + } else { + v = *pkt_p >> 4; + } + andmem(map[idx], lt + v * ks->bsize[f], ks->bsize[f]); + show_match(map[idx], lt, v, ks->bsize[f]); + lt += ks->bsize[f] * BUCKETS; + } +#endif + + /* Now populate the bitmap for the next field, unless this is + * the last field, in which case return the matched key if any + * (steps 4.4 - 4.5). Now map[idx] contains the matching bitmap, + * and map[!idx] is the bitmap for the next field. + * + * If we used the AVX2-based lookup, and this is the last field, + * we can already give ffs_and_fill() a hint about the position + * of the first bit set: that won't be before a 'match' offset. + */ +#ifdef MATCH_CTZL + b = ffs_and_fill(map[idx], match, ks->bsize[f] / 8, map[!idx], + ks->mt[f], !ks->groups[f + 1]); + if (b < 0) { + ks->map_idx = idx; + return 0; + } + if (!ks->groups[f + 1]) { + /* Last field: we're just returning the key without + * filling the next bitmap, so _map[!idx]_ is clear and + * can be reused as *next* bitmap (not initial) for the + * next packet. + */ + ks->map_idx = idx; + return ks->mt[f][b].key; + } +#else + offset = match = 0; + while ((b = ffs_clear(map[idx], ks->bsize[f], offset)) >= 0) { + if (!ks->groups[f + 1]) { + ks->map_idx = !idx; + return ks->mt[f][b].key; + } + + offset = b / (sizeof(int) * 8); + match = 1; + verbose(" map bit %i: fill %i bit%s from %i\n", b, + ks->mt[f][b].n, ks->mt[f][b].n == 1 ? "" : "s", + ks->mt[f][b].to); + fill(map[!idx], ks->mt[f][b].to, ks->mt[f][b].n); + } + + if (!match) { + ks->map_idx = !idx; + return 0; + } +#endif + /* Swap bitmap indices: map[!idx] will be the initial bitmap, + * and map[idx] is guaranteed to be all-zeroes at this point. + */ + idx = !idx; + } + + return 0; +} |