.ifi init_plm "FS-00"
.srv draft ""
.srv draft_date ""
.srv section "%Arg1%"
.pdl 66
.ifi l0h "Address and Name Space Management"
     The functions of address and name space management are to enter segments
.ifi hit "K|address and name space management"
into the process' address space, keep track of them, and to remove them from
the process' address space.  Of course, the introduction of segments and
directories must be done relative to the requirements of access control and
other policies established by directory control (dc_find); indeed, address
and name space management is under the command of directory control.

     Address and name space management maintains the KST (known segment table)
.ifi hit "K|KST"
.ifi hit "S|known segment table~see KST"
.ifi hit "K|address space"
as its main data structure describing the process' address space.  The RNT
.ifi hit "K|name space"
.ifi hit "K|RNT"
(reference name table) is actually maintained by the segment initiation and
termination file system primitives but the relationship between a segment's
reference names and its presence in the address space will be described under
address and name space management.

     The main functions of address and name space management are to initiate
and make known segments, to make unknown and terminate segments, and to add
and remove reference names for them.  Other utility functions involving the
maintenance of KST entries are also included, and are described below.
.ifi l1h "Segment Initiation/Making Known"
     The process of adding a segment to the address space is the process of
.ifi hit "K|initiation"
.ifi hit "K|making known"
"making the segment known", or "initiating" the segment.  Actually,
"initiation" refers to the request from an outer ring to associate a segment
number with a segment; this request may also involve associating a reference
name with the segment.  The process of associating a KST entry with a segment
is the process of "making a segment known", a ring zero internal operation.
Since a user can request the initiation of an already initiated segment, the
initiate function does not necessarily imply the introduction of a segment
into the address space.  The module initiate_ is the user ring callable file
.ifi hit "K|initiate_"
system primitive associated with initiating a segment.  The major activity to
be performed is
.ifi hit "K|makeknown_"
to translate a pathname into a directory entry.  The module makeknown_
performs the process of associating a KST entry and a segment number with the
segment described by the supplied directory entry.

     initiate_ performs the required calls to dc_find to establish the user's
ability to "see" the segment requested.  (In particular, the user is required
to have non-null effective access to the segment.)  It also performs some
courtesy functions such as ensuring that the logical volume containing the
segment is mounted, extending the LOT to encompass the segment number, if
.ifi hit "K|LOT"
necessary, adding any desired reference name, returning the bit count from the
branch, etc.

     makeknown_ does the work of finding and setting up the KST entry for the
segment, given its directory entry.  This is not to be confused with making
the segment active.  (The segment will become connected to the process, and
activated  as a result, if necessary, only when the process actually touches
the segment.  Directories are an exception, however, see below.) The operation
involves finding or creating the KST entry for this segment so that a future
.ifi hit "K|connection"
segment fault on it will work.

     kstsrch is first used to see if the segment is already known.  If so
.ifi hit "K|kstsrch"
fine.  If so, however, and the process wants to allow write access (within the
bounds of access control, of course) and didn't have it before, or is
requesting a privileged initiate and didn't before, the segment needs to be
.ifi hit "K|privilege~initiation"
.ifi hit "K|setfaults"
setfaulted (and the dtem within its KST entry set) so that the process' access
gets recomputed.

     Assuming the segment is not already known, a KST entry is found from the
free list, with the KST being expanded and garbage collected if necessary.
(Refer to garbage collection in a later section.) The UID in the KST entry is
filled in; this KST is threaded into the KST hash list given this UID.  The
filling in of kste.entryp allows seg_fault to activate this segment.  (Refer
to the description of sum and the seg_fault entry to dc_find for details.)

     Various flags are set in the KST entry, transparent modify, write
.ifi hit "K|transparent usage/modification"
allowed, etc., from the argument structure supplied to makeknown_.
The usage count for this ring (validation level) is incremented.  The inferior
count for its parent is incremented to protect it from KST garbage collection.

     Finally, the segment is forced activated if requested.  (It follows that
.ifi hit "K|directory~connection"
any directory control request to make a directory known will be followed
almost immediately by a reference to that directory.  To save the processing
overhead for the segment fault on the directory, directory makeknowns request
explicit activation of the directory.  The directory is not entry held,
though, so it can become deactivated, but this is unlikely before directory
control will get around to referencing the directory.)
.ifi l1h "Segment Usage Counts"
     When a segment or directory is initiated, the "usage count" for the
.ifi hit "K|usage count"
segment for the given ring (the ring of validation) is incremented.  It is
decremented for each request to terminate the segment.  The intended
purpose for this is so that a segment may be initiated by multiply nested
functions in the user ring, and only when the first function finishes (it will
be the last to finish), will the segment actually become made unknown.  This
mechanism also allows a segment to be initiated in multiple rings, with the
user ring unable to make the segment unknown until all rings release claims to
it.

     The usage counts are maintained by segno_usage.  This very simple utility
exists so as to enforce any policy rules about segment usage counts (such as
.ifi hit "K|segno_usage"
when a count hits the limit, it can never be decremented again).  Also, having
segno_usage as an external function allows all segment usage count
manipulation in the system to be easily found.

     The usage count for a gate in its ring of execution (as opposed to the
.ifi hit "K|usage count~gate"
ring of its caller/initiator) is incremented by the dynamic linker when the
linker combines the gates linkage in the target ring, via a side door (into
segno_usage).  This must be done to protect the inner ring linkage from outer
ring termination of the segment.

     The usage count for a segment is also incremented when it is necessary to
.ifi hit "K|KST~garbage collection"
protect the segment from "KST garbage collection".  Refer to the section on
KST garbage collection later in this section.
.ifi l1h "Segment Termination/Making Unknown"
     The opposite counterparts to the initiate/makeknown functions are
.ifi hit "K|termination"
.ifi hit "K|making unknown"
terminate/makeunknown.  Termination is a user ring request to disassociate a
segment number with a segment.  Actually, it is a statement that a segment is
no longer needed.  Depending on the usage counts for the segment, a terminate
request may or may not correspond to actually causing the segment to leave the
address space.  The function of terminating a segment is done by terminate_.
.ifi hit "K|terminate_"
The makeunknown function performs the disassociation of a KST entry with a
.ifi hit "K|makeunknown_"
segment; it is performed within makeunknown_.

     The terminate_ module has as its major job the translation of the user
supplied segment identifier (pathname or segment pointer) into the number of
the segment to be terminated.  In the process of performing this translation,
the systems name lookup policy is enforced.  (That is, the user may not
request the termination of a segment no longer "visible" to the process.)
terminate_ also removes any reference names that are requested to be removed.
Alternatively, terminate_ (makeunknown_, actually) refuses to terminate a
segment if this termination would cause the usage count (number of outstanding
initiations) to exceed the number of reference names.  (Since each reference
name corresponds to an initiation, each reference name on a segment
.ifi hit "K|LOT"
.ifi hit "S|linkage offset table~see LOT"
.ifi hit "K|ISOT"
.ifi hit "S|internal static offset table~see ISOT"
corresponds to an outstanding initiation.) The LOT and ISOT entries for the
segment is also zeroed when the segment is truly made unknown.

     makeunknown_ just decrements the usage count for the ring of validation.
Actually making a segment unknown (when all counts hit zero) is a simple
matter of decrementing the inferior count in the KST entry for its parent,
.ifi hit "K|setfaults"
unthreading the segment's KST entry (making it free), and setfaulting the
segment.
.ifi l1h "Reference Name Manipulation"
     The RNT for a given ring is found via the rnt_ptr in the stack header for
.ifi hit "K|RNT"
the given ring.  It consist of a header and an area to hold the RNT entries.
The RNT itself is allocated in the linkage area for the ring (found via the
combined linkage region pointer (clr_ptr) in the stack header for the ring).

     The RNT is maintained by the program ref_name_.  ref_name_ contains
.ifi hit "K|ref_name_"
entries to add a new reference name/segment number pair (a RNT entry) to the
.ifi hit "S|reference name table~see RNT"
RNT, delete an entry given a reference name, delete all entries for a segment
given its segment number, map a reference name into a segment number, and
return all reference names for a given segment number.  Its operation is pretty
straight forward.
.ifi l1h "Functions for Directory Control"
     Address and name space management is closely aligned with directory
control.  Directory control can't do anything unless it can get address and
name space management to bring directories into the address space.  Address
and name space management, on the other hand, only brings things into the
address space for which directory control approves (for which the security
policy is enforced).

     Address and name space management provides some functions explicitly for
directory control to use to refer to segments and their KST entries.
.ifi l2h "Segment Pointer to Pathname Translation"
     get_pathname_ returns a pathname given a segment number.  For segment
.ifi hit "K|get_pathname_"
.ifi hit "K|segment pointer to pathname translation"
numbers known by the pathname associate memory, this is easy.  Otherwise, it
must be generated.  The directory entry for the object found with
sum$getbranch_root_my gives the entryname portion of the pathname.  The
directory name is found by calling get_pathname_ recursively on the directory
.ifi hit "K|PAM"
containing this entry.  After all of this work, the pathname found is put into
.ifi hit "S|pathname associative memory~see PAM"
the PAM.

     The pathname associative memory is maintained between directory control
and address and name space management to provide a quick map between segment
numbers and directory pathnames.  The PAM is maintained by pathname_am, and is
discussed under mechanisms.

     The utility sum is also an interface module between directory control and
address and name space management.  It locates directory entries via the KST.
The operation of sum is discussed under directory control primitives.
.ifi l1h "KST Maintenance Functions"
     Address and name space management contains several KST maintenance
.ifi hit "K|KST~maintenance"
utilities.

     get_kstep takes a segment number and returns a pointer to the KST entry
.ifi hit "K|get_kstep"
for the segment.  It performs a few validity checks in the process.  Also, the
dir entrypoint makes sure that the object is a directory.

     kst_info returns a few pieces of information found in the KST.  get_uid
.ifi hit "K|kst_info"
returns the UID for a given initiated segment (from the KST entry).  The name
lookup policy does not apply here, since the UID returned is extracted purely
from the KST entry, and could not have changed since the user initiated the
segment.  Also, the UID is returned regardless of whether the segment exists
any more or not.  high_low_seg_count returns the span between low and high
segment number limits in the KST (which implies the user's KST limit).

     kst_util performs utility functions with respect to the KST.  free_range
.ifi hit "K|kst_util"
and get_range deal with ranges of segment numbers (used by very large arrays).
get_range tries to obtain N contiguous free segment numbers.  It tries this
twice.  If the first attempt to find N segment numbers fails, it performs a
.ifi hit "K|KST~garbage collection"
KST garbage collection (see below) and tries once more.  It succeeds if it
finds N such segment numbers, or it can extend the KST (upwards from
kst.highest_used_segno but below kst.highseg).  These entries are unthreaded
from the KST free list.  A flag of all 7's for the KST entry forward pointer
flags them as reserved segments.  At this time, these segment numbers belong
.ifi hit "S|segment number assignment~see KST, maintenance"
to no segment and therefore have no entry pointer associated with them.  The
free_range entry walks the KST entry's for the segments to be released.  The
.ifi hit "K|KST~maintenance~segment number assignment"
first pass makes sure that no segment number is not reserved or has had a
segment assigned to it.  The second pass down these segment numbers frees
them.  initialize_region is used by makeknown_ to free up more KST entries.
The KST is initialized to free entries a few at a time, to avoid paging.
.ifi hit "K|KST~maintenance~256K enable"
set_256K_switch sets the value kst.allow_256K_connect.  The only trick is
.ifi hit "K|setfaults"
that, if the 256K enable switch is being turned off, setfaults must run over
the segment.  unthread_kste unthreads a KSTE from its list.  If the entryp is
0, this must be unthreaded from the free list.  Otherwise, it is unthreaded
from its hash class list.

     kstsrch follows the KST hash threads to look up a KST entry pointer (and
.ifi hit "K|kstsrch"
hash value) for an object, given its UID.

     private_logical_volume
.ifi hit "K|private_logical_volume"
maintains the per-process list of private logical volumes attached to the
process.  This list is found in the KST, after the KST entries.  Connecting
and disconnecting to a logical volume is a simple matter of adding the LV to
this list.  Upon disconnecting, though, all segments on that LV must be
setfaulted, to prevent further use.

     set_kst_attributes performs phcs_ and hphcs_ setting of privileged
.ifi hit "K|set_kst_attributes"
segment use attributes in a KST entry.  phcs_ users can set allow_write,
explicit_deact_ok, tpd (transparent paging device (obsolete)) and audit
.ifi hit "K|transparent usage/modification"
(obsolete).  hphcs_ users can also set tms and tus (transparent modify/usage).
Changing the allow_write attribute is also reflected in the SDW
.ifi hit "K|setfaults"
via a setfaults$disconnect.
.ifi l1h "KST Garbage Collection"
     The KST, at any given time, has a certain size.  At a given time, it can
.ifi hit "K|KST~garbage collection"
be viewed as being divided into two parts, that set of active KST entries,
corresponding to known segments, and the list of free KST entries.  As
segments are made known, they are given free entries.  As they are made
unknown, their entries are put back into the free list.  The system, as a
whole, is expected to clean up after itself so that the KST doesn't fill up
with unneeded segments.

     If the KST does fill up, it is grown.  (The KST is not allocated full
size initially, for historic reasons, to limit the page size of the KST.)  The
KST can be grown just so large, not only because the hardware supports just so
many segment numbers, but also because the KST size is limited
administratively.  If the KST really fills completely, attempts to make
further segments known will fail.

     This limitation can become a problem with respect to directories.  Most
.ifi hit "K|directory~making unknown"
.ifi hit "K|making unknown~directories"
directories within the address space have zero usage counts in all rings and
would therefore normally qualify to be made unknown.  (Directories with known
inferior segments, of course, must remain known.)  Directory control purposely
does not make unknown directories when it is done with them.  This is done for
efficiency.  Not only does this avoid the (relatively small) cost of making
the directory unknown (and freeing its KST entry), but, making a directory
.ifi hit "K|PAM"
unknown requires removing it from the PAM.  The PAM is crucial to the
performance of the process, and keeping as many directories in it as possible
is important.  So, the process' address space contains many directories that
are no longer needed.  These start to accumulate.

     Recognizing this, if an attempt to ask for a new KST entry fails because
there are no more free entries, a garbage collection process is performed to
free some of the stray directories' KST entries.  This process is implemented
.ifi hit "K|kst_util"
by kst_util$garbage_collect.  It looks at all KST entries for potential free
candidates.  It does not free a KST entry that is free or whose corresponding
segment has outstanding initiates in any ring or which has any active
inferiors.  The others it frees.  When a directory is freed, its parent may
become freeable as a result.  Success at freeing a directory, then, lead to an
attempt to free the parent.
.brp


                                          -----------------------------------------------------------


Historical Background

This edition of the Multics software materials and documentation is provided and donated
to Massachusetts Institute of Technology by Group BULL including BULL HN Information Systems Inc. 
as a contribution to computer science knowledge.  
This donation is made also to give evidence of the common contributions of Massachusetts Institute of Technology,
Bell Laboratories, General Electric, Honeywell Information Systems Inc., Honeywell BULL Inc., Groupe BULL
and BULL HN Information Systems Inc. to the development of this operating system. 
Multics development was initiated by Massachusetts Institute of Technology Project MAC (1963-1970),
renamed the MIT Laboratory for Computer Science and Artificial Intelligence in the mid 1970s, under the leadership
of Professor Fernando Jose Corbato. Users consider that Multics provided the best software architecture 
for managing computer hardware properly and for executing programs. Many subsequent operating systems 
incorporated Multics principles.
Multics was distributed in 1975 to 2000 by Group Bull in Europe , and in the U.S. by Bull HN Information Systems Inc., 
as successor in interest by change in name only to Honeywell Bull Inc. and Honeywell Information Systems Inc. .

                                          -----------------------------------------------------------

Permission to use, copy, modify, and distribute these programs and their documentation for any purpose and without
fee is hereby granted,provided that the below copyright notice and historical background appear in all copies
and that both the copyright notice and historical background and this permission notice appear in supporting
documentation, and that the names of MIT, HIS, BULL or BULL HN not be used in advertising or publicity pertaining
to distribution of the programs without specific prior written permission.
    Copyright 1972 by Massachusetts Institute of Technology and Honeywell Information Systems Inc.
    Copyright 2006 by BULL HN Information Systems Inc.
    Copyright 2006 by Bull SAS
    All Rights Reserved