Lockless uidinfo.

[Pawel Jakub Dawidek]

On Tue, Aug 21, 2007 at 02:03:28PM -0400, John Baldwin wrote:
> On Saturday 18 August 2007 12:14:49 pm Pawel Jakub Dawidek wrote:
> > On Sat, Aug 18, 2007 at 08:50:41AM -0700, Alfred Perlstein wrote:
> > > * Pawel Jakub Dawidek <pjd at FreeBSD.org> [070818 07:59] wrote:
> > > > Yes, to lookup uidinfo you need to hold uihashtbl_mtx mutex, so once you
> > > > hold it and ui_ref is 0, noone will be able to reference it, because it
> > > > has to wait to look it up.
> > > 
> > > And the field doesn't need to be volatile to prevent cached/opportunitic
> > > reads?
> > 
> > The only chance of something like this will be the scenario below:
> > 
> > thread1 (uifind)		thread2 (uifree)
> > ----------------		----------------
> > 				refcount_release(&uip->ui_ref))
> > 				/* ui_ref == 0 */
> > mtx_lock(&uihashtbl_mtx);
> > refcount_acquire(&uip->ui_ref);
> > /* ui_ref == 1 */
> > mtx_unlock(&uihashtbl_mtx);
> > 				mtx_lock(&uihashtbl_mtx);
> > 				if (uip->ui_ref > 0) {
> > 					mtx_unlock(&uihashtbl_mtx);
> > 					return;
> > 				}
> > 
> > Now, you suggest that ui_ref in 'if (uip->ui_ref > 0)' may still have
> > cached 0? I don't think it is possible, first refcount_acquire() uses
> > read memory bariers (but we may still need ui_ref to volatile for this
> > to make any difference) and second, think of ui_ref as a field protected
> > by uihashtbl_mtx mutex in this very case.
> > 
> > Is my thinking correct?
> 
> Memory barriers on another CPU don't mean anything about the CPU thread 2 is 
> on.  Memory barriers do not flush caches on other CPUs, etc.  Normally when 
> objects are refcounted in a table, the table holds a reference on the object, 
> but that doesn't seem to be the case here. [...]

But the memory barrier from 'mtx_lock(&uihashtbl_mtx)' above
'if (uip->ui_ref > 0)' would do the trick and I can safely avoid using
atomic read in this if statement, right?

> [...] Have you tried doing something 
> very simple in uifree():
> 
> {
> 	mtx_lock(&uihashtbl_mtx);
> 	if (refcount_release(...)) {
> 		LIST_REMOVE();
> 		mtx_unlock(&uihashtbl_mtx);
> 		...
> 		free();
> 	} else
> 		mtx_unlock(&uihashtbl_mtx);
> }
> 
> I wouldn't use a more complex algo in uifree() unless the simple one is shown 
> to perform badly.  Needless complexity is a hindrance to future maintenance.

Of coure we could do that, but I was trying really hard to remove
contention in the common case. Before we used UIDINFO_LOCK() in the
common case, now you suggesting using global lock here, and I'd really,
really prefer using one atomic only.

> Also, even if you do go with the more complex route, I'd rather you reduce 
> diffs with the current code by keeping the test as 'uip->ui_ref == 0' and 
> keeping the removal code in the if-block.

Will do.

> In chgproccnt() you should use atomic_fetchadd_long() to avoid a race when 
> reading ui_proccnt.
> 
> 
> 	old = atomic_fetchadd_long(&uip->ui_proccnt, diff);
> 	if (old + diff < 0)
> 		printf("....");

I'm aware of this race, but I don't find closing it that much important.
We won't generate false positive here. My vote is to leave it as it is,
because atomic_fetchadd_long() is slower on some archs than
atomic_add_long(), ie. it is implemented using atomic_cmpset_long()
loop, and as I checked by running 8 processes on 8way machine with
older code that used atomic_cmpset_long() loop in 'diff > 0' case,
there is almost one extra loop on every call, which makes it about 6%
slower.

> OTOH, atomic_fetchadd_long() doesn't yet exist, so you will need to fix that, 
> or just always use an atomic_cmpset() loop.

I already implemented those.

-- 
Pawel Jakub Dawidek                       http://www.wheel.pl
pjd at FreeBSD.org                           http://www.FreeBSD.org
FreeBSD committer                         Am I Evil? Yes, I Am!
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 187 bytes
Desc: not available
Url : http://lists.freebsd.org/pipermail/freebsd-arch/attachments/20070821/ad862d70/attachment.pgp