libraries

[Robert C. White Jr.]

in article <15126 at mimsy.UUCP>, chris at mimsy.UUCP (Chris Torek) says:
> 
> 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.

Where do you get this "implementation has nothing to do with it" bull?
We are TALKING inplementation after all.  "Implementation asside" your
comments on implementing archives as directories instead of files are
reduced or nothing.

>>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:

No, no creaking here!

> 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?

I would say that you do not understand "functional units" in terms
of real computer systems arcetecture.  Why would you take a (bad)
directory search routine and increase it's "baddness coefficient"
by including archive searching?? and if your were to do that, wouldn't
it, BY DEFINITION, no longer be a directory search routine?

Who are you anyway?

> Insecure, yes, but on a single user workstation, so what?  (Note that

Too bad life is not "single worksataions" with no intrest in security isn't it?

> 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. ...
       ^^^^^^

You will note that the archive procedes the "files" (meaning their contents)
with HEADER(s).  *Headers* are NOT i-nodes.  There is no "file" in an
archive, only the "contents of the original system object" and a
sufficient quantity of information to RE-CONSTITUTE a file which would
have the same *SYSTEM DEPENDANT* information.

The file is not preserved; only the contents (and by induction, the
system-object level information, because nature is part of contents.)

>      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 :-) ]

SHAME SHAME... Quoting out of context again.  To whit:  [ AR(4)]

DESCRIPTION:
	The archive command ar(1) is used to combine several files into
	one.

(...also...)

	All information in the file member headers is in printable
	ASCII.

NONE of this preserves the "file"ness of the entries, and it all states
that the contributers are all reduced to "one (file)" so it is prima
facie that you do not understand that of which you speak.  If you don't
understand the difference between "a file" and "something that will let
you create a file."  I suggest you compare some *.o file (as a concept)
to using the "cc" command and an *.c file.  This is the same thing as saying
/usr/lib/libc.a is identical to using "ar" and the directory
/usr/src/libs/libc/*.o.  NOT BLODDY LIKELY.

In terms of "practical authority" I suggest you compare the contents of
<inode.h> and <ar.h>.  Archive entries are substancially variant from
WHATEVER your, or anybody elses, computers file-as-valid-system-object
concept is.

>>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.

I can think of things like "consistent refrencing"  "Raw device
information" "file length extension (e.g. oppen for append)"
"stream/socket information" "Open and closure tracking" and perhaps a
dozen reasons that a kernel could not use portable/common archive
formats for actual file manipulation.

The "FUNDAMENTAL PROBLEM" is that the ar format does not have the
flexability or space to provide the kernel with the things it needs to
work with (adding things to/changing the format makes it nolonger ar
format so don't go off on an "I'll just add..." kick; it would make you
look like a fool)

Additional problems include:  Having to read/lseek-past every entry
which procedes the entry you are intrested in.  No convient method for
going backwards without altering the format.  No "lookup" capibility.
Non-tabular format.  Inefficent storage method for random access of
contents.  (this list could be longer, but I have a life to get on
with.)

You can't just say "that's implementation dependant and so not
important"  because your statement is one on implementation.

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

Convienent way of avoiding personal falure, "I'll just skip it..."
Let me guess, you're a fundy, right?

>>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.]

Reading time/effort for a set nember of bytes X is identical no matter
where the X originates.  lseek is faster than open and close.  lseek
does not require any additional fiel table entries.  No steps were
ommited.

If I really had left anything out you would have mentioned them in some
detail instead of just deleting the entire thing and instering a
"fuzzing" generallity.

> 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.

While the extreme case, e.g. 1 object include, sometimes shows a
reduction, unfortunatley most of us compile things slightly more complex
than "hello world" programs.  Your second example also is a fraud in
that it didn't search through a directory containing all the *.o files
normally found in libc.a.  If it had you example would have failed.  In
your "good case" example you only search for the hw.o file mentioned in
the "bad case" portion not a directory containing many *.o files.

More clearly there is no "selection and resolution" phase involved in
your second example, by manually including all the objects ( with *.o )
you are instructing the loader to use "minimum" objects sepsified.  Your
example never invokes the unresolved refrences code that does all the
time consuming things we are discussing.

> -----
> % `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').

So you admit that you didn't scan the full 317, nor the directory that
contained a full 317, you only took the files you needed.  Invalidating
your example.

If you had scanned the full 317 in example 2 using the command indicated
the resulting executable would have been HUGE and this size difference
alone would be the penalty for the "speed" you "gained."  You can, after
all, include any unrelated objects in a load that you chose, so the
loader doesn't have to think about the load much, so it runs faster, so
it wastes 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.

Compare this to:

Read each .a file once.  Juggle the same pointers necessary in both
examples.  Write output.  exit.

LD(1) says that:  If any argument is a library, it is searched exactly
once at the point it is encountered in the argument list.  (order is
only significant in symbol conflict, etc.)

>>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.)

(in terms of directory scanning)

Scan #1:  Looking for the directories mentioned (e.g. scanning parent
	directories)
Scan #2:  Looking for the .Symtab file.  Repeat #3 for each "archive"
	named.  e.g. /usr/lib/libcurses /usr/lib/libc /usr/lib/libm
	or whatever
Scan #n:  Looking for individual .o files  (then of course there is the
	opening and reading and closing of whatever.)
[Scanning can be reduced with potentially infinite disk buffering, but
who has infinite real memory to put it in?]

Please compare this to:

Scan #1:  Looking for the files mentioned (then of course there is the
	opening and reading and closing of whatever single files.)

Your example is artifically fast because you already did the search and
extract phase manually.  what was the "time" on that?

>>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.
>>[elipisis (...) represent conviently removed example of keyed
>>directory scanning (usenet) and arguments as to it's similarity to the
>>system purposed.]
> 
> 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.]

As already stated, your "hello world" example is not accurate because
you did the extraction manually before hand, instead of having the
linker do an intellegent extract based on a symbol table.  The linker
will load as many arbitrary .o files as you like, and quite a lot faster
than the normal simbol refrencing and lookup which is encountered in
both schemes.  In your example there were no unresolved symbols nor
selective loading of objects done by the linker because you had doen the
selecting before hand.  How long did the selecting take you?  was it
longer then the .3u?

Rob.