From patchwork Fri Dec 1 00:03:02 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tom Herbert X-Patchwork-Id: 843259 X-Patchwork-Delegate: davem@davemloft.net Return-Path: X-Original-To: patchwork-incoming@ozlabs.org Delivered-To: patchwork-incoming@ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=vger.kernel.org (client-ip=209.132.180.67; helo=vger.kernel.org; envelope-from=netdev-owner@vger.kernel.org; receiver=) Authentication-Results: ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=quantonium-net.20150623.gappssmtp.com header.i=@quantonium-net.20150623.gappssmtp.com header.b="c5c3aY1t"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 3ynvcz40MXz9sNd for ; Fri, 1 Dec 2017 11:03:47 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751787AbdLAADp (ORCPT ); Thu, 30 Nov 2017 19:03:45 -0500 Received: from mail-pg0-f65.google.com ([74.125.83.65]:32772 "EHLO mail-pg0-f65.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751711AbdLAADo (ORCPT ); Thu, 30 Nov 2017 19:03:44 -0500 Received: by mail-pg0-f65.google.com with SMTP id g7so3709178pgs.0 for ; Thu, 30 Nov 2017 16:03:44 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=quantonium-net.20150623.gappssmtp.com; s=20150623; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=FYdP4g9OGXOx+8ecAxrtrss2EzHu3FFw6+R8R+v/NwY=; b=c5c3aY1tWUpFO756WTqsDuvBFaUfHc2f0VYUKuJfFzwgOmSYnkWsA8bSeG/T4s1XM1 3dHGZ97lZuXsS3ONbREa9j5timO+ICZ33LURdPadkrvXjFdF3Pk8eUFSHGxgvxy3Wvnd mHAgXbcazjvCO3TUv2Wd9OrsyybmpfASg+BRzOPXpefbqQTiCyzGuPPfcOd+b5xjbzr1 jzBiVe+619OH96y1UOjjMX7y9x/Oa7fS3d58QPQdHV8NLcRuT0nPl/H2yBb3Jmzg5RCp MIL4TPM8R2mC3Npwov94/vBl9RGpaNvefWsMtYLnDnBpzQSYop6DwjzOMZ2kp9zrSJ3I EaAQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=FYdP4g9OGXOx+8ecAxrtrss2EzHu3FFw6+R8R+v/NwY=; b=iwg+KMsGx5A4ualgBlY6bg7M/l+175Y8y3TQJi1/+3ZuXiPf+YSKmODNmbbztyyCjd KkZWy/D1oHuvREaEtV3RF5K3KmYZbn784fY2quJpauf/EQWWUCMvEVq902HLzMGhME3f tMy29ysWQuNr6HVuZkZzjakiEsBuYVrPtdGdA4FTOcc6veZLveh5945IUFmtCrDFVowb QNeWdr27Lnictajsc8YOrJ6WFcBZhTnhJFT5I2gD/YUPpWB5xgFD1HmIyHODlicBPspU Z5pjvO2o4YnokmfXODrZhdF9QLiC43ce6I2Kdf7R9Xy0Rzkb9AYgQr09/rfG2VXMwi8R aj3Q== X-Gm-Message-State: AJaThX7rUXbHUVNGsU0/zLhLuRFzVc/zL7Jpqs+PT2wSePNAjiaeZhKX xRNOAxAnAuGDZybyyOkxnERzDQ== X-Google-Smtp-Source: AGs4zMbk5F7tqGn56H+mBGeOEWdeojxbkz4EiuC06R6EpnLmnvETr6fPwgofaNmuZKqZAtN4fLqM6A== X-Received: by 10.98.87.142 with SMTP id i14mr8382008pfj.212.1512086623689; Thu, 30 Nov 2017 16:03:43 -0800 (PST) Received: from localhost.localdomain (c-73-162-13-107.hsd1.ca.comcast.net. [73.162.13.107]) by smtp.gmail.com with ESMTPSA id s66sm10510569pfd.74.2017.11.30.16.03.41 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 30 Nov 2017 16:03:42 -0800 (PST) From: Tom Herbert To: davem@davemloft.net Cc: netdev@vger.kernel.org, rohit@quantonium.net, herbert@gondor.apana.org.au, Tom Herbert Subject: [PATCH net-next 2/5] rhashtable: Add rhastable_walk_peek Date: Thu, 30 Nov 2017 16:03:02 -0800 Message-Id: <20171201000305.2392-3-tom@quantonium.net> X-Mailer: git-send-email 2.11.0 In-Reply-To: <20171201000305.2392-1-tom@quantonium.net> References: <20171201000305.2392-1-tom@quantonium.net> Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org This function is like rhashtable_walk_next except that it only returns the current element in the inter and does not advance the iter. This patch also creates __rhashtable_walk_find_next. It finds the next element in the table when the entry cached in iter is NULL or at the end of a slot. __rhashtable_walk_find_next is called from rhashtable_walk_next and rhastable_walk_peek. Signed-off-by: Tom Herbert --- include/linux/rhashtable.h | 1 + lib/rhashtable.c | 103 ++++++++++++++++++++++++++++++++++++++------- 2 files changed, 88 insertions(+), 16 deletions(-) diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h index 4c976bf320a8..7f3e674e127a 100644 --- a/include/linux/rhashtable.h +++ b/include/linux/rhashtable.h @@ -380,6 +380,7 @@ void rhashtable_walk_enter(struct rhashtable *ht, void rhashtable_walk_exit(struct rhashtable_iter *iter); void rhashtable_walk_start(struct rhashtable_iter *iter) __acquires(RCU); void *rhashtable_walk_next(struct rhashtable_iter *iter); +void *rhashtable_walk_peek(struct rhashtable_iter *iter); void rhashtable_walk_stop(struct rhashtable_iter *iter) __releases(RCU); void rhashtable_free_and_destroy(struct rhashtable *ht, diff --git a/lib/rhashtable.c b/lib/rhashtable.c index eeddfb3199cd..1d58231110af 100644 --- a/lib/rhashtable.c +++ b/lib/rhashtable.c @@ -753,18 +753,16 @@ void rhashtable_walk_start(struct rhashtable_iter *iter) EXPORT_SYMBOL_GPL(rhashtable_walk_start); /** - * rhashtable_walk_next - Return the next object and advance the iterator + * __rhashtable_walk_find_next - Find the next element in a table (or the first + * one in case of a new walk). + * * @iter: Hash table iterator * - * Note that you must call rhashtable_walk_stop when you are finished - * with the walk. + * Returns the found object or NULL when the end of the table is reached. * - * Returns the next object or NULL when the end of the table is reached. - * - * Returns -EAGAIN if resize event occured. Note that the iterator - * will rewind back to the beginning and you may continue to use it. + * Returns -EAGAIN if resize event occurred. */ -void *rhashtable_walk_next(struct rhashtable_iter *iter) +static void *__rhashtable_walk_find_next(struct rhashtable_iter *iter) { struct bucket_table *tbl = iter->walker.tbl; struct rhlist_head *list = iter->list; @@ -772,14 +770,6 @@ void *rhashtable_walk_next(struct rhashtable_iter *iter) struct rhash_head *p = iter->p; bool rhlist = ht->rhlist; - if (p) { - if (!rhlist || !(list = rcu_dereference(list->next))) { - p = rcu_dereference(p->next); - list = container_of(p, struct rhlist_head, rhead); - } - goto next; - } - for (; iter->slot < tbl->size; iter->slot++) { int skip = iter->skip; @@ -826,9 +816,90 @@ void *rhashtable_walk_next(struct rhashtable_iter *iter) return NULL; } + +/** + * rhashtable_walk_next - Return the next object and advance the iterator + * @iter: Hash table iterator + * + * Note that you must call rhashtable_walk_stop when you are finished + * with the walk. + * + * Returns the next object or NULL when the end of the table is reached. + * + * Returns -EAGAIN if resize event occurred. Note that the iterator + * will rewind back to the beginning and you may continue to use it. + */ +void *rhashtable_walk_next(struct rhashtable_iter *iter) +{ + struct rhlist_head *list = iter->list; + struct rhashtable *ht = iter->ht; + struct rhash_head *p = iter->p; + bool rhlist = ht->rhlist; + + if (!iter->walker.tbl) + return NULL; + + if (p) { + if (!rhlist || !(list = rcu_dereference(list->next))) { + p = rcu_dereference(p->next); + list = container_of(p, struct rhlist_head, rhead); + } + if (!rht_is_a_nulls(p)) { + iter->skip++; + iter->p = p; + iter->list = list; + return rht_obj(ht, rhlist ? &list->rhead : p); + } + + /* At the end of this slot, switch to next one and then find + * next entry from that point. + */ + iter->skip = 0; + iter->slot++; + } + + return __rhashtable_walk_find_next(iter); +} EXPORT_SYMBOL_GPL(rhashtable_walk_next); /** + * rhashtable_walk_peek - Return the next object but don't advance the iterator + * @iter: Hash table iterator + * + * Returns the next object or NULL when the end of the table is reached. + * + * Returns -EAGAIN if resize event occurred. Note that the iterator + * will rewind back to the beginning and you may continue to use it. + */ +void *rhashtable_walk_peek(struct rhashtable_iter *iter) +{ + struct rhlist_head *list = iter->list; + struct rhashtable *ht = iter->ht; + struct rhash_head *p = iter->p; + + if (!iter->walker.tbl) + return NULL; + + if (p) + return rht_obj(ht, ht->rhlist ? &list->rhead : p); + + /* No object found in current iter, find next one in the table. */ + + if (iter->skip) { + /* A nonzero skip value points to the next entry in the table + * beyond that last one that was found. Decrement skip so + * we find the current value. __rhashtable_walk_find_next + * will restore the original value of skip assuming that + * the table hasn't changed. + */ + iter->skip--; + } + + return __rhashtable_walk_find_next(iter); +} +EXPORT_SYMBOL_GPL(rhashtable_walk_peek); + +/** * rhashtable_walk_stop - Finish a hash table walk * @iter: Hash table iterator *