xref: /dflybsd-src/sys/net/toeplitz.c (revision f8c589f353e45a43e2df3f5435bc3aeeb83f99bc)

/*
 * Copyright (c) 2009 The DragonFly Project.  All rights reserved.
 *
 * This code is derived from software contributed to The DragonFly Project
 * by Sepherosa Ziehau <sepherosa@gmail.com>
 *
 * 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.
 * 3. Neither the name of The DragonFly Project nor the names of its
 *    contributors may be used to endorse or promote products derived
 *    from this software without specific, prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS 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
 * COPYRIGHT HOLDERS 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.
 */

/*
 * Toeplitz hash function
 *
 * This function is used to support Receive Side Scaling:
 * http://www.microsoft.com/whdc/device/network/ndis_rss.mspx
 *
 * Two things are changed from the above paper:
 * o  Instead of creating random 40 bytes key string, we replicate
 *    2 user defined bytes to form the 40 bytes key string.  So the
 *    hash result of TCP segment is commutative.  '2' is chosen,
 *    since the hash is calculated upon the binary string formed by
 *    concatenating faddr,laddr,fport,lport; the smallest unit is
 *    the size of the fport/lport, which is 2 bytes.
 * o  Precalculated hash result cache is used to reduce the heavy
 *    computation burden
 *
 * Thank Simon 'corecode' Schubert <corecode@fs.ei.tum.de> very much
 * for various constructive suggestions.  Without him, this will not
 * be possible.
 */

#include "opt_rss.h"

#include <sys/param.h>
#include <sys/kernel.h>
#include <sys/systm.h>
#include <sys/sysctl.h>

#include <net/toeplitz.h>
#include <net/toeplitz2.h>

#define TOEPLITZ_KEYSEED0	0x6d
#define TOEPLITZ_KEYSEED1	0x5a
#define TOEPLITZ_INIT_KEYLEN	(TOEPLITZ_KEYSEED_CNT + sizeof(uint32_t))

static uint32_t	toeplitz_keyseeds[TOEPLITZ_KEYSEED_CNT] =
	{ TOEPLITZ_KEYSEED0, TOEPLITZ_KEYSEED1 };

uint32_t	toeplitz_cache[TOEPLITZ_KEYSEED_CNT][256];

TUNABLE_INT("net.toeplitz.keyseed0", &toeplitz_keyseeds[0]);
TUNABLE_INT("net.toeplitz.keyseed1", &toeplitz_keyseeds[1]);

SYSCTL_NODE(_net, OID_AUTO, toeplitz, CTLFLAG_RW, 0, "Toeplitz hash");
SYSCTL_INT(_net_toeplitz, OID_AUTO, keyseed0, CTLFLAG_RD,
	   &toeplitz_keyseeds[0], 0, "Toeplitz hash key seed0");
SYSCTL_INT(_net_toeplitz, OID_AUTO, keyseed1, CTLFLAG_RD,
	   &toeplitz_keyseeds[1], 0, "Toeplitz hash key seed1");

static void
toeplitz_cache_create(uint32_t cache[][256], int cache_len,
		      const uint8_t key_str[], int key_strlen)
{
	int i;

	for (i = 0; i < cache_len; ++i) {
		uint32_t key[NBBY];
		int j, b, shift, val;

		bzero(key, sizeof(key));

		/*
		 * Calculate 32bit keys for one byte; one key for each bit.
		 */
		for (b = 0; b < NBBY; ++b) {
			for (j = 0; j < 32; ++j) {
				uint8_t k;
				int bit;

				bit = (i * NBBY) + b + j;

				k = key_str[bit / NBBY];
				shift = NBBY - (bit % NBBY) - 1;
				if (k & (1 << shift))
					key[b] |= 1 << (31 - j);
			}
		}

		/*
		 * Cache the results of all possible bit combination of
		 * one byte.
		 */
		for (val = 0; val < 256; ++val) {
			uint32_t res = 0;

			for (b = 0; b < NBBY; ++b) {
				shift = NBBY - b - 1;
				if (val & (1 << shift))
					res ^= key[b];
			}
			cache[i][val] = res;
		}
	}
}

#ifdef RSS_DEBUG

static void
toeplitz_verify(void)
{
	in_addr_t faddr, laddr;
	in_port_t fport, lport;

	/*
	 * The first IPv4 example in the verification suite
	 */

	/* 66.9.149.187:2794 */
	faddr = 0xbb950942;
	fport = 0xea0a;

	/* 161.142.100.80:1766 */
	laddr = 0x50648ea1;
	lport = 0xe606;

	kprintf("toeplitz: verify addr/port 0x%08x, addr 0x%08x\n",
		toeplitz_rawhash_addrport(faddr, laddr, fport, lport),
		toeplitz_rawhash_addr(faddr, laddr));
}

#endif	/* RSS_DEBUG */

static void
toeplitz_init(void *dummy __unused)
{
	uint8_t key[TOEPLITZ_INIT_KEYLEN];
	int i;

	for (i = 0; i < TOEPLITZ_KEYSEED_CNT; ++i)
		toeplitz_keyseeds[i] &= 0xff;

	toeplitz_get_key(key, TOEPLITZ_INIT_KEYLEN);

#ifdef RSS_DEBUG
	kprintf("toeplitz: keystr ");
	for (i = 0; i < TOEPLITZ_INIT_KEYLEN; ++i)
		kprintf("%02x ", key[i]);
	kprintf("\n");
#endif

	toeplitz_cache_create(toeplitz_cache, TOEPLITZ_KEYSEED_CNT,
			      key, TOEPLITZ_INIT_KEYLEN);

#ifdef RSS_DEBUG
	toeplitz_verify();
#endif
}
/* After netisr_init */
SYSINIT(toeplitz, SI_SUB_PRE_DRIVERS, SI_ORDER_SECOND, toeplitz_init, NULL);

void
toeplitz_get_key(uint8_t *key, int keylen)
{
	int i;

	if (keylen > TOEPLITZ_KEYLEN_MAX)
		panic("invalid key length %d", keylen);

	/* Replicate key seeds to form key */
	for (i = 0; i < keylen; ++i)
		key[i] = toeplitz_keyseeds[i % TOEPLITZ_KEYSEED_CNT];
}