/*-
* 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",
¶ms->step,
.default_val = 256,
.min = 1, .max = INT_MAX
},
{
"gc.interval_min",
¶ms->interval_min,
.default_val = 50, // ms
.min = 10, .max = 10000
},
{
"gc.interval_max",
¶ms->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);
}
}