From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Matt Armstrong Newsgroups: gmane.emacs.devel Subject: Re: noverlay branch Date: Mon, 10 Oct 2022 11:32:16 -0700 Message-ID: <87r0zffs27.fsf@rfc20.org> References: <87sfjzefvv.fsf@rfc20.org> <875ygt6gbj.fsf@rfc20.org> <87edvf4p08.fsf@rfc20.org> Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-=" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="39039"; mail-complaints-to="usenet@ciao.gmane.io" Cc: emacs-devel@gnu.org To: Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Mon Oct 10 21:24:19 2022 Return-path: Envelope-to: ged-emacs-devel@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1ohyNu-0009vi-Nm for ged-emacs-devel@m.gmane-mx.org; Mon, 10 Oct 2022 21:24:18 +0200 Original-Received: from localhost ([::1]:60676 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1ohyNt-0002A4-3j for ged-emacs-devel@m.gmane-mx.org; Mon, 10 Oct 2022 15:24:17 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:46098) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ohxZm-0002ev-Em for emacs-devel@gnu.org; Mon, 10 Oct 2022 14:32:34 -0400 Original-Received: from relay9-d.mail.gandi.net ([217.70.183.199]:47913) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ohxZj-0002ec-4w for emacs-devel@gnu.org; Mon, 10 Oct 2022 14:32:29 -0400 Original-Received: (Authenticated sender: matt@rfc20.org) by mail.gandi.net (Postfix) with ESMTPSA id 253A2FF808; Mon, 10 Oct 2022 18:32:19 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=rfc20.org; s=gm1; t=1665426742; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=unvn+aLc3RS0VDDpYEb+FamuF6AEfJSAQf8+nVQZU7E=; b=f8rZkBI0PEyZ/kgOwFBDU+YPHtlJG72SzgkVxDlIyZk+1dlZV/Qh49qAJklnX/ddVcVzCu v7ziW55HZzWiUPyOilkkVhrRK+/ByQ6B+/ICcrLvQB53ODtGkjNugYb+nUHKnIOcbOUU+Y s+nDA4IenEUaNnRy27+/5ozkSPCY4ZWQeTVBHrkgHdjUweW0Bu9Hm4XqoYArAjs8qJ/eeK QAhihSoS3255LC5D+437Qx8GcRWpbUH1xWD/n0Y1pVz75B8iec+XHkFmCqbHiJx+IUxBpE jynY7M9UpSH/2J9+8QgxjWLsAvk0q2i1j2SNkk309u6+27KUBP+H9QXdHivjIA== Original-Received: from matt by naz with local (Exim 4.96) (envelope-from ) id 1ohxZZ-008LiJ-17; Mon, 10 Oct 2022 11:32:17 -0700 In-Reply-To: <87edvf4p08.fsf@rfc20.org> Received-SPF: pass client-ip=217.70.183.199; envelope-from=matt@rfc20.org; helo=relay9-d.mail.gandi.net X-Spam_score_int: -23 X-Spam_score: -2.4 X-Spam_bar: -- X-Spam_report: (-2.4 / 5.0 requ) BAYES_00=-1.9, DKIM_INVALID=0.1, DKIM_SIGNED=0.1, RCVD_IN_DNSWL_LOW=-0.7, RCVD_IN_MSPIKE_H2=-0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.io gmane.emacs.devel:297398 Archived-At: --=-=-= Content-Type: text/plain Matt Armstrong writes: > Stefan Monnier writes: > >>> In any case, I do have a new test for tests/src/buffer-tests.el that >>> crashes feature/noverlay Emacs immediately, when ENABLE_CHECKING is on, >>> in a spot in itree.c having to do with offset inheritance. >> >> I tightened up a few things and the code now passes the tests without >> crashing any more. > > Stefan, I now have four commits queued up on > https://git.sr.ht/~matta/emacs/log/feature/noverlay ...now 5 commits on https://git.sr.ht/~matta/emacs/log/feature/noverlay The latest makes all fields of the global itree_null sentinel node read-only. Because this property is only by convention, fragile, and difficult to verify by reading code, I'm going to look at removing itree_node entirely next. --=-=-= Content-Type: text/x-diff Content-Disposition: inline; filename=0005-Stop-reading-and-writing-the-itree_null.parent-field.patch >From b4bdbbcd47530ed80d941bd4bd6d57538ee33ca5 Mon Sep 17 00:00:00 2001 From: Matt Armstrong Date: Mon, 10 Oct 2022 10:45:05 -0700 Subject: [PATCH 5/5] Stop reading and writing the itree_null.parent field entirely. With this change all fields in the itree_null sentinel are read only. This makes accessing itree_null thread safe in an obvious way. Because it took two commits from two peole to get this right, I think we can call this design fragile and difficult to reason about. Another benefit of this commit is as preparation for removing sentinel node completely, and just using NULL. * src/itree.c (itree_null): Statically initialize itree_null.parent to NULL. It is never accessed. (null_is_sane): Assert parent == NULL. (interval_tree_remove_fix): Remove unecessary assignments to parent from node->parent. These were the last places itree_null.parent were read. (interval_tree_remove): Avoid an assignment to itree_null.parent through min->right->parent. (interval_tree_transplant): Avoid an assignment to itree_null.parent through source->parent. --- src/itree.c | 20 +++++++------------- 1 file changed, 7 insertions(+), 13 deletions(-) diff --git a/src/itree.c b/src/itree.c index 8d1dd00319..7b6a5039b3 100644 --- a/src/itree.c +++ b/src/itree.c @@ -146,7 +146,7 @@ Copyright (C) 2017-2022 Free Software Foundation, Inc. /* The sentinel node, the null node. */ struct interval_node itree_null = { - .parent = &itree_null, + .parent = NULL, /* never accessed */ .left = &itree_null, .right = &itree_null, .begin = PTRDIFF_MIN, @@ -162,12 +162,8 @@ Copyright (C) 2017-2022 Free Software Foundation, Inc. static bool null_is_sane (void) { - /* The sentinel node has most of its fields read-only. - - FIXME: PARENT is still read/write. It is written to - ininterval_tree_transplant, and later read. --matt - */ - /* eassert (itree_null.parent == &itree_null); */ + /* All sentinel node fields are read-only. */ + eassert (itree_null.parent == NULL); eassert (itree_null.left == &itree_null); eassert (itree_null.right == &itree_null); eassert (itree_null.begin == PTRDIFF_MIN); @@ -720,7 +716,6 @@ interval_tree_remove_fix (struct interval_tree *tree, other->red = false; parent->red = true; interval_tree_rotate_left (tree, parent); - parent = node->parent; other = parent->right; } @@ -739,7 +734,6 @@ interval_tree_remove_fix (struct interval_tree *tree, other->left->red = false; other->red = true; interval_tree_rotate_right (tree, other); - parent = node->parent; other = parent->right; } other->red = parent->red; /* 4.a */ @@ -759,7 +753,6 @@ interval_tree_remove_fix (struct interval_tree *tree, other->red = false; parent->red = true; interval_tree_rotate_right (tree, parent); - parent = node->parent; other = parent->left; } @@ -778,7 +771,6 @@ interval_tree_remove_fix (struct interval_tree *tree, other->right->red = false; other->red = true; interval_tree_rotate_left (tree, other); - parent = node->parent; other = parent->left; } @@ -859,7 +851,8 @@ interval_tree_remove (struct interval_tree *tree, struct interval_node *node) interval_tree_transplant (tree, min, node); /* We set min->right->parent after `interval_tree_transplant` so that calls to `itree_total_offset` don't get stuck in an inf-loop. */ - min->right->parent = min; + if (min->right != ITREE_NULL) + min->right->parent = min; interval_tree_update_limit (min); /* This call "belongs" with the first `interval_tree_transplant` (of `min_right`, done earlier in the `if`) but we prefer to do it @@ -1486,7 +1479,8 @@ interval_tree_transplant (struct interval_tree *tree, struct interval_node *sour else dest->parent->right = source; - source->parent = dest->parent; + if (source != ITREE_NULL) + source->parent = dest->parent; } -- 2.35.1 --=-=-=--