neil@wcc.oz.au (Neil Murray) (01/23/91)
On recent perusal of my bookshelf I noticed a goodly number of
books on compiler theory but very little on linkers & loaders.
After a little searching I did find a piece on dynamic linking
contained in gnu sources "dld-3.2.1.tar.Z" on a local archive. There
is a research report available from the archive-server@decwrl.dec.com
_Link-Time Code Modification_ report 89/17.
The problem is both these reports deal with advanced techniques or
extensions to a standard linker. I'm after a text that covers linkers
from simple ones through overlay linkers to dynamic linkers. I've seem
loaders as simple as an absolute load and run to the vax/vms image
activator but little on the internal data structures used and algorithms
employed? What are the trade-offs in various techniques? Do linkers'
and loaders' capabilities affect compiler writers in non-obvious ways?
Speaking of capabilities what about capability architectures,
the requirements of the linker/loader must be quite different.
Does anyone know of some decent books on the subject?
---
Neil Murray (R&D Dept) Phone: +61 3 764-1100 Fax: +61 3 764-1179
Webster Computer Corporation, Email: neil@wcc.oz.au
PO Box 195, Ferntree Gully UUCP: {...,uunet}!munnari!wcc.oz.au!neil
Victoria, Australia, 3156.
[An excellent question. Linking is an important topic that is very poorly
treated in the literature. And yes, what you can ask the linker to do can
have significant effects on languages. For example, the fact that traditional
C allows you to have many different uninitialized definitions of a variable
is definitely related to the fact that Unix linkers handle the situation
well. (In many linkers "common" is a special case and there is a low limit
on the number of common areas allowed.) -John]
--
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.mwette@mr-ed.Jpl.Nasa.Gov (Matt Wette) (01/24/91)
In article <9101240056.16069@munnari.oz.au> Neil Murray writes: |> On recent perusal of my bookshelf I noticed a goodly number of |> books on compiler theory but very little on linkers & loaders. |> Does anyone know of some decent books on the subject? You may find some interesting information in G.R.Gircys, "Understanding and Using COFF," O'Reilly and Associates, 1988, ISBN 0-937175-31.5. which describes System V COFF loading. Matt -- Matthew R. Wette | Jet Propulsion Laboratory, 198-326 mwette@csi.jpl.nasa.gov | 4800 Oak Grove Dr, Pasadena,CA 91109 [Good suggestion -- though the book is mostly about the details of COFF, there are several chapters on relocation and linking in general. -John] -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.
wrc@cs.rit.edu (Warren R Carithers) (01/25/91)
The only real discussions of linkers and loaders which I have run across are
chapters in these books:
"System Software: An Introduction to Systems Programming", Second
Edition, Leland Beck; Addison-Wesley, 1990;
ISBN 0-201-50945-8
"Program Translation Fundamentals: Methods and Issues", Peter
Calingaert; Computer Science Press, 1988;
ISBN 0-88175-096-4
Beck discusses distinctions between linkers and loaders, dynamic loading,
linker/loader design options, etc., and has three case studies (System/370
linkage editor, VAX linker, and CYBER loader). This chapter is ~50 pp.,
and includes diagrams and algorithms to support the discussion.
Calingaert has a smaller discussion (~25 pp.) of the same issues. This
text also includes some additional discussion (e.g., the Transfer Vector
technique) not explicitly mentioned in Beck.
I use Beck in my Language Processors class, primarily for the case studies
included in each chapter. I have also received comments from students to the
effect that Beck's presentation is slightly more readable.
----
Warren R. Carithers, Rochester Institute of Technology, Rochester NY 14623-0887
Internet: wrc@cs.rit.edu, wrcics@ultb.isc.rit.edu (716) 475-2288
UUCP: {allegra,rutgers}!rochester!rit!wrc
--
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.clc5q@shamash.cs.Virginia.EDU (01/25/91)
Another source on linkers/loaders is :
"Systems Programming", by John J. Donovan, in the Computer Science
Series by McGraw-Hill, 1972. The book uses a simplified IBM 370-style
assembly language in its various chapters on systems programming topics.
There are chapters on Assemblers, Macro-Assemblers, Loaders/Linkers,
Programming Languages, Formal Languages, Compilers, and Operating Systems.
There is also an appendix on "Linkage Conventions." I don't care much
for the IBM 360/370 architecture or assembly language, but the book is
a good source for the assembler/macro-assembler/linker/loader info that
is rare in compiler books.
Assembler and linker/loader design for an 8080 microcomputer are discussed
in "Systems Programming for Small Computers," by Daniel H. Marcellus,
Prentice-Hall, 1984. Only about 10 pages on linkers/loaders. Also has
chapters on primitive ROM monitor operating system; CP/M operating system;
an interpreter for a subset of BASIC; a compiler for the same; text editor
design; assembler; macro-assembler; and multi-tasking operating systems
for micros.
Two early papers are listed in the bibliography of the loaders chapter in
Donovan's book:
McCarthy, John, Fernando J. Corbato and Marjorie M. Daggett: "The Linking
Segment Subprogram Language and Linking Loader," CACM, vol. 6, no. 7,
June, 1963, pp. 391-395.
McGee, W.C.: "On Dynamic Program Relocation," IBM Systems Journal, vol. 4,
no. 3, 1965, pp. 184-199.
I also recall Bill Gear's book, "Computer Organization and Programming,"
from about 1969; does anyone have a copy to check for linker/loader info?
Clark Coleman
clc5q@virginia.edu
University of Virginia Computer Science
--
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.jones@pyrite.cs.uiowa.edu (Douglas W. Jones) (01/25/91)
In article <9101240056.16069@munnari.oz.au> Neil Murray writes: > On recent perusal of my bookshelf I noticed a goodly number of > books on compiler theory but very little on linkers & loaders. Perhaps this article would help: D. W. Jones. "Assembly Language as Object Code." Software Practice and Experience, Vol 13, No. 8, pages 715-725. In this paper, I point out that a decent assembler (with macro and conditional features, as well as a source inclusion directive) can do everything we usually associate with linkage editors from the FORTRAN generation (with the exception of automatic overlay management). The particular assembler described in this paper is available from me on request. Doug Jones jones@cs.uiowa.edu -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.
Christian.Collberg@DNA.LTH.Se (Christian S. Collberg) (01/27/91)
Here is my BibTeX file of articles on linking and loading. There are also
some articles on unusual uses of link-editors.
============================================================================
@STRING{CS="Computing Surveys"}
@STRING{SPE="Software---Practice and Experience"}
@STRING{SIGPLAN="SIGPLAN Notices"}
@STRING{SOFTENG="IEEE Transactions on Software Engineering"}
@STRING{CSLund="Department of Computer Sciences, Lund University"}
@CONFERENCE{Kieburtz78,
AUTHOR = "R.B. Kieburtz and W. Barabash and C.R. Hill",
TITLE = "A Type-Checking Program Linkage System for {Pascal}",
BOOKTITLE = "3rd International Conference on Software Engineering",
PAGES = {23--28},
ADDRESS = "Atlanta, GA, USA",
MONTH = may,
YEAR = 1978}
@ARTICLE{Rudmik82,
AUTHOR = "Andres Rudmik and Barabara G. Moore",
TITLE = "An Efficient Separate Compilation Strategy for
Very Large Programs",
JOURNAL = SIGPLAN,
PAGES = {301--307},
MONTH = jun,
YEAR = 1982}
@ARTICLE{Barringer79,
AUTHOR = "H. Barringer and P.C. Capon and R. Philips",
TITLE = "The Portable Compiling Systems of {MUSS}",
JOURNAL = SPE,
VOLUME = 9,
PAGES = {645--655},
YEAR = 1979}
@CONFERENCE{Ancona84,
AUTHOR = "M. Ancona and L. De Floriani and D. Dodero and P. Thea",
TITLE = "Program Development by Using a Source Linker",
BOOKTITLE = "4th Jerusalem Conference on Information technology (JCIT).
Next Decade in Information Technology",
PAGES = {251--259},
ADDRESS = "Jerusalem, Israel",
MONTH = may,
YEAR = 1984}
@ARTICLE{Presser72,
AUTHOR = "Leon Presser and John R. White",
TITLE = "Linkers and Loaders",
JOURNAL = CS,
VOLUME = 4,
NUMBER = 3,
PAGES = {149--167},
MONTH = sep,
YEAR = 1972}
@TECHREPORT{Collberg86,
AUTHOR = "Christian S. Collberg and Magnus G. Krampell",
TITLE = "Pasters: Linkers in a Modular World",
INSTITUTION = CSLund,
TYPE = "Technical Report",
NUMBER = "CODEN: LUNDFD6/(NFCS-7002)/(1-27)(1986)",
YEAR = 1986}
@CONFERENCE{Collberg87a,
AUTHOR = "Christian S. Collberg and Magnus G. Krampell",
TITLE = "Design and Implementation of Modular Languages
Supporting Information Hiding",
BOOKTITLE = "Proceedings of the Sixth International Phoenix Confernece
on Computers and Communications",
PAGES = {224--228},
ADDRESS = "Scottsdale, AZ, USA",
MONTH = feb,
YEAR = 1987}
@CONFERENCE{Wall86,
AUTHOR = "David W. Wall",
TITLE = "Global Register Allocation at Link Time",
BOOKTITLE = "Proceedings of the SIGPLAN'86 Symposium
on Compiler Construction",
ADDRESS = "New York",
PAGES = {264--275},
MONTH = "",
YEAR = 1986}
@CONFERENCE{Benitez88,
AUTHOR = "Manuel E. Benitez and Jack W. Davidson",
TITLE = "A Portable Global Optimizer and Linker",
BOOKTITLE = "Proceedings of the SIGPLAN'88 Conference
on Programming Language Design and Implementation",
PAGES = {329--338},
ADDRESS = "Atlanta, GA, USA",
MONTH = jun,
YEAR = 1988}
@ARTICLE{Fraser82,
AUTHOR = "Christopher W. Fraser and David R. Hansson",
TITLE = "A Machine-Independent Linker",
JOURNAL = SPE,
VOLUME = 12,
PAGES = {351--366},
YEAR = 1982}
@INCOLLECTION{Eulenstein82,
AUTHOR = "M. Eulenstein",
TITLE = "An Extension to {Pascal} for Modular Programming and a Proposal
of a Conceptionally Machine Independent Linker",
BOOKTITLE = "Implementierung {Pascal}-artiger Programmiersprachen",
EDITOR = "H. Langmaack and B. Schlender and J.W. Schmidt",
ADDRESS = "Stuttgart",
PUBLISHER = "B.G. Teubner",
YEAR = 1982}
@CONFERENCE{Celentano78,
AUTHOR = "A. Celentano and P.Della Vigna and C. Ghezzi and D. Mandrioli",
TITLE = "Modularization of Block-structured Languages: Thr Case of Pascal",
BOOKTITLE = "Workshop on Reliable Software"
ADDRESS = "Bonn, Germany",
PAGES = {167--79},
MONTH = sep,
YEAR = 1978}
@CONFERENCE{Celentano80,
AUTHOR = "A. Celentano and P.Della Vigna and C. Ghezzi and D. Mandrioli",
TITLE = "Separate Compilation and Partial Specification in Pascal",
JOURNAL = SOFTENG,
VOLUME = 6,
PAGES = {320--328},
MONTH = JUL,
YEAR = 1980}
=============================================================================
Christian.Collberg@dna.lu.se
--
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.