Subject: bug#76538: 31.0.50; 31.0.50; 31.0.50; feature/igc: using magit-section-cycle-global (S-TAB) and magit-section-toggle (TAB) in some random ways blocks GNU Emacs.

From: Gerd Möllmann <[email-masked]>
Date: Fri, 28 Feb 2025 16:01:04 +0100

Gerd Möllmann <[email-masked]> writes:

> Gerd Möllmann <[email-masked]> writes:
>
>> In any case, I think I would try to change DO_MARKERS to start at the
>> end of the marker vector. If fix_marker_vector runs often enough one
>> could also "straighten" the free-list there, maybe.
>
> Or one could build a doubly-linked list of markers in most-recently
> created order. But that would mean 3 array slots per marker in the
> marker vector. Don't know.

Which would be something like the attached. Can someone try this with
the original recipe? (It's a quick sketch, and blah blah.)

>From 0153db3935e129c6b8f43ae2f6f98b8a7b570926 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Gerd=20M=C3=B6llmann?= <[email-masked]>
Date: Fri, 28 Feb 2025 15:55:14 +0100
Subject: [PATCH] Iterating over markers in most-recently added order

---
 src/.lldbinit |   4 ++
 src/buffer.h  |  67 ++++++++++++++++++-----------
 src/igc.c     | 116 ++++++++++++++++++++++++++++++++++++--------------
 src/lisp.h    |   2 +-
 src/pdumper.c |   2 +-
 5 files changed, 131 insertions(+), 60 deletions(-)

diff --git a/src/.lldbinit b/src/.lldbinit
index 01fd51eb07d..17e48fa4967 100644
--- a/src/.lldbinit
+++ b/src/.lldbinit
@@ -120,3 +120,7 @@ process handle SIGINT --pass true --stop false --notify false
 #process attach --waitfor --name emacs (--continue)
 
 # Attach to future Emacs
+
+target create temacs
+settings set -- target.run-args --batch  -l loadup --temacs=pbootstrap 	--bin-dest '/Users/gerd/.local/bin/' --eln-dest '/Users/gerd/.local/lib/emacs/31.0.50/'
+command alias go process launch --working-dir .
diff --git a/src/buffer.h b/src/buffer.h
index 20599bb3ba4..dcc93807409 100644
--- a/src/buffer.h
+++ b/src/buffer.h
@@ -714,31 +714,56 @@ #define BVAR(buf, field) ((buf)->field ## _)
 
 struct marker_it
 {
-#ifdef HAVE_MPS
-  Lisp_Object markers, obj;
-  ptrdiff_t i;
+# ifdef HAVE_MPS
+  struct Lisp_Vector *v;
+  Lisp_Object obj;
+  ptrdiff_t slot;
 # else
   struct Lisp_Marker *marker;
 #endif
 };
 
-#ifdef HAVE_MPS
+# ifdef HAVE_MPS
+
+enum
+{
+  IGC_IDX_FREE_LIST = 0,
+  IGC_IDX_HEAD = 1,
+  IGC_IDX_START = 2,
+
+  IGC_OFF_NEXT = 0,
+  IGC_OFF_PREV = 1,
+  IGC_OFF_MARKER = 2,
+  IGC_MA_NSLOTS = 3,
+};
+
+INLINE int
+slot_to_index (int slot)
+{
+  return (slot * IGC_MA_NSLOTS) + IGC_IDX_START;
+}
+
+#define IGC_MA_FREE_LIST(v) v->contents[IGC_IDX_FREE_LIST]
+#define IGC_MA_HEAD(v) v->contents[IGC_IDX_HEAD]
+
+#define IGC_MA_MARKER(v, slot) v->contents[slot_to_index (slot) + IGC_OFF_MARKER]
+#define IGC_MA_NEXT(v, slot) v->contents[slot_to_index (slot) + IGC_OFF_NEXT]
+#define IGC_MA_PREV(v, slot) v->contents[slot_to_index (slot) + IGC_OFF_PREV]
+
+#define IGC_MA_NSLOTS(v) ((ASIZE (v) - IGC_IDX_START) / IGC_MA_NSLOTS)
+
 INLINE struct marker_it
 marker_it_init (struct buffer *b)
 {
-  Lisp_Object v = BUF_MARKERS (b);
-  if (!VECTORP (v))
+  Lisp_Object vec = BUF_MARKERS (b);
+  if (!VECTORP (vec))
     return (struct marker_it){ .obj = Qnil };
 
-  Lisp_Object obj = Qnil;
-  for (ptrdiff_t i = 1; i < ASIZE (v); ++i)
-    {
-      obj = AREF (v, i);
-      if (MARKERP (obj))
-	return (struct marker_it) { .i = i, .markers = v, .obj = obj };
-    }
-
-  return (struct marker_it) { .obj = Qnil };
+  struct Lisp_Vector *v = XVECTOR (vec);
+  ptrdiff_t slot = XFIXNUM (IGC_MA_HEAD (v));
+  if (slot < 0)
+    return (struct marker_it){ .obj = Qnil };
+  return (struct marker_it) { .slot = slot, .v = v, .obj = IGC_MA_MARKER (v, slot) };
 }
 
 INLINE bool
@@ -750,16 +775,8 @@ marker_it_valid (struct marker_it *it)
 INLINE void
 marker_it_next (struct marker_it *it)
 {
-  it->obj = Qnil;
-  for (++it->i; it->i < ASIZE (it->markers); ++it->i)
-    {
-      Lisp_Object m = AREF (it->markers, it->i);
-      if (MARKERP (m))
-	{
-	  it->obj = m;
-	  break;
-	}
-    }
+  it->slot = XFIXNUM (IGC_MA_NEXT (it->v, it->slot));
+  it->obj = it->slot < 0 ? Qnil : IGC_MA_MARKER (it->v, it->slot);
 }
 
 INLINE struct Lisp_Marker *
diff --git a/src/igc.c b/src/igc.c
index e8e5c892ab3..62c218182ed 100644
--- a/src/igc.c
+++ b/src/igc.c
@@ -2128,21 +2128,39 @@ fix_vectorlike (mps_ss_t ss, struct Lisp_Vector *v)
   return MPS_RES_OK;
 }
 
+static void
+unchain (struct Lisp_Vector *v, int slot)
+{
+  IGC_MA_MARKER (v, slot) = IGC_MA_FREE_LIST (v);
+  IGC_MA_FREE_LIST (v) = make_fixnum (slot);
+
+  int prev = XFIXNUM (IGC_MA_PREV (v, slot));
+  if (prev >= 0)
+    IGC_MA_NEXT (v, prev) = IGC_MA_NEXT (v, slot);
+  else
+    IGC_MA_HEAD (v) = IGC_MA_NEXT (v, slot);
+
+  int next = XFIXNUM (IGC_MA_NEXT (v, slot));
+  if (next >= 0)
+    IGC_MA_PREV (v, next) = IGC_MA_PREV (v, slot);
+}
+
 static mps_res_t
 fix_marker_vector (mps_ss_t ss, struct Lisp_Vector *v)
 {
   MPS_SCAN_BEGIN (ss)
   {
-    for (size_t i = 0, n = vector_size (v); i < n; ++i)
+    for (ptrdiff_t slot = XFIXNUM (IGC_MA_HEAD (v)), next;
+	 slot >= 0; slot = next)
       {
-	Lisp_Object old = v->contents[i];
-	IGC_FIX12_OBJ (ss, &v->contents[i]);
+	next = XFIXNUM (IGC_MA_NEXT (v, slot));
+
+	Lisp_Object old = IGC_MA_MARKER (v, slot);
+	IGC_FIX12_OBJ (ss, &IGC_MA_MARKER (v, slot));
+
 	/* FIXME/igc: this is right for marker vectors only.  */
-	if (NILP (v->contents[i]) && !NILP (old))
-	  {
-	    v->contents[i] = v->contents[0];
-	    v->contents[0] = make_fixnum (i);
-	  }
+	if (NILP (IGC_MA_MARKER (v, slot)) && !NILP (old))
+	  unchain (v, slot);
       }
   }
   MPS_SCAN_END (ss);
@@ -4517,18 +4535,39 @@ alloc_marker_vector (ptrdiff_t len, Lisp_Object init)
 static Lisp_Object
 larger_marker_vector (Lisp_Object v)
 {
-  igc_assert (NILP (v) || (VECTORP (v) && XFIXNUM (AREF (v, 0)) < 0));
-  ptrdiff_t old_len = NILP (v) ? 0 : ASIZE (v);
-  ptrdiff_t new_len = max (2, 2 * old_len);
-  Lisp_Object new_v = alloc_marker_vector (new_len, Qnil);
-  ptrdiff_t i = 0;
+  igc_assert (NILP (v)
+	      || (VECTORP (v)
+		  && XFIXNUM (IGC_MA_FREE_LIST (XVECTOR (v))) < 0));
+  ptrdiff_t old_nslots = NILP (v) ? 0 : IGC_MA_NSLOTS (v);
+  ptrdiff_t new_nslots = max (4, 2 * old_nslots);
+  ptrdiff_t alloc_len = new_nslots * IGC_MA_NSLOTS + IGC_IDX_START;
+  Lisp_Object new_v = alloc_marker_vector (alloc_len, Qnil);
+  struct Lisp_Vector *xnew_v = XVECTOR (new_v);
+  ptrdiff_t slot = 0;
   if (VECTORP (v))
-    for (i = 1; i < ASIZE (v); ++i)
-      ASET (new_v, i, AREF (v, i));
-  for (; i < ASIZE (new_v) - 1; ++i)
-    ASET (new_v, i, make_fixnum (i + 1));
-  ASET (new_v, i, make_fixnum (-1));
-  ASET (new_v, 0, make_fixnum (NILP (v) ? 1 : ASIZE (v)));
+    {
+      struct Lisp_Vector *xv = XVECTOR (v);
+      IGC_MA_FREE_LIST (xnew_v) = IGC_MA_FREE_LIST (xv);
+      IGC_MA_HEAD (xnew_v) = IGC_MA_HEAD (xv);
+      for (slot = 0; slot < IGC_MA_NSLOTS (v); ++slot)
+	{
+	  IGC_MA_MARKER (xnew_v, slot) = IGC_MA_MARKER (xv, slot);
+	  IGC_MA_NEXT (xnew_v, slot) = IGC_MA_NEXT (xv, slot);
+	  IGC_MA_PREV (xnew_v, slot) = IGC_MA_PREV (xv, slot);
+	}
+    }
+  else
+    IGC_MA_HEAD (xnew_v) = make_fixnum (-1);
+
+  for (; slot < IGC_MA_NSLOTS (new_v) - 1; ++slot)
+    {
+      IGC_MA_MARKER (xnew_v, slot) = make_fixnum (slot + 1);
+      IGC_MA_NEXT (xnew_v, slot) = make_fixnum (-1);
+      IGC_MA_PREV (xnew_v, slot) = make_fixnum (-1);
+    }
+
+  IGC_MA_MARKER (xnew_v, slot) = make_fixnum (-1);
+  IGC_MA_FREE_LIST (xnew_v) = make_fixnum (old_nslots);
   return new_v;
 }
 
@@ -4537,15 +4576,24 @@ igc_add_marker (struct buffer *b, struct Lisp_Marker *m)
 {
   Lisp_Object v = BUF_MARKERS (b);
   igc_assert (NILP (v) || VECTORP (v));
-  ptrdiff_t next_free = NILP (v) ? -1 : XFIXNUM (AREF (v, 0));
-  if (next_free < 0)
+  struct Lisp_Vector *xv = NILP (v) ? NULL : XVECTOR (v);
+  ptrdiff_t slot = NILP (v) ? -1 : XFIXNUM (IGC_MA_FREE_LIST (xv));
+  if (slot < 0)
     {
       v = BUF_MARKERS (b) = larger_marker_vector (v);
-      next_free = XFIXNUM (AREF (v, 0));
+      xv = XVECTOR (v);
+      slot = XFIXNUM (IGC_MA_FREE_LIST (xv));
     }
-  ASET (v, 0, AREF (v, next_free));
-  ASET (v, next_free, make_lisp_ptr (m, Lisp_Vectorlike));
-  m->index = next_free;
+
+  IGC_MA_FREE_LIST (xv) = IGC_MA_MARKER (xv, slot);
+  IGC_MA_MARKER (xv, slot) = make_lisp_ptr (m, Lisp_Vectorlike);
+  IGC_MA_NEXT (xv, slot) = IGC_MA_HEAD (xv);
+  IGC_MA_PREV (xv, slot) = make_fixnum (-1);
+  IGC_MA_HEAD (xv) = make_fixnum (slot);
+  ptrdiff_t next = XFIXNUM (IGC_MA_NEXT (xv, slot));
+  if (next >= 0)
+    IGC_MA_PREV (xv, next) = make_fixnum (slot);
+  m->slot = slot;
   m->buffer = b;
 }
 
@@ -4554,11 +4602,12 @@ igc_remove_marker (struct buffer *b, struct Lisp_Marker *m)
 {
   Lisp_Object v = BUF_MARKERS (b);
   igc_assert (VECTORP (v));
-  igc_assert (m->index >= 1 && m->index < ASIZE (v));
-  igc_assert (MARKERP (AREF (v, m->index)) && XMARKER (AREF (v, m->index)) == m);
-  ASET (v, m->index, AREF (v, 0));
-  ASET (v, 0, make_fixnum (m->index));
-  m->index = -1;
+  struct Lisp_Vector *xv = XVECTOR (v);
+  igc_assert (m->slot >= 0 && m->slot < IGC_MA_NSLOTS (v));
+  igc_assert (MARKERP (IGC_MA_MARKER (xv, m->slot))
+	      && XMARKER (IGC_MA_MARKER (xv, m->slot)) == m);
+  unchain (xv, m->slot);
+  m->slot = -1;
   m->buffer = NULL;
 }
 
@@ -4568,9 +4617,10 @@ igc_remove_all_markers (struct buffer *b)
   Lisp_Object v = BUF_MARKERS (b);
   if (VECTORP (v))
     {
-      for (ptrdiff_t i = 1; i < ASIZE (v); ++i)
-	if (MARKERP (AREF (v, i)))
-	  XMARKER (AREF (v, i))->buffer = NULL;
+      struct Lisp_Vector *xv = XVECTOR (v);
+      for (ptrdiff_t slot = 0; slot < IGC_MA_NSLOTS (v); ++slot)
+	if (MARKERP (IGC_MA_MARKER (xv, slot)))
+	  XMARKER (IGC_MA_MARKER (xv, slot))->buffer = NULL;
       BUF_MARKERS (b) = Qnil;
     }
 }
diff --git a/src/lisp.h b/src/lisp.h
index 5117059ef73..a4b97189598 100644
--- a/src/lisp.h
+++ b/src/lisp.h
@@ -3083,7 +3083,7 @@ knuth_hash (hash_hash_t hash, unsigned bits)
 # ifdef HAVE_MPS
   /* If in a buffer's marker vector, this is the index where it is
      stored. */
-  ptrdiff_t index;
+  ptrdiff_t slot;
 # endif
 } GCALIGNED_STRUCT;
 
diff --git a/src/pdumper.c b/src/pdumper.c
index b1484fda144..e94350726ee 100644
--- a/src/pdumper.c
+++ b/src/pdumper.c
@@ -2228,7 +2228,7 @@ dump_marker (struct dump_context *ctx, const struct Lisp_Marker *marker)
       dump_field_lv_rawptr (ctx, out, marker, &marker->next,
 			    Lisp_Vectorlike, WEIGHT_STRONG);
 #else
-      DUMP_FIELD_COPY (out, marker, index);
+      DUMP_FIELD_COPY (out, marker, slot);
 #endif
       DUMP_FIELD_COPY (out, marker, charpos);
       DUMP_FIELD_COPY (out, marker, bytepos);
-- 
2.48.1