Re: [PATCH net-next 2/5] rhashtable: Add rhastable_walk_peek

[Tom Herbert]

On Thu, Nov 30, 2017 at 5:21 PM, Herbert Xu  wrote:
> On Thu, Nov 30, 2017 at 05:15:16PM -0800, Tom Herbert wrote:
>>
>> We don't need a guarantee of stability, but what I am seeing is that
>> we're consisitently dropping entries on when doing a multi-part
>> netlink walk. We start iterating over the table filling in the netlink
>> info. But eventually the netlink info fills up and returns an error.
>> netlink dump gets called again but now the iter of the table returns
>> the object following the one that would have overflowed the netlink
>> buffer. So the result I was seeing is that we dropped one object in in
>> each pass.
>
> Thanks Tom! This information is very useful.
>
> It sounds like this problem isn't specific to ila and would exist
> for all rhashtable users that dump through netlink.  Let me think
> about this a little bit more.
>
Right. Also note that the first patch is inspired by netlink dump
handling also. When we reach the end of the table (walk_next returns
NULL), we'll return a non-zero skb->len if some records have been
written to the buffer. On the next call to the dump we need to bounce
out immediately with zero length returned. Resetting the walker table
in walk start because it's NULL results in infinite loop if -EAGAIN is
ignored by the caller (rhashtable_walk_start returning void is nice
side effect of this).

Tom


> Cheers,
> --
> Email: Herbert Xu 
> Home Page: http://gondor.apana.org.au/~herbert/
> PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH net-next 2/5] rhashtable: Add rhastable_walk_peek

[Herbert Xu]

On Thu, Nov 30, 2017 at 05:15:16PM -0800, Tom Herbert wrote:
>
> We don't need a guarantee of stability, but what I am seeing is that
> we're consisitently dropping entries on when doing a multi-part
> netlink walk. We start iterating over the table filling in the netlink
> info. But eventually the netlink info fills up and returns an error.
> netlink dump gets called again but now the iter of the table returns
> the object following the one that would have overflowed the netlink
> buffer. So the result I was seeing is that we dropped one object in in
> each pass.

Thanks Tom! This information is very useful.

It sounds like this problem isn't specific to ila and would exist
for all rhashtable users that dump through netlink.  Let me think
about this a little bit more.

Cheers,
-- 
Email: Herbert Xu 
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH net-next 2/5] rhashtable: Add rhastable_walk_peek

[Tom Herbert]

On Thu, Nov 30, 2017 at 4:38 PM, Herbert Xu  wrote:
> On Thu, Nov 30, 2017 at 04:03:02PM -0800, Tom Herbert wrote:
>> 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 
>
> Hi Tom:
>
> Could you add some motivation for this feature into the patch
> description? As it is it's difficult to deduce why we would want
> to add something like this given that hashtable walks are always
> unstable and there is no guarantee that two calls to peek or a
> peek followed by a normal walk will see the same entry.
>
Hi Herbert,

We don't need a guarantee of stability, but what I am seeing is that
we're consisitently dropping entries on when doing a multi-part
netlink walk. We start iterating over the table filling in the netlink
info. But eventually the netlink info fills up and returns an error.
netlink dump gets called again but now the iter of the table returns
the object following the one that would have overflowed the netlink
buffer. So the result I was seeing is that we dropped one object in in
each pass.

This fixes the nldump for ila which will be in a follow on patch set.
In pseudo code it looks something like this:

rhashtable_walk_start(rhiter);

/* Get first entty */
ila = rhashtable_walk_peek(rhiter);

while (ila) {
 if (ila_dump_info(ila) < 0)
 break;
 ila = rhashtable_walk_next(rhiter);
}

rhashtable_walk_stop(rhiter);

return;

So peek is only called one and we only advance iter once the current
entry is successfully processed.

Tom



> Thanks,
> --
> Email: Herbert Xu 
> Home Page: http://gondor.apana.org.au/~herbert/
> PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH net-next 2/5] rhashtable: Add rhastable_walk_peek

[Herbert Xu]

On Thu, Nov 30, 2017 at 04:03:02PM -0800, Tom Herbert wrote:
> 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 

Hi Tom:

Could you add some motivation for this feature into the patch
description? As it is it's difficult to deduce why we would want
to add something like this given that hashtable walks are always
unstable and there is no guarantee that two calls to peek or a
peek followed by a normal walk will see the same entry.

Thanks,
-- 
Email: Herbert Xu 
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

[PATCH net-next 2/5] rhashtable: Add rhastable_walk_peek

[Tom Herbert]

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 ? >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 =