[2/5] example:l3fwd: add forward cache

Message ID 1463662955-1241-1-git-send-email-forrest.shi@linaro.org
State New
Headers show

Commit Message

Forrest Shi May 19, 2016, 1:02 p.m.
From: Xuelin Shi <forrest.shi@linaro.org>

add a lookup cache based on flow hash
before lookup fwd_db, lookup the cache first

Signed-off-by: Xuelin Shi <forrest.shi@linaro.org>
---
 example/l3fwd/odp_l3fwd.c    |  27 +++++++--
 example/l3fwd/odp_l3fwd_db.c | 140 ++++++++++++++++++++++++++++++++++++++++---
 example/l3fwd/odp_l3fwd_db.h |  10 ++--
 3 files changed, 159 insertions(+), 18 deletions(-)

Patch

diff --git a/example/l3fwd/odp_l3fwd.c b/example/l3fwd/odp_l3fwd.c
index 704d33e..5f8eaa0 100644
--- a/example/l3fwd/odp_l3fwd.c
+++ b/example/l3fwd/odp_l3fwd.c
@@ -11,6 +11,8 @@ 
 #include <odp/helper/linux.h>
 #include <odp/helper/eth.h>
 #include <odp/helper/ip.h>
+#include <odp/helper/udp.h>
+#include <odp/helper/tcp.h>
 
 #include "odp_l3fwd_db.h"
 
@@ -105,20 +107,33 @@  static void *run_worker(void *arg ODP_UNUSED)
 			odp_packet_t pkt = pkt_tbl[i];
 			odph_ethhdr_t *eth;
 			odph_ipv4hdr_t *ip;
+			odph_udphdr_t  *udp;
 			uint32_t len;
-			uint32_t dst_ip;
 			fwd_db_entry_t *entry;
 			odp_pktout_queue_t outq;
+			ipv4_tuple5_t key;
 
-			if (odp_unlikely(!odp_packet_has_l3(pkt))) {
-				printf("warning: packet has no ip header\n");
+			if (odp_unlikely(!odp_packet_has_ipv4(pkt))) {
+				printf("warning: packet has no ipv4 header\n");
 				return NULL;
 			}
 
 			/*TODO: ipv6 need to be done */
 			ip = (odph_ipv4hdr_t *)odp_packet_l3_ptr(pkt, &len);
-			dst_ip = odp_be_to_cpu_32(ip->dst_addr);
-			entry = find_fwd_db_entry(dst_ip);
+			key.dst_ip = odp_be_to_cpu_32(ip->dst_addr);
+			key.src_ip = odp_be_to_cpu_32(ip->src_addr);
+			key.proto = ip->proto;
+			if (odp_packet_has_udp(pkt) ||
+			    odp_packet_has_tcp(pkt)) {
+				/* UDP or TCP*/
+				void *ptr = odp_packet_l4_ptr(pkt, NULL);
+
+				udp = (odph_udphdr_t *)ptr;
+				key.src_port = odp_be_to_cpu_16(udp->src_port);
+				key.dst_port = odp_be_to_cpu_16(udp->dst_port);
+			}
+
+			entry = find_fwd_db_entry(&key);
 			if (!entry) {
 				pkt_tbl_drop[need_to_drop] = pkt;
 				need_to_drop++;
@@ -130,6 +145,8 @@  static void *run_worker(void *arg ODP_UNUSED)
 				return NULL;
 			}
 
+			ip->ttl--;
+			ip->chksum = odph_ipv4_csum_update(pkt);
 			eth = (odph_ethhdr_t *)odp_packet_l2_ptr(pkt, NULL);
 			memcpy(eth->src.addr, entry->src_mac, ODPH_ETHADDR_LEN);
 			memcpy(eth->dst.addr, entry->dst_mac, ODPH_ETHADDR_LEN);
diff --git a/example/l3fwd/odp_l3fwd_db.c b/example/l3fwd/odp_l3fwd_db.c
index 2140cca..7fde4ae 100644
--- a/example/l3fwd/odp_l3fwd_db.c
+++ b/example/l3fwd/odp_l3fwd_db.c
@@ -22,15 +22,14 @@ 
  * Compute hash value from a flow
  */
 static inline
-uint64_t odp_l3fwd_calc_hash(ipv4_tuple5_t *flow)
+uint64_t odp_l3fwd_calc_hash(ipv4_tuple5_t *key)
 {
 	uint64_t l4_ports = 0;
-	ipv4_tuple5_t key;
+	uint32_t dst_ip, src_ip;
 
-	key = *flow;
-
-	key.dst_ip += JHASH_GOLDEN_RATIO;
-	ODP_BJ3_MIX(key.src_ip, key.dst_ip, l4_ports);
+	src_ip = key->src_ip;
+	dst_ip = key->dst_ip + JHASH_GOLDEN_RATIO;
+	ODP_BJ3_MIX(src_ip, dst_ip, l4_ports);
 
 	return l4_ports;
 }
@@ -157,6 +156,118 @@  char *mac_addr_str(char *b, uint8_t *mac)
 	return b;
 }
 
+/**
+ * Flow cache table entry
+ */
+typedef struct flow_entry_s {
+	ipv4_tuple5_t key;		/**< match key */
+	struct flow_entry_s *next;      /**< next entry on the list */
+	fwd_db_entry_t *fwd_entry;	/**< entry info in db */
+} flow_entry_t;
+
+/**
+ * Flow cache table bucket
+ */
+typedef struct flow_bucket_s {
+	odp_spinlock_t		lock;	/**< Bucket lock*/
+	flow_entry_t		*next;	/**< Pointer to first flow entry in bucket*/
+} flow_bucket_t;
+
+/**
+ * Flow hash table, fast lookup cache
+ */
+typedef struct flow_table_s {
+	flow_bucket_t *bucket;
+	uint32_t count;
+} flow_table_t;
+
+static flow_table_t fwd_lookup_cache;
+
+static inline
+void init_fwd_cache(void)
+{
+	odp_shm_t		hash_shm;
+	flow_bucket_t		*bucket;
+	uint32_t		bucket_count;
+	uint32_t		i;
+
+	bucket_count = ODP_DEF_BUCKET_COUNT;
+
+	/*Reserve memory for Routing hash table*/
+	hash_shm = odp_shm_reserve("route_table",
+				   sizeof(flow_bucket_t) * bucket_count,
+				   ODP_CACHE_LINE_SIZE, 0);
+
+	bucket = odp_shm_addr(hash_shm);
+	if (!bucket) {
+		EXAMPLE_ERR("Error: shared mem alloc failed.\n");
+		exit(-1);
+	}
+
+	fwd_lookup_cache.bucket = bucket;
+	fwd_lookup_cache.count = bucket_count;
+
+	/*Inialize Locks*/
+	for (i = 0; i < bucket_count; i++) {
+		bucket = &fwd_lookup_cache.bucket[i];
+		odp_spinlock_init(&bucket->lock);
+		bucket->next = NULL;
+	}
+}
+
+static inline
+int match_key_flow(ipv4_tuple5_t *key, flow_entry_t *flow)
+{
+	if (key->src_ip == flow->key.src_ip &&
+	    key->dst_ip == flow->key.dst_ip &&
+	    key->src_port == flow->key.src_port &&
+	    key->dst_port == flow->key.dst_port &&
+	    key->proto == flow->key.proto)
+		return 1;
+
+	return 0;
+}
+
+static inline
+flow_entry_t *lookup_fwd_cache(ipv4_tuple5_t *key, flow_bucket_t *bucket)
+{
+	flow_entry_t *rst;
+
+	for (rst = bucket->next; rst != NULL; rst = rst->next) {
+		if (match_key_flow(key, rst))
+			break;
+	}
+
+	return rst;
+}
+
+static inline
+flow_entry_t *insert_fwd_cache(ipv4_tuple5_t *key,
+			       flow_bucket_t *bucket,
+			       fwd_db_entry_t *entry)
+{
+	flow_entry_t *flow;
+
+	flow = lookup_fwd_cache(key, bucket);
+	if (flow)
+		return flow;
+
+	flow = malloc(sizeof(flow_entry_t));
+	flow->key = *key;
+	flow->fwd_entry = entry;
+
+	odp_spinlock_lock(&bucket->lock);
+	if (!bucket->next) {
+		bucket->next = flow;
+	} else {
+		flow->next = bucket->next;
+		bucket->next = flow;
+	}
+	odp_spinlock_unlock(&bucket->lock);
+
+	return flow;
+}
+
 /** Global pointer to fwd db */
 fwd_db_t *fwd_db;
 
@@ -176,6 +287,8 @@  void init_fwd_db(void)
 		exit(EXIT_FAILURE);
 	}
 	memset(fwd_db, 0, sizeof(*fwd_db));
+
+	init_fwd_cache();
 }
 
 int create_fwd_db_entry(char *input)
@@ -287,12 +400,23 @@  void dump_fwd_db(void)
 		dump_fwd_db_entry(entry);
 }
 
-fwd_db_entry_t *find_fwd_db_entry(uint32_t dst_ip)
+fwd_db_entry_t *find_fwd_db_entry(ipv4_tuple5_t *key)
 {
 	fwd_db_entry_t *entry;
+	flow_entry_t *flow;
+	flow_bucket_t *bucket;
+	uint64_t hash;
+
+	/* first find in cache */
+	hash = odp_l3fwd_calc_hash(key);
+	hash &= fwd_lookup_cache.count - 1;
+	bucket = &fwd_lookup_cache.bucket[hash];
+	flow = lookup_fwd_cache(key, bucket);
+	if (flow)
+		return flow->fwd_entry;
 
 	for (entry = fwd_db->list; NULL != entry; entry = entry->next)
-		if (entry->subnet.addr == (dst_ip & entry->subnet.mask))
+		if (entry->subnet.addr == (key->dst_ip & entry->subnet.mask))
 			break;
 
 	return entry;
diff --git a/example/l3fwd/odp_l3fwd_db.h b/example/l3fwd/odp_l3fwd_db.h
index bd27b2a..c632f5b 100644
--- a/example/l3fwd/odp_l3fwd_db.h
+++ b/example/l3fwd/odp_l3fwd_db.h
@@ -21,12 +21,12 @@  extern "C" {
 /**
  * Default number of flows
  */
-#define ODP_MAX_FLOW_COUNT		100000
+#define ODP_DEF_FLOW_COUNT		100000
 
 /**
  * Default Hash bucket number
  */
-#define ODP_MAX_BUCKET_COUNT	(ODP_MAX_FLOW_COUNT / 8)
+#define ODP_DEF_BUCKET_COUNT	(ODP_DEF_FLOW_COUNT / 8)
 
 /**
  * Hash calculation utility
@@ -75,7 +75,7 @@  typedef struct fwd_db_entry_s {
 } fwd_db_entry_t;
 
 /**
- * Forwarding data base hash structure
+ * Forwarding data base
  */
 typedef struct fwd_db_s {
 	uint32_t          index;          /**< Next available entry */
@@ -124,11 +124,11 @@  void dump_fwd_db(void);
 /**
  * Find a matching forwarding database entry
  *
- * @param dst_ip  Destination IPv4 address
+ * @param key  ipv4 tuple
  *
  * @return pointer to forwarding DB entry else NULL
  */
-fwd_db_entry_t *find_fwd_db_entry(uint32_t dst_ip);
+fwd_db_entry_t *find_fwd_db_entry(ipv4_tuple5_t *key);
 
 #ifdef __cplusplus
 }