aboutsummaryrefslogblamecommitdiffstats
path: root/src/kern_wg.c
blob: 671b8b1b2926e658e19d7fe70cb0ba6a37d3d778 (plain) (tree)





















































































































































































































































































































                                                                                          

                                    















                                                   
                            

                                                                  
















                                                    
/*
 * Copyright (c) 2019 Matt Dunwoodie <ncon@noconroy.net>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#include <sys/param.h>

#include <sys/antireplay.h>
#include <sys/bloombucket.h>
#include <sys/fixedmap.h>
#include <sys/mpq.h>

/*
 * antireplay.h
 */

/*
 * The following defines assist the antireplay_check function. *
 * ANTIREPLAY_INTEGER: the integer in the bitmap corresponding to num *
 * ANTIREPLAY_INTEGERBIT: the integer with corresponding single bit set
 */
#define ANTIREPLAY_INTEGER(ctx, num) (ctx->ar_bitmap[num % ARB_BITS / ARI_BITS])
#define ANTIREPLAY_INTEGERBIT(num) (1llu << (num & (ARI_BITS - 1)))

void
antireplay_init(struct antireplay *ctx)
{
	/* We just zero out the struct, expecting that then ctx->ar_head == 0 */
	explicit_bzero(ctx, sizeof(struct antireplay));
}

int
antireplay_update(struct antireplay *ctx, uint64_t num)
{
	/* Bits after ctx->ar_head need to be zeroed. This is called when num is
	 * in front of ctx->ar_head, and those bits need to be set to 0 */
	if (num < ctx->ar_head + ARB_BITS / ARI_BITS) {
		for (; ctx->ar_head <= num; ctx->ar_head += ARI_BITS) {
			ANTIREPLAY_INTEGER(ctx, (ctx->ar_head + 1)) = 0;
		}
	} else {
		bzero(ctx->ar_bitmap, ARB_BITS / ARI_BITS);
	}

	if (ctx->ar_head > (num + ARB_BITS - ARI_BITS)) {
		/* Expired */
		return 1;
	} else if (ANTIREPLAY_INTEGER(ctx, num) & ANTIREPLAY_INTEGERBIT(num)) {
		/* Replayed */
		return 1;
	} else {
		/* Unseen */
		return 0;
	}
}

/*
 * bloombucket.h
 */

void
bb_init(struct bloom_bucket *bb, size_t size, size_t keys, uint8_t interval,
		uint8_t thresh, int type, int flags)
{
	size_t i;

	for (bb->size = 1; bb->size < size; bb->size <<= 1);

	bb->type = type;
	bb->nkeys = keys;
	bb->thresh = thresh;
	bb->interval = interval;
	bb->keys = mallocarray(bb->nkeys, sizeof(*bb->keys), bb->type, flags);
	bb->bucket = mallocarray(bb->size, 1, bb->type, flags | M_ZERO);

	for (i = 0; i < bb->nkeys; i++)
		arc4random_buf(&bb->keys[i], sizeof(*bb->keys));

	timeout_set(&bb->tick, bb_tick, bb);
}

void
bb_destroy(struct bloom_bucket *bb)
{
	free(bb->keys, bb->type, bb->nkeys);
	free(bb->bucket, bb->type, bb->size);
}

void
bb_tick(void *_bb)
{
	struct bloom_bucket *bb = _bb;
	int act;
	size_t i;

	for (i = 0, act = 0; i < bb->size; i++) {
		/* Check to protect underflow, as well as flag
		 * if action has been taken, therefore should
		 * schedule again. */
		if (bb->bucket[i] > 0) {
			bb->bucket[i]--;
			act = 1;
		}
	}

	if (act && !timeout_pending(&bb->tick))
		timeout_add_sec(&bb->tick, bb->interval);
}

int
bb_recv(struct bloom_bucket *bb, uint8_t *buf, size_t n)
{
	size_t i;
	uint64_t hash;
	uint8_t *elem, min = 0xff;

	for (i = 0; i < bb->nkeys; i++) {
		hash = SipHash24(&bb->keys[i], buf, n);
		elem = &bb->bucket[hash & (bb->size - 1)];
		if (*elem < min)
			min = *elem;
		if (*elem < bb->thresh)
			(*elem)++;
	}

	if (!timeout_pending(&bb->tick))
		timeout_add_sec(&bb->tick, bb->interval);

	return min == bb->thresh;
}

uint8_t
bb_load(struct bloom_bucket *bb)
{
	size_t i;
	uint8_t log;
	uint64_t sum;
	for (i = 0, sum = 0; i < bb->size; i++)
		sum += bb->bucket[i];

	sum *= (0xffffffffffffffff / (bb->size * bb->thresh));

	log = 0;
	while (sum >>= 1)
		log++;

	return log;	
}

/*
 * fixedmap.h
 */

#define FM_SIZE(fm) (1 << (fm)->bits)
#define FM_ITEM(fm, k) ((fm)->map[(k) & ((fm)->bits - 1)])

void
fm_init(struct fixed_map *fm)
{
	rw_init(&fm->lock, "fixed_map");
	fm->bits = 0;
	fm->map = NULL;
}

void
fm_destroy(struct fixed_map *fm)
{
	free(fm->map, M_DEVBUF, 0);
}

void
fm_resize(struct fixed_map *fm, size_t size)
{
	struct map_item *old_map;
	size_t old_size, i;

	if (size <= FM_SIZE(fm))
		return;

	rw_enter_write(&fm->lock);
	old_size = FM_SIZE(fm);
	old_map = fm->map;

	for(fm->bits = 1; size >>= 1; fm->bits++);
	fm->map = mallocarray(FM_SIZE(fm), sizeof(*fm->map), M_DEVBUF, M_WAITOK | M_ZERO);

	if (old_map != NULL) {
		for (i = 0; i < old_size; i++)
			FM_ITEM(fm, old_map[i].key) = old_map[i];
		free(old_map, M_DEVBUF, 0);
	}
	rw_exit_write(&fm->lock);
}

uint32_t
fm_reserve(struct fixed_map *fm)
{
	size_t i;
	struct map_item *item = NULL;

	rw_enter_write(&fm->lock);
	for (i = 0; i < FM_SIZE(fm); i++) {
		if (fm->map[i].state == FM_ITEM_EMPTY) {
			item = &fm->map[i];
			break;
		}
	}

	if (item == NULL)
		panic("unable to find space in fixed map");

	item->key = (arc4random() << fm->bits) + i;
	item->state = FM_ITEM_RESERVED;
	rw_exit_write(&fm->lock);

	return item->key;
}

void
fm_set(struct fixed_map *fm, uint32_t k, void *v)
{
	rw_enter_write(&fm->lock);
	if (FM_ITEM(fm, k).key == k ) {
		FM_ITEM(fm, k).value = v;
		FM_ITEM(fm, k).state = FM_ITEM_FILLED;
	}
	rw_exit_write(&fm->lock);
}

uint32_t
fm_insert(struct fixed_map *fm, void *v)
{
	uint32_t k = fm_reserve(fm);
	fm_set(fm, k, v);
	return k;
}

void *
fm_lookup(struct fixed_map *fm, uint32_t k)
{
	void *v;
	rw_enter_read(&fm->lock);
	v = FM_ITEM(fm, k).key == k ? FM_ITEM(fm, k).value : NULL;
	rw_exit_read(&fm->lock);
	return v;
}

void
fm_remove(struct fixed_map *fm, uint32_t k)
{
	rw_enter_write(&fm->lock);
	if (FM_ITEM(fm, k).key == k) {
		FM_ITEM(fm, k).value = NULL;
		FM_ITEM(fm, k).state = FM_ITEM_EMPTY;
	}
	rw_exit_write(&fm->lock);
}

/*
 * mpq.h
 */

void
mpq_init(struct mpq *mpq, int ipl)
{
	mpq->mpq_cursor = NULL;
	mpq->mpq_serializer = NULL;
	mtx_init(&mpq->mpq_mtx, ipl);
	ml_init(&mpq->mpq_list);
}

int
mpq_serialize_try_enter(struct mpq *mpq)
{
	int error = 1;
	mtx_enter(&mpq->mpq_mtx);
	if (mpq->mpq_serializer == NULL) {
		mpq->mpq_serializer = curcpu();
		error = 0;
	}
	mtx_leave(&mpq->mpq_mtx);
	return error;
}

void
mpq_serialize_leave(struct mpq *mpq)
{
	mtx_enter(&mpq->mpq_mtx);
	mpq->mpq_serializer = NULL;
	mtx_leave(&mpq->mpq_mtx);
}

void
mpq_enqueue(struct mpq *mpq, struct mbuf *m)
{
	/* TODO time based dropping of packets */
	CLR(m->m_flags, M_LINK0);
	mtx_enter(&mpq->mpq_mtx);
	ml_enqueue(&mpq->mpq_list, m);
	if (mpq->mpq_cursor == NULL)
		mpq->mpq_cursor = m;
	mtx_leave(&mpq->mpq_mtx);
}

void
mpq_enlist(struct mpq *mpq, struct mbuf_list *list)
{
	mtx_enter(&mpq->mpq_mtx);
	ml_enlist(&mpq->mpq_list, list);
	mtx_leave(&mpq->mpq_mtx);
}

struct mbuf
*mpq_dethread(struct mpq *mpq)
{
	struct mbuf *m;
	mtx_enter(&mpq->mpq_mtx);
	m = mpq->mpq_cursor;
	if (mpq->mpq_cursor != NULL)
		mpq->mpq_cursor = MBUF_LIST_NEXT(mpq->mpq_cursor);
	mtx_leave(&mpq->mpq_mtx);
	return m;
}

struct mbuf
*mpq_dequeue(struct mpq *mpq)
{
	struct mbuf *m;
	mtx_enter(&mpq->mpq_mtx);
	m = MBUF_LIST_FIRST(&mpq->mpq_list);
	if (m != NULL && ISSET(m->m_flags, M_LINK0))
		m = ml_dequeue(&mpq->mpq_list);
	else
		m = NULL;
	mtx_leave(&mpq->mpq_mtx);
	return m;
}