Re: master 3ed79cd: Separate bytecode stack

Re: master 3ed79cd: Separate bytecode stack

[Eli Zaretskii]

This changeset causes compilation warning in a 32-bit build in which
!LISP_WORDS_ARE_POINTERS and which was configured --with-wide-int:

  In file included from bytecode.c:22:
  bytecode.c: In function 'sf_set_ptr':
  bytecode.c:396:20: warning: cast from pointer to integer of different size [-Wpointer-to-int-cast]
    396 |   fp[index] = XIL ((EMACS_INT)value);
	|                    ^
  lisp.h:342:26: note: in definition of macro 'lisp_h_XIL'
    342 | #  define lisp_h_XIL(i) (i)
	|                          ^
  bytecode.c:396:15: note: in expansion of macro 'XIL'
    396 |   fp[index] = XIL ((EMACS_INT)value);
	|               ^~~

The problem is that pointers are 32-bit wide, but EMACS_INT is a 64-bit
integer data type (and not a pointer).

More generally, I'm quite nervous to see void * pointers and integers
being put into the same array.  I think we'd like a cleaner, more
obviously correct, code.

Thanks.

Re: master 3ed79cd: Separate bytecode stack

[Mattias Engdegård]

13 mars 2022 kl. 18.39 skrev Eli Zaretskii <eliz@gnu.org>:
> 
> This changeset causes compilation warning in a 32-bit build in which
> !LISP_WORDS_ARE_POINTERS and which was configured --with-wide-int:
> 
>  In file included from bytecode.c:22:
>  bytecode.c: In function 'sf_set_ptr':
>  bytecode.c:396:20: warning: cast from pointer to integer of different size [-Wpointer-to-int-cast]
>    396 |   fp[index] = XIL ((EMACS_INT)value);

Thank you for testing this configuration! Silly mistake of mine; please try with the pushed change.

> More generally, I'm quite nervous to see void * pointers and integers
> being put into the same array.

Actually what we are doing is storing arbitrary pointers in a Lisp_Object, and this should always be possible. In fact there is already a function for the conversion in one direction, XLP, but there isn't an XPL yet, which is what the code with the warning was doing. We could add an XPL to lisp.h; it would just be moving some code from bytecode.c.

Re: master 3ed79cd: Separate bytecode stack

[Eli Zaretskii]

> From: Mattias Engdegård <mattiase@acm.org>
> Date: Sun, 13 Mar 2022 19:44:22 +0100
> Cc: Emacs-Devel <emacs-devel@gnu.org>
> 
> 13 mars 2022 kl. 18.39 skrev Eli Zaretskii <eliz@gnu.org>:
> > 
> > This changeset causes compilation warning in a 32-bit build in which
> > !LISP_WORDS_ARE_POINTERS and which was configured --with-wide-int:
> > 
> >  In file included from bytecode.c:22:
> >  bytecode.c: In function 'sf_set_ptr':
> >  bytecode.c:396:20: warning: cast from pointer to integer of different size [-Wpointer-to-int-cast]
> >    396 |   fp[index] = XIL ((EMACS_INT)value);
> 
> Thank you for testing this configuration! Silly mistake of mine; please try with the pushed change.

The warning is gone, but I cannot say I'm happy with the code, see
below.

> > More generally, I'm quite nervous to see void * pointers and integers
> > being put into the same array.
> 
> Actually what we are doing is storing arbitrary pointers in a Lisp_Object, and this should always be possible.

I don't think I understand why you need to do this in the first place.
XLP was introduced for very specific and very rare situations, and I
don't see why we would need in this case to use something similar.
What am I missing?  What kind of pointers do you need to store in the
fp array, why, and for what purpose?  And if you do need to do that,
why not use a union?

Re: master 3ed79cd: Separate bytecode stack

[Mattias Engdegård]

13 mars 2022 kl. 19.50 skrev Eli Zaretskii <eliz@gnu.org>:

> The warning is gone

Excellent, thank you for testing!

>  What kind of pointers do you need to store in the
> fp array, why, and for what purpose?  And if you do need to do that,
> why not use a union?

Let's look at what we are doing. We switch to an explicit representation of the bytecode interpreter stack. Each stack frame is composed of two parts: a fixed-sized metadata record containing information such as where to continue execution after the function has terminated, and a variable-sized private data stack for the function. The size of that data stack is specified in the bytecode object.

Like most other interpreters and CPU hardware, we use the standard solution: reserve a block of memory for a stack and carve out stack frames from it as needed, with their two parts next to one another in each frame. The data stack part must be an array of Lisp_Object; here we have little choice. The metadata record consists of a few members each of which fits into the space of a Lisp_Object, which makes the current implementation fairly natural: store those in designated array slots.

There are alternatives, several of which have been tried. One which is basically an equivalent formulation of the same code is to use a C struct for the metadata, then allocate it and the local data stack out from a big untyped stack. This makes metadata access simpler and more type-safe, and eliminates the previously needed accessor functions (sf_get_lisp_ptr etc). The drawback is more casts between pointer types which is slightly more risky than the straightforward XLP etc conversions in the current code. On the other hand, it could actually be faster depending on how friendly the compiler is.

The latter alternative would become a little more palatable if we could use flexible array struct members on all platforms. Given that we assume C99, can we do that now?

Re: master 3ed79cd: Separate bytecode stack

[Eli Zaretskii]

> From: Mattias Engdegård <mattiase@acm.org>
> Date: Mon, 14 Mar 2022 16:56:20 +0100
> Cc: emacs-devel@gnu.org
> 
> 13 mars 2022 kl. 19.50 skrev Eli Zaretskii <eliz@gnu.org>:
> 
> > The warning is gone
> 
> Excellent, thank you for testing!
> 
> >  What kind of pointers do you need to store in the
> > fp array, why, and for what purpose?  And if you do need to do that,
> > why not use a union?
> 
> Let's look at what we are doing. We switch to an explicit representation of the bytecode interpreter stack. Each stack frame is composed of two parts: a fixed-sized metadata record containing information such as where to continue execution after the function has terminated, and a variable-sized private data stack for the function. The size of that data stack is specified in the bytecode object.
> 
> Like most other interpreters and CPU hardware, we use the standard solution: reserve a block of memory for a stack and carve out stack frames from it as needed, with their two parts next to one another in each frame. The data stack part must be an array of Lisp_Object; here we have little choice. The metadata record consists of a few members each of which fits into the space of a Lisp_Object, which makes the current implementation fairly natural: store those in designated array slots.
> 
> There are alternatives, several of which have been tried. One which is basically an equivalent formulation of the same code is to use a C struct for the metadata, then allocate it and the local data stack out from a big untyped stack. This makes metadata access simpler and more type-safe, and eliminates the previously needed accessor functions (sf_get_lisp_ptr etc). The drawback is more casts between pointer types which is slightly more risky than the straightforward XLP etc conversions in the current code. On the other hand, it could actually be faster depending on how friendly the compiler is.

I don't think you answered my questions, or did I miss something?

I'm talking about the 'fp' array, where you store values at least some
of which seem to be pointers to Lisp_Object.  But the storing function
treats them as integers:

  INLINE void
  sf_set_ptr (Lisp_Object *fp, enum stack_frame_index index, void *value)
  {
    fp[index] = XIL ((uintptr_t)value);
  }
  INLINE void
  sf_set_lisp_ptr (Lisp_Object *fp, enum stack_frame_index index,
		   Lisp_Object *value)
  {
    sf_set_ptr (fp, index, value);
  }

Why do you need to do that?  Why not store the pointer itself in the
first place, and make 'fp' be array of pointers to pointer to
Lisp_Object?

My second question was: if you do need to store sometimes a pointer
and sometimes a Lisp_Object that is actually an integer, why not use a
union that will allow you to do both cleanly and safely, in effect
doing all the type-casting and stuff for you?

> The latter alternative would become a little more palatable if we could use flexible array struct members on all platforms. Given that we assume C99, can we do that now?

What do you mean by "flexible array struct members"?  Please show a
code snippet.

Re: master 3ed79cd: Separate bytecode stack

[Mattias Engdegård]

[-- Attachment #1: Type: text/plain, Size: 2823 bytes --]

14 mars 2022 kl. 18.15 skrev Eli Zaretskii <eliz@gnu.org>:

> I'm talking about the 'fp' array, where you store values at least some
> of which seem to be pointers to Lisp_Object.  But the storing function
> treats them as integers:

I did try to explain this but evidently without skill. Let me try again:

What you call "the 'fp' array" is the fixed-size part of a stack frame, which needs to store a few values of types `Lisp_Object`, `Lisp_Object *` and `const unsigned char *` in slots of type `Lisp_Object`. This is nothing unusual: we store pointers in Lisp_Object values everywhere in Emacs and use XIL (etc) to do so. Don't get yourself hung up on the fact that we take the route via integers; that's what we do for Lisp strings, vectors etc as well.

> Why do you need to do that?  Why not store the pointer itself in the
> first place, and make 'fp' be array of pointers to pointer to
> Lisp_Object?

Because we use a part of the overall stack which is an array of Lisp_Object, and in C we can't cast between an array of unions and a union of arrays -- or rather we could try, but if something as benighn as storing pointers in a Lisp_Object makes you squeamish then this stunt would be much worse (as well as technically dubious for all sorts of reasons).

> My second question was: if you do need to store sometimes a pointer
> and sometimes a Lisp_Object that is actually an integer, why not use a
> union that will allow you to do both cleanly and safely, in effect
> doing all the type-casting and stuff for you?

There appears to be a misunderstanding here. The data stack of each stack frame must be an array of Lisp_Object; it cannot be anything else. That's why the overall stack has that type; the frame metadata just uses a few slots between each local data stack. Since the data stacks vary in size, the location of the frame metadata in the overall stack isn't statically known.

I mentioned another possibility that is cleaner in some respects; I'm attaching a tentative patch. It uses a bona fide struct for the metadata and uses hand-placement of the data stacks. The generated code should be identical but might actually be better with the patch for various reasons.

>> The latter alternative would become a little more palatable if we could use flexible array struct members on all platforms. Given that we assume C99, can we do that now?
> 
> What do you mean by "flexible array struct members"?  Please show a
> code snippet.

I'm sure you know it well, it's the ability to put an incomplete array declaration as the last member of a struct, as in:

 struct S { int n; float a[]; };

which roughly means the same thing as declaring that array to be of size zero.
It's not required in our case but would make the next_stack function (see patch) go away.


[-- Attachment #2: stack-metadata-struct.diff --]
[-- Type: application/octet-stream, Size: 8927 bytes --]

diff --git a/src/bytecode.c b/src/bytecode.c
index 8704e6069d..139d37ef43 100644
--- a/src/bytecode.c
+++ b/src/bytecode.c
@@ -335,20 +335,7 @@ bcall0 (Lisp_Object f)
   Ffuncall (1, &f);
 }
 
-/* Layout of the stack frame header. */
-enum stack_frame_index {
-  SFI_SAVED_FP,   /* previous frame pointer */
-
-  /* In a frame called directly from C, the following two members are NULL.  */
-  SFI_SAVED_TOP,  /* previous stack pointer */
-  SFI_SAVED_PC,   /* previous program counter */
-
-  SFI_FUN,        /* current function object */
-
-  SF_SIZE         /* number of words in the header */
-};
-
-/* The bytecode stack size in Lisp words.
+/* The bytecode stack size in bytes.
    This is a fairly generous amount, but:
    - if users need more, we could allocate more, or just reserve the address
      space and allocate on demand
@@ -357,7 +344,7 @@ bcall0 (Lisp_Object f)
    - for maximum flexibility but a small runtime penalty, we could allocate
      the stack in smaller chunks as needed
 */
-#define BC_STACK_SIZE (512 * 1024)
+#define BC_STACK_SIZE (512 * 1024 * sizeof (Lisp_Object))
 
 /* Bytecode interpreter stack:
 
@@ -385,51 +372,32 @@ #define BC_STACK_SIZE (512 * 1024)
            :              :
 */
 
-INLINE void *
-sf_get_ptr (Lisp_Object *fp, enum stack_frame_index index)
-{
-  return XLP (fp[index]);
-}
-
-INLINE void
-sf_set_ptr (Lisp_Object *fp, enum stack_frame_index index, void *value)
-{
-  fp[index] = XIL ((uintptr_t)value);
-}
-
-INLINE Lisp_Object *
-sf_get_lisp_ptr (Lisp_Object *fp, enum stack_frame_index index)
-{
-  return sf_get_ptr (fp, index);
-}
+/* bytecode stack frame header (footer, actually) */
+struct bc_frame {
+  struct bc_frame *saved_fp;        /* previous frame pointer,
+                                       NULL if bottommost frame */
 
-INLINE void
-sf_set_lisp_ptr (Lisp_Object *fp, enum stack_frame_index index,
-		 Lisp_Object *value)
-{
-  sf_set_ptr (fp, index, value);
-}
+  /* In a frame called directly from C, the following two members are NULL.  */
+  Lisp_Object *saved_top;           /* previous stack pointer */
+  const unsigned char *saved_pc;    /* previous program counter */
 
-INLINE const unsigned char *
-sf_get_saved_pc (Lisp_Object *fp)
-{
-  return sf_get_ptr (fp, SFI_SAVED_PC);
-}
+  Lisp_Object fun;                  /* current function object */
+};
 
-INLINE void
-sf_set_saved_pc (Lisp_Object *fp, const unsigned char *value)
+INLINE Lisp_Object *
+next_stack (struct bc_frame *fp)
 {
-  sf_set_ptr (fp, SFI_SAVED_PC, (unsigned char *)value);
+  return (Lisp_Object *)(fp + 1);
 }
 
 void
 init_bc_thread (struct bc_thread_state *bc)
 {
-  bc->stack = xmalloc (BC_STACK_SIZE * sizeof *bc->stack);
+  bc->stack = xmalloc (BC_STACK_SIZE);
   bc->stack_end = bc->stack + BC_STACK_SIZE;
   /* Put a dummy header at the bottom to indicate the first free location.  */
-  bc->fp = bc->stack;
-  memset (bc->fp, 0, SF_SIZE * sizeof *bc->stack);
+  bc->fp = (struct bc_frame *)bc->stack;
+  memset (bc->fp, 0, sizeof *bc->fp);
 }
 
 void
@@ -441,16 +409,16 @@ free_bc_thread (struct bc_thread_state *bc)
 void
 mark_bytecode (struct bc_thread_state *bc)
 {
-  Lisp_Object *fp = bc->fp;
+  struct bc_frame *fp = bc->fp;
   Lisp_Object *top = NULL;     /* stack pointer of topmost frame not known */
   for (;;)
     {
-      Lisp_Object *next_fp = sf_get_lisp_ptr (fp, SFI_SAVED_FP);
+      struct bc_frame *next_fp = fp->saved_fp;
       /* Only the dummy frame at the bottom has saved_fp = NULL.  */
       if (!next_fp)
 	break;
-      mark_object (fp[SFI_FUN]);
-      Lisp_Object *frame_base = next_fp + SF_SIZE;
+      mark_object (fp->fun);
+      Lisp_Object *frame_base = next_stack (next_fp);
       if (top)
 	{
 	  /* The stack pointer of a frame is known: mark the part of the stack
@@ -464,7 +432,7 @@ mark_bytecode (struct bc_thread_state *bc)
 	  /* The stack pointer is unknown -- mark everything conservatively.  */
 	  mark_memory (frame_base, fp);
 	}
-      top = sf_get_lisp_ptr (fp, SFI_SAVED_TOP);
+      top = fp->saved_top;
       fp = next_fp;
     }
 }
@@ -477,10 +445,10 @@ DEFUN ("internal-stack-stats", Finternal_stack_stats, Sinternal_stack_stats,
   struct bc_thread_state *bc = &current_thread->bc;
   int nframes = 0;
   int nruns = 0;
-  for (Lisp_Object *fp = bc->fp; fp; fp = sf_get_lisp_ptr (fp, SFI_SAVED_FP))
+  for (struct bc_frame *fp = bc->fp; fp; fp = fp->saved_fp)
     {
       nframes++;
-      if (sf_get_lisp_ptr (fp, SFI_SAVED_TOP) == NULL)
+      if (fp->saved_top == NULL)
 	nruns++;
     }
   fprintf (stderr, "%d stack frames, %d runs\n", nframes, nruns);
@@ -491,8 +459,8 @@ DEFUN ("internal-stack-stats", Finternal_stack_stats, Sinternal_stack_stats,
 INLINE bool
 valid_sp (struct bc_thread_state *bc, Lisp_Object *sp)
 {
-  Lisp_Object *fp = bc->fp;
-  return sp < fp && sp + 1 >= sf_get_lisp_ptr (fp, SFI_SAVED_FP) + SF_SIZE;
+  struct bc_frame *fp = bc->fp;
+  return sp < (Lisp_Object *)fp && sp + 1 >= next_stack (fp->saved_fp);
 }
 
 /* Execute the byte-code in FUN.  ARGS_TEMPLATE is the function arity
@@ -532,20 +500,20 @@ exec_byte_code (Lisp_Object fun, ptrdiff_t args_template,
   Lisp_Object *vectorp = XVECTOR (vector)->contents;
 
   EMACS_INT max_stack = XFIXNAT (maxdepth);
-  Lisp_Object *frame_base = bc->fp + SF_SIZE;
-  Lisp_Object *fp = frame_base + max_stack;
+  Lisp_Object *frame_base = next_stack (bc->fp);
+  struct bc_frame *fp = (struct bc_frame *)(frame_base + max_stack);
 
-  if (fp + SF_SIZE > bc->stack_end)
+  if ((char *)next_stack (fp) > bc->stack_end)
     error ("Bytecode stack overflow");
 
   /* Save the function object so that the bytecode and vector are
      held from removal by the GC. */
-  fp[SFI_FUN] = fun;
+  fp->fun = fun;
   /* Save previous stack pointer and pc in the new frame.  If we came
      directly from outside, these will be NULL.  */
-  sf_set_lisp_ptr (fp, SFI_SAVED_TOP, top);
-  sf_set_saved_pc (fp, pc);
-  sf_set_lisp_ptr (fp, SFI_SAVED_FP, bc->fp);
+  fp->saved_top = top;
+  fp->saved_pc = pc;
+  fp->saved_fp = bc->fp;
   bc->fp = fp;
 
   top = frame_base - 1;
@@ -914,7 +882,7 @@ #define DEFINE(name, value) [name] = &&insn_ ## name,
 
 	CASE (Breturn):
 	  {
-	    Lisp_Object *saved_top = sf_get_lisp_ptr (bc->fp, SFI_SAVED_TOP);
+	    Lisp_Object *saved_top = bc->fp->saved_top;
 	    if (saved_top)
 	      {
 		Lisp_Object val = TOP;
@@ -925,11 +893,11 @@ #define DEFINE(name, value) [name] = &&insn_ ## name,
 		specpdl_ptr--;
 
 		top = saved_top;
-		pc = sf_get_saved_pc (bc->fp);
-		Lisp_Object *fp = sf_get_lisp_ptr (bc->fp, SFI_SAVED_FP);
+		pc = bc->fp->saved_pc;
+		struct bc_frame *fp = bc->fp->saved_fp;
 		bc->fp = fp;
 
-		Lisp_Object fun = fp[SFI_FUN];
+		Lisp_Object fun = fp->fun;
 		Lisp_Object bytestr = AREF (fun, COMPILED_BYTECODE);
 		Lisp_Object vector = AREF (fun, COMPILED_CONSTANTS);
 		bytestr_data = SDATA (bytestr);
@@ -1004,9 +972,9 @@ #define DEFINE(name, value) [name] = &&insn_ ## name,
 		handlerlist = c->next;
 		top = c->bytecode_top;
 		op = c->bytecode_dest;
-		Lisp_Object *fp = bc->fp;
+		struct bc_frame *fp = bc->fp;
 
-		Lisp_Object fun = fp[SFI_FUN];
+		Lisp_Object fun = fp->fun;
 		Lisp_Object bytestr = AREF (fun, COMPILED_BYTECODE);
 		Lisp_Object vector = AREF (fun, COMPILED_CONSTANTS);
 		bytestr_data = SDATA (bytestr);
@@ -1756,7 +1724,7 @@ #define DEFINE(name, value) [name] = &&insn_ ## name,
 
  exit:
 
-  bc->fp = sf_get_lisp_ptr (bc->fp, SFI_SAVED_FP);
+  bc->fp = bc->fp->saved_fp;
 
   Lisp_Object result = TOP;
   return result;
diff --git a/src/lisp.h b/src/lisp.h
index 8053bbc977..d6cd72cd01 100644
--- a/src/lisp.h
+++ b/src/lisp.h
@@ -3546,7 +3546,7 @@ record_in_backtrace (Lisp_Object function, Lisp_Object *args, ptrdiff_t nargs)
   sys_jmp_buf jmp;
   EMACS_INT f_lisp_eval_depth;
   specpdl_ref pdlcount;
-  Lisp_Object *act_rec;
+  struct bc_frame *act_rec;
   int poll_suppress_count;
   int interrupt_input_blocked;
 };
@@ -4861,14 +4861,14 @@ #define DAEMON_RUNNING (w32_daemon_event != INVALID_HANDLE_VALUE)
 extern void free_bc_thread (struct bc_thread_state *bc);
 extern void mark_bytecode (struct bc_thread_state *bc);
 
-INLINE Lisp_Object *
+INLINE struct bc_frame *
 get_act_rec (struct thread_state *th)
 {
   return th->bc.fp;
 }
 
 INLINE void
-set_act_rec (struct thread_state *th, Lisp_Object *act_rec)
+set_act_rec (struct thread_state *th, struct bc_frame *act_rec)
 {
   th->bc.fp = act_rec;
 }
diff --git a/src/thread.h b/src/thread.h
index a29af702d1..ddba1a2d99 100644
--- a/src/thread.h
+++ b/src/thread.h
@@ -35,9 +35,11 @@ #define THREAD_H
 
 /* Byte-code interpreter thread state.  */
 struct bc_thread_state {
-  Lisp_Object *fp;		/* current frame pointer (see bytecode.c) */
-  Lisp_Object *stack;
-  Lisp_Object *stack_end;
+  struct bc_frame *fp;   /* current frame pointer */
+
+  /* start and end of allocated bytecode stack */
+  char *stack;
+  char *stack_end;
 };
 
 struct thread_state

Re: master 3ed79cd: Separate bytecode stack

[Eli Zaretskii]

> From: Mattias Engdegård <mattiase@acm.org>
> Date: Tue, 15 Mar 2022 15:20:29 +0100
> Cc: Emacs-Devel <emacs-devel@gnu.org>
> 
> >> The latter alternative would become a little more palatable if we could use flexible array struct members on all platforms. Given that we assume C99, can we do that now?
> > 
> > What do you mean by "flexible array struct members"?  Please show a
> > code snippet.
> 
> I'm sure you know it well, it's the ability to put an incomplete array declaration as the last member of a struct, as in:
> 
>  struct S { int n; float a[]; };
> 
> which roughly means the same thing as declaring that array to be of size zero.
> It's not required in our case but would make the next_stack function (see patch) go away.

I think you can use this (we already use it elsewhere in Emacs).

Re: master 3ed79cd: Separate bytecode stack

[Robert Pluim]

>>>>> On Tue, 15 Mar 2022 16:42:01 +0200, Eli Zaretskii <eliz@gnu.org> said:

    Eli> I think you can use this (we already use it elsewhere in Emacs).

We do? <time passes> I can only find one instance in comp.c, but I
guess thatʼs proof enough that it works.

Robert
-- 

Re: master 3ed79cd: Separate bytecode stack

[Stefan Monnier]

Eli Zaretskii [2022-03-15 16:42:01] wrote:

>> From: Mattias Engdegård <mattiase@acm.org>
>> Date: Tue, 15 Mar 2022 15:20:29 +0100
>> Cc: Emacs-Devel <emacs-devel@gnu.org>
>> 
>> >> The latter alternative would become a little more palatable if we could use flexible array struct members on all platforms. Given that we assume C99, can we do that now?
>> > 
>> > What do you mean by "flexible array struct members"?  Please show a
>> > code snippet.
>> 
>> I'm sure you know it well, it's the ability to put an incomplete array
>> declaration as the last member of a struct, as in:
>> 
>>  struct S { int n; float a[]; };
>> 
>> which roughly means the same thing as declaring that array to be of size zero.
>> It's not required in our case but would make the next_stack function (see patch) go away.
>
> I think you can use this (we already use it elsewhere in Emacs).

AFAICT we usually use:

    struct Lisp_Vector
      {
        union vectorlike_header header;
        Lisp_Object contents[FLEXIBLE_ARRAY_MEMBER];
      } GCALIGNED_STRUCT;

but I suspect that by now we don't need this compatibility hack.


        Stefan