GNU bug report logs - #78943
feature/igc [PATCH] Trace current minor maps exactly

Previous Next

To reply to this bug, email your comments to 78943 AT debbugs.gnu.org.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Helmut Eller <eller.helmut <at> gmail.com>
To: bug-gnu-emacs <at> gnu.org
Subject: feature/igc [PATCH] Trace current minor maps exactly
Date: Wed, 02 Jul 2025 14:28:44 +0200

[Message part 1 (text/plain, inline)]

Tags: patch

[0001-Trace-current-minor-maps-exactly.patch (text/x-diff, attachment)]

Message #8 received at 78943 <at> debbugs.gnu.org (full text, mbox):

From: Pip Cet <pipcet <at> protonmail.com>
To: Helmut Eller <eller.helmut <at> gmail.com>
Cc: 78943 <at> debbugs.gnu.org
Subject: Re: bug#78943: feature/igc [PATCH] Trace current minor maps exactly
Date: Wed, 09 Jul 2025 14:29:29 +0000

"Helmut Eller" <eller.helmut <at> gmail.com> writes:

> From 3a1a4549a0545afbddc96a87b404b6c7b835d5b7 Mon Sep 17 00:00:00 2001
> From: Helmut Eller <eller.helmut <at> gmail.com>
> Date: Wed, 2 Jul 2025 14:10:56 +0200
> Subject: [PATCH] Trace current minor maps exactly
>
> * src/keymap.c (current_minor_maps): Use igc_xalloc_lisp_objs_exact
> instead of igc_xzalloc_ambig.

Thanks, LGTM.  Hope that applies to the other accumulated patches, too,
then I'll install them all.

This is a preexisting bug, but I'm suspicious about the code leaking a
pointer to an igc_xzalloc'd area to its caller, which may call Lisp
(when it autoloads a map) in the case of Fminor_mode_key_binding.  If
that Lisp code recursively accesses keymaps and the maps get
reallocated, we end up resurrecting free'd data, and will probably
crash.  (My suspicion is this is the reason for the "don't use realloc"
comment, too).

We should really fix this on master and just use vectors, and it's
probably even less effort for you to do so than it is for me, but I
still don't get how code like this is meant to be fixed.

(I hope the comment about static being defined to the empty string is no
longer accurate :-) ).

Pip

Message #11 received at 78943 <at> debbugs.gnu.org (full text, mbox):

From: Helmut Eller <eller.helmut <at> gmail.com>
To: Pip Cet <pipcet <at> protonmail.com>
Cc: 78943 <at> debbugs.gnu.org
Subject: Re: bug#78943: feature/igc [PATCH] Trace current minor maps exactly
Date: Fri, 11 Jul 2025 23:10:15 +0200

[Message part 1 (text/plain, inline)]

On Wed, Jul 09 2025, Pip Cet wrote:

[...]
> Thanks, LGTM.  Hope that applies to the other accumulated patches, too,
> then I'll install them all.

Thanks.

> This is a preexisting bug, but I'm suspicious about the code leaking a
> pointer to an igc_xzalloc'd area to its caller, which may call Lisp
> (when it autoloads a map) in the case of Fminor_mode_key_binding.  If
> that Lisp code recursively accesses keymaps and the maps get
> reallocated, we end up resurrecting free'd data, and will probably
> crash.  (My suspicion is this is the reason for the "don't use realloc"
> comment, too).
>
> We should really fix this on master and just use vectors, and it's
> probably even less effort for you to do so than it is for me, but I
> still don't get how code like this is meant to be fixed.
>
> (I hope the comment about static being defined to the empty string is no
> longer accurate :-) ).

:-) That's a curious comment.  The overflow check in current_minor_maps
is also curious.

A simple fix for Fminor_mode_key_binding would be to copy the modes and
maps arrays to an alloca'd area before calling Flookup_key.

In the patch below (for master) I tried something different: remove the
global variables cmm_maps and cmm_modes entirely.

Assuming that there are rarely more than a handful of minor modes
active, we can allocate the temporary arrays on the stack; for the case
with very many minor modes we use the GC heap.

The patch uses the GC heap if there are more than 16 minor mode keymaps
active.  I'm not sure if that is enough; viper mode already activates 8.

A nice aspect of the patch is that Fcurrent_active_maps no longer uses
the temparary arrays: the code in the patch knows how to build a list in
reverse order.  So with the patch, current_minor_maps is called less
frequently.  The most frequent callers are now tool_bar_items and
tab_bar_items which call current_minor_maps when the user scrolls
around.

Helmut

[0001-Eliminate-the-global-arrays-cmm_modes-and-cmm_maps.patch (text/x-diff, attachment)]

Message #14 received at 78943 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Helmut Eller <eller.helmut <at> gmail.com>,
 Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: pipcet <at> protonmail.com, 78943 <at> debbugs.gnu.org
Subject: Re: bug#78943: feature/igc [PATCH] Trace current minor maps exactly
Date: Sat, 12 Jul 2025 09:19:59 +0300

> Cc: 78943 <at> debbugs.gnu.org
> From: Helmut Eller <eller.helmut <at> gmail.com>
> Date: Fri, 11 Jul 2025 23:10:15 +0200
> 
> A simple fix for Fminor_mode_key_binding would be to copy the modes and
> maps arrays to an alloca'd area before calling Flookup_key.
> 
> In the patch below (for master) I tried something different: remove the
> global variables cmm_maps and cmm_modes entirely.
> 
> Assuming that there are rarely more than a handful of minor modes
> active, we can allocate the temporary arrays on the stack; for the case
> with very many minor modes we use the GC heap.

We usually don't use the stack for any data larger than 16KB.  Does
this case fit that limit?

> The patch uses the GC heap if there are more than 16 minor mode keymaps
> active.  I'm not sure if that is enough; viper mode already activates 8.
> 
> A nice aspect of the patch is that Fcurrent_active_maps no longer uses
> the temparary arrays: the code in the patch knows how to build a list in
> reverse order.  So with the patch, current_minor_maps is called less
> frequently.  The most frequent callers are now tool_bar_items and
> tab_bar_items which call current_minor_maps when the user scrolls
> around.

Thanks, but please also explain why we should install something like
this on master and not on the igc branch, since the discussion started
from the latter.  What advantages will this get us on master?

Adding Stefan to the discussion.

Message #17 received at 78943 <at> debbugs.gnu.org (full text, mbox):

From: Helmut Eller <eller.helmut <at> gmail.com>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: pipcet <at> protonmail.com, Stefan Monnier <monnier <at> iro.umontreal.ca>,
 78943 <at> debbugs.gnu.org
Subject: Re: bug#78943: feature/igc [PATCH] Trace current minor maps exactly
Date: Sat, 12 Jul 2025 11:05:36 +0200

On Sat, Jul 12 2025, Eli Zaretskii wrote:

>> Cc: 78943 <at> debbugs.gnu.org
>> From: Helmut Eller <eller.helmut <at> gmail.com>
>> Date: Fri, 11 Jul 2025 23:10:15 +0200
>> 
>> A simple fix for Fminor_mode_key_binding would be to copy the modes and
>> maps arrays to an alloca'd area before calling Flookup_key.
>> 
>> In the patch below (for master) I tried something different: remove the
>> global variables cmm_maps and cmm_modes entirely.
>> 
>> Assuming that there are rarely more than a handful of minor modes
>> active, we can allocate the temporary arrays on the stack; for the case
>> with very many minor modes we use the GC heap.
>
> We usually don't use the stack for any data larger than 16KB.  Does
> this case fit that limit?

Yes: sizeof (struct cmm_vector) == 288.

>> The patch uses the GC heap if there are more than 16 minor mode keymaps
>> active.  I'm not sure if that is enough; viper mode already activates 8.
>> 
>> A nice aspect of the patch is that Fcurrent_active_maps no longer uses
>> the temparary arrays: the code in the patch knows how to build a list in
>> reverse order.  So with the patch, current_minor_maps is called less
>> frequently.  The most frequent callers are now tool_bar_items and
>> tab_bar_items which call current_minor_maps when the user scrolls
>> around.
>
> Thanks, but please also explain why we should install something like
> this on master and not on the igc branch, since the discussion started
> from the latter.

The main reason is that Pip said: "We should really fix this on master
and just use vectors..."

> What advantages will this get us on master?

On master, current_minor_maps returns a pointer to a buffer.  That
pointer is safe to use only until the next call to current_minor_maps.
This constraint is easy to forget: Fminor_mode_key_binding uses the
pointer for longer than that.

(Fminor_mode_key_binding calls Flookup_key which can execute arbitrary
Lisp code and hence could call current_minor_maps while the pointer to
the buffer is still used.).

With the patch, this bug would be fixed; that's only a tiny advantage
because in practice the problem occurs extremely rarely.

A more important advantage would be that it reduces "mental load"
because the new current_minor_maps is easier to use.

Helmut

Message #20 received at 78943 <at> debbugs.gnu.org (full text, mbox):

From: Pip Cet <pipcet <at> protonmail.com>
To: Helmut Eller <eller.helmut <at> gmail.com>
Cc: 78943 <at> debbugs.gnu.org
Subject: Re: bug#78943: feature/igc [PATCH] Trace current minor maps exactly
Date: Sat, 12 Jul 2025 10:17:27 +0000

"Helmut Eller" <eller.helmut <at> gmail.com> writes:

> On Wed, Jul 09 2025, Pip Cet wrote:
>
> [...]
>> Thanks, LGTM.  Hope that applies to the other accumulated patches, too,
>> then I'll install them all.
>
> Thanks.
>
>> This is a preexisting bug, but I'm suspicious about the code leaking a
>> pointer to an igc_xzalloc'd area to its caller, which may call Lisp
>> (when it autoloads a map) in the case of Fminor_mode_key_binding.  If
>> that Lisp code recursively accesses keymaps and the maps get
>> reallocated, we end up resurrecting free'd data, and will probably
>> crash.  (My suspicion is this is the reason for the "don't use realloc"
>> comment, too).
>>
>> We should really fix this on master and just use vectors, and it's
>> probably even less effort for you to do so than it is for me, but I
>> still don't get how code like this is meant to be fixed.
>>
>> (I hope the comment about static being defined to the empty string is no
>> longer accurate :-) ).
>
> :-) That's a curious comment.  The overflow check in current_minor_maps
> is also curious.
>
> A simple fix for Fminor_mode_key_binding would be to copy the modes and
> maps arrays to an alloca'd area before calling Flookup_key.
>
> In the patch below (for master) I tried something different: remove the
> global variables cmm_maps and cmm_modes entirely.

Thanks.  It'd be nice to have a more general approach to growable
vectors, but in this case, I don't understand why we use array
structures at all: two simple linked lists should work just as well.

So I don't think a specific new structure for the cmm case is the right
approach here; it should be easy enough to generalize to vectors of
Lisp_Object, and the code would be cleaner without the "two vectors
placed back-to-back" assumption.

One place which would benefit from growable vectors is json.c.

My idea still would be to grow a vector aggressively until it's large
enough to fit all elements, then "truncate" it in place in such a way
that the GC knows to shrink it when it gets copied to the next
generation.

However, even that approach may be too complicated.

Pip

Message #23 received at 78943 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: pipcet <at> protonmail.com, Helmut Eller <eller.helmut <at> gmail.com>,
 78943 <at> debbugs.gnu.org
Subject: Re: bug#78943: feature/igc [PATCH] Trace current minor maps exactly
Date: Sat, 12 Jul 2025 10:04:04 -0400

>> The patch uses the GC heap if there are more than 16 minor mode keymaps
>> active.  I'm not sure if that is enough; viper mode already activates 8.

Could we adjust this size dynamically, keeping a high-water-mark?
This way GC allocation would happen only when the high-water mark is
changed (if it goes beyond a preset threshold if we care about
contrived situations with thousands of minor mode maps).

> Adding Stefan to the discussion.

Fixing the API of `current_minor_modes` sounds good to me.


        Stefan

Message #26 received at 78943 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: pipcet <at> protonmail.com, Helmut Eller <eller.helmut <at> gmail.com>,
 78943 <at> debbugs.gnu.org
Subject: Re: bug#78943: feature/igc [PATCH] Trace current minor maps exactly
Date: Sat, 12 Jul 2025 11:53:59 -0400

> Fixing the API of `current_minor_modes` sounds good to me.
                                   ^^^^^
                                   maps
- Stefan

Message #29 received at 78943 <at> debbugs.gnu.org (full text, mbox):

From: Helmut Eller <eller.helmut <at> gmail.com>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: Eli Zaretskii <eliz <at> gnu.org>, pipcet <at> protonmail.com, 78943 <at> debbugs.gnu.org
Subject: Re: bug#78943: feature/igc [PATCH] Trace current minor maps exactly
Date: Sun, 13 Jul 2025 17:31:36 +0200

On Sat, Jul 12 2025, Stefan Monnier wrote:

>>> The patch uses the GC heap if there are more than 16 minor mode keymaps
>>> active.  I'm not sure if that is enough; viper mode already activates 8.
>
> Could we adjust this size dynamically, keeping a high-water-mark?
> This way GC allocation would happen only when the high-water mark is
> changed (if it goes beyond a preset threshold if we care about
> contrived situations with thousands of minor mode maps).

The only way I can think of is with alloca/SAVE_ALLOCA.  GC allocation
could be avoided entirely if we are willing to call current_minor_maps
twice with when the number of minior mode maps changes:

  size_t size;
  Lisp_Object *buffer;
  static size_t predicted_size = 0;
  do {
    size = predicted_size;
    buffer = SAFE_ALLOCA (size * word_size);
    predicted_size = current_minor_modes (size, buffer)
  } while (size != predicted_size)

But this is not exactly a nice API and it can't be packed up as a
function because of alloca.

>> Adding Stefan to the discussion.
>
> Fixing the API of `current_minor_modes` sounds good to me.

There is a lot of duplicated code in the functions menu_bar_items,
tool_bar_items, and tab_bar_items.  The duplicated code builds an array
of keymaps.  I wonder if we couldn't replace this with
Fcurrent_active_maps?  It seems to do something very similar.

Message #32 received at 78943 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Helmut Eller <eller.helmut <at> gmail.com>
Cc: Eli Zaretskii <eliz <at> gnu.org>, pipcet <at> protonmail.com, 78943 <at> debbugs.gnu.org
Subject: Re: bug#78943: feature/igc [PATCH] Trace current minor maps exactly
Date: Sun, 13 Jul 2025 18:33:53 -0400

> But this is not exactly a nice API and it can't be packed up as
> a function because of alloca.

We have such things in the C code, but I'm not fond of them, indeed.

>> Fixing the API of `current_minor_modes` sounds good to me.
> There is a lot of duplicated code in the functions menu_bar_items,
> tool_bar_items, and tab_bar_items.  The duplicated code builds an array
> of keymaps.  I wonder if we couldn't replace this with
> Fcurrent_active_maps?  It seems to do something very similar.

IIRC there are some subtle issues that get in the way, mostly about
ordering, but last time I looked at it was more than 10 years ago, so it
might be worth revisiting.


        Stefan

Message #35 received at 78943 <at> debbugs.gnu.org (full text, mbox):

From: Helmut Eller <eller.helmut <at> gmail.com>
To: Pip Cet <pipcet <at> protonmail.com>
Cc: 78943 <at> debbugs.gnu.org
Subject: Re: bug#78943: feature/igc [PATCH] Trace current minor maps exactly
Date: Tue, 15 Jul 2025 19:12:05 +0200

[Message part 1 (text/plain, inline)]

On Sat, Jul 12 2025, Pip Cet wrote:

> Thanks.  It'd be nice to have a more general approach to growable
> vectors, but in this case, I don't understand why we use array
> structures at all: two simple linked lists should work just as well.

It seems that arrays are used because in some places the active minor
maps need to be processed in the reversed order from the order they are
stored in minor-mode-map-alist.

[...]
> My idea still would be to grow a vector aggressively until it's large
> enough to fit all elements, then "truncate" it in place in such a way
> that the GC knows to shrink it when it gets copied to the next
> generation.

This could work with MPS but I'm not so sure about the classic GC.

Here is a bit a different approach that doesn't use the cmm_vector:

  1. adds some test cases for the following changes

  2. uses Fcurrent_active_maps in keyboard.c and replaces the duplicated
     code with a common function

  3. replaces the remaining uses of current_minor_maps with
     functions that create some temporary lists

  4. This is an optional improvement for 2, if we are hellbent on
     avoiding consing & reversing the list returned from
     Fcurrent_active_maps.  This patch avoids the list at the cost of
     some complexity and alloca.

[0001-Add-some-minor-mode-keymap-related-tests.patch (text/x-diff, attachment)]

[0002-Refactor-menu_bar_items-tab_bar_items-and-tool_bar_i.patch (text/x-diff, attachment)]

[0003-Eliminate-the-global-arrays-cmm_modes-and-cmm_maps.patch (text/x-diff, attachment)]

[0004-In-menu_bar_items-avoid-consing-reversing-the-list-o.patch (text/x-diff, attachment)]

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.