Ravenbrook / Projects / Memory Pool System / Version 1.111 Product Sources / Design Documents

Memory Pool System Project

# MPS to Client Message Protocol

This document contains a guide to the MPS to Client Message Protocol, followed by the historical initial design. References, History, Copyright and License are at the end.

# Guide

Readership: any MPS developer. Not confidential.

## Introduction

Messages are used when the MPS needs to asynchronously send information to the client. Currently, messages are used to signal:

- finalization ("`_finalization`" message);
- trace start ("`_gc_start`" message);
- trace end ("`_gc`" message).

The Originator of the message is some part of the MPS. For example, the finalization system (see poolmrg.c) is the originator of finalization messages, sent to the client when an object is no longer exactly reachable.

The MPS's Message-system (message.c) keeps messages that have been posted and are awaiting collection by the client in an arena-wide queue -- these are "queued messages".

The Client:

1. periodically calls mps_message_poll() and/or mps_message_get() to get a message from the MPS Message queue;
2. calls accessor functions (eg. mps_message_finalization_ref()) to read data out of the message;
3. calls mps_message_discard() when it has finished using the message.

The design is intended to support two alternative models of Client:

- a client with a central function that Gets all messages, and dispatches them to the various parts of the Client;
- a client with no such central function, but instead several parts which each Get only the message types they are interested in.

## The Message-system

The Message-system does just two things:

- class-based method dispatch on any valid message (methods: Delete, slot accessors);
- queue for messages that have been Posted but not yet Got.

Note that message type is now an attribute of a message class: each class implements exactly one type. (But multiple different classes, such as for several different pool classes, may all implement a single common message type).

## How to Originate a Message

Any part of the MPS can be a message Originator. Any struct can be a message, as long as it:

- contains an embedded MessageStruct (used by the Message-system for housekeeping);
- makes appropriate MessageInit() and MessageFinish() calls (for its embedded MessageStruct);
- has a Delete() function, to be called when the Client calls mps_message_discard();
- has appropriate accessor functions.

The Originator must define a message class, which is simply a struct containing the Delete and accessor functions, and a few other bits of housekeeping. The Originator may wish to define a new message type too.

Here's an example of a message. Notice the embedded MessageStruct:

>     typedef struct TraceStartMessageStruct {
>       Sig sig;
>       char why[TRACE_START_MESSAGE_WHY_LEN];
>       MessageStruct messageStruct;
>     } TraceStartMessageStruct;

The Originator allocates storage for messages. It is important to consider how to handle the case where this allocation fails because of insufficient free memory. Here are some sensible allocation strategies:

- Pre-allocate the struct when creating the subject it will refer to. The message is then ready to post at any time. This is ideal for subjects that the client creates explicitly, because failure to allocate the message makes the whole operation fail and report a non-OK result code. This approach only allows a fixed number of messages over the entire lifetime of the subject. (Used for finalization messages).

- Allocate the struct from control pool (with ControlAlloc) immediately before posting, and free it (with ControlFree) in the Delete method. Must cope with failure to allocate.

- Allocate the struct from control pool (with ControlAlloc) long in advance of posting. This is needed for messages that are likely to be emitted when memory is low, such as trace start messages. Must cope with failure to allocate. (Used for trace start and trace end messages).

Note: Originators should not re-use message structs. Each message should be dynamically allocated, posted once, queued for as long as the client wants, and then freed when the client discards it. Otherwise the Originator is imposing a limit on the maximum number of ungot (queued) messages, which therefore requires the client to either get the messages 'promptly', or risk losing messages. But typically there is no way for the client to reliably meet this promptness constraint. (Note also that the MPS message system does not distinguish between unsent and received states). See also job001570.

If a message cannot be allocated, the Originator should report an error code if possible. If not possible, for example because the message is about an operation that was not explicitly requested by the Client, then there is a "`droppedMessages`" counter in the arena. Increment this. It's not great, but what else can you do?

It is good design to make the Client's life as easy as possible by making message behaviour as simple as possible. Ideally, make sure that messages will never be dropped. If there is a set of messages that make sense together (eg trace start and trace end), then ideally make sure that the set is 'all or nothing' -- either all messages will be sent, or all will be dropped. Where logical, add new accessors to an existing message, instead of creating a new message type. All this simplifies the code the Client has to write: Client code that has to rendezvous several messages with one another is tricky to write and tricky to test.

## Lifecycle

The normal lifecycle of a Message is:

> (alloc Init) unsent (Post) queued (Get) received (Discard Delete Finish free)

The struct is a valid message between Init and Finish. The Originator is permitted to Finish and free an unsent message.

MessagePost() simply links the struct into the message queue (using a RingStruct inside the MessageStruct): no copying occurs. The message is now queued, and MessageOnQueue() returns true. The Originator must not free a queued message.

When the client calls mps_message_get(), the Message-system simply unlinks the message from the queue. The message is now received, and is in use by the client. The Originator must not free or change a received message, because the Client would then have a reference to freed memory, or would see inconsistent data.

When the Client calls mps_message_discard(), the Message-system calls through to the Originator-supplied Delete method. The Originator calls Finish and free.

### Abnormal lifecycles

If the Client has not enabled messages of this type (with mps_message_type_enable), Posting the message immediately Discards it, which calls the Delete method:

> (alloc Init) unsent (Post Discard Delete Finish free) -- client did not enable this message type

Therefore whenever an Originator calls MessagePost(), beware:

- it must be safe to call the Originator's Delete method;
- the delete may deallocate and unmap the message, so the Originator must not use its reference to the message any more.

If the client has enabled but never gets the message, it remains on the message queue until ArenaDestroy. Theoretically these messages could accumulate forever until they exhaust memory. This is intentional: the client should not enable a message type and then never get it!

> (alloc Init) unsent (Post) queued (ArenaDestroy Discard Delete Finish free) -- client never gets message

Messages can also be dropped from the queue if the client calls mps_message_type_disable() when there are already some messages of that type queued:

> (alloc Init) unsent (Post) queued (_type_disable Discard Delete Finish free) -- client disables this message type

If the client simply drops its reference without calling mps_message_discard (this is a client error), the memory will not be reclaimed until ArenaDestroy. This is intentional: the control pool is not garbage-collected:

> (alloc Init) unsent (Post) queued (Get) received (ArenaDestroy free) -- client never discards message

## Future ideas

### Shrinking MessageStruct

(Because every finalised object requires a MessageStruct, so it would be nice to keep it small).

The field `Clock postedClock` could be implemented and stored by only those message types that use it. A bit messy though.

# Initial Design

                         MPS TO CLIENT MESSAGE PROTOCOL
                               design.mps.message
                                 incomplete doc
                                 drj 1997-02-13

    INTRODUCTION

    .readership: Any MPS developer.

    .intro: The MCMP provides a means by which clients can receive messages from
    the MPS asynchronously.  Typical messages may be low memory notification (or in
    general low utility), finalization notification, soft-failure notification.
    There is a general assumption that it should not be disastrous for the MPS
    client to ignore messages, but that it is probably in the clients best interest
    to not ignore messages.  The justification for this is that the MPS cannot
    force the MPS client to read and act on messages, so no message should be
    critical [bogus, since we cannot force clients to check error codes either -
    Pekka 1997-09-17].

    .contents: This document describes the design of the external and internal
    interfaces and concludes with a sketch of an example design of an internal
    client.  The example is that of implementing finalization using PoolMRG.

    REQUIREMENTS

    .req: The MPS/Client message protocol will be used for implementing
    finalization (see design.mps.finalize and req.dylan.fun.final).  It will also
    be used for implementing the notification of various conditions (possibly
    req.dylan.prot.consult is relevant here).

    INTERFACE

    External Interface

    .if.queue:

    Messages are presented as a single queue per arena.  Various functions are
    provided to inspect the queue and inspect messages in it (see below).

    Functions

    .if.fun:

    The following functions are provided:

    .if.fun.poll: Poll.  Sees whether there are any messages pending.

    mps_bool_t mps_message_poll(mps_arena_t arena);

    Returns 1 only if there is a message on the queue of arena.  Returns 0
    otherwise.

    .if.fun.enable: Enable.  Enables the flow of messages of a certain type.

    void mps_message_type_enable(mps_arena_t arena, mps_message_type_t type);

    Enables the specified message type.  The queue of messages of a arena will
    contain only messages whose types have been enabled.  Initially all message
    types are disabled.  Effectively this function allows the client to declare to
    the MPS what message types the client understands.  The MPS does not generate
    any messages of a type that hasn't been enabled.  This allows the MPS to add
    new message types (in subsequent releases of a memory manager) without
    confusing the client.  The client will only be receiving the messages if they
    have explicitly enabled them (and the client presumably only enables message
    types when they have written the code to handle them).

    .if.fun.disable: Disable.  Disables the flow of messages of a certain type.

    void mps_message_type_disable(mps_arena_t arena, mps_message_type_t type);

    The antidote to mps_message_type_enable.  Disables the specified message type.
    Flushes any existing messages of that type on the queue, and stops any further
    generation of messages of that type. This permits clients to dynamically
    decline interest in a message type, which may help to avoid a memory leak or
    bloated queue when the messages are only required temporarily.

    .if.fun.get: begins a message "transaction".

    mps_bool_t mps_message_get(mps_message_t *message_return, mps_arena_t arena,
    mps_message_type_t type);

    If there is a message of the specified type on the queue then the first such
    message will be removed from the queue and a handle to it will be returned to
    the client in *messageReturn; in this case the function will return TRUE.
    Otherwise it will return FALSE.  Having obtained a handle on a message in this
    way, the client can use the type-specific accessors to find out about the
    message.  When the client is done with the message the client should call
    mps_message_discard; failure to do so will result in a resource leak.

    .if.fun.discard: ends a message "transaction".

    void mps_message_discard(mps_arena_t arena, mps_message_t message);

    Indicates to the MPS that the client is done with this message and its
    resources may be reclaimed.

    .if.fun.type.any: Determines the type of a message in the queue

    mps_bool_t mps_message_queue_type(mps_message_type_t *type_return, mps_arena_t
    arena);

    Returns 1 only if there is a message on the queue of arena, and in this case
    updates *type_return to be the type of a message in the queue.  Otherwise
    returns 0.

    .if.fun.type: Determines the type of a message (that has already been got).

    mps_message_type_t mps_message_type(mps_arena_t arena, mps_message_t message)

    Return the type of the message.  Only legal when inside a message transaction
    (i.e. after mps_message_get and before mps_message_discard).  Note that the
    type will be the same as the type that the client passed in the call to
    mps_message_get.

    Types of messages

    .type: The type governs the "shape" and meaning of the message.

    .type.int: Types themselves will just be a scalar quantity, an integer.

    .type.semantics: A type indicates the semantics of the message.
    .type.semantics.interpret: The semantics of a message are interpreted by the
    client by calling various accessor methods on the message.  .type.accessor: The
    type of a message governs which accessor methods are legal to apply to the
    message.

    .type.example: Some example types:

    .type.finalization: There will be a finalization type.  The type is abstractly:
    FinalizationMessage(Ref).

    .type.finalization.semantics: A finalization message indicates that an object
    has been discovered to be finalizable (see design.mps.poolmrg.def.final.object
    for a definition of finalizable).  .type.finalization.ref: There is an accessor
    to get the reference of the finalization message (i.e. a reference to the
    object which is finalizable) called mps_message_finalization_ref.
    .type.finalization.ref.scan: Note that the reference returned should be stored
    in scanned memory.

    .compatibility:

    Compatibility issues

    .compatibility.future.type-new: Notice that message of a type that the client
    doesn't understand are not placed on the queue, therefore the MPS can introduce
    new types of message and existing client will still function and will not leak
    resources.  This has been achieved by getting the client to declare the types
    that the client understands (with mps_message_type_enable, .if.fun.enable).

    .compatibility.future.type-extend: The information available in a message of a
    given type can be extended by providing more accessor methods.  Old clients
    won't get any of this information but that's okay.

    Internal Interface

    .message.instance: Messages are instances of Message Classes.
    .message.concrete: Concretely a Message is represented by a MessageStruct.  A
    MessageStruct has the usual signature field (see design.mps.sig).  A
    MessageStruct has a type field which defines its type, a ring node, which is
    used to attach the message to the queue of pending messages, a class field,
    which identifies a MessageClass object.  .message.intent: The intention is that
    a MessageStruct will be embedded in some richer object which contains
    information relevant to that specific type of message.

    .message.type:

    typedef struct MessageStruct *Message;

    .message.struct:

    struct MessageStruct {
      Sig sig;
      MessageType type;
      MessageClass class;
      RingStruct node;
    } MessageStruct;

    .class: A message class is an encapsulation of methods.  It encapsulates
    methods that are applicable to all types of messages (generic) and methods that
    are applicable to messages only of a certain type (type-specific).
    .class.concrete: Concretely a message class is represented by a
    MessageClassStruct (a struct).  Clients of the Message module are expected to
    allocate storage for and initialise the MessageClassStruct.  It is expected
    that such storage will be allocated and initialised statically.

    .class.one-type: A message class implements exactly one message type.
    The identifier for this type is stored in the "type" field of the
    MessageClassStruct.  Note that the converse is not true: a single
    message type may be implemented by two (or more) different message
    classes (for example: for two pool classes that require different
    implementations for that message type).

    BEGIN OBSOLETE SECTION "class-not-type".
    [.class.not-type.not: It used to be the case that message classes and message
    types were completely distinct.  This was never used and was unnecessary.  It
    was removed by making message-type an attribute of the implementing
    message-class, ie. moving the type field out of MessageStruct and into
    MessageClassStruct.  RHSK 2008-11-24.]
    .class.not-type: Note that message classes and message types are distinct.
    .class.not-type.why: (see also mail.drj.1997-07-15.10-33(0) from which this is
    derived)  This allows two different implementations (ie classes) of messages
    with the same meaning (ie type).  This may be necessary because the (memory)
    management of the messages may be different in the two implemtations (which is
    bogus).  The case of having one class implement two types is not expected to be
    so useful.  .class.not-type.why.not: It's all pretty feeble justification
    anyway.
    END OBSOLETE SECTION "class-not-type"

    .class.methods.generic: The generic methods are:

    delete - used when the message is destroyed (by the client calling
    mps_message_discard).  The class implementation should finish the message (by
    calling MessageFinish) and storage for the message should be reclaimed (if
    applicable).

    .class.methods.specific:

    The type specific methods are:

    .class.methods.specific.finalization:

    Specific to MessageTypeFinalization

    finalizationRef - returns a reference to the finalizable object represented by
    this message.

    .class.methods.specific.collectionstats:

    Specific to MessageTypeCollectionStats

    collectionStatsLiveSize - returns the number of bytes (of objects) that were
    condemned but survived.

    collectionStatsCondemnedSize - returns the number of bytes condemned in the
    collection.

    collectionStatsNotCondemnedSize - returns the the number of bytes (of objects)
    that are subject to a GC policy (ie collectable) but were not condemned in the
    collection.

    .class.type:

    typedef struct MessageClassStruct *MessageClass;

    .class.sig.double: The MessageClassStruct has a signature field at both ends.
    This is so that if the MessageClassStruct changes size (by adding extra methods
    for example) then any static initializers will generate errors from the
    compiler (there will be a type error causes by initialising a non-sig type
    field with a sig) unless the static initializers are changed as well.

    .class.struct:

    typedef struct MessageClassStruct {
      Sig sig;                      /* design.mps.sig */
      const char *name;             /* Human readable Class name */

      /* generic methods */
      MessageDeleteMethod delete;   /* terminates a message */

      /* methods specific to MessageTypeFinalization */
      MessageFinalizationRefMethod finalizationRef;

      /* methods specific to MessageTypeCollectionStats */
      MessageCollectionStatsLiveSizeMethod collectionStatsLiveSize;
      MessageCollectionStatsCondemnedSizeMethod collectionStatsCondemnedSize;
      MessageCollectionStatsNotCondemnedSizeMethod collectionStatsNotCondemnedSize;

      Sig endSig;                   /* design.mps.message.class.sig.double */
    } MessageClassStruct;

    .space.queue: The arena structure is augmented with a structure for managing
    for queue of pending messages.  This is a ring in the ArenaStruct.

    struct ArenaStruct
    {
      ...
      RingStruct messageRing;
      ...
    }

    Functions

    .fun.init:
    /* Initializes a message */
    void MessageInit(Arena arena, Message message, MessageClass class);

    Initializes the MessageStruct pointed to by message.  The caller of this
    function is expected to manage the store for the MessageStruct.

    .fun.finish:
    /* Finishes a message */
    void MessageFinish(Message message);

    Finishes the MessageStruct pointed to by message.  The caller of this function
    is expected to manage the store for the MessageStruct.

    .fun.post:
    /* Places a message on the client accessible queue */
    void MessagePost(Arena arena, Message message);

    This function places a message on the queue of a arena.  .fun.post.precondition
    : Prior to calling the function the node field of the message must be a
    singleton.  After the call to the function the message will be available for
    MPS client to access.  After the call to the function the message fields must
    not be manipulated except from the message's class's method functions (i.e.,
    you mustn't poke about with the node field in particular).

    .fun.empty:
    void MessageEmpty(Arena arena);

    Empties the message queue.  This function has the same effect as discarding all
    the messages on the queue.  After calling this function there will be no
    messages on the queue.  .fun.empty.internal-only: This functionality is not
    exposed to clients.  We might want to expose this functionality to our clients
    in the future.

    Message Life Cycle

    .life: A message will be allocated by a client of the message module, it will
    be initialised by calling MessageInit.  The client will eventually post the
    message on the external queue (in fact most clients will create a message and
    then immediately post it).  The message module may then apply any of the
    methods to the message.  The message module will eventually destroy the message
    by applying the Delete method to it.

    EXAMPLES

    Finalization

    [possibly out of date, see design.mps.finalize and design.mps.poolmrg instead
    -- drj 1997-08-28]

    This subsection is a sketch of how PoolMRG will use Messages for finalization
    (see design.mps.poolmrg).

    PoolMRG has guardians (see design.mps.poolmrg.guardian), guardians are used to
    manage final references and detect when an object is finalizable.

    The link part of a guardian will include a MessageStruct.

    The MessageStruct is allocated when the final reference is created (which is
    when the referred to object is registered for finalization).  This avoids
    allocating at the time when the message gets posted (which might be a tricky,
    undesirable, or impossible, time to allocate).

    PoolMRG has two queues: the entry queue, and the exit queue.  The entry
    queue will use a ring; the exit queue of MRG will simply be the
    external message queue.

    [The evil hack of 'borrowing' MessageStruct's ring node for the entry
    queue was removed from the code ages ago, so I've removed the account
    of it from this text too.  RHSK 2006-12-11]

    MRG Message class

    del - frees both the link part and the reference part of the guardian.

## A. References

## B. Document History

2002-06-07 | RB | Converted from MMInfo database design document.
2006-10-25 | RHSK | Created guide.
2006-12-11 | RHSK | More on lifecycle; unmention evil hack in initial design.
2008-12-19 | RHSK | Simplify and clarify lifecycle. Remove description of and deprecate re-use of messages.

## C. Copyright and License

This document is copyright © 1995-2002, 2006, 2008 Ravenbrook Limited. All rights reserved. This is an open source license. Contact Ravenbrook for commercial licensing options.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
3. Redistributions in any form must be accompanied by information on how to obtain complete source code for the this software and any accompanying software that uses this software. The source code must either be included in the distribution or be available for no more than the cost of distribution plus a nominal fee, and must be freely redistributable under reasonable conditions. For an executable file, complete source code means the source code for all modules it contains. It does not include source code for modules or files that typically accompany the major components of the operating system on which the executable file runs.

This software is provided by the copyright holders and contributors "as is" and any express or implied warranties, including, but not limited to, the implied warranties of merchantability, fitness for a particular purpose, or non-infringement, are disclaimed. In no event shall the copyright holders and contributors be liable for any direct, indirect, incidental, special, exemplary, or consequential damages (including, but not limited to, procurement of substitute goods or services; loss of use, data, or profits; or business interruption) however caused and on any theory of liability, whether in contract, strict liability, or tort (including negligence or otherwise) arising in any way out of the use of this software, even if advised of the possibility of such damage.

`$Id: //info.ravenbrook.com/project/mps/version/1.111/design/message/index.html#2 $`

Ravenbrook / Projects / Memory Pool System / Version 1.111 Product Sources / Design Documents