From: gt8134b@prism.gatech.EDU (Howlin' Bob)
Newsgroups: comp.sys.hp48
Subject: Shared library proposal - Jump table
Date: 16 Oct 92 18:24:53 GMT
Organization: Georgia Institute of Technology

Hi, all!

  I've spent some time refining my plans for the shared library, and I'm
one step closer to ready to start :-).
 
This post talks about the machine language jump table that will be
necessary for implementing a ML-callable set of library routines.  
It is by no means the final decision, just a starting point for my
work and -- hopefully -- some more suggestions.

====================================================================== 

   Because any HP48 object must be relocatable (i.e. can be moved in
memory and still run, even if it was initially loaded somwehere else),
the implementation of a shared library which contains, among other
things, ML-callable routines raises some thorny problems.

   Machine language programmers on the HP48 are used to calling 
subroutines in two ways:
   1. if the subroutine resides in ROM, the address of the routine
      never changes.  Therefore, an absolute call to the address is
      used.  this looks like "gosbvl XXXXX" or "call.a XXXXX" in the
      two mnemonic sets used on the HP48.  The XXXXX is an absolute
      (non-PC relative) reference to the location.

   2. if the subroutine resides in the program object itself (i.e. the
      CODE object), then a PC-relative  call must be used.  PC-relative
      calls reference a memory location by adding or subtracting a
      given amount from the current program counter.  These look
      like "gosub +YYY" or "gosub  -YYY" in HP mnemonics.  However,
      modern assemblers and linkers will calculate the displacement
      automatically if given a symbolic reference.  For example:

      caller      a=dat0    a
                  gosub     callee	** callee is replaced at assemble-
                  dat0=a    a		** or link- time by a displacement
                  LOOP			** HP's assembler inserts the
					** code for returning to RPL.
      callee      acex      a
                  rtn


   Neither of these methods really applies to SHLIB48.  It resides outside
of the calling program, so simple relative gosub's won't work.  However,
neither is it like the HP's ROM, as a library is a RAM object and will
move around at certain times.  Therefore, absolute addresses won't work,
as the absolute address of the library will also change.
   If the HP48 had a Memory Management Unit (MMU), I could just remap
the library to a prespecified virtual address.  However, the designers
of the SATURN processor lacked such brilliant foresight :-).
   In the MMU's stead, any program which wishes to use SHLIB48's
ML-callable routines must perform a slightly more complicated (and
admittedly slower) process to access SHLIB48's routines.  

   The brunt of this process is contained in some startup code and
a subroutine that must be placed in such programs.  This is a brief
description of those:

STARTUP CODE:
------------
   The startup code must search memory for the SHLIB48 library.  There
are several ways to implement such a process, none of which have been
tested, written, or even seriously contemplated yet.  Rest assured,
several solutions will be considered and implemented when I get to
that point.
   Whatever method is used, the startup code must somehow inform the
machine language program of the library's absolute address in such a way
that Garbage Collection is avoided.  I have not researched library
memory storage well enough to know exactly how this should be done.
I have reason to believe that the FIRST library installed on the HP48
does not move unless something drastic happens to the memory scheme
(i.e.  FREEing or MERGEing a card, or ON-A-F...).  If this is so, then
many of my concerns evaporate.  The only things a SHLIB program would
be prohibited to do would be FREEing or MERGEing a card.  Well, Jan
Brittenson's SHADOW program comes to mind.  Add to the restrictions
the prohibition from fiddling with the memory map, such as SHADOW or
bank-switching.
   If all libraries can and do move during garbage collection, the
problem becomes a bit hairier, but still manageable.  Operations that
allocate memory (which can force GC) would have to occur BEFORE 
the start code for SHLIB.  Alternately, if memory allocation is
unavoidable, the location of the library would have to be reloaded
after every memory op.  Most programs allocate memory in one large
chunk upon entry and never allocate again.

   The rest of the article operates with the assumption that the
library's address has been found.  Also, the library was parsed by
the startup code to find the address of the global library jump table.
It is the address of the jump table that the program will use.

   To speed resolution of library addresses, the startup code will
search the library's jump table for the addresses of the entries
of the routines it needs.  These addresses will be placed in a LOCAL
jump table, solely for the purpose of the program.  Think of this
as a jump table cache.
   If a library needed 4 routines from SHLIB48, its local jump table
cache would be 20 nibbles long (NUM_ROUTINES * ADDR_SIZE, where ADDR_SIZE
is the size in nibbles of any address on the HP48).  The cache would
reside at CACHE_ADDRESS and look like this:
 
  Contents:            Offset from CACHE_ADDRESS:
  +----------------+
  + ENTRY0 address +   0
  +----------------+
  + ENTRY1 address +   5
  +----------------+
  + ENTRY2 address +   10
  +----------------+
  + ENTRY3 address +   15
  +----------------+


THE CALLING SUBROUTINE:
----------------------
   Given the library's address, the machine language has to find the address
within it of the library routine of interest.  To avoid the memory overhead
of rewriting the same search-and-call code over and over, this procedure
could be contained in one subroutine that the program uses to access all
SHLIB48 routines.

   The process would proceed like this:

   1) The program would load the entry number of the routine it wished
      to execute into a register (I'll call it register X for now).
   2) The program would call its local LIBCALL subroutine
      (i.e. "gosub LIBCALL").
   3) The LIBCALL subroutine would jump to the appropriate routine.

   The real work takes place in the LIBCALL subroutine.

   1) The CACHE_ADDRESS, which should probably be kept in some register
      location for speed of access, would be incremented by ENTRY_NUMBER * 5.
      This can be expressed as:
         ENTRY_REFERENCE = CACHE_ADDRESS + (X * ADDR_SIZE)

         where X is the register holding ENTRY_NUMBER

   2) The ENTRY_REFERENCE now points to the area of memory which contains
      the address of the routine.  To jump to the routine, simply execute
      the instruction:

        PC=(C)     or 
        PC=(A)     (whichever register holds ENTRY_REFERENCE)

   3) Since the program executed a GOSUB to use the LIBCALL subroutine,
      the return address is left on the RSTK.  LIBCALL executed a 
      GOTO-like instruction, so this return address is left on the stack.
      Now, the library routine need simply execute a RTN to return to
      the proper place in the calling program.

   This scheme is called double indirection.  It is a bit confusing,
especially the way I have described it.  Let me draw a simple figure:

CACHE_ADDRESS 
 |                                    SHLIB48
 \--->  +----------------+            +----------+
        + ENTRY0_REF     +   ------>  | ROUTINE0 |
        +----------------+            |          |
        + ENTRY1_REF     +   ------>  | ROUTINE1 |
        +----------------+            |          |
        + ENTRY2_REF     +   ------>  | ROUTINE2 |
        +----------------+            |          |
        + ENTRY3_REF     +   ------>  | ROUTINE3 |
        +----------------+            +----------+

          Local Jump                 Body of SHLIB48
          Table Cache                     library


======================================================================    

   That's pretty much the state of my plans right now.  Let me give you
a quick implementation of LIBCALL that is sure to change.  It's just
a proof-of-thought :-) right now.  This is totally off-the-cuff, so
don't take it to heart.  
I will assume for this example that the program is keeping the address
of the local jump table in the A field of register R3.

*******************************************************************
** LIBCALL
**     - jump to the SHLIB routine referred to locally by the
**       number passed in A
**
** IN:   local jump table address in R3.A           (CACHE_ADDRESS)
**       local jump table entry number passed in A  (ENTRY_NUMBER)
**
**  -- uses registers A[A], C[A]
**
*******************************************************************

LIBCALL      c=a     a
             a=a+a   a    * A now holds 2*ENTRY_NUMBER
             a=a+a   a    * A now holds 4*ENTRY_NUMBER
             a=a+c   a    * A=5*ENTRY_NUMBER
             c=r3.F  a    * c=cache_address
             c=c+a   a    * c=cache_address + entry_number*addr_size
             pc=(c)       * jump to library routine
         


And that's that.  Not too much trouble, if you ask me.  Not for what
you get in return.
Feel free to post questions or comments, or email me.

Robert Sanders


-- 
Howlin' Bob
Georgia Institute of Technology, Atlanta Georgia, 30332
uucp:	  ...!{decvax,hplabs,ncar,purdue,rutgers}!gatech!prism!gt8134b
Internet: gt8134b@prism.gatech.edu