net/npf/npf_conndb.c

/*-
 * Copyright (c) 2010-2020 The NetBSD Foundation, Inc.
 * All rights reserved.
 *
 * This material is based upon work partially supported by The
 * NetBSD Foundation under a contract with Mindaugas Rasiukevicius.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

/*
 * NPF connection storage.
 *
 * Lock-free connection lookups are protected by EBR with an atomic
 * reference acquisition before exiting the critical path.  The caller
 * is responsible for re-checking the connection state.
 *
 * Warning (not applicable for the userspace npfkern):
 *
 *	thmap is partially lock-free data structure that uses its own
 *	spin-locks on the writer side (insert/delete operations).
 *
 *	The relevant interrupt priority level (IPL) must be set and the
 *	kernel preemption disabled across the critical paths to prevent
 *	deadlocks and priority inversion problems.  These are essentially
 *	the same guarantees as a spinning mutex(9) would provide.
 *
 *	This is achieved with SPL routines splsoftnet() and splx() around
 *	the thmap_del() and thmap_put() calls.  Note: we assume that the
 *	network stack invokes NPF at IPL_SOFTNET or lower, but not higher.
 */

#ifdef _KERNEL
#include <sys/cdefs.h>
__KERNEL_RCSID(0, "$NetBSD: npf_conndb.c,v 1.9 2020/05/30 14:16:56 rmind Exp $");

#include <sys/param.h>
#include <sys/types.h>

#include <sys/atomic.h>
#include <sys/kmem.h>
#include <sys/thmap.h>
#endif

#define __NPF_CONN_PRIVATE
#include "npf_conn.h"
#include "npf_impl.h"

struct npf_conndb {
	thmap_t *		cd_map;

	/*
	 * There are three lists for connections: new, all and G/C.
	 *
	 * New connections are atomically inserted into the "new-list".
	 * The G/C worker will move them to the doubly-linked list of all
	 * active connections.
	 */
	npf_conn_t *		cd_new;
	LIST_HEAD(, npf_conn)	cd_list;
	LIST_HEAD(, npf_conn)	cd_gclist;

	/* The last inspected connection (for circular iteration). */
	npf_conn_t *		cd_marker;
};

typedef struct {
	int		step;
	int		interval_min;
	int		interval_max;
} npf_conndb_params_t;

/*
 * Pointer tag for connection keys which represent the "forwards" entry.
 */
#define	CONNDB_FORW_BIT		((uintptr_t)0x1)
#define	CONNDB_ISFORW_P(p)	(((uintptr_t)(p) & CONNDB_FORW_BIT) != 0)
#define	CONNDB_GET_PTR(p)	((void *)((uintptr_t)(p) & ~CONNDB_FORW_BIT))

void
npf_conndb_sysinit(npf_t *npf)
{
	npf_conndb_params_t *params = npf_param_allocgroup(npf,
	    NPF_PARAMS_CONNDB, sizeof(npf_conndb_params_t));
	npf_param_t param_map[] = {
		{
			"gc.step",
			&params->step,
			.default_val = 256,
			.min = 1, .max = INT_MAX
		},
		{
			"gc.interval_min",
			&params->interval_min,
			.default_val = 50, // ms
			.min = 10, .max = 10000
		},
		{
			"gc.interval_max",
			&params->interval_max,
			.default_val = 5000, // ms
			.min = 10, .max = 10000
		},
	};
	npf_param_register(npf, param_map, __arraycount(param_map));
}

void
npf_conndb_sysfini(npf_t *npf)
{
	const size_t len = sizeof(npf_conndb_params_t);
	npf_param_freegroup(npf, NPF_PARAMS_CONNDB, len);
}

npf_conndb_t *
npf_conndb_create(void)
{
	npf_conndb_t *cd;

	cd = kmem_zalloc(sizeof(npf_conndb_t), KM_SLEEP);
	cd->cd_map = thmap_create(0, NULL, THMAP_NOCOPY);
	KASSERT(cd->cd_map != NULL);

	LIST_INIT(&cd->cd_list);
	LIST_INIT(&cd->cd_gclist);
	return cd;
}

void
npf_conndb_destroy(npf_conndb_t *cd)
{
	KASSERT(cd->cd_new == NULL);
	KASSERT(cd->cd_marker == NULL);
	KASSERT(LIST_EMPTY(&cd->cd_list));
	KASSERT(LIST_EMPTY(&cd->cd_gclist));

	thmap_destroy(cd->cd_map);
	kmem_free(cd, sizeof(npf_conndb_t));
}

/*
 * npf_conndb_lookup: find a connection given the key.
 */
npf_conn_t *
npf_conndb_lookup(npf_t *npf, const npf_connkey_t *ck, npf_flow_t *flow)
{
	npf_conndb_t *cd = atomic_load_relaxed(&npf->conn_db);
	const unsigned keylen = NPF_CONNKEY_LEN(ck);
	npf_conn_t *con;
	void *val;

	/*
	 * Lookup the connection key in the key-value map.
	 */
	int s = npf_config_read_enter(npf);
	val = thmap_get(cd->cd_map, ck->ck_key, keylen);
	if (!val) {
		npf_config_read_exit(npf, s);
		return NULL;
	}

	/*
	 * Determine whether this is the "forwards" or "backwards" key
	 * and clear the pointer tag.
	 */
	*flow = CONNDB_ISFORW_P(val) ? NPF_FLOW_FORW : NPF_FLOW_BACK;
	con = CONNDB_GET_PTR(val);
	KASSERT(con != NULL);

	/*
	 * Acquire a reference and return the connection.
	 */
	atomic_inc_uint(&con->c_refcnt);
	npf_config_read_exit(npf, s);
	return con;
}

/*
 * npf_conndb_insert: insert the key representing the connection.
 *
 * => Returns true on success and false on failure.
 */
bool
npf_conndb_insert(npf_conndb_t *cd, const npf_connkey_t *ck,
    npf_conn_t *con, npf_flow_t flow)
{
	const unsigned keylen = NPF_CONNKEY_LEN(ck);
	const uintptr_t tag = (CONNDB_FORW_BIT * !flow);
	void *val;
	bool ok;

	/*
	 * Tag the connection pointer if this is the "forwards" key.
	 */
	KASSERT(!CONNDB_ISFORW_P(con));
	val = (void *)((uintptr_t)(void *)con | tag);

	int s = splsoftnet();
	ok = thmap_put(cd->cd_map, ck->ck_key, keylen, val) == val;
	splx(s);

	return ok;
}

/*
 * npf_conndb_remove: find and delete connection key, returning the
 * connection it represents.
 */
npf_conn_t *
npf_conndb_remove(npf_conndb_t *cd, npf_connkey_t *ck)
{
	const unsigned keylen = NPF_CONNKEY_LEN(ck);
	void *val;

	int s = splsoftnet();
	val = thmap_del(cd->cd_map, ck->ck_key, keylen);
	splx(s);

	return CONNDB_GET_PTR(val);
}

/*
 * npf_conndb_enqueue: atomically insert the connection into the
 * singly-linked list of the "new" connections.
 */
void
npf_conndb_enqueue(npf_conndb_t *cd, npf_conn_t *con)
{
	npf_conn_t *head;

	do {
		head = atomic_load_relaxed(&cd->cd_new);
		atomic_store_relaxed(&con->c_next, head);
	} while (atomic_cas_ptr(&cd->cd_new, head, con) != head);
}

/*
 * npf_conndb_update: migrate all new connections to the list of all
 * connections; this must also be performed on npf_conndb_getlist()
 * to provide a complete list of connections.
 */
static void
npf_conndb_update(npf_conndb_t *cd)
{
	npf_conn_t *con;

	con = atomic_swap_ptr(&cd->cd_new, NULL);
	while (con) {
		npf_conn_t *next = atomic_load_relaxed(&con->c_next); // union
		LIST_INSERT_HEAD(&cd->cd_list, con, c_entry);
		con = next;
	}
}

/*
 * npf_conndb_getlist: return the list of all connections.
 */
npf_conn_t *
npf_conndb_getlist(npf_conndb_t *cd)
{
	npf_conndb_update(cd);
	return LIST_FIRST(&cd->cd_list);
}

/*
 * npf_conndb_getnext: return the next connection, implementing
 * the circular iteration.
 */
npf_conn_t *
npf_conndb_getnext(npf_conndb_t *cd, npf_conn_t *con)
{
	/* Next.. */
	if (con == NULL || (con = LIST_NEXT(con, c_entry)) == NULL) {
		con = LIST_FIRST(&cd->cd_list);
	}
	return con;
}

/*
 * npf_conndb_gc_incr: incremental G/C of the expired connections.
 */
static unsigned
npf_conndb_gc_incr(npf_t *npf, npf_conndb_t *cd, const time_t now)
{
	const npf_conndb_params_t *params = npf->params[NPF_PARAMS_CONNDB];
	unsigned target = params->step;
	unsigned gc_conns = 0;
	npf_conn_t *con;

	KASSERT(mutex_owned(&npf->conn_lock));

	/*
	 * Second, start from the "last" (marker) connection.
	 * We must initialise the marker if it is not set yet.
	 */
	if ((con = cd->cd_marker) == NULL) {
		con = npf_conndb_getnext(cd, NULL);
		cd->cd_marker = con;
	}

	/*
	 * Scan the connections:
	 * - Limit the scan to the G/C step size.
	 * - Stop if we scanned all of them.
	 * - Update the marker connection.
	 */
	while (con && target--) {
		npf_conn_t *next = npf_conndb_getnext(cd, con);

		/*
		 * Can we G/C this connection?
		 */
		if (npf_conn_expired(npf, con, now)) {
			/* Yes: move to the G/C list. */
			LIST_REMOVE(con, c_entry);
			LIST_INSERT_HEAD(&cd->cd_gclist, con, c_entry);
			npf_conn_remove(cd, con);
			gc_conns++;

			/* This connection cannot be a new marker anymore. */
			if (con == next) {
				next = NULL;
			}
			if (con == cd->cd_marker) {
				cd->cd_marker = next;
				con = next;
				continue;
			}
		}
		con = next;

		/*
		 * Circular iteration: if we returned back to the
		 * marker connection, then stop.
		 */
		if (con == cd->cd_marker) {
			break;
		}
	}
	cd->cd_marker = con;
	return gc_conns;
}

/*
 * gc_freq_tune: G/C frequency self-tuning.
 *
 * If there is something to G/C, then exponentially increase the wake
 * up frequency.  Otherwise, reduce the frequency.  Enforce the lower
 * and upper bounds.
 *
 * => Returns the number milliseconds until next G/C.
 */
static unsigned
gc_freq_tune(const npf_t *npf, const npf_conndb_t *cd, const unsigned n)
{
	const npf_conndb_params_t *params = npf->params[NPF_PARAMS_CONNDB];
	int wtime = npf->worker_wait_time;
	wtime = n ? (wtime >> 1) : (wtime << 1);
	return MAX(MIN(wtime, params->interval_max), params->interval_min);
}

/*
 * npf_conndb_gc: garbage collect the expired connections.
 *
 * => Must run in a single-threaded manner.
 * => If 'flush' is true, then destroy all connections.
 * => If 'sync' is true, then perform passive serialisation.
 */
void
npf_conndb_gc(npf_t *npf, npf_conndb_t *cd, bool flush, bool sync)
{
	struct timespec tsnow;
	unsigned gc_conns = 0;
	npf_conn_t *con;
	void *gcref;

	getnanouptime(&tsnow);

	/* First, migrate all new connections. */
	mutex_enter(&npf->conn_lock);
	npf_conndb_update(cd);
	if (flush) {
		/* Just unlink and move all connections to the G/C list. */
		while ((con = LIST_FIRST(&cd->cd_list)) != NULL) {
			LIST_REMOVE(con, c_entry);
			LIST_INSERT_HEAD(&cd->cd_gclist, con, c_entry);
			npf_conn_remove(cd, con);
		}
		cd->cd_marker = NULL;
	} else {
		/* Incremental G/C of the expired connections. */
		gc_conns = npf_conndb_gc_incr(npf, cd, tsnow.tv_sec);
	}
	mutex_exit(&npf->conn_lock);

	/*
	 * Ensure it is safe to destroy the connections.
	 * Note: drop the conn_lock (see the lock order).
	 */
	gcref = thmap_stage_gc(cd->cd_map);
	if (sync && (gcref || !LIST_EMPTY(&cd->cd_gclist))) {
		npf_config_enter(npf);
		npf_config_sync(npf);
		npf_config_exit(npf);
	}
	thmap_gc(cd->cd_map, gcref);

	/* Self-tune the G/C frequency. */
	npf->worker_wait_time = gc_freq_tune(npf, cd, gc_conns);

	if (LIST_EMPTY(&cd->cd_gclist)) {
		return;
	}

	/*
	 * Garbage collect all expired connections.
	 * May need to wait for the references to drain.
	 */
	while ((con = LIST_FIRST(&cd->cd_gclist)) != NULL) {
		/*
		 * Destroy only if removed and no references.  Otherwise,
		 * just do it next time, unless we are destroying all.
		 */
		const unsigned refcnt = atomic_load_relaxed(&con->c_refcnt);

		if (__predict_false(refcnt)) {
			if (flush) {
				kpause("npfcongc", false, 1, NULL);
				continue;
			}
			break; // exit the loop
		}
		LIST_REMOVE(con, c_entry);
		npf_conn_destroy(npf, con);
	}
}