Date: Fri, 21 May 2004 12:19:37 -0700 (PDT) From: Julian Elischer <julian@elischer.org> To: John Baldwin <jhb@FreeBSD.org> Cc: freebsd-arch@FreeBSD.org Subject: Re: atomic reference counting primatives. Message-ID: <Pine.BSF.4.21.0405211153350.72391-100000@InterJet.elischer.org> In-Reply-To: <200405210959.25368.jhb@FreeBSD.org>
next in thread | previous in thread | raw e-mail | index | archive | help
On Fri, 21 May 2004, John Baldwin wrote:
> On Thursday 20 May 2004 10:54 pm, M. Warner Losh wrote:
> > In message:
> > <Pine.BSF.4.21.0405201340590.72391-100000@InterJet.elischer.org>
> >
> > Julian Elischer <julian@elischer.org> writes:
> > : This has been raised before but I've come across uses for it again and
> > : again so I'm raising it again.
> > : JHB once posted some atomic referenc counting primatives. (Do you still
> > : have them John?)
> > : Alfred once said he had soem somewhere too, and other s have commentted
> > : on this before, but we still don't seem to have any.
> > :
> > : every object is reference counted with its own code and
> > : sometimes it's done poorly.
> > :
> > : Some peiople indicated that there are cases where a generic refcounter
> > : can not be used and usd this as a reason to not have one at all.
> > :
> > : So, here are some possibilities..
> > : my first "write it down without too much thinking" effort..
> > :
> > : typedef {mumble} refcnt_t
> > :
> > : refcnt_add(refcnt_t *)
> > : Increments the reference count.. no magic except to be atomic.
> > :
> > :
> > : int refcnt_drop(refcnt *, struct mutex *)
> > : Decrements the refcount. If it goes to 0 it returns 0 and locks the
> > : mutex (if the mutex is supplied)..
> >
> > What prevents refcnt_add() from happening after ref count drops to 0?
> > Wouldn't that be a race? Eg, if we have two threads:
> >
> >
> > Thread A Thread B
> >
> > objp = lookup();
> > [1] refcnt_drop(&objp->ref, &objp->mtx);
> > [2] refcnt_add(&obj->ref);
> > BANG!
> >
> > If [1] happens before [2], then bad things happen at BANG! If [2]
> > happens before [1], then the mutex won't be locked at BANG and things
> > is good. Thread A believes it has a valid reference to objp after the
> > refcnt_add and no way of knowing otherwise.
> >
> > Is there a safe way to use the API into what you are proposing?
>
> This situation can't happen if you are properly using reference counting. For
> the reference count to be at 1 in thread B, it has to have the only reference
> meaning that the object has already been removed from any lists, etc.
Exactly.. B needs to have got his copy of th reference from somewhere,
and that reference should have been counted somewhere as should B's copy
of it.
So, the reference count should be at least 2 before B drops his
reference.. and possibly 3..
I would even go on record as saying that I have seen and liked
a refcount API which was (from memory something like):
void * refcnt_add(offsetof(struct obj, refcnt), void ** object_p)
which takes a pointer to the object pointer you are copyuing, and
atomically increments it and returns the contents of the pointer.
If the contents of the pointer are NULL, then it retunrs NULL
and doesn't increment anything..
The reference decrement atomically reduced the reference count and
zapped the pointer, and retunred a copy of the pointer if
the reference count had gone to 0 (or NULL if not).
So usage was:
struct xx *globalpointer; /* has its own owner somewhere */
mypointer = refcnt_add(offsetof(xx, refcnt), globalptr)
if (mypointer == NULL) {
printf("didn't find an object\n"
return (-1);
}
manipulate(mypointer)
if ((tmppointer = refcnt_drop(&mypointer, &globalpointer))) {
free(tmppointer);
}
someone else who owns the globalpointer reference might might in
the meanwhile do:
if ((tmppointer = refcnt_drop(globalpointer->refcnt, &globalpointer))) {
free(tmppointer);
}
and you were guaranteed to get a predictable result.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?Pine.BSF.4.21.0405211153350.72391-100000>