From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: ludo@gnu.org (Ludovic =?UTF-8?Q?Court=C3=A8s?=) Newsgroups: gmane.lisp.guile.bugs Subject: bug#28590: [PATCH 0/7] Attempt to reduce memory growth Date: Wed, 04 Oct 2017 15:09:17 +0200 Message-ID: <8760bv9i0y.fsf@gnu.org> References: <87poafkvsm.fsf@gnu.org> <20171003114352.13984-1-ludo@gnu.org> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-=" X-Trace: blaine.gmane.org 1507122632 31839 195.159.176.226 (4 Oct 2017 13:10:32 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Wed, 4 Oct 2017 13:10:32 +0000 (UTC) User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.3 (gnu/linux) Cc: 28590@debbugs.gnu.org To: wingo@igalia.com Original-X-From: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Wed Oct 04 15:10:16 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 1dzjRE-0006Xb-Oz for guile-bugs@m.gmane.org; Wed, 04 Oct 2017 15:10:13 +0200 Original-Received: from localhost ([::1]:35156 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1dzjRM-00033k-5Y for guile-bugs@m.gmane.org; Wed, 04 Oct 2017 09:10:20 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:43213) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1dzjRA-0002wT-GS for bug-guile@gnu.org; Wed, 04 Oct 2017 09:10:13 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1dzjR4-0008Qs-2E for bug-guile@gnu.org; Wed, 04 Oct 2017 09:10:08 -0400 Original-Received: from debbugs.gnu.org ([208.118.235.43]:39052) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1dzjR3-0008Qc-Up for bug-guile@gnu.org; Wed, 04 Oct 2017 09:10:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1dzjR3-00061j-P3; Wed, 04 Oct 2017 09:10:01 -0400 X-Loop: help-debbugs@gnu.org Resent-From: ludo@gnu.org (Ludovic =?UTF-8?Q?Court=C3=A8s?=) Original-Sender: "Debbugs-submit" Resent-CC: bug-guile@gnu.org Resent-Date: Wed, 04 Oct 2017 13:10:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 28590 X-GNU-PR-Package: guile X-GNU-PR-Keywords: Original-Received: via spool by 28590-submit@debbugs.gnu.org id=B28590.150712256923121 (code B ref 28590); Wed, 04 Oct 2017 13:10:01 +0000 Original-Received: (at 28590) by debbugs.gnu.org; 4 Oct 2017 13:09:29 +0000 Original-Received: from localhost ([127.0.0.1]:47733 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dzjQX-00060q-7i for submit@debbugs.gnu.org; Wed, 04 Oct 2017 09:09:29 -0400 Original-Received: from eggs.gnu.org ([208.118.235.92]:51965) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dzjQV-00060d-Cr for 28590@debbugs.gnu.org; Wed, 04 Oct 2017 09:09:27 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1dzjQO-0007hZ-KH for 28590@debbugs.gnu.org; Wed, 04 Oct 2017 09:09:22 -0400 Original-Received: from fencepost.gnu.org ([2001:4830:134:3::e]:56019) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1dzjQO-0007hF-Fn; Wed, 04 Oct 2017 09:09:20 -0400 Original-Received: from [2a01:e0a:1d:7270:6a6c:dc17:fc02:cfda] (port=49612 helo=ribbon) by fencepost.gnu.org with esmtpsa (TLS1.2:RSA_AES_256_CBC_SHA1:256) (Exim 4.82) (envelope-from ) id 1dzjQO-0006OY-0E; Wed, 04 Oct 2017 09:09:20 -0400 In-Reply-To: <20171003114352.13984-1-ludo@gnu.org> ("Ludovic \=\?utf-8\?Q\?Cou\?\= \=\?utf-8\?Q\?rt\=C3\=A8s\=22's\?\= message of "Tue, 3 Oct 2017 13:43:45 +0200") X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] 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:8849 Archived-At: --=-=-= Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Ludovic Court=C3=A8s skribis: > I=E2=80=99ll try to combine that with incremental marking of the weak tab= le, but > I=E2=80=99m not very hopeful. Here=E2=80=99s an attempt to mark tables incrementally. Unfortunately it misses references sometimes (e.g., values of a weak-key table do not get marked even though they should.) I=E2=80=99m unsure whether incremental marking is actually doable: the mark procedure only knows its own part of the mark state, not the global mark state. For instance, it cannot distinguish between different mark phases. I tried to fix that by memorizing the =E2=80=98GC_mark_no=E2=80=99= value we were in when we left the mark procedure, but that didn=E2=80=99t help. Ideas? Ludo=E2=80=99. --=-=-= Content-Type: text/x-patch Content-Disposition: inline diff --git a/libguile/weak-table.c b/libguile/weak-table.c index 1a99a130f..cec9ee8ae 100644 --- a/libguile/weak-table.c +++ b/libguile/weak-table.c @@ -1,4 +1,4 @@ -/* Copyright (C) 2011, 2012, 2013, 2014 Free Software Foundation, Inc. +/* Copyright (C) 2011, 2012, 2013, 2014, 2017 Free Software Foundation, Inc. * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public License @@ -94,6 +94,15 @@ typedef struct { scm_t_bits value; } scm_t_weak_entry; +#define WEAK_MAGIC 0x9876123450UL + +struct weak_mark_state +{ + unsigned long magic; /* distinguished magic number */ + unsigned long index; /* index where to resume marking */ + unsigned long count; /* number of entries in the array */ + scm_t_weak_entry *entries; /* pointer to the array of entries */ +}; struct weak_entry_data { scm_t_weak_entry *in; @@ -252,6 +261,7 @@ typedef struct { unsigned long upper; /* when to grow */ int size_index; /* index into hashtable_size */ int min_size_index; /* minimum size_index */ + struct weak_mark_state *mark_state; } scm_t_weak_table; @@ -288,7 +298,11 @@ rob_from_rich (scm_t_weak_table *table, unsigned long k) /* If we are to free up slot K in the table, we need room to do so. */ assert (table->n_items < size); - + + /* To be on the safe side, have the next mark phase start from the + beginning. */ + table->mark_state->index = 0; + empty = k; do empty = (empty + 1) % size; @@ -318,6 +332,10 @@ give_to_poor (scm_t_weak_table *table, unsigned long k) /* Slot K was just freed up; possibly shuffle others down. */ unsigned long size = table->size; + /* To be on the safe side, have the next mark phase start from the + beginning. */ + table->mark_state->index = 0; + while (1) { unsigned long next = (k + 1) % size; @@ -354,49 +372,96 @@ give_to_poor (scm_t_weak_table *table, unsigned long k) static int weak_key_gc_kind; static int weak_value_gc_kind; +extern GC_word GC_mark_no; + static struct GC_ms_entry * mark_weak_key_table (GC_word *addr, struct GC_ms_entry *mark_stack_ptr, struct GC_ms_entry *mark_stack_limit, GC_word env) { - scm_t_weak_entry *entries = (scm_t_weak_entry*) addr; - unsigned long k, size = GC_size (addr) / sizeof (scm_t_weak_entry); - - for (k = 0; k < size; k++) + struct weak_mark_state *state = (struct weak_mark_state *) addr; + scm_t_weak_entry *entries = state->entries; + unsigned long k, size = state->count; + unsigned long credit = GC_PROC_BYTES / sizeof (GC_word); + + if (state->magic != WEAK_MAGIC) + /* STATE might point to a freed element. */ + return mark_stack_ptr; + + for (k = state->index; + credit > 0 && k < size; + k++) if (entries[k].hash && entries[k].key) { SCM value = SCM_PACK (entries[k].value); - mark_stack_ptr = GC_MARK_AND_PUSH ((GC_word*) SCM2PTR (value), + mark_stack_ptr = GC_MARK_AND_PUSH ((GC_word *) SCM2PTR (value), mark_stack_ptr, mark_stack_limit, NULL); + credit--; } + if (k == size) + /* We marked ENTRIES till the end. */ + state->index = 0; + else + { + /* Save the current index and push ADDR back on the mark stack so + we can resume later. */ + state->index = k; + mark_stack_ptr = GC_MARK_AND_PUSH (addr, + mark_stack_ptr, mark_stack_limit, + NULL); + } + return mark_stack_ptr; } static struct GC_ms_entry * mark_weak_value_table (GC_word *addr, struct GC_ms_entry *mark_stack_ptr, - struct GC_ms_entry *mark_stack_limit, GC_word env) + struct GC_ms_entry *mark_stack_limit, GC_word env) { - scm_t_weak_entry *entries = (scm_t_weak_entry*) addr; - unsigned long k, size = GC_size (addr) / sizeof (scm_t_weak_entry); - - for (k = 0; k < size; k++) + struct weak_mark_state *state = (struct weak_mark_state *) addr; + scm_t_weak_entry *entries = state->entries; + unsigned long k, size = state->count; + unsigned long credit = GC_PROC_BYTES / sizeof (GC_word); + + if (state->magic != WEAK_MAGIC) + /* STATE might point to a freed element. */ + return mark_stack_ptr; + + for (k = state->index; + credit > 0 && k < size; + k++) if (entries[k].hash && entries[k].value) { SCM key = SCM_PACK (entries[k].key); - mark_stack_ptr = GC_MARK_AND_PUSH ((GC_word*) SCM2PTR (key), + mark_stack_ptr = GC_MARK_AND_PUSH ((GC_word *) SCM2PTR (key), mark_stack_ptr, mark_stack_limit, NULL); + credit--; } + if (k == size) + /* We marked ENTRIES till the end. */ + state->index = 0; + else + { + /* Save the current index and push ADDR back on the mark stack so + we can resume later. */ + state->index = k; + mark_stack_ptr = GC_MARK_AND_PUSH (addr, + mark_stack_ptr, mark_stack_limit, + NULL); + } + return mark_stack_ptr; } -static scm_t_weak_entry * + +static struct weak_mark_state * allocate_entries (unsigned long size, scm_t_weak_table_kind kind) { - scm_t_weak_entry *ret; - size_t bytes = size * sizeof (*ret); + struct weak_mark_state *ret; + size_t bytes = size * sizeof (scm_t_weak_entry) + sizeof *ret; switch (kind) { @@ -414,6 +479,9 @@ allocate_entries (unsigned long size, scm_t_weak_table_kind kind) } memset (ret, 0, bytes); + ret->magic = WEAK_MAGIC; + ret->count = size; + ret->entries = (scm_t_weak_entry *) ((char *) ret + sizeof (*ret)); return ret; } @@ -533,6 +601,7 @@ update_entry_count (scm_t_weak_table *table) static void resize_table (scm_t_weak_table *table) { + struct weak_mark_state *mark_state, *old_state; scm_t_weak_entry *old_entries, *new_entries; int new_size_index; unsigned long old_size, new_size, old_k; @@ -554,11 +623,13 @@ resize_table (scm_t_weak_table *table) } while (!is_acceptable_size_index (table, new_size_index)); - new_entries = allocate_entries (new_size, table->kind); + mark_state = allocate_entries (new_size, table->kind); + new_entries = mark_state->entries; old_entries = table->entries; old_size = table->size; - + + table->mark_state = mark_state; table->size_index = new_size_index; table->size = new_size; if (new_size_index <= table->min_size_index) @@ -618,6 +689,8 @@ resize_table (scm_t_weak_table *table) SCM_PACK (copy.key), SCM_PACK (copy.value), table->kind); } + + old_state->magic = 0; } /* Run after GC via do_vacuum_weak_table, this function runs over the @@ -807,6 +880,9 @@ weak_table_remove_x (scm_t_weak_table *table, unsigned long hash, hash = (hash << 1) | 0x1; k = hash_to_index (hash, size); + /* To be on the safe side, mark the whole array of entries again. */ + table->mark_state->index = 0; + for (distance = 0; distance < size; distance++, k = (k + 1) % size) { unsigned long other_hash; @@ -869,7 +945,8 @@ make_weak_table (unsigned long k, scm_t_weak_table_kind kind) n = hashtable_size[i]; table = scm_gc_malloc (sizeof (*table), "weak-table"); - table->entries = allocate_entries (n, kind); + table->mark_state = allocate_entries (n, kind); + table->entries = table->mark_state->entries; table->kind = kind; table->n_items = 0; table->size = n; --=-=-=--