From a724e8dbd67ce3d9bf5a24bd836dea4ad3a5516f Mon Sep 17 00:00:00 2001 From: Stefano Brivio Date: Tue, 19 Nov 2019 01:18:17 +0100 Subject: pipapo: Initial import Signed-off-by: Stefano Brivio diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..76025f6 --- /dev/null +++ b/Makefile @@ -0,0 +1,78 @@ +CFLAGS += -Wall -Wextra -pedantic -march=native -mtune=native -MMD + +all: pipapo pipapo.debug pipapo.show pipapo.mem pipapo.noavx2 pipapo.nosimd pipapo.check + +SRCS := $(shell find . ! -type l -name "*.c") +OBJS := $(SRCS:.c=.o) +OBJS_DEBUG := $(SRCS:.c=.debug.o) +OBJS_SHOW := $(SRCS:.c=.show.o) +OBJS_MEM := $(SRCS:.c=.mem.o) +OBJS_NOAVX2 := $(SRCS:.c=.noavx2.o) +OBJS_NOSIMD := $(SRCS:.c=.nosimd.o) +OBJS_CHECK := $(SRCS:.c=.check.o) +DEPS := $(OBJS:.o=.d) $(OBJS_DEBUG:.o=.d) $(OBJS_SHOW:.o=.d) $(OBJS_MEM:.o=.d) $(OBJS_NOAVX2:.o=.d) $(OBJS_NOSIMD:.o=.d) $(OBJS_CHECK:.o=.d) + +$(OBJS): CFLAGS += -Ofast -funroll-loops -D__MATCH_AVX2 -D__MATCH_CTZL +$(OBJS_DEBUG): CFLAGS += -O0 -g -D__MATCH_AVX2 -D__MATCH_CTZL +$(OBJS_SHOW): CFLAGS += -DVERBOSE +$(OBJS_MEM): CFLAGS += -DVERBOSE -D__MATCH_AVX2 -D__MATCH_CTZL +$(OBJS_NOAVX2): CFLAGS += -Ofast -funroll-loops -DMATCH_UNROLLED -D__MATCH_CTZL +$(OBJS_NOSIMD): CFLAGS += -Ofast -funroll-loops -DMATCH_UNROLLED +$(OBJS_CHECK): CFLAGS += -DVERBOSE -Ofast -funroll-loops -DMATCH_UNROLLED + +pipapo: $(OBJS) + $(CC) $(CFLAGS) $(OBJS) -o pipapo + +pipapo.debug: $(OBJS_DEBUG) + $(CC) $(CFLAGS) $(OBJS_DEBUG) -o pipapo.debug + +pipapo.show: $(OBJS_SHOW) + $(CC) $(CFLAGS) $(OBJS_SHOW) -o pipapo.show + +pipapo.mem: $(OBJS_MEM) + $(CC) $(CFLAGS) $(OBJS_MEM) -o pipapo.mem + +pipapo.noavx2: $(OBJS_NOAVX2) + $(CC) $(CFLAGS) $(OBJS_NOAVX2) -o pipapo.noavx2 + +pipapo.nosimd: $(OBJS_NOSIMD) + $(CC) $(CFLAGS) $(OBJS_NOSIMD) -o pipapo.nosimd + +pipapo.check: $(OBJS_CHECK) + $(CC) $(CFLAGS) $(OBJS_CHECK) -o pipapo.check + +%.debug.c: %.c + ln -s $< $@ + +%.show.c: %.c + ln -s $< $@ + +%.mem.c: %.c + ln -s $< $@ + +%.noavx2.c: %.c + ln -s $< $@ + +%.nosimd.c: %.c + ln -s $< $@ + +%.check.c: %.c + ln -s $< $@ + +%.o: %.c Makefile + $(CC) $(CFLAGS) -MMD -c -o $@ $< + +LINKS := $(shell find . -type l -name "*.c") + +.SECONDARY: + +.PHONY: clean tests +clean: + -${RM} pipapo pipapo.debug pipapo.show pipapo.mem pipapo.noavx2 pipapo.nosimd $(OBJS) $(OBJS_DEBUG) $(OBJS_SHOW) $(OBJS_MEM) $(OBJS_NOAVX2) $(OBJS_NOSIMD) $(OBJS_CHECK) $(DEPS) $(LINKS) + -${RM} -r tests/plots + +tests: all + cd tests; ./run.sh + display tests/plots/*.png + +-include $(DEPS) diff --git a/README b/README new file mode 100644 index 0000000..3a6a81d --- /dev/null +++ b/README @@ -0,0 +1,16 @@ +Build with: + + make + +Run tests and display performance plots with: + + make tests + +Run the 'show' target to show all the steps with an example ruleset and +packet list, e.g.: + + ./pipapo.show tests/net_port_ranged.tiny tests/net_port_ranged.tiny.packets + +Run the main target for a quick performance test against a ruleset, e.g.: + + ./pipapo tests/net_port.static tests/net_port.static.packets diff --git a/avx2.h b/avx2.h new file mode 100644 index 0000000..fca4c60 --- /dev/null +++ b/avx2.h @@ -0,0 +1,355 @@ +/* PIPAPO - PIle PAcket POlicies + * + * avx2.h - Lookup routines based on AVX2 intrinsics + * + * Author: Stefano Brivio + * License: GPLv2 + */ + +#include +#include + +#define AVX_LOAD(lt, g, v, bsize) \ + _mm256_stream_load_si256((__m256i *)(lt + (g * BUCKETS + (v)) * bsize)); + +/** + * avx2_lookup4() - AVX2-based lookup for packet fields of 4 four-bit groups + * @map: Previous matching bitmap that will be updated + * @lt: Lookup table for this field + * @pkt: Packet bytes to be matched + * @bsize: Bucket size for this lookup table, in bytes + * @first: If this is the first field in a set, start with all-ones bitmap + * @last: Last field: stop on the first match and return position + * + * Load buckets from lookup table corresponding to the values of each 4-bit + * group of packet bytes, and perform a bitwise intersection between them. If + * this is the first field in the set, simply AND the buckets together + * (equivalent to using an all-ones starting bitmap), use the provided starting + * bitmap otherwise. Then store the resulting match bitmap in @map. + * + * This implements steps 4.1 to 4.3 of the algorithm description, and is used + * for 16-bit fields (i.e. ports). + * + * Return: 32-byte rounded position of match, if last field, otherwise 0 on + * match and -1 on no match. + */ +__always_inline int avx2_lookup4(uint8_t *map, uint8_t *lt, uint8_t *pkt, + int bsize, int first, int last) +{ + __m256i r0, r1, r2, r3, r4; + int i, ret = -1; + + for (i = 0; i < bsize; i += 32) { + r0 = AVX_LOAD(lt + i, 0, pkt[0] >> 4, bsize); + r1 = AVX_LOAD(lt + i, 1, pkt[0] & 0x0f, bsize); + r2 = AVX_LOAD(lt + i, 2, pkt[1] >> 4, bsize); + r3 = AVX_LOAD(lt + i, 3, pkt[1] & 0x0f, bsize); + + if (first) { + r4 = _mm256_and_si256(r1, r0); + } else { + r4 = _mm256_stream_load_si256((__m256i *)(map + i)); + + r4 = _mm256_and_si256(r0, r4); + r4 = _mm256_and_si256(r1, r4); + } + r4 = _mm256_and_si256(r2, r4); + r4 = _mm256_and_si256(r3, r4); + + if (!_mm256_testz_si256(r4, r4)) { + if (last) { + _mm256_store_si256((__m256i *)(map + i), r4); + return i; + } + ret = 0; + } + _mm256_store_si256((__m256i *)(map + i), r4); + } + + return ret; +} + +/** + * avx2_lookup8() - AVX2-based lookup for packet fields of 8 four-bit groups + * @map: Previous matching bitmap that will be updated + * @lt: Lookup table for this field + * @pkt: Packet bytes to be matched + * @bsize: Bucket size for this lookup table, in bytes + * @first: If this is the first field in a set, start with all-ones bitmap + * @last: Last field: stop on the first match and return position + * + * Load buckets from lookup table corresponding to the values of each 4-bit + * group of packet bytes, and perform a bitwise intersection between them. If + * this is the first field in the set, simply AND the buckets together + * (equivalent to using an all-ones starting bitmap), use the provided starting + * bitmap otherwise. Then store the resulting match bitmap in @map. + * + * This implements steps 4.1 to 4.3 of the algorithm description, and is used + * for 32-bit fields (i.e. IPv4 addresses). + * + * Return: 32-byte rounded position of match, if last field, otherwise 0 on + * match and -1 on no match. + */ +__always_inline int avx2_lookup8(uint8_t *map, uint8_t *lt, uint8_t *pkt, + int bsize, int first, int last) +{ + __m256i r0, r1, r2, r3, r4, r5, r6, r7, r8; + int i, ret = -1; + + for (i = 0; i < bsize; i += 32) { + r0 = AVX_LOAD(lt + i, 0, pkt[0] >> 4, bsize); + r1 = AVX_LOAD(lt + i, 1, pkt[0] & 0x0f, bsize); + r2 = AVX_LOAD(lt + i, 2, pkt[1] >> 4, bsize); + r3 = AVX_LOAD(lt + i, 3, pkt[1] & 0x0f, bsize); + r4 = AVX_LOAD(lt + i, 4, pkt[2] >> 4, bsize); + r5 = AVX_LOAD(lt + i, 5, pkt[2] & 0x0f, bsize); + r6 = AVX_LOAD(lt + i, 6, pkt[3] >> 4, bsize); + r7 = AVX_LOAD(lt + i, 7, pkt[3] & 0x0f, bsize); + + if (first) { + r8 = _mm256_and_si256(r1, r0); + } else { + r8 = _mm256_stream_load_si256((__m256i *)(map + i)); + r8 = _mm256_and_si256(r0, r8); + r8 = _mm256_and_si256(r1, r8); + } + r8 = _mm256_and_si256(r2, r8); + r8 = _mm256_and_si256(r3, r8); + r8 = _mm256_and_si256(r4, r8); + r8 = _mm256_and_si256(r5, r8); + r8 = _mm256_and_si256(r6, r8); + r8 = _mm256_and_si256(r7, r8); + + if (!_mm256_testz_si256(r8, r8)) { + if (last) { + _mm256_store_si256((__m256i *)(map + i), r8); + return i; + } + ret = 0; + } + _mm256_store_si256((__m256i *)(map + i), r8); + } + + return ret; +} + +/** + * avx2_lookup12() - AVX2-based lookup for packet fields of 12 four-bit groups + * @map: Previous matching bitmap that will be updated + * @lt: Lookup table for this field + * @pkt: Packet bytes to be matched + * @bsize: Bucket size for this lookup table, in bytes + * @first: If this is the first field in a set, start with all-ones bitmap + * @last: Last field: stop on the first match and return position + * + * Load buckets from lookup table corresponding to the values of each 4-bit + * group of packet bytes, and perform a bitwise intersection between them. If + * this is the first field in the set, simply AND the buckets together + * (equivalent to using an all-ones starting bitmap), use the provided starting + * bitmap otherwise. Then store the resulting match bitmap in @map. + * + * This implements steps 4.1 to 4.3 of the algorithm description, and is used + * for 48-bit fields (i.e. MAC addresses). + * + * Return: 32-byte rounded position of match, if last field, otherwise 0 on + * match and -1 on no match. + */ +__always_inline int avx2_lookup12(uint8_t *map, uint8_t *lt, uint8_t *pkt, + int bsize, int first, int last) +{ + __m256i r0, r1, r2, r3, r4, r5, r6, r7, r8, r9, r10, r11, r12; + int i, ret = -1; + + for (i = 0; i < bsize; i += 32) { + r0 = AVX_LOAD(lt + i, 0, pkt[0] >> 4, bsize); + r1 = AVX_LOAD(lt + i, 1, pkt[0] & 0x0f, bsize); + r2 = AVX_LOAD(lt + i, 2, pkt[1] >> 4, bsize); + r3 = AVX_LOAD(lt + i, 3, pkt[1] & 0x0f, bsize); + r4 = AVX_LOAD(lt + i, 4, pkt[2] >> 4, bsize); + r5 = AVX_LOAD(lt + i, 5, pkt[2] & 0x0f, bsize); + r6 = AVX_LOAD(lt + i, 6, pkt[3] >> 4, bsize); + r7 = AVX_LOAD(lt + i, 7, pkt[3] & 0x0f, bsize); + r8 = AVX_LOAD(lt + i, 8, pkt[4] >> 4, bsize); + r9 = AVX_LOAD(lt + i, 9, pkt[4] & 0x0f, bsize); + r10 = AVX_LOAD(lt + i, 10, pkt[5] >> 4, bsize); + r11 = AVX_LOAD(lt + i, 11, pkt[5] & 0x0f, bsize); + + if (first) { + r12 = _mm256_and_si256(r0, r1); + } else { + r12 = _mm256_stream_load_si256((__m256i *)(map + i)); + r12 = _mm256_and_si256(r0, r12); + r12 = _mm256_and_si256(r1, r12); + } + + r12 = _mm256_and_si256(r0, r12); + r12 = _mm256_and_si256(r1, r12); + r12 = _mm256_and_si256(r2, r12); + r12 = _mm256_and_si256(r3, r12); + r12 = _mm256_and_si256(r4, r12); + r12 = _mm256_and_si256(r5, r12); + r12 = _mm256_and_si256(r6, r12); + r12 = _mm256_and_si256(r7, r12); + r12 = _mm256_and_si256(r8, r12); + r12 = _mm256_and_si256(r9, r12); + r12 = _mm256_and_si256(r10, r12); + r12 = _mm256_and_si256(r11, r12); + + if (!_mm256_testz_si256(r12, r12)) { + if (last) { + _mm256_store_si256((__m256i *)(map + i), r12); + return i; + } + ret = 0; + } + _mm256_store_si256((__m256i *)(map + i), r12); + } + + return ret; +} + +/** + * avx2_lookup32() - AVX2-based lookup for packet fields of 32 four-bit groups + * @map: Previous matching bitmap that will be updated + * @lt: Lookup table for this field + * @pkt: Packet bytes to be matched + * @bsize: Bucket size for this lookup table, in bytes + * @first: If this is the first field in a set, start with all-ones bitmap + * @last: Last field: stop on the first match and return position + * + * Load buckets from lookup table corresponding to the values of each 4-bit + * group of packet bytes, and perform a bitwise intersection between them. If + * this is the first field in the set, simply AND the buckets together + * (equivalent to using an all-ones starting bitmap), use the provided starting + * bitmap otherwise. Then store the resulting match bitmap in @map. + * + * This implements steps 4.1 to 4.3 of the algorithm description, and is used + * for 128-bit fields (i.e. IPv6 addresses). + * + * Return: 32-byte rounded position of match, if last field, otherwise 0 on + * match and -1 on no match. + */ +__always_inline int avx2_lookup32(uint8_t *map, uint8_t *lt, uint8_t *pkt, + int bsize, int first, int last) +{ + __m256i r0, r1, r2, r3, r4, r5, r6, r7, r8, r9, r10, r11, r12, r13, r15; + int i, ret = -1; + + for (i = 0; i < bsize; i += 32) { + r0 = AVX_LOAD(lt + i, 0, pkt[0] >> 4, bsize); + r1 = AVX_LOAD(lt + i, 1, pkt[0] & 0x0f, bsize); + r2 = AVX_LOAD(lt + i, 2, pkt[1] >> 4, bsize); + r3 = AVX_LOAD(lt + i, 3, pkt[1] & 0x0f, bsize); + r4 = AVX_LOAD(lt + i, 4, pkt[2] >> 4, bsize); + r5 = AVX_LOAD(lt + i, 5, pkt[2] & 0x0f, bsize); + r6 = AVX_LOAD(lt + i, 6, pkt[3] >> 4, bsize); + r7 = AVX_LOAD(lt + i, 7, pkt[3] & 0x0f, bsize); + r8 = AVX_LOAD(lt + i, 8, pkt[4] >> 4, bsize); + r9 = AVX_LOAD(lt + i, 9, pkt[4] & 0x0f, bsize); + r10 = AVX_LOAD(lt + i, 10, pkt[5] >> 4, bsize); + r11 = AVX_LOAD(lt + i, 11, pkt[5] & 0x0f, bsize); + r12 = AVX_LOAD(lt + i, 12, pkt[6] >> 4, bsize); + r13 = AVX_LOAD(lt + i, 13, pkt[6] & 0x0f, bsize); + + if (first) { + r15 = _mm256_and_si256(r0, r1); + } else { + r15 = _mm256_stream_load_si256((__m256i *)(map + i)); + r15 = _mm256_and_si256(r0, r15); + r15 = _mm256_and_si256(r1, r15); + } + + r15 = _mm256_and_si256(r2, r15); + r15 = _mm256_and_si256(r3, r15); + r15 = _mm256_and_si256(r4, r15); + r15 = _mm256_and_si256(r5, r15); + r15 = _mm256_and_si256(r6, r15); + r15 = _mm256_and_si256(r7, r15); + r15 = _mm256_and_si256(r8, r15); + r15 = _mm256_and_si256(r9, r15); + r15 = _mm256_and_si256(r10, r15); + r15 = _mm256_and_si256(r11, r15); + r15 = _mm256_and_si256(r12, r15); + r15 = _mm256_and_si256(r13, r15); + + r0 = AVX_LOAD(lt + i, 14, pkt[7] >> 4, bsize); + r1 = AVX_LOAD(lt + i, 15, pkt[7] & 0x0f, bsize); + r2 = AVX_LOAD(lt + i, 16, pkt[8] >> 4, bsize); + r3 = AVX_LOAD(lt + i, 17, pkt[8] & 0x0f, bsize); + r4 = AVX_LOAD(lt + i, 18, pkt[9] >> 4, bsize); + r5 = AVX_LOAD(lt + i, 19, pkt[9] & 0x0f, bsize); + r6 = AVX_LOAD(lt + i, 20, pkt[10] >> 4, bsize); + r7 = AVX_LOAD(lt + i, 21, pkt[10] & 0x0f, bsize); + r8 = AVX_LOAD(lt + i, 22, pkt[11] >> 4, bsize); + r9 = AVX_LOAD(lt + i, 23, pkt[11] & 0x0f, bsize); + r10 = AVX_LOAD(lt + i, 24, pkt[12] >> 4, bsize); + r11 = AVX_LOAD(lt + i, 25, pkt[12] & 0x0f, bsize); + r12 = AVX_LOAD(lt + i, 26, pkt[13] >> 4, bsize); + r13 = AVX_LOAD(lt + i, 27, pkt[13] & 0x0f, bsize); + + r15 = _mm256_and_si256(r0, r15); + r15 = _mm256_and_si256(r1, r15); + r15 = _mm256_and_si256(r2, r15); + r15 = _mm256_and_si256(r3, r15); + r15 = _mm256_and_si256(r4, r15); + r15 = _mm256_and_si256(r5, r15); + r15 = _mm256_and_si256(r6, r15); + r15 = _mm256_and_si256(r7, r15); + r15 = _mm256_and_si256(r8, r15); + r15 = _mm256_and_si256(r9, r15); + r15 = _mm256_and_si256(r10, r15); + r15 = _mm256_and_si256(r11, r15); + r15 = _mm256_and_si256(r12, r15); + r15 = _mm256_and_si256(r13, r15); + + r0 = AVX_LOAD(lt + i, 28, pkt[14] >> 4, bsize); + r1 = AVX_LOAD(lt + i, 29, pkt[14] & 0x0f, bsize); + r2 = AVX_LOAD(lt + i, 30, pkt[15] >> 4, bsize); + r3 = AVX_LOAD(lt + i, 31, pkt[15] & 0x0f, bsize); + + r15 = _mm256_and_si256(r0, r15); + r15 = _mm256_and_si256(r1, r15); + r15 = _mm256_and_si256(r2, r15); + r15 = _mm256_and_si256(r3, r15); + + if (!_mm256_testz_si256(r15, r15)) { + if (last) { + _mm256_store_si256((__m256i *)(map + i), r15); + return i; + } + ret = 0; + } + _mm256_store_si256((__m256i *)(map + i), r15); + } + + return ret; +} + +/** + * avx2_lookup() - AVX2-based lookup for packet fields + * @map: Previous matching bitmap that will be updated + * @lt: Lookup table for this field + * @pkt: Packet bytes to be matched + * @bsize: Bucket size for this lookup table, in bytes + * @first: If this is the first field in a set, start with all-ones bitmap + * @last: If this is the last field in a set, stop on the first match + * + * This implements steps 4.1 to 4.3 of the algorithm description. + * + * Return: 32-byte rounded position of match, if last field, otherwise 0 on + * match and -1 on no match. + */ +__always_inline int avx2_lookup(uint8_t *map, uint8_t *lt, uint8_t *pkt, + int groups, int bsize, int first, int last) +{ + if (groups == 4) + return avx2_lookup4(map, lt, pkt, bsize, first, last); + if (groups == 8) + return avx2_lookup8(map, lt, pkt, bsize, first, last); + if (groups == 12) + return avx2_lookup12(map, lt, pkt, bsize, first, last); + if (groups == 32) + return avx2_lookup32(map, lt, pkt, bsize, first, last); + + return 0; +} diff --git a/match.c b/match.c new file mode 100644 index 0000000..31bdb5f --- /dev/null +++ b/match.c @@ -0,0 +1,284 @@ +/* PIPAPO - PIle PAcket POlicies + * + * match.c - Equivalent match implementation for kernel + * + * Author: Stefano Brivio + * License: GPLv2 + */ + +#include +#include +#include +#include + +#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; +} diff --git a/match.h b/match.h new file mode 100644 index 0000000..c3821a7 --- /dev/null +++ b/match.h @@ -0,0 +1,24 @@ +/** + * struct kernel_set - Representation of in-kernel set data + * @groups: Number of 4-bit groups for each field (algorithm step 3.1) + * @offset: Offset of field within packet data, in bytes + * @bsize: Lookup table bucket size for field, in bytes + * @lt: Lookup table for field (algorithm steps 3.2 - 3.4) + * @mt: Mapping table for field (algorithm steps 3.5 - 3.6) + * @map: Result bitmap, two copies: swap indices instead of copying + * @map_idx: Index of current matching bitmap + * @max_bsize: Maximum lookup table bucket size for all fields in the set + */ +struct kernel_set { + int groups[MAX_FIELDS]; + int offset[MAX_FIELDS]; + int bsize[MAX_FIELDS]; + uint8_t *lt[MAX_FIELDS]; + union map_bucket *mt[MAX_FIELDS]; + uint8_t *map[2]; + int map_idx; + int max_bsize; +}; + +struct kernel_set *kernel_init(struct set *s, struct desc_spec **layout); +uint32_t match(struct kernel_set *ks, uint8_t *packet); diff --git a/pipapo.c b/pipapo.c new file mode 100644 index 0000000..d44cb72 --- /dev/null +++ b/pipapo.c @@ -0,0 +1,1093 @@ +/* PIPAPO - PIle PAcket POlicies + * + * pipapo.c - Stand-alone algorithm implementation + * + * Author: Stefano Brivio + * License: GPLv2 + * + * + * == 1. Problem + * + * Match packets against n generic entries with m (ipset-like) fields in a set, + * mapping them to n keys, for example: + * + * --- fields ---> + * | [net],[port],[net]... => [key] + * entries [net],[port],[net]... => [key] + * | [net],[port],[net]... => [key] + * V ... + * + * where [net] fields can be IP ranges or netmasks, and [port] fields are port + * ranges. Arbitrary packet fields (source and destination IPv4, IPv6, MAC + * addresses and ports) can be matched. + * + * + * == 2. Introduction + * + * This algorithm is loosely inspired by [Ligatti 2010], and fundamentally + * relies on the consideration that every contiguous range in a space of b bits + * can be converted into b netmasks, from Theorem 3 in [Rottenstreich 2010]. + * Despite the fact that we don't implement a boolean classifier here, some + * relevant optimisation ideas were inspired by [Kogan 2014], especially related + * to the notion of order-independent regions of a classifier. + * + * Classification against a number of entries, that require matching given bits + * of a packet field, is performed by grouping those bits in sets of arbitrary + * size, and classifying packet bits one group at a time. + * + * Example: to match the source port (16 bits) of a packet, we can divide + * those 16 bits in 4 groups of 4 bits each. Given the entry: + * 0000 0001 0101 1001 + * and a packet with source port: + * 0000 0001 1010 1001 + * first and second groups match, but the third doesn't. We conclude that the + * packet doesn't match the given entry. + * + * Translate the set to a sequence of lookup tables, one per field. Each table + * has two dimensions: bit groups to be matched for a single packet field, and + * all the possible values of said groups. Each group in the table maps to the + * next group through a set of rules, which are generated from entries during + * the pre-computation phase. The last group in a table maps to the next table, + * and the set of matched rules after the last table in the set is mapped to a + * single verdict key. + * + * To match, we perform table lookups using the values of relevant packet bits, + * divided according to the groups, and use a sequence of bitwise operations to + * progressively evaluate rule matching. + * + * In the description below, the basic idea is described first, and + * optimisations are illustrated later. Steps with O(n) computational complexity + * are then all reduced to O(log(n)) problems. + * + * + * == 3. Precomputation + * + * - For each packet field: + * + * (3.1) divide the b packet bits we want to classify into groups of size t, + * obtaining ceil(b / t) groups + * + * Example: match on destination IP address, with t = 4: 32 bits, 8 groups + * of 4 bits each + * + * (3.2) allocate a lookup table with one column ("bucket") for each possible + * value of a group, and with one row for each group + * + * Example: 8 groups, 2^4 buckets: + * + * bucket + * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 + * 0 + * 1 + * 2 + * 3 + * 4 + * 5 + * 6 + * 7 + * + * (3.3) map the bits we want to classify for the current field, for a given + * entry, to a single rule for non-ranged and netmask set items, and to one or + * multiple rules for ranges. Ranges are expanded to composing netmasks: + * + * Example: 2 entries, 10.0.0.5:1024 and 192.168.1.0-192.168.2.1:2048 + * - rule #0: 10.0.0.5 + * - rule #1: 192.168.1.0/24 + * - rule #2: 192.168.2.0/31 + * + * (3.4) insert references to the rules in the lookup table, selecting buckets + * according to bit values of a rule in the given group + * + * Example: given: + * - rule #0: 10.0.0.5 mapping to buckets + * < 0 10 0 0 0 0 0 5 > + * - rule #1: 192.168.1.0/24 mapping to buckets + * < 12 0 10 8 0 1 < 0..15 > < 0..15 > > + * - rule #2: 192.168.2.0/31 mapping to buckets + * < 12 0 10 8 0 2 0 < 0..1 > > + * + * these bits are set in the lookup table: + * + * bucket + * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 + * 0 0 1,2 + * 1 1,2 0 + * 2 0 1,2 + * 3 0 1,2 + * 4 0,1,2 + * 5 0 1 2 + * 6 0,1,2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 + * 7 1,2 1,2 1 1 1 0,1 1 1 1 1 1 1 1 1 1 1 + * + * (3.5) if this is not the last field in the set, build a mapping table that + * maps rules from the lookup table to rules belonging to the same entry in + * the next lookup table + * + * Example: 2 entries, 10.0.0.5:1024 and 192.168.1.0-192.168.2.1:2048 + * + * given lookup table #0 (see example above): + * + * bucket + * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 + * 0 0 1,2 + * 1 1,2 0 + * 2 0 1,2 + * 3 0 1,2 + * 4 0,1,2 + * 5 0 1 2 + * 6 0,1,2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 + * 7 1,2 1,2 1 1 1 0,1 1 1 1 1 1 1 1 1 1 1 + * + * and lookup table #1 with: + * - rule #0: 1024 mapping to buckets + * < 0 0 4 0 > + * - rule #1: 2048 mapping to buckets + * < 0 0 5 0 > + * + * bucket + * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 + * 0 0,1 + * 1 0,1 + * 2 0 1 + * 3 0,1 + * + * we need to map rules for 10.0.0.5 in lookup table #0 (rule #0) to 1024 + * in lookup table #1 (rule #0) and rules for 192.168.1.0-192.168.2.1 + * (rules #1, #2) to 2048 in lookup table #2 (rule #1): + * + * rules + * 0 1 2 + * map to: 0 1 1 + * + * (3.6) if this is the last field in the set, build a mapping table that maps + * rules from the last lookup table to verdict keys + * + * Example: 10.0.0.5:1024 gives 66 as verdict and + * 192.168.1.0-192.168.2.1:2048 gives 42. From the rules of lookup table #2 + * as mapped above: + * + * rules + * 0 1 + * map to: 66 42 + * + * + * == 4. Matching + * + * (4.1) We use a result bitmap, with the size of a single lookup table bucket, + * to represent the matching state that applies at every algorithm step. + * + * - For each packet field: + * + * (4.2) start with an all-ones result bitmap + * + * (4.3) perform a lookup into the table corresponding to the current field, + * for each group, and at every group, AND the current result bitmap with the + * value from the lookup table bucket + * + * Example: 192.168.1.5 < 12 0 10 8 0 1 0 5 >, with lookup table from + * pre-computation example. + * Lookup table buckets are at least 3 bits wide, we'll arbitrarily assume + * they are 8 bits for convenience. Initial result bitmap is 0xff, the + * steps below show the value of the result bitmap after each group is + * processed: + * + * bucket + * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 + * 0 0 1,2 + * + * result bitmap is now: 0xff & 0x6 [bucket 12] = 0x6 + * + * 1 1,2 0 + * + * result bitmap is now: 0x6 & 0x6 [bucket 0] = 0x6 + * + * 2 0 1,2 + * + * result bitmap is now: 0x6 & 0x6 [bucket 10] = 0x6 + * + * 3 0 1,2 + * + * result bitmap is now: 0x6 & 0x6 [bucket 8] = 0x6 + * + * 4 0,1,2 + * + * result bitmap is now: 0x6 & 0x7 [bucket 0] = 0x6 + * + * 5 0 1 2 + * + * result bitmap is now: 0x6 & 0x2 [bucket 1] = 0x2 + * + * 6 0,1,2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 + * + * result bitmap is now: 0x2 & 0x7 [bucket 0] = 0x2 + * + * 7 1,2 1,2 1 1 1 0,1 1 1 1 1 1 1 1 1 1 1 + * + * final result bitmap for this field is: 0x2 & 0x3 [bucket 5] = 0x2 + * + * (4.4) at the next field, start with a new, all-zeroes result bitmap. For + * each bit set in the previous result bitmap, OR the new result bitmap with + * the corresponding value from the mapping table for this field + * + * Example: with mapping table from pre-computation example, current result + * bitmap 0x02: + * + * rules + * 0 1 2 + * map to: 0 1 1 + * + * new result bitmap is 0x00 | 0x02 [bit/rule 1 was set] = 0x02 + * + * we can now extend this example to cover the second iteration of the step + * above (lookup and AND bitmap): assuming the port field is + * 2048 < 0 0 5 0 >, with starting result bitmap 0x2, and lookup table + * for "port" field from pre-computation example: + * + * bucket + * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 + * 0 0,1 + * 1 0,1 + * 2 0 1 + * 3 0,1 + * + * operations are: 0x2 & 0x3 [bucket 0] & 0x3 [bucket 0] & 0x2 [bucket 5] + * & 0x3 [bucket 0], resulting bitmap is 0x2. + * + * (4.5) if this is the last field in the set, look up the value from the + * verdict table corresponding to the final result bitmap + * + * Example: 0x2 resulting bitmap from 192.168.1.5:2048, verdict table from + * pre-computation example: + * + * rules + * 0 1 + * map to: 66 42 + * + * the verdict is 42. + * + * + * == 5. Ideas for Future Optimisations + * + * (5.1) Reduction of number of rules by allowing inverted netmasks + * + * CAVEAT: This needs some complicated tracking for inverted entries, which + * aren't implemented here at all. In order to further halve the number of + * rules as described below, we also need to use sets of netmasks, instead of a + * single netmask for each entry, and intersect between them and their + * inversions. This also introduces further complexity. + * + * Theorem 3 in [Rottenstreich 2010] shows that every range of b bits can be + * converted into b bitmaps, with inversions, as also illustrated by section 9 + * in [Kogan 2014]. + * + * Further, if we allow partial subtractions between netmasks, for each range R + * of b bits, that can be converted into a b0 number of bitmaps, there exists a + * complementary range, R1, that can be converted into a b1 number of bitmaps, + * such that b1 + b0 = b. + * + * [TODO: Formal proof. This consideration is intuitively true and was validated + * by bruteforcing over the IPv4 address space, so we can safely use it in the + * implementation for the moment.] + * + * By construction, this allows us to express any range of b bits as ceil(b / 2) + * entries, either as reversed or direct entries. By allowing reversed entries, + * we need to also provide a reverse mapping possibility, which is achieved by + * modifying the mapping table from pre-computation step 4.5, and the step + * itself, as follows: + * - every bit corresponding to a reverse rule is set in the initial result + * bitmap, which is not necessarily an all-zeroes bitmap anymore + * - the transformation step becomes a XOR operation: the XOR step with the + * modified initial bitmap reverses the result, if we guarantee that one + * single XOR step is performed. This comes, in turn, from optimisation 5.2 + * + * Example: match on 0.0.0.1-127.255.255.255:1024 and on 192.168.1.1:1024. + * A direct mapping means we need 31 rules for the first address range, using + * reversed rules we only need 2 rules instead (rule #0: 0.0.0.0/32, + * rule #1: 128.0.0.0/1). Rule #2: 192.168.1.1/32. + * First lookup table: + * bucket + * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 + * 0 0 1 1 1 1 1,2 1 1 1 + * 1 0,1,2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 + * 2 0,1 1 1 1 1 1 1 1 1 1 1,2 1 1 1 1 1 + * 3 0,1 1 1 1 1 1 1 1 1,2 1 1 1 1 1 1 1 + * 4 0,1,2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 + * 5 0,1 1,2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 + * 6 0,1,2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 + * 7 0,1 1,2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 + * + * Second lookup table: rule #0: 1024 for first entry, rule #1: 1024 for + * second entry + * bucket + * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 + * 0 0,1 + * 1 0,1 + * 2 0,1 + * 3 0,1 + * + * mapping table: initial bitmap is 0x1 (entry with rule #0 in second table + * is reversed in first table: set bit #0) + * rules + * 0 1 2 + * XOR with: 0x1 0x1 0x2 + * + * - expansion to reverse rules is selected if the number of reversed rules is + * strictly less than the number of needed direct rules. + * + * (5.2) Single step for match and fill from result bitmap + * + * CAVEAT: This significantly affects complexity of listing and deletion, + * because once rules are replaced, further steps are needed to rebuild the + * originating entries. + * + * Step 4.4 loops over all bits set in the current result bitmap: this is + * needed as set entries might overlap, for one or more fields. The + * computational complexity of mapping steps is O(m * log(n)), with m > 1 + * overlapping factor, because we have no tight bounds on the number of + * overlapping entries. However, we can apply a reduction step on lookup tables, + * and ensure a single bit is set in the result bitmap after each lookup table + * is considered, with three observations: + * + * (5.2.1) In case two entries overlap entirely in a given lookup table, and + * their rules are present in the previous mapping table (or if it's the first + * lookup table), the entries can map to the same set of rules without loss of + * generality. + * + * Example: given entries 192.168.1.0/24:1024 and 192.168.1.0/24:2048, first + * lookup table initially has rules: + * #0: 192.168.1.0/24 + * #1: 192.168.1.0/24 + * and second lookup table has rules: + * #0: 1024 + * #1: 2048 + * with mapping table #0 -> #0 | #1 -> #1. + * After this reduction step, the first lookup table has a single + * rule (#0: 192.168.1.0/24), mapping to both rule #0 and #1. + * + * Example: given entries 192.168.1.0/24:1024:10.0.0.1 and + * 192.168.2.0/24:1024:10.0.0.1, we don't apply any reduction step. + * First lookup table has rules: + * #0: 192.168.1.0/24 + * #1: 192.168.2.0/24 + * and second lookup table has rules: + * #0: 1024 + * #1: 1024 + * with first mapping table #0 -> #0 | #1 -> #1. As there are no + * images in the first lookup table with both rules #0 and #1 set, + * these two rules will be preserved. Third lookup table has two + * rules: + * #0: 10.0.0.1/32 + * #1: 10.0.0.1/32 + * and second mapping table is: #0 -> #0 | #1 -> #1. + * + * (5.2.2) In case two entries overlap partially in a given lookup table, due to + * the way we expand ranges to netmasks, one set of rules is always a proper + * subset of the other overlapping one. That is, we can hit this situation: + * + * bucket + * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 + * 0 x,y + * 1 x,y x,y y y + * + * but not: + * + * bucket + * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 + * 0 x,y + * 1 x x,y y y + * + * so in case entries corresponding to x map to a proper subset of the y rules, + * x rules never occur without y rules. We can then replace the x,y pairs by + * x, and merge their mapping tables. + * + * Example: entries: 192.168.1.1-192.168.1.2:1 + * expands to: 192.168.1.1/32:1 (#0:#0), 192.168.1.2/32:1 (#1:#0) + * 192.168.1.0-192.168.1.1:2 + * expands to: 192.168.1.0/31:2 (#2:#1) + * 192.168.1.0-192.168.1.2:3 + * expands to: 192.168.1.0/31:3 (#3:#2), 192.168.1.2/32:3 (#4:#2) + * + * First lookup table (only last group shown): + * bucket + * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 + * ... + * 7 2,3 0,2,3 1,4 + * + * Second lookup table (only last group shown): + * bucket + * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 + * ... + * 3 0 1 2 + * + * Initial mapping table: #0 -> #0 | #1 -> #0 | #2 -> #1 | #3 -> #2 | #4 -> #2 + * + * Apply reduction step from 5.2.1 twice to first lookup table: rule #1 + * entirely overlaps with #4, #2 entirely overlaps with #3. New lookup table: + * + * bucket + * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 + * ... + * 7 2 0,2 1 + * + * New mapping table: #0 -> #0 | #1 -> #0, #2 | #2 -> #1, #2 + * + * Apply reduction step from 5.2.2: 0 never occurs without 2: + * + * bucket + * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 + * ... + * 7 2 0 1 + * + * New mapping table: #0 -> #0, #1, #2 | #1 -> #0, #2 | #2 -> #1, #2 + * + * (5.2.3) There are no other ways entries can overlap (directly from set + * theory) + * [TODO: Formal proof or reference.] + * + * (5.3) Single step for invert, match and bitmap fill operations (comes almost + * for free with 5.2 and 5.1). + * + * We can now replace the loop from 4.4 with a single XOR operation + * depending on the single bit set in the result bitmask after a lookup table is + * evaluated. Computational complexity of that step becomes, in theory, O(1): + * a single bit is set, hence lookup of the corresponding bitmap can be done in + * constant time. For all practical implementations, this is O(log(n)): the + * number of words in the mapping table grows linearly with the number of + * entries, but number of rules grows sublinearly and we can find the set bit + * with very efficient operations, too (e.g. x86's TZCNT, AVX-512 VPLZCNTQ, + * PPC's CNTLZ, etc.)] + * + * (5.4) [TODO: Evaluate if this provides an actual advantage even with an + * implementation of step 4.3 optionally based on AVX2 VPAND instrinsics.] + * As an alternative to finding the first bit set in the result bitmap for the + * mapping table lookup, we can terminate step 4.3 early, once we reach the last + * group of a table and a set bit is found in the result, and use the position + * of this bit directly for the mapping table lookup. + * + * (5.5) [TODO: Evaluate how bad this is on architectures where branching is + * expensive, e.g. PPC, find out if it makes sense to implement this optionally + * depending on architecture.] + * - We can terminate the algorithm early if the initial result bitmap, as we + * start processing the next lookup table, is empty: that means that the + * packet won't match any entry + * - We can terminate step 4.3 early if the result bitmap happens to be empty + * after a group is entirely evaluated: this means the result bitmap will be + * also empty at the beginning of step 4.4. We can't terminate the whole + * algorithm in this case, though, as entries might be represented with an + * inverted set of rules. + * + * (5.6) The mapping table described in step (3.5) grows in size linearly with + * the product of rules for the current field and rules for the next field. For + * entries with non-overlapping rules in a given field, this size would grow + * with the number of rules for this field, independently of the fact that these + * rules might map to the same set of rules in the next field. + * + * Example: one entry, 192.168.1.0-192.168.2.1:2048 + * + * given lookup table #0 (see example above): + * + * bucket + * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 + * 0 0 1,2 + * 1 1,2 0 + * 2 0 1,2 + * 3 0 1,2 + * 4 0,1,2 + * 5 0 1 2 + * 6 0,1,2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 + * 7 1,2 1,2 1 1 1 0,1 1 1 1 1 1 1 1 1 1 1 + * + * and lookup table #1 with: + * - rule #0: 1024 mapping to buckets + * < 0 0 4 0 > + * - rule #1: 2048 mapping to buckets + * < 0 0 5 0 > + * + * bucket + * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 + * 0 0,1 + * 1 0,1 + * 2 0 1 + * 3 0,1 + * + * we need to map rules for 10.0.0.5 in lookup table #0 (rule #0) to 1024 + * in lookup table #1 (rule #0) and rules for 192.168.1.0-192.168.2.1 + * (rules #1, #2) to 2048 in lookup table #2 (rule #1): + * + * rules + * 0 1 2 + * map to: 0 1 1 + * + * + * == 6. References + * + * [Ligatti 2010] + * A Packet-classification Algorithm for Arbitrary Bitmask Rules, with + * Automatic Time-space Tradeoffs + * Jay Ligatti, Josh Kuhn, and Chris Gage. + * Proceedings of the IEEE International Conference on Computer + * Communication Networks (ICCCN), August 2010. + * http://www.cse.usf.edu/~ligatti/papers/grouper-conf.pdf + * + * [Rottenstreich 2010] + * Worst-Case TCAM Rule Expansion + * Ori Rottenstreich and Isaac Keslassy. + * 2010 Proceedings IEEE INFOCOM, San Diego, CA, 2010. + * http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.212.4592&rep=rep1&type=pdf + * + * [Kogan 2014] + * SAX-PAC (Scalable And eXpressive PAcket Classification) + * Kirill Kogan, Sergey Nikolenko, Ori Rottenstreich, William Culhane, + * and Patrick Eugster. + * Proceedings of the 2014 ACM conference on SIGCOMM, August 2014. + * http://www.sigcomm.org/sites/default/files/ccr/papers/2014/August/2619239-2626294.pdf + */ + +#ifndef VERBOSE +#define PERF_TEST_BLOCK 100 +#endif + +#include +#include +#include +#include +#include +#include +#include + +#include "pipapo.h" +#include "set.h" +#include "match.h" +#include "util.h" + +/* Specifiers for set description: label, type, length, and offset in packet */ +struct desc_spec desc_specs[] = { + { "key", KEY, 0, 0 }, + { "dmac", MAC, MAC_LEN, 0 }, + { "smac", MAC, MAC_LEN, 6 }, + { "saddr", ADDR, ADDR_LEN, 26 }, + { "daddr", ADDR, ADDR_LEN, 30 }, + { "sport", PORT, PORT_LEN, 34 }, + { "dport", PORT, PORT_LEN, 36 }, + { "saddr6", ADDR6, ADDR6_LEN, 22 }, + { "daddr6", ADDR6, ADDR6_LEN, 38 }, + { "sport6", PORT, PORT_LEN, 54 }, + { "dport6", PORT, PORT_LEN, 56 }, + { NULL, 0, 0, 0 }, +}; + +/** + * desc_parse_spec() - Parse set layout from tokens on first line of set file + * @d: Pre-allocated set description to fill in + * @n: Number of field tokens + * @tokens: Labels of fields in desired set layout + * + * Return: 0 on success, negative error code on failure + */ +int desc_parse_spec(struct desc *d, int n, char (*tokens)[BUFSIZ]) +{ + struct desc_spec *spec; + int i; + + d->row_size = sizeof(enum set_ops); + + for (i = 0; i < n; i++) { + for (spec = desc_specs; spec->label; spec++) { + if (!strncmp(tokens[i], spec->label, BUFSIZ)) + break; + } + + if (!spec->label) { + fprintf(stderr, "Invalid set specifier token %s\n", + tokens[i]); + return -EINVAL; + } + + d->layout[i] = spec; + + if (spec->type == KEY) { + d->row_size += sizeof(uint32_t); + continue; + } + + d->fields++; + if (spec->type == ADDR) + d->row_size += sizeof(struct addr); + else if (spec->type == ADDR6) + d->row_size += sizeof(struct addr6); + else if (spec->type == PORT) + d->row_size += sizeof(struct port); + else if (spec->type == MAC) + d->row_size += sizeof(struct mac); + } + + return 0; +} + +/** + * desc_parse_entry() - Parse set entries from set file + * @d: Pre-allocated set description, d->data to be filled + * @at: Starting position in d->data to be filled with next set entry + * @n: Number of fields + * @tokens: Set items: addresses, ports, ranges thereof + * + * Return: 0 on success, negative error code on failure + */ +int desc_parse_entry(struct desc *d, int at, int n, char (*tokens)[BUFSIZ]) +{ + int i, base = at * d->row_size, offset, b; + struct addr6 a6; + struct addr a; + struct port p; + char *c, *end; + struct mac m; + uint32_t key; + uint8_t v[6]; + + if (!strncmp(tokens[0], "list", strlen(tokens[0]))) { + *(enum set_ops *)(d->data + base) = LIST; + return 0; + } + + if (!strncmp(tokens[0], "add", strlen(tokens[0]))) + *(enum set_ops *)(d->data + base) = ADD; + else if (!strncmp(tokens[0], "delete", strlen(tokens[0]))) + *(enum set_ops *)(d->data + base) = DEL; + else + return -EINVAL; + offset = sizeof(enum set_ops); + tokens++; + n--; + + for (i = 0; i < n; i++) { + switch (d->layout[i]->type) { + case KEY: + key = strtoul(tokens[i], &end, 10); + if (*end) + return -EINVAL; + + memcpy(d->data + base + offset, &key, sizeof(key)); + offset += sizeof(key); + break; + case ADDR: + /* IPv4... */ + if ((c = strchr(tokens[i], '-'))) { + /* range */ + if (!inet_aton(c + 1, (struct in_addr *)&a.end)) + return -EINVAL; + a.cidr = 0; + *c = 0; + } else if ((c = strchr(tokens[i], '/'))) { + /* netmask */ + *c = 0; + a.cidr = strtoul(c + 1, &end, 10); + if (*end) + return -EINVAL; + } else { + /* address */ + a.cidr = 32; + } + + if (!inet_aton(tokens[i], (struct in_addr *)&a.start)) + return -EINVAL; + + memcpy(d->data + base + offset, &a, sizeof(a)); + offset += sizeof(a); + break; + case ADDR6: + /* IPv6... */ + if ((c = strchr(tokens[i], '-'))) { + /* range */ + if (!inet_pton(AF_INET6, c + 1, &a6.end)) + return -EINVAL; + a6.cidr = 0; + *c = 0; + } else if ((c = strchr(tokens[i], '/'))) { + /* netmask */ + *c = 0; + a6.cidr = strtoul(c + 1, &end, 10); + if (*end) + return -EINVAL; + } else { + /* address */ + a6.cidr = 128; + } + + if (!inet_pton(AF_INET6, tokens[i], &a6.start)) + return -EINVAL; + + memcpy(d->data + base + offset, &a6, sizeof(a6)); + offset += sizeof(a6); + break; + case PORT: + if ((c = strchr(tokens[i], '-'))) { + *c = 0; + p.end = htons(strtoul(c + 1, &end, 10)); + if (*end) + return -EINVAL; + } else { + p.end = 0; + } + + p.start = htons(strtoul(tokens[i], &end, 10)); + if (*end) + return -EINVAL; + + memcpy(d->data + base + offset, &p, sizeof(p)); + offset += sizeof(p); + break; + case MAC: + if ((c = strchr(tokens[i], '-'))) + *c = 0; + + b = sscanf(tokens[i], + "%hhx:%hhx:%hhx:%hhx:%hhx:%hhx%*c", + v + 0, v + 1, v + 2, v + 3, v + 4, v + 5); + if (b != 6) + return -EINVAL; + memcpy(&m.start, v, 6); + + if (c) { + b = sscanf(c + 1, + "%hhx:%hhx:%hhx:%hhx:%hhx:%hhx%*c", + v + 0, v + 1, v + 2, + v + 3, v + 4, v + 5); + if (b != 6) + return -EINVAL; + memcpy(&m.end, v, 6); + } else { + memset(&m.end, 0, 6); + } + + memcpy(d->data + base + offset, &m, sizeof(m)); + offset += sizeof(m); + break; + } + } + + return 0; +} + +/** + * usage() - Display usage and exit + * @argv0: Executable name + */ +void usage(const char *argv0) +{ + fprintf(stderr, "%s \n", argv0); + exit(1); +} + +/** + * packet_parse() - Parse packets and expected key from path into binary format + * @path: Path to packet file + * @ret: Pointer to packet buffer, incremented by this function + * + * Return: 0 on success, negative error code on failure + */ +static int packet_parse(const char *path, uint8_t **ret) +{ + int alloc, n, byte_count, packet_count = 0, err; + uint8_t *packets, *pos, *tmp; + char buf[BUFSIZ], *end; + char *p; + FILE *f; + + alloc = BUFSIZ; + pos = packets = malloc(alloc * (sizeof(uint32_t) + PACKET_SIZE)); + if (!packets) + return -ENOMEM; + + f = fopen(path, "r"); + if (!f) { + err = -errno; + goto fail; + } + + while (fgets(buf, BUFSIZ, f)) { + if (!*buf || *buf == '#' || *buf == ' ' || *buf == '\n') + continue; + + if (++packet_count > alloc) { + alloc += BUFSIZ; + tmp = realloc(packets, + alloc * (sizeof(uint32_t) + PACKET_SIZE)); + if (!tmp) { + err = -ENOMEM; + goto fail_close; + } + packets = tmp; + pos = packets; + pos += (packet_count - 1) * + (sizeof(uint32_t) + PACKET_SIZE); + } + + /* Key */ + p = strtok(buf, " \t"); + n = strtoul(p, &end, 0); + if (*end) { + err = -EINVAL; + goto fail_close; + } + *(uint32_t *)pos = n; + pos += sizeof(uint32_t); + + /* Packet bytes */ + byte_count = 0; + while ((p = strtok(NULL, " \t\n"))) { + n = strtoul(p, &end, 0); + if (*end) { + err = -EINVAL; + goto fail_close; + } + *pos = n; + pos++; + if (++byte_count >= PACKET_SIZE) + break; + } + if (byte_count < PACKET_SIZE) { + memset(pos, 0, PACKET_SIZE - byte_count); + pos += PACKET_SIZE - byte_count; + } + } + fclose(f); + + *ret = packets; + verbose("Read %i packets from %s\n", packet_count, path); + + return packet_count; + +fail_close: + fclose(f); +fail: + free(packets); + return err; +} + +/** + * desc_parse() - Parse set file from path + * @path: Path to set file + * @d: Pre-allocated set, with description and data parts + * + * Return: 0 on success, negative error code on failure + */ +int desc_parse(const char *path, struct desc *d) +{ + int first = 1, err = 0, alloc = 0, n; + char t[9][BUFSIZ]; + char buf[BUFSIZ]; + uint8_t *tmp; + FILE *f; + + f = fopen(path, "r"); + if (!f) + return -errno; + + while (fgets(buf, BUFSIZ, f)) { + n = sscanf(buf, "%s %s %s %s %s %s %s %s %s", t[0], + t[1], t[2], t[3], t[4], t[5], t[6], t[7], t[8]); + if (!n || *t[0] == '#') + continue; + + if (first) { + /* First line is the set type specifier */ + err = desc_parse_spec(d, n, t); + if (err) + goto out; + + first = 0; + continue; + } + + if (d->entries == alloc) { + alloc += BUFSIZ; + tmp = realloc(d->data, alloc * d->row_size); + if (!tmp) { + err = -ENOMEM; + goto out; + } + d->data = tmp; + } + + err = desc_parse_entry(d, d->entries++, n, t); + } + +out: + fclose(f); + return err; +} + +/** + * main() - Entry point: parse set and packets, pre-compute, match + * @argc: Argument count + * @argv: Path to set description and packet files + * + * Return: 0 on success, 1 on matching failure, negative error code otherwise + */ +int main(int argc, char **argv) +{ + int packet_count, offset = 0, i, err; + uint8_t *packets, *ptr; + struct desc d = { 0 }; + struct kernel_set *ks; + struct set s = { 0 }; + uint32_t key; +#ifdef VERBOSE + char *total_mem_suffix = "B"; + int total_mem = 0; + struct field *f; +#else + struct timespec tp_start, tp_end; + int repeat = 0, b = 0; + double time = 0; +#endif + (void)key; + + if (argc != 3) + usage(argv[0]); + + verbose("=== Parsing\n"); + + if ((packet_count = packet_parse(argv[2], &packets)) < 0) { + fprintf(stderr, "Parsing failed, %s\n", strerror(packet_count)); + exit(packet_count); + } + + if ((err = desc_parse(argv[1], &d))) { + fprintf(stderr, "Parsing failed, %s\n", strerror(err)); + return err; + } + verbose("\n"); + + verbose("=== Pre-computation\n"); + + if ((err = init(&s, d.layout))) { + fprintf(stderr, "Set init failed, %s\n", strerror(err)); + return err; + } + + for (i = 0; i < d.entries; i++) { + if (*(enum set_ops *)(d.data + offset) == ADD) + err = add(&s, d.layout, + d.data + offset + sizeof(enum set_ops)); + else if (*(enum set_ops *)(d.data + offset) == LIST) + list_or_del(&s, d.layout, NULL); + else if (*(enum set_ops *)(d.data + offset) == DEL) + err = list_or_del(&s, d.layout, + d.data + offset + + sizeof(enum set_ops)); + + if (err) + return err; + offset += d.row_size; + } + + for (i = 0; d.layout[i]->type != KEY; i++) { + verbose("\n"); + verbose("Lookup table for %s:\n", d.layout[i]->label); + show_lookup(&s.fields[i]); + verbose("Mapping table for %s:\n", d.layout[i]->label); + show_mapping(&s.fields[i], d.layout[i + 1]->type == KEY); + } + verbose("\n"); + + verbose("=== Match\n"); + + ks = kernel_init(&s, d.layout); + +#ifndef VERBOSE +repeat_block: + repeat = PERF_TEST_BLOCK; + b++; + clock_gettime(CLOCK_MONOTONIC, &tp_start); + do { +#endif + ptr = packets; + for (i = 0; i < packet_count; i++) { + key = match(ks, ptr + sizeof(uint32_t)); +#ifdef VERBOSE + verbose("Packet #%i => key: %u\n\n", i, key); + if (key != *(uint32_t *)ptr) { + verbose("FAIL: expected key: %u\n", + *(uint32_t *)ptr); + return 1; + } +#endif + ptr += PACKET_SIZE + sizeof(uint32_t); + } +#ifndef VERBOSE + } while (repeat--); + clock_gettime(CLOCK_MONOTONIC, &tp_end); + time += (tp_end.tv_sec - tp_start.tv_sec) + + (tp_end.tv_nsec - tp_start.tv_nsec) / 1E9; + if (time < 5) { + goto repeat_block; + } + + fprintf(stdout, "Matched %lfM packets in %lfs (%lf Mpps)\n", + PERF_TEST_BLOCK * b * packet_count / 1000.0 / 1000, + time, + PERF_TEST_BLOCK * b * packet_count / 1000.0 / 1000 / time); +#endif + +#ifdef VERBOSE + verbose("\n"); + + verbose("\n=== Memory Usage\n"); + for_each_field(f, &s, d.layout) { + char *lt_suffix = "B", *mt_suffix = "B", *field_suffix = "B"; + int lt_size = f->groups * BUCKETS * f->bsize; + int mt_size = f->rules * sizeof(*f->mt); + int field_size; + + total_mem += field_size = lt_size + mt_size + sizeof(*f); + + if (lt_size > 20 * 1024) { + lt_size /= 1024; + lt_suffix = "KiB"; + } + + if (mt_size > 20 * 1024) { + mt_size /= 1024; + mt_suffix = "KiB"; + } + + if (field_size > 20 * 1024) { + field_size /= 1024; + field_suffix = "KiB"; + } + + verbose("Field %i, %s, %i rules:\n", i, d.layout[i]->label, + f->rules); + verbose(" lookup table: %i%s\n", lt_size, lt_suffix); + free(f->lt); + verbose(" mapping table: %i%s\n", mt_size, mt_suffix); + free(f->mt); + verbose(" total: %i%s\n", field_size, field_suffix); + verbose("\n"); + } + + if (total_mem > 50 * 1024 * 1024) { + total_mem /= 1024 * 1024; + total_mem_suffix = "MiB"; + } else if (total_mem > 20 * 1024) { + total_mem /= 1024; + total_mem_suffix = "KiB"; + } + verbose("Total: %i%s\n", total_mem, total_mem_suffix); +#endif + + /* Rest of allocated data is volatile */ + free(s.fields); + free(d.data); + free(packets); + free(ks->map[0]); + free(ks->map[1]); + for (i = 0; i < 8; i++) { + free(ks->lt[i]); + free(ks->mt[i]); + } + free(ks); + + return 0; +} diff --git a/pipapo.h b/pipapo.h new file mode 100644 index 0000000..4d10ca8 --- /dev/null +++ b/pipapo.h @@ -0,0 +1,141 @@ +#define PACKET_SIZE 64 +#define GROUP_BITS 4 +#define BUCKETS (1 << GROUP_BITS) +#define MAX_FIELDS 8 /* E.g. mac,mac,addr,addr,port,port */ + +#define ADDR_LEN 4 +#define ADDR6_LEN 16 +#define PORT_LEN 2 +#define MAC_LEN 6 + +#ifdef __MATCH_AVX2 +#ifdef __AVX2__ +#define MATCH_AVX2 +#else +#warning "AVX2 not supported, disabling" +#endif +#endif + +#ifdef __MATCH_CTZL +#ifdef __GNUC__ +#define MATCH_CTZL +#else +#warning "__builtin_ctzl() not supported, disabling" +#endif +#endif + +/** + * enum desc_type - Types used in set description entries + * @KEY: Verdict key for packets matching entry + * @ADDR: IPv4 address + * @PORT: Generic 16-bit port + * @ADDR6: IPv6 address + * @MAC: MAC address + */ +enum desc_type { + KEY, + ADDR, + PORT, + ADDR6, + MAC, +}; + +/** + * enum set_ops - Operations used in set files + * @ADD: Add entry to set + * @LIST: List current set entries + * @DEL: Delete entry from set + */ +enum set_ops { + ADD, + LIST, + DEL, +}; + +/** + * struct desc_spec - Description of a single set specifier + * @label: Field name + * @type: Type of set field + * @len: Length of packet field to be matched, in bytes + * @offset: Field offset in packet, bytes + */ +struct desc_spec { + char *label; + enum desc_type type; + int len; + int offset; +}; + +/** + * struct desc - Description of a set + * @layout: Layout as array of field specifiers + * @fields: Number of fields + * @row_size: Size of binary data for one entry (input to pre-computation) + * @entries: Total number of set operations + * @data: Binary data for pre-computation, concatenation of structs below + */ +struct desc { + struct desc_spec *layout[MAX_FIELDS]; + int fields; + int row_size; + int entries; + uint8_t *data; +}; + +/** + * struct addr - Represent an IPv4 address, range or mask (in set description) + * @start: Start of range, or address + * @end: End of range, zero for single addresses or masks + * @cidr: Mask length, 0 for ranges, 32 for single addresses + */ +struct addr { + uint32_t start; + uint32_t end; + uint8_t cidr; +}; + +/** + * struct addr6 - Represent an IPv6 address, range or mask (in set description) + * @start: Start of range, or address + * @end: End of range, zero for single addresses or masks + * @cidr: Mask length, 0 for ranges, 128 for single addresses + */ +struct addr6 { + uint32_t start[4]; + uint32_t end[4]; + uint8_t cidr; +}; + +/** + * struct port - Represent a port or port range (in set description) + * @start: Start of range, or single port number + * @end: End of range, zero for single port + */ +struct port { + uint16_t start; + uint16_t end; +}; + +/** + * struct mac - Represent a MAC address or range (in set description) + * @start: Start of range, or single MAC address + * @end: End of range, zero for single MAC address + */ +struct mac { + uint8_t start[6]; + uint8_t end[6]; +}; + +/** + * union map_bucket - Bucket in mapping table (algorithm steps 3.5, 3.6) + * @to: First rule number (in next field) this rule maps to + * @n: Number of rules (in next field) this rule maps to + * @key: If there's no next field, key this rule maps to + */ +union map_bucket { + struct { + uint32_t to:24; + uint32_t n:8; + }; + uint32_t key; +}; diff --git a/set.c b/set.c new file mode 100644 index 0000000..6943b36 --- /dev/null +++ b/set.c @@ -0,0 +1,902 @@ +/* PIPAPO - PIle PAcket POlicies + * + * set.c - Insertion, listing, deletion + * + * Author: Stefano Brivio + * License: GPLv2 + */ + +#include +#include +#include +#include +#include +#include + +#include "pipapo.h" +#include "set.h" +#include "util.h" + +/** + * struct rule_map - Internal convenience only: first number and amount of rules + * @x: Number of first rule + * @n: Rule count + */ +struct rule_map { + int x, n; +}; + +/** + * base_step_diff() - Check if setting 'step' bit in mask changes it + * @base: Mask we are expanding + * @step: Step bit for given expansion step + * @len: Total length of mask space (set and unset bits), bytes + * + * Convenience function for mask expansion. + * + * Return: non-zero if given step bit changes mask base, 0 otherwise. + */ +static int base_step_diff(uint8_t *base, int step, int len) +{ + uint8_t tmp[16]; + + memcpy(tmp, base, len); + set_bit(tmp + len - 1 - step / 8, step % 8, len); + + return memcmp(tmp, base, len); +} + +/** + * base_step_after_end() - Check if mask reaches after range end with given step + * @base: Mask we are expanding + * @end: End of range + * @step: Step bit for given expansion step + * @len: Total length of mask space (set and unset bits), bytes + * + * Convenience function for mask expansion. + * + * Return: non-zero if mask exceeds range with step bit, 0 otherwise. + */ +static int base_step_after_end(uint8_t *base, uint8_t *end, int step, int len) +{ + uint8_t tmp[16]; + int i; + + memcpy(tmp, base, len); + + for (i = 0; i <= step; i++) + set_bit(tmp + len - 1 - i / 8, i % 8, len); + + return memcmp(tmp, end, len) > 0; +} + +/** + * resize() - Resize lookup and mapping tables according to new number of rules + * @f: Field containing lookup and mapping tables + * @old_rules: Previous amount of rules in field + * @rules: New amount of rules + * + * Increase, decrease or maintain tables size depending on new amount of rules, + * and copy data over. In case the new size is smaller, throw away data for + * highest-numbered rules. + * + * Return: 0 on success, -ENOMEM on allocation failure. + */ +static int resize(struct field *f, int old_rules, int rules) +{ + uint8_t *new_lt = NULL, *new_p, *old_lt = f->lt, *old_p; + union map_bucket *new_mt, *old_mt = f->mt; + ssize_t new_bucket_size, copy; + int group, bucket; + + new_bucket_size = DIV_ROUND_UP(rules, 8); +#if defined(MATCH_AVX2) || defined(MATCH_CTZL) + new_bucket_size = round_up(new_bucket_size, 32); +#endif + + if (new_bucket_size == f->bsize) + goto mt; + + if (new_bucket_size > f->bsize) + copy = f->bsize; + else + copy = new_bucket_size; + + new_p = new_lt = calloc(new_bucket_size, f->groups * BUCKETS); + if (!new_lt) + return -ENOMEM; + + old_p = old_lt; + for (group = 0; group < f->groups; group++) { + for (bucket = 0; bucket < BUCKETS; bucket++) { + memcpy(new_p, old_p, copy); + new_p += copy; + old_p += copy; + + if (new_bucket_size > f->bsize) + new_p += new_bucket_size - f->bsize; + else + old_p += f->bsize - new_bucket_size; + } + } +mt: + new_mt = calloc(rules, sizeof(*new_mt)); + if (!new_mt) { + free(new_lt); + return -ENOMEM; + } + + if (f->mt) + memcpy(new_mt, f->mt, min(old_rules, rules) * sizeof(*new_mt)); + + f->bsize = new_bucket_size; + + if (new_lt) { + f->lt = new_lt; + free(old_lt); + } + + f->mt = new_mt; + free(old_mt); + + return 0; +} + +/** + * bucket_set_bit() - Set rule bit in lookup bucket according to group value + * @f: Field containing lookup table + * @rule: Rule bit number to be set + * @group: Bit group in field + * @v: Value of 4-bit group + */ +static void bucket_set_bit(struct field *f, int rule, int group, int v) +{ + uint8_t *pos; + + pos = f->lt + f->bsize * BUCKETS * group; + pos += f->bsize * v; + + set_bit(pos, rule, f->bsize); +} + +/** + * insert() - Insert new rule in field given binary data and mask length + * @f: Field containing lookup table + * @data: Base value of classifying entry + * @mask_len: Length of mask, matches field length for non-ranged entry + * + * Insert a new rule reference in lookup buckets corresponding to data and + * mask_len. This implements algorithm step 3.4. + * + * Return: 1 on success, negative error code on failure. + */ +static int insert(struct field *f, uint8_t *data, int mask_len) +{ + int rule = f->rules++, group, ret, i, v; + uint8_t mask; + + ret = resize(f, f->rules - 1, f->rules); + if (ret) + return ret; + + for (group = 0; group < f->groups; group++) { + if (group % 2) + v = data[group / 2] & 0x0f; + else + v = (data[group / 2] & 0xf0) >> 4; + + if (mask_len >= (group + 1) * 4) { + /* Not masked */ + bucket_set_bit(f, rule, group, v); + } else if (mask_len <= group * 4) { + /* Completely masked */ + for (i = 0; i < (4 << 2); i++) + bucket_set_bit(f, rule, group, i); + } else { + /* The mask limit falls on this group */ + mask = 0x0f >> (mask_len - group * 4); + for (i = 0; i < (4 << 2); i++) { + if ((i & ~mask) == (v & ~mask)) + bucket_set_bit(f, rule, group, i); + } + } + } + + return 1; +} + +/** + * expand() - Expand range to composing netmasks and insert into lookup table + * @f: Field containing lookup table + * @start: Start of range + * @end: End of range + * @mask_len: Length of mask, matches field length for non-ranged entry TODO + * + * Expand range to composing netmasks and insert corresponding rule references + * in lookup buckets. This implements algorithm steps 3.3 - 3.4. + * + * Return: number of inserted rules on success, negative error code on failure. + */ +static int expand(struct field *f, uint8_t *start, uint8_t *end, int len) +{ + int step, masks = 0, err; + uint8_t base[16]; + + memcpy(base, start, len); + while (memcmp(base, end, len) <= 0) { + step = 0; + while (base_step_diff(base, step, len)) { + if (base_step_after_end(base, end, step, len)) + break; + step++; + + if (step >= len * 8) + goto out; + } + + err = insert(f, base, len * 8 - step); + if (err < 0) + return err; + + masks++; + bit_sum(base, step, len); + } + +out: + return masks; +} + +/** + * map() - Insert references in mapping tables, mapping rules between fields + * @s: Set data + * @layout: Set layout + * @rmap: Table of rule maps, arrays of first rule and amount of rules + * in next field a given rule maps to, for each field + * @key: Verdict key the inserted rules finally map to, in last field + * + * This implements algorithm steps 3.5 - 3.6. + */ +static void map(struct set *s, struct desc_spec **layout, + struct rule_map rmap[16], uint32_t key) +{ + struct field *f; + int i, j; + + for (i = 0, f = s->fields; layout[i + 1]->type != KEY; i++, f++) { + for (j = 0; j < rmap[i].n; j++) { + f->mt[rmap[i].x + j].to = rmap[i + 1].x; + f->mt[rmap[i].x + j].n = rmap[i + 1].n; + } + } + + for (j = 0; j < rmap[i].n; j++) + f->mt[rmap[i].x + j].key = key; +} + +/** + * add() - Insert one entry in set data + * @s: Set data + * @layout: Set layout + * @data: Concatenation of structs with parsed values for each field item + * + * This is the entry point for all algorithm steps in section 3. + */ +int add(struct set *s, struct desc_spec **layout, uint8_t *data) +{ + uint8_t zero_mac[MAC_LEN] = { 0 }; + struct rule_map rmap[16] = { 0 }; + char buf[BUFSIZ], buf2[BUFSIZ]; + struct field *f; + struct addr6 *a6; + struct addr *a; + struct port *p; + struct mac *m; + int i, ret = 0; + + (void)buf; + (void)buf2; + + for_each_field(f, s, layout) { + /* See union map_bucket */ + if (f->rules >= (1 << (24 - 1)) - 256) + return -ENOSPC; + } + + verbose("Adding entry:\n"); + + for_each_field(f, s, layout) { + rmap[i].x = f->rules; + + verbose(" inserting %s, ", layout[i]->label); + + switch (layout[i]->type) { + case ADDR: + a = (struct addr *)data; + + if (a->cidr == 0) { + verbose("start: %s, end: %s, ", + inet_ntop(AF_INET, &a->start, buf, + BUFSIZ), + inet_ntop(AF_INET, &a->end, buf2, + BUFSIZ)); + } else if (a->cidr == 32) { + verbose("address: %s, ", + inet_ntop(AF_INET, &a->start, buf, + BUFSIZ)); + } else { + verbose("address: %s/%i, ", + inet_ntop(AF_INET, &a->start, buf, + BUFSIZ), + a->cidr); + } + + if (a->cidr) + ret = insert(f, (uint8_t *)&a->start, a->cidr); + else + ret = expand(f, (uint8_t *)&a->start, + (uint8_t *)&a->end, ADDR_LEN); + if (ret < 0) + return ret; + + data += sizeof(*a); + break; + case ADDR6: + a6 = (struct addr6 *)data; + + if (a6->cidr == 0) { + verbose("start: %s, end: %s, ", + inet_ntop(AF_INET6, &a6->start, buf, + BUFSIZ), + inet_ntop(AF_INET6, &a6->end, buf2, + BUFSIZ)); + } else if (a6->cidr == 128) { + verbose("address: %s, ", + inet_ntop(AF_INET6, &a6->start, buf, + BUFSIZ)); + } else { + verbose("address: %s/%i, ", + inet_ntop(AF_INET6, &a6->start, buf, + BUFSIZ), + a6->cidr); + } + + if (a6->cidr) + ret = insert(f, (uint8_t *)&a6->start, + a6->cidr); + else + ret = expand(f, (uint8_t *)&a6->start, + (uint8_t *)&a6->end, ADDR6_LEN); + if (ret < 0) + return ret; + + data += sizeof(*a6); + break; + case PORT: + p = (struct port *)data; + + if (p->end) + verbose("start: %i, end: %i, ", + ntohs(p->start), ntohs(p->end)); + else + verbose("port: %i, ", ntohs(p->start)); + + if (p->end) + ret = expand(f, (uint8_t *)&p->start, + (uint8_t *)&p->end, PORT_LEN); + else + ret = insert(f, (uint8_t *)&p->start, + ADDR6_LEN * 8); + if (ret < 0) + return ret; + + data += sizeof(*p); + break; + case MAC: + m = (struct mac *)data; + + if (memcmp(&m->end, zero_mac, MAC_LEN)) + verbose("start: %02x:%02x:%02x:%02x:%02x:%02x, " + "end: %02x:%02x:%02x:%02x:%02x:%02x, ", + m->start[0], m->start[1], m->start[2], + m->start[3], m->start[4], m->start[5], + m->end[0], m->end[1], m->end[2], + m->end[3], m->end[4], m->end[5]); + else + verbose("mac: %02x:%02x:%02x:%02x:%02x:%02x, ", + m->start[0], m->start[1], m->start[2], + m->start[3], m->start[4], m->start[5]); + + if (memcmp(&m->end, zero_mac, MAC_LEN)) + ret = expand(f, m->start, m->end, MAC_LEN); + else + ret = insert(f, m->start, MAC_LEN * 8); + if (ret < 0) + return ret; + + data += sizeof(*m); + break; + case KEY: + break; + } + + if (ret > 1) + verbose("rules %i-%i\n", rmap[i].x, + rmap[i].x + ret - 1); + else + verbose("rule %i\n", rmap[i].x); + rmap[i].n = ret; + } + + map(s, layout, rmap, *(uint32_t *)data); + + return 0; +} + +/** + * rules_same_key() - Find amount of rules mapping to the same rules/key + * @f: Field containing mapping table + * @start: First rule to be checked against subsequent ones + * + * This is used to find out how many rules were created as part of the same set + * entry, for listing and deletion. + * + * Return: amount of rules mapping to the same rules or key given starting one + */ +static int rules_same_key(struct field *f, int start) +{ + uint32_t key; + int r; + + for (r = start; r < f->rules; r++) { + if (r != start && key != f->mt[r].key) + return r - start; + + key = f->mt[r].key; + } + + if (r != start) + return r - start; + + return 0; +} + +/** + * aggregate() - Aggregate rules back to originating entries, print or match + * @f: Field containing lookup and mapping tables + * @type: Field type + * @start: First rule for entry + * @len: Amount of rules originated from same entry + * @match: Optional (used for deletion), struct with field value + * + * This is used in listing, to print originating entries for rules found in + * lookup tables, and in deletion, to check a group of rules against the values + * we want to delete from a given set field. + * + * Return: 0 on match or if no match is requested, non-zero otherwise. + */ +static int aggregate(struct field *f, enum desc_type type, int start, int len, + uint8_t *match) +{ + uint8_t left[16] = { 0 }, *l = left, right[16] = { 0 }, *r = right; + uint8_t zero_mac[MAC_LEN] = { 0 }; + char buf_l[BUFSIZ], buf_r[BUFSIZ]; + int g, b, x0, x1, mask_len = 0; + struct addr6 *a6; + struct addr *a; + struct port *p; + struct mac *m; + + for (g = 0; g < f->groups; g++) { + x0 = x1 = -1; + for (b = 0; b < BUCKETS; b++) { + if (test_bit(f->lt + (g * BUCKETS + b) * f->bsize, + start)) + if (x0 == -1) + x0 = b; + if (test_bit(f->lt + (g * BUCKETS + b) * f->bsize, + start + len - 1)) + x1 = b; + } + + if (g % 2) { + *(l++) |= x0 & 0x0f; + *(r++) |= x1 & 0x0f; + } else { + *l |= x0 << 4; + *r |= x1 << 4; + } + + if (x1 - x0 == 0) + mask_len += 4; + else if (x1 - x0 == 1) + mask_len += 3; + else if (x1 - x0 == 3) + mask_len += 2; + else if (x1 - x0 == 7) + mask_len += 1; + } + + l = left; + r = right; + + switch (type) { + case ADDR: + if (match) { + a = (struct addr *)match; + if (!a->cidr) + return !memcmp(&a->start, l, ADDR_LEN) && + !memcmp(&a->end, r, ADDR_LEN); + return !memcmp(&a->start, l, ADDR_LEN) && + (a->cidr == mask_len); + } + + inet_ntop(AF_INET, l, buf_l, BUFSIZ); + inet_ntop(AF_INET, r, buf_r, BUFSIZ); + if (mask_len == 32) + fprintf(stdout, "%s ", buf_l); + else if (len == 1) + fprintf(stdout, "%s/%i ", buf_l, mask_len); + else + fprintf(stdout, "%s-%s ", buf_l, buf_r); + break; + case ADDR6: + if (match) { + a6 = (struct addr6 *)match; + if (!a6->cidr) + return !memcmp(&a6->start, l, ADDR6_LEN) && + !memcmp(&a6->end, r, ADDR6_LEN); + return !memcmp(&a6->start, l, ADDR_LEN) && + (a6->cidr == mask_len); + } + + inet_ntop(AF_INET6, l, buf_l, BUFSIZ); + inet_ntop(AF_INET6, r, buf_r, BUFSIZ); + if (mask_len == 128) + fprintf(stdout, "%s ", buf_l); + else if (len == 1) + fprintf(stdout, "%s/%i ", buf_l, mask_len); + else + fprintf(stdout, "%s-%s ", buf_l, buf_r); + break; + case PORT: + if (match) { + p = (struct port *)match; + return p->start == *(uint16_t *)l && + (!p->end || p->end == *(uint16_t *)r); + } + + if (mask_len == 16 && len == 1) + fprintf(stdout, "%u ", ntohs(*(uint16_t *)l)); + else + fprintf(stdout, "%u-%u ", ntohs(*(uint16_t *)l), + ntohs(*(uint16_t *)r)); + break; + case MAC: + if (match) { + m = (struct mac *)match; + return !memcmp(&m->start, l, MAC_LEN) && + (memcmp(zero_mac, &m->end, MAC_LEN) || + !memcmp(&m->end, r, MAC_LEN)); + } + + if (mask_len == 48 && len == 1) + fprintf(stdout, "%02x:%02x:%02x:%02x:%02x:%02x ", + l[0], l[1], l[2], l[3], l[4], l[5]); + else + fprintf(stdout, "%02x:%02x:%02x:%02x:%02x:%02x-" + "%02x:%02x:%02x:%02x:%02x:%02x ", + l[0], l[1], l[2], l[3], l[4], l[5], + r[0], r[1], r[2], r[3], r[4], r[5]); + break; + default: + break; + } + + return 0; +} + +/** + * unmap() - Delete group of rules from mapping table, renumber remaining ones + * @mt: Mapping table + * @rules: Original amount of rules in mapping table + * @start: First rule to be deleted + * @n: Amount of rules originated from same entry + * @to_offset: First rule index in next field this group of rules maps to + * @is_key: If this is the last field, delete key from mapping table + * + * This is used to unmap rules from the mapping table for a single field, + * maintaining consistency and compactness for the existing ones. In pictures: + * let's assume that we want to delete rules 2 and 3 from the following mapping + * table: + * + * rules + * 0 1 2 3 4 + * map to: 4-10 4-10 11-15 11-15 16-18 + * + * the result will be: + * + * rules + * 0 1 2 + * map to: 4-10 4-10 11-13 + * + * for fields before the last one. In case this is the mapping table for the + * last field in a set, and its rules map to verdict keys: + * + * rules + * 0 1 2 3 4 + * key: 42 42 33 33 44 + * + * the result will be: + * + * rules + * 0 1 2 + * key: 42 42 44 + */ +void unmap(union map_bucket *mt, int rules, int start, int n, int to_offset, + int is_key) +{ + int i; + + memmove(mt + start, mt + start + n, (rules - start - n) * sizeof(*mt)); + memset(mt + rules - n, 0, n * sizeof(*mt)); + + if (is_key) + return; + + for (i = start; i < rules - n; i++) + mt[i].to -= to_offset; +} + +/** + * drop() - Delete entry from lookup and mapping tables, given rule mapping + * @s: Set data + * @layout: Set layout + * @rmap: Table of rule maps, arrays of first rule and amount of rules + * in next field a given entry maps to, for each field + * + * For each rule in lookup table buckets mapping to this set of rules, drop + * all bits set in lookup table mapping. In pictures, assuming we want to drop + * rules 0 and 1 from this lookup table: + * + * bucket + * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 + * 0 0 1,2 + * 1 1,2 0 + * 2 0 1,2 + * 3 0 1,2 + * 4 0,1,2 + * 5 0 1 2 + * 6 0,1,2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 + * 7 1,2 1,2 1 1 1 0,1 1 1 1 1 1 1 1 1 1 1 + * + * rule 2 becomes rule 0, and the result will be: + * + * bucket + * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 + * 0 0 + * 1 0 + * 2 0 + * 3 0 + * 4 0 + * 5 0 + * 6 0 + * 7 0 0 + * + * once this is done, call unmap() to drop all the corresponding rule references + * from mapping tables. + */ +static void drop(struct set *s, struct desc_spec **layout, + struct rule_map rmap[16]) +{ + struct field *f; + int i, g, b; + + for_each_field(f, s, layout) { + for (g = 0; g < f->groups; g++) { + for (b = 0; b < BUCKETS; b++) + fold_bits(f->lt + (g * BUCKETS + b) * f->bsize, + rmap[i].x, rmap[i].n, f->bsize); + } + unmap(f->mt, f->rules, rmap[i].x, rmap[i].n, rmap[i + 1].n, + layout[i + 1]->type == KEY); + + resize(f, f->rules, f->rules - rmap[i].n); + f->rules -= rmap[i].n; + } +} + +/** + * list_or_del() - List set entries, or delete entry if del_match is passed + * @s: Set data + * @layout: Set layout + * @del_match: Optional, delete matching entry (concatenation of values) + * + * Return: 0 on listing and successful deletion, -ENOENT on match failure. + */ +int list_or_del(struct set *s, struct desc_spec **layout, uint8_t *del_match) +{ + int f0_rules, fx_rules, start, first_rule = 0, i, l, found; + struct rule_map rmap[16] = { 0 }; + uint8_t *p = del_match; + struct field *f; + + if (!del_match) { + fprintf(stdout, "List:"); + for (l = 0; layout[l]->type != KEY; l++) + fprintf(stdout, " %s", layout[l]->label); + fprintf(stdout, "\n"); + } + + while ((f0_rules = rules_same_key(s->fields + 0, first_rule))) { + start = first_rule; + fx_rules = f0_rules; + + p = del_match; + for (i = 0, f = s->fields; layout[i]->type != KEY; i++, f++) { + found = aggregate(f, layout[i]->type, start, fx_rules, + p); + + rmap[i].x = start; + rmap[i].n = fx_rules; + + if (del_match) { + if (!found) + break; + if (layout[i]->type == ADDR) + p += sizeof(struct addr); + else if (layout[i]->type == ADDR6) + p += sizeof(struct addr6); + else if (layout[i]->type == PORT) + p += sizeof(struct port); + else if (layout[i]->type == MAC) + p += sizeof(struct mac); + + if (layout[i + 1]->type == KEY && + *(uint32_t *)p == f->mt[start].key) { + drop(s, layout, rmap); + return 0; + } + } + + if (layout[i + 1]->type == KEY) { + fprintf(stdout, "%u\n", f->mt[start].key); + } else { + fx_rules = f->mt[start].n; + start = f->mt[start].to; + } + } + + first_rule += f0_rules; + } + + if (del_match) + return -ENOENT; + + return 0; +} + +/** + * init() - Initialise set data + * @set: Empty set, array of fields + * @layout: Parsed set layout + * + * Return: 0 on success, -ENOMEM on allocation failure. + */ +int init(struct set *s, struct desc_spec **layout) +{ + struct field *f; + int i; + + for (i = 0; layout[i]->type != KEY; i++); + + s->fields = malloc(sizeof(struct field) * i); + if (!s->fields) + return -ENOMEM; + + s->fields[i - 1].groups = 0; + + for_each_field(f, s, layout) { + f->groups = layout[i]->len * 2; /* 4-bit groups */ + f->offset = layout[i]->offset; + f->bsize = 0; + f->rules = 0; + f->lt = NULL; + f->mt = NULL; + } + + return 0; +} + +#ifdef VERBOSE +/** + * show_lookup() - Print lookup table for given field + * @field: Field containing lookup table + * + * For documentation purposes only. + */ +void show_lookup(struct field *f) +{ + int bucket, group, in_group = 0, v; + uint8_t *copy, *p; + + copy = malloc(f->groups * BUCKETS * f->bsize); + memcpy(copy, f->lt, f->groups * BUCKETS * f->bsize); + + fprintf(stdout, "%20s\n", "bucket"); + fprintf(stdout, "group "); + for (bucket = 0; bucket < BUCKETS; bucket++) + fprintf(stdout, "%5i", bucket); + fprintf(stdout, "\n"); + + p = copy; + for (group = 0; group < f->groups; group++) { + if (in_group) + fprintf(stdout, " "); + else + fprintf(stdout, "%3i ", group); + + in_group = 0; + for (bucket = 0; bucket < BUCKETS; bucket++) { + v = ffs_clear(p, f->bsize, 0); + if (v >= 0) { + in_group = 1; + fprintf(stdout, "%5i", v); + } else { + fprintf(stdout, " "); + } + p += f->bsize; + } + + if (in_group) { + p -= BUCKETS * f->bsize; + group--; + } + fprintf(stdout, "\n"); + } + + free(copy); +} + +/** + * show_lookup() - Print mapping table for given field + * @field: Field containing mapping table + * @to_key: Last field: print verdict keys instead of mapping to next field + * + * For documentation purposes only. + */ +void show_mapping(struct field *f, int to_key) +{ + uint32_t prev_key; + int r, prev_r; + + prev_key = f->mt[0].key; + prev_r = 0; + for (r = 1; r < f->rules + 1; r++) { + if (r < f->rules && f->mt[r].key == prev_key) + continue; + + if (prev_r != r - 1) + fprintf(stdout, "( %i-%i => ", prev_r, r - 1); + else + fprintf(stdout, "( %i => ", r - 1); + + if (to_key) { + fprintf(stdout, "%u ) ", prev_key); + } else { + if (f->mt[r - 1].n > 1) { + fprintf(stdout, "%i-%i ) ", f->mt[r - 1].to, + f->mt[r - 1].to + f->mt[r - 1].n - 1); + } else { + fprintf(stdout, "%i ) ", f->mt[r - 1].to); + } + } + + if (r < f->rules) { + prev_key = f->mt[r].key; + prev_r = r; + } + } + + fprintf(stdout, "\n"); +} +#endif diff --git a/set.h b/set.h new file mode 100644 index 0000000..37845d3 --- /dev/null +++ b/set.h @@ -0,0 +1,43 @@ +/** + * struct field - Pre-computed field data + * @offset: Offset in packet header, bytes + * @groups: Number of 4-bit groups + * @rules: Number of inserted rules + * @bsize: Lookup table bucket size, bytes + * @lt: Lookup table + * @mt: Mapping table (n:m rules in next field) + */ +struct field { + int offset; + int groups; + int rules; + + int bsize; + uint8_t *lt; + union map_bucket *mt; +}; + +/** + * struct set - Array of sets + * @fields: Composing fields + */ +struct set { + struct field *fields; +}; + +#define for_each_field(f, s, layout) \ + for ((i) = 0, (f) = (s)->fields; \ + (layout)[(i)]->type != KEY; \ + i++, f++) + +int init(struct set *s, struct desc_spec **layout); +int add(struct set *s, struct desc_spec **layout, uint8_t *data); +int list_or_del(struct set *s, struct desc_spec **layout, uint8_t *match); + +#ifdef VERBOSE +void show_lookup(struct field *f); +void show_mapping(struct field *f, int to_key); +#else +#define show_lookup(...) do { } while (0) +#define show_mapping(...) do { } while (0) +#endif diff --git a/tests/gen.sh b/tests/gen.sh new file mode 100755 index 0000000..05b3b51 --- /dev/null +++ b/tests/gen.sh @@ -0,0 +1,214 @@ +#!/bin/sh -e +# +# PIPAPO - PIle PAcket POlicies +# +# tests/gen.sh - Generate test sets and packets +# +# Author: Stefano Brivio +# License: GPLv2 + +rand() { + shuf -i ${1}-${2} -n 1 +} + +port() { + if [ "${size}" = "single" ]; then + p1=$(rand 0 65535) + p2=$((p1 / 2 + 1)) + + printf "dport key\na ${p1} 1\n" > port.single + printf "1 0 0 0 0 0 0 0 0 0 0 0 0 0x08 0x00 0x45 0 64 0 1 2 3 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 %i %i\n" $((p1 / 256)) $((p1 % 256)) > port.single.packets + printf "0 0 0 0 0 0 0 0 0 0 0 0 0 0x08 0x00 0x45 0 64 0 1 2 3 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 %i %i\n" $((p2 / 256)) $((p2 % 256)) >> port.single.packets + return + fi + + case ${size} in + tiny) n=100 ;; + small) n=1000 ;; + mid) n=10000 ;; + big) n=100000 ;; + huge) n=200000 ;; + esac + + :> port.${size}.packets + printf "dport key\n" > port.${size} + p=$(rand 0 10) + mul=$(rand 1 2) + inc=$(rand 1 50) + nopkt=0 + for i in $(seq 1 ${n}); do + p=$((p * mul + inc)) + if [ ${p} -ge 65536 ]; then + nopkt=1 + p=$((p % 65536)) + fi + if [ ${nopkt} -eq 0 ]; then + printf "%i 0 0 0 0 0 0 0 0 0 0 0 0 0x08 0x00 0x45 0 64 0 1 2 3 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 %i %i\n" ${i} $((p / 256)) $((p % 256)) >> port.${size}.packets + fi + printf "a %i %i\n" ${p} ${i} >> port.${size} + done +} + +net_port() { + if [ "${size}" = "single" ]; then + p1=$(rand 0 65535) + p2=$((p1 / 2 + 1)) + + printf "daddr dport key\na 10.$((p1 / 256)).$((p1 % 256)).5 ${p1} 1\n" > net_port.single + printf "1 0 0 0 0 0 0 0 0 0 0 0 0 0x08 0x00 0x45 0 64 0 1 2 3 0 0 1 0 0 0 0 0 0 10 %i %i 5 0 0 %i %i\n" $((p1 / 256)) $((p1 % 256)) $((p1 / 256)) $((p1 % 256)) > net_port.single.packets + printf "0 0 0 0 0 0 0 0 0 0 0 0 0 0x08 0x00 0x45 0 64 0 1 2 3 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 %i %i\n" $((p2 / 256)) $((p2 % 256)) >> net_port.single.packets + return + fi + + case ${size} in + tiny) n=10 ;; + small) n=100 ;; + mid) n=316 ;; + big) n=1000 ;; + huge) n=10000 ;; + esac + + :> net_port.${size}.packets + printf "daddr dport key\n" > net_port.${size} + a=$(rand 0 10) + p=$(rand 0 10) + inc=$(rand 1 50) + nopkt=0 + for i in $(seq 1 ${n}); do + mul=$(rand 1 5) + a=$((a + inc * mul)) + if [ ${a} -lt 4294967296 ]; then + a=$((a % 4294967296)) + else + nopkt=1 + fi + + a1=$((a / 16777216)) + a2=$(((a / 65536) % 256)) + a3=$(((a / 256) % 256)) + a4=$((a % 256)) + + p=$(((p * mul + inc) % 65536)) + p1=$((p / 256)) + p2=$((p % 256)) + + if [ ${nopkt} -eq 0 ]; then + printf "%i 0 0 0 0 0 0 0 0 0 0 0 0 0x08 0x00 0x45 0 64 0 1 2 3 0 0 1 0 0 0 0 0 0 %i %i %i %i 0 0 %i %i\n" ${i} ${a1} ${a2} ${a3} ${a4} ${p1} ${p2} >> net_port.${size}.packets + fi + printf "a %i.%i.%i.%i %i %i\n" ${a1} ${a2} ${a3} ${a4} ${p} ${i} >> net_port.${size} + done +} + +net_port_ranged() { + if [ "${size}" = "single" ]; then + p1=$(rand 0 65535) + p2=$((p1 / 2 + 1)) + + printf "daddr dport key\na 10.$((p1 / 256)).0.$((p1 % 256))-10.$((p1 / 256)).$((p1 / 256)).$((p1 / 256)) ${p1} 1\n" > net_port_ranged.single + printf "1 0 0 0 0 0 0 0 0 0 0 0 0 0x08 0x00 0x45 0 64 0 1 2 3 0 0 1 0 0 0 0 0 0 10 %i 0 %i 0 0 %i %i\n" $((p1 / 256)) $((p1 % 256)) $((p1 / 256)) $((p1 % 256)) > net_port_ranged.single.packets + printf "0 0 0 0 0 0 0 0 0 0 0 0 0 0x08 0x00 0x45 0 64 0 1 2 3 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 %i %i\n" $((p2 / 256)) $((p2 % 256)) >> net_port_ranged.single.packets + return + fi + + case ${size} in + tiny) n=10 ;; + small) n=100 ;; + mid) n=316 ;; + big) n=1000 ;; + huge) n=10000 ;; + esac + + :> net_port_ranged.${size}.packets + printf "daddr dport key\n" > net_port_ranged.${size} + a=$(rand 0 10) + p=$(rand 0 10) + inc=$(rand 1 50) + nopkt=0 + for i in $(seq 1 ${n}); do + mul=$(rand 2 5) + a=$((a + inc * mul)) + if [ ${a} -lt 4094967296 ]; then + a=$((a % 4094967296)) + else + nopkt=1 + fi + + end=$((a + inc)) + + s1=$((a / 16777216)) + s2=$(((a / 65536) % 256)) + s3=$(((a / 256) % 256)) + s4=$((a % 256)) + + e1=$((end / 16777216)) + e2=$(((end / 65536) % 256)) + e3=$(((end / 256) % 256)) + e4=$((end % 256)) + + p=$(((p * mul + inc) % 60536)) + p1=$((p / 256)) + p2=$((p % 256)) + + if [ ${nopkt} -eq 0 ] && [ ${s4} -ne ${e4} ]; then + printf "%i 0 0 0 0 0 0 0 0 0 0 0 0 0x08 0x00 0x45 0 64 0 1 2 3 0 0 1 0 0 0 0 0 0 %i %i %i %i 0 0 %i %i\n" ${i} ${s1} ${s2} ${s3} ${s4} ${p1} ${p2} >> net_port_ranged.${size}.packets + printf "%i 0 0 0 0 0 0 0 0 0 0 0 0 0x08 0x00 0x45 0 64 0 1 2 3 0 0 1 0 0 0 0 0 0 %i %i %i %i 0 0 %i %i\n" ${i} ${e1} ${e2} ${e3} ${e4} ${p1} ${p2} >> net_port_ranged.${size}.packets + fi + printf "a %i.%i.%i.%i-%i.%i.%i.%i %i-%i %i\n" ${s1} ${s2} ${s3} ${s4} ${e1} ${e2} ${e3} ${e4} ${p} $((p + inc)) ${i} >> net_port_ranged.${size} + done +} + +mac_net6_ranged() { + case ${size} in + single) n=1 ;; + tiny) n=3 ;; + small) n=10 ;; + mid) n=31 ;; + big) n=100 ;; + huge) n=316 ;; + esac + + :> mac_net6_ranged.${size}.packets + printf "dmac saddr6 key\n" > mac_net6_ranged.${size} + m=$(rand 0 10) + a=$(rand 0 10) + inc=$(rand 1 50) + nopkt=0 + for i in $(seq 1 ${n}); do + mul=$(rand 2 5) + + a=$((a + inc * mul)) + end=$((a + inc)) + + sh=$((a / 65535)) + sl=$((a % 65535)) + + eh=$((end / 65535)) + el=$((end % 65535)) + + s1=$((sh / 256)) + s2=$((sh % 256)) + s3=$((sl / 256)) + s4=$((sl % 256)) + + e1=$((eh / 256)) + e2=$((eh % 256)) + e3=$((el / 256)) + e4=$((el % 256)) + + m=$(((m * mul + inc) % 60536)) + m1=$((m / 256)) + m2=$((m % 256)) + + printf "%i 0 0 0 0 %i %i 0 0 0 0 0 0 0x86 0xdd 0x60 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x20 0x01 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x%02x 0x%02x 0x%02x 0x%02x\n" ${i} ${m1} ${m2} ${s1} ${s2} ${s3} ${s4} >> mac_net6_ranged.${size}.packets + printf "%i 0 0 0 0 %i %i 0 0 0 0 0 0 0x86 0xdd 0x60 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x20 0x01 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x%02x 0x%02x 0x%02x 0x%02x\n" ${i} ${m1} ${m2} ${e1} ${e2} ${e3} ${e4} >> mac_net6_ranged.${size}.packets + printf "a 00:00:00:00:%02x:%02x-00:00:00:%02x:00:00 2001::%04x:%04x-2001::%04x:%04x %i\n" ${m1} ${m2} $((m1 + 1)) ${sh} ${sl} ${eh} ${el} ${i} >> mac_net6_ranged.${size} + done +} + +for type in port net_port net_port_ranged mac_net6_ranged; do + for size in single tiny small mid big huge; do + printf "Generating ${type}.${size} test set..." + ${type} ${size} + printf " done\n" + done +done diff --git a/tests/mac_mac_addr_addr_port_port.static b/tests/mac_mac_addr_addr_port_port.static new file mode 100644 index 0000000..f578a1d --- /dev/null +++ b/tests/mac_mac_addr_addr_port_port.static @@ -0,0 +1,204 @@ +# Equivalent of mac,mac,net,net,port,port +dmac smac saddr daddr sport dport key +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 10.0.0.1-10.255.255.253 1.0.0.3-254.254.254.251 10-1000 1-60000 42 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-5000 22 43 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4000 22 4000 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4001 22 4001 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4002 22 4002 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4003 22 4003 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4004 22 4004 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4005 22 4005 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4006 22 4006 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4007 22 4007 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4008 22 4008 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4009 22 4009 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4010 22 4010 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4011 22 4011 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4012 22 4012 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4013 22 4013 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4014 22 4014 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4015 22 4015 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4016 22 4016 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4017 22 4017 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4018 22 4018 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4019 22 4019 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4020 22 4020 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4021 22 4021 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4022 22 4022 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4023 22 4023 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4024 22 4024 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4025 22 4025 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4026 22 4026 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4027 22 4027 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4028 22 4028 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4029 22 4029 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4030 22 4030 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4031 22 4031 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4032 22 4032 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4033 22 4033 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4034 22 4034 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4035 22 4035 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4036 22 4036 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4037 22 4037 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4038 22 4038 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4039 22 4039 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4040 22 4040 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4041 22 4041 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4042 22 4042 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4043 22 4043 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4044 22 4044 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4045 22 4045 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4046 22 4046 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4047 22 4047 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4048 22 4048 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4049 22 4049 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4050 22 4050 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4051 22 4051 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4052 22 4052 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4053 22 4053 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4054 22 4054 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4055 22 4055 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4056 22 4056 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4057 22 4057 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4058 22 4058 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4059 22 4059 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4060 22 4060 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4061 22 4061 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4062 22 4062 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4063 22 4063 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4064 22 4064 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4065 22 4065 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4066 22 4066 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4067 22 4067 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4068 22 4068 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4069 22 4069 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4070 22 4070 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4071 22 4071 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4072 22 4072 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4073 22 4073 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4074 22 4074 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4075 22 4075 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4076 22 4076 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4077 22 4077 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4078 22 4078 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4079 22 4079 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4080 22 4080 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4081 22 4081 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4082 22 4082 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4083 22 4083 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4084 22 4084 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4085 22 4085 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4086 22 4086 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4087 22 4087 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4088 22 4088 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4089 22 4089 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4090 22 4090 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4091 22 4091 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4092 22 4092 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4093 22 4093 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4094 22 4094 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4095 22 4095 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4096 22 4096 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4097 22 4097 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4098 22 4098 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4099 22 4099 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4100 22 4100 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4101 22 4101 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4102 22 4102 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4103 22 4103 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4104 22 4104 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4105 22 4105 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4106 22 4106 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4107 22 4107 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4108 22 4108 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4109 22 4109 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4110 22 4110 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4111 22 4111 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4112 22 4112 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4113 22 4113 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4114 22 4114 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4115 22 4115 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4116 22 4116 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4117 22 4117 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4118 22 4118 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4119 22 4119 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4120 22 4120 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4121 22 4121 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4122 22 4122 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4123 22 4123 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4124 22 4124 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4125 22 4125 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4126 22 4126 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4127 22 4127 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4128 22 4128 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4129 22 4129 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4130 22 4130 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4131 22 4131 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4132 22 4132 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4133 22 4133 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4134 22 4134 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4135 22 4135 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4136 22 4136 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4137 22 4137 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4138 22 4138 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4139 22 4139 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4140 22 4140 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4141 22 4141 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4142 22 4142 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4143 22 4143 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4144 22 4144 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4145 22 4145 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4146 22 4146 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4147 22 4147 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4148 22 4148 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4149 22 4149 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4150 22 4150 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4151 22 4151 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4152 22 4152 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4153 22 4153 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4154 22 4154 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4155 22 4155 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4156 22 4156 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4157 22 4157 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4158 22 4158 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4159 22 4159 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4160 22 4160 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4161 22 4161 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4162 22 4162 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4163 22 4163 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4164 22 4164 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4165 22 4165 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4166 22 4166 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4167 22 4167 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4168 22 4168 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4169 22 4169 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4170 22 4170 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4171 22 4171 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4172 22 4172 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4173 22 4173 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4174 22 4174 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4175 22 4175 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4176 22 4176 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4177 22 4177 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4178 22 4178 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4179 22 4179 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4180 22 4180 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4181 22 4181 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4182 22 4182 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4183 22 4183 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4184 22 4184 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4185 22 4185 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4186 22 4186 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4187 22 4187 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4188 22 4188 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4189 22 4189 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4190 22 4190 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4191 22 4191 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4192 22 4192 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4193 22 4193 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4194 22 4194 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4195 22 4195 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4196 22 4196 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4197 22 4197 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4198 22 4198 +a 00:b0:cc:ac:c1:00 00:de:ad:c0:ff:ee-00:de:ad:c0:ff:ff 192.168.1.1 192.168.1.2 1-4199 22 4199 diff --git a/tests/mac_mac_addr_addr_port_port.static.packets b/tests/mac_mac_addr_addr_port_port.static.packets new file mode 100644 index 0000000..fac1061 --- /dev/null +++ b/tests/mac_mac_addr_addr_port_port.static.packets @@ -0,0 +1,7 @@ +# KEY BYTES, PACKET_SIZE bytes as decimal or hex will be read, the rest + discarded, packets are zero-padded if less than PACKET_SIZE. KEY is the + expected matching key from the ruleset, 0 if no match is expected +# Key MAC IPv4 DSCP Length ID Flags TTL Checksum Source Destination sport dport +42 0x00 0xb0 0xcc 0xac 0xc1 0x00 0x00 0xde 0xad 0xc0 0xff 0xfe 0x08 0x00 0x45 0 64 0 1 2 3 0 0 1 0 0 10 0 128 255 10 0 0 3 0 10 0 22 +0 0x00 0xb0 0xcc 0xac 0xc1 0x00 0x00 0xde 0xad 0xc0 0xff 0xfe 0x08 0x00 0x45 0 64 0 1 2 3 0 0 1 0 0 192 168 1 1 10 0 0 3 0 10 0 22 +43 0x00 0xb0 0xcc 0xac 0xc1 0x00 0x00 0xde 0xad 0xc0 0xff 0xfe 0x08 0x00 0x45 0 64 0 1 2 3 0 0 1 0 0 192 168 1 1 192 168 1 2 0 10 0 22 diff --git a/tests/net_port.static b/tests/net_port.static new file mode 100644 index 0000000..9ab492c --- /dev/null +++ b/tests/net_port.static @@ -0,0 +1,15 @@ +# Equivalent of net,port +saddr dport key +a 10.0.0.0-10.255.255.251 22 42 +a 192.168.1.1 1024 666 +a 10.0.0.0-10.0.0.10 80-82 8 +a 192.168.1.0/24 5000-6000 10 +a 8.8.8.0/24 222 66 +d 192.168.1.0/24 5000-6000 10 +a 192.168.1.0/24 5000-6000 10 +l +d 8.8.8.0/24 222 66 +d 192.168.1.0/24 5000-6000 10 +a 192.168.1.0/24 5000-6000 10 +l + diff --git a/tests/net_port.static.packets b/tests/net_port.static.packets new file mode 100644 index 0000000..bb983dd --- /dev/null +++ b/tests/net_port.static.packets @@ -0,0 +1,15 @@ +# KEY BYTES, PACKET_SIZE bytes as decimal or hex will be read, the rest + discarded, packets are zero-padded if less than PACKET_SIZE. KEY is the + expected matching key from the ruleset, 0 if no match is expected +# Key MAC IPv4 DSCP Length ID Flags TTL Checksum Source Destination sport dport +42 0 0 0 0 0 0 0 0 0 0 0 0 0x08 0x00 0x45 0 64 0 1 2 3 0 0 1 0 0 10 0 128 255 10 0 0 1 1 0 0 22 +42 0 0 0 0 0 0 0 0 0 0 0 0 0x08 0x00 0x45 0 64 0 1 2 3 0 0 1 0 0 10 255 255 251 10 0 0 1 1 0 0 22 +42 0 0 0 0 0 0 0 0 0 0 0 0 0x08 0x00 0x45 0 64 0 1 2 3 0 0 1 0 0 10 0 0 0 10 0 0 1 1 0 0 22 +0 0 0 0 0 0 0 0 0 0 0 0 0 0x08 0x00 0x45 0 64 0 1 2 3 0 0 1 0 0 10 255 255 252 10 0 0 1 1 0 0 22 +0 0 0 0 0 0 0 0 0 0 0 0 0 0x08 0x00 0x45 0 64 0 1 2 3 0 0 1 0 0 10 255 255 251 10 0 0 1 1 0 0 23 +666 0 0 0 0 0 0 0 0 0 0 0 0 0x08 0x00 0x45 0 64 0 1 2 3 0 0 1 0 0 192 168 1 1 10 0 0 1 1 0 4 0 +0 0 0 0 0 0 0 0 0 0 0 0 0 0x08 0x00 0x45 0 64 0 1 2 3 0 0 1 0 0 192 168 1 1 10 0 0 1 1 0 4 1 +8 0 0 0 0 0 0 0 0 0 0 0 0 0x08 0x00 0x45 0 64 0 1 2 3 0 0 1 0 0 10 0 0 5 10 0 0 1 1 0 0 81 +10 0 0 0 0 0 0 0 0 0 0 0 0 0x08 0x00 0x45 0 64 0 1 2 3 0 0 1 0 0 192 168 1 2 10 0 0 1 1 0 19 136 +0 0 0 0 0 0 0 0 0 0 0 0 0 0x08 0x00 0x45 0 64 0 1 2 3 0 0 1 0 0 192 168 2 2 10 0 0 1 1 0 19 136 +0 0 0 0 0 0 0 0 0 0 0 0 0 0x08 0x00 0x45 0 64 0 1 2 3 0 0 1 0 0 192 168 1 2 10 0 0 1 1 0 23 113 diff --git a/tests/plot.sh b/tests/plot.sh new file mode 100755 index 0000000..7c4904e --- /dev/null +++ b/tests/plot.sh @@ -0,0 +1,19 @@ +#!/bin/sh + +xmax=200000 +avx=plots/rate_port.data +noavx=plots/rate_noavx2_port.data +nosimd=plots/rate_nosimd_port.data +out=plots/port.png + +gnuplot < +# License: GPLv2 + +check() { + if ! ../pipapo.check ${type}.${size} ${type}.${size}.packets >/dev/null; then + echo " functional test: FAIL at ${type}.${size} ${type}.${size}.packets" + exit 1 + fi + echo " functional test: PASS" +} + +pps() { + s="$(wc -l ${type}.${size})" + s=${s% *} + if [ ${s} -gt 10 ]; then + s=$((s / 10)) + s=$((s * 10)) + fi + + pps="$(../pipapo ${type}.${size} ${type}.${size}.packets | sed -nr 's/.* \((.*) Mpps\)$/\1/p')" + printf "%i %f\n" "${s}" "${pps}" >> plots/rate_${type}.data + echo " matching rate (AVX2): ${pps} Mpps" + + pps="$(../pipapo.noavx2 ${type}.${size} ${type}.${size}.packets | sed -nr 's/.* \((.*) Mpps\)$/\1/p')" + printf "%i %f\n" "${s}" "${pps}" >> plots/rate_noavx2_${type}.data + echo " matching rate (no AVX2): ${pps} Mpps" + + pps="$(../pipapo.nosimd ${type}.${size} ${type}.${size}.packets | sed -nr 's/.* \((.*) Mpps\)$/\1/p')" + printf "%i %f\n" "${s}" "${pps}" >> plots/rate_nosimd_${type}.data + echo " matching rate (no SIMD): ${pps} Mpps" +} + +mem() { + s="$(wc -l ${type}.${size})" + s=${s% *} + if [ ${s} -gt 10 ]; then + s=$((s / 10)) + s=$((s * 10)) + fi + + out="$(../pipapo.mem ${type}.${size} ${type}.${size}.packets | sed -nr 's/^Total: ([0-9].*)((KiB$|MiB$|B$))$/\1 \2/p')" + case ${out} in + *" KiB") + _out=$((${out%% *} * 1024)) + ;; + *" MiB") + _out=$((${out%% *} * 1024 * 1024)) + ;; + *" B") + _out=${out%% *} + ;; + esac + + printf "%i %i\n" "${s}" "${_out}" >> plots/memory_${type}.data + + echo " memory used: $(echo ${out} | tr -d ' ')" +} + +[ -d plots ] || { ./gen.sh && mkdir -p plots; } + +plot() { + title="$(echo ${title} | tr '_' ', ')" + gnuplot < plots/rate_${type}.data + :> plots/rate_noavx2_${type}.data + :> plots/rate_nosimd_${type}.data + :> plots/memory_${type}.data + done + + for size in single tiny small mid big huge; do + echo " - size: ${size}" + check + pps + mem + done + + plot + + echo +done + +for test in *.static; do + echo "=== TEST: ${test}" + type="${test%*.static}" + :> plots/rate_${type}.data + :> plots/rate_noavx2_${type}.data + :> plots/rate_nosimd_${type}.data + :> plots/memory_${type}.data + size="static" + + check + pps + mem + + echo +done + +exit 0 diff --git a/util.c b/util.c new file mode 100644 index 0000000..f1d4538 --- /dev/null +++ b/util.c @@ -0,0 +1,217 @@ +/* PIPAPO - PIle PAcket POlicies + * + * util.c - Convenience routines + * + * Author: Stefano Brivio + * License: GPLv2 + */ + +#include +#include +#include + +#include "pipapo.h" + +/** + * set_bit() - Set single bit in arbitrary-sized word + * @data: Word + * @n: Bit number + * + * Equivalent to set_bit() in kernel. + */ +void set_bit(uint8_t *data, int n) +{ + data[n / 8] |= 1 << (n % 8); +} + +/** + * bit_sum() - Sum bit to arbitrary-sized word with carry + * @v: Word + * @n: Bit number + * @len: Word length + */ +void bit_sum(uint8_t *v, int n, int len) +{ + int carry = 0, i; + + for (i = len - 1 - n / 8; i >= 0; i--) { + if (carry) + v[i]++; + else + v[i] += 1 << (n % 8); + + if (v[i]) + break; + carry = 1; + } +} + +/** + * bit_sub() - Subtract bit from arbitrary-sized word with carry + * @v: Word + * @n: Bit number + * @len: Word length + */ +void bit_sub(uint8_t *v, int n, int len) +{ + int carry = 0, i; + + for (i = len - 1 - n / 8; i >= 0; i--) { + if (carry) + v[i]--; + else + v[i] -= 1 << (n % 8); + + if (v[i] != 0xff) + break; + carry = 1; + } +} + +/** + * andmem() - AND two memory regions + * @dst: First operand and destination + * @src: Second operand + * @len: Length of memory region + * + * Equivalent to bitmap_and() in kernel. + */ +void andmem(uint8_t *dst, uint8_t *src, unsigned len) +{ + while (len >= sizeof(long)) { + *(unsigned long *)dst &= *(unsigned long *)src; + dst += sizeof(long); + src += sizeof(long); + len -= sizeof(long); + } + + while (len >= sizeof(int)) { + *(unsigned int *)dst &= *(unsigned int *)src; + dst += sizeof(int); + src += sizeof(int); + len -= sizeof(int); + } + + while (len--) { + *dst &= *src; + dst++; + src++; + } +} + +/** + * ffs_clear() - Find first bit set in memory region and clear it + * @data: Start of memory region + * @len: Length of memory region + * @offset: Starting offset in byte + * + * Similar purpose as for_each_set_bit_from() in kernel. + * + * Return: position of first set bit, if any, -1 otherwise + */ +int ffs_clear(uint8_t *data, unsigned int len, int byte_offset) +{ + int tmp = 0, n, c = byte_offset; + + data += byte_offset; + len -= byte_offset; + + while (len) { + if (len >= sizeof(long)) { + n = ffsl(*(unsigned long *)data); + if (n--) { + *((unsigned long *)data) &= ~(1UL << n); + return n + c * 8; + } + len -= sizeof(long); + data += sizeof(long); + c += sizeof(long); + } else if (len >= sizeof(int)) { + n = ffs(*(unsigned int *)data); + if (n--) { + *((unsigned int *)data) &= ~(1U << n); + return n + c * 8; + } + len -= sizeof(int); + data += sizeof(int); + c += sizeof(int); + } else { + memcpy(&tmp, data, len); + n = ffs(tmp); + if (n--) { + data[n / 8] &= ~(1U << (n % 8)); + return n + c * 8; + } + return -1; + } + } + + return -1; +} + +/** + * test_bit - Test bit in memory region + * @data: Memory region + * @n: Bit to be tested + * + * Equivalent to test_bit() in kernel. + * + * Return: 1 if bit set, 0 if bit unset. + */ +int test_bit(uint8_t *data, int n) +{ + return !!(data[n / 8] & (1 << (n % 8))); +} + +/** + * fold_bits() - Shift a bitmap region, removing a given amount of bits + * @data: Memory region + * @first: First bit to be removed + * @n: Amount of bits to be removed + * @len: Size of memory region + * + * Similar to bitmap_shift_left() in kernel, *not* equivalent to bitmap_fold(). + * For example, with this bitmap, if start is 7 and n is 4: + * + * 1000 0110 1100 0001 + * | | | | + * 7 0 15 8 + * + * we are removing these four bits: + * + * x000 0110 1100 0xxx + * | | | | + * 7 0 15 8 + * + * resulting in: + * + * 0000 0110 0000 1100 + * | | | | + * 7 0 15 8 + */ +void fold_bits(uint8_t *data, int first, int n, int len) +{ + uint8_t keep, carry; + int i; + + if (first % 8) + keep = data[first / 8] & (0xff >> (8 - first % 8)); + else + keep = 0; + + while (n) { + for (i = first / 8; i < len; i++) { + if (i < len - 1) + carry = data[i + 1] & 0x01; + else + carry = 0; + + data[i] >>= 1; + data[i] |= carry << 7; + } + n--; + } + + data[first / 8] &= 0xff << (first % 8); + data[first / 8] |= keep; +} diff --git a/util.h b/util.h new file mode 100644 index 0000000..94fc0f2 --- /dev/null +++ b/util.h @@ -0,0 +1,110 @@ +#define DIV_ROUND_UP(n, d) (((n) + (d) - 1) / (d)) +#define __round_mask(x, y) ((__typeof__(x))((y)-1)) +#define round_up(x, y) ((((x)-1) | __round_mask(x, y))+1) + +#define min(x, y) (((x) < (y)) ? (x) : (y)) + +#define likely(x) __builtin_expect(!!(x), 1) +#define unlikely(x) __builtin_expect(!!(x), 0) + +#ifdef VERBOSE +#define verbose(...) fprintf(stdout, __VA_ARGS__) +#else +#define verbose(...) do { } while (0) +#endif + +void set_bit(uint8_t *data, int n, int len); +void bit_sum(uint8_t *v, int n, int len); +void bit_sub(uint8_t *v, int n, int len); +void andmem(uint8_t *dst, uint8_t *src, int len); +void ormem(uint8_t *dst, uint8_t *src, int len); +int ffs_clear(uint8_t *data, int len, int byte_offset); +int test_bit(uint8_t *data, int n); +void fold_bits(uint8_t *data, int bit, int n, int len); + +/** + * fill() - Fill bits in given region + * @data: Memory region + * @start: First bit to set + * @len: Number of bits to set + * + * Equivalent to bitmap_set() in kernel. + */ +__always_inline void fill(uint8_t *data, int start, int len) +{ + uint8_t mask; + + data += start / 8; + if (likely(start % 8 || len < 8)) { + if (len + start % 8 < 8) { + mask = 0xff >> (8 - len); + *data |= mask << (start % 8); + return; + } + + *data |= 0xff << (start % 8); + len -= 8 - start % 8; + data++; + + if (len < 8) { + mask = 0xff >> (8 - len); + *data |= mask; + return; + } + } + memset(data, 0xff, len / 8); + data += len / 8; + + if (len %= 8) + *data |= 0xff >> (8 - len); +} + +/** + * ffs_and_fill() - For each set bit, set bits from selected mapping table item + * @map: Bitmap to be scanned for set bits + * @offset: Optional, initial offset, bytes + * @len: Length of bitmap in 64-bit words + * @dst: Destination bitmap + * @mt: Mapping table containing bit set specifiers + * @one: Find a single bit and return, don't fill + * + * Original implementation by Daniel Lemire, public domain. + * + * For each bit set in map, select the bucket from mapping table with index + * corresponding to the position of the bit set. Use start bit and amount of + * bits specified in bucket to fill region in dst. + * + * If __builtin_ctzl() is available, this is vastly more efficient compared to + * looking for bits using ffs64() as we can directly iterate without having to + * return the bit position and clearing it or caching it for each set bit. + * + * If __builtin_ctzl() is not available, ffs_clear() will be used instead. + * + * Return: 0 on match, bit position if 'one' is passed, -1 otherwise. + */ +__always_inline int ffs_and_fill(uint8_t *map, int offset, int len, + uint8_t *dst, union map_bucket *mt, int one) +{ + uint64_t bitset; + int k, ret = -1; + + for (k = offset / 8; k < len; k++) { + bitset = ((uint64_t *)map)[k]; + while (bitset) { + uint64_t t = bitset & -bitset; + int r = __builtin_ctzl(bitset); + + if (unlikely(one)) + return(k * 64 + r); + + ret = 0; + + fill(dst, mt[k * 64 + r].to, mt[k * 64 + r].n); + + bitset ^= t; + } + map[k] = 0; + } + + return ret; +} -- cgit v0.10.2