From owner-freebsd-arch@FreeBSD.ORG Fri May 21 12:20:00 2004 Return-Path: Delivered-To: freebsd-arch@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id ED51F16A4CE; Fri, 21 May 2004 12:19:59 -0700 (PDT) Received: from sccrmhc12.comcast.net (sccrmhc12.comcast.net [204.127.202.56]) by mx1.FreeBSD.org (Postfix) with ESMTP id 953A743D39; Fri, 21 May 2004 12:19:58 -0700 (PDT) (envelope-from julian@elischer.org) Received: from interjet.elischer.org ([24.7.73.28]) by comcast.net (sccrmhc12) with ESMTP id <2004052119194001200oj2q5e>; Fri, 21 May 2004 19:19:41 +0000 Received: from localhost (localhost.elischer.org [127.0.0.1]) by InterJet.elischer.org (8.9.1a/8.9.1) with ESMTP id MAA87919; Fri, 21 May 2004 12:19:39 -0700 (PDT) Date: Fri, 21 May 2004 12:19:37 -0700 (PDT) From: Julian Elischer To: John Baldwin In-Reply-To: <200405210959.25368.jhb@FreeBSD.org> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII cc: arch@FreeBSD.org cc: freebsd-arch@FreeBSD.org Subject: Re: atomic reference counting primatives. X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 21 May 2004 19:20:00 -0000 On Fri, 21 May 2004, John Baldwin wrote: > On Thursday 20 May 2004 10:54 pm, M. Warner Losh wrote: > > In message: > > > > > > Julian Elischer 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.