![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to run.tex CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / sml / doc / papers / runtime|
Return to run.tex CVS log | Up to [Research Unix] / researchv10no / cmd / sml / doc / papers / runtime |
1.1 root 1: \documentstyle[11pt]{article}
2: \bibliographystyle{plain} %changed from alpha
3: \documentstyle{openbib}
4: \makeindex
5: \oddsidemargin .5in % Left margin on odd-numbered pages.
6: \evensidemargin .5in % Left margin on even-numbered pages.
7: \topmargin .5in % Nominal distance from top of page to top of
8: \headheight 0pt % Height of box containing running head.
9: \headsep 0pt % Space between running head and text.
10: % Bottom of page:
11: \footheight 12pt % Height of box containing running foot.
12: \footskip 30pt % Distance from baseline of box containing
13: % foot to baseline of last line of text.
14: \textwidth 5.5in % width of text on page
15:
16: %\newcommand{\mysection}[1]{\section{\protect\large\bf #1}}
17: %\setcounter{secnumdepth}{0}
18:
19: \sloppy
20:
21: \begin{document}
22: \title{A Runtime System \\ (DRAFT)}
23: \author{Andrew W. Appel\thanks{
24: Supported in part by NSF Grants
25: DCR-8603453 and CCR-880-6121}
26: \\ Princeton University}
27: \date{February 1989}
28: \maketitle
29: \begin{abstract}
30: The runtime data structures of the Standard ML of New Jersey compiler
31: are simple yet general. As a result, code generators are easy to implement,
32: programs execute quickly, garbage collectors are easy to implement and
33: work efficiently, and a variety of runtime facilities can be provided with
34: ease.
35: \end{abstract}
36:
37: \section{Introduction}
38: \label{introduction}
39:
40: Some languages, like Lisp, Smalltalk, ML, Prolog, etc. rely heavily on a
41: {\em runtime system} to provide essential services. The most important
42: such service is the management of dynamically-allocated storage
43: (e.g. {\bf garbage collection}), but the runtime system may also provide
44: facilities like
45:
46: \begin{itemize}
47: \item {\bf Stream input/output:} on operating systems (like Unix) that do not
48: have a buffered input/output facility, the process must provide its own;
49: this might be handled in the runtime system.
50: \item {\bf Structured input/output:} the ability to automatically
51: write a large linked data structure to a file, and read it back in
52: with all links adjusted, is a great convenience that can be implemented
53: efficiently in the runtime system.
54: \item {\bf Process suspension:} a snapshot of an
55: executing process may be ``preserved'' in a file, so that
56: the execution of that file causes a new process to start exactly
57: where the saved one left off.
58: \item {\bf Operating system calls:} operating system services needed by
59: a program may be conveniently packaged by the runtime system.
60: \item {\bf Handling of interrupts and asynchronous events:} if the programming
61: language has a mechanism to handle asynchronous events, it relies on the
62: runtime system for its implementation.
63: \item {\bf Handling of arithmetic exceptions:} the programming language's
64: exception-handling mechanism must be implemented in cooperation with
65: the runtime system.
66: \item {\bf Assembly-language implementation of language primitives:}
67: it may be inconvenient for the compiler to generate code for some features
68: of the programming language; these functions can be implemented as calls
69: to runtime system routines.
70: \item {\bf Foreign-language procedure calls:} calls to subroutines written
71: in other languages may be mediated by the runtime system.
72: \item {\bf Fun with continuations:} Languages with features like {\em call with
73: current continuation}, which allows the explicit manipulation of threads
74: of control, require runtime-system cooperation.
75: \item {\bf Execution profiling:} Automatic measurement of the time spent in
76: different parts of the user program can be accomplished with the help of
77: the runtime system.
78: \item {\bf Debugging:} starting, stopping, and displaying the execution state
79: of user programs can be accomplished only by low-level routines.
80: \end{itemize}
81:
82: Since this list is rather long, and several of these features may interact,
83: it is evident that runtime systems can become nasty and complicated.
84: The proliferation of data types may make the implementation of
85: the garbage collector (and other programs that must traverse the data)
86: inefficient.
87:
88: We particularly wanted a runtime data layout that provided fast
89: allocation of records and fast garbage collection, since ML makes very
90: heavy use of dynamically-allocated storage. To this end, we eliminated
91: the runtime stack and use a very simple data format.
92: The only runtime data types are {\em integers}, {\em pointers},
93: {\em records}, and {\em strings}.
94: Then we found that this very simple structure allowed the easy implementation
95: of many of the services described above.
96:
97: Our runtime system has relatively few ML-specific
98: features; it could be used equally well for other languages. This paper
99: describes the design and implementation of the SML-NJ runtime system.
100: It should be read in conjunction with an earlier paper on the
101: SML-NJ generational garbage collector\cite{appel89:sggc}.
102:
103: \begin{quotation}{
104: \small Text in smaller type is of interest only to those who might
105: have to read, modify, or maintain the source code to the runtime system.
106: }\end{quotation}
107:
108: \section{Standard ML of New Jersey}
109: \label{standard}
110: The ML language originated as part of the Edinburgh LCF proof system
111: \cite{gordon78}, and was soon implemented as a stand-alone compiler
112: \cite{cardelli83:ml}\cite{cardelli84}. The language was
113: ``standardized'' \cite{milner84}\cite{macqueen84}
114: \cite{milner85}\cite{harper88}, and
115: Standard ML has been implemented at Edinburgh, Cambridge, and
116: New Jersey\cite{appel87:sml}; the New Jersey implementation is
117: a joint effort between researchers at AT\&T Bell Laboratories and
118: Princeton University.
119:
120: Though ML was first implemented as the meta-language of a theorem-proving
121: system, Standard ML is a general-purpose
122: programming language with several advantages over more conventional
123: languages. Its important characteristics are:
124:
125: \begin{itemize}
126: \item {\bf Automatic garbage collection:} this is a great convenience in
127: writing correct and readable programs.
128: \item {\bf Static, polymorphic types:} like Pascal, types are checked
129: at compile-time and not at runtime; but like Lisp, there is great flexibility
130: and re-usability of code.
131: \item {\bf Safety:} there are no runtime insecurities (i.e. ``core is never
132: dumped''); this is unlike the C language, where unsafe pointers run
133: rampant, and like Lisp (except when Lisp programmers turn off the runtime
134: type checking for efficiency). In ML, there is no run-time type checking,
135: but safety is guarateed by compile-time type checking.
136: \item {\bf Higher-order functions:} like Scheme (and lambda-calculus); this
137: can lead to a desirable conciseness of expression.
138: \item {\bf Typechecked Modules:} like Ada and Modula.
139: \item {\bf Exception handling:} a dynamically-scoped exception
140: mechanism allows both hardware- and software-generated exceptions
141: to be caught and handled by user programs.
142: \end{itemize}
143:
144: One important feature of a systems programming language
145: is not prescribed by the list above, and in fact cannot be specified
146: by a language definition: an efficient and robust implementation.
147: Standard ML of New Jersey\cite{appel87:sml} is meant to be a complete,
148: efficient, robust, and cleanly written compiler for the language.
149: It has an optimizing code generator based on continuation-passing style
150: \cite{appel89:cps}.
151:
152: A knowledge of ML is not necessary to understand its runtime system.
153:
154: \section{Tagging schemes}
155: \label{tagging}
156:
157: Almost all the pieces of the runtime system must deal with the data structures
158: of the executing program. Therefore, it is helpful to keep the format of
159: this data as simple and straightforward as possible.
160:
161: ML, like Lisp, allows polymorphic functions: a function that reverses a list
162: of objects (for example) need not know the type of the objects. In order that
163: the same piece of executable code can operate on objects of arbitrary type,
164: it is necessary that every object be represented in the same amount of space.
165: As in Lisp, this is achieved by making everything be the size of a pointer;
166: if an object's natural representation is larger (as for a record of $n$
167: objects), then it is represented by a pointer to storage on the heap.
168:
169: The garbage collector must be able to determine the size and layout of each
170: object it traverses. This can be accomplished in several ways:
171: \begin{itemize}
172: \item {\bf By encoding a type-tag\index{tag}
173: inside each pointer;} we chose not to do this
174: because it reduces the number of bits left for actual addressing.
175: In these days of 32-bit pointers and 100-megabyte memories, it is easy
176: to imagine the need for every bit of addressability we can muster.
177: \item {\bf By reserving different areas of memory for objects of different
178: types.}
179: BIBOP\index{BIBOP} (Big Bag Of Pages) schemes require that each page hold objects of a single
180: type, and a global table maps pages to types. This is relatively efficient,
181: and doesn't reduce the number of addressable words. But it complicates the
182: process of allocating and copying objects, since several free regions
183: are simultaneously required.
184: \item {\bf Statically-typed languages don't require any runtime-tagging} at all;
185: instead, the compiler can tell the garbage collectector about the type
186: system of the program. This has worked well in Pascal\cite{britton75}.
187: Even though it is also theoretically possible in ML, in practice the
188: polymorphic type system introduces overhead and complexity that make
189: this method unattractive\cite{appel89:tag}.
190: \item {\bf Each record can have a descriptor at the beginning} that explains
191: which fields are integers and which are pointers. This method works
192: well in non-polymorphic languages like Modula-2+ and Mesa, where
193: descriptors can be computed at compile-time and just inserted
194: in records as they are created. However,
195: in polymorphic languages like Lisp and ML
196: this descriptor would have to be laboriously
197: constructed each time a record is created, introducing unacceptable overhead.
198: \item {\bf Each record can have a descriptor\index{descriptor} at the
199: beginning} that tells
200: the length of the record, and {\bf each field can have a tag bit} that tells
201: whether it is a pointer or a non-pointer.
202: This is what we have done.
203: \end{itemize}
204:
205: To have a tag word on each record, and a tag bit on each
206: field, is not clever at all; but we are not always
207: striving for cleverness, we
208: want simplicity and efficiency. If all our records were {\em cons} cells,
209: then one-third of memory would be devoted to tag words; but memories
210: are large and cheap. And in Standard ML, records are of many different
211: sizes, and two-word records are not particularly predominant.
212:
213: By having only one free region, we are
214: able to do fast allocation\index{allocation}
215: and also manage the total amount of virtual
216: memory used\cite{appel89:sggc}; this would be much more difficult
217: with a BIBOP scheme.
218:
219: \section{Data formats in our runtime system}
220: \label{data}
221: Standard ML of New Jersey has
222: records, strings, procedures (machine code),
223: closures, constructors, arrays, byte-arrays, floating-point
224: numbers, references (modifiable one-word records),
225: modules, and integers. This large set of language primitives and
226: user-defined datatypes are represented
227: by just two runtime data formats: one for objects that contain pointers
228: (records, closures, constructors, arrays, references, modules), and
229: the other for objects containing no pointers (strings, procedures,
230: byte-arrays, floating point). The garbage collector (and other
231: parts of the runtime system) need to understand only these two formats,
232: not the many kinds of ML objects.
233:
234: A {\em field\index{field}} is either a
235: {\em pointer\index{pointer}} or an {\em integer\index{integer}}. Pointers
236: have a low-order bit of 0; integers have a low-order bit of 1.
237: It is necessary to distinguish pointers from non-pointers in order that
238: the garbage collector\index{garbage collector}
239: will know what structures to traverse.
240: On a byte-addressable machine, all pointers to aligned (4-byte) words
241: are multiples of 4 anyway, so pointers have a low-order bit of 0 in
242: their natural representation. The high-order 31 bits of an integer
243: field can represent an integer in the range $[-2^{30}, +2^{30}-1]$.
244:
245: Some Lisp implementations use a similar representation except that
246: pointers have a low-order 1 and integers have a low-order 0. This makes
247: arithmetic on tagged integers somewhat easier, and takes advantage
248: of the fact that pointers are usually used with a displacement addressing mode;
249: the displacement can be adjusted by 1 with no penalty in efficiency.
250: This is probably a better arrangement, but
251: either version of this scheme will work; and a simple analysis\cite{appel89:tag}
252: shows that the efficiency trade-offs are negligible, and that
253: doing arithmetic around the low-order integer tag is not very costly.
254:
255: An {\em object on the heap} may be either a {\em record\index{record}}
256: (containing fields,
257: i.e. pointers and tagged integers) or
258: a {\em string\index{string}}
259: (containing bytes of an arbitrary bit-pattern, but no pointers).
260:
261: A {\em record} is a sequence of $n>0$ fields numbered $0,1,...,n-1$.
262: Each record has a {\em descriptor} at position $-1$. The low-order bit
263: of a descriptor\index{descriptor} is 1
264: (making it look like an integer), the next three
265: bits identify the object as a record, and the high-order 28 bits give the
266: number of fields. Thus, each record is limited to one gigabyte, which
267: should not be a significant limitation (seriously, though, it is important
268: to avoid miserly restrictions on the sizes of objects).
269:
270: In the implementation of closures, it is useful to be able to point
271: at the interior of records. However, it is always necessary for the
272: garbage collector, given a pointer, to find the descriptor of an object.
273: If the
274: fields $0$ through $k-1$ of a record are all pointers, then a pointer
275: can point at the $k^{\rm th}$ field of the record; since the
276: descriptor is unboxed (has a low-order bit of 1) and the fields $0$ through
277: $k-1$ will all be boxed, the garbage collector can easily search backward
278: for the descriptor of the record. So, we allow pointers to the interior
279: of a record, providing all the previous fields are boxed; this is sufficiently
280: flexible for our needs in implementing closures, as will be described.
281: Otherwise,
282: no pointer may address the interior of a record.
283:
284: A {\em string\index{string}}
285: contains $n>0$ bytes (numbered from $0$ to $n-1$),
286: padded with trailing zero bytes
287: to a multiple of four.
288: Immediately preceding the $0^{\rm th}$ byte is a one-word
289: descriptor whose low-order bit is 1, whose next three bits describe
290: the type of string (and distinguish strings from records),
291: and whose upper 28 bits give the length in bytes.
292:
293: Strings are used for a variety of purposes;
294: they can hold printable characters, real numbers, machine code,
295: or any other kind of data that doesn't contain pointers. In fact,
296: a string object can hold several embedded string objects.
297: A pointer may point at the $0^{\rm th}$ byte of a string, and may point to
298: an embedded string at the
299: $k^{\rm th}$ byte provided that $k>0$ is a multiple of 4 and that the bytes
300: $k-4, k-3, k-2, k-1$ contain a {\em back-pointer\index{back-pointer}}
301: descriptor that
302: contains the number $k$ (the offset to the beginning of the record).
303: This allows the beginning of a string object
304: to be found quickly, given a pointer into it.
305: Note that a back-pointer couldn't be distinguished from data, except
306: for the fact that it is found just before the pointed-to byte of the
307: string.
308:
309: The three tag\index{tag} bits of a descriptor\index{descriptor}
310: can denote any of these kinds of records,
311: strings, etc:
312:
313: \begin{itemize}
314: \item[0] record\index{record}
315: \item[1] forwarding-pointer\index{forwarding pointer}
316: (for the garbage collector\index{garbage collector})
317: \item[2] back-pointer (that precedes an referenceable location in a string)
318: \item[3] embedded string\index{embedded string} length (described below)
319: \item[4] array\index{array} (just like a record).
320: \item[5] byte-array\index{byte-array}
321: (just like a string).
322: \item[6] this tag value is unused.
323: \item[7] string\index{string}
324: \end{itemize}
325:
326: Because of ML's static type system, it is not necessary to put type information
327: in the descriptors of objects. Therefore, tags are necessary only
328: for the garbage collector's benefit, since it must distinguish objects of
329: different formats.
330:
331: The only exception to this rule is that mutable objects (arrays, byte-arrays)
332: must be distinguishable from immutable objects (records, strings)
333: in order to implement the polymorphic
334: equality\index{equality}
335: feature. For all purposes of the runtime system, arrays
336: are identical to records, and byte-arrays are identical to strings.
337:
338: A dynamically-typed language like Lisp would require more than
339: three bits to distinguish types of objects; this would not pose a
340: serious problem. It would still be possible in Lisp to have just
341: two formats (pointer-containing and pointer-free), as in our runtime system.
342:
343: \section{Forwarding pointers}
344: \label{forwarding}
345: \index{forwarding}
346: The Standard ML of New Jersey runtime system has a generational garbage
347: collector\index{garbage collector}
348: that takes advantage of object lifetime and referencing
349: patterns\cite{appel89:sggc}.
350: But at the heart of any generational garbage collector is a simple
351: copying garbage collector as originally described by Cheney\cite{cheney70}.
352: Objects are copied from {\em fromspace} to {\em tospace} in a breadth-first
353: order, with the {\em tospace} itself serving as the queue for the breadth-first
354: traversal. The {\em fromspace} versions of objects are overwritten
355: with {\em forwarding pointers}, so that when other references to them are
356: found, it is easy to find the {\em tospace} copies of them.
357:
358: The fundamental operation in Cheney's algorithm is to {\em forward} a pointer.
359: This means taking a pointer into {\em fromspace} and making it point to {\em tospace}.
360: If the {\em fromspace} object it points to has already been copied, then its
361: forwarding pointer is taken as the new value; otherwise, the object must
362: be copied to {\em tospace} and a forwarding pointer installed.
363:
364: Forwarding is relatively easy using our runtime data format. We have a special
365: kind of descriptor {\bf forwarding-pointer}, that indicates that a {\em fromspace}
366: object has already been copied. If an object has this descriptor, then
367: the first word (after the descriptor) is to be interpreted as the address
368: of the copy. The only complications in forwarding are that pointers
369: may point into the middle of records and strings.
370:
371: Our runtime system (and garbage collector) is implemented in C.
372: In figures~\ref{forward}, \ref{trappc}, \ref{gc} we show the entire
373: core of our copying garbage collector. We could use pseudo-code
374: and describe the algorithm abstractly, but we want to emphasize that
375: our simple runtime data format does permit an efficient and easy-to-implement
376: garbage collector.
377:
378: We pretend that all ML values are integers, and make liberal use of
379: casts to maintain this pretense. Our \verb"forward" function is
380: shown in figure~\ref{forward}; it
381: takes an ML value (by reference) and modifies it (if a pointer into
382: {\em fromspace}) to point into {\em tospace}.
383: \begin{figure}[htbp]
384: \label{forward}
385: \begin{verbatim}
386: 1 forward(int *refloc)
387: 2 {register int *m = *((int**)(refloc)), len;
388: 3 if( (m&1)==0 && (m >= (int*)lowest && m < (int*)highest))
389: 4 { m--; /* make m point at the descriptor */
390: 5 while(1)
391: 6 {len = (*m)>>4;
392: 7 switch(m&15)
393: 8 {case tag_backptr:
394: 9 m -= len;
395: 10 continue;
396: 11 case tag_string:
397: 12 case tag_bytearray:
398: 13 len = (len+3)/4;
399:
400: 19 /* fall through */
401: 20 case tag_record:
402: 21 case tag_array:
403: 22 {int **i=(int**)m, **j=to_ptr;
404: 23 while (j+len >= to_lim)
405: 24 do to_lim=gmore();
406: 25 while (len-- >= 0)
407: 26 do {*j++ = *i++;}
408: 27 ((int**)m)[1]= 1+(int*)to_ptr;
409: 28 to_ptr = j;
410: 29 }
411: 30 (*m) = tag_forwarded;
412: 31 /* fall through */
413: 32 case tag_forwarded:
414: 33 *(int*)(refloc) += ((int*)m)[1] - ((int)(m+1));
415: 34 return;
416: 35 case tag_embedded:
417: 36 default:
418: 37 m--; continue;
419: 38 }} } }
420: \end{verbatim}
421: \caption{The {\tt forward} function}
422: \end{figure}
423: Line 2 establishes $m$ as a copy of the original value to be forwarded.
424: Line 3 considers only the case that $m$ is a pointer, and points into
425: {\em fromspace}. (Any pointers not into {\em fromspace} are treated as constants.)
426: Line 4 adjusts m to point at the descriptor of the {\em fromspace} object.
427:
428: Lines 5--38 loop until the beginning of the object is found.
429: If [line 8] $m$ points to a back-pointer\index{back-pointer},
430: the appropriate offset is subtracted
431: and we start again; similarly, if [lines 35,36] $m$ points to a pointer
432: (which can happen if we
433: point into the middle of a closure\index{closure} record) or an
434: embedded\index{embedded string} descriptor,
435: then $m$ is decremented and we try again.
436:
437: If $m$ is a string\index{string length} or byte array [line 13],
438: then we adjust its $len$ to count in words rather
439: than bytes (i.e. we divide by 4, rounding up).
440: (Lines 14--18 are explained below.)
441:
442: Now at line 22 we have either a string or record in {\em fromspace}
443: that needs to be copied. We verify that there's enough space remaining
444: in {\em tospace}; if not, we call the function \verb"gmore" that will either
445: \index{gmore}
446: get more space or die trying. Then we copy all the words of the
447: object. Finally [lines 27 and 30] we install a forwarding pointer
448: into the {\em fromspace} object and mark its descriptor as forwarded.
449:
450: For an already forwarded object (line 33), whether it was forwarded
451: in a previous call or just now, adjust the reference \verb|*refloc|
452: to point at the new object. Since the reference might have pointed
453: at the middle of the old object, we must take care to make it point
454: to the corresponding location in the new object; this is accomplished
455: by the computation:
456: \[
457: {\rm old\;pointer} + {\rm beginning\;of\;new\;object} -
458: {\rm beginning\;of\;old\;object.}
459: \]
460:
461: Then the \verb"forward" function returns.
462:
463: Almost without exception, all pointers to objects point to places where
464: an immediately preceding descriptor\index{descriptor}
465: explains the format of the object.
466: The exception is an artifact of the
467: very fast allocation mechanism that can create and initialize
468: a $k$-word object in $k+2$ instructions\cite{appel89:sggc}.
469: This mechanism relies on a page fault\index{fault}
470: trap to invoke the garbage collector
471: when the free space is exhausted; when this trap occurs, the program
472: \index{pc}
473: counter will point into the middle of a string object that might
474: be moved by the garbage collector. This is the only reference that
475: points to a place in a string that lacks a backpointer\index{back-pointer}.
476: It can be handled
477: relatively simply: as each string object is moved, we check to see
478: if the saved program counter points into the middle of it; if so,
479: we adjust the saved program counter. Since the number of string objects
480: is typically less than one percent of the number of record objects,
481: very costly overall. The test occurs at line 14, as shown in
482: figure~\ref{trappc}.
483: \index{trap_pc}
484: \begin{figure}[htbp]
485: \label{trappc}
486: \begin{verbatim}
487:
488: 14 if (!trap_pc_done
489: 15 && m < trap_pc && m+len >= trap_pc)
490: 16 {trap_pc_done=1;
491: 17 trap_pc += to_ptr - (int**)m;
492: 18 }
493: \end{verbatim}
494: \caption{Testing the (saved) program counter}
495: \end{figure}
496:
497: \section{Garbage collection}
498: \label{garbage}
499:
500: Once the \verb"forward"ing procedure is written, a simple copying garbage
501: collector is trivial (figure~\ref{gc}).
502: \index{garbage collector}
503: \begin{figure}[htbp]
504: \label{gc}
505: \begin{verbatim}
506: 1 gc(int *from_low, int *from_high,
507: 2 int *to_low, int *to_high,
508: 3 int **roots,
509: 4 int *trap_pcx, int *(*get_more)()
510: 5 )
511: 6 { gmore=get_more; trap_pc = *trap_pcx; to_ptr = to_low;
512: 7 trap_pc_done = !(trap_pc>=(int*)from_low
513: 8 && trap_pc<(int*)from_high);
514: 9 lowest=from_low; highest=from_high;
515:
516: 10 while (*roots) forward(*roots++);
517:
518: 11 { int *x = to_low;
519: 12 while (x<to_ptr)
520: 13 { int *p = x+1, descr = (*x), len=descr>>4;
521: 14 if (string_or_bytearray(descr))
522: 15 x += (len+3)/4 + 1;
523: 16 else {x += len+1;
524: 17 do {forward(p++);} while (p<x);
525: 18 } }
526:
527: 19 *trap_pcx = trap_pc;
528: 20 }
529: \end{verbatim}
530: \caption{The {\tt gc} function}
531: \end{figure}
532: The function \verb|gc| is parametrized by the lower and upper bounds
533: of {\em fromspace} and the lower and upper bounds of {\em tospace}. The \verb"roots"
534: parameter is a vector of pointers to the roots of accessible objects;
535: in the Standard ML system this is little more than the addresses of
536: saved machine registers. The last two parameters are the address
537: of the saved program counter (necessary as explained in
538: section~\ref{forwarding})
539: and the address of a function which can be called to expand the {\em tospace}
540: if necessary.
541:
542: The first step [lines 6--9] is to put various quantities into global
543: variables to make them accessible to the \verb"forward" procedure,
544: since C does not have nested procedures.
545:
546: The next step is to forward all the root variables (line 10).
547:
548: Finally [lines 11-18],
549: we forward each word of each record in {\em tospace}. Since the
550: \verb|forward| procedure may increment the \verb"to_ptr" variable
551: that denotes the end of the filled portion of {\em tospace}, we have to
552: keep iterating until \verb|x| catches up with it. In effect,
553: the {\em tospace} between \verb|x| and \verb|to_ptr| is the queue of the
554: breadth-first search. The queue must eventually become empty,
555: since there is a finite amount of accessible data to be copied.
556: In this phase, integers (and strings) are just skipped, since
557: they contain no pointers that need forwarding.
558:
559: This garbage collector is relatively simple, and therefore it's not difficult
560: to make it fast. Even the fanciest of generational or concurrent collectors
561: relies on a program like this as its inner loop; the very simple layout
562: of data in the Standard ML runtime system makes efficiency easy.
563:
564: \section{Fast allocation}
565: \label{fast}
566:
567: Copying garbage collection, because it takes time proportional only to the
568: live data and not to the amount of garbage, can be arbitrarily
569: efficient\cite{appel87:gc}. That is, there is no lower bound on the
570: amortized cost of garbage collection for each cell allocated.
571: Standard ML's generational copying garbage collector\cite{appel89:sggc}
572: expends on the order of one (amortized)
573: machine instruction for every cell allocated; the precise amortized
574: cost is proportional to the ratio of live data to heap size.
575:
576: Since garbage collection is so fast, it makes sense to make
577: allocation\index{allocation}
578: fast too. Standard ML of New Jersey allocates a new record every
579: 40 to 80 machine instructions, so we want a very low overhead on the
580: creation of an object.
581:
582: Since copying garbage collectors compact the live objects into consecutive
583: memory cells, the free region is all contiguous. This means that to create
584: an $n$-word object, we can just grab the next $n$ words of the free space.
585: Since objects are created so often, it makes sense to make allocation
586: in-line (with no procedure call) and to reserve a register \verb"fr" to point
587: to the beginning of the free region. Then it becomes very simple
588: to allocate a new object: \verb"A = CONS(B,C)" is implement as
589: \begin{enumerate}
590: \item mem[fr+2] := C
591: \item mem[fr+1] := B
592: \item mem[fr] := descriptor(2,tag\_record)
593: \item A := fr+1
594: \item fr := fr+3
595: \end{enumerate}
596: Each of these lines is one machine instruction. Thus, in five instructions
597: (plus one instruction of amortized garbage collection overhead)
598: we have made a new {\em cons} cell; it takes only twice as long to create
599: a data structure as it does to read it!
600: This fast allocation encourages a simple and clean programming style;
601: no longer do programmers have to stand on their heads to avoid {\em cons}ing.
602:
603: Of course, this won't work if the free region is exhausted. We can insert
604: an explicit test to make sure that \verb"fr" is not near the end of the
605: free region. But a more clever trick is to make the virtual memory page
606: at the end of the free region inaccessible, so that we will get a page
607: fault\index{fault}\index{page fault}
608: when the free region is exhausted. That's why we store the
609: last field (\verb"mem[fr+2]") first in the example above; it's simpler
610: for the garbage collector if the fault occurs at the very beginning
611: of creating the new cell.
612: (On the MC68020, the state of the machine at a page fault is complicated,
613: and it's not easy to restart the faulting instruction; so on that machine
614: we use an explicit comparison with a limit register.)
615:
616: The page fault will be caught by the hardware and handed to the operating
617: system, which can then pass control to the user process. The user process
618: then has to find all the registers of the faulting procedure; these
619: registers are the roots of the accessible data. Appel\cite{appel89:sggc}
620: and Cormack\cite{cormack88} both describe schemes for finding these
621: registers; Cormack's is simpler and more reliable.
622:
623: The ML program and the garbage collector behave like two processes
624: (threads\index{thread})
625: running in the same address space: while one thread executes, the
626: other's registers are saved. When ML suspends itself (either
627: because of a page fault indicating end of free space, or voluntarily),
628: it saves its registers into a static area that looks just like a process
629: control block, so that the garbage collector (and other parts of the
630: runtime system) can access them.
631:
632: \begin{quotation}
633: {\small Here's how Cormack's scheme works: A page fault arrives, causing
634: the operating system to invoke the C function \verb"ghandle".
635: \index{ghandle}
636: This function is passed (as an argument) a structure containing
637: the address of the faulting instruction. Other saved registers are
638: at undocumented locations on the stack. \verb"ghandle" saves the
639: \index{saved_pc}\index{pc}
640: faulting pc in \verb"saved_pc", and modifies its argument structure
641: to point to the assembly-language function \verb"saveregs". Then it
642: returns; the operating system restores the pc from the argument
643: structure, restores other registers (from those undocumented locations),
644: and resumes. But of course, we have fooled the operating system into
645: \index{saveregs}
646: resuming in \verb"saveregs", which stores all registers into known
647: global variables and returns to the C thread (i.e. in the function
648: \verb"runML").
649:
650: The C thread (typically) does garbage collection, then calls the
651: assembly-language function \verb"restoreregs", which loads registers
652: (and program counter) from their global variables and resumes execution
653: of the ML thread.
654:
655: Sometimes it's useful to invoke the C thread without a page fault,
656: e.g. to export the process state into a file or to do a structured
657: write. In this case, \verb"saveregs" can be called directly from assembly
658: code in the ML thread.
659: }
660: \end{quotation}
661: \section{Heap allocation of procedure call frames}
662: \label{heap}
663:
664: Since heap allocation is so cheap, we put procedure call frames on the
665: heap instead of on the stack\index{stack}.
666: This has many advantages\cite{appel89:cps},
667: but the one of interest here is that it greatly simplifies the runtime
668: system. Many of the facilities described in this paper
669: would be much more complicated to implement if runtime stacks had to be
670: dealt with.
671:
672: Any record on the stack must be initialized as it is created;
673: otherwise it will contain garbage data that could be interpreted
674: by the garbage collector as spurious pointers. However, typical
675: code generators will allocate a call frame on
676: entry to a procedure and spill registers into it as needed.
677: This must be avoided. One way to solve
678: this problem is to delay allocation of the frame; values can be accumulated
679: in registers until spilling is necessary, then all the registers can
680: be spilled at once into a newly-created frame, which is just a record
681: object in runtime data format. Thus, the frame is completely initialized
682: as it is created.
683:
684: The Standard ML of New Jersey compiler doesn't use ``procedure call frames.''
685: Since it uses continuation\index{continuation}-passing
686: style\cite{steele78}\cite{kranz86}\cite{appel89:cps},
687: what an ordinary mortal might call a ``frame'' is really just the
688: closure of a continuation. It is easy to create closures as ordinary
689: records that are completely initialized when they are created.
690: This simplifies both the code generator
691: and the runtime system, though the trick described in the previous paragraph
692: will work for more conventional code generators.
693:
694: Since there's no runtime stack, the
695: {\em call-with-current-continuation}\cite{rees86}
696: \index{call-with-current-continuation}
697: primitive can be implemented very efficiently. In implementations
698: with a runtime stack, the entire stack must be copied when {\em call/cc}
699: is evaluated (or else there must be a lot of extra complexity in stack
700: management); without a stack, the execution of
701: {\em call/cc}, and the execution of
702: saved continuations, take just a few instructions each. This makes
703: {\em call/cc} a practical programming tool, just as fast allocation
704: makes {\em cons} practical.
705:
706: \section{Representing ML structures in records and strings}
707: \label{representing}
708: Section~\ref{data} describes just two kinds of
709: objects---records\index{record} and
710: strings\index{string}---referenceable at their beginning and (in a limited way)
711: at interior points. All of the kinds of ML data can be represented
712: in records and strings.
713:
714: An ML value must be representable in one word. A larger value can be {\em
715: boxed} by putting it in several words on the heap and keeping a (one-word)
716: pointer to it. A small value (like a 31-bit integer)
717: can be kept {\em unboxed\index{unboxed values}} by representing it without indirection in
718: a machine word.
719: Boxed\index{boxed values}
720: values (pointers)
721: are distinguished from unboxed values (integers, or data represented as
722: integers)
723: by their low-order bit.
724:
725: An ML {\bf record\index{record}}
726: is an $n$-tuple of values. It has a natural representation
727: as a record in our runtime data format. ML has a {\it pro forma}
728: record of length 0; as our runtime data format does not allow objects of length
729: 0 (since that would leave no room to put a forwarding pointer, as described in
730: a section~\ref{forwarding}),
731: the empty record
732: is represented as the unboxed integer 0. This does no harm, since
733: no fields can be selected from an empty record anyway.
734:
735: An ML {\bf array\index{array}} is also an $n$-tuple of values.
736: In the ML language,
737: record-field offsets are determined at compile-time, whereas
738: arrays may be indexed by runtime values;
739: and arrays may be modified after
740: they are created, whereas records are immutable.
741: But neither of these
742: differences matters to the runtime system.
743: The polymorphic equality function of ML requires distinguishing between
744: mutable and immutable objects at runtime, so arrays and records
745: have different tags, however; this requires that they have different
746: tags.
747:
748: ML does permit
749: arrays\index{arrays of length 0} of length 0,
750: but our runtime data format does not.
751: Happily, all arrays of length 0 have
752: the same behaviour, so a special object of length 0 (located outside
753: the garbage-collectible region) serves to represent all the
754: empty arrays.
755:
756: {\bf References} in ML are mutable objects:
757: \verb"val a = ref 5" declares a reference\index{reference variables}
758: variable \verb"a" that may be
759: changed by a later assignment statement, unlike most variables which cannot
760: be modified once defined. Reference variables behave just like single-element
761: arrays, and that's how they are represented in the runtime system.
762:
763: ML has {\bf datatype\index{datatype}}
764: declarations to allow tagged variant types. For example,
765: the declaration
766: \begin{verbatim}
767: datatype t = NAME of string | NUMBER of int
768: \end{verbatim}
769: specifies a type \verb"t" that can be either a string or an integer,
770: depending on whether the constructor\index{constructor} \verb"NAME"
771: or \verb"NUMBER" is used to create it.
772: The program can examine any object of type \verb"t" and determine whether
773: it has the \verb"NAME" or \verb"NUMBER" representation---that is, it
774: is a {\em tagged} union. An object of type \verb"t" is represented
775: as a two-element record: one field contains the tag (a small integer),
776: and the other field contains the value.
777: The details of constructor representation may be of interest
778: only to those knowledgeable in ML, and are described in
779: section~\ref{constructor}.
780:
781: ML has {\bf strings\index{string}}
782: of characters. Strings can be of any non-negative length.
783: Since our runtime representation cannot support objects of length 0
784: (because one word is needed to store the forwarding pointer, as described
785: in a section~\ref{forwarding}),
786: the empty string\index{empty string}\index{null string}
787: \index{string of length 0}
788: must be treated specially. However, it turns out that
789: it is never necessary to create a new empty string; the only occurrences
790: of empty strings are as literals in the program text. String
791: literals (and back-pointers) will be discussed in section~\ref{function}.
792:
793: Strings\index{Strings of length one} of length one are treated specially by the compiler,
794: though this is not necessary either for the ML language or for our runtime
795: data format. Single-character strings\index{single-character strings}
796: \index{characters}
797: are treated as unboxed integers
798: between 0 and 255, to avoid heap-allocation for this (frequent) special case.
799: Though this technique may cause
800: less allocation, it requires special tests on every
801: string operation. It's not clear whether this special case saves more than
802: it costs. However, this special case is transparent to the runtime system
803: anyway; all conversions, etc. are handled explicitly by the compiler;
804: the single-character strings are not a new runtime data format, but
805: look like ordinary unboxed integers.
806:
807: {\bf Byte-arrays\index{byte-arrays}}
808: in ML are to strings as arrays are to records: they have the
809: same representation as strings, but their tag is different to facilitate
810: certain language features.
811:
812: {\bf Floating-point\index{floating-point}} numbers are too large to fit in
813: one word. Even if we chose
814: to use single-precision floating point, it would be difficult to store
815: them unboxed\index{unboxed}
816: because there is no bit available for use as a tag\index{tag} bit.
817: Thus, all floating-point numbers are stored boxed, with 8 bytes of data and
818: one word of descriptor.
819: The descriptor\index{descriptor}
820: must be one that indicates that the contents of the
821: object contain no pointers.
822: Since ML is statically typed, the language
823: never needs to distinguish (at runtime) floating-point numbers from
824: strings, so we can just represent a double-precision float as an 8-byte
825: string. This is not an ASCII string, it is the hardware representation;
826: a ``string'' descriptor does not denote that the contents are printable
827: characters, just that there is an arbitrary bit-pattern not containing
828: pointers.
829:
830: Similarly, {\bf machine-code procedures}
831: \index{machine code} do not require a separate class
832: of descriptor. From the garbage collector's point of view, machine
833: code is just like strings: it contains bits that are to be (perhaps)
834: moved from place to place but which never represent pointers.
835: Thus, machine code is just kept in string objects. The mechanism by
836: which we avoid placing pointers\index{pointers}
837: (or any reference to other objects)
838: in machine code will be described in section~\ref{modules}.
839:
840: \section{Closures}
841: \label{closures}
842: \index{closure}
843: In ML, as in many lexically scoped languages, functions may have free
844: variables. That is, the body of a function may reference not only its
845: own formal parameters\index{formal parameters}
846: (the bound variables of the function), but the
847: formal parameters of a statically enclosing function. Consider the
848: function
849: \begin{verbatim}
850: fun add(x) = let fun add1(y) = x+y
851: in add1
852: end
853: \end{verbatim}
854: The function \verb"add(x)" defines an internal function \verb"add1(y)" that
855: adds \verb"x" and \verb"y", and then \verb"add" returns \verb"add1" as its
856: result. The variable \verb"x" is bound by \verb"add", and
857: \verb"y" is bound by \verb"add1". Therefore, if we just consider the
858: function definition \verb"fun add1(y) = x+y", the variable \verb"x"
859: is a free variable\index{free variable} of this internal function.
860:
861: In order to evaluate \verb"add1" applied to some argument, we must have
862: a context in which the value \verb"x" is defined. It will not suffice
863: for the \verb"add" function just to return a pointer to the machine code
864: of \verb"add1" as its result. Instead, it must return a {\em closure}:
865: a combination of a code-pointer an some information about the values of
866: all the free variables (in this case, just \verb"x").
867:
868: For example, the result of evaluating \verb"add(5)" is (abstractly) the
869: function which will always add 5 to its argument.
870: Figure~\ref{add5} shows a possible representation
871: as a record object, with a descriptor at the beginning for the
872: garbage collector.
873: \begin{figure}[htbp]
874: \label{add5}
875: \begin{verbatim}
876: +------+
877: | desc |
878: +------+
879: p--> | o------------> machine code for add1
880: +------+
881: | 5 |
882: +------+
883: \end{verbatim}
884: \caption{A simple closure.}
885: \end{figure}
886: The pointer \verb"p" is the runtime representation of the particular version
887: of \verb"add1" in which \verb|x| is bound to 5. This pointer may be passed
888: as an argument to some other function that doesn't know anything about
889: the \verb"add1" function. All the other function has to know is how
890: to ``call'' a closure. The calling sequence might be:
891: \begin{enumerate}
892: \item Put \verb|p| in register 0.
893: \item Put the return address in register 1.
894: \item Fetch p[0] into register 2.
895: \item Jump to the address contained in register 2.
896: \end{enumerate}
897: Step 1 is necessary so that when \verb"add1" is entered, it can gain
898: access to the closure record where the binding of \verb"x" is stored.
899: Step 2 is just the normal saving of a return address, which might
900: in many cases be on a stack instead of in a register. Steps 3 and
901: 4 are just the typical code necessary to jump to a runtime-bound address.
902:
903: It is important to note that the function that calls a closure \verb"p"
904: doesn't need to access any part of it except the machine-code pointer
905: in \verb|p[0]|. This means that the free variables (the rest of the
906: closure) may have an arbitrary arrangement, known only to the
907: function that builds the closure (\verb"add", in this case) and the
908: function that executes it (\verb"add1", in this case). Closures can
909: be structured in many ways\cite{appel88:clo}, and can even point
910: to other closures for access to free variables (i.e., they can
911: have ``static links\index{static link},'' in Algol terminology).
912:
913: Clearly, closures are represented a lot like records. A closure has several
914: fields, each of which is either a machine-code pointer or a free variable.
915: The machine-code pointer is just a (boxed) string pointer,
916: and the free variables are
917: just one-word ML objects. Therefore, we use record\index{record}
918: objects to represent closures.
919:
920: When several functions share a set of free variables, it is convenient
921: to have a {\bf multiple-function closure.}
922: \index{closure for multiple functions}
923: \index{multiple functions closure}
924: \index{shared closure}
925: Consider the functions
926: \begin{verbatim}
927: fun test(y,z) =
928: let fun even(i) = if i=0 then y else odd(i-1)
929: and odd(i) = if i=0 then z else even(i-1)
930: in (even,odd)
931: end
932: \end{verbatim}
933: This function, when applied to arguments \verb"(3,7)", would return
934: two functions (let's call them \verb"even37" and \verb"odd37").
935: from integer to integer. \verb"Even37" applied to even integers
936: returns 3 and applied to odd integers returns 7, and \verb"odd37"
937: works the other way around.
938:
939: We could represent these functions by two different closures, as shown
940: in figure~\ref{twoclos}.
941: \begin{figure}[htbp]
942: \label{twoclos}
943: \begin{verbatim}
944:
945: +------+
946: | desc |
947: +------+
948: even37 --> | o------------> machine code for even
949: +------+
950: y | 3 |
951: +------+
952: odd | o-------> odd37
953: +------+
954:
955: +------+
956: | desc |
957: +------+
958: odd37 --> | o------------> machine code for odd
959: +------+
960: z | 7 |
961: +------+
962: even | o--------> even37
963: +------+
964: \end{verbatim}
965: \caption{Two mutually recursive closures}
966: \end{figure}
967: This is particularly unfortunate because \verb"even" and \verb"odd"
968: are free variables\index{free variables}
969: of each other, and this requires the construction
970: of a cyclic data structure of closures, which can get complicated.
971:
972: A more clever trick\cite{appel87:sml}\cite{kranz86} is to let these
973: two functions share a closure, as shown in figure~\ref{oneclos}.
974: \begin{figure}[htbp]
975: \label{oneclos}
976: \begin{verbatim}
977: +------+
978: | desc |
979: +------+
980: even37 --> | o------------> machine code for even
981: +------+
982: odd37 --> | o------------> machine code for odd
983: +------+
984: y | 3 |
985: +------+
986: z | 7 |
987: +------+
988: \end{verbatim}
989: \caption{Two functions sharing a closure}
990: \end{figure}
991: Now, when \verb"even37" is called, its closure-pointer will be loaded
992: in register 0, and it knows that it can access \verb:y: at offset 2 from
993: register 0. And when \verb"odd37" is called, its closure pointer
994: (which is really a pointer to the second field of the record) will be
995: loaded in register 0, and it can access \verb"z" at offset 2.
996: In some situations, the same free variable may be accessed by different
997: functions in the closure, and the code generator will have to remember
998: that the offsets\index{offset} from register 0 to a particular field
999: depend on which closure-pointer is loaded (i.e. which function we are
1000: generating code for).
1001:
1002: Finally, if \verb"even" wants to call \verb"odd", it can just generate
1003: the appropriate closure value in register 0 by adding an offset of 1
1004: to its own closure pointer. In general, all mutually recursive
1005: functions can be handled this way, and cyclic\index{cyclic closure}
1006: closure structures
1007: are never required. But even non-mutually-recursive sets of functions
1008: can save storage by sharing closures.
1009:
1010: It should now be clear why (in section~\ref{data}) we arranged for
1011: pointers into the middle of record objects. Given the pointer
1012: \verb"odd37", the garbage collector can easily search backward until
1013: it finds the descriptor\index{descriptor}
1014: of the record; the descriptor is unboxed,
1015: while all of the previous machine-code pointers are boxed fields.
1016:
1017: \section{Function entry points}
1018: \label{function}
1019:
1020: A typical compilation\index{compilation unit} unit
1021: will contain many functions, and it would be
1022: unwieldy to make a different string object for each function:
1023: since the functions in a compilation unit often call each other,
1024: these calls will go much faster as pc-relative jumps than if
1025: we had to fetch addresses from closures. But to achieve pc-relative
1026: jumps, the relative distance between two functions cannot change;
1027: and the garbage collector moves objects around.
1028: So to achieve
1029: this constant distance, we must put several functions in the
1030: same string object, and have several
1031: entry points.
1032:
1033: For example, the \verb"even", \verb"odd", and \verb"test"
1034: functions of section~\ref{closures} could all be placed a single string,
1035: \index{embedded string}
1036: with appropriate back-pointer descriptors (figure~\ref{embedded1}).
1037: \begin{figure}[htbp]
1038: \label{embedded1}
1039: \begin{verbatim}
1040: +------+
1041: | desc |
1042: +------+
1043: test --> | t |
1044: + e +
1045: | s |
1046: + t +
1047: | |
1048: +------+
1049: | [5] |
1050: +------+
1051: even --> | e |
1052: + v +
1053: | e |
1054: + n +
1055: | |
1056: +------+
1057: | [10] |
1058: +------+
1059: odd --> | o |
1060: + d +
1061: | d |
1062: +------+
1063: \end{verbatim}
1064: \caption{Three code strings embedded in a string}
1065: \end{figure}
1066: The numbers \verb"[5]" and \verb"[10]" are back-pointers, formatted
1067: as described in section~\ref{data}. They tell the garbage collector
1068: the offset to the beginning of the object, so it can find the true descriptor.
1069:
1070: The advantage to putting several functions in the same string is that
1071: they can refer to each other directly, without having to access each
1072: other through closures. Of course, it will be necessary to adjust
1073: the closure\index{closure}
1074: pointer in register 0. Here, \verb"even" could call \verb"odd"
1075: by this (simpler) calling sequence:
1076: \begin{enumerate}
1077: \item Add 1 to register 0 (to adjust p).
1078: \item Put the return address in register 1.
1079: \item Jump to \verb"odd".
1080: \end{enumerate}
1081:
1082: The garbage collector may move a code string from one place to another
1083: in memory, so it is necessary that the jump in step 3 be a
1084: pc\index{pc}-relative
1085: jump.
1086:
1087: ML programs may contain literal\index{literal}
1088: \index{string literal}
1089: strings and floating\index{floating point constant} point constants.
1090: These are embedded within string objects amongst the machine-code
1091: functions. For example,
1092: \begin{verbatim}
1093: fun show(b) = if b then "true" else "false"
1094: \end{verbatim}
1095: could almost have the representation shown in figure~\ref{embedded2}.
1096: \begin{figure}[htbp]
1097: \label{embedded2}.
1098: \begin{verbatim}
1099: +------+
1100: | desc |
1101: +------+
1102: show --> | s |
1103: + h +
1104: | o |
1105: + w +
1106: | |
1107: +------+
1108: | [5] |
1109: +------+
1110: true --> | true |
1111: +------+
1112: | [7] |
1113: +------+
1114: false --> | fals |
1115: + +
1116: | e000 |
1117: +------+
1118: \end{verbatim}
1119: \caption{String literals, oversimplified}
1120: \end{figure}
1121: The function \verb"show" returns a pointer to \verb"true" or \verb"false";
1122: this pointer points into the middle of the large string object at one
1123: of the embedded strings. Because the embedded string is preceded by a
1124: back-pointer descriptor, the garbage collector won't be confused.
1125:
1126: There's a slight problem with this. Although the garbage collector doesn't
1127: need to know the length of the string \verb|"true"|, the ML program might
1128: apply the \verb"length" function to it.
1129: String\index{string length} lengths are kept in the
1130: descriptor word, and are accessed by fetching field $-1$ and shifting
1131: off the tag bits. The problem here is that the descriptor for \verb"true"
1132: is a back-pointer\index{back-pointer},
1133: not a string descriptor. The solution---simple and
1134: inelegant---is to introduce a new kind of descriptor, an {\em embedded
1135: string}, which contains the length of the string and always is preceded
1136: by a backpointer. Thus, the actual representation of the \verb"show"
1137: function is more like figure~\ref{embedded3}.
1138: \begin{figure}[htbp]
1139: \label{embedded3}
1140: \begin{verbatim}
1141: +------+
1142: | desc |
1143: +------+
1144: show --> | s |
1145: + h +
1146: | o |
1147: + w +
1148: | |
1149: +------+
1150: | [6] |
1151: +------+
1152: | 4emb |
1153: +------+
1154: true --> | true |
1155: +------+
1156: | [9] |
1157: +------+
1158: | 5emb |
1159: +------+
1160: false --> | fals |
1161: + +
1162: | e000 |
1163: +------+
1164: \end{verbatim}
1165: \caption{String literals embedded in a code string}
1166: \end{figure}
1167:
1168: The treatment of embedded \index{floating point constant}
1169: floating point constants is just like that of
1170: embedded strings. However, the ML program will never need to take the
1171: length of a floating point constant, so the embedded-string descriptor
1172: can be omitted and a simple backpointer\index{backpointer} will suffice.
1173: Note that embedded strings of length 0 are permitted, since there
1174: is no need for a word to install a forwarding pointer (see
1175: section~\ref{forwarding},
1176: and note that forwarding pointers go only at the beginning of the
1177: entire string object, not at embedded strings).
1178:
1179: The address of string and floating constants may appear in machine code,
1180: but only in a pc\index{pc}-relative way, since code objects may be moved in memory
1181: by the garbage collector\index{garbage collector}.
1182:
1183: \section{Modules and compilation units}
1184: \label{modules}
1185:
1186: Standard ML has a powerful module\index{module}
1187: system, allowing nested modules,
1188: modules as parameters to other modules, thinning of a richer module
1189: to form a smaller module, etc. The module system can be represented
1190: entirely as records and functions in the runtime system\cite{appel87:sml};
1191: no new machinery is needed.
1192:
1193: A compilation unit\index{compilation unit}
1194: is just a sequence of function and value declarations that
1195: will be compiled together into one string object. But one compilation
1196: unit may refer to values defined in another, and a linkage\index{linkage}
1197: mechanism is required.
1198:
1199: We can use the power of higher-order functions to implement the linkage
1200: in a way that is transparent to the runtime system. If unit \verb"B"
1201: refers to a value in unit \verb"A", then the compiler will treat
1202: \verb"A" as an implicit parameter of \verb"B". For example, suppose we have
1203: two compilation units
1204: \begin{verbatim}
1205: fun f(x,y) = x+y
1206: \end{verbatim}
1207: and
1208: \begin{verbatim}
1209: fun g(z) = f(z,z)
1210: \end{verbatim}
1211: clearly \verb"f" is a free variable\index{free variable}
1212: of \verb"g". But the compiler can
1213: parametrize the second unit, as if it were written
1214: \begin{verbatim}
1215: fun g0(f) = let fun g(z) = f(z,z)
1216: in g
1217: end
1218: \end{verbatim}
1219: This compilation unit has no free variables; the ML system will simply
1220: apply the second unit to the first one, yielding the desired function
1221: \verb"g". The compiler must keep track of inter-module references
1222: in order to do this, but at least the runtime mechanism for linkage is simple.
1223:
1224: So, each compilation unit is a closed function with no free variables.
1225: No special linkage mechanism is built into the runtime system; the
1226: closure\index{closure}
1227: mechanism handles linkage very elegantly.
1228:
1229: Eliminating free variables from compilation units also simplifies the
1230: code generator\index{code generator}.
1231: Whenever the code generator must analyze local free variables,
1232: generate pc\index{pc}-relative references, etc.,
1233: its job is much simpler because there
1234: are no global references to other objects. The interface between the
1235: front end of the compiler and the code generator are much cleaner as a result.
1236:
1237: \section{Linkage to assembly language}
1238: \label{linkage}
1239:
1240: Some primitives of a programming language are best implemented in a different
1241: language (typically assembly language\index{assembly language}).
1242: Standard ML of New Jersey
1243: makes use of 8 functions written in assembly language, and 8 functions written
1244: in C\index{C}.
1245: (For comparison, more than 100 standard-library\index{standard library}
1246: functions are written
1247: in ML.) The assembly-language functions are:
1248: \begin{enumerate}
1249: \item {\bf array\index{array}(n,x)} creates an array of length $n$, each element initialized
1250: to $x$.
1251: \item {\bf callc\index{callc}(f,a)} calls a C-language function $f$ with argument $a$.
1252: \item {\bf create\_b(n)} creates\index{create\_b} a byte-array of length $n$.
1253: \item {\bf create\_s(n)} creates\index{create\_s} a string of length $n$.
1254: \item {\bf floor\index{floor}(x)} returns the smallest integer less than
1255: or equal to $x$.
1256: \item {\bf logb\index{logb}(x)} returns the exponent part of (the floating-point) $x$.
1257: \item {\bf scalb\index{scalb}(x)} inserts a new exponent into (floating-point) $x$.
1258: \item {\bf syscall\index{syscall}(i,args,k)} does operating system
1259: \index{operating system} kernel-call $i$ with
1260: $k$ arguments.
1261: \end{enumerate}
1262: The assembly-language functions are located at (constant) addresses within
1263: the runtime system. But it's a good idea to follow the rules about
1264: free variables\index{free variables}
1265: in module-linkages\index{linkage}: even the references to assembly-language
1266: primitives should not be ``hard-wired'' addresses in code objects.
1267: If this were done, then all ML code would have to be re-compiled whenever
1268: the runtime system was re-compiled.
1269:
1270: Instead, we just treat the assembly-language functions as a special
1271: record object containing nine elements. Other modules are parametrized
1272: by this \verb"Assembly" module just as if it were an ordinary one.
1273: All the assembly-language functions follow the ML calling conventions.
1274:
1275: Most of the C functions are to provide access to system calls with
1276: hard-to-manage interfaces, like \verb"fork", etc.
1277: There is an added complication that the C and ML calling conventions
1278: don't match.
1279: The assembly-language function \verb"callc" arranges the arguments
1280: for an ML function to call a C function. The details are uninteresting,
1281: but the point is that absolute references are again avoided.
1282:
1283: \begin{quotation}
1284: {\small The file \verb"boot/assembly.sig" contains the signature
1285: \verb"Assembly", approximately as in figure~\ref{assembly}.
1286: \begin{figure}
1287: \label{assembly}
1288: \begin{verbatim}
1289: signature ASSEMBLY =
1290: sig
1291: datatype datalist = DATANIL | DATACONS of (string * string * datalist)
1292: type func
1293: datatype funclist = FUNC of (func * string * funclist)
1294: type object
1295: structure A : sig
1296: val array : int * 'a -> 'a array
1297: val callc : 'b (* func*) * 'a -> 'c
1298: val create_b : int -> string
1299: val create_s : int -> string
1300: val floor : real -> int
1301: val logb : real -> int
1302: val scalb : real * int -> real
1303: val syscall : int * string list * int -> int
1304: end
1305: exception Div
1306: exception Float of string
1307: exception Interrupt
1308: exception Overflow
1309: exception SystemCall of string
1310: exception UnboundTable
1311: val array0 : 'a array
1312: val bytearray0 : string
1313: val collected : int ref
1314: val collectedfrom : int ref
1315: val current : string ref
1316: val datalist : datalist
1317: val external : funclist
1318: val gcmessages : int ref
1319: val gcprof : string ref
1320: val majorcollections : int ref
1321: val minorcollections : int ref
1322: val opsys : int (* 1 = vax bsd ultrix, 4.2, 4.3
1323: 2 = sunos 3.0, 4.0
1324: 3 = vax v9 (bell labs) *)
1325: val pstruct : object ref
1326: val ratio : int ref
1327: end
1328: \end{verbatim}
1329: \caption{The {\tt ASSEMBLY} signature}
1330: \end{figure}
1331: \index{Assembly structure}
1332: The substructure \verb"A" is the machine-dependent part (implemented
1333: in assembly language), and the other components (exceptions, constants,
1334: etc.) are just data structures that can be described machine-independently
1335: in C.
1336: \verb"A" is arranged as an ML record
1337: at the label \verb"runvec"\index{runvec}
1338: in the file \verb"VAX.prim.s", \verb"M68.prim.s",
1339: etc. The machine-independent part
1340: is in \verb"cstruct.c"\index{cstruct.c}.
1341:
1342: The exceptions in this structure are just those that can be raised
1343: from C or assembly language. Exceptions as elaborated by the compiler
1344: look like references to strings, and in \verb"cstruct.c" are implemented
1345: as initialized structures to mimic this
1346: with all the appropriate descriptors.
1347:
1348: The values \verb"array0" and \verb"bytearray0" are just the array and
1349: \index{array0}\index{array of length 0}
1350: \index{bytearray0}
1351: byte-array of length 0; this is necessary because objects of length 0
1352: are not permitted in the garbage-collectible region.
1353:
1354: \index{collected}\index{collectedfrom}
1355: \index{majorcollections}\index{minorcollections}\index{ratio}
1356: The references \verb"collected", \verb"collectedfrom",
1357: \verb"majorcollections", and \verb"minorcollections" are updated by
1358: the garbage collector with performance information. The \verb"ratio"
1359: variable can be set from ML to tell the garbage collector what
1360: ratio to maintain between heap size and amount of live data.
1361:
1362: \index{current}\index{profiling}
1363: The variable \verb"current" is used in execution profiling\cite{appel88:prof};
1364: it is a pointer
1365: to an array of length 2 of ML integers. When profiling is enabled,
1366: a timer interrupt will periodically
1367: cause current[1] to be incremented.
1368:
1369: \index{pstruct}
1370: \index{loader}
1371: \index{Initial}
1372: The \verb"pstruct" is a pointer to the \verb"Initial" (pervasive)
1373: structure. The ML loader (\verb"boot/loader.sml") needs this
1374: because other modules may reference the structure \verb"Initial".
1375:
1376: \index{datalist}
1377: The \verb"datalist" is used for linkage to sharable compiled ML code.
1378: In vanilla Unix, such code must be link-loaded into the text segment
1379: of the sml executable file, and the \verb"datalist" provides the ML
1380: loader a way to get to it. Each element of the data list contains
1381: two strings (the name of the module, and the executable code), along
1382: with a link to the next element.
1383:
1384: \index{funclist}
1385: The \verb"funclist" is similarly used for linkage to functions implemented
1386: in C. These functions could be described in the Assembly signature
1387: but this requires recompilation whenever a new function is added.
1388: The funclist is terminated by a function whose name is "xxxx". All functions
1389: in the list must have a name of exactly 4 characters.
1390: All C-functions must take exactly one argument in ML format and return
1391: a result in ML format. The functions implemented in C at this writing are:
1392: \begin{itemize}
1393: \item{\bf fion\index{fion}} tells how many characters may be read from an open
1394: file-descriptor without blocking.
1395: \item{\bf fork\index{fork}} does a Unix process fork.
1396: \item{\bf prof\index{prof}} is obsolete.
1397: \item{\bf syst\index{syst}} executes a shell command as a sub-process.
1398: \item{\bf time\index{time}} gets execution-time information from the operating system
1399: and the garbage collector.
1400: \item{\bf argv\index{argv}} gets the command-line arguments of the executing program
1401: (as a list of strings).
1402: \item{\bf envi\index{envi}} gets the Unix environment\index{environment}
1403: string (as a list of strings).
1404: \item{\bf blas\index{blas}} does a structured\index{structured write} write (as described section~\ref{structured}).
1405: \item{\bf salb\index{salb}} does a structured read.
1406: \end{itemize}
1407:
1408: These functions should be careful not to allocate memory using \verb"malloc".
1409: \index{malloc}
1410:
1411: All of these functions are called from the ML ``thread'' (see
1412: section~\ref{fast}).
1413: Some C functions may require the (temporary) suspension of the ML thread,
1414: e.g. to do a garbage collection for a structured write.
1415: By setting the global variable \verb"cause"\index{cause} to a nonzero
1416: value and then returning, a function may cause control to be grabbed
1417: immediately thereafter in the thread\index{thread} controller.
1418: }
1419: \end{quotation}
1420:
1421: \section{Access to operating system services}
1422: \label{access}
1423:
1424: A typical operating system\index{operating system}
1425: provides many services, each with one or
1426: more operations (``system calls''). A very early version of Standard ML of
1427: New Jersey made little use of these services, so it sufficed to write
1428: an assembly-language interface to each desired system call, and then
1429: call the assembly-language functions from ML programs. As the ML environment
1430: grew more sophisticated, it needed more operating system services, so the
1431: number of assembly-language interface functions grew. This eventually
1432: became intolerable.
1433:
1434: Now there is just one assembly-language interface function, \verb"syscall",
1435: \index{syscall}
1436: that takes a list of arguments and a system-call number. This function
1437: pushes the arguments onto the stack and makes the system call. The ML standard
1438: library hides the \verb"syscall" function behind a variety of typechecked
1439: functions. Implementing these functions in ML rather than assembly language
1440: is better for two reasons: ML is safer and easier to program in, and (more
1441: important) the ML code doesn't need to be rewritten for each target
1442: architecture.
1443:
1444: \begin{quotation}
1445: {\small All Unix system calls return integer values. These are
1446: converted into ML integers (by shifting and incrementing) and returned
1447: as the result of \verb"syscall". Many system calls take parameters
1448: by reference that they stuff results into. These results are (of course)
1449: not appropriately tagged for ML. A byte-array (of the
1450: appropriate length) is used
1451: as the actual parameter for such an argument, and then
1452: the results can be extracted from the byte-array after the system call.
1453:
1454: Integer arguments to system calls are shifted right by \verb"syscall"
1455: to convert them into their (untagged) representation.
1456:
1457: String and byte-array arguments are left alone, yielding their natural
1458: representation. However, strings\index{string}
1459: in C (and Unix) are terminated
1460: by a null character, whereas strings in ML have a length prefix.
1461: The prefix is ignored by the kernel, since it occurs at offset -4 (bytes).
1462: To achieve null termination of strings, you may take the actual ML argument
1463: and concatenate the string \verb|"\000\000"| of two zero characters (two
1464: characters are required because of the unboxed representation of
1465: single-character strings, and the possibility that the actual argument
1466: is an empty string).
1467: }
1468: \end{quotation}
1469: \section{Constructor representations}
1470: \label{constructor}
1471: Those unfamiliar with ML might wish to skip this section.
1472:
1473: Some of the constructors\index{constructor}
1474: in an ML datatype\index{datatype} may not carry values.
1475: For example, in the type
1476: \begin{verbatim}
1477: datatype 'a option = NONE | SOME of 'a
1478: \end{verbatim}
1479: the \verb"SOME" constructor carries value of type \verb"'a"
1480: and the
1481: \verb"NONE" constructor carries no value. Constructors that carry no value
1482: are represented not as two-element records, but as (unboxed) small integers.
1483: In this case, \verb"NONE"
1484: is represented by the integer 0 (with a low-order 1 tag bit),
1485: and \verb"SOME(x)" is represented by a two-element record containing the value
1486: \verb"x" and a small integer representing the \verb"SOME" constructor.
1487: The ML program can distinguish which constructor has been used by
1488: testing for ``boxity:''\index{boxity}
1489: \verb"NONE" is an unboxed value\index{unboxed value}, \verb"SOME(x)"
1490: is a boxed value\index{boxed value},
1491: and the low-order bit will distinguish them.
1492:
1493: Finally, in the case that there is only one value-carrying constructor,
1494: and the value carried always has a boxed representation, the extra
1495: indirection record can be eliminated. Thus, for the {\bf list} datatype
1496: \begin{verbatim}
1497: datatype 'a list = NIL | CONS of ('a * 'a list)
1498: \end{verbatim}
1499: the constructor \verb"NIL" can be represented as the unboxed integer 0, the
1500: constructor \verb"CONS(a,b)" can be represented as a two-element record
1501: containing \verb"a" and \verb"b". Again, the low-order ``boxity'' bit
1502: distinguishes the constructors. If there had been several value-carrying
1503: constructors, then the boxity bit alone could not distinguish them,
1504: and an indirection record (containing the carried value and a small
1505: integer denoting the constructor) would be required.
1506:
1507: It is tempting to play more elaborate tricks with the representation of
1508: constructors. For example, the {\em option} datatype described above
1509: might not seem to need an extra indirection; surely the boxity bit
1510: should be enough to distinguish between \verb"NONE" and \verb"SOME(x)"?
1511: The problem is that the value \verb"x" might itself be either boxed or
1512: unboxed; the indirection guarantees that \verb"SOME(x)" will indeed be boxed.
1513:
1514: Similarly, it is tempting to use a clever representation for the datatype
1515: \begin{verbatim}
1516: type t = a * b
1517: datatype atom = NUMBER of int | RECORD of t
1518: \end{verbatim}
1519: Here, the values carried by the NUMBER constructor are always unboxed, and
1520: the values carried by the RECORD constructor are always boxed; the
1521: boxity can serve to distinguish them.
1522:
1523: The problem with these schemes is caused by the abstraction provided by
1524: ML {\em functors\index{functor}}:
1525: a functor might take the atom datatype as a parameter
1526: with some of its structure hidden:
1527: \begin{verbatim}
1528: functor F(sig type t
1529: datatype atom = NUMBER of int | RECORD of t
1530: end)
1531: \end{verbatim}
1532: and here it is not at all clear that \verb"t" is always boxed.
1533: (Unfortunately, this problem applies to the ``clever'' representation of the {\em list}
1534: datatype as well, but we have chosen to ignore it there---we can
1535: detect the (rare) problems with partially-abstracted lists
1536: as functor parameters and give error messages, but we didn't want
1537: to use an extra indirection in the representation of lists.)
1538: The problem of functor/datatype interaction
1539: could be considered a defect in the language design.
1540:
1541: \begin{quotation}
1542: {\small Note that the constructor tag is element 1 of the record and
1543: the value is element 0. There's no particular reason for this; it's
1544: probably a bad idea. For exception constructors, the constructor
1545: tag is not a small integer, it is a \verb"string ref". A ref cell is
1546: used instead of just a string so that (generative)
1547: exceptions may be compared
1548: for equality in pattern-matching exception\index{exception} constructors.
1549: }
1550: \end{quotation}
1551: \section{Suspending a process}
1552: \label{suspending}
1553: \index{exportML}
1554: Having designed a simple layout of runtime objects, we can now implement
1555: easily a variety of runtime services.
1556:
1557: A convenient feature of a programming environment is the ability to save
1558: the current state of the computation in a file, so that by executing
1559: that file on a later date the computation can be resumed. In an interactive
1560: system, one might wish to compile and load some programs, and then
1561: ``save the world'' so that in the next session these programs don't
1562: have to be re-loaded. This feature could also be useful for program
1563: checkpoints.
1564:
1565: It's not too hard to suspend a process in this way. It's even possible
1566: to make the resulting
1567: file an ordinary executable file. An executable file
1568: contains a header, a text segment, and a data segment. The (read-only)
1569: text segment
1570: of the saved file will be identical to the text segment of the currently
1571: executing process, so a single \verb"write" system call will serve to
1572: write it to the file. The data segment of the file will consist of the
1573: original data segment of the process plus any newly allocated heap memory;
1574: again, one or two \verb"write"s will put it neatly into the file.
1575: (It is useful to do a garbage collection immediately before saving,
1576: to minimize the size of the file.)
1577: Finally, the header can be synthesized appropriately.
1578:
1579: An early version of Standard ML of New Jersey used a runtime
1580: stack\index{stack}, and
1581: we had no end of trouble getting the stack saved correctly. A Unix executable
1582: file doesn't have a stack segment, so the stack had to be copied into the
1583: heap before saving. And after restoring and copying back to the stack
1584: segment, we found that we had creamed the (new process's) command-line
1585: arguments, etc. When we eliminated the runtime stack, these annoyances
1586: ceased.
1587:
1588: \begin{quotation}
1589: {\small
1590: \index{magic number}
1591: The resulting executable file has a ZMAGIC magic number on
1592: Berkeley Unix, and NMAGIC on SunOs 4.0. This is because ZMAGIC
1593: implies dynamic loading of shared libraries on SunOs 4.0, which complicates
1594: the address map. Creating executable files is annoyingly difficult
1595: in operating systems like SunOs and Mach, whose notion of a process
1596: address map is not as simple as in Berkeley Unix.
1597: }
1598: \end{quotation}
1599: \section{Structured writes and reads}
1600: \label{structured}
1601:
1602: \index{structured write}
1603: It's often necessary to take a data structure (with many records, pointers,
1604: strings, etc.) and write it to a file in binary form so it can be read
1605: back in quickly. It's always possible to do this in an {\em ad hoc} way
1606: for each different kind of data structure that has to be written, but
1607: it's sometimes difficult to get the pointer-sharing relations right.
1608: Since the runtime data format has enough information for the garbage-collector
1609: to traverse the structure, then a writer/reader must be able to traverse
1610: it as well.
1611:
1612: In fact, we can view the saving of such a structure
1613: as just a garbage collection.
1614: The argument to the \verb"structured-write" function is just a root pointer,
1615: and \verb"structured-write" must traverse all the data accessible from this
1616: root. In doing so, it must copy the data to a file, being careful
1617: to make only one copy of each record.
1618:
1619: \index{garbage collection}
1620: We can, in fact, just invoke the \verb"gc" procedure, giving as the
1621: \verb"roots" argument just a singleton vector---the pointer that
1622: was handed to \verb"structured-write". Then, the resulting {\em tospace}
1623: will be exactly the desired contents of the file, which can be written
1624: out in a single operation.
1625:
1626: At this point, however, memory is in a bit of a mess; some objects have
1627: been forwarded and others have not. One solution is just to finish the
1628: garbage collection: each of the ``normal'' roots of the data is
1629: forwarded, and then (again) all the remaining unforwarded pointers in
1630: {\em tospace} are forwarded. Then memory is again consistent, and execution
1631: may continue.
1632:
1633: This is unattractive because the time required to do a structured write
1634: is now proportional to the amount of all live data, not proportional
1635: to the amount written. So a different solution is better: keep
1636: a separate list of
1637: repair\index{repair}
1638: information about the {\em fromspace} objects that were overwritten with
1639: forwarding pointers. Whenever a {\em fromspace} object is forwarded,
1640: two words of information must be kept about it: the location of the
1641: object itself, and
1642: the previous value
1643: of its first word (that was overwritten). Then, repair is easy;
1644: the list of repair information can be traversed, and each {\em fromspace}
1645: object is restored to its original state.
1646: The descriptor can be recovered by copying the descriptor of the
1647: {\em tospace} copy (accessed via the forwarding pointer), and the first
1648: word (which had been overwritten by the forwarding pointer) can then
1649: be recovered from the repair information.
1650: Saving the repair information is fast, and performing the repairs is also
1651: fast. The time to do a structured write is now proportional (with a small
1652: constant of proportionality!) to the amount written.
1653:
1654: There's one last problem. Where do we keep the repair information, and
1655: what if it grows too large? The repair information can be kept at the
1656: far end of {\em tospace}. Then, as long as the amount written is fairly small,
1657: we'll never run into it. And if we do run into it, that means that
1658: the amount written must be at least half the size of {\em tospace} (where {\em tospace}
1659: is always at least the size of the total accessible data). What we can do
1660: in this case is just to toss away the repair information, and go ahead
1661: with a garbage collection!
1662:
1663: \begin{quotation}
1664: {\small In a multi-generation system (as in SML-NJ's runtime system),
1665: we do a (cheap) minor collection before the structured write; the collection
1666: referred to in the paragraphs above is a major collection.
1667: }
1668: \end{quotation}
1669: \section{Buffered input/output}
1670: \label{buffered}
1671:
1672: Some operating systems (like Unix) don't provide buffered\index{buffered I/O}
1673: input and output
1674: as a primitive, and even in operating systems that do, the overhead
1675: of one system call per character may be too high. What the runtime
1676: system can do is provide this service for user programs.
1677:
1678: The Unix/C\index{C} standard library\cite{kernighan78} demonstrates that
1679: \index{standard library}
1680: the runtime system need not provide this service; instead, library
1681: routines can implement buffered I/O. We have taken the same approach
1682: in our system; the buffered I/O functions are implemented in ML as library
1683: functions, and the runtime system is completely ignorant of buffered I/O.
1684:
1685:
1686: \section{Execution profiling}
1687: \label{execution}
1688:
1689: \index{profiling}
1690: In large software systems it can become difficult to tell where
1691: the inefficiencies are. Execution profilers can help with this process.
1692: A typical profiler might provided information about the amount of time
1693: spent in each procedure and the number of times it was called.
1694:
1695: Standard ML of New Jersey has an execution profiler\cite{appel88:prof},
1696: which will only briefly be described here. Call counts are handled
1697: completely independently of the runtime system; the compiler inserts
1698: program variables that are incremented on entry to procedures, and the
1699: profiler examines these variables to generate call-count information.
1700:
1701: Execution-time estimates are more difficult. The Unix \verb"prof" system
1702: call starts a timer interrupt in the operating system that periodically
1703: samples the program's program counter. An affine function is applied
1704: to the PC and the corresponding element of a ``histogram'' array is
1705: incremented. Then the histogram can be compared against the object
1706: file to see how many interrupts occurred in each procedure, which gives
1707: a good estimate of actual time spend in each procedure.
1708:
1709: With a garbage collector that moves procedures around in memory, this
1710: method becomes unwieldy. Instead, the runtime system has a variable
1711: \verb"current" that points at a sample-count cell for the currently
1712: executing procedure. Whenever (profiled) code begins executing a procedure
1713: (or returns from a call), it assigns the address of the new procedure's
1714: \index{current}
1715: sample-count variable into \verb"current" (the compiler inserts code to do
1716: this). The timer interrupt, instead
1717: of examining the PC, just increments the cell pointed to by \verb"current".
1718:
1719: This very simple mechanism does not greatly complicate the runtime system,
1720: but provides profiling information with a relatively low overhead.
1721:
1722: \section{Debugging}
1723: \label{debugging}
1724:
1725: We are currently developing a high-level
1726: debugger\index{debugger} based on the same principles as our
1727: profiler---namely, minimal interaction with the runtime system.
1728: The work is still in its early stages, but we believe that
1729: it is possible to make a debugger this way, and that the runtime system
1730: won't have to grow much in size to support it. A detailed description
1731: of our plans is beyond the scope of this paper.
1732:
1733: \section{Handling of interrupts and exceptions}
1734: \label{handling}
1735:
1736: The ML language has an exception\index{exception}-handling
1737: mechanism with dynamically-nested
1738: handlers. Some exceptions are raised by the program itself, some are related
1739: to synchronous hardware exceptions (like floating point errors), and
1740: some are generated asynchronously (like the \verb"Interrupt" exception
1741: raised when the user presses the interrupt key).
1742:
1743: The ML program has a ``current-exception-handler'' register that just
1744: contains a pointer to a continuation\index{continuation}
1745: (i.e. a closure).
1746: Raising an exception just
1747: corresponds to invoking this continuation with the exception-object
1748: as an argument. Dynamic nesting of handlers is handled completely by the
1749: compiler: it generates code that saves the previous handler (in the
1750: new handler's closure) and restores it upon exit from the scope of the
1751: new handler.
1752:
1753: This makes it particularly easy for the programming language's exception
1754: mechanism to be attached to the hardware's notion of fault or interrupt.
1755: When a fault or interrupt\index{interrupt}
1756: occurs, the operating system calls a special
1757: (assembly-language)
1758: function in the runtime system. This function then determines what
1759: caused the fault, clears it if necessary, then {\em does not} return to the
1760: operating system but just invokes the current-exception-handler continuation
1761: on the appropriate exception object.
1762:
1763: \section{Fancier garbage collectors and object boundaries}
1764: \label{fancier}
1765:
1766: Our current system uses a good, simple generational garbage
1767: collector\cite{appel89:sggc}. Generation garbage
1768: collection\cite{lieberman83}\cite{ungar84} is based on the observations
1769: that newer records tend to become garbage more quickly, so that the
1770: collector should concentrate its effort on the newer records; and that
1771: newer records tend to point to older records, but not vice versa, so that
1772: the older records need not be searched for roots into the newer area.
1773:
1774: Sometimes, however, older records are modified (by a \verb"rplaca" operation
1775: in Lisp or an assignment operation in ML)
1776: to point to newer ones.
1777: Generational garbage collectors require
1778: the maintenance of a list of all modified records.
1779: To ensure portability,
1780: we use a very simple scheme to maintain this list: the compiler
1781: inserts instructions after each \verb"update" operation to put the
1782: address of the updated cell on a special list for the garbage collector
1783: to use.
1784:
1785: \index{page fault}\index{virtual memory}\index{garbage collector}
1786: A clever trick is to use the virtual memory system in maintaining this list.
1787: It is only updates to records in older generations that must be remembered;
1788: we can just make all the memory occupied by older generations read-only,
1789: and an update will cause a page fault. The fault-handler can then put the
1790: page on a list of updated pages, and mark the page as writeable.
1791: During garbage collection, the entire page can be searched for
1792: roots into the newer region.
1793:
1794: A different virtual-memory trick can be used to achieve concurrent garbage
1795: collection\cite{appel88:gc}. By making the pages of the {\em tospace} inaccessible
1796: until they have been scanned and forwarded, we can allow the ML program
1797: to continue executing even while the garbage collector is running.
1798: An access to an unscanned page of {\em tospace} causes a page fault, and the
1799: fault handler scans that page and makes it accessible.
1800: Then the latency is bounded by the product of the page size and the
1801: record size (in practice, to just a few milliseconds).
1802: This is very desirable in a real-time or interactive system.
1803:
1804: Both of these algorithms require that pages be scanned (and forwarded)
1805: out of order. When objects cross page boundaries, it is difficult
1806: to know where the first object on a page begins, so that its descriptor
1807: may be found. There are solutions to this problem that involve keeping
1808: track of objects that cross page boundaries\cite{appel88:gc}, but the
1809: SML-NJ runtime system has a runtime data format that allows a very
1810: simple solution.
1811:
1812: Suppose we need to scan a particular page (to forward all its pointers).
1813: When we start at the beginning of the page, we don't know whether
1814: we are in the middle of a record or of a string; and we don't know
1815: where the descriptor for the object is.
1816: But if we knew that the page contained only records, then we wouldn't need
1817: to find the descriptor;
1818: the important thing about records is that their boundaries can be ignored.
1819: If a page consists of the last part of one record, followed by several
1820: complete records, followed by the first part of the last record, the
1821: pointers in all of those records can be scanned and forwarded
1822: without regard to the boundaries. Since the descriptors are unboxed
1823: (they look like integers), they won't be touched; and all the other
1824: fields are tagged pointers or integers which will be forwarded (or not)
1825: appropriately. (See figure~\ref{boundaries} for an illustration.)
1826: \begin{figure}[htbp]
1827: \label{boundaries}
1828: \begin{verbatim}
1829: +------+--object boundary
1830: | desc |
1831: +------+
1832: | o------------>
1833: -----+------+-----page boundary
1834: | 5 |
1835: +------+--object boundary
1836: | desc |
1837: +------+
1838: | o------------>
1839: +------+
1840: | o------------>
1841: +------+--object boundary
1842: | desc |
1843: +------+
1844: | 7 |
1845: +------+
1846: | o------------>
1847: -----+------+-----page boundary
1848: | 6 |
1849: +------+
1850: | o------------>
1851: +------+--object boundary
1852: \end{verbatim}
1853: \caption{Object boundaries may be ignored by the forwarding algorithm}
1854: \end{figure}
1855:
1856: And if we knew that the page contained only strings, then it wouldn't
1857: need to be scanned at all, since strings contain no pointers.
1858:
1859: Thus, a simple arrangement that's useful when pages need to be scanned
1860: in arbitrary order is
1861: to segregate pointer-containing objects (records and arrays) from
1862: non-pointer-containing objects (strings and byte-arrays). This isn't necessary
1863: for the newly-allocated objects; the compiler can continue to maintain
1864: just one register that points at the beginning of the free space. But
1865: the copying garbage collector (the functions \verb"gc" and \verb"forward")
1866: must copy records and strings into different parts of memory.
1867: This greatly simplifies the implementation of page-based garbage collection
1868: algorithms.
1869:
1870: \section{Size of the SML-NJ runtime system}
1871: \label{size}
1872:
1873: Our runtime system is implemented in 1548 lines of C and 232 lines of
1874: assembly language (the assembly language must be duplicated for each
1875: target architecture). This is small indeed, considering the functionality
1876: of our Standard ML system. We have made it small by moving as much as possible
1877: out of the runtime system, and by having a simple format for ML data.
1878:
1879: This 1780 lines of code can be divided approximately as follows:
1880: \begin{enumerate}
1881: \item[291] lines of C to initialize and link the Standard ML library
1882: and loader, which then loads the rest of the system.
1883: {\tiny (run.c)}
1884: \item[299] lines to implement the copying garbage collector with repairs.
1885: {\tiny (gc.c)}
1886: \item[55] lines of C to implement the simulated process-switching required
1887: for garbage-collector access to ML registers.
1888: {\tiny (callgc.c)}
1889: \item[400] lines for the management of generational garbage collection,
1890: and for deciding when to ask the operating system for more memory.
1891: {\tiny (callgc.c)}
1892: \item[304] lines to implement C-language functions and data structures
1893: used as primitives by the ML program.
1894: {\tiny (cstruct.c)}
1895: \item[117] lines of C to implement the suspending of process states into
1896: Unix executable files.
1897: {\tiny (export.c)}
1898: \item[72] lines of utility functions for C functions that manipulate ML
1899: objects.
1900: {\tiny (objects.c)}
1901: \item[38] lines of assembly language to handle simulated process switching.
1902: {\tiny (*.prim.s)}
1903: \item[195] lines of assembly language to implement primitive functions
1904: callable by ML programs.
1905: {\tiny (*.prim.s)}
1906: \end{enumerate}
1907: For comparison, the Icon runtime system\cite{griswold86} (excluding
1908: its interpreter) is 18,000 lines of C; the T3\cite{kranz86} runtime system is
1909: 1,900(?) lines of C and assembly language; the FranzLisp runtime system
1910: (including interpreter)
1911: is 19,500 lines of C; the Poly/ML runtime system is ??? lines of ???.
1912:
1913: \section{Conclusion}
1914: \label{conclusion}
1915:
1916: It's easy to implement a hi-tech runtime system if you do it cleanly.
1917:
1918: \section{Acknowlegements}
1919:
1920: David MacQueen, Trevor Jim, and Bruce Duba have all worked on the runtime
1921: system, and their assistance has been valuable. Norman Ramsey provided
1922: many useful suggestions about the organization of this paper.
1923:
1924: %\cleardoublepage
1925: \bibliographystyle{plain}
1926: \bibliography{appel}
1927: %\cleardoublepage
1928: %\printindex
1929: \end{document}
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.