From: jwz@lucid.com (Jamie Zawinski)
Subject: tagging schemes (was Re: Help: Decstation malloc returns too big value.)
Organization: Lucid, Inc., Menlo Park, CA
Distribution: gnu
Date: Thu, 9 Apr 1992 21:22:45 GMT

In article <1992Apr7.214736.2223@wsrcc.com> wolfgang@wsrcc.COM (Wolfgang S. Rupprecht) wrote:
> 
> Well, you can rip out the quaint tag-in-the-address logic and put the
> tag in the lisp structs itself.  Unless I'm missing some major gotcha
> this should only take a week or so.

Making lisp integers be compound structures is a really bad idea.

In a pointer, the bottom two bits are generally unused; if all memory is
allocated on word-boundaries, then the bottom two bits of a valid pointer
to the beginning of an object will be 0.  Thus you can store a type-tag in
these two bits without intruding on the address space.  One possible set
of tags would be

	00  - cons
	01  - even fixnum
	10  - odd fixnum
	11  - compound structure

If the tag is 00, then it's a pointer to a Lisp_Cons.  If the tag is
01 or 10, then shift it right by one bit.  This give you 31-bit fixnums.
If the tag is 11, then mask it off, and look at a secondary type-tag
that lies in the object itself.

If you can live with 30 bit fixnums, then you can have a type for "other"
immediate objects, like the invisible forwarding pointers used for those
lisp variables which indirect to C variables, and for the Lisp_Internal 
and Lisp_Internal_Stream types.  However, I don't think it would be that
hard to redesign things such that the "other" immediate objects could be
eliminated entirely.

> It shouldn't take more than a week of hacking.

I really don't think so...

I think that the above is what the emacs tagging scheme should eventually 
look like, but there is a compromise that can be made as a first step that
has some of the benefits of the above; I may be implementing something like
the following soon.

Add a new type, Named_Vector, which looks like:

struct Named_Vector
  {
    int size;
    int marked_size;
    struct Named_Vector *next;
    Lisp_Object type_name;
    void *contents[1];
  };

Allocate it just like a vector: the `contents' slot is not really 1 word
long, it varies according to the `size' slot.  When marking this object in
the garbage collector, only mark the first N slots of `contents', where N is
what is in the `marked_size' slot.  `size' may be larger than `marked_size',
in which case, there are non-tagged C pointers at the end of contents.  In
this way, you've got an abstraction that lets you cleanly implement the 
Lisp_Compiled, Lisp_Process, Lisp_Window, and Lisp_Window_Configuration 
types, as well as any that may show up in the future.  For example:

struct Lisp_Process
{
    int size;			/* this is always 18 */
    int marked_size;		/* this is always 7 */
    struct Named_Vector *next;
    Lisp_Object type_name;	/* this is always the symbol "process" */

    /* The slots that hold lisp objects: */
    Lisp_Object name;
    Lisp_Object command;
    Lisp_Object filter;
    Lisp_Object sentinel;
    Lisp_Object buffer;
    Lisp_Object mark;
    Lisp_Object status;

    /* Slots used only by the C code, for non-GCable objects: */
    int infd;
    int outfd;
    int pid;
    int command_channel_p;
    int childp;
    int kill_without_query;
    int raw_status_low;
    int raw_status_high;
    int pty_flag;
    int tick;
    int update_tick;
};

This lets you eliminate about a dozen primary type-tags (actually, chase
them into the structure from the pointer) and, if the Lisp_Void,
Lisp_Internal, and Lisp_Internal_Stream types were gotten rid of (which 
I don't think would be too hard) then the remaining types would fit into
four bits.

And here's the good part: given a subr which allocates a fully-marked
named-vector with a given symbol in its type slot, most of defstruct could
be implemented in elisp.

The Common Lisp #S read-syntax would be trivial.  Printing could be 
controlled by format strings on the type-symbol's plist: the syntax could
even be something as simple as "#<%t %2 %3>" to mean print the type-name, 
then the second and third slots of the structure.  (I think this is 
necessary because you don't want the printer to call arbitrary lisp code.
Changing things so that GC can happen in places that it couldn't before is
really hard to get right.)

	-- Jamie

Newsgroups: gnu.emacs.bug