summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--Makefile78
-rw-r--r--README16
-rw-r--r--avx2.h355
-rw-r--r--match.c284
-rw-r--r--match.h24
-rw-r--r--pipapo.c1093
-rw-r--r--pipapo.h141
-rw-r--r--set.c902
-rw-r--r--set.h43
-rwxr-xr-xtests/gen.sh214
-rw-r--r--tests/mac_mac_addr_addr_port_port.static204
-rw-r--r--tests/mac_mac_addr_addr_port_port.static.packets7
-rw-r--r--tests/net_port.static15
-rw-r--r--tests/net_port.static.packets15
-rwxr-xr-xtests/plot.sh19
-rwxr-xr-xtests/run.sh119
-rw-r--r--util.c217
-rw-r--r--util.h110
18 files changed, 3856 insertions, 0 deletions
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 <sbrivio@redhat.com>
+ * License: GPLv2
+ */
+
+#include <immintrin.h>
+#include <stdint.h>
+
+#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 <sbrivio@redhat.com>
+ * License: GPLv2
+ */
+
+#include <stdio.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "pipapo.h"
+#include "util.h"
+#include "set.h"
+#include "match.h"
+
+#ifdef MATCH_AVX2
+#include "avx2.h"
+#endif
+
+/**
+ * match_init() - Initialise equivalent of matching data representation
+ * @s: Set data
+ * @layout: Set layout
+ *
+ * This conceptually corresponds to the creation of in-kernel matching data.
+ *
+ * Return: 0 on success, NULL on failure
+ */
+struct kernel_set *kernel_init(struct set *s, struct desc_spec **layout)
+{
+ struct kernel_set *ks;
+ struct field *f;
+ int i;
+
+ ks = calloc(sizeof(*ks), 1);
+ if (!ks)
+ return NULL;
+
+ for_each_field(f, s, layout) {
+ ks->offset[i] = f->offset;
+ ks->groups[i] = f->groups;
+ ks->bsize[i] = f->bsize;
+#ifdef MATCH_AVX2
+ ks->lt[i] = aligned_alloc(32, f->groups * f->bsize * BUCKETS);
+#else
+ ks->lt[i] = malloc(f->groups * f->bsize * BUCKETS);
+#endif
+ memcpy(ks->lt[i], f->lt, f->groups * f->bsize * BUCKETS);
+
+#ifdef MATCH_CTZL
+ ks->mt[i] = aligned_alloc(8, f->rules * sizeof(*ks->mt[i]));
+#else
+ ks->mt[i] = malloc(f->rules * sizeof(*ks->mt[i]));
+#endif
+ memcpy(ks->mt[i], f->mt, f->rules * sizeof(*ks->mt[i]));
+
+ if (f->bsize > ks->max_bsize)
+ ks->max_bsize = f->bsize;
+ }
+ ks->groups[i] = 0;
+
+#ifdef MATCH_AVX2
+ ks->map[0] = aligned_alloc(32, round_up(ks->max_bsize, 32));
+ ks->map[1] = aligned_alloc(32, round_up(ks->max_bsize, 32));
+ memset(ks->map[0], 0, ks->max_bsize);
+ memset(ks->map[1], 0, ks->max_bsize);
+#else
+ ks->map[0] = calloc(ks->max_bsize, 1);
+ ks->map[1] = calloc(ks->max_bsize, 1);
+#endif
+
+ return ks;
+}
+
+#if defined(VERBOSE) && !defined(MATCH_UNROLLED) && !defined(MATCH_AVX2)
+/**
+ * show_match() - Show bucket and bitmap result for a single matching step
+ * @res: Resulting bitmap to be displayed
+ * @group_lt: Pointer to lookup table row for current bit group
+ * @v: Value of packet bytes for current group
+ * @bsize: Lookup bucket size, in bytes
+ *
+ * For documentation purposes only: this shows algorithm step 4.3 in detail.
+ */
+static void show_match(uint8_t *res, uint8_t *group_lt, int v, int bsize)
+{
+ uint8_t *bucket = group_lt + v * bsize;
+ int i;
+
+ fprintf(stdout, " bucket: ");
+ for (i = 0; i < bsize; i++)
+ fprintf(stdout, "%02x ", bucket[i]);
+ fprintf(stdout, "(value: %i)\n", v);
+
+ fprintf(stdout, " result: ");
+ for (i = 0; i < bsize; i++)
+ fprintf(stdout, "%02x ", res[i]);
+ fprintf(stdout, "\n\n");
+}
+#else
+#define show_match(...) do { } while (0)
+#endif
+
+#ifdef VERBOSE
+/**
+ * show_field() - Show field packet bytes and initial bitmap for given field
+ * @f: Index of current field in set
+ * @pkt: Packet bytes for this field
+ * @init: Initial bitmap
+ * @bsize: Lookup bucket size, in bytes
+ *
+ * For documentation purposes only: this shows algorithm steps 4.1 and 4.2.
+ */
+static void show_field(int f, uint8_t *pkt, int len, uint8_t *init, int bsize)
+{
+ int i;
+
+ fprintf(stdout, "\nField %i, packet bytes:", f);
+ for (i = 0; i < len; i++)
+ fprintf(stdout, " %02x", pkt[i]);
+
+ fprintf(stdout, ", initial bitmap:");
+ for (i = 0; i < bsize; i++)
+ fprintf(stdout, " %02x", init[i]);
+ fprintf(stdout, "\n\n");
+}
+#else
+#define show_field(...) do { } while (0)
+#endif
+
+/* Provide explicitly unrolled versions for lookup steps: the compiler doesn't
+ * know that only some group sizes make sense. This speeds up non-AVX2 matching.
+ */
+#define MATCH_REPEAT_4(x) \
+ andmem(map[idx], lt + (x + 0 + (*pkt_p >> 4)) * ks->bsize[f], \
+ ks->bsize[f]); \
+ andmem(map[idx], lt + (x + 16 + (*pkt_p & 0x0f)) * ks->bsize[f], \
+ ks->bsize[f]); \
+ pkt_p++; \
+ andmem(map[idx], lt + (x + 32 + (*pkt_p >> 4)) * ks->bsize[f], \
+ ks->bsize[f]); \
+ andmem(map[idx], lt + (x + 48 + (*pkt_p & 0x0f)) * ks->bsize[f], \
+ ks->bsize[f]); \
+ pkt_p++;
+
+#define MATCH_REPEAT_8(x) \
+ MATCH_REPEAT_4(x) \
+ MATCH_REPEAT_4(x + 64)
+
+#define MATCH_REPEAT_12 \
+ MATCH_REPEAT_8(0) \
+ MATCH_REPEAT_4(128)
+
+#define MATCH_REPEAT_32 \
+ MATCH_REPEAT_8(0) \
+ MATCH_REPEAT_8(128) \
+ MATCH_REPEAT_8(256) \
+ MATCH_REPEAT_8(384)
+
+/**
+ * match() - Equivalent of in-kernel matching implementation
+ * @ks: Kernel representation of set data
+ * @packet: Packet bytes
+ *
+ * This conceptually corresponds to the in-kernel matching function, and it
+ * implements algorithm steps 4.1 to 4.5.
+ *
+ * Return: matched key if any, 0 otherwise
+ */
+uint32_t match(struct kernel_set *ks, uint8_t *packet)
+{
+ int f, g, b, match = 0, offset, idx = ks->map_idx;
+ uint8_t *pkt_p, *lt, v, **map = ks->map;
+
+ (void)g;
+ (void)v;
+ (void)offset;
+ (void)match;
+
+#ifndef MATCH_AVX2
+ /* AVX2 implementation loads all matching buckets first, so an explicit
+ * initial all-ones bitmap isn't needed.
+ */
+ memset(map[idx], 0xff, ks->max_bsize);
+#endif
+
+ /* Go through each set field */
+ for (f = 0; ks->groups[f]; f++) {
+ lt = ks->lt[f];
+ pkt_p = packet + ks->offset[f];
+
+ show_field(f, pkt_p, ks->groups[f] / 2, map[idx], ks->bsize[f]);
+
+ /* For each 4-bit group, select lookup table bucket depending on
+ * packet bytes value, AND bucket values (steps 4.1 - 4.3).
+ */
+#ifdef MATCH_UNROLLED
+ if (ks->groups[f] == 4) {
+ MATCH_REPEAT_4(0);
+ } else if (ks->groups[f] == 8) {
+ MATCH_REPEAT_8(0);
+ } else if (ks->groups[f] == 12) {
+ MATCH_REPEAT_12;
+ } else if (ks->groups[f] == 32) {
+ MATCH_REPEAT_32;
+ }
+#elif defined(MATCH_AVX2)
+ match = avx2_lookup(map[idx], lt, pkt_p, ks->groups[f],
+ ks->bsize[f], f == 0, !ks->groups[f + 1]);
+ if (match < 0) {
+ ks->map_idx = idx;
+ return 0;
+ }
+#else /* !MATCH_UNROLLED && !MATCH_AVX2 */
+ for (g = 0; g < ks->groups[f]; g++) {
+ if (g % 2) {
+ v = *pkt_p & 0x0f;
+ pkt_p++;
+ } else {
+ v = *pkt_p >> 4;
+ }
+ andmem(map[idx], lt + v * ks->bsize[f], ks->bsize[f]);
+ show_match(map[idx], lt, v, ks->bsize[f]);
+ lt += ks->bsize[f] * BUCKETS;
+ }
+#endif
+
+ /* Now populate the bitmap for the next field, unless this is
+ * the last field, in which case return the matched key if any
+ * (steps 4.4 - 4.5). Now map[idx] contains the matching bitmap,
+ * and map[!idx] is the bitmap for the next field.
+ *
+ * If we used the AVX2-based lookup, and this is the last field,
+ * we can already give ffs_and_fill() a hint about the position
+ * of the first bit set: that won't be before a 'match' offset.
+ */
+#ifdef MATCH_CTZL
+ b = ffs_and_fill(map[idx], match, ks->bsize[f] / 8, map[!idx],
+ ks->mt[f], !ks->groups[f + 1]);
+ if (b < 0) {
+ ks->map_idx = idx;
+ return 0;
+ }
+ if (!ks->groups[f + 1]) {
+ /* Last field: we're just returning the key without
+ * filling the next bitmap, so _map[!idx]_ is clear and
+ * can be reused as *next* bitmap (not initial) for the
+ * next packet.
+ */
+ ks->map_idx = idx;
+ return ks->mt[f][b].key;
+ }
+#else
+ offset = match = 0;
+ while ((b = ffs_clear(map[idx], ks->bsize[f], offset)) >= 0) {
+ if (!ks->groups[f + 1]) {
+ ks->map_idx = !idx;
+ return ks->mt[f][b].key;
+ }
+
+ offset = b / (sizeof(int) * 8);
+ match = 1;
+ verbose(" map bit %i: fill %i bit%s from %i\n", b,
+ ks->mt[f][b].n, ks->mt[f][b].n == 1 ? "" : "s",
+ ks->mt[f][b].to);
+ fill(map[!idx], ks->mt[f][b].to, ks->mt[f][b].n);
+ }
+
+ if (!match) {
+ ks->map_idx = !idx;
+ return 0;
+ }
+#endif
+ /* Swap bitmap indices: map[!idx] will be the initial bitmap,
+ * and map[idx] is guaranteed to be all-zeroes at this point.
+ */
+ idx = !idx;
+ }
+
+ return 0;
+}
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 <sbrivio@redhat.com>
+ * 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 <stdio.h>
+#include <arpa/inet.h>
+#include <stdint.h>
+#include <string.h>
+#include <stdlib.h>
+#include <errno.h>
+#include <time.h>
+
+#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 <ruleset> <packets>\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 <sbrivio@redhat.com>
+ * License: GPLv2
+ */
+
+#include <arpa/inet.h>
+#include <errno.h>
+#include <stdio.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+
+#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 <sbrivio@redhat.com>
+# 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 <<EOF
+ set terminal pngcairo size 600,400 enhanced font 'Lucida Sans,10' rounded
+ set logscale x
+ set xlabel "Entries for each field"
+ set ylabel "Mpps"
+ set title 'Single port'
+ set grid
+ set key right top
+ set output '${out}'
+ plot '${avx}' w l ls 1 t 'AVX2', '${noavx}' w l ls 2 t 'No AVX2', '${nosimd}' w l ls 3 t 'No SIMD'
+EOF
diff --git a/tests/run.sh b/tests/run.sh
new file mode 100755
index 0000000..2b32f2a
--- /dev/null
+++ b/tests/run.sh
@@ -0,0 +1,119 @@
+#!/bin/sh -e
+#
+# PIPAPO - PIle PAcket POlicies
+#
+# tests/run.sh - Run functional and performance tests, plot matching rates
+#
+# Author: Stefano Brivio <sbrivio@redhat.com>
+# 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 <<EOF
+ set terminal pngcairo size 600,400 enhanced font 'Lucida Sans,10' rounded
+ set logscale x
+ set xlabel "Entries for each field"
+ set ylabel "Mpps"
+ set title '${title}'
+ set grid
+ set key right top
+ set output 'plots/${type}.png'
+ plot 'plots/rate_${type}.data' w l ls 1 t 'AVX2', 'plots/rate_noavx2_${type}.data' w l ls 2 t 'No AVX2', 'plots/rate_nosimd_${type}.data' w l ls 3 t 'No SIMD'
+EOF
+}
+
+for type in port net_port net_port_ranged mac_net6_ranged; do
+ echo "=== TEST: ${type}"
+ for size in single tiny small mid big huge; do
+ :> 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 <sbrivio@redhat.com>
+ * License: GPLv2
+ */
+
+#include <stdint.h>
+#include <string.h>
+#include <strings.h>
+
+#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;
+}
generated by cgit v0.10.2 at 2024-11-21 08:48:51 (GMT)