From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Andy Wingo Newsgroups: gmane.lisp.guile.bugs Subject: bug#19180: Weak tables harmful to GC? Date: Tue, 31 Oct 2017 09:25:53 +0100 Message-ID: <877evbiuzy.fsf__7093.74309885806$1509438439$gmane$org@igalia.com> References: <87wp9gwz8m.fsf@gnu.org> <87fug4o8z2.fsf@pobox.com> <87wp54z3p5.fsf@gnu.org> <87zi9th1i6.fsf_-_@gnu.org> <87y3o454pr.fsf@gnu.org> <87r2tvncs5.fsf@dustycloud.org> <87wp3mwwef.fsf@gnu.org> <87mv4gd0ik.fsf@elephly.net> <87a80eie63.fsf@gnu.org> <87k1zimhmt.fsf@elephly.net> <87bmktn96e.fsf@elephly.net> <87tvyl9n22.fsf@gnu.org> <87r2tnlhno.fsf@elephly.net> <87a8087qz7.fsf@gnu.org> <87she0lf1y.fsf@igalia.com> <87zi88ut3k.fsf@gnu.org> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-=" X-Trace: blaine.gmane.org 1509438439 9764 195.159.176.226 (31 Oct 2017 08:27:19 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Tue, 31 Oct 2017 08:27:19 +0000 (UTC) User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.2 (gnu/linux) Cc: 19180@debbugs.gnu.org, Ricardo Wurmus , guile-devel@gnu.org To: ludo@gnu.org (Ludovic =?UTF-8?Q?Court=C3=A8s?=) Original-X-From: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Tue Oct 31 09:27:14 2017 Return-path: Envelope-to: guile-bugs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1e9Rt4-0001IK-RP for guile-bugs@m.gmane.org; Tue, 31 Oct 2017 09:27:07 +0100 Original-Received: from localhost ([::1]:44222 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1e9RtC-0004zT-A0 for guile-bugs@m.gmane.org; Tue, 31 Oct 2017 04:27:14 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:52367) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1e9Rt5-0004yt-8G for bug-guile@gnu.org; Tue, 31 Oct 2017 04:27:09 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1e9Rt1-0004Uk-V1 for bug-guile@gnu.org; Tue, 31 Oct 2017 04:27:07 -0400 Original-Received: from debbugs.gnu.org ([208.118.235.43]:34477) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1e9Rt1-0004UQ-QM for bug-guile@gnu.org; Tue, 31 Oct 2017 04:27:03 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1e9Rt0-0003si-8x for bug-guile@gnu.org; Tue, 31 Oct 2017 04:27:03 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Andy Wingo Original-Sender: "Debbugs-submit" Resent-CC: bug-guile@gnu.org Resent-Date: Tue, 31 Oct 2017 08:27:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 19180 X-GNU-PR-Package: guile X-GNU-PR-Keywords: Original-Received: via spool by 19180-submit@debbugs.gnu.org id=B19180.150943836714855 (code B ref 19180); Tue, 31 Oct 2017 08:27:02 +0000 Original-Received: (at 19180) by debbugs.gnu.org; 31 Oct 2017 08:26:07 +0000 Original-Received: from localhost ([127.0.0.1]:43158 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1e9Rs5-0003rV-C1 for submit@debbugs.gnu.org; Tue, 31 Oct 2017 04:26:07 -0400 Original-Received: from pb-sasl1.pobox.com ([64.147.108.66]:53551 helo=sasl.smtp.pobox.com) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1e9Rs3-0003rL-J5 for 19180@debbugs.gnu.org; Tue, 31 Oct 2017 04:26:04 -0400 Original-Received: from sasl.smtp.pobox.com (unknown [127.0.0.1]) by pb-sasl1.pobox.com (Postfix) with ESMTP id DB9DA9F411; Tue, 31 Oct 2017 04:26:02 -0400 (EDT) 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=LYtEwACY5SHYy+adzJRj7w74yUE=; b=tnvGic kJhsCd8EWv7UlibEO61enQbusJHWcfu3TfEUdm1yHAGHSa6OW3PeKaxIpoglThjj OivHNIu9Qedr/uVSRjFMUqUjuS+60UfxPhkMTwH8QpddLZkka8bkLvTlO6HAiC3k NBmSx1D9UkCJvOYaVvt47l5R0ddjd9ZSV9YME= Original-Received: from pb-sasl1.nyi.icgroup.com (unknown [127.0.0.1]) by pb-sasl1.pobox.com (Postfix) with ESMTP id D1EFF9F40F; Tue, 31 Oct 2017 04:26:02 -0400 (EDT) Original-Received: from sparrow (unknown [88.160.190.192]) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by pb-sasl1.pobox.com (Postfix) with ESMTPSA id DDA5E9F40D; Tue, 31 Oct 2017 04:26:00 -0400 (EDT) In-Reply-To: <87zi88ut3k.fsf@gnu.org> ("Ludovic =?UTF-8?Q?Court=C3=A8s?="'s message of "Tue, 31 Oct 2017 00:13:51 +0100") X-Pobox-Relay-ID: 20D608DA-BE15-11E7-905F-ABEFD5707B88-02397024!pb-sasl1.pobox.com X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 208.118.235.43 X-BeenThere: bug-guile@gnu.org List-Id: "Bug reports for GUILE, GNU's Ubiquitous Extension Language" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Original-Sender: "bug-guile" Xref: news.gmane.org gmane.lisp.guile.bugs:8877 Archived-At: --=-=-= Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable On Tue 31 Oct 2017 00:13, ludo@gnu.org (Ludovic Court=C3=A8s) writes: > I built libguile with the patch (I haven=E2=80=99t yet taken the time to = rebuild > all of Guile). It works, but unfortunately it still shows quick growth > of the heap on this example (): Fixed in attached patches (on top of the other one). This was a race between the periodic vacuum process, which should run after GC via a finalizer, and the mutator. If the mutator had the weak table lock, the vacuum would never be run. Of course in the test below, the mutator usually has the table lock, so we ended up often skipping the vacuum, which causes the table size to grow, which causes the active heap size to grow, which causes the bytes-allocated-before-GC to increase, and which ultimately is a vicious circle. In my tests this patch fixes the issue, though the level at which the heap stabilizes can vary slightly as there's a bit of nondeterministic concurrency as the mutator and the vacuum process still race a bit. Right now for me it stabilizes at about 6.2M of heap. >> weak_key_gc_kind =3D >> GC_new_kind (GC_new_free_list (), >> - GC_MAKE_PROC (GC_new_proc (mark_weak_key_table), 0), >> + GC_MAKE_PROC (GC_new_proc (mark_weak_key_entry), 0), >> 0, 0); > > I think we should avoid custom mark procedures and use a bitmap here, as > recommended in the libgc headers (like =E2=80=98wcar_pair_descr=E2=80=99 = in weaks.c in > 2.0.) Good idea; fixed. Andy --=-=-= Content-Type: text/x-patch Content-Disposition: inline; filename=0002-Refactor-weak-table-to-use-bitmaps-for-weak-entries.patch >From 098c4171ef53791d97b5c675218f302efc7bcf26 Mon Sep 17 00:00:00 2001 From: Andy Wingo Date: Tue, 31 Oct 2017 09:10:55 +0100 Subject: [PATCH 2/3] Refactor weak table to use bitmaps for weak entries --- libguile/weak-table.c | 107 ++++++++++++-------------------------------------- 1 file changed, 25 insertions(+), 82 deletions(-) diff --git a/libguile/weak-table.c b/libguile/weak-table.c index ff8a01fb0..fab98149f 100644 --- a/libguile/weak-table.c +++ b/libguile/weak-table.c @@ -25,7 +25,7 @@ #include #include "libguile/bdw-gc.h" -#include +#include #include "libguile/_scm.h" #include "libguile/hash.h" @@ -152,70 +152,10 @@ typedef struct { -/* The GC "kinds" for singly-weak tables. */ -static int weak_key_gc_kind; -static int weak_value_gc_kind; -static int doubly_weak_gc_kind; - -static struct GC_ms_entry * -mark_weak_key_entry (GC_word *addr, struct GC_ms_entry *mark_stack_ptr, - struct GC_ms_entry *mark_stack_limit, GC_word env) -{ - scm_t_weak_entry *entry = (scm_t_weak_entry*) addr; - - if (entry->next) - mark_stack_ptr = GC_MARK_AND_PUSH ((GC_word*) entry->next, - mark_stack_ptr, mark_stack_limit, - NULL); - - if (entry->hash && entry->key) - { - SCM value = SCM_PACK (entry->value); - if (SCM_HEAP_OBJECT_P (value)) - mark_stack_ptr = GC_MARK_AND_PUSH ((GC_word*) SCM2PTR (value), - mark_stack_ptr, mark_stack_limit, - NULL); - } - - return mark_stack_ptr; -} - -static struct GC_ms_entry * -mark_weak_value_entry (GC_word *addr, struct GC_ms_entry *mark_stack_ptr, - struct GC_ms_entry *mark_stack_limit, GC_word env) -{ - scm_t_weak_entry *entry = (scm_t_weak_entry*) addr; - - if (entry->next) - mark_stack_ptr = GC_MARK_AND_PUSH ((GC_word*) entry->next, - mark_stack_ptr, mark_stack_limit, - NULL); - - if (entry->hash && entry->value) - { - SCM key = SCM_PACK (entry->key); - if (SCM_HEAP_OBJECT_P (key)) - mark_stack_ptr = GC_MARK_AND_PUSH ((GC_word*) SCM2PTR (key), - mark_stack_ptr, mark_stack_limit, - NULL); - } - - return mark_stack_ptr; -} - -static struct GC_ms_entry * -mark_doubly_weak_entry (GC_word *addr, struct GC_ms_entry *mark_stack_ptr, - struct GC_ms_entry *mark_stack_limit, GC_word env) -{ - scm_t_weak_entry *entry = (scm_t_weak_entry*) addr; - - if (entry->next) - mark_stack_ptr = GC_MARK_AND_PUSH ((GC_word*) entry->next, - mark_stack_ptr, mark_stack_limit, - NULL); - - return mark_stack_ptr; -} +/* GC descriptors for the various kinds of scm_t_weak_entry. */ +static GC_descr weak_key_descr; +static GC_descr weak_value_descr; +static GC_descr doubly_weak_descr; static scm_t_weak_entry * allocate_entry (scm_t_weak_table_kind kind) @@ -225,20 +165,18 @@ allocate_entry (scm_t_weak_table_kind kind) switch (kind) { case SCM_WEAK_TABLE_KIND_KEY: - ret = GC_generic_malloc (sizeof (*ret), weak_key_gc_kind); + ret = GC_malloc_explicitly_typed (sizeof (*ret), weak_key_descr); break; case SCM_WEAK_TABLE_KIND_VALUE: - ret = GC_generic_malloc (sizeof (*ret), weak_value_gc_kind); + ret = GC_malloc_explicitly_typed (sizeof (*ret), weak_value_descr); break; case SCM_WEAK_TABLE_KIND_BOTH: - ret = GC_generic_malloc (sizeof (*ret), doubly_weak_gc_kind); + ret = GC_malloc_explicitly_typed (sizeof (*ret), doubly_weak_descr); break; default: abort (); } - memset (ret, 0, sizeof (*ret)); - return ret; } @@ -852,18 +790,23 @@ SCM_DEFINE (scm_doubly_weak_hash_table_p, "doubly-weak-hash-table?", 1, 0, 0, void scm_weak_table_prehistory (void) { - weak_key_gc_kind = - GC_new_kind (GC_new_free_list (), - GC_MAKE_PROC (GC_new_proc (mark_weak_key_entry), 0), - 0, 0); - weak_value_gc_kind = - GC_new_kind (GC_new_free_list (), - GC_MAKE_PROC (GC_new_proc (mark_weak_value_entry), 0), - 0, 0); - doubly_weak_gc_kind = - GC_new_kind (GC_new_free_list (), - GC_MAKE_PROC (GC_new_proc (mark_doubly_weak_entry), 0), - 0, 0); + GC_word weak_key_bitmap[GC_BITMAP_SIZE (scm_t_weak_entry)] = { 0 }; + GC_word weak_value_bitmap[GC_BITMAP_SIZE (scm_t_weak_entry)] = { 0 }; + GC_word doubly_weak_bitmap[GC_BITMAP_SIZE (scm_t_weak_entry)] = { 0 }; + + GC_set_bit (weak_key_bitmap, GC_WORD_OFFSET (scm_t_weak_entry, next)); + GC_set_bit (weak_value_bitmap, GC_WORD_OFFSET (scm_t_weak_entry, next)); + GC_set_bit (doubly_weak_bitmap, GC_WORD_OFFSET (scm_t_weak_entry, next)); + + GC_set_bit (weak_key_bitmap, GC_WORD_OFFSET (scm_t_weak_entry, value)); + GC_set_bit (weak_value_bitmap, GC_WORD_OFFSET (scm_t_weak_entry, key)); + + weak_key_descr = GC_make_descriptor (weak_key_bitmap, + GC_WORD_LEN (scm_t_weak_entry)); + weak_value_descr = GC_make_descriptor (weak_value_bitmap, + GC_WORD_LEN (scm_t_weak_entry)); + doubly_weak_descr = GC_make_descriptor (doubly_weak_bitmap, + GC_WORD_LEN (scm_t_weak_entry)); } void -- 2.14.1 --=-=-= Content-Type: text/x-patch Content-Disposition: inline; filename=0003-More-robust-vacuuming-of-in-use-weak-tables.patch >From 3304f9dc2cf106426570acc8437b4e39fe5edf91 Mon Sep 17 00:00:00 2001 From: Andy Wingo Date: Tue, 31 Oct 2017 08:43:09 +0100 Subject: [PATCH 3/3] More robust vacuuming of in-use weak tables * libguile/weak-table.c (scm_t_weak_table); Add last_gc_no member. * libguile/weak-table.c (vacuum_weak_table): Only vacuum if we haven't done so since the last GC. (scm_c_weak_table_ref, scm_c_weak_table_put_x, scm_c_weak_table_remove_x) (scm_c_weak_table_fold): Vacuum the weak table if needed. (scm_weak_table_clear_x): Update last_gc_no flag, as no more vacuuming will be needed. --- libguile/weak-table.c | 25 ++++++++++++++++++++++--- 1 file changed, 22 insertions(+), 3 deletions(-) diff --git a/libguile/weak-table.c b/libguile/weak-table.c index fab98149f..461d4a47c 100644 --- a/libguile/weak-table.c +++ b/libguile/weak-table.c @@ -31,7 +31,6 @@ #include "libguile/hash.h" #include "libguile/eval.h" #include "libguile/ports.h" - #include "libguile/validate.h" #include "libguile/weak-list.h" #include "libguile/weak-table.h" @@ -141,6 +140,7 @@ typedef struct { unsigned long upper; /* when to grow */ int size_index; /* index into hashtable_size */ int min_size_index; /* minimum size_index */ + GC_word last_gc_no; } scm_t_weak_table; @@ -275,8 +275,14 @@ resize_table (scm_t_weak_table *table) static void vacuum_weak_table (scm_t_weak_table *table) { + GC_word gc_no = GC_get_gc_no (); unsigned long k; + if (gc_no == table->last_gc_no) + return; + + table->last_gc_no = gc_no; + for (k = 0; k < table->n_buckets; k++) { scm_t_weak_entry **loc = table->buckets + k; @@ -427,6 +433,7 @@ make_weak_table (unsigned long k, scm_t_weak_table_kind kind) table->upper = 9 * n / 10; table->size_index = i; table->min_size_index = i; + table->last_gc_no = GC_get_gc_no (); scm_i_pthread_mutex_init (&table->lock, NULL); return scm_cell (scm_tc7_weak_table, (scm_t_bits)table); @@ -456,8 +463,10 @@ do_vacuum_weak_table (SCM table) custom predicate, or via finalizers run explicitly by (gc) or in an async (for non-threaded Guile). We add a restriction that prohibits the first case, by convention. But since we can't - prohibit the second case, here we trylock instead of lock. Not so - nice. */ + prohibit the second case, here we trylock instead of lock. In any + case, if the mutex is held by another thread, then the table is in + active use, so the next user of the table will handle the vacuum + for us. */ if (scm_i_pthread_mutex_trylock (&t->lock) == 0) { vacuum_weak_table (t); @@ -513,6 +522,8 @@ scm_c_weak_table_ref (SCM table, unsigned long raw_hash, scm_i_pthread_mutex_lock (&t->lock); + vacuum_weak_table (t); + ret = weak_table_ref (t, raw_hash, pred, closure, dflt); scm_i_pthread_mutex_unlock (&t->lock); @@ -535,6 +546,8 @@ scm_c_weak_table_put_x (SCM table, unsigned long raw_hash, scm_i_pthread_mutex_lock (&t->lock); + vacuum_weak_table (t); + weak_table_put_x (t, raw_hash, pred, closure, key, value); scm_i_pthread_mutex_unlock (&t->lock); @@ -555,6 +568,8 @@ scm_c_weak_table_remove_x (SCM table, unsigned long raw_hash, scm_i_pthread_mutex_lock (&t->lock); + vacuum_weak_table (t); + weak_table_remove_x (t, raw_hash, pred, closure); scm_i_pthread_mutex_unlock (&t->lock); @@ -604,6 +619,8 @@ scm_weak_table_clear_x (SCM table) scm_i_pthread_mutex_lock (&t->lock); + t->last_gc_no = GC_get_gc_no (); + for (k = 0; k < t->n_buckets; k++) { for (entry = t->buckets[k]; entry; entry = entry->next) @@ -628,6 +645,8 @@ scm_c_weak_table_fold (scm_t_table_fold_fn proc, void *closure, scm_i_pthread_mutex_lock (&t->lock); + vacuum_weak_table (t); + for (k = 0; k < t->n_buckets; k++) { scm_t_weak_entry *entry; -- 2.14.1 --=-=-=--