From patchwork Thu Jan 18 18:20:23 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Wang, Yipeng1" X-Patchwork-Id: 863247 X-Patchwork-Delegate: ian.stokes@intel.com Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=openvswitch.org (client-ip=140.211.169.12; helo=mail.linuxfoundation.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver=) Received: from mail.linuxfoundation.org (mail.linuxfoundation.org [140.211.169.12]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 3zN35Y6g3hz9sDB for ; Fri, 19 Jan 2018 12:24:33 +1100 (AEDT) Received: from mail.linux-foundation.org (localhost [127.0.0.1]) by mail.linuxfoundation.org (Postfix) with ESMTP id BD33A10E1; Fri, 19 Jan 2018 01:23:02 +0000 (UTC) X-Original-To: dev@openvswitch.org Delivered-To: ovs-dev@mail.linuxfoundation.org Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 7FCD51005 for ; Fri, 19 Jan 2018 01:22:58 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mga01.intel.com (mga01.intel.com [192.55.52.88]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id E204C419 for ; Fri, 19 Jan 2018 01:22:57 +0000 (UTC) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from fmsmga008.fm.intel.com ([10.253.24.58]) by fmsmga101.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 18 Jan 2018 17:22:56 -0800 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.46,379,1511856000"; d="scan'208";a="11524487" Received: from skx-yipeng.jf.intel.com ([10.54.81.175]) by fmsmga008.fm.intel.com with ESMTP; 18 Jan 2018 17:22:56 -0800 From: Yipeng Wang To: dev@openvswitch.org, jan.scheurich@ericsson.com Date: Thu, 18 Jan 2018 10:20:23 -0800 Message-Id: <1516299624-452546-4-git-send-email-yipeng1.wang@intel.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1516299624-452546-1-git-send-email-yipeng1.wang@intel.com> References: <1516299624-452546-1-git-send-email-yipeng1.wang@intel.com> X-Spam-Status: No, score=-5.4 required=5.0 tests=BAYES_00, DATE_IN_PAST_06_12, RCVD_IN_DNSWL_HI, T_RP_MATCHES_RCVD autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Cc: charlie.tai@intel.com Subject: [ovs-dev] [RFC 3/4] dpif-netdev: Use way-associative cache X-BeenThere: ovs-dev@openvswitch.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Sender: ovs-dev-bounces@openvswitch.org Errors-To: ovs-dev-bounces@openvswitch.org This commit uses a way-associative cache (CD) rather than a simple single entry hash table for DFC. Experiments show that this design generally has much higher hit rate. Since miss is much costly than hit, a CD-like structure that improves hit rate should help in general. Signed-off-by: Yipeng Wang --- lib/dpif-netdev.c | 107 +++++++++++++++++++++++++++++++++++------------------- 1 file changed, 70 insertions(+), 37 deletions(-) diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c index 3e87992..50a1d25 100644 --- a/lib/dpif-netdev.c +++ b/lib/dpif-netdev.c @@ -150,8 +150,10 @@ struct netdev_flow_key { */ #define DFC_MASK_LEN 20 +#define DFC_ENTRY_PER_BUCKET 8 #define DFC_ENTRIES (1u << DFC_MASK_LEN) -#define DFC_MASK (DFC_ENTRIES - 1) +#define DFC_BUCKET_CNT (DFC_ENTRIES / DFC_ENTRY_PER_BUCKET) +#define DFC_MASK (DFC_BUCKET_CNT - 1) #define EMC_MASK_LEN 14 #define EMC_ENTRIES (1u << EMC_MASK_LEN) #define EMC_MASK (EMC_ENTRIES - 1) @@ -171,13 +173,14 @@ struct emc_cache { int sweep_idx; }; -struct dfc_entry { - struct dp_netdev_flow *flow; +struct dfc_bucket { + uint16_t sig[DFC_ENTRY_PER_BUCKET]; + struct dp_netdev_flow *flow[DFC_ENTRY_PER_BUCKET]; }; struct dfc_cache { struct emc_cache emc_cache; - struct dfc_entry entries[DFC_ENTRIES]; + struct dfc_bucket buckets[DFC_BUCKET_CNT]; int sweep_idx; }; @@ -749,9 +752,9 @@ dpif_netdev_xps_revalidate_pmd(const struct dp_netdev_pmd_thread *pmd, static int dpif_netdev_xps_get_tx_qid(const struct dp_netdev_pmd_thread *pmd, struct tx_port *tx); -static inline bool dfc_entry_alive(struct dfc_entry *ce); +static inline bool dfc_entry_alive(struct dp_netdev_flow *flow); static void emc_clear_entry(struct emc_entry *ce); -static void dfc_clear_entry(struct dfc_entry *ce); +static void dfc_clear_entry(struct dfc_bucket *b, int idx); static void dp_netdev_request_reconfigure(struct dp_netdev *dp); @@ -774,11 +777,13 @@ emc_cache_init(struct emc_cache *emc) static void dfc_cache_init(struct dfc_cache *flow_cache) { - int i; + int i, j; emc_cache_init(&flow_cache->emc_cache); - for (i = 0; i < ARRAY_SIZE(flow_cache->entries); i++) { - flow_cache->entries[i].flow = NULL; + for (i = 0; i < DFC_BUCKET_CNT; i++) { + for (j = 0; j < DFC_ENTRY_PER_BUCKET; j++) { + flow_cache->buckets[i].flow[j] = NULL; + } } flow_cache->sweep_idx = 0; } @@ -796,10 +801,12 @@ emc_cache_uninit(struct emc_cache *emc) static void dfc_cache_uninit(struct dfc_cache *flow_cache) { - int i; + int i, j; - for (i = 0; i < ARRAY_SIZE(flow_cache->entries); i++) { - dfc_clear_entry(&flow_cache->entries[i]); + for (i = 0; i < DFC_BUCKET_CNT; i++) { + for (j = 0; j < DFC_ENTRY_PER_BUCKET; j++) { + dfc_clear_entry(&(flow_cache->buckets[i]), j); + } } emc_cache_uninit(&flow_cache->emc_cache); } @@ -2245,39 +2252,46 @@ emc_lookup(struct emc_cache *emc, const struct netdev_flow_key *key) return NULL; } -static inline struct dfc_entry * +static inline struct dp_netdev_flow * dfc_entry_get(struct dfc_cache *cache, const uint32_t hash) { - return &cache->entries[hash & DFC_MASK]; + struct dfc_bucket *bucket = &cache->buckets[hash & DFC_MASK]; + uint16_t sig = hash >> 16; + for (int i = 0; i < DFC_ENTRY_PER_BUCKET; i++) { + if(bucket->sig[i] == sig) { + return bucket->flow[i]; + } + } + return NULL; } static inline bool -dfc_entry_alive(struct dfc_entry *ce) +dfc_entry_alive(struct dp_netdev_flow *flow) { - return ce->flow && !ce->flow->dead; + return flow && !flow->dead; } static void -dfc_clear_entry(struct dfc_entry *ce) +dfc_clear_entry(struct dfc_bucket *b, int idx) { - if (ce->flow) { - dp_netdev_flow_unref(ce->flow); - ce->flow = NULL; + if (b->flow[idx]) { + dp_netdev_flow_unref(b->flow[idx]); + b->flow[idx] = NULL; } } static inline void -dfc_change_entry(struct dfc_entry *ce, struct dp_netdev_flow *flow) +dfc_change_entry(struct dfc_bucket *b, int idx, struct dp_netdev_flow *flow) { - if (ce->flow != flow) { - if (ce->flow) { - dp_netdev_flow_unref(ce->flow); + if (b->flow[idx] != flow) { + if (b->flow[idx]) { + dp_netdev_flow_unref(b->flow[idx]); } if (dp_netdev_flow_ref(flow)) { - ce->flow = flow; + b->flow[idx] = flow; } else { - ce->flow = NULL; + b->flow[idx] = NULL; } } } @@ -2288,10 +2302,25 @@ dfc_insert(struct dp_netdev_pmd_thread *pmd, struct dp_netdev_flow *flow) { struct dfc_cache *cache = &pmd->flow_cache; - struct dfc_entry *current_entry; - current_entry = dfc_entry_get(cache, key->hash); - dfc_change_entry(current_entry, flow); + struct dfc_bucket *bucket = &cache->buckets[key->hash & DFC_MASK]; + uint16_t sig = key->hash >> 16; + for (int i = 0; i < DFC_ENTRY_PER_BUCKET; i++) { + if(bucket->sig[i] == sig) { + dfc_change_entry(bucket, i, flow); + return; + } + } + for (int i = 0; i < DFC_ENTRY_PER_BUCKET; i++) { + if(bucket->flow[i] == NULL) { + bucket->sig[i] = sig; + dfc_change_entry(bucket, i, flow); + return; + } + } + int idx = random_uint32() & (DFC_ENTRY_PER_BUCKET - 1); + bucket->sig[idx] = sig; + dfc_change_entry(bucket, idx, flow); } static inline struct dp_netdev_flow * @@ -2308,10 +2337,9 @@ dfc_lookup(struct dfc_cache *cache, struct netdev_flow_key *key, } /* EMC lookup not successful: try DFC lookup. */ - struct dfc_entry *current_entry = dfc_entry_get(cache, key->hash); - flow = current_entry->flow; + flow = dfc_entry_get(cache, key->hash); - if (dfc_entry_alive(current_entry) && + if (flow != NULL && dfc_entry_alive(flow) && dpcls_rule_matches_key(&flow->cr, key)) { /* Found a match in DFC. Insert into EMC for subsequent lookups. @@ -2345,15 +2373,20 @@ static void dfc_slow_sweep(struct dfc_cache *cache) { /* Sweep the EMC so that both finish in the same time. */ - if ((cache->sweep_idx & (DFC_ENTRIES/EMC_ENTRIES - 1)) == 0) { + if ((cache->sweep_idx & (DFC_BUCKET_CNT/EMC_ENTRIES - 1)) == 0) { emc_slow_sweep(&cache->emc_cache); } - struct dfc_entry *entry = &cache->entries[cache->sweep_idx]; - if (!dfc_entry_alive(entry)) { - dfc_clear_entry(entry); + if((cache->sweep_idx & (DFC_ENTRY_PER_BUCKET - 1)) == 0) { + uint32_t bkt = cache->sweep_idx / DFC_ENTRY_PER_BUCKET; + struct dfc_bucket *bucket = &cache->buckets[bkt]; + for (int i = 0; i < DFC_ENTRY_PER_BUCKET; i++){ + if (!dfc_entry_alive(bucket->flow[i])) { + dfc_clear_entry(bucket, i); + } + } } - cache->sweep_idx = (cache->sweep_idx + 1) & DFC_MASK; + cache->sweep_idx = (cache->sweep_idx + 1) & (DFC_ENTRIES - 1); } static struct dp_netdev_flow *