From patchwork Wed Jul 18 14:07:59 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Daniel Klein X-Patchwork-Id: 1211291 X-Patchwork-Delegate: alexne@voltaire.com Return-Path: X-Original-To: patchwork-linux-rdma@patchwork.kernel.org Delivered-To: patchwork-process-083081@patchwork1.kernel.org Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by patchwork1.kernel.org (Postfix) with ESMTP id E90533FCFC for ; Wed, 18 Jul 2012 14:08:10 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753931Ab2GROII (ORCPT ); Wed, 18 Jul 2012 10:08:08 -0400 Received: from eu1sys200aog107.obsmtp.com ([207.126.144.123]:34062 "HELO eu1sys200aog107.obsmtp.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with SMTP id S1753868Ab2GROIH (ORCPT ); Wed, 18 Jul 2012 10:08:07 -0400 Received: from mtlsws123.lab.mtl.com ([82.166.227.17]) (using TLSv1) by eu1sys200aob107.postini.com ([207.126.147.11]) with SMTP ID DSNKUAbDRASFEyA3Q6KK2lTnG8SLP339HaE8@postini.com; Wed, 18 Jul 2012 14:08:07 UTC Received: from r-vnc07.lab.mtl.com (r-vnc07.lab.mtl.com [10.208.0.119]) by mtlsws123.lab.mtl.com (8.13.8/8.13.8) with ESMTP id q6IE83UH010458; Wed, 18 Jul 2012 17:08:03 +0300 Received: from r-vnc07.lab.mtl.com (localhost.localdomain [127.0.0.1]) by r-vnc07.lab.mtl.com (8.13.8/8.13.8) with ESMTP id q6IE83Uc015036; Wed, 18 Jul 2012 17:08:03 +0300 Received: (from danielk@localhost) by r-vnc07.lab.mtl.com (8.13.8/8.13.8/Submit) id q6IE83Xm015035; Wed, 18 Jul 2012 17:08:03 +0300 From: Daniel Klein To: linux-rdma@vger.kernel.org Cc: Daniel Klein Subject: [PATCH] opensm: improve search common pkeys. Date: Wed, 18 Jul 2012 17:07:59 +0300 Message-Id: <1342620479-14923-1-git-send-email-danielk@mellanox.com> X-Mailer: git-send-email 1.7.8.2 Sender: linux-rdma-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-rdma@vger.kernel.org improving runtim of search comon pkeys code to o(n). Signed-off-by: Daniel Klein --- opensm/osm_pkey.c | 94 +++++++++++++++++++++++++++++++++++++++-------------- 1 files changed, 69 insertions(+), 25 deletions(-) diff --git a/opensm/osm_pkey.c b/opensm/osm_pkey.c index 69657dc..ef5c033 100644 --- a/opensm/osm_pkey.c +++ b/opensm/osm_pkey.c @@ -374,9 +374,6 @@ ib_net16_t osm_physp_find_common_pkey(IN const osm_physp_t * p_physp1, pkey_tbl1 = osm_physp_get_pkey_tbl(p_physp1); pkey_tbl2 = osm_physp_get_pkey_tbl(p_physp2); - if (allow_both_pkeys) - goto SearchByKeys; - map_iter1 = cl_map_head(&pkey_tbl1->keys); map_iter2 = cl_map_head(&pkey_tbl2->keys); @@ -401,34 +398,81 @@ ib_net16_t osm_physp_find_common_pkey(IN const osm_physp_t * p_physp1, map_iter1 = cl_map_next(map_iter1); } - return 0; + if (!allow_both_pkeys) + return 0; -SearchByKeys: + /* + When using allow_both_pkeys, the keys in pkey tables are the + pkey value including membership bit. + Therefore, in order to complete the search, we also need to + compare port\s 1 full pkeys with port 2 limited pkeys, and + port 2 full pkeys with port 1 full pkeys. + */ - /* Select to iterate over the table with the least elements */ - if (cl_map_count(&pkey_tbl1->keys) < cl_map_count(&pkey_tbl2->keys)) { - map_iter = cl_map_head(&pkey_tbl1->keys); - map_end = cl_map_end(&pkey_tbl1->keys); - pkey_tbl = pkey_tbl2; - } else { - map_iter = cl_map_head(&pkey_tbl2->keys); - map_end = cl_map_end(&pkey_tbl2->keys); - pkey_tbl = pkey_tbl1; - } + map_iter1 = cl_map_head(&pkey_tbl1->keys); + map_iter2 = cl_map_head(&pkey_tbl2->keys); - while (map_iter != map_end) { - pkey1 = (ib_net16_t *) cl_map_obj(map_iter); - key = cl_map_key(map_iter); + /* comparing pkey_tbl1 full with pkey_tbl2 limited */ + while ((map_iter1 != cl_map_end(&pkey_tbl1->keys)) && + (map_iter2 != cl_map_end(&pkey_tbl2->keys))) { + pkey1 = (ib_net16_t *) cl_map_obj(map_iter1); + pkey2 = (ib_net16_t *) cl_map_obj(map_iter2); - pkey2 = cl_map_get(&pkey_tbl->keys, key | IB_PKEY_TYPE_MASK); - if (!pkey2) - pkey2 = cl_map_get(&pkey_tbl->keys, - key & ~IB_PKEY_TYPE_MASK); + if (!ib_pkey_is_full_member(*pkey1)) { + map_iter1 = cl_map_next(map_iter1); + continue; + } + if (ib_pkey_is_full_member(*pkey2)) { + map_iter2 = cl_map_next(map_iter2); + continue; + } + + if (match_pkey(pkey1, pkey2)) + return *pkey1; + + /* advance the lower value if they are not equal */ + pkey1_base = cl_map_key(map_iter1); + pkey2_base = cl_map_key(map_iter2); + if (pkey2_base == pkey1_base) { + map_iter1 = cl_map_next(map_iter1); + map_iter2 = cl_map_next(map_iter2); + } else if (pkey2_base < pkey1_base) + map_iter2 = cl_map_next(map_iter2); + else + map_iter1 = cl_map_next(map_iter1); + } - if (pkey2 && match_pkey(pkey1, pkey2)) - return (pkey_tbl == pkey_tbl2 ? *pkey1 : *pkey2); + map_iter1 = cl_map_head(&pkey_tbl1->keys); + map_iter2 = cl_map_head(&pkey_tbl2->keys); - map_iter = cl_map_next(map_iter); + /* comparing pkey_tbl1 limited with pkey_tbl2 full */ + while ((map_iter1 != cl_map_end(&pkey_tbl1->keys)) && + (map_iter2 != cl_map_end(&pkey_tbl2->keys))) { + pkey1 = (ib_net16_t *) cl_map_obj(map_iter1); + pkey2 = (ib_net16_t *) cl_map_obj(map_iter2); + + if (ib_pkey_is_full_member(*pkey1)) { + map_iter1 = cl_map_next(map_iter1); + continue; + } + if (!ib_pkey_is_full_member(*pkey2)) { + map_iter2 = cl_map_next(map_iter2); + continue; + } + + if (match_pkey(pkey1, pkey2)) + return *pkey1; + + /* advance the lower value if they are not equal */ + pkey1_base = cl_map_key(map_iter1); + pkey2_base = cl_map_key(map_iter2); + if (pkey2_base == pkey1_base) { + map_iter1 = cl_map_next(map_iter1); + map_iter2 = cl_map_next(map_iter2); + } else if (pkey2_base < pkey1_base) + map_iter2 = cl_map_next(map_iter2); + else + map_iter1 = cl_map_next(map_iter1); } return 0;