From: torvalds@klaava.Helsinki.FI (Linus Benedict Torvalds)
Newsgroups: comp.arch
Subject: Re: Jump tables for shared libraries
Date: 30 Jul 92 16:21:08 GMT
Organization: University of Helsinki

In article <1992Jul30.151301.27595@crd.ge.com> davidsen@crd.ge.com (bill davidsen) writes:
>
>  A recent post to comp.os.linux indicated that there would be a change
>to jump tables for the shared libraries in the next release. WHile I
>understand the convenience features of jump tables, it would seem that
>there would be a better way to avoid relinking programs, which would
>avoid the overhaed of the indirection.

[ Note that this has been extensively discussed on the linux kernel and
  gcc mailing-lists..  We've just kept pretty quiet about it on the net,
  as there were some problems with actual implementation.  They seem to
  be mostly solved. ]

>  Two thoughts come to mind. The first is to have some form of runtime
>loader, which would do the linking at image activation time, rather than
>at image store time. This would cause startup overhead, but would avoid
>runtime overhead due to the indirect.

This means page sharing and demand-loading are impossible (or /very/
hard to implement), so it's actually not a good idea.  The result is a
slower system than one using jump-tables, as binries use up to 2 times
more memory, resulting in more swapping etc. 

The current linux page-sharing (of both shared libraries and
executables) results in /much/ lower memory needs for most things
(especially notable under X). Also, when the system runs out of memory,
linux starts discarding clean pages (ie usually code) as well as doing
actual paging to disk: the system knows it can re-demand-load any clean
pages when it needs them.

With any kind of dynamic shared libraries, the above would be
essentially impossible: the shared X libraries use the normal C
libraries, so they would have to be dynamically linked, making the
code-pages dirty and unshareable as well as forcing more swapping. 

>				 The second would be to have the
>jump table in unmapped memory, and have the o/s catch the call, modify
>the image in memory to use the real address, and then restart the
>program at the point of the call. This moves stuff down into the kernel,
>and imposes a trap for each point in the image at which a library call
>occurs.

This is /much/ slower than the one unnecessary indirection. The
indirection is actually just one machine-code instruction: a simple
"jmp" to the correct address.  Trapping to the kernel for each library
call would probably make for a system that is twice (or more) as slow.

And modifying the image in memory is impossible (or close to, anyway):
what if the address is in a register variable? And it has the same
page-sharing/demand-loading problem as the previous possibility.

>  Is there newer and/or better thinking on this problem? I estimated the
>overhead at up to 5%, and the original poster mentioned that he actually
>measured 2-4% on programs. While that makes me feel good about my
>estimating skills, I'm not overjoyed at the thought of a 2-4% drop in
>performance. Hopefully someone will suggest an alternative method which
>I can pass along for consideration.

The overhead shouldn't be too big for any real applications: it does
result in a pre-fetch flush, and the library jump-table pages have to be
loaded in.  With many programs using the shared libraries, the latter is
no problem: the jump-tables are essentially in memory all the time. 
Jump-tables were thought to be the best possible solution: easy updating
of shared libs with pretty minimal performance/memory loss.  Any dynamic
system is liable to be slower, more complicated and have more problems. 

		Linus