Lockless uidinfo.

[Pawel Jakub Dawidek]

On Tue, Aug 21, 2007 at 05:53:34PM -0400, John Baldwin wrote:
> On Tuesday 21 August 2007 03:19:02 pm Pawel Jakub Dawidek wrote:
> > > 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?
> 
> Yes, though that may be rather non-obvious to other people, or to yourself 6 
> months down the road.  You should probably document it.

Agreed, I added a comment that should explain it.

> > > 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.
> 
> *sigh*  You ignored my last sentence.  You need to think about other people 
> who come and read this later or yourself 12 months from now when you've paged 
> out all the uidinfo stuff from your head.
> 
> Hmm, what happens if you get this:
> 
> thread A
> --------
> 
>  refcount_release() - drops to 0
> 
>   preempted
> 
>                                  thread B
>                                  --------
>                                  uihold() - refcount goes to 1
>                                  ...
>                                  uifree() - refcount goes to 0
>                                  removes object from table and frees it
> 
>   resumes
> 
>   mtx_lock(&uihashtbl);
> 
>   sees refcount of 0 so tries to destroy object again
> 
>  *BOOM* (corruption, panic, etc.)

Grr, good catch.

> This is the race that the current code handles by taking a reference
> on the uid while it drops the uidinfo lock to acquire the table lock.
> 
> Probably you need to not drop the last reference unless you hold the 
> uihashtbl_mtx, which means not using refcount_release() and manually use an 
> atomic_cmpset_int() if the refcount is > 1 to drop a ref to optimize the 
> common case:
> 
> 	old = uip->ui_refs;
> 	if (old > 1) {
> 		if (atomic_cmpset_int(&uip->ui_refs, old, old - 1))
> 			return;
> 	}
> 
> 	mtx_lock(&uihashtbl_mtx);
> 	if (refcount_release(&uip->ui_refs)) {
> 		/* remove from table and free */
> 	}
> 	mtx_unlock(&uihashtbl_mtx);

How about we relookup it after acquiring the uihashtbl_mtx lock?
Something like this (comments removed):

	uid_t uid;

	uid = uip->ui_uid;
	if (!refcount_release(&uip->ui_ref))
		return;
	mtx_lock(&uihashtbl_mtx);
	uip = uilookup(uid);
	if (uip != NULL && uip->ui_ref == 0) {
		LIST_REMOVE(uip, ui_hash);
		mtx_unlock(&uihashtbl_mtx);
		FREE(uip, M_UIDINFO);
		return;
	}
	mtx_unlock(&uihashtbl_mtx);

I updated the patch at:

	http://people.freebsd.org/~pjd/patches/uidinfo_waitfree.patch

-- 
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/20070822/33a0e30f/attachment.pgp