All of lore.kernel.org
 help / color / mirror / Atom feed
From: Peter Zijlstra <peterz@infradead.org>
To: Nick Piggin <npiggin@suse.de>
Cc: Linux Kernel Mailing List <linux-kernel@vger.kernel.org>,
	David Miller <davem@davemloft.net>,
	Paul McKenney <paulmck@us.ibm.com>, Ingo Molnar <mingo@elte.hu>
Subject: Re: [rfc][patch] dynamic data structure switching
Date: Mon, 10 Sep 2007 13:55:52 +0200	[thread overview]
Message-ID: <1189425352.21778.12.camel@twins> (raw)
In-Reply-To: <20070902182738.GA13145@wotan.suse.de>

On Sun, 2007-09-02 at 20:27 +0200, Nick Piggin wrote:

> Index: linux-2.6/lib/dyndata.c
> ===================================================================
> --- /dev/null
> +++ linux-2.6/lib/dyndata.c
> @@ -0,0 +1,80 @@
> +#include <linux/dyndata.h>
> +#include <linux/mutex.h>
> +#include <linux/rcupdate.h>
> +#include <linux/seqlock.h>
> +
> +void dyn_data_init(struct dyn_data *dd, void *cur_data)
> +{
> +	dd->cur = cur_data;
> +	dd->old = NULL;
> +	seqcount_init(&dd->resize_seq);
> +	mutex_init(&dd->resize_mutex);
> +}
> +
> +/*
> + * Slowpath lookup. There is a resize in progress and we weren't able to
> + * find the item we wanted in dyn_data_lookup: run the full race-free
> + * lookup protocol.
> + */
> +static noinline void *dyn_data_lookup_slow(struct dyn_data *dd, dd_lookup_fn fn, void *arg)
> +{
> +	void *ret;
> +	void *cur, *old;
> +	unsigned seq;
> +
> +	cur = dd->cur;
> +	old = dd->old;
> +
> +	do {
> +		seq = read_seqcount_begin(&dd->resize_seq);
> +		ret = fn(cur, arg);
> +		if (ret)
> +			return ret;
> +		if (!old)
> +			return NULL;
> +
> +		ret = fn(old, arg);
> +		if (ret)
> +			return ret;
> +	} while (read_seqcount_retry(&dd->resize_seq, seq));

With the seqlock protecting the whole xfer a lookup for a non-existing
item might spin here for a very long time.

Maybe we should create this sleeping seqlock we talked and provide both
a sleeping and non sleeping version of this lookup function.

> +	return NULL;
> +}
> +
> +void *dyn_data_lookup(struct dyn_data *dd, dd_lookup_fn fn, void *arg)
> +{
> +	void *ret;
> +
> +	rcu_read_lock();
> +	if (likely(!dd->old))
> +		ret = fn(dd->cur, arg);
> +	else
> +		ret = dyn_data_lookup_slow(dd, fn, arg);
> +	rcu_read_unlock();
> +
> +	return ret;
> +}
> +
> +void *dyn_data_replace(struct dyn_data *dd, dd_transfer_fn fn, void *new)
> +{
> +	int xfer_done;
> +	void *old;
> +
> +	BUG_ON(!mutex_is_locked(&dd->resize_mutex));

So its up to the caller to take resize_mutex, but there is no mention of
this requirement. Why cannot it be taken inside this function?

> +	old = dd->cur;
> +	BUG_ON(dd->old);
> +	dd->old = old;
> +	synchronize_rcu();
> +	rcu_assign_pointer(dd->cur, new);
> +	synchronize_rcu();
> +	do {
> +		write_seqcount_begin(&dd->resize_seq);
> +		xfer_done = fn(old, new);
> +		write_seqcount_end(&dd->resize_seq);
> +	} while (!xfer_done);
> +	dd->old = NULL;
> +	synchronize_rcu();
> +
> +
> +	return old;
> +}
> Index: linux-2.6/include/linux/dyndata.h
> ===================================================================
> --- /dev/null
> +++ linux-2.6/include/linux/dyndata.h
> @@ -0,0 +1,94 @@
> +#ifndef __DYNDATA_H__
> +#define __DYNDATA_H__
> +

<snip>

> +
> +#include <linux/mutex.h>
> +#include <linux/seqlock.h>
> +
> +struct dyn_data {
> +	void *cur;
> +	void *old;
> +	seqcount_t resize_seq;
> +	struct mutex resize_mutex;
> +};
> +
> +typedef void *(dd_lookup_fn)(void *dstruct, void *arg);
> +typedef int (dd_transfer_fn)(void *old_ds, void *new_ds);
> +
> +void dyn_data_init(struct dyn_data *dd, void *cur_data);
> +void *dyn_data_lookup(struct dyn_data *dd, dd_lookup_fn fn, void *arg);
> +void *dyn_data_replace(struct dyn_data *dd, dd_transfer_fn fn, void *new);
> +
> +static inline void *dyn_data_current_dstruct(struct dyn_data *dd)
> +{
> +	return dd->cur;
> +}
> +
> +#endif



  parent reply	other threads:[~2007-09-10 11:56 UTC|newest]

Thread overview: 9+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2007-09-02 18:27 [rfc][patch] dynamic data structure switching Nick Piggin
2007-09-02 18:36 ` Nick Piggin
2007-09-05 23:05   ` Fast path efficiency (Re: [rfc][patch] dynamic data structure switching) Oleg Verych
2007-09-06  7:14     ` Nick Piggin
2007-09-06 11:35     ` Andi Kleen
2007-09-10 11:55 ` Peter Zijlstra [this message]
2007-09-10 13:39   ` [rfc][patch] dynamic data structure switching Nick Piggin
  -- strict thread matches above, loose matches on Subject: below --
2007-09-10 16:58 Oleg Nesterov
2007-09-10 20:48 ` Nick Piggin

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=1189425352.21778.12.camel@twins \
    --to=peterz@infradead.org \
    --cc=davem@davemloft.net \
    --cc=linux-kernel@vger.kernel.org \
    --cc=mingo@elte.hu \
    --cc=npiggin@suse.de \
    --cc=paulmck@us.ibm.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.