Re: Shared Libraries.

[Stephen Usher <steve@earth.ox.ac.uk>]

>A Proposal for Implementing Shared Libraries
>
>I think I've finally figured out a "good" way to implement shared
>libraries (i.e. low overhead, doesn't need VM, requires few changes
>to existing applications). Here's my proposal; please let me know what
>you think. (In case it isn't obvious, this is *very* far from being
>cast in stone :-). I do think we need to do shared libraries soon,
>though.)

I agree, shared libraries are needed soon, though maybe not before
non-blocking SCSI/ACSI/IDE devices with a generic disk interface above and
the filesystems above that. The current situation is rapidly becoming
untenable as most of MiNT's performance degradation is with disk I/O. This
will be even worse if the disk keeps on being accessed to load shared
library modules on the fly.

>A shared library will be implemented as a DRI format object file, with
>the GST long name symbol table. A program linked with shared libraries
>will have the same format, but with an additional header prepended
>which gives the names and version numbers of the shared libraries it
>requires.

Hmm... why are you thinking about using such a mixed bag of formats? Why did
you choose those particular formats? Why not use something like a Unix "ar"
format file or similar?

>Both the libraries and the programs will be compiled to use
>register A5 as a base register (e.g. when compiled with gcc they will
>be compiled with -mbaserel). They need not be position independent;
>the libraries will appear at the same virtual address (determined at
>load time) in every process, and programs will be relocated at load
>time by the kernel.

This is fine for the 68000 based Atari's, but this does seem rather cripling
for the new generation of Atari's which use the 68030. I understand that
you want to keep the 68000 and 68030 kernels as close as possible, but
couldn't shared libraries be mapped differently on the two architectures?

What you suggest seems fine for the 68000 based machines, but for the 68030
based machines it seems a bit of a munge, why not give all processes on
these machines the same virtual address space and map the shared library
objects into that address space?

>
>The data and bss segments of a given shared library will always be
>located at the same (relative) offset in the data/bss area of
>a program using that library. (Note that I'm going to call the
>"data/bss area" just the "data segment" from here on in, because the
>bss is just a special part of the data segment from the kernel's point
>of view.)
>
>For example, let's consider 2 programs, BAR and FOO. BAR uses libraries A,
>B, and C; FOO uses A, C, and D.
>
>BAR's data segment will look like this: (assuming that A, B, C, and D are
>the first 4 libraries loaded, and were loaded in that order)
>
>------------------------------------------------------------------------------
>| A's data |   B's data   |   C's data  |           BAR's data               |
>------------------------------------------------------------------------------
>
>FOO's data segment will look like this:
>
>------------------------------------------------------------------------------
>| A's data |   FOO's data |   C's data  |  D's data  |  more of FOO's data   |
>------------------------------------------------------------------------------
>
>Note that FOO's data segment is split up. This is because library C expects
>its data to come at a certain offset (after A's and B's), and so C's data
>segment in process FOO must start at that offset. Since FOO doesn't use
>library B, the part of its data segment that B would normally use is
>available for FOO's use. The kernel will be responsible for finding
>such "holes" and taking advantage of them where possible. (This may
>actually turn out to be tricky, since arrays will have to be contiguous.)
>We also may want to provide a way to specify that certain libraries are
>mutually exclusive. In the example above, if libraries B and D were
>mutually exclusive, then D's data could occupy the same offsets as B's
>(or a subset thereof, if D has less data).

It looks like you might get into a problem of massive memory fragmentation..
it could get very messy. :-(

What happens if FOO needs A, B, C & D? This scheme also means that all the
library modules will have to be loaded at load time instead at first call
time (doesn't it?).

>
>Does this make sense? The key thing is that since everyone is using
>register A5 as a base register, the libraries can always find their
>data (at the particular fixed offset into the data segment assigned to
>them).
>
>The disadvantage of this scheme is that once more than 64K of data is
>filled up, libraries and/or programs that use 16 bit offsets will be
>in trouble. There are ways around this, of course.

Yes, but they are probably cludges!

>
>Another disadvantage is that program load times will be longer, since
>the kernel is going to have to do the relocation and symbol resolving.
>
>An alternative would be to use something like Sun's global offset table.
>That scheme is slower, though, since it adds another layer of indirection
>to variable references.

It may be slower (slightly), but at least it is very flexible in that you
only have to initialise the offset on the first call of the module when it
is loaded. Also this method would work just as well in a virtual address
space, except you'd give a virtual address of the module. What size of
offset were you thinking of having? 16bit? 32bit?  Depends upon architecture?

>Please let me know your thoughts on this matter.
>
>Eric

How about an alternative....

(1) Have in the kernel a table of currently loaded modules, each with a
	reference count.
(2) Modules are loaded into an arbitary memory location with a read-only
	copy of their initialised data space at the time of first reference
	and a copy of the initialised data space is placed in the process'
	shared lib data segment, which is separate from it's own data
	segment. The total size of the shared library data segment is 64K on
	the 68000 based machines and "unlimited" on 68030 based machines,
	there is no limit imposed upon the normal data segment. Shared data
	is accessed via an offset table.
(3) Modules are deleted once the last program to use them exits, or
	alternatively... The kernel table has a timer which is added to
	every time a module is accessed. After n context switches, any
	module which has not been accessed in that time could be deleted
	from memory and a flag in the table set to say that the module is
	active but not in memory. When the module is next accessed, it is
	re-loaded, but the data space is not copied to the currently running
	program. This would improve memory usage no end, especially if
	modules were of a fixed size or a multiple of a fixed size, no
	memory fragmentation! This would give a sort of virtual memory even
	for 68000 based machines.

I understand the problems with this method, ie each shared library call has
a system call overhead etc. But there is a major advantage in that loaded
programs which are only using a small number of their routines in a small
loop would rapidly reduce in memory usage, allowing other programs to use
the memory for their routines.

You do realise the case I'm thinking of is X-Windows, don't you? :-)

Just think, the majority of X applications would be sitting waiting for
input in one routine from a shared library, taking up very little memory.

I've thought this up on the fly, so there could be massive holes in my
arguments, oh well, it seems like a good idea at the moment.

Steve

-- 
---------------------------------------------------------------------------
Computer Systems Administrator, Dept. of Earth Sciences, Oxford University.
E-Mail: steve@uk.ac.ox.earth (JANET) steve@earth.ox.ac.uk (Internet).
Tel:- Oxford (0865) 282110 (UK) or +44 865 282110 (International).