Re: Extensible hashing and RCU

[Evgeniy Polyakov <johnpol@2ka.mipt.ru>]

[-- Attachment #1: Type: text/plain, Size: 189 bytes --]

On Tue, Feb 20, 2007 at 07:59:07PM +0300, Evgeniy Polyakov (johnpol@2ka.mipt.ru) wrote:
> I've attached source code and running script.
> $ ./run.sh

Yep, of course.

-- 
	Evgeniy Polyakov

[-- Attachment #2: test.c --]
[-- Type: text/plain, Size: 2308 bytes --]

#include <stdlib.h>
#include <stdio.h>
#include <errno.h>
#include <string.h>
#include <unistd.h>
#include <time.h>

#include <arpa/inet.h>

typedef unsigned int u32;
typedef unsigned short u16;
typedef unsigned char u8;

typedef unsigned int __u32;
typedef unsigned short __u16;
typedef unsigned char __u8;

#include "jhash.h"

struct hash_entry
{
	unsigned long		counter;
};

static inline __u32 num2ip(__u8 a1, __u8 a2, __u8 a3, __u8 a4)
{
	__u32 a = 0;

	a |= a1;
	a <<= 8;
	a |= a2;
	a <<= 8;
	a |= a3;
	a <<= 8;
	a |= a4;

	return a;
}

static inline __u8 get_random_byte(void)
{
	return 1 + (int) (255.0 * (rand() / (RAND_MAX + 1.0)));
}

static inline __u16 get_random_word(void)
{
	return 1 + (int) (65536.0 * (rand() / (RAND_MAX + 1.0)));
}

unsigned int hash_addr1(__u32 faddr, __u16 fport, __u32 laddr, __u16 lport)
{
	unsigned int h = (laddr ^ lport) ^ (faddr ^ fport);
	h ^= h >> 16;
	h ^= h >> 8;
	return h;
}

unsigned int hash_addr(__u32 faddr, __u16 fport, __u32 laddr, __u16 lport)
{
	u32 ports;
	unsigned int h;

	ports = lport;
	ports <<= 16;
	ports |= fport;

	h = jhash_3words(faddr, laddr, ports, 123123);
#ifdef HASH_FOLD
	h ^= h >> 16;
	h ^= h >> 8;
#endif
	return h;
}

int main()
{
	struct hash_entry *table;
	__u32 saddr, daddr;
	__u16 sport, dport;
	unsigned int hash, i, *results;
	unsigned int hash_size = (1<<10), iter_num = 100;

	table = malloc(hash_size * sizeof(struct hash_entry));
	if (!table)
		return -ENOMEM;
	
	results = malloc(hash_size * sizeof(unsigned int));
	if (!results)
		return -ENOMEM;

	for (i=0; i<hash_size; ++i) {
		results[i] = 0;
		table[i].counter = 0;
	}

	srand(time(NULL));

	daddr = num2ip(192, 168, 0, 1);
	dport = htons(80);
	saddr = num2ip(192, 168, 0, 2);
	saddr = num2ip(get_random_byte(), get_random_byte(), get_random_byte(), get_random_byte());
	sport = ntohs(10000);
	
	for (i=0; i<hash_size*iter_num; ++i) {
		//sport++;
		sport = get_random_word();

#ifdef USE_XOR
		hash = hash_addr1(saddr, ntohs(sport), daddr, dport);
#else
		hash = hash_addr(saddr, ntohs(sport), daddr, dport);
#endif
		hash &= (hash_size - 1);

		table[hash].counter++;
	}

	for (i=0; i<hash_size; ++i)
		results[table[i].counter]++;
	
	for (i=1; i<hash_size; ++i)
		printf("%u %u\n", i, results[i]);
		//printf("%u %lu\n", i, table[i].counter);
	
	return 0;
}

[-- Attachment #3: run.sh --]
[-- Type: application/x-sh, Size: 414 bytes --]

[-- Attachment #4: artefact.png --]
[-- Type: image/png, Size: 5071 bytes --]

[-- Attachment #5: distribution.png --]
[-- Type: image/png, Size: 9984 bytes --]