Alignment of Lisp_Subr

Alignment of Lisp_Subr

[Stefan Monnier]

So I have finally gotten around to move my tags from the top 3 to the
bottom 3 bits of a Lisp_Object so that Lisp_Objects can now be allocated
anywhere.

Here are the problems I'm facing (all of them due to the new constraint
that objects need to be aligned on 8 byte boundaries) and I'm wondering what
is the best solution for them:

- Lisp_Misc has currently a size that is not a multiple of 8.
  I solved that by adding some padding with

   /* A miscellaneous object, when it's on the free list.  */
   struct Lisp_Free
     {
       int type : 16;	/* = Lisp_Misc_Free */
       unsigned gcmarkbit : 1;
       int spacer : 15;
       union Lisp_Misc *chain;
   #ifdef USE_LSB_TAG
       /* Try to make sure that sizeof(Lisp_Misc) is a multiple of 8.
          This assumes that Lisp_Marker is the largest of the alternatives.  */
       char padding[8 * ((sizeof (struct Lisp_Marker) - 1) / 8 + 1)
   	            - sizeof (struct Lisp_Intfwd)];
   #endif
     };

  I think this solution is acceptable since it only increases the size
  of Lisp_Misc objects from 5 words to 6 words (i.e. by 20%) on typical
  32bit machines.  Maybe we could reduce this cost by making use of this
  extra word, although I'm not sure how.

- Structures of type Lisp_Subr are statically allocated and are not
  guaranteed to be aligned on a multiple of 8.  I currently solve this
  by adding __attributes__ ((__aligned__ (8))), but this only works for GCC
  AFAIK.  The only alternative I can think of is to add a padding field
  to Lisp_Subr and when its address is not a multiple of 8, memmove it
  by a few bytes (I think `defsubr' is the only place where we refer
  to these statically allocated Sfoo variables).
  Any comment on which approach is preferable ?

- malloc does not guarantee on all systems that the returned value
  will be a multiple of 8 (or does it?).  How can I check it so as
  to automatically determine whether I can set USE_LSB_TAG (i.e. in
  `configure').  Is a heuristic check of calling malloc a few times
  with a few different odd sizes sufficient?


        Stefan

Re: Alignment of Lisp_Subr

[Miles Bader]

On Wed, Nov 12, 2003 at 11:22:33AM -0500, Stefan Monnier wrote:
> - Structures of type Lisp_Subr are statically allocated and are not
>   guaranteed to be aligned on a multiple of 8.  I currently solve this
>   by adding __attributes__ ((__aligned__ (8))), but this only works for GCC
>   AFAIK.  The only alternative I can think of is to add a padding field
>   to Lisp_Subr and when its address is not a multiple of 8, memmove it
>   by a few bytes (I think `defsubr' is the only place where we refer
>   to these statically allocated Sfoo variables).
>   Any comment on which approach is preferable ?

I think the compiler will force the structure to be aligned to the strictest
alignment of any component, so if you stick an field with 8-byte-alignment in
there _somewhere_, the compiler should do everything for you.  It should even
work to put the `forcing field' in as a member of a union with another field,
and simply never use the forcing field.  On many platforms, `double' could be
used as the type of the forcing-field, but I'm not sure how universal this
is.

Given that subrs are not the most space critical object though, it seems
simplest to just use __attributes__ when compiling with gcc (#ifdef
__GNUC__), and add the padding field when compiling with another compiler.

> - malloc does not guarantee on all systems that the returned value
>   will be a multiple of 8 (or does it?).

It guarantees `most strict' alignment, which on many platforms is 8 bytes
(because of doubles), and I think many malloc implementations are
conservative and assume 8 bytes anyway.  However I don't think you can assume
this though; a quick google shows plenty of people complaining about exactly
this issue (they expected 8-byte alignment, and got less; common culprits
seem to be MS and SCO mallocs... :-)

I guess in the common case where emacs uses its builtin malloc, or glibc's,
you'll have #defines to tell you though...

-Miles
-- 
In New York, most people don't have cars, so if you want to kill a person, you
have to take the subway to their house.  And sometimes on the way, the train
is delayed and you get impatient, so you have to kill someone on the subway.
  [George Carlin]

Re: Alignment of Lisp_Subr

[Richard Stallman]

    - Structures of type Lisp_Subr are statically allocated and are not
      guaranteed to be aligned on a multiple of 8.  I currently solve this
      by adding __attributes__ ((__aligned__ (8))), but this only works for GCC
      AFAIK.  The only alternative I can think of is to add a padding field
      to Lisp_Subr and when its address is not a multiple of 8, memmove it
      by a few bytes (I think `defsubr' is the only place where we refer
      to these statically allocated Sfoo variables).
      Any comment on which approach is preferable ?

Subr objects are allocated statically, but I don't think anything
requires that.  There is no harm in copying the data to some new,
properly-aligned block of memory and using that block instead.

Re: Alignment of Lisp_Subr

[Stephen J. Turnbull]

>>>>> "Miles" == Miles Bader <miles@gnu.org> writes:

    Miles> On Wed, Nov 12, 2003 at 11:22:33AM -0500, Stefan Monnier
    Miles> wrote:

    >> - Structures of type Lisp_Subr are statically allocated and are
    >> not guaranteed to be aligned on a multiple of 8.  I currently
    >> solve this by adding __attributes__ ((__aligned__ (8))), but
    >> this only works for GCC AFAIK.

    Miles> I think the compiler will force the structure to be aligned
    Miles> to the strictest alignment of any component, so if you
    Miles> stick an field with 8-byte-alignment in there _somewhere_,
    Miles> the compiler should do everything for you.  It should even
    Miles> work to put the `forcing field' in as a member of a union
    Miles> with another field, and simply never use the forcing field.
    Miles> On many platforms, `double' could be used as the type of
    Miles> the forcing-field, but I'm not sure how universal this is.

XEmacs has a typedef and a family of macros for forcing alignment.  I
believe the author is Martin Buchholz <martin@xemacs.org>.  We don't
need to force 8 bytes, but I'd be surprised if Martin doesn't know how
to do that for a very wide variety of platforms.

There may be issues with Lisp objects with tagbits at the bottom.  I
know XEmacs had some problems on recent glibc, which were never
properly diagnosed.  It's probable that this was due to excessive
cleverness in optimizing space use of malloc blocks, but if you do run
into weirdness (we were crashing) feel free to ping me and I'll dig up
the thread.

-- 
Institute of Policy and Planning Sciences     http://turnbull.sk.tsukuba.ac.jp
University of Tsukuba                    Tennodai 1-1-1 Tsukuba 305-8573 JAPAN
               Ask not how you can "do" free software business;
              ask what your business can "do for" free software.

Re: Alignment of Lisp_Subr

[Gaute B Strokkenes]

On 13 nov 2003, stephen@xemacs.org wrote:

> There may be issues with Lisp objects with tagbits at the bottom.  I
> know XEmacs had some problems on recent glibc, which were never
> properly diagnosed.  It's probable that this was due to excessive
> cleverness in optimizing space use of malloc blocks, but if you do
> run into weirdness (we were crashing) feel free to ping me and I'll
> dig up the thread.

Are you saying that glibc malloc does not return blocks that are
sufficiently aligned?  My copy of the glibc manual says:

  The block that `malloc' gives you is guaranteed to be aligned so
  that it can hold any type of data.  In the GNU system, the address
  is always a multiple of eight on most systems, and a multiple of 16
  on 64-bit systems.

-- 
Gaute Strokkenes                        http://www.srcf.ucam.org/~gs234/
Not enough people play SKEE-BALL..  They're always thinking about
 COCAINE or and ALIEN BEINGS!!

Re: Alignment of Lisp_Subr

[Stephen J. Turnbull]

>>>>> "Gaute" == Gaute B Strokkenes <Gaute> writes:

    Gaute> On 13 nov 2003, stephen@xemacs.org wrote:

    >> There may be issues with Lisp objects with tagbits at the
    >> bottom.  I know XEmacs had some problems on recent glibc, which
    >> were never properly diagnosed.  It's probable that this was due
    >> to excessive cleverness in optimizing space use of malloc
    >> blocks, but if you do run into weirdness (we were crashing)
    >> feel free to ping me and I'll dig up the thread.

    Gaute> Are you saying that glibc malloc does not return blocks
    Gaute> that are sufficiently aligned?  My copy of the glibc manual
    Gaute> says:

No, I'm saying that XEmacs (which has had tagbits in the lower bits
for a couple of years now) was crashing for unknown reasons.  Wolfram
Gloger thought it might have to do with tagbits in Lisp objects, but
the bug was never identified.  A separate issue from alignment, but it
is related to moving tagbits from high bits to low bits, which was one
main difference between XEmacs (which had problems) and GNU Emacs
(which didn't) at that time (about a year ago).


-- 
Institute of Policy and Planning Sciences     http://turnbull.sk.tsukuba.ac.jp
University of Tsukuba                    Tennodai 1-1-1 Tsukuba 305-8573 JAPAN
               Ask not how you can "do" free software business;
              ask what your business can "do for" free software.

Re: Alignment of Lisp_Subr

[Gaute B Strokkenes]

On 14 nov 2003, stephen@xemacs.org wrote:

>>>>>> "Gaute" == Gaute B Strokkenes <Gaute> writes:
>
> Gaute> On 13 nov 2003, stephen@xemacs.org wrote:
>
>>> There may be issues with Lisp objects with tagbits at the
>>> bottom.  I know XEmacs had some problems on recent glibc, which
>>> were never properly diagnosed.  It's probable that this was due
>>> to excessive cleverness in optimizing space use of malloc
>>> blocks, but if you do run into weirdness (we were crashing)
>>> feel free to ping me and I'll dig up the thread.
>
> Gaute> Are you saying that glibc malloc does not return blocks
> Gaute> that are sufficiently aligned?  My copy of the glibc manual
> Gaute> says:
>
> No, I'm saying that XEmacs (which has had tagbits in the lower bits
> for a couple of years now) was crashing for unknown reasons.
> Wolfram Gloger thought it might have to do with tagbits in Lisp
> objects, but the bug was never identified.

Ah, sorry.  I read you as saying that glibc was "excessively clever"
with the way it managed memory, but on a second reading that's not
what you were saying at all.

As an aside, putting tagbits in the lowest order bits ought to make
it easier to use emacs with the Boehm GC (though I'm not sure that is
necessarily a great idea.)

-- 
Gaute Strokkenes                        http://www.srcf.ucam.org/~gs234/
I know how to do SPECIAL EFFECTS!!