Screen Version

School of Computer Science & Engineering
University of New South Wales
 Advanced Operating Systems 
 COMP9242 2002/S2 

Linking in Mungi

Inherent features of a SASOS:

• data have unique address, independent of context,
• a particular address always refers to the same data.

So, how keep private data of separate executions of the same program separate?

• Can allocate stacks at unique addresses.
• How about the data segment, in particular global statics?

==> Need to re-think linking.

Static linking in UNIX

-

all symbols resolved by linker

Dynamic linking in UNIX

-

some symbols resolved by loader

Properties of dynamic linking:

+

Library code only exists in single copy (RAM and disk).

+

New library versions immediately usable.

+

Reduced startup latency if library resident.

-

Execution fails if library removed.

-

Overhead due to level of indirection.

Symbol resolution at load time

• Loader enters external references into global object table (GOT).
• Functions invoked by indirect jump via GOT.

Lazy loading

• Delay library load time until first function invocation.
• GOT initialised to point to stub code.
• Stubs invoke lazy loader.
• Loader fixed up pointers in GOT.

Features:

+

Reduce startup latency (at expense of later stalls).

+

Save overhead for libraries not actually invoked.

-

Delayed failure if library not available.

Dynamic linking problems

Position of library code is not know at library link time
==> library must use position-independent code (PIC).

-

All jumps must be:

-

PC-relative,

-

off a register, or

-

indirect (via GOT).

-

Every function must first locate GOT (via PC-relative load)
==> overhead.

The global offset table is private static data:

 $.$

Global to library

==>

cannot be on stack.

 $.$

Private to invocation

==>

every process needs own copy.

==>

GOT cannot be allocated at a fixed address.

==>

GOT must be allocated in a per-library data segment
at known (at link-time) offset from library code
(to allow PC-relative addressing).

Same holds for any variables declared static or extern in library
e.g.: errno

Linking in a SASOS

 $.$

Static linking works as in UNIX (with same drawbacks)
except for private static data.

 $.$

Why copy when everything is in the address space anyway?

Can execute library code in place.

-

Called global static linking [CLFL94] (all references resolved at link time).

Features of global static linking

+

Code sharing (as for dynamic linking).

-

No automatic replacement of libraries,
re-linking required (as for static linking).

-

Removing library results in failure (as for dynamic linking).

-

Cannot have private static data in library.

-

Private static data is a problem for dynamic linking too.

Problems with private static data

 $.$

Same address ==> same data in a SASOS

==>

Different processes' private static data
must be allocated at different addresses.

==>

Need per-invocation, per-library data segments.

 $.$

How to locate data segment?

• Cannot use PC-relative addressing.
• Caller must pass address to callee:
  • explicit parameter (Nemesis[Ros95]),
  • global pointer register (Mungi[DH99]).

    +

    No overhead for intra-module calls.

Dynamic linking in Mungi

Module descriptor contains:

• pointer to module's data segment,
• pointers to imported functions.

Dynamic linking in Mungi...

• Calling sequence differs between local and cross-module invocation

  -

  supported by modified GNU assembler.

• Cross-module calling overhead is about 3 instructions.
• Module description objects specify module interface.
• Function pointers consist of
  (entrypoint address, global pointer value).

  -

  Appropriate compiler modification not done yet.

Module description object

libc.mm:

[IMPORTS]

[EXPORTS]
strlen
bcopy
...

[OBJECTS]
c1.o
c2.o
...

main.mm:

[IMPORTS]
libc.mm

[EXPORTS]

[OBJECTS]
main.o
sub.o
...

Code preparation process

Problems: Exported variables

Cannot do:

extern int errno;

-

Bad practice anyway, changed to:

extern int *__errno();
#define errno (*(__errno()))

for multi-threading support in

• Solaris,
• Digital Unix,
• Irix,
• Linux, ...

Performance

	Irix/32-bit/SGI-cc			Mungi/64-bit/GCC
	static	dynamic	dyn/stat	static	dynamic	dyn/stat
lookup	7.26(3)	8.02(3)	1.104(10)	7.568(6)	8.199(4)	1.083(3)
f. trav.	4.77(3)	5.17(4)	1.084(15)	6.013(6)	6.040(3)	1.004(6)
b. trav.	5.13(2)	5.68(4)	1.107(12)	6.976(4)	7.011(4)	1.005(1)
insert	4.61(2)	5.02(2)	1.087(10)	4.528(4)	4.755(3)	1.051(1)
total	21.7(1)	23.9(1)	1.097(12)	25.08(1)	26.00(1)	1.037(1)

Performance: Apples vs Apples (i.e., 64-bit static)

	Irix	Mungi		Mungi/Irix
		good	bad	good	bad
lookup	7.367	7.169	7.452	0.973	1.012
forward traverse	5.904	6.085	6.079	1.031	1.030
backward traverse	6.796	6.992	6.991	1.029	1.029
insert	4.755	4.724	4.801	0.993	1.010
total	24.822	24.970	25.323	1.006	1.020

Conclusions

-

Mungi's dynamic linking overhead is significantly lower than Irix'

-

Irix's higher overhead is inherent in multi-address-space approach:

 ${}$

Irix cannot guarantee that library can always be mapped to same address.

==>

Irix cannot execute ``in-place''.

==>

Irix cannot avoid using position-independent code.

 $.$

Compare quickstart facility in Digital Unix[DEC94]:
allocate libraries at fixed addresses.

-

Single-address-space system reduce costs.