Re: [RFC][PATCH] module: Optimize __module_address() using a latched RB-tree

[Peter Zijlstra <peterz@infradead.org>]

On Thu, Feb 26, 2015 at 08:13:35PM +0100, Peter Zijlstra wrote:
> > > +static void __tree_insert(struct latch_tree_root *mod_tree, struct module *mod, int idx)
> > > +{
> > > +	struct rb_root *root = &mod_tree->tree[idx & latch_bit];
> > > +	struct module_node *mn = &mod->tree_node[idx];
> > > +	struct rb_node **link = &root->rb_node;
> > > +	struct rb_node *parent = NULL;
> > > +	unsigned long mod_val, m_val;
> > > +	struct module *m;
> > > +	int i;
> > > +
> > > +	mn->mod = mod;
> > > +	mod_val = mod_value(mod, idx);
> > > +
> > > +	while (*link) {
> > > +		parent = *link;
> > > +		m = mod_entry(parent);
> > > +		i = mod_node_idx(m, parent);
> > > +		m_val = mod_value(m, i);
> > > +
> > > +		if (mod_val < m_val)
> > > +			link = &parent->rb_left;
> > > +		else
> > > +			link = &parent->rb_right;
> > > +	}
> > > +
> > > +	rb_link_node(&mn->node, parent, link);
> > 
> > This makes the new module visible to readers, if I understand correctly.
> 
> You do.

I think I have reconsidered; this does not in fact make it visible.

> > There needs to be a memory barrier between initialization and this call
> > to rb_link_node(), otherwise, both the CPU (well, for Alpha) and the
> > compiler (for everyone) can reorder, which could result in some hapless
> > reader seeing pre-initialized data.
> > 
> > Or did I miss the memory barrier?
> 
> I was going with the one in list_add_rcu() and the two in
> raw_write_seqcount_latch(), however, now that you made me look at it, I
> need one in here to ensure mn->mod is observed.

The 'second' raw_write_seqcount_latch() makes it visible, not the first.

Let me clarify with some documentation I just wrote:

 * The basic form is a data structure like:
 *
 * struct latch_struct {
 *     seqcount_t              seq;
 *     struct data_struct      data[2];
 * };
 *
 * Where a modification, which is assumed to be externally serialized, does the
 * following:
 *
 * void latch_modify(struct latch_struct *latch, ...)
 * {
 *     smp_wmb();      <- Ensure that the last data[1] update is visible
 *     latch->seq++;
 *     smp_wmb();      <- Ensure that the seqcount update is visible
 *
 *     modify(latch->data[0], ...);
 *
 *     smp_wmb();      <- Ensure that the data[0] update is visible
 *     latch->seq++;
 *     smp_wmb();      <- Ensure that the seqcount update is visible
 *
 *     modify(latch->data[1], ...);
 * }
 *
 * The query will have a form like:
 *
 * struct entry *latch_query(struct latch_struct *latch, ...)
 * {
 *     struct entry *entry;
 *     unsigned seq;
 *     int idx;
 *
 *     do {
 *             seq = latch->seq;
 *             smp_rmb();
 *
 *             idx = seq & 0x01;
 *             entry = data_query(latch->data[idx], ...);
 *
 *             smp_rmb();
 *     } while (seq != latch->seq);
 *
 *     return entry;
 * }
 *
 * So during the modification, queries are first redirected to data[1]. Then we
 * modify data[0]. When that is complete, we redirect queries back to data[0]
 * and we can modify data[1].

So any addition to data[0] does not become visible until we redirect
the readers back to it, which is the second latch increment.

This therefore obviates the need for the atomic publish APIs RCU
traditionally employs.

Let me go clarify this point in said documentation.