From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Andy Wingo Newsgroups: gmane.lisp.guile.devel Subject: Re: [PATCH] Efficient Gensym Hack (v2) Date: Wed, 07 Mar 2012 18:25:49 +0100 Message-ID: <87vcmgz5k2.fsf@pobox.com> References: <87mx7vx8zg.fsf@netris.org> <87pqcqvysj.fsf@netris.org> <8762eg1ypg.fsf@pobox.com> <878vjcwedw.fsf@netris.org> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: dough.gmane.org 1331141202 25136 80.91.229.3 (7 Mar 2012 17:26:42 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Wed, 7 Mar 2012 17:26:42 +0000 (UTC) Cc: Ken Raeburn , guile-devel@gnu.org To: Mark H Weaver Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Wed Mar 07 18:26:39 2012 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1S5KdE-0005Yu-V5 for guile-devel@m.gmane.org; Wed, 07 Mar 2012 18:26:33 +0100 Original-Received: from localhost ([::1]:53784 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1S5KdE-0003wz-9o for guile-devel@m.gmane.org; Wed, 07 Mar 2012 12:26:32 -0500 Original-Received: from eggs.gnu.org ([208.118.235.92]:43213) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1S5Kco-0003ut-Kr for guile-devel@gnu.org; Wed, 07 Mar 2012 12:26:30 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1S5Kch-0004Wj-Pw for guile-devel@gnu.org; Wed, 07 Mar 2012 12:26:06 -0500 Original-Received: from a-pb-sasl-sd.pobox.com ([74.115.168.62]:48091 helo=sasl.smtp.pobox.com) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1S5Kch-0004Wb-Gc for guile-devel@gnu.org; Wed, 07 Mar 2012 12:25:59 -0500 Original-Received: from sasl.smtp.pobox.com (unknown [127.0.0.1]) by a-pb-sasl-sd.pobox.com (Postfix) with ESMTP id E0990962A; Wed, 7 Mar 2012 12:25:56 -0500 (EST) DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=pobox.com; h=from:to:cc :subject:references:date:in-reply-to:message-id:mime-version :content-type; s=sasl; bh=bp0VvGcmRbCskvdFKmuiyEapPag=; b=vqDizQ kJj4piGCasT4KAc6xEPmFIDTcdHkmr88W5QY5Zd5j+wcItCoeEiUSSDqSVoQPyeI srwQL1VM33Gm4EP/XLcG4Mq8GL+QzXzDUQ8d0si03QSvkPWV1IUjUpc7jFFuPQVT 63ds4PeYs8yDZG6sezHRje6k4ua4O4XQt6OEw= DomainKey-Signature: a=rsa-sha1; c=nofws; d=pobox.com; h=from:to:cc :subject:references:date:in-reply-to:message-id:mime-version :content-type; q=dns; s=sasl; b=Y/iTgC98jeHI+rzSXwkmYpsw8v9WvPQ/ Y+cwxLzxZftFC+FGDHn8uSEN5BECcUPtMrYRMObYAGaPk2FAeyzwWGp/JCJPhrLy 3nHTEqDVXe1sgRmyyxWfjvhTXdCMogHYL4OtXfiL4gwAoxWYxNQaG04ycYTeCyLq khMr8g4uZU4= Original-Received: from a-pb-sasl-sd.pobox.com (unknown [127.0.0.1]) by a-pb-sasl-sd.pobox.com (Postfix) with ESMTP id D826D9629; Wed, 7 Mar 2012 12:25:56 -0500 (EST) Original-Received: from badger (unknown [90.163.36.96]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by a-pb-sasl-sd.pobox.com (Postfix) with ESMTPSA id 6998F9628; Wed, 7 Mar 2012 12:25:55 -0500 (EST) In-Reply-To: <878vjcwedw.fsf@netris.org> (Mark H. Weaver's message of "Wed, 07 Mar 2012 11:43:23 -0500") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.3 (gnu/linux) X-Pobox-Relay-ID: 98BE812A-687A-11E1-80FD-65B1DE995924-02397024!a-pb-sasl-sd.pobox.com X-detected-operating-system: by eggs.gnu.org: Solaris 10 (beta) X-Received-From: 74.115.168.62 X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Original-Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.devel:14040 Archived-At: Hi Mark! Thanks for the response. I have various minor thoughts here and one serious note on GC. On Wed 07 Mar 2012 17:43, Mark H Weaver writes: >>> + if (!STRINGBUF_SHARED (buf)) >>> + { >>> + scm_i_pthread_mutex_lock (&stringbuf_write_mutex); >>> + SCM_SET_CELL_WORD_0 (buf, SCM_CELL_WORD_0 (buf) | STRINGBUF_F_SHARED); >>> + scm_i_pthread_mutex_unlock (&stringbuf_write_mutex); >>> + } >> >> Does this work, with C's memory model? > > That's true. However, in that case, the shared flag is already being > set by another thread, so it doesn't matter, because the only > requirement of this function is to make sure the flag gets set. I think it will be fine. Thanks for walking through it with me. >>> + /* Attempt to intern the symbol */ >>> + handle = scm_hash_fn_create_handle_x (symbols, sym, SCM_UNDEFINED, >>> + symbol_lookup_hash_fn, >>> + symbol_lookup_assoc_fn, >>> + NULL); >>> + } while (SCM_UNLIKELY (!scm_is_eq (sym, SCM_CAR (handle)))); >> >> Note that this is racy: this is a weak key hash table, so it's not safe >> to access the car of the handle outside the alloc lock. > > It's not an issue here, because the only thing I'm doing with the 'car' > is checking that it's 'eq?' to the lazy gensym that's being forced. If > it _is_ 'eq?' to our gensym, then there's no possibility that it will be > nulled out, because we hold a reference to it. If it's _not_ 'eq?' to > our gensym, then we don't care whether it's null or not; in either case > we have failed to intern this name and we try again with the next > counter value. > > However, note that 'intern_symbol', 'lookup_interned_symbol', and > 'lookup_interned_latin1_symbol' all access the 'car' of a handle of the > symbol table outside of the alloc lock, and those might indeed be > problems. Those issues are not from this patch though. The relevant > code was last changed by you in 2011. Yes, it was part of an attempt to correct this situation, and part of a learning process as well. I'm more satisfied with master's correctness in this regard. >>> + /* We must not clear the lazy gensym flag until our symbol has >>> + been interned. The lock does not save us here, because another >>> + thread could retrieve our gensym's name or hash outside of any >>> + lock. */ >>> + SCM_SET_CELL_WORD_0 (sym, (SCM_CELL_WORD_0 (sym) >>> + & ~SCM_I_F_SYMBOL_LAZY_GENSYM)); >>> + } >>> + scm_i_pthread_mutex_unlock (&symbols_lock); >>> +} >> >> Doing all this work within a mutex is prone to deadlock, if allocation >> causes a finalizer to run that forces another lazy symbol. > > Ugh. Well, we already have a problem then, because 'intern_symbol' also > does allocation while holding this lock, via 'symbol_lookup_assoc_fn', > which calls 'scm_symbol_to_string', which must allocate the string > object (symbols hold only stringbufs). Therefore, with Guile 2.0.5, if > anyone calls 'scm_from_*_symbol' within a finalizer, there is already > the possibility for deadlock. Yuck. > Have I mentioned lately how much I hate locks? :/ :) Locks aren't really the problem here though -- it's the finalizer-introduced concurrency, specifically in the case in which your program is in a critical section. If we ran finalizers in a separate thread, we would not have these issues. > The good news is that it should be possible to fix this (pre-existing) > class of problems for 'symbols_lock' in stable-2.0 by changing > 'symbol_lookup_assoc_fn' to avoid allocation. That's not enough. Adding spine segments, ribs, and associating a disappearing link all allocate memory, and those are internal to the hash table implementation. ^ The serious note :) Maybe you'll never hit it. I don't know. It depends very much on your allocation pattern. What's the likelihood that a finalizer accesses a symbol's characters? Who knows. Maybe it's good enough to document this defect in 2.0. "Don't try to string->symbol or symbol->string in a finalizer". Andy -- http://wingolog.org/