Re: [rfc][patch] dynamic data structure switching

[Peter Zijlstra <peterz@infradead.org>]

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