Skip to content

Commit

Permalink
improvements to ipv4 routing, fix /0
Browse files Browse the repository at this point in the history
  • Loading branch information
@catphish
catphish committed Jan 3, 2018
1 parent f1e6228 commit 2be75ee
Show file tree
Hide file tree
Showing 2 changed files with 136 additions and 133 deletions.
59 changes: 33 additions & 26 deletions router.c
View file
Expand Up @@ -65,8 +65,8 @@ void *thread_main(void * f) {
struct netmap_ring *txring;

// Temporary variables for per-packet data
uint32_t next_hop_ip = 0;
uint8_t next_hop_interface = 1;
uint32_t next_hop_ip;
uint8_t next_hop_interface;

// Pointers for packet data
char *rxbuf;
Expand Down Expand Up @@ -109,31 +109,34 @@ void *thread_main(void * f) {
while (!nm_ring_empty(rxring)) {
// Increment packet count for stats
batch_total++;

// Find the packet in the RX buffer
rxbuf = NETMAP_BUF(rxring, rxring->slot[rxring->cur].buf_idx);
// Assume the frame is an IPv4 packet and perform a lookup
trie_node_search(&t4, rxbuf+30, &next_hop_ip, &next_hop_interface);
// Fetch the appropriate TX ring
txring = txrings[next_hop_interface];

// Check for space in the TX ring
if(nm_ring_space(txring)) {
// Copy the packet length and data from RX to TX
txring->slot[txring->cur].len = rxring->slot[rxring->cur].len;

// Zero-copy buffer swap
uint32_t pkt = rxring->slot[rxring->cur].buf_idx;
rxring->slot[rxring->cur].buf_idx = txring->slot[txring->cur].buf_idx;
txring->slot[txring->cur].buf_idx = pkt;

// Find the buffer buffer in case we want to modify the frame (TTL etc)
txbuf = NETMAP_BUF(txring, txring->slot[txring->cur].buf_idx);

// Advance the TX ring pointer
txring->head = txring->cur = nm_ring_next(txring, txring->cur);
// Assume the frame is an IPv4 packet and perform a lookup
if(trie_node_search(&t4, rxbuf+30, &next_hop_ip, &next_hop_interface)) {
// Fetch the appropriate TX ring
txring = txrings[next_hop_interface];

// Check for space in the TX ring
if(nm_ring_space(txring)) {
// Copy the packet length and data from RX to TX
txring->slot[txring->cur].len = rxring->slot[rxring->cur].len;

// Zero-copy buffer swap
uint32_t pkt = rxring->slot[rxring->cur].buf_idx;
rxring->slot[rxring->cur].buf_idx = txring->slot[txring->cur].buf_idx;
txring->slot[txring->cur].buf_idx = pkt;

// Find the buffer buffer in case we want to modify the frame (TTL etc)
txbuf = NETMAP_BUF(txring, txring->slot[txring->cur].buf_idx);

// Advance the TX ring pointer
txring->head = txring->cur = nm_ring_next(txring, txring->cur);
}
// Mark the TX interface as dirty so it will be flushed
interface_dirty[next_hop_interface] = 1;
}
// Mark the TX interface as dirty so it will be flushed
interface_dirty[next_hop_interface] = 1;
// Advance the RX ring pointer
rxring->head = rxring->cur = nm_ring_next(rxring, rxring->cur);
}
Expand All @@ -148,11 +151,14 @@ int main(int argc, char **argv)

// Populate IPv4 routing table
trie_init(&t4);
uint32_t ip_r;
for(int n=0;n<1000000;n++) { // 1 Million IPs
ip_r = htonl(167772160+n); // 10.0.0.0 + n
uint32_t ip_r = 0;
for(int n=0;n<1000000;n+=2) { // 1 Million IPs
// Insert into IPv4 routing table, next-hop local broadcast (IP 0) to interface 1
ip_r = htonl(167772160+n); // 10.0.0.0 + n
trie_node_put(&t4, (char*)&ip_r, 32, 0, 1);
// Insert into IPv4 routing table, next-hop local broadcast (IP 0) to interface 3
ip_r = htonl(167772160+n+1); // 10.0.0.0 + n + 1
trie_node_put(&t4, (char*)&ip_r, 32, 0, 3);
}

// A struct to hold thread information
Expand All @@ -172,5 +178,6 @@ int main(int argc, char **argv)
for(int n=0; n<RING_COUNT; n++) {
pthread_join(forwarder[n].thread, NULL);
}

return(0);
}
210 changes: 103 additions & 107 deletions trie.c
View file
Expand Up @@ -20,37 +20,37 @@
*/
static node_t *_node_malloc(trie_t *t)
{
node_t *n;
node_t *n;

// add new memory cell
if (t->last == NULL || t->last->ln + 1 == TRIE_MEMORY_CELL_SIZE)
// add new memory cell
if (t->last == NULL || t->last->ln + 1 == TRIE_MEMORY_CELL_SIZE)
{
trie_memory_t *pom = t->last;
t->last = (trie_memory_t *) malloc(sizeof (trie_memory_t));

if (t->last == NULL)
{
trie_memory_t *pom = t->last;
t->last = (trie_memory_t *) malloc(sizeof (trie_memory_t));

if (t->last == NULL)
{
fprintf(stderr, "Cannot allocate memory\n");
exit(EXIT_FAILURE);
}

t->last->ln = 0;
t->last->next = NULL;

if (pom != NULL)
{
pom->next = t->last;
}
fprintf(stderr, "Cannot allocate memory\n");
exit(EXIT_FAILURE);
}
// get node
n = &(t->last->cells[t->last->ln]);
t->last->ln++; // next cell
n->next_hop_ip = 0;
n->next_hop_interface = 0;
n->l = NULL;
n->r = NULL;
// return
return n;

t->last->ln = 0;
t->last->next = NULL;

if (pom != NULL)
{
pom->next = t->last;
}
}
// get node
n = &(t->last->cells[t->last->ln]);
t->last->ln++; // next cell
n->next_hop_ip = 0;
n->next_hop_interface = 0;
n->l = NULL;
n->r = NULL;
// return
return n;
}

/**
Expand All @@ -60,9 +60,9 @@ static node_t *_node_malloc(trie_t *t)
*/
void trie_init(trie_t *t)
{
t->first = t->last = NULL;
t->root = _node_malloc(t);
t->first = t->last;
t->first = t->last = NULL;
t->root = _node_malloc(t);
t->first = t->last;
}

/**
Expand All @@ -72,14 +72,14 @@ void trie_init(trie_t *t)
*/
void trie_destroy(trie_t *t)
{
trie_memory_t *current = t->first, *pom;

while (current != NULL)
{
pom = current->next;
free(current);
current = pom;
}
trie_memory_t *current = t->first, *pom;

while (current != NULL)
{
pom = current->next;
free(current);
current = pom;
}
}

/**
Expand All @@ -93,41 +93,37 @@ void trie_destroy(trie_t *t)
*/
void trie_node_put(trie_t *t, uint8_t *ip, uint8_t cidr, uint32_t next_hop_ip, uint8_t next_hop_interface)
{
node_t *current = t->root;
int i;

// add each bit of address prefix to tree
for (i = 0; i < cidr; i++)
node_t *current = t->root;
int i;

// add each bit of address prefix to tree
for (i = 0; i < cidr; i++)
{
// bit is 1 => go right
if (((ip[i / 8] >> (7 - i % 8)) & 1) > 0)
{
// create path if not exists
if (current->r == NULL)
{
current->r = _node_malloc(t);
}
// next
current = current->r;
}
// bit is 0 => go left
else
{
// bit is 1 => go right
if (((ip[i / 8] >> (7 - i % 8)) & 1) > 0)
{
// create path if not exists
if (current->r == NULL)
{
current->r = _node_malloc(t);
}
// next
current = current->r;
}
// bit is 0 => go left
else
{
// create path if not exists
if (current->l == NULL)
{
current->l = _node_malloc(t);
}
// next
current = current->l;
}
// last bit => add to node
if ((i + 1) == cidr)
{
current->next_hop_ip = next_hop_ip;
current->next_hop_interface = next_hop_interface;
}
// create path if not exists
if (current->l == NULL)
{
current->l = _node_malloc(t);
}
// next
current = current->l;
}
}
current->next_hop_ip = next_hop_ip;
current->next_hop_interface = next_hop_interface;
}

/**
Expand All @@ -142,41 +138,41 @@ void trie_node_put(trie_t *t, uint8_t *ip, uint8_t cidr, uint32_t next_hop_ip, u
*/
uint8_t trie_node_search(trie_t *t, uint8_t *ip, uint32_t *next_hop_ip, uint8_t *next_hop_interface)
{
node_t *current = t->root;
uint8_t found = 0;
uint8_t byte;
int i = 0;
int j;

while(1) {
byte = ip[i++];
for (j=0; j<8; j++)
{
// search right
if (byte & 0x80)
{
current = current->r;
}
// search left
else
{
current = current->l;
}
// end of road
if (current == NULL)
{
return found;
}
// change last network
if (current->next_hop_interface)
{
*next_hop_interface = current->next_hop_interface;
*next_hop_ip = current->next_hop_ip;
found = 1;
}
byte <<= 1;
}
node_t *current = t->root;
uint8_t found = 0;
uint8_t byte;
int i = 0;
int j;

while(1) {
// change last network
if (current->next_hop_interface)
{
*next_hop_interface = current->next_hop_interface;
*next_hop_ip = current->next_hop_ip;
found = 1;
}
byte = ip[i++];
for (j=0; j<8; j++)
{
// search right
if (byte & 0x80)
{
current = current->r;
}
// search left
else
{
current = current->l;
}
// end of road
if (current == NULL)
{
return found;
}
byte <<= 1;
}
}

return found;
return found;
}

0 comments on commit 2be75ee

Please sign in to comment.