.ifi init_plm "FS-00"
.srv draft ""
.srv draft_date ""
.srv section %Arg1%
.pdl 66
.ifi l0h "Directory Locks and Locking"
     The locking of directories is essential to the operation of directory
control.  Locking a directory prevents other processes from modifying the
directory while it is being manipulated.  Likewise, the unlocking of
directories is essential, when the manipulations are done, so that other
processes may access the directory.
.ifi l1h "Types of Directory Locks"
     A directory may be locked for reading or writing.  Directory locks are
.ifi hit "K|directory~locks~types"
multiple reader/single writer locks.  

     A directory locked for reading allows other processes to similarly lock
the directory for reading.  Also, when locking for reading, other processes
.ifi hit "K|directory~locks~read"
may hold the directory locked for reading and it will not be necessary to wait
for them to release their locks.  It is not allowed to modify a directory when
it is locked for reading.

     A directory locked for writing does not allow any other process to hold
.ifi hit "K|directory~locks~write"
any type of lock on the directory.  With a write lock, the process is free to
modify the directory.  When setting a write lock, it will be necessary to wait
until all other processes release their locks before the directory can be
locked.  Also, after locking the directory, other processes will have to wait
until the lock is released before they can lock the directory.  Write locks
are therefore more costly, generally, than read locks.
.ifi l1h "Directory Locking Rules"
     Directory locks are below the AST lock, as described under segment
.ifi hit "K|directory~locks~rules"
activation below.  Directory locks are wait locks; the event is the UID of the
directory.

     The locking hierarchy for directory locks follows the hierarchy.  That is,
.ifi hit "K|directory~locks~hierarchy"
if it is necessary to lock a series of directories, it is necessary to lock a
son directory before locking its parent.  This is necessary so that
sum$getbranch works correctly.  Thus, if a directory is locked and it is
necessary to lock a son, it is required to unlock the parent, lock the son,
then relock the parent.  Some validity check must then be made to ensure
that the parent or the process' access has not changed in the meanwhile.
.ifi l1h "Directory Locking Mechanism"
     Directory locks are maintained by the program lock.  They are maintained
.ifi hit "K|directory~locks~mechanism"
in the segment dir_lock_seg.  dir_lock_seg is protected by its own lock.  The
dir_lock_seg lock is a wait lock.  Its event is DIR_LOCK_SEG_EVENT, the ASCII
string "drls" (octal 144162154163).  It is below any directory lock, with
respect to locking a directory.  It is important to note that the directory
locks are not kept in the directories themselves.  It is necessary to go to
dir_lock_seg to find them.  This does have the advantage, though, that the set
of locks held by a process is immediately available.

     Directories are locked on the basis of their UID's.  This provides an
easy way to scan dir_lock_seg to see if the directory in question is already
locked.
.ifi l2h "Structure of dir_lock_seg"
     dir_lock_seg contains the list of all directories in the system that are
.ifi hit "K|directory~locks~dir_lock_seg"
.ifi hit "S|dir_lock_seg~see directory, locks, dir_lock_seg"
currently locked, including the list of all processes holding a lock on those
directories.  dir_lock_seg is described by dir_lock_seg_.incl.pl1.

.inl +5
.unl +5
dir_lock_seg.header.seg_lock
.brf
a standard hardcore lock (process id, event and notify switch)
.unl +5
dir_lock_seg.header.n_dir_locks
.brf
the maximum number of directory locks that could be held.  This is the maximum
number of eligible processes (since any process holding a directory lock must
be in ring 0 and therefore can't lose eligibility) times the maximum number of
locks a process could hold (maximum tree depth).
.unl +5
dir_lock_seg.header.highest_in_use
.brf
the highest dir_lock cell in use.
.unl +5
dir_lock_seg.header.max_readers
.brf
the maximum readers a directory can have.  This is the maximum number of
eligible processes.
.unl +5
dir_lock_seg.header.readers_ptr
.brf
points to dir_lock_seg.readers
.unl +5
dir_lock_seg.header.locks_ptr
.brf
points to dir_lock_seg.dir_locks
.unl +5
dir_lock_seg.header.meters.find_calls
.brf
the number of times that an attempt was made to find a lock cell for a given
UID
.unl +5
dir_lock_seg.header.meters.find_failures
.brf
the number of times that a cell for the given UID was not found
.unl +5
dir_lock_seg.header.meters.max_in_use
.brf
the highest value of dir_lock_seg.highest_in_use

.unl +5
dir_lock_seg.dir_locks
.brf
an array of directory locks

.unl +5
dir_lock.uid
.brf
UID of directory being locked.  This value is used as the wait event when
waiting for the lock on this directory.
.unl +5
dir_lock.flags.notify_sw
.brf
TRUE if some process is waiting for notification of the unlocking of this
directory 
.unl +5
dir_lock.flags.salvage_sw
.brf
indicates the directory is locked for salvaging.  This information is of use
to verify_lock.
.unl +5
dir_lock.lock_count
.brf
if positive, this indicates the directory is locked for writing; if negative,
it is the number of directory reads; if zero, the directory is not locked
.unl +5
dir_lock.write_locker
.brf
process id holding the directory locked; if zero, the list of readers appears
in dir_lock_seg.readers

.unl +5
dir_lock_seg.readers
.brf
the array of process ids holding this directory locked
.inl -5
.ifi l2h "Operation of lock"
     The method by which a directory is locked follows.  All
.ifi hit "K|directory~locks~operation of lock"
lockings/unlockings are done with dir_lock_seg locked.  If it is necessary to
wait for a directory lock, dir_lock_seg is unlocked during the wait (as it
must be to allow directories to become unlocked).  After the wait, anything
may have changed so the lock attempt must be completely retried.

     First, a lock cell (dir_lock, above) must be found to describe this
directory.  A run is made looking for a cell that already describes this
directory.  If one is found, fine.  If not, a cell must be created.  This
occurrence counts toward meters.find_failures, above.  Creating a cell either
requires using a free cell (one with a UID of 0) or expanding the dir_locks
array (incrementing highest_in_use (but not higher than n_dir_locks)).

     After this, the obvious locking rules apply.  If the directory is already
locked for reading and a read lock is desired, add this process to the list of
readers.  If the directory is already locked for reading and a write lock is
desired, flag the directory as requiring notification upon unlocking and wait.
If the directory is locked for writing, wait regardless of the type of lock
desired.  Within this logic is various checks for mylock conditions.

     The UID that is locked upon is found from the directory header.  This
value is normally safe to retrieve from the header even with the directory
.ifi hit "K|UID~validation"
unlocked.  However, this value may become damaged.  So, various checks are
made for validity, in particular, that the value matches the UID value in the
KST.  Generally, the KST value (which was derived from the branch within the
.ifi hit "K|directory salvager"
parent) is considered the more accurate.  Indeed, the salvager lock entry uses
the KST value only, and eventually patches this into the directory.  If the
various checks fail, the directory is locked for salvaging, the directory
salvaged, and the desired locking retried.

     Unlocking a directory starts with finding the dir_lock cell for the
directory.  (In this case, it won't be created if not found.) This is done on
the basis of the UID from the directory header.  If this fails, it either
means that the directory wasn't locked or that the directory was trashed.  An
attempt is then made to find the dir_lock cell for the UID given in the KST
entry.  If that succeeds fine.  Otherwise, an assumption is made that the
directory was not locked.

     The dir_lock cell is then marked as unlocked (to this process).  If the
directory was locked for writing, clear the dir_lock cell and notify if the
notify flag was on.  If the directory was locked for reading, decrement the
reader count.  If the count becomes zero, notify if the notify flag was on and
clear the dir_lock cell.  (If the cell to be cleared was the last cell,
decrement highest_in_use.)

     Between the finding of the dir_lock cell for unlocking and the actual
unlocking of this cell, the write behind check is made.  (The write behind
mechanism is turned on by the DIRW config parameter.  It causes directories to
be force written after modifications.) The ASTE pointer is found for the
directory, without locking the AST.  Page control is called to force write the
directory, given the known UID.  (Page control checks this UID against that of
the ASTE under the page table lock, thus removing the need to have the AST
.ifi hit "K|directory write behind"
.ifi hit "S|dirw~see directory write behind"
locked during this time.  If the ASTE is not free and the UID's match, the
force write is done.) If the file map changed flag is on, the VTOCE must also
be force written.  In this case, the AST must be locked.  Under the AST lock,
a check is made to ensure that this ASTE still describes the directory (the
UID's match).  If so, vtoc_man (update_vtoce) is used to update the VTOCE from
the ASTE.  This force writing is done holding the directory locked, as it must
to avoid further modifications, but without holding the dir_lock_seg lock.
The dir_lock_seg must be relocked after force writing so as to be able to
unlock the directory.
.ifi l1h "Special Uses and Rules for Directory Locks"
     Various programs lock directories in special ways.  The non-obvious ways
in which directories must be locked to obtain the desired effect is the
subject of this sub-section.
.ifi l2h "Segment Activation "
     The module seg_fault needs access to directory entries in order to obtain
.ifi hit "K|directory~locks~effect on connection"
the necessary information to activate a segment.

     If a directory is locked for reading, a segment immediately subordinate
to that directory can be activated, since seg_fault will succeed in getting
the read lock it wants.  If the directory is locked for writing, no
immediately subordinate segments can be activated.

     Note also that, since touching any directory (or hierarchy segment) can
cause a seg_fault, seg_fault cannot lock any directory (this requiring
touching it) when it has the AST locked.  So, it must lock the directory
containing the entry for the segment to be  activated first, which is why the
AST lock is above the directory locks.
.ifi l2h "Pseudo-Directories"
     Since directories are locked by recording their UIDs in dir_lock_seg,
.ifi hit "K|directory~pseudo"
rather than by any recording within the directories themselves, it is possible
to lock a directory given its UID even if the directory is not known (or
non-existant).  This trick is used to prevent modification to a directory when
it is not even known if the directory exists.  With this scheme, a simulated
directory header is fabricated with the desired UID patched in.  Such a
simulated directory is acceptable to lock.  The volume dumper uses this trick
when activating a segment whose relationship to the hierarchy is unknown.  The
volume retriever uses it when referencing a potentially non-existant object.
priv_delete_vtoce also uses this for potentially non-existant segments, where
locking the pseudo-parent avoids problems with other processes.
.ifi l1h "Directory Lock Salvaging"
     When a process crawls out of ring zero as the result of a fault therein,
.ifi hit "K|directory~locks~salvaging"
verify_lock is called to make sure the process doesn't leave any locks left
locked.  Relative to the file system, this involves unlocking all directory
locks held.

     The internal routine VERIFY_DIRECTORIES within verify_lock walks down all
of the directory locks.  For any directory found locked to this process, the
identity is added to an internal array by the internal routine VERIFY_DIR,
which finds the directory and checks the modify field in its header.  The
.ifi hit "K|directory salvager"
routine SALVAGE_DIRECTORIES calls the on_line_salvager for each directory in
this list, under protection of the dir lock (for salvaging) and an any_other
handler.
.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