path: root/match.c

/* 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;
}