.ifi init_plm "FS-00"
.srv draft ""
.srv draft_date ""
.srv section %Arg1%
.pdl 66
.ifi l0h "Directory Control Primitives"
     Some of the various operating programs and utilities within directory
control are described in this section.  Certain modules within directory
control are described elsewhere.  In particular, the reader should refer to
the section on dc_find and access control and the section on directory control
mechanisms for further details of the internal operation of directory control.
.ifi l1h "Pathname to Entry Translation"
     dc_find performs all pathname to entry translations, as described under
.ifi hit "K|pathname to entry translation"
"mechanisms".  Since all such requests correspond to a user request for an
operation upon an entry, all such translations must have some associated
access check required.  As such, it is required that all pathname to entry
translations be done by dc_find so that the corresponding operation upon the
entry is validated and audited.

     The locating of a directory by dc_find was discussed under file system
mechanisms.  The locating of a directory entry is also done within dc_find.
.ifi hit "K|directory~entry~locating"
As mentioned under mechanisms, the find_entry routine within dc_find locates a
given directory entry given a four bit string, where each bit specifies that
the desired name should be a segment, directory, link or nothing
(non-existant).

     In the normal non-chase case, find_entry is asked to find an entry that
is a segment, directory or link.  The caller of dc_find decides what to do
with the type of object found.  In the normal chase case, find_entry is also
.ifi hit "K|link chasing"
called to find a segment, directory or link.  However, if a link is found, the
link pathname is extracted, the directory holding the link unlocked, and a new
search started.  This link chasing only proceeds so far, of course.

     In the process of finding a directory, find_entry is told to find either
a directory or a link.  If a link is found, the link chasing mechanism
described under file system mechanisms is used.

     For the link target lookup function, find_entry will find anything.  If a
.ifi hit "K|link target"
link is found, it is chased.  If nothing is found, though, the caller will
know the name of the directory in question, and the entryname that was under
search which would be returned to the user.  This function must enforce the
name lookup policy against this directory.

     For the non-chase append function, find_entry is told to accept only
.ifi hit "K|creation"
nothing.  For the append through link function, find_entry will accept a link
or nothing; it will chase a link if found.

     The obscure use of find_entry is in the initiate function for the dynamic
linker.  In this case, the linker has provided a directory pointer and a name
to find.  However, the name may be a link.  So, find_entry would want to find
.ifi hit "K|dynamic linker"
a segment or link.  However, making a restrictive request like this would
cause find_entry to enforce the name lookup policy if the name weren't found,
.ifi hit "K|name lookup policy"
an undesirable event for the linker (as explained under access control).  So,
find_entry is told to find anything.  If it returns a link, it is chased.  If
it returns a branch, fine.  This is returned to the caller.  If nothing is
found, the caller simply gets error_table_$no_info.
.ifi l1h "Segment Pointer to Entry Translation"
     The translation of a segment pointer into the corresponding entry pointer
.ifi hit "K|segment pointer to entry translation"
is done by sum (segment utility module).  This function is used internal to
.ifi hit "K|sum"
many file system primitives to locate the directory entry corresponding to the
parent of a given directory, or the parents' parent, etc.  However, the
translation of a given user segment pointer into the corresponding entry must
have some associated access check; as such, the only allowed caller of sum
given a user supplied segment pointer must be dc_find.  (The sole exception is
seg_fault.  seg_fault calls sum itself, passing the result to dc_find.  This
.ifi hit "K|connection"
is true because the call to sum on a non-active segment may itself take a
segment fault upon the parent; seg_fault takes the recursive segment fault
because its stack frame is much smaller than that of dc_find.  It is still
true that dc_find will enforce the name lookup policy with respect to
translating the user supplied pointer (the fault location) into an entry.)

     The getbranch entry of sum takes a segment pointer and returns a pointer
to the directory entry for the segment.  This is easily possible by use of the
entryp field within the KST entry for the segment.  sum uses the segment
number to find the KST entry for the segment, uses the KST entry to find the
parent directory pointer and then locks the directory as specified by the
caller (as is indeed necessary to keep the returned entry pointer valid).  The
getbranch_root_my entry differs in two ways.  First, when supplied the root as
an argument, it returns error_table_$root as opposed to error_table_$noentry.
Also, it tolerates being called when the parent directory is locked (rather
than crashing with a mylock error).  In this case, it returns the
error_table_$mylock, so the caller knows enough not to unlock the parent
directory (until the program that did lock it unlocks it).

     As mentioned under the description of the KST, the entryp field in the
KST entry points to the directory entry for the segment.  However, since the
directory is not kept locked during process operation, this entryp is not
guaranteed to be valid.  First of all, the segment may be deleted.  Secondly,
.ifi hit "K|directory salvager~compactor"
the directory can be salvaged, and the directory compactor can move directory
entries around.  So, the entryp in the KST entry must be made valid.  This is
.ifi hit "K|validate_entryp"
done by the internal routine validate_entryp within sum.

     validate_entryp starts by assuming the entryp is valid (which it is 99+%
of the time).  Some consistency checks are made against the entryp to see if
it does describe the directory entry desired.  The checks ensure that the UID
within the entry matches that of the KST entry, that the entry claims to
belong to a segment or directory, that the primary name entry's owner is the
same UID (this double check for UID of two fields that are both within the
entry is to remove possible confusion between a directory element that
corresponds to the entry (has the same UID) but is not the entry itself), and
that the branch switch is set (this check ensures that the supposed entry is
not a link pathname, since users can only supply ASCII pathnames, and no ASCII
pathname can set the branch switch (high order bit in a word)).  If these
checks fail, the directory entry must be found.  This is a simple matter of
walking down the directory entries looking for the segment's UID.  If the
object can't be found, it must have been deleted.  error_table_$seg_deleted is
returned.  It is a rule of the name lookup policy that all callers of sum who
pass in a user supplied pointer must filter this error code.  As such, the
only caller of sum who is allowed to have this condition occur (that the
requested segment was deleted) is dc_find.  This must certainly be true, since
only dc_find is allowed to take a user supplied pointer (via a user ring or
fault side call) and attempt to map it into a directory entry, while
performing required access checks.
.ifi l1h "UID Path to Entry Translation"
     uid_path_util within dc_find performs the mapping of a UID pathname into
an entry.  This function is intended for use by master directory control.  The
.ifi hit "K|UID path to entry translation"
operation was described under "mechanisms".  Again, it follows that a user
request for such a translation implies an operation upon the entry; this is
why this function is contained solely within dc_find so that security policies
may be enforced.
.ifi l1h "Security Functions"
     The principle security related function within hardcore is imbedded in
.ifi hit "K|security policy~enforcement"
.ifi hit "K|dc_find"
.ifi hit "S|dc_find~see also security policy"
dc_find.  This module makes all security decisions within ring zero.  It
performs all security related auditing.  Its operation is described in the
.ifi hit "S|access control~see security policy"
section on access control.

     The master module for determining access to objects is access_mode.  It
.ifi hit "K|access_mode"
computes the access the process would have to a given object (access mode and
extended access mode of a segment), given a pointer to the directory entry for
the segment.  It comes in three flavors/entries: raw (compute access on base
of ACL only), authorization (factor in AIM) and effective (access including
ring).  It also has the entrypoints user, which computes raw access given a
user name (group id), and the entrypoint user_effmode which computes effective
access given a user name, authorization and ring number.  The operation of
this routine, as well as the implications of its use, can be found in the
section on access control.

     change_dtem changes the dtem (date-time entry modified) field for an
entry in a directory.  This function is part of the process of performing a
.ifi hit "K|change_dtem"
setfaults on a segment, and is the equivalent of setfaults when applied to a
directory.  The description of this mechanism appears in the section on access
control.

     check_gate_acl_ checks the ACL on a gate.  The restrictions on the ACL of
.ifi hit "K|check_gate_acl_"
a gate appears in the section on access control.

     update_kste_access is called by fs_modes and dc_find when it is
.ifi hit "K|update_kste_access"
.ifi hit "K|fs_modes"
discovered that the access information in the KST entry is out of date.  For
directories, this consists of copying the entry's extended ring brackets
(courtesy of access_mode$authorization) and dtbm.  (For the root, the ring
brackets are 7, 7 and the dtbm is 0.) For segments, it copies the ring
brackets and dtbm via access_mode$authorization (access_modes$raw if the
segment was priv init).
.ifi l1h "ACL Term Manipulation"
     Matching of a group id against an ACL list is performed in two places.
.ifi hit "K|ACL~directory structure"
access_modes, which needs to be performant with respect to ACL matching,
performs its own ACL scan.  This scan is simplified by the fact that the group
id for which it is matching is fully qualified (has no "*" components).  When
the group id to match against an ACL is of free form (potentially some "*"
.ifi hit "K|acc_list_"
components), the matching is done by acc_list_.  The calling sequence for
acc_list_ returns an ACL term pointer for any match, but a zero error code
only for an exact match.  This error code is used by ACL listing primitives.

     The standard low-level operations upon an ACL are performed by acl_.  It
.ifi hit "K|acl_"
can list, delete and add a term to an ACL, and separately delete an entire
ACL.  It operates only on the ACL; the entry must be updated (including ACL
term counts) by the caller.

     The list_entry entrypoint looks for a particular ACL term.  It can be
called in one of two ways, to either match a given group id or to find the ith
ACL term.  When called to match a group-id, it is given an acl_entry
structure.  acc_list_$match finds the desired ACL term.  The modes from this
term are copied into the caller's acl_entry structure, thus giving the caller
.ifi hit "K|directory~structure~access names"
the desired information.  When called to find the ith ACL term, it walks down
the ACL term list i times.  In this case, the modes are copied out as before,
but the various pointers in the access_name structure must be followed to get
the access names.

     del_entry deletes a term from an ACL.  acc_list_$match finds the desired
.ifi hit "K|acc_name_"
term.  acc_name_$delete deletes (dereferences) the access names in the term.
The acl_entry structure is unthreaded from the ACL term list and itself freed
(by fs_alloc$free).

     del_acl deletes the entire ACL.  It walks down the ACL, deleting the
access_name structures (acc_name_$delete) and the acl_entry structures
(fs_alloc$delete).  The forward and backward pointers to the ACL are zeroed.

     add_entry adds an ACL term to an ACL.  It uses acc_list_$match to
determine where in the ACL this ACL term should go.  If acc_list_$match finds
the ACL term, only the modes are changed in the acl_entry structure.
Otherwise, an acl_entry must be allocated (fs_alloc$alloc) and threaded into
the ACL and filled in.
.ifi l1h "Directory Space Management"
     The contents of a directory were described in the section describing the
directory structure.   The manipulation of the various entries, as well as the
manipulation of the ACLs is described elsewhere.

     fs_alloc is the keeper of the area that is a directory.  It is
.ifi hit "K|fs_alloc"
.ifi hit "K|directory~structure~allocation area"
effectively a simplified and more efficient version of the general area
allocation/freeing mechanisms.  The init entry marks the entire area as free,
with no entries of any given size allocated.  alloc first checks for a free
entry of the desired size, and, if not found, allocates a new one in the
previously un-allocated area at the end.  free returns the specified entry to
the pool corresponding to that size.
.ifi l2h "Access Name Manipulation"
     The access_name structures within a directory are maintained by
.ifi hit "K|acc_name_"
acc_name_.  It is the keeper of the threads for access_name structures.  It has
entrypoints to add (encode), delete and lookup (get) an access_name from/to a
group id.
.ifi l2h "Hash Table Manipulation"
     The hash table within a directory is maintained by hash.  hash performs
the usual hash functions.  There are two interesting
.ifi hit "K|directory~structure~hash table"
.ifi hit "K|hash"
aspects of this routine.  It checks the names to be hashed for valid ASCII.
Also, if the number of hashed names exceeds the size for the hash table in the
directory, the directory is rehashed.  A new hash table is obtained, the old
one freed, and the names rehashed for this new table.  This operation is done
under the protection of the bit dir.rehashing.  hash honors this bit; when
.ifi hit "K|directory salvager"
.ifi hit "K|directory~rehashing"
found on for a directory (result of a crash) the directory must be salvaged.

     allocate_dir_ht_ allocates directory hash tables.  It takes an argument
.ifi hit "K|allocate_dir_ht_"
specifying how many names to be considered when choosing a hash table size.
This value is normally zero but is used by hash, when growing the hash table.
Given this number of names, a proper size hash table is created.  The area for
this is obtained (fs_alloc$alloc).  The hash table header is filled in and the
directory header changed to indicate this new hash table.
.ifi l1h "Usage of dc_find"
     File system primitives must call dc_find to locate a directory or a
.ifi hit "K|dc_find~usage"
directory entry, so that the system's security policy is enforced.  As such,
most file system primitives consist of a call to dc_find to find the desired
.ifi hit "K|directory~releasing"
entry or directory, code to manipulate this entry, and a call to release the
directory or entry found.

     The file system primitive must call the dc_find entrypoint that
corresponds to the type of access required for the file system function at
hand.  The correct read versus write entrypoint must be called.  Note that
most write entrypoints take as an argument an access operation sub-operation
code (defined in fs_obj_access_codes.incl.pl1) needed to audit the operation.
The returned code will be zero only if the operation is granted.  Otherwise,
the returned pointers will be null, and an attempted access violation would
have been audited.

     When the file system operation is done, the directory must be unlocked
and released (dereferenced).  For dc_find pointer functions, the directory is
not dereferenced because it was not referenced (usage count incremented) when
sum found it, since the directory was guaranteed to be known and inferior
segment held.

     As such, the standard code fragment involving dc_find follows.

.fif
file_system_primitive$path: entry (path, code);

          call dc_find$foo (path, ep, code);
          if code ^= 0 then return;
          locked = "1"b;
          called_find = "1"b;
          go to common;

file_system_primitive$ptr: entry (ptr, code);

          call dc_find$foo_ptr (ptr, ep, code);
          if code ^= 0 then return;
          locked = "1"b;
          called_find = "0"b;

common:   dp = ptr (ep, 0);

       <manipulate entry here>

          if called_find then 
               call dc_find$finished (dp, DC_FIND_UNLOCK_DIR);
          else call lock$dir_unlock (dp);
          return;
.fin
.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