path: root/src/routing.c

#include "routing.h"

#include "log.h"
#include "metrics.h"

#include <assert.h>
#include <limits.h>
#include <string.h>
#include <stdbool.h>
#include <stdlib.h>
#include <pthread.h>
#include <arpa/inet.h>
#include <prom_metric_sample_histogram.h>

// The DHT routing table has a keyspace of 0 -- 2^160 split into buckets of 8.
// When a bucket becomes full, we split it in half. As we further expand the
// routing table we only continue to split the buckets on the side we fall on.
//
// Initially, this may sound like a binary tree (because we split it in two),
// but looking at it as a flat array leads to some interesting intuitions.
// Since we only expand one half of the "tree", the total size is bounded by
// the depth of the tree log2(2^160) == 160.
//
// As a flat array we notice the intrinsic properties of the routing table.
// With a bucket size of 8, the routing table contains 160 * 8 == 1280 nodes.
// As the node ids get less similar to our own our grouping of them becomes
// less detailed. While the bucket we are in contains node very close to us,
// the nodes furthest away from us are grouped in buckets with nodes they
// barely resemble.
//
// +----------------------------+
// | n1 | n2 | n3 | ... | n1280 |
// +----------------------------+
//   More                  Less
//  <--------Similarity-------->
//  <----------Detail---------->
//

#include <arpa/inet.h>
struct table {
	struct nodeid myID;
	struct entry table[RT_SIZE];
};

struct table* pTable;

struct nodeid myID;
struct entry *table;
int table_size = RT_SIZE;

void routing_init(struct nodeid* myid) {
	pTable = malloc(sizeof(struct table));
	if(myid != NULL) pTable->myID = *myid;

	table = pTable->table;
	myID = pTable->myID;

	routing_flush();
}

void routing_setid(struct nodeid *id) {
	pTable->myID = *id;
	myID = pTable->myID;
}

void routing_update_metrics() {
	char buf[4]; // Largest value is 157 + \0

	struct entry *entry = pTable->table;
	for(uint8_t i = 0; i < RT_IDBITS-RT_BBITS; i++) {
		sprintf(buf, "%d", i);

		uint8_t filled = 0;
		for(uint8_t j = 0; j < RT_BSIZE; j++) {
			filled += entry->set;
			entry++;
		}

		prom_gauge_set(routing_table_occupied, filled, (const char*[]){buf});
	}
}

void routing_rebuild_table() {
	struct entry table_swap[RT_SIZE];
	memcpy(table_swap, pTable->table, sizeof(pTable->table));
	routing_flush();

	for(size_t i = 0; i < RT_SIZE; i++) {
		if(!table_swap[i].set) continue;

		struct entry *entry;
		if(routing_offer(&table_swap[i].id, &entry)) {
			*entry = table_swap[i];
		} else {
			dbg("Dropping a client since we already have enough in that bucket");
		}
	}
}

void routing_flush() {
	memset(pTable->table, 0, sizeof(pTable->table));
}

// Calculate the common bit prefix between two node ids.
uint8_t prefix(struct nodeid* a, struct nodeid* b) {
	uint8_t c = 0;
	for(uint8_t i = 0; i < 5; i++) {
		// Since the nodeids are stored in host byteorder in the words we have
		// to make sure they're big endian before doing the prefix match,
		// otherwise we end up with prefix matching that's different from the
		// rest of the network
		uint32_t word = htonl(a->inner[i]) ^ htonl(b->inner[i]);

		// This word is different, find the location of the difference
		if (word != 0)
			return c + __builtin_clz(word);

		// This word is completely the same
		c += sizeof(word) * CHAR_BIT;
	}

	return c;
}

static int8_t scan(uint16_t baseIndex, struct nodeid* id) {
	assert(baseIndex < RT_SIZE - RT_BSIZE);
	int8_t index = -2;

	for(size_t i = baseIndex; i < baseIndex + RT_BSIZE; i++) {
		if(!pTable->table[i].set) {
			index = index == -2 ? i - baseIndex : index;
			continue;
		}

		if(memcmp(&pTable->table[i].id, id, sizeof(struct nodeid)) == 0) {
			return -1;
		}
	}
	
	return index;
}

static uint16_t base_bucket(struct nodeid* id) {
	uint16_t bucketIndex = prefix(&pTable->myID, id);
	assert(bucketIndex != RT_IDBITS);

	// If they are sufficiently similar they end up in the final bucket. Clamp the index to ensure.
	bucketIndex = bucketIndex > (RT_IDBITS - RT_BBITS) ? (RT_IDBITS - RT_BBITS) : bucketIndex;
	assert(bucketIndex <= RT_IDBITS - RT_BBITS);

	return bucketIndex * RT_BSIZE;
}

struct entry* routing_get(struct nodeid* id) {
	uint16_t baseIndex = base_bucket(id);
	for(size_t i = baseIndex; i < baseIndex + RT_BSIZE; i++) {
		if(!pTable->table[i].set) continue;

		if(memcmp(&pTable->table[i].id, id, sizeof(struct nodeid)) == 0) {
			return &pTable->table[i];
		}
	}

	return NULL;
}

#if UINT8_MAX > RAND_MAX
#error UINT8_MAX is larger than RAND_MAX
#endif
static uint8_t rand_byte() {
	int limit = (RAND_MAX / UINT8_MAX)*UINT8_MAX;
	int val;
	while((val = rand()) >= limit);

	return val % UINT8_MAX;
}

struct nodeid rand_nodeid_in_bucket(struct nodeid *self, struct nodeid *other) {
	struct nodeid target;
	{
		char *target_byte = (char*)&target;
		for(size_t i = 0; i < sizeof(target); i++) (*target_byte++) = rand_byte();
	}

	uint8_t bucket = prefix(self, other);
	uint8_t byte = bucket / 8;
	uint8_t residual = bucket % 8;

	for(size_t i = 0; i < byte; i++) {
		target.inner_b[i] = self->inner_b[i];
	}
	uint8_t mask = 0xFF >> residual;
	target.inner_b[byte] = (target.inner_b[byte] & mask) | (self->inner_b[byte] & ~mask);

	return target;
}

void routing_remove(struct nodeid* id) {
	struct entry* entry = routing_get(id);

	entry->set = false;
	entry->expire = 0;
    routing_update_metrics();
}

bool routing_interested(struct nodeid* id) {
	uint16_t bucketIndex = prefix(&pTable->myID, id);
	// The nodeid is the same as our own
	if(bucketIndex == RT_IDBITS) {
		return false;
	}
	prom_histogram_observe(offered, bucketIndex, NULL);

	uint16_t baseIndex = base_bucket(id);
	int8_t inBucketIndex = scan(baseIndex, id);

	if(inBucketIndex < 0) {
		// The bucket either already contains the node, or it has no more space
		return false;
	}

	return true;
}

// Offer the routing table a new node
bool routing_offer(struct nodeid* id, struct entry **dest) {
	uint16_t bucketIndex = prefix(&pTable->myID, id);
	// The nodeid is the same as our own
	if(bucketIndex == RT_IDBITS) {
		return false;
	}

	uint16_t baseIndex = base_bucket(id);
	int8_t inBucketIndex = scan(baseIndex, id);

	if(inBucketIndex < 0) {
		// The bucket either already contains the node, or it has no more space
		return false;
	}

	struct entry* entry = &pTable->table[baseIndex + inBucketIndex];
	entry->set = true;
	entry->id = *id;

	*dest = entry;
	return true;
}

struct item {
	struct nodeid distance;
	bool set;
	uint16_t index;
};
int compareItem(const void* a_v, const void* b_v) {
	struct item* a = (struct item*)a_v;
	struct item* b = (struct item*)b_v;

	// If either of the two are not set, the one that is set comes before the
	// one that isn't.
	if(!a->set || !b->set) return b->set - a->set;

	return memcmp(&a->distance, &b->distance, sizeof(struct nodeid));
}

size_t routing_closest(struct nodeid* needle, size_t n, struct entry** res) {
	assert(n <= RT_SIZE);
	static struct item items[RT_SIZE] = {0};
	for(uint16_t i = 0; i < RT_SIZE; i++) {
		items[i].index = i;
	}

	{
		struct item* item;
		struct entry* entry;
		for(item = &items[0], entry = &pTable->table[0]; item < &items[RT_SIZE] && entry < &pTable->table[RT_SIZE]; item++, entry++){
			item->set = entry->set;
			for(uint8_t j = 0; j < 5; j++) {
				item->distance.inner[j] = entry->id.inner[j] ^ needle->inner[j];
			}
		}
	}

	// @PERFORMANCE: There's an algorithm known as quickselect which can select
	// the top k elements from a list while only doing a partial sort.
	// I imagine that would be more efficient than this full sort.
	qsort(items, RT_SIZE, sizeof(struct item), compareItem);

	size_t read;
	for(read = 0; read < n; read++) {
		if(!items[read].set)
			break;
		res[read] = &pTable->table[items[read].index];
	}

	return read;
}

void routing_oldest(struct entry** dest) {
	*dest = NULL;

	for(struct entry* entry = pTable->table; entry < pTable->table+RT_SIZE; entry++){
		if(!entry->set)
			continue;

		if(entry->expire == 0)
			continue;

		if(*dest == NULL) {
			*dest = entry;
			continue;
		}

		if(difftime((*dest)->expire, entry->expire) > 0.0) {
			*dest = entry;
		}
	}
}

void routing_reset_expire(time_t expire) {
	for(struct entry* entry = pTable->table; entry < pTable->table+RT_SIZE; entry++){
		if(!entry->set)
			continue;

		if(entry->expire != 0)
			continue;

		entry->expire = expire;
	}
}

void routing_status(int* filled, int* size, double* load_factor, size_t load_factor_len) {
	*size = RT_SIZE;

	*filled = 0;
	for(size_t i = 0; i < RT_SIZE; i++) {
		if(pTable->table[i].set)
			(*filled)++;
	}

	int per_bucket = RT_SIZE / load_factor_len;
	int overflow = RT_SIZE % load_factor_len;
	struct entry* table_cursor = pTable->table;
	for(int i = 0; i < load_factor_len; i++) {
		int is_overflow = i < overflow;
		for(int j = 0; j < per_bucket + is_overflow; j++) {
			load_factor[i] += table_cursor->set;
			table_cursor++;
		}
		load_factor[i] /= per_bucket + is_overflow;
	}
}