libraries

[Chris Torek]

In article <1278 at nusdhub.UUCP> rwhite at nusdhub.UUCP (Robert C. White Jr.)
writes:
>Wrong-O kid!  An archive library is a "File which contains the
>original contents of zero-or-more external sources, usually text or
>object files, which have been reduced to a single system object."

This is an implementation detail.

>As subjective proof of this address this question:  "Can you 'archive'
>a a device special file and then access the device or service through
>direct refrence to the archive?"  The answer is OF COURSE *NO* because ...

Indeed?  Is that creaking I hear coming from the limb upon which you
have climbed?  Perhaps I should break it off, lest others be tempted to
go out on it as well:

Why, certainly, you can `archive' a device special file and then access
the device via the archive.  What would you say if I told you I had
added ar-file searching to the directory scanning code in namei?
Insecure, yes, but on a single user workstation, so what?  (Note that
while `ar' ignores S_IFCHR and S_IFBLK on extraction, they do in fact
appear in the header mode field.  It is eminently possible to scan ar
files in the kernel as if they were directories.  Pointless, perhaps,
but easy.)

>(1) device special files have no "contents" per-se and (2) The archive
>does not preserve the "file" concept on an individual-entry basis.

% man 5 ar

AR(5)               UNIX Programmer's Manual                AR(5)
     ...
     A file produced by ar has a magic string at the start, fol-
     lowed by the constituent files, each preceded by a file
     header. ...

     Each file begins on a even (0 mod 2) boundary; a new-line is
     inserted between files if necessary. ...

That should tell you that each `entry' is a `file'.  [Argument from
authority: the manual says so :-) ]

>If you do not understand the difference between a  "system object" file,
>and "the contents of a" file go to FILE MGMT. THEORY 101.  Do not pass
>go, do not collect your next paycheck.

The difference is an *implementation* question again.  There is no
fundamental reason that the kernel could not use `ar' format for
directories that contain files with exactly one link.

(Since the rest of the argument is built on this, I am going to skip
ahead.)

>As an excersize in intuition and deduction try the following:

[steps left out: essentially, decide how much time it would take to
 link-edit by reading individual .o files instead of a .a file.]

I have already wasted more time and net bandwidth on this subject than
I really cared to use; but here is a very simple timing comparison for
a `hello world' program%.  Viz:

	# N.B.: these were both run twice to prime the cache and
	# make the numbers settle.

	% time ld -X /lib/crt0.o -o hw0 hw.o -lc
	0.5u 0.4s 0:02 52% 24+112k 41+3io 2pf+0w
	% time ld -X /lib/crt0.o -o hw1 *.o
	0.2u 0.4s 0:01 48% 25+98k 30+10io 2pf+0w
	%

Reading individual .o files is *FASTER*.  It took the *same* amount of
system time (to a first approximation) and *less* user time to read
the needed .o files than it did to read (and ignore the unneeded parts
of) the archive, for a total of 33% less time.  It also took less memory
space and fewer disk transfers.

-----
% `hw.o' needs only a few .o files, but hey, I want the results to look
good.
-----

Now, there were only a few .o files involved in this case: hw1 needed
only the set

	_exit.o bcopy.o bzero.o calloc.o cerror.o close.o doprnt.o
	exit.o findiop.o flsbuf.o fstat.o getdtablesize.o getpagesize.o
	hw.o ioctl.o isatty.o lseek.o makebuf.o malloc.o printf.o
	read.o sbrk.o perror.o stdio.o write.o

which is only 25 out of a potential 317 (that includes a few dozen
compatibility routines, over one hundred syscalls, etc.).  Real programs
would need more .o files, and it will indeed require more open calls.
There is another issue, which I shall address momentarily, and that
is deciding which .o files are needed (which I did `by hand' above,
so that it does not count in the output from `time').

>>>How many times would you have to scan the contents of /usr/lib/*.o to
>>>load one relatively complex c program (say vn).

>>Either one time, or (preferably) zero times.

>A library directory you never scan would be useless. Ncest' Pa?
>[sic ;-)]

(Ne c'est pa, if anyone cares... ne ~= not, c'est ~= is, pa ~= way:
is not that the way.)

Clearly we are not communicating.

The linker need not `look at' any .o files.  Its task is to link.  To
do this it must know which files define needed symbols, and which
symbols those files need, and so forth, recursively, until all needed
symbols are satisfied.  Now, how might ld perform that task?

For an archive random library---/lib/libc.a, for instance---it does not
scan the entire archive.  It pulls one sub-file out of the archive,
__.SYMDEF.  This file lists which symbols are defined by which files.
It does not now list which symbols are needed by which files, but it is
easy to imagine that, in a new scheme, the file that takes its place
does.

So what ld might do, then, is read the `.symtab' file and, using that
information, recursively build a list of needed .o files.  It could
then open and link exactly those .o files---never touching any that are
not needed.  If your C program consists of `main() {}', all you need
is exit.o.  ld would read exactly two files from the C library.  And
hey presto! we have scanned the contents of /lib/libc/*.o zero times.
If your C program was the hello-world example above, ld would read
exactly 26 files (the 25 .o's plus .symtab)---and again, scan the
contents of /lib/libc/*.o zero times.

>I can garentee at least two scans.

Perhaps you mean something else here: the number of times the kernel
must look at directory entries to find any given .o file.  If
directories were as fast as they should be, the answer would be `1'.
(Consider, e.g., a Unix with hashed directories.)

>There are a few things I don not have to *test* to know. ... I do not
>have to implement a looser of a library scheme using a symbol table
>file and individual object files to know that it is a dumb idea.

But if you do not test them, you may still be wrong.  See the hello-
world example above.  Linking individual .o files is sometimes *faster*
---even in the current (4.3BSD-tahoe) system.  And my original point
still stands: if archives are a necessary efficiency hack, there may
be something wrong with the underlying system.  I think that, in
principle, they *should* be unnecessary, and we should come up with
a way to make them so.  [But I must admit that it is not high on my
priority list.]

>p.s. You try being dislexic for a few years and then make comments
>about spelling.

(That, incidentally, was why the remark was in the `cheap shots'
footnote.  I apologise for it, although not for my general attitude.)
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163)
Domain:	chris at mimsy.umd.edu	Path:	uunet!mimsy!chris