Re: [RFC PATCH 0/3] page count lock for simpler put_page

["Paul E. McKenney" <paulmck@linux.vnet.ibm.com>]

On Fri, Aug 12, 2011 at 06:43:25PM +0200, Andrea Arcangeli wrote:
> On Fri, Aug 12, 2011 at 09:08:13AM -0700, Paul E. McKenney wrote:
> > It should not be hard.  I already have an API for rcutorture testing
> > use, but it is not appropriate for your use because it is unsynchronized.
> 
> Sounds good.
> 
> > We need to be careful with what I give you and how you interpret it.
> > The most effective approach would be for me to give you an API that
> > filled in a cookie given a pointer to one, then another API that took
> > pointers to a pair of cookies and returned saying whether or not a
> > grace period had elapsed.  You would do something like the following:
> 
> Even a raw number of events is ok, but it will work like a cookie.

Cookie would be best.  ;-)

> > 	rcu_get_gp_cookie(&pagep->rcucookie);
> > 	. . .
> > 
> > 	rcu_get_gp_cookie(&autovarcookie);
> > 	if (!rcu_cookie_gp_elapsed(&pagep->rcucookie, &autovarcookie))
> > 		synchronize_rcu();
> > 
> > So, how much space do I get for ->rcucookie?  By default, it is a pair
> > of unsigned longs, but I could live with as small as a single byte if
> > you didn't mind a high probability of false negatives (me telling you
> > to do a grace period despite 16 of them having happened in the meantime
> > due to overflow of a 4-bit field in the byte).
> 
> It could be 2 longs just fine (so it's 64bit on 32bit too and guarantees
> no false positive as it'll never overflow for the lifetime of the
> hardware), we've tons of free space to use in page[1-511].* .

Very good!!!  

> I'm currently unsure how the cookie can be allowed to be smaller than
> the real counter though. I don't see how is it possible.

Just put the low-order bits of the counter in the byte.  This could
cause rcu_cookie_gp_elapsed() to get confused, but the only possible
confusion would be for it to make you do synchronize_rcu() when it
wasn't necessary to do so.  This is a performance problem rather than
a correctness problem, though.

But the more bits you give me, the lower the probability of needless
calls to synchronize_rcu().

> > That covers TREE_RCU and TREE_PREEMPT_RCU, on to TINY_RCU and TINY_PREEMPT_RCU.
> > 
> > TINY_RCU will require more thought, as it doesn't bother counting grace
> > periods.  Ah, but in TINY_RCU, synchronize_rcu() is free, so I simply
> > make rcu_cookie_gp_elapsed() always return false.
> 
> Yes it'll surely be safe for us, on UP we have no race and in fact
> get_page_unless_zero isn't even called in the speculative lookup in UP. With
> the code above you could return always true with TINY_RCU and skip the
> call.

Or maybe I make rcu_cookie_gp_elapsed() take only one cookie and
compare it to the current cookie.  This would save a bit of code in
the TINY cases:

	rcu_get_gp_cookie(&pagep->rcucookie);
	. . .

	if (!rcu_cookie_gp_elapsed(&pagep->rcucookie))
		synchronize_rcu();

The compiler should then be able to recognize synchronize_rcu() as dead
code in the TINY case.

The main downside of this approach is that you couldn't check for two
past points having a grace period between them, but I don't see a use
case for this right offhand.

> > OK, TINY_PREEMPT_RCU...  It doesn't count grace periods, either.  But it
> > is able to reliably detect if there are any RCU readers in flight,
> > and there normally won't be, so synchronize_rcu() is again free in the
> > common case.  And no, I don't want to count grace periods as this would
> > increase the memory footprint.  And the whole point of TINY_PREEMPT_RCU
> > is to be tiny, after all.  ;-)
> 
> Ok so it returns always false, and synchronize_rcu is always called,
> but it will normally do nothing there.

Sounds good.

> > If you need SRCU, you are out of luck until I get my act together and
> > merge it in with the other RCU implementations, which might be awhile
> > still.
> 
> Good luck because we don't need SRCU, we just need a synchronize_rcu
> vs rcu_read_lock.

Whew!  ;-)

> > For TREE_*RCU, the calls to rcu_get_gp_cookie() will cost you a lock
> > round trip.  I am hoping to be able to use the counters stored in the
> > rcu_data structure, which means that I would need to disable preemption
> > and re-enable it.  Or maybe disable and re-enable irqs instead, not yet
> > sure which.  This might require me to be conservative and make
> > rcu_cookie_gp_elapsed() unless two grace periods have elapsed.  Things
> > get a bit tricky -- yes, I could just use the global counters, but that
> > would mean that rcu_get_gp_cookie() would need to acquire a global lock,
> > and I suspect that you intend to invoke it too often for that to be
> > a winning strategy.
> 
> It is invoked at every page allocation, there are some locks taken
> there already but they're per-mm (mm->page_table_lock). I'd be nice if
> we could run it without taking locks.

OK, so I should try hard to make rcu_get_gp_cookie() access the per-CPU
rcu_data structure, then.

How long would there normally be between recording the cookie and
checking for the need for a grace period?  One disk access?  One HZ?
Something else?

> If we make it a raw unsigned long long we read it in order (first lower
> bits, then higher bits on 32bit) and store it in the opposite
> direction (first increment the higher part, then increment the lower
> part or reset it to 0), can't we avoid all the locks and worst case we
> get a false positive when we compare?

If I can make use of the values in the per-CPU rcu_data structure, no
locks are required.  Might need to disable preemption and/or interrupts,
but nothing beyond that.

> > Thoughts?  And how many bits do I get for the cookie?
> 
> As many as you want.

Woo-hoo!!!  ;-)

							Thanx, Paul

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>