Difference between revisions of "UNIX V6 internals"

From Computer History Wiki
Jump to: navigation, search
(better heaers, typo)
(+Booting)
(10 intermediate revisions by the same user not shown)
Line 1: Line 1:
The internals of [[UNIX Sixth Edition|UNIX V6]] are relatively easy to understand, particularly with the aid of the (justly) famed [[Lions book]], John Lions' ''Commentary on UNIX 6th Edition''.
+
The internals of [[UNIX Sixth Edition|UNIX V6]] are relatively easy to understand, particularly with the aid of the (justly) famed [[Lions book]], John Lions' ''Commentary on UNIX 6th Edition''. Reading [[UNIX V6 memory layout]], which explains V6's use of physical [[main memory]], and [[PDP-11 Memory Management]], is recommended as a first step, before tackling Lions.
  
Here are a few notes on various topics which are covered in a bit more detail than in Lions, and which may be helpful.
+
Here are a few notes on various specific topics which are covered in more detail than in Lions, and which may be helpful.
 +
 
 +
==Booting==
 +
 
 +
UNIX [[kernel]]s consists of a number of smallish [[relocatable binary]] modules which are statically [[linking|linked]] into a large [[object code]] image; during [[bootstrap|booting]], that image is loaded into memory and started. After the usual initialization, the '0th' [[process]] (which in V6 has the task of [[swapping]] processes in and out) is hand-crafted; if then 'forks' into two, using the standard UNIX fork() [[system call]] (which creates a 'clone' of the existing process).
 +
 
 +
The second process then runs a tiny program (the binary for which is built into the kernel) which does an 'exec()' system call, to read in and run "/etc/init". That process/command then does another fork(), and the child process from that exec()'s the shell ([[command interpreter]], in "/bin/sh").
  
 
==savu(), retu() and aretu()==
 
==savu(), retu() and aretu()==
  
These are the primitives which switch, or otherwise adjust, [[stack]]s in the [[kernel]]. aretu() is significantly different from retu() - the latter switches to a different [[process]]/stack, whereas aretu() does a 'non-local goto' in the current process. (Actually, technically, it switches to a different [[stack frame]] on the current stack; when the [[subroutine]] which had called aretu() returns, it does not return to its caller, but instead returns to the procedure which had called savu().) In addition to switching to a different stack, retu() also switches to a saved stack frame on that stack, in the same manner as aretu().
+
These are the primitives which switch, or otherwise adjust, [[stack]]s in the kernel. aretu() is significantly different from retu() - the latter switches to a different process/stack, whereas aretu() does a 'non-local goto' in the current process. (Actually, technically, it switches to a different [[stack frame]] on the current stack; when the [[subroutine]] which had called aretu() returns, it does not return to its caller, but instead returns to the procedure which had called savu().) In addition to switching to a different stack, retu() also switches to a saved stack frame on that stack, in the same manner as aretu().
  
 
Note that in [[PDP-11]] [[C programming language|C]] all stack frames look identical, but this is not true of other machines/[[compiler]]s. So if subroutine A calls savu(), and subroutine B calls aretu(), when the call to aretu() returns, procedure B is still running, but on procedure A's stack frame. So on machines where A's stack frame looks different from B's, hilarity ensues; this famously caused a problem when [[Unix Seventh Edition]] was moved to the [[Interdata 8/32]].
 
Note that in [[PDP-11]] [[C programming language|C]] all stack frames look identical, but this is not true of other machines/[[compiler]]s. So if subroutine A calls savu(), and subroutine B calls aretu(), when the call to aretu() returns, procedure B is still running, but on procedure A's stack frame. So on machines where A's stack frame looks different from B's, hilarity ensues; this famously caused a problem when [[Unix Seventh Edition]] was moved to the [[Interdata 8/32]].
  
==rsav, qsav and ssav==
+
===rsav, qsav and ssav===
  
There are actually three sets of saved stack information stored in the 'user' [[structure]] (the [[swapping|swappable]] per-process data block):
+
There are actually three sets of saved stack information stored in the 'user' [[structure]] (the swappable per-process data block):
 
<pre> int u_rsav[2]; /* save r5,r6 when exchanging stacks */
 
<pre> int u_rsav[2]; /* save r5,r6 when exchanging stacks */
 
int u_qsav[2]; /* label variable for quits and interrupts */
 
int u_qsav[2]; /* label variable for quits and interrupts */
Line 18: Line 24:
 
Calls to retu(), the primitive to switch stacks/processes, ''always'' use rsav. The others are for 'non-local gotos' inside a process.
 
Calls to retu(), the primitive to switch stacks/processes, ''always'' use rsav. The others are for 'non-local gotos' inside a process.
  
One can think of the qsav as a poor man's [[condition handler|exception handler]] for process software [[interrupt]]s. When a process is sleeping on some event, when it is interrupted from out of that wait, rather than the sleep() call returning, it wakes up returning from the procedure that did the savu(qsav). (That is because sleep() - which is the procedure that's running when the call to aretu(qsav) returns - does a return immediately after restoring the stack to the frame saved in qsav.)
+
One can think of the qsav as a poor man's [[condition handler|exception handler]] for software [[interrupt]]s to a process while it's asleep in the kernel, waiting for something. When a process is interrupted out of such a wait, rather than the sleep() call returning, the process wakes up returning from the procedure that did the savu(qsav). (That happens because sleep() - which is the procedure that's running when the call to aretu(qsav) returns - does a return immediately after restoring the stack to the frame saved in qsav.)
  
The ssav is used in association with swapping; when a process is swapped out, since that can happen in a number of ways/places, the call stack can contains calls to various things like expand(), etc. When it's swapped back in, the simplest thing to do is to just throw that all away, and have it go back to where it was just before it was decided to swap it out.
+
The ssav is used in association with swapping; when a process is swapped out, since that can happen in a number of ways/places, the call stack can contains calls to various things like expand(), etc. When it's swapped back in, apparently rather than include code in all those places to unwind the call stack, the simplest thing to do is to just throw that all away, and have it go back to where it was just before it was decided to swap it out.
  
 
==exec() and pure-text images==
 
==exec() and pure-text images==
  
For simple [[program]]s/commands (stored in the [[file system]] in a [[file]], and read into [[main memory]] to [[execute]] them), UNIX divides the [[address space]] of a process into a mixed 'text/data' [[segment]] and a 'stack' segment, using [[hardware]] support from [[PDP-11 Memory Management]]. The text/data segment contains both [[object code]], and data.
+
For simple [[program]]s/commands (stored in the [[file system]] in a [[file]], and read into main memory to [[execute]] them), UNIX divides the [[address space]] of a process into a mixed 'text/data' [[segment]] and a 'stack' segment, using [[hardware]] support from PDP-11 Memory Management. The text/data segment contains both [[object code]], and data.
  
UNIX also has the ability to provide separate 'text' and 'data' segments (referred to as a 'pure text'); the text segment will be read-only, and shared between all processes executing that program.
+
UNIX also has the ability to provide separate 'text' (referred to as a 'pure text') and 'data' segments; the text segment will be read-only, and shared between all processes executing that program/command.
  
 
(Note that for simplicity, the data and stack segments are stored contiguously in physical main memory, although they are in separate segments in the address space of the process.)
 
(Note that for simplicity, the data and stack segments are stored contiguously in physical main memory, although they are in separate segments in the address space of the process.)
  
The operation of the exec() system call (which replaces the contents of the address space of a process with new contents, read in from a program/command in a file) is fairly simple for mixed programs/commands: a block of main memory large enough to hold the new program/command is allocated (the process may pause before this happens), the text and data is read in, and off it goes.
+
The operation of the exec() system call (which replaces the contents of the address space of a process with new contents, read in from a program/command stored in a file) is fairly simple for mixed programs/commands: a block of main memory large enough to hold the new program/command is allocated (the process may pause to be swapped out before this happens), the text and data is read in, and off it goes.
  
 
Both newproc() (the routine that implements the fork() operation) and expand() (the routine used to re-size the data/stack segments of a process) have code which uses a simple memory-memory copy if there is enough free memory to do what they have been requested to do.
 
Both newproc() (the routine that implements the fork() operation) and expand() (the routine used to re-size the data/stack segments of a process) have code which uses a simple memory-memory copy if there is enough free memory to do what they have been requested to do.
Line 36: Line 42:
 
Things are considerably more complex when the new program/command has a pure text.
 
Things are considerably more complex when the new program/command has a pure text.
  
In such a case, exec() calls xalloc(), which, if the text was not already available, reads in a copy of the pure text from the file, and then ''always'' moves that (contiguous) copy out to the swap device. In both this case, and if the text was in use, but not already in main memory, it ''also'' swaps the rest of the process out, because, as the code explains:
+
In such a case, exec() calls xalloc(), which, if the text was not already available (either in main memory, or swapped out), reads in a copy of the pure text from the file, and then ''always'' moves that (contiguous) copy out to the swap device. In both this case, and if the text was in use, but not already in main memory, it ''also'' swaps the rest of the process out, because, as the code explains:
 
<pre>
 
<pre>
 
   if the calling process
 
   if the calling process
Line 45: Line 51:
 
The first part of of the comment is applicable even in the case where the text was just read into main memory: note that the process doesn't yet have a data or stack segment allocated at that point, just the 'user' area. (The two will be stored contiguously with the 'user' area, when they are eventually added.)
 
The first part of of the comment is applicable even in the case where the text was just read into main memory: note that the process doesn't yet have a data or stack segment allocated at that point, just the 'user' area. (The two will be stored contiguously with the 'user' area, when they are eventually added.)
  
The data and stack segments will be set up later in the exec() code, after the call to xalloc() returns, after the process is swapped back in, but this may be impossible if the text segment is 'poorly' placed in main memory - which is why the in-memory copy is discarded.
+
The data and stack segments will be set up later in the exec() code, after the call to xalloc() returns, after the process is swapped back in, but this may be impossible if the text segment is 'poorly' placed in main memory - which is why the in-memory copy is discarded. (This is more likely to be an issue on systems with a limited amount of main memory, of course.)
  
(In fact, the process will _never_ have anything other than a 'user' area when in xalloc(); the only call to xalloc() in the system is immediately preceeded by an "expand(USIZE)" which throws away everything except the 'user' area.)
+
(In fact, the process will ''never'' have anything other than a 'user' area when in xalloc(); the only call to xalloc() in the system is immediately preceeded by an "expand(USIZE)" which throws away everything except the 'user' area.)
  
 
(It would be possible to do what the comment suggests - adding code to check to see if there's enough memory available to hold the pure text as well as the rest of the process, and if so, avoiding the swap-out/in of the 'user' segment of the process.)
 
(It would be possible to do what the comment suggests - adding code to check to see if there's enough memory available to hold the pure text as well as the rest of the process, and if so, avoiding the swap-out/in of the 'user' segment of the process.)
  
Anyway, unlike the mixed text/data case, a considerable number of swap operations ''inevitably result'', (the exact number depending on exactly what the situation is with main memory); for the first instance of a pure-text program/command, at least:
+
Anyway, unlike the mixed text/data case, a considerable number of swap operations ''inevitably'' result, (the exact number depending on exactly what the situation is with main memory); for the first instance of a pure-text program/command, at least:
 +
 
 +
* swapping out the text
 +
* swapping out the 'user' area
 +
* swapping the text back in
 +
* swapping the 'user' area back in
 +
 
 +
The last two are performed by the so-called 'swapping' process (process 0), which runs in a permanent loop in the kernel, in sched(); its job is to find processes that need to be swapped in, and do so (perhaps after swapping others out, to make room).
 +
 
 +
Note that at that point, after the two swaps in, the process still does not have its data and stack segments; therefore, the call to expand(), after the return from xalloc(), to allocate the memory for them, may ''also'' result in a swap out/in cycle.
 +
 
 +
==See also==
 +
 
 +
* [[Unix V6 dump analysis]]
 +
* [[Installing UNIX Sixth Edition]]
 +
** [[Setting up UNIX Sixth Edition]]
 +
** [[Upgrading UNIX Sixth Edition‎]]
 +
** [[Running UNIX V6 on an -11/23]]
 +
* [[Installing Unix v6 (PDP-11) on SIMH]]
 +
** [[Running Unix v6 in SIMH]]
 +
* [[Installing UNIX Sixth Edition on Ersatz-11]]
 +
 
 +
==External links==
  
* swapping out the text:
+
* [https://minnie.tuhs.org/pipermail/tuhs/2018-February/014299.html Odd behaviour on V6 startup]
* swapping out the 'user' area:
 
* swapping the 'user' area back in:
 
* swapping the text back in.
 
  
 
[[Category: UNIX]]
 
[[Category: UNIX]]

Revision as of 12:28, 4 January 2022

The internals of UNIX V6 are relatively easy to understand, particularly with the aid of the (justly) famed Lions book, John Lions' Commentary on UNIX 6th Edition. Reading UNIX V6 memory layout, which explains V6's use of physical main memory, and PDP-11 Memory Management, is recommended as a first step, before tackling Lions.

Here are a few notes on various specific topics which are covered in more detail than in Lions, and which may be helpful.

Booting

UNIX kernels consists of a number of smallish relocatable binary modules which are statically linked into a large object code image; during booting, that image is loaded into memory and started. After the usual initialization, the '0th' process (which in V6 has the task of swapping processes in and out) is hand-crafted; if then 'forks' into two, using the standard UNIX fork() system call (which creates a 'clone' of the existing process).

The second process then runs a tiny program (the binary for which is built into the kernel) which does an 'exec()' system call, to read in and run "/etc/init". That process/command then does another fork(), and the child process from that exec()'s the shell (command interpreter, in "/bin/sh").

savu(), retu() and aretu()

These are the primitives which switch, or otherwise adjust, stacks in the kernel. aretu() is significantly different from retu() - the latter switches to a different process/stack, whereas aretu() does a 'non-local goto' in the current process. (Actually, technically, it switches to a different stack frame on the current stack; when the subroutine which had called aretu() returns, it does not return to its caller, but instead returns to the procedure which had called savu().) In addition to switching to a different stack, retu() also switches to a saved stack frame on that stack, in the same manner as aretu().

Note that in PDP-11 C all stack frames look identical, but this is not true of other machines/compilers. So if subroutine A calls savu(), and subroutine B calls aretu(), when the call to aretu() returns, procedure B is still running, but on procedure A's stack frame. So on machines where A's stack frame looks different from B's, hilarity ensues; this famously caused a problem when Unix Seventh Edition was moved to the Interdata 8/32.

rsav, qsav and ssav

There are actually three sets of saved stack information stored in the 'user' structure (the swappable per-process data block):

	int	u_rsav[2];	/* save r5,r6 when exchanging stacks */
	int	u_qsav[2];	/* label variable for quits and interrupts */
	int	u_ssav[2];	/* label variable for swapping */

Calls to retu(), the primitive to switch stacks/processes, always use rsav. The others are for 'non-local gotos' inside a process.

One can think of the qsav as a poor man's exception handler for software interrupts to a process while it's asleep in the kernel, waiting for something. When a process is interrupted out of such a wait, rather than the sleep() call returning, the process wakes up returning from the procedure that did the savu(qsav). (That happens because sleep() - which is the procedure that's running when the call to aretu(qsav) returns - does a return immediately after restoring the stack to the frame saved in qsav.)

The ssav is used in association with swapping; when a process is swapped out, since that can happen in a number of ways/places, the call stack can contains calls to various things like expand(), etc. When it's swapped back in, apparently rather than include code in all those places to unwind the call stack, the simplest thing to do is to just throw that all away, and have it go back to where it was just before it was decided to swap it out.

exec() and pure-text images

For simple programs/commands (stored in the file system in a file, and read into main memory to execute them), UNIX divides the address space of a process into a mixed 'text/data' segment and a 'stack' segment, using hardware support from PDP-11 Memory Management. The text/data segment contains both object code, and data.

UNIX also has the ability to provide separate 'text' (referred to as a 'pure text') and 'data' segments; the text segment will be read-only, and shared between all processes executing that program/command.

(Note that for simplicity, the data and stack segments are stored contiguously in physical main memory, although they are in separate segments in the address space of the process.)

The operation of the exec() system call (which replaces the contents of the address space of a process with new contents, read in from a program/command stored in a file) is fairly simple for mixed programs/commands: a block of main memory large enough to hold the new program/command is allocated (the process may pause to be swapped out before this happens), the text and data is read in, and off it goes.

Both newproc() (the routine that implements the fork() operation) and expand() (the routine used to re-size the data/stack segments of a process) have code which uses a simple memory-memory copy if there is enough free memory to do what they have been requested to do.

Things are considerably more complex when the new program/command has a pure text.

In such a case, exec() calls xalloc(), which, if the text was not already available (either in main memory, or swapped out), reads in a copy of the pure text from the file, and then always moves that (contiguous) copy out to the swap device. In both this case, and if the text was in use, but not already in main memory, it also swaps the rest of the process out, because, as the code explains:

  if the calling process
  is misplaced in core the text image might not fit.
  Quite possibly the code after "out:" could check to
  see if the text does fit and simply swap it in.

The first part of of the comment is applicable even in the case where the text was just read into main memory: note that the process doesn't yet have a data or stack segment allocated at that point, just the 'user' area. (The two will be stored contiguously with the 'user' area, when they are eventually added.)

The data and stack segments will be set up later in the exec() code, after the call to xalloc() returns, after the process is swapped back in, but this may be impossible if the text segment is 'poorly' placed in main memory - which is why the in-memory copy is discarded. (This is more likely to be an issue on systems with a limited amount of main memory, of course.)

(In fact, the process will never have anything other than a 'user' area when in xalloc(); the only call to xalloc() in the system is immediately preceeded by an "expand(USIZE)" which throws away everything except the 'user' area.)

(It would be possible to do what the comment suggests - adding code to check to see if there's enough memory available to hold the pure text as well as the rest of the process, and if so, avoiding the swap-out/in of the 'user' segment of the process.)

Anyway, unlike the mixed text/data case, a considerable number of swap operations inevitably result, (the exact number depending on exactly what the situation is with main memory); for the first instance of a pure-text program/command, at least:

  • swapping out the text
  • swapping out the 'user' area
  • swapping the text back in
  • swapping the 'user' area back in

The last two are performed by the so-called 'swapping' process (process 0), which runs in a permanent loop in the kernel, in sched(); its job is to find processes that need to be swapped in, and do so (perhaps after swapping others out, to make room).

Note that at that point, after the two swaps in, the process still does not have its data and stack segments; therefore, the call to expand(), after the return from xalloc(), to allocate the memory for them, may also result in a swap out/in cycle.

See also

External links