MULTICS DESIGN DOCUMENT MDD-006-01
To: MDD Distribution
From: Gary C. Dixon
Date: April 28, 1986
Subject: Multics File System
Abstract:
Internal Organization of the Directory Control and the Address
and Name Space Management functions within the Multics system.
Revisions:
REVISION DATE AUTHOR
initial 85-07-01 Keith Loepere
01 86-04-27 Gary C. Dixon |
_________________________________________________________________
Multics Design Documents are the official design descriptions of
the Multics Trusted Computing Base. They are internal documents,
which may be released outside of Multics System Development only
with the approval of the Director.
i
MDD-006 Multics File System
CONTENTS
Page
Section 1 Introduction . . . . . . . . . . . . . . 1-1
Section 2 Directory Structures . . . . . . . . . . 2-1
2.1 Directory Header . . . . . . . . . 2-1
2.2 Directory Allocation Area . . . . 2-3
2.3 Directory Entries . . . . . . . . 2-3
2.4 Entry Names . . . . . . . . . . . 2-6
2.5 Hash Table . . . . . . . . . . . . 2-6
2.6 ACL and Access Names . . . . . . . 2-7
2.7 Example . . . . . . . . . . . . . 2-10
Section 3 Directory Locks and Locking . . . . . . . 3-1
3.1 Types of Directory Locks . . . . . 3-1
3.2 Directory Locking Rules . . . . . 3-1
3.3 Directory Locking Mechanism . . . 3-2
3.3.1 Structure of dir_lock_seg . . 3-2
3.3.2 Operation of lock . . . . . . 3-3
3.4 Special Uses and Rules for
Directory Locks . . . . . . . . . . . 3-5
3.4.1 Segment Activation . . . . . 3-5
3.4.2 Pseudo-Directories . . . . . 3-5
3.5 Directory Lock Salvaging . . . . . 3-6
Section 4 File System Mechanisms . . . . . . . . . 4-1
4.1 Locating and Holding Directories
and Directory Entries . . . . . . . . 4-1
4.1.1 Locating Directories . . . . 4-1
4.1.2 Locating Directory Entries . 4-3
4.1.3 Keeping Valid Directory and
Entry Pointers . . . . . . . . . . 4-4
Keeping Directories from being
Terminated . . . . . . . . . . 4-4
Keeping Directories from being
Modified . . . . . . . . . . . 4-5
4.1.4 The Pathname Associative
Memory (PAM) . . . . . . . . . . . 4-6
Usage of the PAM . . . . . . . . 4-6
Operation of the PAM . . . . . . 4-6
4.1.5 Summary . . . . . . . . . . . 4-8
ii
Multics File System MDD-006
CONTENTS (cont)
Page
4.2 Re-locating Directories and
Directory Entries . . . . . . . . . . 4-8
4.2.1 Re-validating Directory Entry
Pointers . . . . . . . . . . . . . 4-9
4.2.2 Validating Directory Contents 4-9
4.2.3 Return Area Management . . . 4-9
4.2.4 Summary . . . . . . . . . . . 4-10
4.3 Modifying Directories . . . . . . 4-12
4.3.1 Signalling that a
Modification is in Progress . . . 4-12
4.3.2 Recording Access and
Attribute Changes - dtem . . . . . 4-12
4.3.3 Recording Directory Contents
Modified - dtcm . . . . . . . . . 4-12
Section 5 Access Control - dc_find . . . . . . . . 5-1
5.1 Basic Security Model . . . . . . . 5-1
5.1.1 Basic Access Catagories . . . 5-2
Contents Properties . . . . . . 5-2
Status Properties . . . . . . . 5-3
Attribute Properties . . . . . . 5-3
5.2 Access Computations . . . . . . . 5-3
5.3 Known Segment Access Maintenance . 5-5
5.4 Access Manipulation . . . . . . . 5-6
5.5 AIM File System Privilege . . . . 5-6
5.6 Attempted Access Violations
Auditing Policy . . . . . . . . . . . 5-7
5.7 Name Lookup Policy . . . . . . . . 5-8
5.8 Successful Access Audit Policy . . 5-9
5.9 Detailed Security Policy . . . . . 5-9
5.9.1 Access Mode Restrictions . . 5-9
5.9.2 Gate ACL restrictions . . . . 5-10
5.9.3 Directory Contents Getting . 5-10
Access Class Check . . . . . . . 5-10
IACL Listing . . . . . . . . . . 5-10
Examining a Sub-tree for
Deletion . . . . . . . . . . . 5-10
Directory Entry Listing . . . . 5-10
Quota Getting . . . . . . . . . 5-11
5.9.4 Directory Contents Setting . 5-11
IACL Setting . . . . . . . . . . 5-11
5.9.5 Object Contents Setting . . . 5-11
Bit Count Setting . . . . . . . 5-11
Segment Truncation . . . . . . . 5-11
5.9.6 Status Property Getting . . . 5-12
ACL Listing . . . . . . . . . . 5-12
Name Listing . . . . . . . . . . 5-12
iii
MDD-006 Multics File System
CONTENTS (cont)
Page
5.9.7 Status Property Setting . . . 5-12
ACL Setting . . . . . . . . . . 5-12
Ring Bracket Setting . . . . . . 5-12
File System Object Renaming . . 5-13
File System Object Deleting . . 5-13
Miscelaneous Properties . . . . 5-13
5.9.8 Attribute Property Setting . 5-13
5.9.9 Attribute Property Getting . 5-13
Ring Bracket Getting . . . . . . 5-14
Miscelaneous Properties . . . . 5-14
5.9.10 File System Object Appending 5-14
5.9.11 Initiated Segment Attributes 5-14
5.9.12 Link Target Chasing . . . . 5-14
5.9.13 Working Directory and Search
Rule Setting . . . . . . . . . . . 5-15
5.9.14 Segment Initiation . . . . . 5-15
Dynamic Linking . . . . . . . . 5-15
5.9.15 Segment Termination . . . . 5-15
5.9.16 Master Directory Quota
Setting . . . . . . . . . . . . . 5-16
5.9.17 Quota Moving . . . . . . . . 5-16
5.9.18 Object Reclassification . . 5-16
5.9.19 Node Reclassification . . . 5-16
5.9.20 Volume Retrieving . . . . . 5-16
5.9.21 Segment Connection . . . . . 5-17
5.9.22 Gate Definition Getting . . 5-17
Section 6 Directory Control Primitives . . . . . . 6-1
6.1 Pathname to Entry Translation . . 6-1
6.2 Segment Pointer to Entry
Translation . . . . . . . . . . . . . 6-2
6.3 UID Path to Entry Translation . . 6-3
6.4 Security Functions . . . . . . . . 6-4
6.5 ACL Term Manipulation . . . . . . 6-4
6.6 Directory Space Management . . . . 6-5
6.6.1 Access Name Manipulation . . 6-6
6.6.2 Hash Table Manipulation . . . 6-6
6.7 Usage of dc_find . . . . . . . . . 6-6
Section 7 Data Structures within Address and Name
Space Management . . . . . . . . . . . . 7-1
7.1 The KST . . . . . . . . . . . . . 7-1
7.1.1 KST Entries . . . . . . . . . 7-2
7.2 The RNT . . . . . . . . . . . . . 7-3
7.2.1 RNT Entries . . . . . . . . . 7-4
Section 8 Address and Name Space Management . . . . 8-1
iv
Multics File System MDD-006
CONTENTS (cont)
Page
8.1 Segment Initiation/Making Known . 8-1
8.2 Segment Usage Counts . . . . . . . 8-3
8.3 Segment Termination/Making Unknown 8-3
8.4 Reference Name Manipulation . . . 8-4
8.5 Functions for Directory Control . 8-4
8.5.1 Segment Pointer to Pathname
Translation . . . . . . . . . . . 8-5
8.6 KST Maintenance Functions . . . . 8-5
8.7 KST Garbage Collection . . . . . . 8-6
Section 9 File System Primitives . . . . . . . . . 9-1
9.1 AIM Related Primitives . . . . . . 9-1
9.1.1 Access Class Checks . . . . . 9-1
9.1.2 Access Class Setting . . . . 9-1
9.2 ACL Primitives . . . . . . . . . . 9-2
9.2.1 Old-style Primitives . . . . 9-3
9.2.2 New-style Primitives . . . . 9-3
9.3 Ring Bracket Primitives . . . . . 9-5
9.4 Name Listing . . . . . . . . . . . 9-5
9.5 File System Object Creation . . . 9-6
9.6 File System Object Renaming . . . 9-7
9.7 File System Object Deletion . . . 9-8
9.7.1 Sub-tree Deletion . . . . . . 9-9
9.8 Property Getting Primitives . . . 9-10
9.9 Segment Initiation . . . . . . . . 9-11
9.10 Segment Termination . . . . . . . 9-11
9.11 Dynamic Linker Support . . . . . 9-11
9.12 Property Setting Primitives . . . 9-13
9.13 Segment Truncation . . . . . . . 9-13
9.14 Quota Primitives . . . . . . . . 9-14
9.15 Miscellaneous Functions . . . . . 9-15
9.15.1 Quota Correction . . . . . . 9-15
9.15.2 Root Directory Creation . . 9-15
9.15.3 Dump Copying . . . . . . . . 9-16
9.15.4 Segment Moving . . . . . . . 9-16
9.15.5 Volume Retriever/Dumper . . 9-16
Volume Dumper . . . . . . . . . 9-16
Volume Retriever . . . . . . . . 9-17
9.15.6 Privileged Versions of
Operations . . . . . . . . . . . . 9-18
9.15.7 Set Sons LVID . . . . . . . 9-18
9.15.8 Disk Table Location . . . . 9-19
9.15.9 Temp Wiring . . . . . . . . 9-19
9.15.10 UID Path Utilities . . . . 9-19
Appendix A Glossary . . . . . . . . . . . . . . . . A-1
v
Multics File System MDD-006
SECTION 1
INTRODUCTION
The Multics subsystems of directory control and of address and
name space management are two intermingled subsystems within the
Multics supervisor. Together with the file system primitives,
they are referred to as the file system portion of the Multics
supervisor. They form the major user visible portion of the
Multics supervisor, as far as the user's access to the hierarchy
and the formation of the user's address space is concerned. Both
of these subsystems are discussed in this MDD, with an attempt to
separate their functions for discussion purposes.
Directory control is that portion of the system that concerns
itself with the structuring of the file system into directories
and segments and controlling access to those objects. It also
maintains the description of the access to segments (whose access
control is actually in the hardware). It lies logically above
segment and page control, using their facilities to access the
contents of directories as if they were normal segments.
Directory control is not strictly above segment control, of
course, since segment control does thread ASTEs together relative
to the hierarchy structure. (That is to say, segment control
knows the difference between directories and segments.) Segment
control has a path into directory control to compute access modes
for the segments' SDWs and to audit successful granting of access
as well as attempted access violations to the contents of the
segments it controls.
Address and name space management is that portion of the system
that concerns itself with the introduction into, and the removal
from, a user's address space of file system objects (segments and
directories). Also, it maintains the names by which these
objects are known within the process. That is, it maintains the
reference names for these objects, as well as maintaining the
correlation between the identity within the address space of an
object (its segment number) and the pathname of the object.
Directory control lies under address and name space management,
in that this latter subsystem uses directory control to find and
determine access to objects. Directory control is not strictly
1-1
MDD-006 Multics File System
under address and name space management in that directory control
must bring various directories into the user's address space just
to reach them (walking down the hierarchy or when chasing links).
These extra directories enter the user's address space but not
strictly the user's name space.
The functions attributed to address and name space management
include maintaining the known segment table (KST) for the process
and the reference name table (RNT) for each ring. Included
within maintaining the KST is the task of making segments known
(bringing them into the address space, i.e., assigning them a
segment number) and making them unknown and keeping track of
assigned segment numbers.
The functions attributed to directory control are the following.
Directory control locates directories and specific entries within
those directories. It determines users' access to the
directories or entries at hand and audits attempted access
violations, if necessary. If access is allowed, the calling file
system primitive will perform its operation on the directories or
the directory entries. These operations consist of file system
object creation, deletion, and the getting and setting of the
properties of these objects.
1-2
Multics File System MDD-006
SECTION 2
DIRECTORY STRUCTURES
The structure of directories is the subject of this section. At
its simplest, a directory consists of a list of entries, each
describing a file system object (segment, directory or link).
Each of these entries possesses a list of names by which the
entry is known. Entries describing a branch have an ACL. Added
to all of this is a hash table that allows for quick look ups of
a given name. Finally, some compaction techniques are used to
avoid replicating person and project names within the directory.
A directory is divided into a variety of data areas. The upper
half of word 1 of each of these possible data areas is the type
of the data area. This field is used to perform consistency
checks within the various directory control programs and is also
used by the directory salvager. The various values for the type
field are found in fs_types.incl.pl1. The lower half of word 1
of these data areas is the size of the data area in words. For
those data areas that are threaded into lists, word 0 contains a
backward and forward thread, with the forward thread being in the
upper half of the word.
222...111 DDDIIIRRREEECCCTTTOOORRRYYY HHHEEEAAADDDEEERRR
A directory starts out with a directory header (described by
dir_header.incl.pl1). All other entries within the directory are
found from pointers in this header. Various header fields
describe the directory as a whole.
dir.type
the value DIR_HEADER_TYPE (3) to designate this area (which
starts at word 0 of the directory) as the directory header
dir.size
size of the directory header
dir.version_number
the version number of the header, currently 2
dir.modify
the value of the process id of the process currently
modifying this directory. This field is set when a process
2-1
MDD-006 Multics File System
begins a modification sequence and is zeroed at the end of
the sequence. In this way, the on-line salvager
(verify_lock, actually) can easily sense a directory in an
inconsistent state upon a crawlout.
dir.dtc
obsolete
dir.uid
the UID of the directory, copied from the branch. This is
"777777777777"b3 for the root.
dir.pvid
the physical volume id of the directory, copied from the
branch
dir.sons_lvid
the logical volume id for all inferior non-directory
segments created under this directory. It will also become
the sons_lvid for all non-master directories created under
this directory. This field is copied from the directory
branch.
dir.access_class
AIM attributes of the directory, copied from branch
dir.vtocx
the VTOC index of this directory, copied from branch
dir.per_process_sw
indicates that this directory contains per process segments
dir.master_dir
TRUE if this is a master directory
dir.force_rpv
TRUE if segments created under this directory must be on the
RPV
dir.tree_depth
the number of levels from the root of this directory. This
is zero for the root.
dir.dts
the date-time this directory was last salvaged
dir.master_dir_uid
the UID of the superior master directory. This is
"777777777777"b3 for the root.
dir.change_pclock
the directory change pseudo-clock. It is incremented by one
each time the directory is modified (when sum$dirmod is
called). This value is of use to programs that must unlock
a directory between two successive operations. If this
pseudo-clock has the same value upon re-locking as it did
when the directory was last unlocked, the program can be
sure that no change took place to the directory invalidating
the programs' assumptions about the directory's contents.
Refer to directory relocking mechanisms for details.
dir.owner
the UID of the parent directory (used for validity checks).
This is "777777777777"b3 for the root.
2-2
Multics File System MDD-006
222...222 DDDIIIRRREEECCCTTTOOORRRYYY AAALLLLLLOOOCCCAAATTTIIIOOONNN AAARRREEEAAA
Other than the directory header, which always starts at word 0 of
a directory, the rest of the data areas within the directory are
allocated within it. The procedure fs_alloc manages the rest of
the space within a directory as a simplified area. This area is
found from the directory header. It is described by
dir_allocation_area.incl.pl1.
dir.arearp
the relative pointer to the beginning of the allocation area
The area management policy is as follows. A directory, at any
given time, consists of a portion that is threaded into blocks,
followed by an empty portion (not threaded into blocks). Each
block is either used by some purpose (it has a non-zero type
field and is threaded into some list) or is free (and threaded
into a free list). When an attempt is made to allocate a block
within a directory, a check is made for a free block of the
correct size. If one is found, it is used. Otherwise, the
unused area at the end is shortened by creating a new block of
the desired size at the beginning of the unused area. When a
block is freed, it is marked as so and added to the free list of
blocks of that size. Free blocks are not used for any block size
except for the block size for which they were created. Free
blocks are not consolidated, nor the blocks rearranged except by
the directory compactor (within the salvager)
area.nsizes
the number of block sizes available
area.lu
(last used) the next available word offset within the
directory describing the unused area
area.lw
the last word offset within the directory
area.array.fptr (size_index)
the relative offset of the first free block of the given
size
area.array.size (size_index)
the size of this given set of blocks
The various size blocks (and the number of different size blocks)
that are used (and placed into this area header) comes from
active_hardcore_data$alloc_sizes.
222...333 DDDIIIRRREEECCCTTTOOORRRYYY EEENNNTTTRRRIIIEEESSS
The various entries within a directory, whether they describe a
branch or a link, are threaded into a single list of entries.
These lists are found from the directory header.
2-3
MDD-006 Multics File System
dir.seg_count
the number of non-directory branches
dir.dir_count
the number of directory branches
dir.lcount
the number of links
dir.entryfrp
the relative pointer to the beginning of the entry list
dir.entrybrp
the relative pointer to the end of the entry list
The directory entry for a segment is the same as for a directory
except that certain fields are meaningless for the inappropriate
type. The directory entry for a link is the same as that for a
branch for the first 24 words so that they may all be treated the
same relative to chasing threads, examining the branch switch,
etc.
The basic data items within a directory entry are shown below.
The format of a directory entry for a branch is shown by
dir_entry.incl.pl1; the format for a link entry is shown by
dir_link.incl.p1.
entry.type, link.type
the value of DIR_TYPE (4) if this is a branch for a
directory, SEG_TYPE (7) is this is a branch for a segment,
or LINK_TYPE (5) if this is a non-branch entry (a link)
entry.size, link.size
the size of this directory entry
entry.efrp, link.efrp
the forward (relative) pointer to the next directory entry
entry.ebrp, link.ebrp
the backward (relative) pointer to the previous directory
entry
entry.bs, link.bs
(branch switch) TRUE if this is a branch entry
entry.uid, link.uid
the unique id of the entry
entry.dtem, link.dtem
the date-time this entry was last modified. This can be
used to detect the possible need to recompute access on the
entry. (Refer to directory entry relocking mechanisms for
more details.)
entry.dtd, link.dtd
the date-time dumped of this entry
For a branch entry, the following fields are defined.
entry.dirsw
TRUE if this is a directory branch
entry.pvid
2-4
Multics File System MDD-006
the physical volume id of the object
entry.vtocx
the VTOC entry index of the object
entry.oosw
obsolete
entry.per_process_sw
indicates segment is per process
entry.copysw
TRUE if a copy should be made of this segment upon a write
violation
entry.safety_sw
TRUE if the object is not to be deleted
entry.multiple_class
TRUE if the segment has multiple security classes
entry.audit_flag
TRUE if the segment must be audited for security (not
currently used)
entry.security_oosw
TRUE if the object is out-of-service for security reasons
entry.entrypt_sw
TRUE if call limiter is to be enabled in the SDW
entry.entrypt_bound
call limiter for the SDW (gates only)
entry.master_dir
TRUE for a master directory
entry.tpd
obsolete
entry.access_class
AIM security attributes
entry.ring_brackets
ring brackets on segment
entry.ex_ring_brackets
extended ring brackets
entry.bc
bit count for a segment, msf component indicator for a
directory
entry.sons_lvid
logical volume id for immediately inferior non-directory
segments (directories only)
entry.owner
UID of containing directory (must match dir.uid)
If this is a non-branch entry (link), the following fields are
defined.
link.pathname_size
the number of characters in link.pathname
link.pathname
pathname of link
link.owner
UID of the containing directory (must match dir.uid)
2-5
MDD-006 Multics File System
222...444 EEENNNTTTRRRYYY NNNAAAMMMEEESSS
Each entry in a directory may have an arbitrarily large number of
names. These names are kept in a list originating from the
entry. The declaration of a name (the structure "names") is
found in dir_name.incl.pl1. The name structure that contains the
primary name is found within the entry or link structure for
which it is the primary name. This name structure is linked just
like any other name structure for the entry, though.
entry.primary_name, link.primary_name
the area reserved within the entry for the name structure
holding the primary name
entry.nnames, link.nnames
number of names for this entry
entry.name_frp, link.name_frp
relative pointer to the start of the name list (this will
point to entry/link.primary_name)
entry.name_brp, link.name_brp
relative pointer to the end of the name list
names.type
the value NAME_TYPE (6)
names.size
the size of this structure
names.fp
relative pointer to the next name
names.bp
relative pointer to the previous name
names.name
a name for this entry
names.entry_rp
relative pointer to the owning entry
names.owner
UID of the owning entry
222...555 HHHAAASSSHHH TTTAAABBBLLLEEE
For speed when looking for a name within a directory, a hash
table is maintained within each directory. This hash table is
maintained by the program hash. It is found from the directory
header and allocated within the directory. The hash table can be
of one of several possible sizes
(active_hardcore_data$hash_tables_sizes). When the hash table
becomes too full (number of names is greater than the hash table
size), a new hash table of larger size is generated, rehashing
the existing names.
dir.hash_table_rp
relative pointer to the start of the name hash table
dir.htsize
2-6
Multics File System MDD-006
the size of hash table
dir.htused
(hash table used) the total of the number of names of all of
the entries in this directory
dir.rehashing
TRUE if the hash table is being reconstructed. If this flag
is found on when the hash table is to be searched, a
directory salvage is automatically performed.
The hash table has the usual format. Each name is hashed (using
the algorithm in hash_index_). The <hash value>th entry of the
hash table contains a relative pointer to the name structure. If
more than one name hashes to the same value, these multiple names
are threaded into a list starting at the <hash value>th hash
table entry.
hash_table.type
the value HASH_TABLE_TYPE (13 octal)
hash_table.size
the size of this structure
hash_table.name_rp
the hash table array (dir.htsize)
hash_table.modify
obsolete
hash_table.checksum
obsolete
hash_table.owner
obsolete
names.ht_index
index of hash table entry for this name
names.hash_thread
relative pointer to the next name that hashes to the same
value as this one
222...666 AAACCCLLL AAANNNDDD AAACCCCCCEEESSSSSS NNNAAAMMMEEESSS
Each branch entry can have an ACL. Also, a directory may contain
an IACL for each ring (1 to 7) for segments and one each per ring
for directories. The ACL is stored as a list of ACL entries. An
ACL entry is described by the include file dir_acl.incl.pl1. The
IACLs are found from the directory header, the branch ACL from
the entry. The ACL is stored in the usual order (scanning
order).
dir.acle_total
the total number of ACL entries in directory
dir.iacl_count.seg (validation level)
the number of initial ACL entries for segments
dir.iacl_count.dir (validation level)
the number of initial ACL entries for directories
2-7
MDD-006 Multics File System
dir.iacl.seg_frp (validation level)
relative pointer to the start of the initial ACL for
segments
dir.iacl.seg_brp (validation level)
relative pointer to the end of the initial ACL for segments
dir.iacl.dir_frp (validation level)
relative pointer to the start of the initial ACL for
directories
dir.iacl.dir_brp (validation level)
relative pointer to the end of the initial ACL for
directories spb
entry.acle_count
the number of entries on the ACL for the branch
entry.acl_frp
relative pointer to the start of the ACL for the branch
entry.acl_brp
relative pointer to the end of the ACL for the branch
acl_entry.type
the value ACLE_TYPE (2)
acl_entry.size
the size of this structure
acl_entry.frp
relative pointer to the next ACL entry in this ACL
acl_entry.brp
relative pointer to the previous ACL entry in this ACL
acl_entry.mode
corresponding access modes for the userid described by this
ACL entry
acl_entry.ex_mode
corresponding extended access modes for the userid described
by this ACL entry
acl_entry.checksum
obsolete
acl_entry.owner
the UID of the owning entry. For IACLs, this is the UID of
the directory.
Each ACL entry references a particular userid
(person.project.tag). Such a userid is also present as the
author and bit count author for each branch and the author for
each link. Since it is expected that a component of such
userid's (person and project names) will be duplicated many times
within a directory, these access names are stored only once each.
Each structure that wishes to contain a userid will contain a
relative pointer to an access_name structure for the person, a
relative pointer to an access_name structure for the project, and
the tag (as just that single character).
entry.author.pers_rp, link.author.pers_rp
relative pointer to the person name structure for the user
who created the branch
2-8
Multics File System MDD-006
entry.author.proj_rp, link.author.proj_rp
relative pointer to the project name structure for the user
who created the branch
entry.author.tag, link.author.tag
the tag of the user who created the branch
entry.bc_author.pers_rp
relative pointer to the person name structure for the user
who set the bit count
entry.bc_author.proj_rp
relative pointer to the project name structure for the user
who set the bit count
entry.bc_author.tag
the tag of the user who set the bit count
acl_entry.name.pers_rp
relative pointer to the person name structure for the userid
associated with this ACL entry. A value of zero implies
that the person value is "*".
acl_entry.name.proj_rp
relative pointer to the project name structure for the
userid associated with this ACL entry. A value of zero
implies that the project value is "*".
acl_entry.name.tag
the tag of the userid associated with this ACL entry
The various person and project names stored within a directory
are kept in lists, found from the directory header. This list
allows any attempt to add a new name (by acc_name_) to scan these
lists before adding the name. The name is stored in the
access_name structure, declared in dir_acl.incl.pl1.
dir.pers_brp
relative pointer to the end of the person name list
dir.proj_brp
relative pointer to the end of the project name list
dir.pers_frp
relative pointer to the start of the person name list
dir.proj_frp
relative pointer to the start of the project name list
access_name.type
the value ACCESS_NAME_TYPE (1)
access_name.size
the size of this structure
access_name.frp
relative pointer to the next name structure within the
directory
access_name.brp
relative pointer to the previous name structure within the
directory
access_name.salv_flag
2-9
MDD-006 Multics File System
obsolete
access_name.usage
the number of ACL entries, author entries or bit count
author entries that refer to this name. This count is kept
so that this structure may be freed when the count becomes
zero.
access_name.name
the person or project name itself
access_name.checksum
obsolete
access_name.owner
the UID of the containing directory (must match dir.uid)
222...777 EEEXXXAAAMMMPPPLLLEEE
As an example, consider the directory containing the following
entries.
branch 1
names: seg
author: Inzr.SysD.z
bc_author: Loe.Mult.a
ACL: Loe.Mult.a rw
Inzr.SysD.* rw
branch 2
names: dir
author: Loe.Mult.a
bc_author: Loe.Mult.a
ACL: Loe.Mult.* sma
*.SysD.* sma
link 1
names: link
add
author: Loe.Mult.a
A possible structure for this directory would be as shown on the
following pages. (Other threading of blocks are possible
depending on the order of creation of the objects.) Each page
shows a particular set of threads within this directory. Figure
1 shows the threading of entries. Figure 2 shows the threading
of the names, both those contained within entries and those
external to them. Figure 3 shows the hash table threads. Figure
4 shows the threading of the lists of person and project names.
Figure 5 shows the author and bit count author threads to the
person and project names. Figure 6 shows the threading of ACL
entries and the threading of these to the person and project
names. Note that the count of the references to the person and
project names is the total of the references for figures 5 and 6.
2-10
Multics File System MDD-006
/=========\ /=========\ /=========\ /=========\
| dir | | entry | | entry | | entry |
| | | | | | | |
| e e | | e e | | e e | | e e |
| n n | | n n | | n n | | n n |
| t t | | t t | | t t | | t t |
| b f | | b f | | b f | | b f |
| p p | | p p | | p p | | p p |
\=========/ \=========/ \=========/ \=========/
V V>>>>>>>>>>>>A V<><><><><><>A V<><><><><><>A A
V A
V>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>A
/=========\ /=========\ /=========\ /=========\
| ht | |acl_entry| |acl_entry| | names |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
\=========/ \=========/ \=========/ \=========/
/=========\ /=========\
|acl_entry| |acl_entry|
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
\=========/ \=========/
/=========\ /=========\ /=========\ /=========\
| accessor| | accessor| | accessor| | accessor|
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
\=========/ \=========/ \=========/ \=========/
Figure 1
2-11
MDD-006 Multics File System
/=========\ /=========\ /=========\ /=========\
| dir | | entry | | entry | | entry |
| | |nn " enn| |nn " enn| |nn " enn|
| | |aa s naa| |aa d naa| |aa l naa|
| | |mm e tmm| |mm i tmm| |mm i tmm|
| | |ee g ree| |ee r ree| |ee n ree|
| | |bf " ybf| |bf " ybf| |bf k ybf|
| | |pp ppp| |pp ppp| |pp " ppp|
\=========/ \=========/ \=========/ \=========/
VVA<<<VAA VVA<<<VAA AVVA<<<VAV
VV>>>>>AA VV>>>>>AA AVV>>>>>AA
V>>>>>>>A V>>>>>>>A AV V
AV>>>>>>VV
A<<<<<<AVA
/=========\ /=========\ /=========\ /=========\
| ht | |acl_entry| |acl_entry| | names |
| | | | | | | " enn|
| | | | | | | a naa|
| | | | | | | d tmm|
| | | | | | | d ree|
| | | | | | | " yfb|
| | | | | | | ppp|
\=========/ \=========/ \=========/ \=========/
/=========\ /=========\
|acl_entry| |acl_entry|
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
\=========/ \=========/
/=========\ /=========\ /=========\ /=========\
| accessor| | accessor| | accessor| | accessor|
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
\=========/ \=========/ \=========/ \=========/
Figure 2
2-12
Multics File System MDD-006
/=========\ /=========\ /=========\ /=========\
| dir | | entry | | entry | | entry |
| h | | " v t| | " v t| | " v t|
| a | | s a h| | d a h| | l a h|
| s | | e l r| | i l r| | i l r|
| h | | g u e| | r u e| | n u e|
| t | | " e a| | " e a| | k e a|
| p | | 2 d| | 2 d| | " 3 d|
\=========/ \=========/ \=========/ \=========/
V A V>>>>>>>>>>>A A
V A>>>>>>>>>>>>A A
V A A
V AA>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>A
V AA
/=========\ /=========\ /=========\ /=========\
| ht | |acl_entry| |acl_entry| | names |
| vvv| | | | | | " v t|
| aaa| | | | | | a a h|
| lll| | | | | | d l r|
| uuu| | | | | | d u e|
| eee| | | | | | " e a|
| 123| | | | | | 1 d|
\=========/ \=========/ \=========/ \=========/
V>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>A
/=========\ /=========\
|acl_entry| |acl_entry|
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
\=========/ \=========/
/=========\ /=========\ /=========\ /=========\
| accessor| | accessor| | accessor| | accessor|
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
\=========/ \=========/ \=========/ \=========/
Figure 3
2-13
MDD-006 Multics File System
/=========\ /=========\ /=========\ /=========\
| dir | | entry | | entry | | entry |
| p p p p | | | | | | |
| e e r r | | | | | | |
| r r o o | | | | | | |
| s s j j | | | | | | |
| f b f b | | | | | | |
| p p p p | | | | | | |
\=========/ \=========/ \=========/ \=========/
V V V V>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>V
V V V>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>V V
V V V V
V V>>>>>>>>>V V V
V>>>>>>>>>V V V V
/=========\ V V /=========\ /=========\ V V /=========\
| ht | V V |acl_entry| |acl_entry| V V | names |
| | V V | | | | V V | |
| | V V | | | | V V | |
| | V V | | | | V V | |
| | V V | | | | V V | |
| | V V | | | | V V | |
| | V V | | | | V V | |
\=========/ V V \=========/ \=========/ V V \=========/
V V V V
V V V V
V V /=========\ /=========\ V V
V V |acl_entry| |acl_entry| V V
V V | | | | V V
V V | | | | V V
V V | | | | V V
V V | | | | V V
V V | | | | V V
V V | | | | V V
V V \=========/ \=========/ V V
V V V V
V<<<<<<V V>>>>>>>>V V<<<<<<V V>>>>>>>>V
V A<><><><><><><A V V A<><><><><><><A V
V A A V V A A V
/=========\ /=========\ /=========\ /=========\
| accessor| | accessor| | accessor| | accessor|
| " b f | | " b f | | " b f | | " b f |
| I r r | | L r r | | M r r | | S r r |
| n p p | | o p p | | u p p | | y p p |
| z | | e | | l | | s |
| r | | " | | t | | D |
| " | | | | " | | " |
\=========/ \=========/ \=========/ \=========/
Figure 4
2-14
Multics File System MDD-006
/=========\ /=========\ /=========\ /=========\
| dir | | entry | | entry | | entry |
| | | pap pbp | | pap pbp | | pap |
| | | eur ecr | | eur ecr | | eur |
| | | rto rao | | rto rao | | rto |
| | | shj suj | | shj suj | | shj |
| | | ror rtr | | ror rtr | | ror |
| | | prp php | | prp php | | prp |
\=========/ \=========/ \=========/ \=========/
V<<<<<<V V V V V V V V V<<<<<V V>>>>>>>>>V
V V<<<<<<X<V V V V V V>>>X>>>>>>>>>>>>>>>V V
V V V<<<<X<<<X<<<<<<<<<V V>X>>>>>X>V V V
V V V V>>>X>>>>>>>>>>>>>X>>>>>X>X>>>>>>>>>>>>>X>X>V
V V V V>>>>V V<<<<<<V V V V V V
/=========\V V V/=========\ V V/=========\ V V /=========\ V V V
| ht |V V V|acl_entry| V V|acl_entry| V V | names | V V V
| |V V V| | V V| | V V | | V V V
| |V V V| | V V| | V V | | V V V
| |V V V| | V V| | V V | | V V V
| |V V V| | V V| | V V | | V V V
| |V V V| | V V| | V V | | V V V
| |V V V| | V V| | V V | | V V V
\=========/V V V\=========/ V V\=========/ V V \=========/ V V V
V<<V V V V<<<<<<<<<<<X<V V V V<<<<<<<<<<<V V V
V V<<V V V V V V V V<<<<<<<<<<<V V
V V V<<V V V<X<<<<<<<<<<<<<<V V V V V
V V V V<<V V V V V V V
V V V V /=========\V V /=========\ V V V V
V V V V |acl_entry|V V |acl_entry| V V V V
V V V V | |V V | | V V V V
V V V V | |V V | | V V V V
V V V V | |V V | | V V V V
V V V V | |V V | | V V V V
V V V V | |V V | | V V V V
V V V V | |V V | | V V V V
V V V V \=========/V V \=========/ V V V V
V V V V V<<V V V V V V
V V V V>>>>>>>V V V V<<<<<<<<<<V V V V>>>>>>V
V V V>>>>>>>V V V V>>>V V V<<<<<<<<<<V V V
V V>>>>>>>V V V V V V V V<<<<<<<<<<V V
/=========\ /=========\ /=========\ /=========\
| accessor| | accessor| | accessor| | accessor|
| " c | | " c | | " c | | " c |
| I o | | L o | | M o | | S o |
| n u | | o u | | u u | | y u |
| z n | | e n | | l n | | s n |
| r t | | " t | | t t | | D t |
| " 2 | | 6 | | " 6 | | " 3 |
\=========/ \=========/ \=========/ \=========/
Figure 5
2-15
MDD-006 Multics File System
/=========\ /=========\ /=========\ /=========\
| dir | | entry | | entry | | entry |
| | | a a | | a a | | |
| | | c c | | c c | | |
| | | l l | | l l | | |
| | | b f | | f b | | |
| | | r r | | r r | | |
| | | p p | | p p | | |
\=========/ \=========/ \=========/ \=========/
V V V V
V>X>>>>>V V<<<<<X<V
V V V V
/=========\ /=========\ V V /=========\ /=========\
| ht | |acl_entry| V V |acl_entry| | names |
| | | p f b p | V V | p b f p | | |
| | | e r r r | V V | e r r r | | |
| | | r p p o | V V | r p p o | | |
| | | s j | V V | s j | | |
| | | r r | V V | r r | | |
| | | p p | V V | p p | | |
\=========/ \=========/ V V \=========/ \=========/
V<<<V V V V<V V>V V V V>>>V
V A V V V V A V
V V V>X>>>>>X>X>>>X>>>>>X>V
V A V V<<<X<V V V V
V A V V V A V V
V /=========\ V /=========\ V V
V |acl_entry| V |acl_entry| V V
V | p b f p | V | p f b p | V V
V | e r r r | V | e r r r | V V
V | r p p o | V | r p p o | V V
V | s j | V | s j | V V
V | r r | V | r r | V V
V | p p | V | p p | V V>>>>>>>V
V<<<<<<V \=========/ V \=========/ V V
V V V>>>X>>>V V>>>X>>>>>>>V V
V V V V V V V
V V V<<V V V<<V V V
V V V V V V V
/=========\ /=========\ /=========\ /=========\
| accessor| | accessor| | accessor| | accessor|
| " c | | " c | | " c | | " c |
| I o | | L o | | M o | | S o |
| n u | | o u | | u u | | y u |
| z n | | e n | | l n | | s n |
| r t | | " t | | t t | | D t |
| " 2 | | 6 | | " 6 | | " 3 |
\=========/ \=========/ \=========/ \=========/
Figure 6
2-16
Multics File System MDD-006
SECTION 3
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.
333...111 TTTYYYPPPEEESSS OOOFFF DDDIIIRRREEECCCTTTOOORRRYYY LLLOOOCCCKKKSSS
A directory may be locked for reading or writing. Directory
locks are 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 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 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.
333...222 DDDIIIRRREEECCCTTTOOORRRYYY LLLOOOCCCKKKIIINNNGGG RRRUUULLLEEESSS
Directory locks are below the AST lock, as described under
segment activation below. Directory locks are wait locks; the
event is the UID of the directory.
3-1
MDD-006 Multics File System
The locking hierarchy for directory locks follows the hierarchy.
That is, 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.
333...333 DDDIIIRRREEECCCTTTOOORRRYYY LLLOOOCCCKKKIIINNNGGG MMMEEECCCHHHAAANNNIIISSSMMM
Directory locks are maintained by the program lock. They are
maintained 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.
333...333...111 SSStttrrruuuccctttuuurrreee ooofff dddiiirrr_llloooccckkk_ssseeeggg
dir_lock_seg contains the list of all directories in the system
that are 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.
dir_lock_seg.header.seg_lock
a standard hardcore lock (process id, event and notify
switch)
dir_lock_seg.header.n_dir_locks
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).
dir_lock_seg.header.highest_in_use
the highest dir_lock cell in use.
dir_lock_seg.header.max_readers
the maximum readers a directory can have. This is the
maximum number of eligible processes.
dir_lock_seg.header.readers_ptr
points to dir_lock_seg.readers
dir_lock_seg.header.locks_ptr
3-2
Multics File System MDD-006
points to dir_lock_seg.dir_locks
dir_lock_seg.header.meters.find_calls
the number of times that an attempt was made to find a lock
cell for a given UID
dir_lock_seg.header.meters.find_failures
the number of times that a cell for the given UID was not
found
dir_lock_seg.header.meters.max_in_use
the highest value of dir_lock_seg.highest_in_use
dir_lock_seg.dir_locks
an array of directory locks
dir_lock.uid
UID of directory being locked. This value is used as the
wait event when waiting for the lock on this directory.
dir_lock.flags.notify_sw
TRUE if some process is waiting for notification of the
unlocking of this directory
dir_lock.flags.salvage_sw
indicates the directory is locked for salvaging. This
information is of use to verify_lock.
dir_lock.lock_count
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
dir_lock.write_locker
process id holding the directory locked; if zero, the list
of readers appears in dir_lock_seg.readers
dir_lock_seg.readers
the array of process ids holding this directory locked
333...333...222 OOOpppeeerrraaatttiiiooonnn ooofff llloooccckkk
The method by which a directory is locked follows. All
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)).
3-3
MDD-006 Multics File System
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 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 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 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
3-4
Multics File System MDD-006
(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.
333...444 SSSPPPEEECCCIIIAAALLL UUUSSSEEESSS AAANNNDDD RRRUUULLLEEESSS FFFOOORRR DDDIIIRRREEECCCTTTOOORRRYYY LLLOOOCCCKKKSSS
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.
333...444...111 SSSeeegggmmmeeennnttt AAAccctttiiivvvaaatttiiiooonnn
The module seg_fault needs access to directory entries in order
to obtain 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.
333...444...222 PPPssseeeuuudddooo---DDDiiirrreeeccctttooorrriiieeesss
Since directories are locked by recording their UIDs in
dir_lock_seg, 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.
3-5
MDD-006 Multics File System
333...555 DDDIIIRRREEECCCTTTOOORRRYYY LLLOOOCCCKKK SSSAAALLLVVVAAAGGGIIINNNGGG
When a process crawls out of ring zero as the result of a fault
therein, 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 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.
3-6
Multics File System MDD-006
SECTION 4
FILE SYSTEM MECHANISMS
Various mechanisms common within the file system will be
presented. In the process of explaining these mechanisms, some
of the operation of directory control will presented. This
section discusses mechanisms mostly internal to directory
control; the description of the more external functions of the
file system (entry creation, for example) will be found under the
description of the various file system primitives.
444...111 LLLOOOCCCAAATTTIIINNNGGG AAANNNDDD HHHOOOLLLDDDIIINNNGGG DDDIIIRRREEECCCTTTOOORRRIIIEEESSS AAANNNDDD DDDIIIRRREEECCCTTTOOORRRYYY EEENNNTTTRRRIIIEEESSS
Finding a directory involves bringing that directory into the
process' address space (if it is not already there) and
determining the identity of the directory within the address
space (its segment number or pointer). Finding a directory entry
involves finding the directory and then finding the entry within
the directory. Various mechanisms exist to perform these
operations in various ways. It is also necessary to use certain
mechanisms to keep the directories and directory entries from
disappearing or changing during the time in which they are being
manipulated.
The official rules state that all finding of directories and
directory entries (other than parents of already validated
entries) must be performed by the module dc_find, so that it may
enforce the security policy of the system. This sub-section
describes the method by which dc_find locates directories and
directory entries.
This sub-section also describes the method by which dc_find, and
callers of dc_find, maintain the validity of the pointers they
have to the directories and directory entries.
444...111...111 LLLooocccaaatttiiinnnggg DDDiiirrreeeccctttooorrriiieeesss
The object of locating a directory involves taking the "name" of
a directory and mapping it into the "address" (segment number or
4-1
MDD-006 Multics File System
pointer) of the directory within the address space (and bringing
the directory into the address space, if necessary). The "name"
of a directory is either its pathname or its UID pathname (UID of
the directory and all superior directories back to the root).
The process of finding a directory, given its pathname, in its
basic (overly simplified) form, is an iterative process performed
by dc_find's internal routine find_dirsegno. The process is to
start with the root and then find the various subordinate
directories, in turn, until the desired directory is encountered.
The root is inherently known. (Address and name space management
can initiate the root by simply declaring a segment whose
directory entry pointer is null; segment control special cases
this to mean the root.) Once the "address" of the root is known,
the next subordinate directory (given the next entryname stripped
from the pathname) can be found. (The directory entry for the
subordinate directory is found as described in the next section.
Address and name space management uses this directory entry
pointer (and the UID obtained from it) to initiate the
subordinate directory.) This process is repeated until the
desired directory is found.
It is not allowed to bring AIM isolated directories into the
address space since by so doing the user is informed of their
existence. This is not allowed since the names of objects
subordinate to AIM isolated directories are also AIM isolated
information. find_dirsegno checks directories for AIM isolation
and stops (with an audit) when such a directory is encountered.
Within the above process, it is possible that a link will be
encountered. If this happens, that portion of the pathname
already resolved is replaced by the link target and the process
starts over. (Say that >a>b>c>d is being located and that >a>b>c
is a link to >e>f. Then, once >a>b has been located, we will see
that the directory entry for c describes it as a link to >e>f.
The pathname >e>f>d will be formed, the directories >a and >a>b
will no longer be needed, and the process of finding the
directory will start again looking for >e>f>d.)
Locating a directory given its UID path is similar to the process
for locating a directory given its pathname. This is done by the
internal routine uid_path_util within dc_find (not to be confused
with the file system primitive of the same name). In the UID
path case, instead of searching through each directory found for
the directory entry describing the next subordinate directory
name, a search is made for the directory entry having the UID of
the next subordinate directory. There is no need to worry about
handling links in the process.
4-2
Multics File System MDD-006
444...111...222 LLLooocccaaatttiiinnnggg DDDiiirrreeeccctttooorrryyy EEEnnntttrrriiieeesss
The object of locating a directory entry is to take the "name" of
a file system object and find the directory entry corresponding
to this object. The "name" in this case could be the pathname of
the object, the UID path of the object, or a pointer to the
object.
The process of finding the directory entry given a pathname is
basically to find the containing directory (given the directory
portion of the pathname) and then to look up the entry describing
the entryname portion.
Looking up an entry, given a name, is done by find_entry (within
dc_find). find_entry uses the directory name hash table
(actually, it uses hash$search) to find the entry. find_entry
takes a name and a type desired for the object to be found. The
type is a four bit string with a bit meaning each of directory,
segment, link or nothing. Each one bit means that the caller
will allow the found object to be of the type corresponding to
that one bit. (A type of nothing means that the caller will
allow the object to not exist.) The various uses of the type
field will be described under the description of dc_find.
find_entry is responsible for checking the basic validity of the
directory entry found, and auditing attempts to look up a name of
the wrong type. find_entry also makes the check for an entry
being security-out-of-service.
When finding a directory entry given a pathname, it is possible
that the final target is a link. (Links within the directory
portion of the pathname would have been chased by find_dirsegno.)
The chasing of final target links, if desired, is performed by
find_ (within dc_find). Chasing links simply involves taking the
link target found and repeating the directory entry locating
function repeatedly. A counter is kept here, as in all link
chasing functions, to keep this search from proceeding
indefinitely.
Searching for a directory entry given its UID path was mostly
described under locating a directory, above. The search for a
given entry given a UID must be done by hand (unlike the search
given an entryname) since no hash table is maintained in the
directory for UIDs.
Locating a directory entry given a pointer to the owning object
is performed by sum (segment utility module). This module is
used by dc_find when given the pointer to an object. It is also
commonly used throughout directory control, when a program has a
pointer to a directory and wishes to find the directory entry
describing this directory.
4-3
MDD-006 Multics File System
sum has two entries of use here, getbranch and getbranch_root_my.
From the point of this discussion, the only difference between
sum$getbranch and sum$getbranch_root_my is that the later will
return a null entry pointer and error_table_$root when the
supplied object pointer points to the root whereas the former
returns error_table_$noentry (it considers this an error). The
directory entry pointer is found from the KST entry for the
object; this will be described within the description of sum
under directory control primitives.
| Note that it is never valid to reference kste.entryp directly to
| get a pointer to the directory entry associated with the KST
| entry. While the directory is unlocked, the directory entry
| could have been deleted or moved by the directory salvager.
| Instead, sum must always be called to lock the containing
| directory and to get a pointer to the directory entry. The
| directory must remain locked for reading during the period in
| which the directory entry is to be referenced. See section 7 for
| more details.
444...111...333 KKKeeeeeepppiiinnnggg VVVaaallliiiddd DDDiiirrreeeccctttooorrryyy aaannnddd EEEnnntttrrryyy PPPoooiiinnnttteeerrrsss
The above descriptions of locating directories and directory
entries was overly simplified. In actuality, these various
programs (and their callers) must concern themselves with
maintaining the validity of the pointers that they generate to
the directories and directory entries. In particular, they must
make sure that address and name space management does not remove
any of these directories from the address space while they are
being manipulated. Also, they must make sure that no other
process is modifying these directories while they are being
searched or in other ways manipulated.
KEEPING DIRECTORIES FROM BEING TERMINATED
The mechanics of keeping these directories from being removed
from the address space (i.e., made unknown) by address and name
space management is discussed further under that section. For
now, we will consider that there are two rules: a directory will
be protected from being made unknown in the address space if it
has a non-zero usage count (in the KST entry) or a directory or
segment subordinate to it has a non-zero usage count. That is,
either the directory must be marked as in use or some subordinate
directory must be in use. (It is required that all directories
superior to a directory within the address space must also be
within the address space.)
Having address and name space management bring a directory into
the address space automatically increments the usage count by
one. Thus, programs need not worry about these directories
4-4
Multics File System MDD-006
disappearing within the address space from under them. However,
it is necessary to clean up these directories for fear of filling
the address space with useless directories. This is done through
segno_usage$decrement.
Thus, an expanded view of the process of locating a directory
follows. The root is made known (and its usage count incremented
as a result). The first level directory's entry is found. Given
this entry, the first level directory itself is made known (and
its usage count incremented as a result). Now that the root will
be "held" by this first level directory, the root's usage count
is decremented. The second level directory's entry is found
within the first level directory. This second level directory is
made known (and its usage count incremented as a result). The
usage count of the first level directory is decremented. And so
on. When the desired directory is reached, only this last
directory will have its usage count incremented. The calling
program is guaranteed that this directory will remain in the
address space. When the calling program is done with the
directory, decrementing the usage count for it is sufficient to
free all superior directories (unless, of course, they have
non-zero usage counts because of some other operation proceeding
at the time). Refer to the usage of dc_find under directory
control primitives for more details.
KEEPING DIRECTORIES FROM BEING MODIFIED
Perhaps the most important part of the mechanism to find
directory entries is missing from the above: directory locking.
When searching a directory for an entry, or when operating upon
the entry found (or any other contents of a directory), it is
necessary to have the directory locked to prevent modifications
to the directory by other processes. Directory locking is
described in another section. From the point of view of a given
directory control program, the various entry pointers that
program keeps will only stay valid (continue to point to the
desired entries) as long as the containing directory is locked.
As such, a further expansion of the mechanism needed to find a
directory is the following. The root is found. It is locked, so
that the first level directory entry can be found. Once this
directory is known, the root can be unlocked. This first level
directory is then locked so that the second level directory's
entry can be found and then made known. The first level
directory can then be unlocked. And so on.
dc_find will return pointers to directories that are locked. The
calling programs must unlock them when done. Refer to the usage
of dc_find under directory control primitives for more details.
4-5
MDD-006 Multics File System
444...111...444 TTThhheee PPPaaattthhhnnnaaammmeee AAAssssssoooccciiiaaatttiiivvveee MMMeeemmmooorrryyy (((PPPAAAMMM)))
Having to walk down all of the directories from the root every
time that a directory is to be found would be very inefficient.
In a normal process, there is a tendency to refer to the same set
of directories over and over. For this reason, each process
maintains a pathname associative memory (by the program
pathname_am) that maps pathnames to directory segment numbers
(and vice versa).
USAGE OF THE PAM
The most common usage of the PAM is in find_dirsegno to optimize
the locating of a directory. The PAM based directory finding
mechanism is as follows.
Start with the desired pathname. See if it is in the PAM
(pathname_am$get_segno). If so, its segment number is already
known; this can be returned. If not, look to see if the parent
directory's pathname is in the PAM. And so on. Walking up the
pathname in this way will stop when either the root is
encountered (at which time the previously described mechanism
comes into play) or a directory is found in the PAM. If a PAM
match is found, find_dirsegno can simply walk down the hierarchy
from there, instead of from the root.
pathname_am$get_segno increments the usage count for the
directory found just as if the directory were made known in the
usual way. The directory so found will need its usage count
decremented when done.
For each directory that find_dirsegno finds while walking down
the hierarchy from the root or the PAM found directory,
find_dirsegno places this pathname/segment number pair into the
PAM (pathname_am$set). This will help find_dirsegno out the next
time it wants to find this pathname.
The other usage of the PAM is by get_pathname_. get_pathname_
takes a segment number and returns its pathname. This operation
is described under address and name space management. It uses
the PAM (pathname_am$get_path) as a shortcut to walking up the
hierarchy to find the pathname. Also, after it has expended its
effort to find a pathname, it sets this into the PAM for later
use.
OPERATION OF THE PAM
The pathname associative memory is maintained within PDS by
pathname_am. The PAM consists of a threaded list of entries
mapping directory pathname to segment number. The list is
4-6
Multics File System MDD-006
threaded with the most recently used at the head of the list.
When a new pathname is added to the PAM, the tail entry (least
recently used) is deleted and this new pathname added as the
head. Performing a match within the PAM (either during a
get_path or a get_segno operation) causes the matching entry to
be rethreaded to the head of the list. Note that multiple
pathnames may refer to the same segment number.
When a pathname becomes invalid by virtue of the target's being
deleted or made unknown, it is removed from the PAM (clear
entrypoint). It is important to note that pathnames in the PAM
are not protected from being made unknown by address and name
space management (but address and name space management will
properly remove such a directory from the PAM when it is made
unknown). The PAM pathnames are protected when a get_segno
operation succeeds by virtue of the incrementing of the usage
count mentioned above. The process of removing the directory
from the address space during KST garbage collection will
properly clear the pathname from the PAM.
The operation of the PAM is vastly complicated by the question of
the renaming and deleting of directories (especially by other
processes). If a directory is renamed, it is necessary to
invalidate all pathnames for that directory, as well as any
directory subordinate to that directory within the PAM. Since
other processes do not wish to walk through the PAM of all other
processes when a directory rename is done, a mechanism has been
devised to require maintaining the minimum amount of data across
processes.
This mechanism uses active_hardcore_data$pam_flush_buffer
(indexed, circularly, by active_hardcore_data$pam_flush_level) to
keep track of the extent to which all processes must flush their
PAM of directories affected by some process. The basic operation
is for the PAM to keep track of the UID pathnames of the
directories within the PAM (via the UID field in the KST entry
for the directory), and to use pam_flush_buffer to show what UIDs
need flushing. That is, if some process renames the directory
with UID N, that process informs other processes to flush all PAM
entries for whom the corresponding directory's UID pathname
(derived by walking down the KST) contains N. The mechanism to
keep track of this single piece of information is very simple,
making this cross-process passing of UIDs desirable.
The workings of this revolves around ahd$pam_flush_level and the
user's pam.flush_level. Before the user updates the PAM, the
process flushes its PAM as required by the active_hardcore_data
(ahd) information as described below. pam.flush_level is set to
ahd$pam_flush_level when a PAM update is finished. After this
time, ahd$pam_flush_level is incremented by one each time some
process declares a need to flush PAMs in other processes. When
the process looks at the PAM next, if pam.flush_level is equal to
4-7
MDD-006 Multics File System
ahd$pam_flush_level, fine. If not, then the next N
(ahd$pam_flush_level - pam.flush_level) slots in the circular
ahd$pam_flush_buffer queue contain UIDs of directories to flush
from the PAM. If N is greater than the size of
ahd$pam_flush_buffer, it follows that the process lost track of
what UIDs to flush, and must therefore flush all of them. Also,
when setting a value into ahd$pam_flush_buffer, if the process
notices that other setters of ahd$pam_flush_buffer caught up with
it (wrapped around this circular buffer), the process forces the
last slot of ahd$pam_flush_buffer to 777777777777 (the root) to
force everyone to flush all of their PAM's the next time around.
This examining and setting of ahd$pam_flush_level is done with
appropriate hardware locking instructions.
It was deemed undesirable to maintain the UID pathname for each
PAM entry within the PAM (for size reasons); it is also
undesirable to compute this for each PAM entry each time there is
a UID to flush. So, an optimization is used. If the UID to
flush does not correspond to a directory within this process (as
determined via the UID hash kept in the KST), which is most
likely to be the case, the UID does not need to be flushed. Only
if the UID (from ahd$pam_flush_buffer) exists within the process
is it necessary to look for PAM entries that correspond.
444...111...555 SSSuuummmmmmaaarrryyy
File system programs must take certain precautions to keep the
directory and directory entry pointers they possess valid.
dc_find performs the necessary functions to make the returned
pointers stay valid. It is necessary, though, for the calling
programs to clean this up.
If the directory control program (that which calls dc_find) has a
pointer to a directory entry, the directory pointer itself is
found (ptr (ep, 0)). Given this pointer to the directory, the
directory control program must unlock the directory. If the
directory was found given a pointer to the object, this is all
that is necessary. (In such cases, sum$getbranch was called to
find the directory. The directory's usage count was not
incremented since it is being "held" by the inferior object.)
Otherwise, the directory must be dereferenced (its usage count
decremented). The functions of unlocking and dereferencing are
done by calling dc_find$finished. This entry unlocks the
directory and dereferences it, on the basis of an argument
supplied to it.
444...222 RRREEE---LLLOOOCCCAAATTTIIINNNGGG DDDIIIRRREEECCCTTTOOORRRIIIEEESSS AAANNNDDD DDDIIIRRREEECCCTTTOOORRRYYY EEENNNTTTRRRIIIEEESSS
It is sometimes not possible to keep a directory locked
throughout the series of events relating to the directory. For
4-8
Multics File System MDD-006
instance, address and name space management maintains the
directory entry pointer for each object in the address space so
that segment control can activate and deactivate them. These
directories clearly can not be kept locked during the run of the
process. Also, even during relatively short directory control
sequences, it is necessary to unlock directories to keep from
violating some other system locking rule (an example is given
later in this section). Thus, a mechanism must exist so that a
directory can be unlocked so that it can easily be re-locked and
the process' assumptions re-validated about it.
444...222...111 RRReee---vvvaaallliiidddaaatttiiinnnggg DDDiiirrreeeccctttooorrryyy EEEnnntttrrryyy PPPoooiiinnnttteeerrrsss
When an object is brought into the address space, address and
name space management must place the directory entry pointer for
the object in its KST entry. (This information is needed by
seg_fault at activation time.) If the directory containing this
entry is to be unlocked, the next time around this directory
entry pointer may be invalid, due to salvaging (compaction) of
the directory. The way to re-validate this entry pointer (or to
make it valid), and, indeed, the method used by sum, is to call
validate_entryp. validate_entryp performs a set of checks given
the entry pointer (with the directory locked, of course) to see
if this pointer still indicates the entry in question. If these
checks fail, a search of the directory for the entry having the
UID from the KST entry is done. If this fails, the segment must
have been deleted and an error is returned. Refer to the
translation of segment pointers to directory entries for more
details.
444...222...222 VVVaaallliiidddaaatttiiinnnggg DDDiiirrreeeccctttooorrryyy CCCooonnnttteeennntttsss
If a directory must be unlocked between two operations, it is
necessary to determine if the contents of the directory had
changed. This is done as follows. The program inspects
dir.change_pclock. This value is incremented by one each time a
process modifies the contents of the directory. If this value
hasn't changed since it was last locked, it wasn't modified.
444...222...333 RRReeetttuuurrrnnn AAArrreeeaaa MMMaaannnaaagggeeemmmeeennnttt
The normal sequence of events when returning information about a
file system object to the user ring is the following. The
directory is found, locked and the directory entry found. The
data is copied into the a temporary data space. The directory is
unlocked. The data is then copied into the user's data space,
taking whatever faults may arise. When the user's data is being
copied into a directory, it is copied before finding and locking
4-9
MDD-006 Multics File System
the directory, to take any potential faults at this time. It is
undesirable for faults to occur with directories locked.
A special mechanism is used, though, when the amount of data to
be copied out is large, in particular, when it is too large (or
variable) to be copied into a ring 0 temporary area. Examples of
this are when returning the ACL of an object, or the names within
a directory. These operations must copy their data into the user
ring within the loop processing the directory. They must be
careful since a fault could occur during this copying. Worse yet
is that they need to allocate the space (normally) for these
return values. This creates a special problem.
A directory control operation of this type will walk down the
directory first to determine how much data must be returned. The
allocation of this data, though, can not occur with the directory
locked since this allocation may extend an extensible area which
would not be possible if the area were immediately subordinate to
the directory. So, the directory must be unlocked, the area in
the user ring allocated, and the directory relocked. After this,
the change_pclock comparison described above determines if the
counts possessed of the data to return has been invalidated.
It is not necessary to recalculate access to the directory at
this time to determine if the operation is still allowed. This
is because the process is guaranteed that the directory didn't
change if the pclock test succeeds. (If it failed, it must
recalculate access.) Since the directory didn't change, even if
some other process did change the process' access to the
directory, the information that is about to be returned is the
same that it just saw, and is data it did have access to and
could have just as well copied out before the access was
changed.]
The relocking of the directory is done with a seg_fault_error
handler. (Locking the directory references the directory
header.) This is done because the directory may be deleted with
the directory unlocked. (Directories are prevented from deletion
while locked.)
444...222...444 SSSuuummmmmmaaarrryyy
If a directory must be unlocked, it is necessary to revalidate
any assumptions about it when it is relocked.
The main question is one of access. Does this process still have
access to the object? When the operation being performed
modifies the object, it must use care. The possibility exists
that some other process may delete this process' access to the
directory, and that other process would be surprised to see the
directory's contents modified after the access was deleted.
4-10
Multics File System MDD-006
However, if the operation to be performed merely returns
information, an optimization can be used. If the directory's
contents can be shown to have not changed since the access check
was made (by dc_find), then, even if some other process deleted
this process' access to the directory, this does not change what
this process' is allowed to see at the time of the access check.
Since it could just as well have returned the information at that
time, it might as well still return it now.
If the process was holding a pointer to a directory, then
relocking the directory must ensure that the process still has
access to the directory and that any assumptions based on its
contents have not changed. This is done by checking
dir.change_pclock. If dir.change_pclock hasn't changed, neither
has the directory and so no loss of access matters. A change of
dir.change_pclock requires that dc_find be rerun. Note that the
directory can be deleted while it is unlocked.
If the process was holding a pointer to a directory entry, then
relocking the parent must refind the entry pointer
(validate_entryp), recheck access on the parent and make sure no
assumptions about the entry have changed. This is normally done
by checking dir.change_pclock. No change implies no change to
the entry and so any access loss does not matter. The dtem field
in the entry can also be used to simply ensure that the process
still has access to the entry, since dtem is guaranteed to be
advanced by at least one for any access change. Checking
entry.dtem, however, is not sufficient when the operation to be
performed modifies the entry since a change of access to the
parent of this entry by some other process would not have changed
the dtem of this entry.
If the process was holding a pointer to a segment, then relocking
the parent must ensure that the segment held is still the segment
desired, that access still exists on the parent, and that no
assumptions about the segment have changed. Any subsequent
reference to the segment will validate that it still exists and
that its UID matches what was desired (via seg_fault).
entry.dtem or dir.change_pclock can be examined to validate the
other conditions. (Again, entry.dtem is not a sufficient check
if the segment is to be modified.)
If it is necessary to rerun dc_find, it is necessary to make sure
that the object found is the same as the one for which any
assumptions had been made. (If no assumptions are maintained
across the relocking, this can be ignored.) It is possible that
two names were swapped in the parent and so the pointer dc_find
returns to the object named "foo" points to a different object
than was "foo" the last time around. It is easy to tell if this
"foo" is the same as the previous "foo"; simply check its UID. A
check of entry.dtem is not necessary since dc_find would have
4-11
MDD-006 Multics File System
revalidated access unless some assumptions about "foo" could have
been affected during the unlocking.
444...333 MMMOOODDDIIIFFFYYYIIINNNGGG DDDIIIRRREEECCCTTTOOORRRIIIEEESSS
Whenever a directory control program modifies a directory,
several operations must be performed.
444...333...111 SSSiiigggnnnaaalllllliiinnnggg ttthhhaaattt aaa MMMooodddiiifffiiicccaaatttiiiooonnn iiisss iiinnn PPPrrrooogggrrreeessssss
When a process starts a modification, the process must lock the
directory for writing. Also, the process id of that process must
be recorded in dir.modify. In this way, crawlouts will detect
that the contents of the directory are in question and that a
directory salvage is to be performed. When the modification is
done (and notified, as explained below), the dir.modify field is
reset to zero and the directory unlocked.
444...333...222 RRReeecccooorrrdddiiinnnggg AAAcccccceeessssss aaannnddd AAAttttttrrriiibbbuuuttteee CCChhhaaannngggeeesss --- dddttteeemmm
If the modification being performed to a directory entry involves
potentially changing the access some process has to the object,
this must be reflected to those processes. First, setfaults must
be called to force all processes to recompute their access to the
object. Secondly, change_dtem must be called.
change_dtem will change the date-time entry modified field for
this entry to the current time. It does this in a way so as to
guarantee that the dtem is incremented by at least one (dtem is
only accurate to 1/16 sec.). It also keeps dtem from getting too
far in the future. Since change_dtem must sometimes wait for
time to go by so as to properly set the dtem, change_dtem must be
called judiciously. The dtem must be modified, though, when
access has been changed.
Calling change_dtem with respect to a directory is the equivalent
of performing a setfaults on the directory. This is explained in
the section on access control.
When an attribute of an entry is changed, change_dtem is still
called. In this case, though, the dtem is not critical; it is
just for user's information. As such, change_dtem is not called
if the dtem matches the current time.
444...333...333 RRReeecccooorrrdddiiinnnggg DDDiiirrreeeccctttooorrryyy CCCooonnnttteeennntttsss MMMooodddiiifffiiieeeddd --- dddtttcccmmm
The date-time contents modified (dtcm) field for a segment (which
is maintained in the VTOCE/ASTE) is exactly that. It is
4-12
Multics File System MDD-006
maintained with extensive mechanism described in the Storage
System PLM. The dtcm field for a directory has a different
meaning.
The dtcm for a directory is advanced to the current time if a
branch anywhere subordinate to the directory is modified or if
directory control explicitly declares the directory as modified.
When directory control operations such as the salvager are
running, it is desirable to not let the directory be flagged as
modified until the salvaging is done. For this reason, the dtcm
of directories is maintained in an unusual way.
Address and name space management flags all directories with the
gtms (global transparent modified switch) on. This causes page
control to not notice modifications of pages within directories,
and, therefore, to not set the fms (file modified switch) or the
dtcm. The dtcm must be updated manually. When a directory
update is done, sum$dirmod must be called. sum$dirmod finds the
ASTE (activating the directory if necessary and locking the AST).
The gtms switch is turned off so that pc$updates can be called.
This causes the fms switch to be set for this directory and all
superiors, as well as updating the dtcm. The gtms switch is then
turned off. This is all done under the directory lock, so that
no one else will be in a modification sequence.
4-13
Multics File System MDD-006
SECTION 5
ACCESS CONTROL - DC_FIND
Internal to directory control is the module dc_find. It is
responsible for locating directories and directory entries for
the file system primitives. In the process of locating these
entities, dc_find makes the necessary access checks, auditing
successful accesses and attempted access violations when
necessary. Indeed, dc_find is the enforcer of the systems'
security policy within the file system.
Much of the operation of dc_find is explained in the section on
directory control mechanisms. This section provides a few more
details. Its main purpose, though, is to explain the systems'
security policy (with respect to the file system) and to list the
various access checks (i.e., functions) available within dc_find.
555...111 BBBAAASSSIIICCC SSSEEECCCUUURRRIIITTTYYY MMMOOODDDEEELLL
Multics possesses three different security measures: ACLs, AIM
and rings. These mechanisms are well described in the Reference
Guide and will not be explained here.
The access modes a process has to an object depends on some
combination of the user's presence in the ACL of the object, the
user's AIM authorization versus the object's AIM classification,
and the user's ring (normally the user's validation level) versus
the ring brackets of the object. The access modes a user has on
an object determined by only calculating the access modes given
by the ACL of the object is called the user's "raw" access modes.
If the AIM classification calculation is factored in, the
resulting access modes are referred to as the user's
"authorization" access modes. Finally, if ring bracket
computations are also factored in, the resulting access modes are
referred to as the user's "effective" access modes.
Whether or not a given process is allowed to perform a specific
access to an object is a function of the access modes the process
has on the object, the access modes the process has on the
object's directory entry (that is, the process' access modes on
5-1
MDD-006 Multics File System
the parent directory), the access modes the process has on the
parent's directory entry, and so on, depending on the type of
access being attempted.
555...111...111 BBBaaasssiiiccc AAAcccccceeessssss CCCaaatttaaagggooorrriiieeesss
The basic access catagories revolve around getting and setting
the three main classes of properties of a file system object.
These are listed below. A more detailed description of what
properties are considered to be within these classes, as well as
what access operations are not (strictly) in these classes, is
provided later.
CONTENTS PROPERTIES
The contents properties of a segment are the machine words that
constitute the segment. The security requirements for accessing
these words are based on the effective access modes the user
possesses to the segment. This is enforced by the hardware,
given the authorization access modes and the ring brackets of the
segment, inserted into the segment's SDW by dc_find on behalf of
segment control.
The bit count of a segment is also a contents property of the
segment (but only when the attempted access is to set the bit
count). The security requirement for setting this content
property is the same as for writing into the segment; that is,
the effective access modes must include "w" permission.
The contents properties of a directory are the IACLs of the
directory, the list of names within the directory (but not the
entries they represent) and the quota cells for the directory.
The security requirement for getting these properties is that the
effective access modes must include "s" permission. The security
requirement for setting these properties is that the effective
access modes must include "m" permission.
The bit count (MSF component indicator) of a directory is also a
contents property of the directory (but only when the attempted
access is to set the bit count). The security requirement for
setting this content property is that the effective access modes
must include "m" permission if the bit count is to be decreased
(implying a decrease in the number of components in the MSF) and
the effective access modes must include "a" permission if the bit
count is to be increased (implying an increase in the number of
MSF components).
There are no contents properties for links.
5-2
Multics File System MDD-006
STATUS PROPERTIES
The status properties of an object are those properties
considered as belonging to the parent directory of the object.
These are the names and the ACL of the object. For links, the
link target is also a status property.
The security requirements for getting a status property for an
object is that the effective access modes on the containing
directory must include "s" permission. The security requirements
for setting a status property for an object is that the effective
access modes on the containing directory must include "m"
permission.
Accessing a status property of an object often requires that the
user be within the read bracket of the object for getting the
property and within the write bracket (or modify bracket) for
setting the property. The user need not have any specific ACL or
AIM relationship with the object.
ATTRIBUTE PROPERTIES
The attribute properties of an object are almost all other
properties. These are properties that the user is allowed to
access given access to the parent directory or access to the
object. The rational is that access to the object allows the
user to deduce these properties.
The security requirements for getting an attribute property of an
object are that the effective access modes on the parent
directory must include "s" permission or the effective access
modes on the object must be non-null. Attribute properties are
normally considered the same as status properties with respect to
setting them. Some, however, allow the setting of the property
if the effective access modes on the parent directory include "m"
permission or the effective access modes on the object include
"w" (or "m") permission.
Accessing an attribute property of an object often requires that
the user be within the read bracket of the object for getting the
property and within the write bracket (or modify bracket) for
setting the property. The user need not have any specific ACL or
AIM relationship with the object.
555...222 AAACCCCCCEEESSSSSS CCCOOOMMMPPPUUUTTTAAATTTIIIOOONNNSSS
The principle module concerned with determining a process' access
to an object is access_mode. It computes the access a process
has with respect to the ACL, optionally factors in the AIM
restrictions, and, optionally factors in the ring brackets.
5-3
MDD-006 Multics File System
access_modes determines the access to the root, since it has no
ACL (or directory entry, for that matter). The extended access
modes of the root are "sma" to the Initializer (that which has a
process id of tc_data$initializer_id) and "s" to everyone else,
independent of ring and authorization. The raw/authorization
segment access modes are "rw" to everyone. The effective segment
access modes are "rw" only when in ring 0.
Apart from the root, the Initializer is also given "rw"
authorization segment access to all directories and "sma"
extended access to all directories.
In the normal case, access_modes finds the ACL from the directory
entry and implements its own ACL match to determine the raw
access modes. Failure to match returns zero for both segment and
extended access modes, except for directories for which all
processes possess "rw" raw access.
The AIM test follows, if authorization or effective access was
desired. If this is a directory and the user has AIM dir
privilege, the raw access modes stand; if this is a segment and
the user has AIM seg privilege, the raw access modes stand.
Otherwise, the test proceeds through tests of read_write_allowed_
and read_allowed. (The read_write_allowed_ check is skipped if
the user does not have "w" raw mode on the segment or "ma" raw
mode on the directory). If the read_write_allowed_ check passes,
the raw modes stand. If not, the read_allowed_ test is made. If
this passes, the raw modes stand except that "ma" directory
access or "w" segment access is forced off.
If neither the read_write_allowed_ AIM test nor the read_allowed_
AIM test pass, the user is given null access modes. The
exception to this is for multi_class (as declared in the
directory entry) segments whose execute bracket are zero or one.
For these segments, if a write_allowed_ pass succeeds, the raw
access modes stand.
The final tests made are when effective access is desired. For
segments, this involves a test of the segment ring brackets in
the directory entry. For directories, this involves a check,
first of the extended (directory) ring brackets to find the
extended access modes, and then the segment ring brackets to
determine segment access modes. The rules are: if the ring is
less than or equal to the "a" bracket, the extended modes stand.
If it is greater than the "s" bracket but less or equal to the
"a" bracket, "ma" access is deleted. Otherwise, the access is
null. For segment acess the rules are: if the ring is equal to
the "w" bracket, the access modes stand. If it is less than the
"w" bracket, "e" access is deleted. If it is greater than the
"w" bracket but less than or equal to the "r" bracket, "w" access
is deleted. Otherwise, if the ring is less than or equal to the
5-4
Multics File System MDD-006
"e" bracket, "rw" access is deleted. Finally, if the ring is
greater than the "e" bracket, all access is deleted.
Note that this routine uses usage_values to meter itself in
active_hardcore_data.
555...333 KKKNNNOOOWWWNNN SSSEEEGGGMMMEEENNNTTT AAACCCCCCEEESSSSSS MMMAAAIIINNNTTTEEENNNAAANNNCCCEEE
The authorization access computed by access_modes for a segment
within the address space is stored within the SDW for the
segment, as is the segment's ring brackets. This information is
maintained in the SDWs by segment control (actually by dc_find).
When the user's access to the segment is potentially changed, the
primitive performing the change requests that segment control
perform a "setfaults" (by calling setfaults). This segment
control primitive invalidates the SDW in every process that
references the segment, forcing a recomputation of access at the
next segment fault on this segment in each process. When
setfaults is called, change_dtem is also, to guarantee that the
dtem in the branch is advanced by at least one, for a reason
explained below.
The authorization access for segments is stored within the KST
entry for the segment. The file system uses this information to
optimize its computation of authorization segment access. While
a segment is connected to the process, the SDW access fields will
match these KST values. When the segment is not connected, it is
the KST values that are kept up to date. Any request for the
access modes of an initiated segment (via dc_find or via
fs_modes, the ring zero internal mode lookup routine) will
recompute the KST access fields if necessary. If the process'
access was changed to the segment, then the dtem within the KST
entry will not match that in the branch because of the previous
call to change_dtem. The access will be recomputed by calling
update_kste_access. The next connection (segment fault) made to
this segment will copy these values into the SDW. (Since the SDW
fields are updated only at seg_fault time, it is possible to
accurately audit the access a process has to a segment by
watching the setting of the SDW access fields.)
The authorization access of each directory within an address
space is also maintained within the KST entry for the directory.
Changing the dtem for a directory's directory entry is the
equivalent of calling setfaults for a segment. Before looking at
the access field for the directory in the KST entry, dc_find will
check to see if the dtem of the directory matches the dtem of the
directory when this access computation was made (as recorded in
the KST entry). If it does not, the access is recomputed with
update_kste_access. Since any file system operation upon a
directory or entry is done with the directory locked (but refer
to directory relocking strategy under file system mechanisms), it
5-5
MDD-006 Multics File System
is not necessary to have a literal equivalent to setfaults for
directories.
555...444 AAACCCCCCEEESSSSSS MMMAAANNNIIIPPPUUULLLAAATTTIIIOOONNN
The access control information pertenent to the three access
control mechanisms are maintained by three separate programs.
ringbr_ changes the ring brackets. acl and asd_ (old and new
style primitives) change the ACL. reclassify changes the access
class. These programs are described under the file system
primitives, and under file system mechanisms.
555...555 AAAIIIMMM FFFIIILLLEEE SSSYYYSSSTTTEEEMMM PPPRRRIIIVVVIIILLLEEEGGGEEE
The system maintains the notion of AIM privileges. These are set
via a call to the system_privilege_ gate. The enabling of a
certain AIM privilege causes the system to ignore AIM
considerations relative to the software mechanisms that would
relate to that privilege. There are two AIM privileges or
interest to the file system, seg and dir privilege. These
privileges are enabled and disabled by the program
set_privileges.
Enabling seg privilege causes the raw and authorization access
modes to all segments to be the same for the process. That is,
the process can read or write any segment independent of access
class. For this to work, as a start, access_mode recognizes the
seg privilege. Also, when seg privilege is enabled (or
disabled), all segments within the process have the dtem field in
their KST entries set and the segments themselves setfaulted
(within the process), so that access will be recomputed, as
described above.
A softer version of seg privilege, that applies to a single
segment, is to privilege initiate the segment
(system_privilege_$initiate). When a segment is privilege
initiated, this fact is recorded in the KST entry for the
segment. This flag is factored into access computations with
respect to the segment. The presence of the privilege initiated
flag is also considered by the truncate function. By the way,
enabling seg privilege will not setfault segments already
privilege initiated.
The dir privilege causes the raw and authorization access modes
for all directories to be the same for the process. That is, the
process can operate on any directory regardless of access class.
The dir privilege flag is respected by access_mode. Enabling (or
disabling) dir privilege sets the dtem field in all directories
KST entries to force access to be recomputed, as described above.
5-6
Multics File System MDD-006
555...666 AAATTTTTTEEEMMMPPPTTTEEEDDD AAACCCCCCEEESSSSSS VVVIIIOOOLLLAAATTTIIIOOONNNSSS AAAUUUDDDIIITTTIIINNNGGG PPPOOOLLLIIICCCYYY
For each attempted access of a property of an object, dc_find
(who finds the object) makes a series of access checks. If the
access requirements are not met, an access violation was
attempted. Attempted access violations are considered a security
auditable event. The auditing of these events is done by
access_audit_$log_entry_ptr, as invoked by dir_control_error
within dc_find.
dir_control_error determines the correct security offense. Not
only is this necessary so that the correct auditing message is
generated, but it is also necessary so as not to release too much
information to the user. After the correct offense is
determined, dir_control_error invokes the security auditing
procedure (access_audit_) if this process has been designated as
requiring such a security audit.
dc_find will either return an error code describing the point of
access failure (such as "Incorrect access on entry" or "Incorrect
access to directory containing entry") or a code expressing
failure to locate the desired entry. However, the code
"Insufficient access to return any information" may have to be
returned if the "name lookup policy" is not satisfied.
dir_control_error has entrypoints corresponding to the various
circumstances under which an attempted access violation is
detected. Each entry decides the circumstances under which
error_table_$no_info is returned.
For the append case, the access violation corresponds to a lack
of access in the directory (name duplication errors are handled
by name_existant). Failure to append is considered a failure to
look up the name being appended. Thus, error_table_$no_info is
returned if the user has null access to the directory into which
the object was being appended.
Failure to get/set an attribute property checks the access on the
parent directory and on the object. The user gets
error_table_$no_info only if the user has null access on both the
entry and the parent.
The status function is called only for the status_attributes
function of dc_find, in which the user is allowed to see both
status and attribute properties, attribute properties if the user
has attribute access and status properties if the user has status
access. The caller would call the attributes entry if the user
lacked access to see both sets of properties; dir_control_error
knows in this case that the user must have attributes access but
lack status access. So, error_table_$no_info would not be
returned in this case.
5-7
MDD-006 Multics File System
The name_existant and name_non_existant entries enforce the name
lookup policy as described below.
555...777 NNNAAAMMMEEE LLLOOOOOOKKKUUUPPP PPPOOOLLLIIICCCYYY
The basic policy regarding the determination of the correct
security offense (censoring the error code) is that the error
code returned to the user should inform the user of the user's
lack of access, but only if the user has sufficient access to
determine the existence of the object. The user is allowed to
know the existence of any object to which the user's effective
access modes on the object are non-null or to which the user's
effective access modes on the parent are non-null. Non-null
access on the object allows the user to initiate the object, thus
proving its existence. Possessing "s" access on the parent
allows the listing of the object's name; possessing "m" access
allows affecting the object; possessing "a" access allows
attempting to append another occurrence of the object, thus
sensing the existence of the object. When the object doesn't
exist, the user's effective access modes on the directory that
would have contained the object must be non-null for the user to
be allowed to know of the non-existence.
When the user lacks the ability to determine the existence of an
object, the returned error code is error_table_$no_info
("Insufficient access to return any information."). Otherwise,
the user receives the intended error.
The user must also be returned the error error_table_$no_info if
the user lacks access to determine the user's access to the
object (the user lacks access to the parent's parent). This is a
less restrictive test than the existence test and so it is not
explicitly performed.
This name lookup error policy also applies when a directory
within a pathname is a segment. This is considered an attempt to
determine the existence of the segment without access to the
segment.
Applying this name lookup policy to the file system object
appending function means that attempting to append an object is
interpreted as an attempt to determine the existence of the
object. Thus, the user must have non-null access to the
directory in which the append is being attempted to be informed
of the failure of an append operation.
The name lookup policy is enforced for attempted access
violations by the name_existant and name_non_existant entrypoints
to dir_control_error. name_existant is called when a name is
found, but is not the right type. Examples are when the name
corresponds to a name duplication at append time, or when a
5-8
Multics File System MDD-006
pathname is being found and a component of the pathname is
actually a segment. The user would be given error_table_$no_info
only if the user has null access on both the parent and against
the mis-typed entry. The name_non_existant entry is called when
the name to be found doesn't exist. The user sees
error_table_$no_info if the user has null access to the directory
that would have contained the name.
The name lookup policy is enforced for successful accesses by
virtue of passing the required access checks for the operation at
hand. For operations that have no explicit access check
(terminating a segment, for instance), the dc_find function
enforces the name lookup policy by looking for non-null access on
the object or the object's parent.
555...888 SSSUUUCCCCCCEEESSSSSSFFFUUULLL AAACCCCCCEEESSSSSS AAAUUUDDDIIITTT PPPOOOLLLIIICCCYYY
Since all access computations within the file system are made by
dc_find, dc_find is the obvious place to perform the auditing of
successful accesses. Indeed, once all access checks made by
dc_find have been made, dc_find performs the necessary auditing
of the granting of access. It is important to note that audit
messages are therefore generated at the point of access granting,
not at the point of completion of the operation in question.
This is done for two reasons. First, it is better
modularization. It is clearly better for one module (dc_find) to
perform all auditing, especially since it validated the access.
Second, it is possible that an attempted operation may fail for
some potentially obscure reason. It is better to audit that the
operation was started (access was granted) than to possibly fail
to audit later when the operation is half done.
This policy does create one problem: the creation of an entry.
When access is granted for object creation, the object does not
yet exist, so the audit message cannot properly refer to it. So,
object creation is doubly audited; once when creation access was
granted, and a second time when the object fully comes into
existence.
555...999 DDDEEETTTAAAIIILLLEEEDDD SSSEEECCCUUURRRIIITTTYYY PPPOOOLLLIIICCCYYY
This section lists all of the access controlled operations in
ring zero and the access checks performed.
555...999...111 AAAcccccceeessssss MMMooodddeee RRReeessstttrrriiiccctttiiiooonnnsss
For a segment, any combination of the three access modes ("r",
"e" and "w") may be given in an ACL term. Any combination of the
5-9
MDD-006 Multics File System
three directory access modes may be given in an ACL term ("s",
"m" and "a") except that "m" may not be given without "s".
555...999...222 GGGaaattteee AAACCCLLL rrreeessstttrrriiiccctttiiiooonnnsss
There are restrictions that apply to the ACL terms within the ACL
for a non-ring 0/1 gate. In particular, only the user's project
and the SysDaemon project may appear on such gates. The rule is
that the project names within the ACL terms must be either
SysDaemon or the project of the process setting the ACL terms.
The routine that performs this validation is check_gate_acl_. It
can be called in two ways; one with an actual ACL, as appears in
a directory, and one with a ACL structure as is supplied to asd_.
555...999...333 DDDiiirrreeeccctttooorrryyy CCCooonnnttteeennntttsss GGGeeettttttiiinnnggg
The access requirements for reading the contents of a directory
were described under contents properties, above. The dc_find
entrypoint used to perform this type of access is dir_read.
Specific examples of reading the contents of a directory are
given below.
ACCESS CLASS CHECK
The function access_class_check, called via system_privilege_,
validates the access class fields of the entries in a directory.
To do this, it internally lists the entries (contents) within the
directory and reads the access class fields.
IACL LISTING
The IACL of a directory are standard contents properties of a
directory. No extra requirements exist for listing the IACL for
lower rings.
EXAMINING A SUB-TREE FOR DELETION
A sub-tree can be deleted by the del_dir_tree function. Since
this function uses delentry to delete objects, it does not
enforce particular requirements for the deletion. It does,
however, internally lists the entries (contents) of the
directory.
5-10
Multics File System MDD-006
DIRECTORY ENTRY LISTING
A process may list the name space (and types) of all objects
within a directory if it meets the directory contents reading
access requirements. Such a process may also list the link
pathnames.
QUOTA GETTING
The segment and directory quota limit and quota used, as well as
the time-record product (trp) of a directory, contained in its
VTOCE, are considered to be contents properties of the directory.
555...999...444 DDDiiirrreeeccctttooorrryyy CCCooonnnttteeennntttsss SSSeeettttttiiinnnggg
The access requirements for modifying the contents of a directory
were described under contents properties, above. The dc_find
entrypoint used to perform this type of access is dir_write.
Specific examples of writing the contents of a directory are
given below.
IACL SETTING
The IACL for a directory can be set if the contents setting
access requirements are met. The IACL can only be set for rings
greater than or equal to the current validation level.
555...999...555 OOObbbjjjeeecccttt CCCooonnnttteeennntttsss SSSeeettttttiiinnnggg
The access requirements for setting the contents of an object
were given above. Specific special examples are given below.
BIT COUNT SETTING
The access requirements for setting the bit count of an object
were explained above. Note that the bit count of an upgraded
directory may not be set (except for ring 1 directories). Thus,
non-ring 1 multi-class MSFs are not allowed. The access checking
is done by the dc_find entrypoints obj_bc_write and
obj_bc_delta_write.
SEGMENT TRUNCATION
The process must possess "w" effective access on a segment to
truncate it (following the standard access requirements for
writing). Note, though, that auditing is not done when a
5-11
MDD-006 Multics File System
truncate is attempted on a segment whose copy switch is on. This
is because the truncate (write) would have been allowed if a copy
were to be made. Also, a truncate is allowed of segments that
were privileged initiated (allowing a method for truncating lower
ring objects). The dc_find entrypoint that applies is
obj_truncate.
555...999...666 SSStttaaatttuuusss PPPrrrooopppeeerrrtttyyy GGGeeettttttiiinnnggg
The access requirements for getting a status property of an
object were described above, under the description of status
properties. The dc_find entrypoint associated with this type of
access is obj_status_read. Specific accesses of this type are
given below.
ACL LISTING
Reading the ACL of an object requires "s" effective access on the
containing directory.
NAME LISTING
Listing the names of a specific entry (within the status_ or
status_long functions) requires "s" effective access.
555...999...777 SSStttaaatttuuusss PPPrrrooopppeeerrrtttyyy SSSeeettttttiiinnnggg
The access requirements for setting a status property were
explained above under the description of status properties. Such
accesses require a call to dc_find$obj_status_write, or
dc_find$obj_access_write for changes to access information.
Specific accesses to which this access model applies follow.
ACL SETTING
Adding or deleting terms from the ACL of an object is considered
to affect a status property of the object. The validation level
must be within the write (modify) bracket of the object.
RING BRACKET SETTING
Setting the ring brackets of an object has the same importance
has modifying the ACL. They are considered a status property
when set. The validation level must also be within the "w"/"m"
bracket of the object.
5-12
Multics File System MDD-006
FILE SYSTEM OBJECT RENAMING
The access rules for adding, deleting and renaming objects are
the access rules for setting status properties of the object.
The process' validation level must be within the write (modify)
bracket of the object (if a branch).
FILE SYSTEM OBJECT DELETING
To delete an object is considered to change a status property of
the object (its existence). The validation level must also be
within the write (modify) bracket of the target. (Also, the
safety and copy switches of the object must be off. If the
object is a directory, it must be empty. Attempting to delete a
non-empty upgraded directory is a covert channel auditable
event.)
MISCELANEOUS PROPERTIES
The properties that are considered as status properties when
setting are: copy switch (validation level must be within
"w"/"m" bracket of object); author and bit count author (no
validation level check); date-time dumped, used, modified and
entry modified (no validation level check); volume dump switches
(validation level check applies); safety switch (validation level
check applies); don't null zero page (dnzp) switch (no validation
level check applies); synchronized switch (validation level check
applies); max length (validation level check applies); son's
logical volume/rpv only switch (no validation level check
applies).
555...999...888 AAAttttttrrriiibbbuuuttteee PPPrrrooopppeeerrrtttyyy SSSeeettttttiiinnnggg
The access requirements for setting an attribute property were
explained above under the description of attributes properties.
The only property that is viewed as an attribute property when
setting is the damaged switch. No validation level requirements
exist on the target for the damaged switch.
555...999...999 AAAttttttrrriiibbbuuuttteee PPPrrrooopppeeerrrtttyyy GGGeeettttttiiinnnggg
The access requirements for getting an attribute property of an
object were described above, under the description of attribute
properties.
5-13
MDD-006 Multics File System
RING BRACKET GETTING
The ring brackets of an object not (necessarily) within the
address space may be viewed as an attribute property of the
object.
MISCELANEOUS PROPERTIES
The properties considered as attribute properties when getting
them are: date-time entry modified, date-time dumped, date-time
used, date-time contents modified, records used, logical volume
id, current length, bit count, copy switch, damaged switch,
synchronized switch, ring brackets, UID, object type, author, bit
count author, raw and effective access modes,
security-out-of-service flag, multiple-class switch, entry bound,
access classmaster directory flag, physical volume id, usage
count, volume dump switches, maximum length.
555...999...111000 FFFiiillleee SSSyyysssttteeemmm OOObbbjjjeeecccttt AAAppppppeeennndddiiinnnggg
Appending a file system object within a directory requires "a"
effective access on the directory. If a branch is being
appended, then it must normally be of the same AIM classification
as the parent directory. It must also have all of its ring
brackets be greater than or equal to the validation level. There
are a few exceptions. A directory with a specified terminal
quota may be created of a higher access class. Also, a
multi-class segment may be created but only in ring 1.
555...999...111111 IIInnniiitttiiiaaattteeeddd SSSeeegggmmmeeennnttt AAAttttttrrriiibbbuuuttteeesss
The process is allowed to ask for the ring brackets and current
effective access modes for any branch within the process' address
space for which the user's access modes are non-null, or for
which the user possesses "s" effective access on the parent
directory. These rules follow from reasoning what attributes the
process could determine by making test references to the segment.
The pathname of an initiated segment may be requested following
the rules of the name lookup policy. (This includes returning
the pathname of the current working directory or the search
rules.)
555...999...111222 LLLiiinnnkkk TTTaaarrrgggeeettt CCChhhaaasssiiinnnggg
The process can find the target of a set of links if either the
process has non-null effective access to the directory that does
(or would) contain the target or if the process has non-null
5-14
Multics File System MDD-006
effective access to the target. This is the standard name lookup
access policy.
555...999...111333 WWWooorrrkkkiiinnnggg DDDiiirrreeeccctttooorrryyy aaannnddd SSSeeeaaarrrccchhh RRRuuullleee SSSeeettttttiiinnnggg
To set a directory as the current working directory, the process
must either have non-null effective access to the directory or
non-null effective access on the parent (name lookup policy).
This same rule is followed when adding a directory to the search
rules.
555...999...111444 SSSeeegggmmmeeennnttt IIInnniiitttiiiaaatttiiiooonnn
The process is allowed to initiate any segment to which the user
possesses non-null effective access. Refer to the description on
segment activation for details of access revokation.
DYNAMIC LINKING
The resolution of a dynamic link into a target is a special case
of segment initiation. Indeed, the dynamic linker's search
facility (fs_search) attempts to initiate the desired named
object in each directory in the search rules. If the object
exists, the normal access checks of segment initiation will be
used. If the segment succeeds in being initiated, this is fine.
If the segment is found but the user lacks access to the segment,
the searching stops. If the segment exists but is invisible
(according to the name lookup policy), searching continues.
Also, if the segment doesn't exist in the given search directory,
searching continues.
The segment will not exist within most (if not all) of the
directories within the search rules. As such, it is undesirable
to apply (i.e., spend cpu time) enforcing the name lookup policy
for each directory. So, failures to find a segment within a
directory when trying to initiate the segment for the dynamic
linker automatically return error_table_$no_info, even when the
user might possess access to see the non-existence. Since the
dynamic linker is only interested in cases where the initiate
succeeds, this lack of information (whether the user can see the
non-existence) has no affect. Since dc_find is passing out less
information in this case, not more, there is no security
implication of this optimization.
555...999...111555 SSSeeegggmmmeeennnttt TTTeeerrrmmmiiinnnaaatttiiiooonnn
The process may terminate any segment within the address space
not known in other rings. The process may terminate any segment
5-15
MDD-006 Multics File System
by pathname only if the process has access to see the existence
of the segment (name lookup policy).
555...999...111666 MMMaaasssttteeerrr DDDiiirrreeeccctttooorrryyy QQQuuuoootttaaa SSSeeettttttiiinnnggg
Setting the quota on a master directory requires "m" raw access
to the directory. The validation level must also be within the
"m" bracket of the directory. This operation is done within
master directory control and has its own AIM rules enforced by
master directory control itself, and the master directory
creation function of append.
555...999...111777 QQQuuuoootttaaa MMMooovvviiinnnggg
To move quota between a directory and its parent, the process
must have "m" effective access to the parent and "m" effective
access on the directory itself. (Actually, the process must have
"m" raw access on the directory, the validation level must also
be within the "m" bracket of the directory and the directory must
be of the same access class as the user or be strictly upgraded.
Lower authorization processes are allowed to give quota to (but
not take it away from) higher authorization directories. Higher
authorization processes cannot move the quota back.)
555...999...111888 OOObbbjjjeeecccttt RRReeeccclllaaassssssiiifffiiicccaaatttiiiooonnn
Performing a reclassify operation (correcting the access class of
an object) requires "m" raw access on the object's parent
directory. (It is not meaningful to make an AIM check in this
case, since the AIM classification of the object is in doubt.)
555...999...111999 NNNooodddeee RRReeeccclllaaassssssiiifffiiicccaaatttiiiooonnn
Reclassifying the contents of a directory and the directory
itself requires "m" raw access on the parent of the directory.
This is for the same reason as for the object reclassification
function. It is also necessary to have "s" access on the target
directory (to be able to list the objects to be reclassified) and
"m" access (to be able to reclassify the objects). This "sm"
check is also a raw check since the AIM classes are questionable.
555...999...222000 VVVooollluuummmeee RRReeetttrrriiieeevvviiinnnggg
The access checks performed by the volume retriever, before it
"copies" data into the target segment or directory, are performed
within ring zero. The access requirements are "rw"/"sm"
effective access on the target for the user requesting the
5-16
Multics File System MDD-006
retrieval or "sm" effective access on the parent directory for
the user requesting the retrieval.
555...999...222111 SSSeeegggmmmeeennnttt CCCooonnnnnneeeccctttiiiooonnn
The access modes that a process possesses to a segment are found
within the segment's SDW within the process. These access fields
are maintained by segment control within the KST entry, and are
copied into the SDW by dc_find. A segment is not allowed to be
added to a process' address space unless the process possesses
non-null effective access to the segment (see segment initiation,
below). However, it is possible for access to be deleted from
the segment while the process has the segment initiated. When
the user still possesses some access to the segment but not
enough for the machine operation at hand, the standard fault
mechanism will audit the access violation and return the normal
error code to the user. When the authorization access modes
become null (which required that the segment was previously
setfaulted from the address space), seg_fault (actually, dc_find)
will refuse any attempt to re-activate the segment (for this
process). The seg_fault entry of dc_find will audit this
occurrence and determine the user error code. If the returned
error code is error_table_$no_info, this can be interpreted to
mean that the process lacks access to see the access. Note,
also, that such a seg_fault can be interpreted as an attempt by
the user to determine the state of existence of the segment. If
the segment was deleted and the process lacks access to the
parent that previously contained it, error_table_$no_info will be
returned. This censoring of the seg_deleted code from sum
follows the name lookup policy rules applying to the use of sum.
Refer to segment pointer to entry translation for more details.
555...999...222222 GGGaaattteee DDDeeefffiiinnniiitttiiiooonnn GGGeeettttttiiinnnggg
By normal access rules, the definitions for a gate would not be
readable from the user ring, since the read bracket for a gate
would be lower than the user's ring. However, it is desirable
for the user to be able to read out the definitions for a gate;
this is not privileged information since the user is allowed to
call the gate (assuming proper access). So, an obscure function
of dc_find is to allow this. This is done by translating the
user supplied object pointer (which would have the user's ring in
it), into a pointer to the object within the ring within which
the definitions may be read (the read bracket). The caller of
obj_linkage_ring_ptr (within ring 0) actually reads the
definitions for the user.
5-17
Multics File System MDD-006
SECTION 6
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.
666...111 PPPAAATTTHHHNNNAAAMMMEEE TTTOOO EEENNNTTTRRRYYY TTTRRRAAANNNSSSLLLAAATTTIIIOOONNN
dc_find performs all pathname to entry translations, as described
under "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. 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 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.
6-1
MDD-006 Multics File System
For the link target lookup function, find_entry will find
anything. If a 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 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 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, 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.
666...222 SSSEEEGGGMMMEEENNNTTT PPPOOOIIINNNTTTEEERRR TTTOOO EEENNNTTTRRRYYY TTTRRRAAANNNSSSLLLAAATTTIIIOOONNN
The translation of a segment pointer into the corresponding entry
pointer is done by sum (segment utility module). This function
is used internal to 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 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
6-2
Multics File System MDD-006
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, 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 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.
666...333 UUUIIIDDD PPPAAATTTHHH TTTOOO EEENNNTTTRRRYYY TTTRRRAAANNNSSSLLLAAATTTIIIOOONNN
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 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.
6-3
MDD-006 Multics File System
666...444 SSSEEECCCUUURRRIIITTTYYY FFFUUUNNNCCCTTTIIIOOONNNSSS
The principle security related function within hardcore is
imbedded in dc_find. This module makes all security decisions
within ring zero. It performs all security related auditing.
Its operation is described in the section on access control.
The master module for determining access to objects is
access_mode. It 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 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 a gate appears in the section on access control.
update_kste_access is called by fs_modes and dc_find when it is
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).
666...555 AAACCCLLL TTTEEERRRMMM MMMAAANNNIIIPPPUUULLLAAATTTIIIOOONNN
Matching of a group id against an ACL list is performed in two
places. 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 "*"
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.
6-4
Multics File System MDD-006
The standard low-level operations upon an ACL are performed by
acl_. It 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 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 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.
666...666 DDDIIIRRREEECCCTTTOOORRRYYY SSSPPPAAACCCEEE MMMAAANNNAAAGGGEEEMMMEEENNNTTT
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
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.
6-5
MDD-006 Multics File System
666...666...111 AAAcccccceeessssss NNNaaammmeee MMMaaannniiipppuuulllaaatttiiiooonnn
The access_name structures within a directory are maintained by
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.
666...666...222 HHHaaassshhh TTTaaabbbllleee MMMaaannniiipppuuulllaaatttiiiooonnn
The hash table within a directory is maintained by hash. hash
performs the usual hash functions. There are two interesting
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 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 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.
666...777 UUUSSSAAAGGGEEE OOOFFF DDDCCC_FFFIIINNNDDD
File system primitives must call dc_find to locate a directory or
a 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 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
6-6
Multics File System MDD-006
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.
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;
6-7
Multics File System MDD-006
SECTION 7
DATA STRUCTURES WITHIN ADDRESS AND
NAME SPACE MANAGEMENT
The main data structures within address and name space management
are the KST (known segment table) and the RNT (reference name
table). The KST is a hardcore (and ring 0) data structure that
maps segment numbers for non-hardcore segments into their
location within the hierarchy. The RNT, which exists once per
ring within the linkage area for that ring, provides a mapping of
reference names (dynamic linker search names) to segments within
the process, for that ring.
777...111 TTTHHHEEE KKKSSSTTT
kst_seg (the KST) is actually divided into three areas (other
than the KST header). These are the KST entries themselves, the
private logical volume connection table and the KST UID hash
table.
The logical volume connection table lists the LVIDs for any
private logical volumes attached to the process. This list is
maintained by private_logical_volume, and is not discussed here
further.
The UID hash table is a hash table used in conjunction with UID
hash threads maintained within the KST entries themselves. The
hash is to take the mod of the UID against the hash table size.
These hash threads are used by kstsrch to optimize address space
searches. When a segment is to be made known, kstsrch looks up
the segment's UID (from its branch) with these threads as a quick
way of determining if the segment to be made known is already
known.
Each KST entry represents one known, non-hardcore segment within
the address space. These KST entries are critical to maintaining
the notion of the contents of the address space. The KST entries
are threaded by their UID hash values, as mentioned above. Free
KST entries are threaded into one list.
7-1
MDD-006 Multics File System
777...111...111 KKKSSSTTT EEEnnntttrrriiieeesss
The fields within a KST entry are explained below.
kste.fp
is either the relative pointer (within the KST) to the next
KST entry whose UID hashes to the same hash value as does
the UID of this segment, or it is the relative pointer to
the next free KST entry, if the segment number corresponding
to this KST entry does not correspond to a known segment.
kste.segno
is the segment number corresponding to this KST entry.
Although KST entries form an array, and hence their segment
numbers are inherently known, references to KST entries
found via their hash threads use this field to find the
corresponding segment number.
kste.usage_count (0:7)
records the extent to which a segment is "referenced" within
the process. The value (for each ring) is the number of
outstanding initiations within that ring. That is, when the
usage count for a ring hits zero, the segment is not
considered known in that ring. (Actually, only when all
usage counts become zero does the segment become unknown.)
These values are used to know when to terminate a segment
from the address space. Also refer to KST garbage
collection.
kste.entryp
is a pointer to the directory entry for the segment. This
value is null for the root. Note that the directory that
contains this entry is most likely unlocked at any time that
this entry pointer is being referenced, and so the pointer
| is not guaranteed valid. To get a pointer to the directory
| entry associated with the KST entry, you must call
| sum$getbranch or sum$getbranch_root_my to lock the
| containing directory and get a validated pointer to the
| directory entry. The directory must remain locked for
| reading during the period in which the directory entry is
| being referenced. If you only need a pointer to the
| containing directory, you can use ptr(kste.entryp,0) without
| calling sum.
kste.uid
the UID of the segment. This is "777777777777"b3 for the
root.
kste.access_information.dtbm
the last time that this process noticed that the branch was
modified. This value is used in conjunction with the
corresponding field in the directory entry to determine when
access may have changed; refer to the maintenance of access
under access control for the maintenance and use of
kste.access_information.
kste.access_information.extended_access
extended access from the branch
7-2
Multics File System MDD-006
kste.access_information.access
"rew" authorization access computed from the branch
kste.access_information.ex_rb
ring brackets from branch
kste.flags.dirsw
TRUE if the segment is a directory
kste.flags.allow_write
FALSE if initiated without write permission. This is used
to mask out write permission that would otherwise be given
by the branch.
kste.flags.priv_init
TRUE if the segment was privileged initiated. The presence
of this bit overrides AIM computations for this segment; it
also allows truncations to be performed on the segment
independent of AIM.
kste.flags.tms
(transparent modify switch) causes modifications of the
segment to not set the DTCM field in the ASTE (by virtue of
the propogation of this bit into the ASTE at segment
activation). Note that any process connecting to the
segment without this flag, however, causes modifications to
start recording. This flag is set for all directories;
refer to recording directory modifications for details.
kste.flags.tus
(transparent usage switch) causes usage of the segment to
not set the DTU field in the ASTE (by virtue of the
propogation of this bit into the ASTE at segment
activation). Note that any process connecting to the
segment without this flag, however, causes usage to be
recorded.
kste.flags.tpd
(transparent paging device) obsolete
kste.flags.audit
obsolete
kste.flags.explicit_deact_ok
indicates a willingness to allow explicit deactivation of
this segment via force deactivation. This bit is propogated
into the ASTE at segment activation; any process connecting
to this segment without this bit set defeats the ability to
explicitly deactivate the segment.
kste.infcount
for segments, this is the LV index (within the logical
volume connection table); for directories, this is the
inferior count. The inferior count is used to protect
directories with active inferiors from KST garbage
collection.
777...222 TTTHHHEEE RRRNNNTTT
The reference name table provides the ability of a process to
establish an arbitrary number of names with a segment. These
7-3
MDD-006 Multics File System
names are used by the dynamic linker when processing the
"initiated segments" search rule. The establishment of reference
names (usually for object segments) allows these segments to be
found without knowing the pathnames.
The RNT is a per ring data structure. This is necessary so that
user ring software cannot confuse lower ring subsystems. The RNT
for a given ring appears in the linkage area for that ring. It
is allocated by makestack, when makestack creates the stack for
the given ring. The RNT consists of a header and the RNT
entries. The header contains a pointer to the area in which RNT
entries are allocated as well as a pointer to the search rules
for that ring. The header also contains a hash table (threaded
through the RNT entries themselves) for providing quick lookups
of RNT entries given either a reference name, or a segment
number.
777...222...111 RRRNNNTTT EEEnnntttrrriiieeesss
Each RNT entry contains one reference name for one segment. The
RNT entries are threaded together by two hash threads, one for
segment number hashing and one for reference name hashing. The
entry contains the segment number of the segment, and the
reference name and length. The length of the RNT entry is the
minimum needed for the given reference name.
RNT entries are maintained by the program ref_name_. Details can
be found in the section on address and name space management.
7-4
Multics File System MDD-006
SECTION 8
ADDRESS AND NAME SPACE MANAGEMENT
The functions of address and name space management are to enter
segments 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) as its main data structure describing the process'
address space. The 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.
888...111 SSSEEEGGGMMMEEENNNTTT IIINNNIIITTTIIIAAATTTIIIOOONNN///MMMAAAKKKIIINNNGGG KKKNNNOOOWWWNNN
The process of adding a segment to the address space is the
process of "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 system primitive
associated with initiating a segment. The major activity to be
performed is to translate a pathname into a directory entry. The
8-1
MDD-006 Multics File System
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
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 segment fault on it will work.
kstsrch is first used to see if the segment is already known. If
so 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 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
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 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,
8-2
Multics File System MDD-006
though, so it can become deactivated, but this is unlikely before
directory control will get around to referencing the directory.)
888...222 SSSEEEGGGMMMEEENNNTTT UUUSSSAAAGGGEEE CCCOOOUUUNNNTTTSSS
When a segment or directory is initiated, the "usage count" for
the 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 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 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 protect the segment from "KST garbage collection".
Refer to the section on KST garbage collection later in this
section.
888...333 SSSEEEGGGMMMEEENNNTTT TTTEEERRRMMMIIINNNAAATTTIIIOOONNN///MMMAAAKKKIIINNNGGG UUUNNNKKKNNNOOOWWWNNN
The opposite counterparts to the initiate/makeknown functions are
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_. The makeunknown function performs the disassociation
of a KST entry with a 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)
8-3
MDD-006 Multics File System
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 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, unthreading the segment's KST
entry (making it free), and setfaulting the segment.
888...444 RRREEEFFFEEERRREEENNNCCCEEE NNNAAAMMMEEE MMMAAANNNIIIPPPUUULLLAAATTTIIIOOONNN
The RNT for a given ring is found via the rnt_ptr in the stack
header for 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 entries to add a new reference name/segment number pair
(a RNT entry) to the 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.
888...555 FFFUUUNNNCCCTTTIIIOOONNNSSS FFFOOORRR DDDIIIRRREEECCCTTTOOORRRYYY CCCOOONNNTTTRRROOOLLL
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.
8-4
Multics File System MDD-006
888...555...111 SSSeeegggmmmeeennnttt PPPoooiiinnnttteeerrr tttooo PPPaaattthhhnnnaaammmeee TTTrrraaannnssslllaaatttiiiooonnn
get_pathname_ returns a pathname given a segment number. For
segment 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 containing this entry.
After all of this work, the pathname found is put into 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.
888...666 KKKSSSTTT MMMAAAIIINNNTTTEEENNNAAANNNCCCEEE FFFUUUNNNCCCTTTIIIOOONNNSSS
Address and name space management contains several KST
maintenance utilities.
get_kstep takes a segment number and returns a pointer to the KST
entry 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 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 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 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 to no
8-5
MDD-006 Multics File System
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 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.
set_256K_switch sets the value kst.allow_256K_connect. The only
trick is 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 hash value) for an object, given its UID.
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 segment use attributes in a KST entry. phcs_ users
can set allow_write, explicit_deact_ok, tpd (transparent paging
device (obsolete)) and audit (obsolete). hphcs_ users can also
set tms and tus (transparent modify/usage). Changing the
allow_write attribute is also reflected in the SDW via a
setfaults$disconnect.
888...777 KKKSSSTTT GGGAAARRRBBBAAAGGGEEE CCCOOOLLLLLLEEECCCTTTIIIOOONNN
The KST, at any given time, has a certain size. At a given time,
it can 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.
8-6
Multics File System MDD-006
This limitation can become a problem with respect to directories.
Most 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 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 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.
8-7
Multics File System MDD-006
SECTION 9
FILE SYSTEM PRIMITIVES
The file system primitives described in this section are those
that are (for the most part) directly callable from the user ring
via a gate entry. These primitives implement the various file
system functions (ACL listing, object deletion, address space
manipulation, etc). They make heavy use of the facilities of
directory control and of address and name space management, as
discussed in the previous sections.
999...111 AAAIIIMMM RRREEELLLAAATTTEEEDDD PPPRRRIIIMMMIIITTTIIIVVVEEESSS
There are only two AIM related primitives. access_class_check,
which validates a directory, and reclassify, which can change the
access class of objects.
999...111...111 AAAcccccceeessssss CCClllaaassssss CCChhheeeccckkksss
The primitive access_class_check sets the soos (security out of
service) switch off for an object that meets the various AIM
restrictions. These checks are: the access class of all objects
must be equal to the containing directory, or the object must be
multi-class and must be of greater class than the directory and
in ring one (for segments) or have a terminal quota
(directories). Also, this directory must itself be equal to its
parent, or greater and have a terminal quota. If all succeeds,
it will turn off soos. If it fails, it turns it on.
999...111...222 AAAcccccceeessssss CCClllaaassssss SSSeeettttttiiinnnggg
reclassify is the privileged routine that changes the access
classes for objects.
The common routine setup finds the object in question and the
access classes. It finds the object and the parent. The logical
volume for the object is found, not only to check for mountedness
but to ensure that its AIM limits allow the new classification.
9-1
MDD-006 Multics File System
The branch entry reclassifies an object to the class of its
parent. The access class of the parent (found in setup) is set
for the son. Also, the son's multi-class attribute is forced
off. Normal termination then proceeds.
Changing the access class of the object involves changing the
directory entry (requires the directory being write locked) and
changing the VTOCE. For this, this program must lock the AST,
fetch the VTOCE, patch the access class and output the VTOCE.
change_dtem is called to reflect this access change. If any of
this fails, the soos switch is turned on for the son.
sys_seg changes a segment to be multi-class. After a few checks,
the access class is patched in, as well as the multi-class bit.
In this case, normal termination involves unlocking the parent
directory and performing a setfaults on the son (to pick up
access class change). sum$dirmod is called.
The node entry changes the access class of a directory and its
contents. The process must have "sm" access to the directory for
this to work, since this operation implies a directory name list
function, as well as a reclassify function. The quota limit is
obtained for this directory, so reclassify can later check for
the presence of terminal quota. (In particular, if the directory
is an upgraded directory, it must have a terminal quota account.)
The parent directory is unlocked at this time, even though it
will be needed later, to avoid holding it so long. The parent
directory can be easily relocked later via sum. The directory is
traversed, forcing the access class (and reseting the multi-class
status) of all segments who are not multi-class segments of
higher class than requested; for sub-directories, those equal to
the access class have their multi-class status reset, those
greater are set, and those less are set security out of service.
A separate loop makes sure that all upgraded sub-directories have
quota accounts; otherwise, they are set soos. This finishes the
directory (after sum$dirmod). For the parent, though (who was
locked earlier when the main directory's access class was set),
reclassify makes the parent dir soos if it had an error setting
the class for a sub-ordinate segment.
999...222 AAACCCLLL PPPRRRIIIMMMIIITTTIIIVVVEEESSS
There are two sets of ACL primitives. The module acl implements
the old style primitives. The old style primitives had no
concept of IACLs. They also merged the setting of ring brackets
with the setting of ACL terms. asd_ and friends implement the
new style calling sequence primitives.
9-2
Multics File System MDD-006
999...222...111 OOOlllddd---ssstttyyyllleee PPPrrriiimmmiiitttiiivvveeesss
acl implements the old-style ACL primitives. The actual work on
ACL terms is performed by acl_.
In the add side, there are two entrypoints, aadd to add a list of
ACL terms and a1add to add a single ACL term. a1add creates a
single element array of ACL terms from its arguments and joins
the common code for ACL term addition. The code finds the
appropriate directory entry, checks access modes, flags the
directory as being modified, adds the ACL terms and then cleans
up after itself.
The areplace entrypoint replaces an entire ACL with another. It
basically finds and locks the directory, deletes the old ACL,
adds the new and then cleans up.
The entrypoint adelete deletes terms from an ACL. In this
entrypoint, a count of -1 means that all ACL terms are to be
deleted. The internal routine delete_acl performs the deletion.
Of course, these ACL changing primitives must call change_dtem
and perform a setfaults on the segment.
ACL listing is done by alist. Internal routines list_acl and
list_acl_entries perform the listing, with the directory locked
for reading only. Listing is performed into internal areas to
avoid area problems. After the directory is unlocked, the ACL is
copied to the user area, with an area handler set up if such an
area needed to be allocated.
999...222...222 NNNeeewww---ssstttyyyllleee PPPrrriiimmmiiitttiiivvveeesss
asd_ contains the new style ACL primitives, the actual work on
ACLs being performed by acl_. asd_ contains numerous entrypoints
for listing, deleting, replacing and adding ACL terms to ACLs.
The list group consists of: list_idall (IACL for dirs),
list_dall (ACL for a dir), list_isall (IACL for segs) and
list_sall (ACL for a seg). Also present are entrypoint beginning
with r_, which perform the same function as the non-r_
entrypoints but work with structures having refer extents. The
actual work is performed by two internal routines, one for when a
specified list of terms is desired (and the place for such ACL to
be returned is therefore supplied) and one for when the entire
ACL is desired, requiring the allocation of said list in the user
supplied area, using the standard area return mechanism. But
first, the directory is found, access checked and locked. For
IACLs, the directory itself is found. For normal ACLs, the entry
pointer is found. The ACL start pointer is found and the
internal listing routines are called. The directory is unlocked.
9-3
MDD-006 Multics File System
If the ACL count is zero, various kludges are applied to the
returned lists to form valid pl1. In particular, a one element
array specifying its extent (to the user) as zero is allocated.
The delete, add and replace (ACL and IACL terms) entries all
merge into one common code path. These entries consist of:
del_identries (delete IACL for dirs), del_dentries (delete ACL
for a dir), del_isentries (delete IACL for segs), del_sentries
(delete ACL for a seg), replace_idall (replace IACL for dirs),
replace_dall (replace ACL for a dir), replace_isall (replace IACL
for segs), replace_sall (replace ACL for a seg), add_identries
(add IACL for dirs), add_dentries (add ACL for a dir),
add_isentries (add IACL for segs) and add_sentries (add ACL for a
seg).
The directory is found and locked for writing; it is flagged as
being in the process of being modified. If the ACL being
modified is the ACL of an object, the dtem of the object is
changed (change_dtem).
For deletion of ACL terms, it is a simple matter to iterate over
the supplied ACL terms, splitting them (acc_name_$elements) and
use acl_$del_entry to delete the term. The ACL counts are
maipulated also.
The replace and add entries come next. It starts with the usual
check for valid projects in ACL terms for non-ring 1 gates
(check_gate_acl_). For the replace entries, the old ACL is first
deleted. The SysDaemon ACL is put back if so indicated by
arguments. For add or replace, the input ACL is iterated over,
taking each term, copying it, taking it apart and adding it to
the entry's ACL. The ACL term counts are updated.
After this, the entry is setfaulted (unless IACLs are being
manipulated) and the directory unlocked.
Since the input list of ACL terms to add/delete/replace is
variable extent, it is necessary to reference it with the
directory locked. As a result, any random fault may occur during
the changing of the ACL. Because of this, all such operations in
asd_ run with an any_other handler enabled. (Note that the old
style primitives do not need this, since they copied all (limited
size) input structures into stack space before locking the
directory.) This any_other handler provides a cushion, so that
errors return to the user as an error code (error_table_$argerr)
rather than a crawlout. The critical reason for the any_other
handler, though, is that asd_ must ensure that a setfaults is
done on the target segment, even if the ACL update does not
finish, since an aborted operation may have partially changed the
ACL.
9-4
Multics File System MDD-006
Aside from acl and asd_, a primitive between the old and new
styles is list_inacl_all. This primitive returns all IACLs (seg
and dir) for all rings for a directory. The code is standard for
directory control. It uses the same dc_find functions and return
area management techniques as asd_.
999...333 RRRIIINNNGGG BBBRRRAAACCCKKKEEETTT PPPRRRIIIMMMIIITTTIIIVVVEEESSS
ringbr_ performs the user callable ring bracket getting and
setting functions. It involves a simple matter of validating
input arguments, finding and locking the directory and then
getting/changing the values. Of course, if the object is being
made a gate, it must perform a check_gate_acl_. Also, the ring
brackets of data management objects (as specified by performing a
vtoc_attributes$get_info to get the synchronized flag) must
follow those rules. The dtem of the directory must be updated
(change_dtem; also sum$dirmod must be called at the end). Also,
setfaults must be called upon the object. (Refer to the section
on directory control mechanisms.)
999...444 NNNAAAMMMEEE LLLIIISSSTTTIIINNNGGG
The star name matching primitives for the file system are
implemented within star_. The entrypoints are: star_ (normal)
and star_priv (privileged entry) (perform a "normal" type list);
list_dir ("dc_pack" type list); list_dir_fast ("fast" "dc_pack"
type list); dir_list_ ("fast" "star_list" entry); list_
("star_list" entry); list_priv ("star_list" privileged entry).
A privileged entry is one in which "s" access is not needed on
the directory to be listed.
A "fast" list is one in which the VTOCE's of the individual
objects are not needed to satisfy the request. If this is not a
fast list, the sons_lvid (as specified in the dir header) must be
mounted.
A "star_list" entry returns a greater amount of information about
each object (the difference between star_entry and
star_list_branch or star_list_link in star_info.incl.pl1).
A "dc_pack" operation returns even more information, in a format
for backup. (See dc_pack.incl.pl1.) A "dc_pack" operation
always matches **.
Either way, the star name is examined and the types of objects to
match determined. The usual mechanisms are used to find and lock
the directory, checking access. Since the star list function
returns a variable extent structure, the area return management
policy is used.
9-5
MDD-006 Multics File System
The internal entry MAKE_ENTRY_LIST counts the objects that match
the desired star name. It special cases non-star names and makes
a call to hash$search for efficiency.
The internal routine RETURN_INFO drives the placement of the
desired information into the allocated structures. It calls
vtoc_attributes$get_info, if necessary, to get VTOC resident
information. It then calls the routines that copies the desired
data into the allocated structures, either RETURN_DCPACK_INFO or
RETURN_STAR_INFO.
999...555 FFFIIILLLEEE SSSYYYSSSTTTEEEMMM OOOBBBJJJEEECCCTTT CCCRRREEEAAATTTIIIOOONNN
append is the master routine for creating new file system
objects. It is also used by the volume retriever/segment
adopter. Entrypoints are: master_dir, retv, create_branch_,
branchx, branch and link.
The first step is the getting of the various attributes of the
new entry. These are set via arguments and defaults. When a
branch is being appended, the access modes of the new branch must
also be determined from the arguments.
dc_find ensures that the object doesn't exist in the process of
finding the target directory. The access checks for appending
appear there.
The directory is locked for writing. The tree depth of the
directory is found; if a new directory is being appended, the
maximum hierarchy tree depth cannot be exceeded. For retv calls,
it is necessary to make a check against the UID of all branches
in the directory. Either way, a hash search for the new name is
performed; it is not allowed that it be found. If a segment is
being appending, the target logical volume must be mounted. A
UID is found for the segment (this is an supplied argument for
the retv entry). With the directory locked and flagged as in
progress of modification, the object can now be appended.
Links are easy. Simply figure out how much space it will need,
allocate it (fs_alloc$alloc) and fill it in.
Branch appending is as follows. The IACL for the object is found
(directory vs segment vs validation level). For segments, if the
new object is a non-ring 1 gate, the IACL (combined with the
user_acl term) must be valid (check_gate_acl_). A directory
entry is allocated (fs_alloc$alloc) and its base filled in.
(This is just copied from the supplied entry for the retv entry).
The ACL is added. This consists of adding the service_acl term
and then adding each term of the IACL and then the user_acl term.
(For a cross retv operation, the user_acl is not added. If this
9-6
Multics File System MDD-006
is a retv operation but not a cross retv operation, no ACLs are
added.)
For any type of object, the supplied name is added to it and
hashed in. The various other directory entry values are filled
in.
For branches, a VTOCE is now obtained (create_vtoce). Its VTOCE
index is placed in the directory entry for the new branch. If
this is a segment being created, finishing up consists of filling
in the directory entry and updating the directory's segment
count. If this is a directory being created, the internal
routine setup_directory comes into play. This routine sets the
same sort of information as for segments. It, however, wants to
initialize the new directory.
To setup a new directory, the directory into which the entry was
just appended is set as not within modification. (This is to
avoid possible problems with lock claiming the parent needs
salvaging). makeknown_ is called upon the new object. The quota
is checked before the new directory is touched. The new
directory header is filled in, a hash table created, etc. Quota
supplied is moved to it, unless this is a master dir creation in
which quota$append_mdir_set comes into play. If the priv_mqsw
switch is on and the new access class is greater than the
directory into which this was appended, the soos flag is set
(which is what allowed us to create this directory for the retv).
This new directory is flagged as modified (sum$dirmod) and made
unknown. The directory into which this directory was appended is
re-flagged as currently undergoing modification, and normal
append finishing is run.
Note that the setup described above is not performed for the
cross retv operation, who will later supply the directory/segment
contents.
The final step is to thread this new object into the directory
lists, flag the directory as modified (sum$dirmod) and unlock
this directory.
The file system call hcs_$make_seg calls make_seg, which simply
calls append$branch and then initiate_.
999...666 FFFIIILLLEEE SSSYYYSSSTTTEEEMMM OOOBBBJJJEEECCCTTT RRREEENNNAAAMMMIIINNNGGG
chname is the module for adding and deleting (and changing) names
on directory entries. It comes in three flavors, one (cfile)
which takes a directory and entry name, one (cseg) which takes a
pointer to an initiated segment and a retv entrypoint is supplied
with the directory entry pointer. The arguments are an old and
new name; if the old name is blank, this implies an addname of
9-7
MDD-006 Multics File System
the new; if the new name is blank, this implies a deletename of
the old; if both are supplied, this implies a rename. A check is
made to ensure that the only name on the entry is being deleted.
The first step is to add the new name, if present. It is hashed
into the directory (which checks for name duplication) and this
new name block is allocated and threaded into the list of names.
The old name is then deleted. A hash search for the name is
done, it is unhashed and threaded out of the entry's name list.
The name block is freed from the directory.
If the name being deleted was the primary name, this adds a
complication. The primary name is stored in the entry structure
itself. So, the old primary name must be removed, the next name
in the name list picked and threaded out, put into the entry
structure, and then hashed in its new location. Also, if the
primary name is deleted, the AST name table entry for this
segment must be changed.
If this object is a directory, the pathname associative memory
entries for the name are flushed.
The directory is cleared of its being modified state and
sum$dirmod notices the modification.
999...777 FFFIIILLLEEE SSSYYYSSSTTTEEEMMM OOOBBBJJJEEECCCTTT DDDEEELLLEEETTTIIIOOONNN
The logic involved in deleting a file system object is contained
within delentry. It has multiple entrypoints for calling from
the user ring through hcs_ and entries for ring zero operations.
The normal entrypoints are dfile and dseg, which take a
dirname/entryname pair and a initiated segment pointer,
respectively. There is also a priv_dfile entry, to set the
priv_entry flag, which bypasses access checking (among other
things). The priv_duid entry deletes an object given its UID
path. The retv entrypoint is used to bypass access checking.
Finally, the salv_delete_branch entry is used by the salvager to
delete a branch without thinking about its (bad) VTOCE.
The salv_delete_branch and retv entries supplied the directory
entry pointer for the object. All other entries must use dc_find
to find the entry and check access.
The type of the entry to delete is found. Links are easy and
bypass the following operations.
For branches, the user must be in the "w" or "m" brackets of the
object and the safety and copy switches must be off, except for
the retv and privileged entries.
9-8
Multics File System MDD-006
If this is a directory to be delete, it must be empty.
makeknown_ is used to activate the directory to be deleted. At
this time, the parent is unlocked. This is done since the son
will be locked, and the locking hierarchy requires the parent to
be unlocked at this time. The sub-directory is locked. If this
succeeds, the parent is relocked, rechecking access. Now the
directory can be checked for emptiness.
For segments, the volume containing them must be mounted. (Such
a check was unnecessary for directories.)
The VTOCE of the branch is deleted (delete_vtoce) freeing the
pages.
All entries join eventually. The entry is removed from the
directory. The name is hashed out. Its ACL is deleted. The
acc_name structure for the author and bit_count author are
deleted. The entry is unthreaded. If this is directory, then if
it is per-process, the pathname associative memory from here down
is flushed; otherwise, this entry is simply removed from the PAM.
sum$dirmod reflects the modification of the parent.
If this was the deletion of a directory, it is unlocked. (It was
kept locked so no one could create in it while it was being
deleted.) A side door to directory unlocking must be used to
unlock this directory, since it is no longer here. Final cleanup
proceeds as normal.
999...777...111 SSSuuubbb---tttrrreeeeee DDDeeellleeetttiiiooonnn
As a practical matter, most deletions of a set of objects, or of
a sub-tree, are performed via outer ring logic calling the file
system primitives repeatedly. This is especially necessary so as
to be able to delete mailboxes and the like. However, there is a
sub-tree deleting primitive used now and again. It is
del_dir_tree.
del_dir_tree deletes all entries in a directory. It is a
recursive program, recursing down the directory subtree to delete
objects in subordinate directories. The program is basically
viewed as a ring 0 star_list program, that uses delentry to
delete the objects it lists. Since one cannot delete an entry
(delentry or del_dir_tree$recurse) unless the directory is
unlocked, the directory is unlocked during the delentry call.
After each call, the directory must be relocked, validating
access. This is repeated until the directory is empty. During
the unlocked time a seg_fault_error handler is kept ready to
catch deletions of the directory.
9-9
MDD-006 Multics File System
Also, if the delete of the subordinate entry fails because of the
safety or copy switches being set, they are reset and another try
of the deletion made.
Deletion of subordinate directories containing other objects is
handled by recursing on del_dir_tree. If this fails because of
access, access is forced.
999...888 PPPRRROOOPPPEEERRRTTTYYY GGGEEETTTTTTIIINNNGGG PPPRRRIIIMMMIIITTTIIIVVVEEESSS
As mentioned in the section on access control, the properties of
file system properties are divided into three groups: status,
attribute and contents properties. The ACL status properties are
described above.
Various attribute properties of file system objects within the
address space, most notably the process' access to them, may be
obtained by fs_get. This access is computed basically from the
KSTE/SDW information (by dc_find).
Also present within fs_get are various ref_name asssociated
things. These include fs_get$seg_ptr, which simply calls
ref_name_$get_segno; fs_get$search_rules which copies, expanding
segment numbers into pathnames, the search rules from the RNT of
the given ring; fs_get$path_name which does a get_pathname_
(after enforcing the name lookup policy on the segment number via
dc_find); fs_get$ref_name which returns the nth refname (from
ref_name_$get_refnames); fs_get$trans_sw which returns (and sets)
pds$transparent; fs_get$get_link_target which simply calls the
link tracer in dc_find.
The status_ primitive is the usual target of attribute property
requests. It comes in various flavors, depending on the internal
variable status_call. The meaningful values are 0, ENTRY_status_
(1), ENTRY_status_long (2) and ENTRY_status_min (3). The
differences include, obviously, what function is performed. The
variable has other side effects, though. The values of 1 and 2
are used for the traditional status calls that return hoardes of
information. A value of 0 is used by entries like get_author. A
value of 3 is used by entries like get_safety_sw. The value of 0
requires "s" permission on the directory containing the object.
A value of 3 allows for "s" on the directory or non-null on the
object itself. For values of 1 and 2, not having "s" permission
but having non-null access on the object allows attribute
properties to be returned, but not status properties. The
general operation of the routine is straightforward. Note that
the main status entries use the return area mechanism described
under file system mechanisms for returning the entry's names.
9-10
Multics File System MDD-006
999...999 SSSEEEGGGMMMEEENNNTTT IIINNNIIITTTIIIAAATTTIIIOOONNN
initiate_ is the workings for hcs_$initiate and other related
calls. It is also used by certain ring zero primitives to make a
segment known in the process. Its entries are: initiate_ and
initiate_count (normal entries), priv_init and priv_init_count
(work with the equivalent of dir privilege and use raw versus
effective access mode), initiate_seg_count and initiate_seg (take
a directory pointer and entryname instead of the directory and
entry name).
dc_find finds the corresponding directory entry, checking for
non-null effective access. The object is checked to be on a
mounted logical volume.
Given the directory entry, an attempt is made to make the segment
known. The directory must remain locked while the segment is |
being made known, to ensure that the directory entry does not |
move or get deleted while makeknown_ and |
seg_fault$makeknown_activate reference the directory entry while |
activating the segment. When makeknown_ returns, the directory |
is unlocked. Refer to address and name space management for more |
details. |
The ref name supplied is added to the RNT (ref_name_$insert).
Finally, a check is made to see if the LOT for the given ring
must be grown to handle this new segment number.
Also present within initiate_ is an entry that doesn't actually
initiate the target, it just finds its directory entry and
decides (via a kstsrch) whether the segment is known to the
process. This is provided as an optimization for delete_, who
uses this information (the returned segment pointer) to decide if
the segment being deleted needs to be terminated (via term_)
before the deletion.
999...111000 SSSEEEGGGMMMEEENNNTTT TTTEEERRRMMMIIINNNAAATTTIIIOOONNN
User requests for segment termination are made to terminate_, the
inverse of initiate_. It consists of basically just a call to
makeunknown_, after the name lookup enforcement done by dc_find.
It will also zero the LOT entry for the segment, and delete the
refnames for the segment. Refer to address and name space
management for more details.
999...111111 DDDYYYNNNAAAMMMIIICCC LLLIIINNNKKKEEERRR SSSUUUPPPPPPOOORRRTTT
Although the operation of the dynamic linker is beyond the scope
of this manual, the file system support for dynamic linker
searches is described here. fs_search performs the work of
9-11
MDD-006 Multics File System
finding an object given the search rules. Since this module is
the user of search rules, it is also the keeper of the working
directory, which is maintained with the get_wdir and set_wdir
entrypoints. The operation is a simple matter of testing each
search rule.
Before trying any search rules, though, fs_search makes a test
reference of the stack for the ring of validation. This is done
so as to force the invocation of makestack, if this is a new
ring, so that the RNT and search rules will be initialized.
For real directory search rules, this module finds the directory
given the segment number. (Two tests are performed for validity.
Since search rules are saved by directory segment number, and the
directories in question can be terminated by the user, this
segment number must be checked to see if if still refers to the
directory it should be (search rule directory UID = kste.uid).)
initiate_$initiate_seg_count initiates the segment. (Refer to
the section on access control for special processing of the name
lookup rule by this entrypoint.)
The initiated segments search rule performs a RNT look up, with
ref_name_$getr_segno.
The working_dir search rule uses the value of the working dir
internally recorded (pds$wdir (ring)). The referencing_dir
search rule keys off the directory indicated by the input
reference pointer. (The KSTE entry for this segment is found and
its parent (kste.entryp) determines the directory to search.)
initiate_search_rules maintains the search rules for a user (per
ring, in the RNT) and the system search rules (in
active_hardcore_data). This later function is performed under
the protection of active_hardcore_data$search_rules_lock.
initiate_search_rules is called when the user changes the search
rules, and also whenever a new stack is created (by makestack).
Adding a rule to a user search rule list is a simple array
operation. When adding a pathname, though, dc_find enforces the
name lookup policy, obtaining/finding a segment number for it in
the process. This number (and the directory's UID) are kept in
the search rule data. The directories so found are held via
their usage counts. When supplying a new set of search rules to
replace an existing set, then, the usage counts of the old search
rule directories must be decremented to un-hold them. (Of
course, this dereferencing (potentially causing a future making
unknown) must audit, enforcing the name lookup policy via
dc_find.)
Setting the working directory is functionally the same as setting
a search rule directory.
9-12
Multics File System MDD-006
999...111222 PPPRRROOOPPPEEERRRTTTYYY SSSEEETTTTTTIIINNNGGG PPPRRRIIIMMMIIITTTIIIVVVEEESSS
set allows the setting of myriads of object attributes.
Common to all of these are the internal procedures find_entry and
get_entry_ptr. find_entry finds the directory entry in question.
get_entry_ptr works given a segment pointer to find the directory
entry. Either way, they extract the dirsw and check ring
brackets of the final object, if necessary.
The finish up portion of set takes two flavors: finish and
unlock. finish updates the dtem of the object (unless
transparent modify is specified) and then proceeds to unlock.
unlock performs the sum$dirmod and the unlocking of the
directory.
Within the usual file system limitations and rules, the setting
of the properties is straight forward. A few special notices are
listed below.
The auth setting function must use acc_name_ to delete the old
author and add the new author. The bit count functions must
likewise use acc_name_ to delete the old and add the new
bit_count author.
When setting dates, only the dtem and dtd can be set in the
branch. The dtu and dtm must be set in the VTOCE/ASTE by
vtoc_attributes. All references to VTOCEs are nice enough to
make sure that the logical volume is mounted first.
The setting of the volume_dump_switches, dnzp (don't null zero
pages), synchronized switch, max length and the damaged switch
must also reference the VTOCE via vtoc_attributes.
The setting of the entry bound (call limiter) is not allowed for
directories. It is necessary to setfaults the segment being so
set.
set_for_reloader is used to set all sorts of values by the
reloader. It can set: safety_sw; tpd (transparent paging device
(obsolete)); author; bit count author; dtu, dtm and max length
(vtoc_attributes); dtem and dtd; entry bound (note that it is not
necessary to setfaults when setting the entry bound if the max
length was set since this would have caused a setfaults earlier
and the segment can not be reconnected to anyone's process since
the directory is write locked).
999...111333 SSSEEEGGGMMMEEENNNTTT TTTRRRUUUNNNCCCAAATTTIIIOOONNN
Although a segment can be truncated by simply zeroing trailing
pages, this is not efficient. So, truncate is provided to
9-13
MDD-006 Multics File System
truncate (zeroes and frees the end) of segments by releasing
pages directly. The segment must not be a directory.
truncate_vtoce truncates the desired trailing pages followed by
sum$dirmod reflected the length change. The truncation of the
segment to a desired word is done by hand.
999...111444 QQQUUUOOOTTTAAA PPPRRRIIIMMMIIITTTIIIVVVEEESSS
quota is the file system interface to quota maintenance. It
operates freely on the quota limits but needs quotaw to
manipulate the quota used cells. To call quotaw, quota must find
the appropriate ASTE and thereby lock the AST. Otherwise, only
the directories in question need be locked.
Many of the entries start by calling get_quota_cell to find the
quota cell. This involves finding the directory whose cell is
needed, locking it as required, and using
vtoc_attributes$get_quota to fetch the quota cell.
The entries dqlong_reset and qlong_reset are used by accounting
to reset the trp (time record product) for the directory. They
subtract the specified amount from the trp figure. The original
quota cell is obtained by get_quota_cell, locking the directory
for writing (which prevents activation/deactivation and other
possible changes to the quota terminal-ness). sum$dirmod
reflects that the directory was changed.
dqset and qset set a quota limit. dqrestor and qrestor/qreload
set the quota limit as well as the trp and the tup (time of trp
update) for the reloaders. They are all privileged entries.
They also fetch the quota cell, locking the directory for
writing. The directory is forced to be active so that direct
references can be made to ASTE values. If the terminal quota
status of this cell isn't changing, the ASTE can be simply
patched. Otherwise, quotaw must be used to walk up the quota
hierarchy to the terminal account to change the quotas and
terminal status. The AST is unlocked (locked in activating the
directory), unlock the parent and record the directory as
modified (sum$dirmod).
mdir_set sets the quota on a master directory. append_mdir_set
is used by append to set the initial quota for a master
directory.
dqread and qread/qget, along with priv_dqread and priv_qread (who
do not check access) get the current quota and trp values for a
directory. The quota cell is obtained, the directory locked, and
the directory made active so that the used figures can be
obtained, the trp updated while this is being done, and the
information returned.
9-14
Multics File System MDD-006
check, check_file and check_seg check to see if the quota used on
a cell may be increased by a given amount within the quota limit
present. The actual work is done by quotaw (under the PTL).
dqmove and qmove perform a move quota between a parent and its
son. The arguments are the pathname of the parent and the
entryname of the son. This starts by finding the son directory.
An interesting manifestation of this particular system function
is that a user is allowed to move quota from a directory to an
upgraded directory from an authorization equal to that of the
lower directory's access class. This special casing is
understood by dc_find.
All qmove entries obtain the qcells for the parent and son
directories. The various validity checks for quota moving (not
down from master_dir, parent has no quota limit, etc) are done.
Both directories are made active (forcing son active forces
parent). The trp of both are updated since a change in both
directory's quota cells is being made which would screw up a
subsequent trp update. quotaw$mq performs the actual move (since
this operation may change the directory that holds the terminal
account. quota will manually update the location of the terminal
trp cell if this is necessary.) vtoc_attributes writes back the
quota cells (limits; the usage values are extracted from ASTE
information).
999...111555 MMMIIISSSCCCEEELLLLLLAAANNNEEEOOOUUUSSS FFFUUUNNNCCCTTTIIIOOONNNSSS
Various unique (mostly privileged support) functions are listed.
999...111555...111 QQQuuuoootttaaa CCCooorrrrrreeeccctttiiiooonnn
correct_qused examines the number of pages used by the objects
subordinate to a directory to correct the quota used figure for
the directory. The operation of this function is described in
the storage system PLM. The support provided to this primitive
by directory control is that correct_qused uses a write lock on a
directory to eliminate the possibility of segment creations and
deletions. Also, the set of active segments subordinate to this
directory cannot change by virtue of this write lock (refer to
the section on directory locks for details).
999...111555...222 RRRoooooottt DDDiiirrreeeccctttooorrryyy CCCrrreeeaaatttiiiooonnn
The root directory is created, during a cold boot initialization,
by create_root_dir. This program simply fills in the directory
header and hash table for the new (empty) root dir.
9-15
MDD-006 Multics File System
999...111555...333 DDDuuummmppp CCCooopppyyyiiinnnggg
A dump found in the dump partition is copied into hierarchy
segments by copy_fdump (name is historic). The creation of the
hierarchy segments is via a normal call to append. The only
thing interesting about this program is its creation of a rolling
abs-seg on the dump partition; this mechanism is described in the
Initialization SDN.
999...111555...444 SSSeeegggmmmeeennnttt MMMooovvviiinnnggg
fs_move moves segments. It is a basically obsolete function that
could just as well be performed in the user ring. It moves data
from one segment to another by optionally truncating the target
and moving data in (no deletion of target) and then truncating
the source. On its way it checks for max length limits and
quota, to help ensure success of the move. These checks are not
done under any locks, though, so there is no guarantee.
On the other hand, there is the real segment mover, invoked via
vacate_pv. For a segment, the segment entry is found, the
segment made known (makeknown_), the segment activated (activate)
and the segment mover called. All of these locks are then
undone. (vacate_pv also sets and resets the vacating flag for a
physical volume; this mechanism is described in the Storage
System PLM.)
999...111555...555 VVVooollluuummmeee RRReeetttrrriiieeevvveeerrr///DDDuuummmpppeeerrr
The file system support for the volume dumper/retriever is
imbedded within hc_dmpr_primitives, retv_copy and retv_util.
VOLUME DUMPER
hc_dmpr_primitives contains hardcore utilities for the volume
dumper. It has a curious pseudo relationship to directory
control. The volume dumper internally builds abs-segs describing
a segment on a physical volume it wishes to dump. For segments
that are active, it wants to use the ASTE they have, keeping the
AST locked to prevent segmoves, boundfaults, etc. For not active
segments, it wants to activate them (using an abs-seg built given
their VTOCE), but in such a way as to prevent some other process
from activating them (using their branch info) without its having
to hold the AST lock (which would make it hard to activate the
segment). To do this requires a write lock on the objects'
containing dir. Since is is not desirable to have to find this
dir, this program builds a pseudo-dir, with the UID of the
directory that would have been wanted to lock within it.
lock$dir_lock_write is then called. lock is capable of dealing
9-16
Multics File System MDD-006
with this pseudo-dir. If some other process wanted to lock the
real dir, lock could not tell the difference between this
pseudo-dir and the real one, since such a match is done by UID.
This mechanism, then, is part of the abs mechanisms for fetching
the segment upon which to operate.
VOLUME RETRIEVER
retv_copy is the hardcore routine that copies data into a segment
or directory for the volume retriever. This function exists as a
hardcore primitive so as to provide a controlled way of replacing
a directory with another.
The basic operation is to find the object's directory entry which
may or may not have a corresponding VTOCE at this time, locking
the directory in the process, check access, find or create the
VTOCE, make the segment known and then copy the new data in.
Various VTOC attributes are then set from the supplied arguments.
During the course of the copy, rw access is forced on in the
segment in this process. The object is entry held and its parent
locked so this access cannot be changed (or anyone else get to
the segment).
The operation for a directory is harder. Basically the directory
that is being installed wants to match up with what is being
replaced. That is, any objects in the old dir not in the new
should be deleted. Also, any in the old that are in the new
should be preserved as is. To get and keep the directory in
sync, it is locked. Since it may not really exist (have no VTOCE
or contents), a pseudo directory is built for the lock routine to
have. The directory matchup routine walks down the old
directory. For each entry it finds in the new also, it copies
the old pvid and VTOCE index into the new entry. If the object
is not in the new dir, it deletes it. To do this, it unlocks
this directory (which it does using the real directory, now that
it exists) and unlocks the parent so that del_dir_tree or
delentry (both using the retv entrypoint) can eliminate the
object. After this, the directory and its parent are relocked
(following the directory relocking rules) and the scan restarted.
This eventually succeeds when the dirs are in sync. Any object
that can't be deleted is put on a list of objects to just ignore.
When the directory is replaced, they will go away by not being
findable.
The other operation necessary for directories is maintaining the
quota tree. When the parent's entry was locked, its quota info
was fetched. The quota for this new dir is found as well as the
sum of that received from its inferiors. If it was necessary to
create a VTOCE for this new directory, its quota info is useless
and that supplied by the input VTOCE is used. Otherwise, only
the quota and received figures supplied apply. The check that is
9-17
MDD-006 Multics File System
desired is that the quota received from this directory plus that
received from its inferiors plus the parent quota is less than or
equal to that distributed by the parent. If this is so, the
quota for this new directory can be set with that computed
safely, without destroying the quota tree. Otherwise, the quota
must be forced to 1 (non-zero) to force this directory to have
terminal quota.
retv_util provides various utilities for the volume retriever.
The delete entry deletes an object by calling
delentry$salv_delete_branch. The set_bc entry patches the bit
count in the entry, returning the old bit count. The get entry
returns the contents of the directory entry. The check entry
returns the object type and dtm. The status entry also returns
the user effmode, user mode on parent, UID, pvid, volid and dtd.
The name_list entry returns all of the names on the object. It
uses the standard area return management mechanism when returning
the names. The addname entry uses chname$retv to bypass access
checks. The add_acl entry uses acl_$add_entry to add ACL terms.
It adds the terms on an all or nothing basis. sum$dirmod is
called.
999...111555...666 PPPrrriiivvviiillleeegggeeeddd VVVeeerrrsssiiiooonnnsss ooofff OOOpppeeerrraaatttiiiooonnnsss
The file system provides certain privileged versions of some file
system primitives. Some are mentioned above.
Aside from these, there exists level_0_, which performs the work
of the hphcs_$foo entries that do not have special privileged
entrypoints. It simply sets the validation level to 0, calls the
equivalent function, and resets the validation level.
ring0_init performs the phcs_$foo functions with respect to
initiating and terminating objects. It sets the validation level
to 0, performs the operation, and resets the validation level.
999...111555...777 SSSeeettt SSSooonnnsss LLLVVVIIIDDD
set_sons_lvid sets the sons LVID for a directory. The program
starts with a little bit of fancy lock footwork, in that the
access check is made against the parent of the target directory,
and so dc_find must be called upon the parent. However, the
target directory itself needs to be locked, and so it is
necessary to unlock the parent and relock it after the son is
locked. (Refer to the section on holding directory entries).
The LVID is set (as well as the fact that this becomes a master
dir) in the directory header. If the directory is active, its
AST is found and the master dir bit sit on there also.
sum$dirmod is called on the directory.
9-18
Multics File System MDD-006
The entrypoint set_rpv within this module does the same things as
above, except that it sets the force_rpv bit in the directory
header (to apply to this dir's sons).
999...111555...888 DDDiiissskkk TTTaaabbbllleee LLLooocccaaatttiiiooonnn
When a disk_table_ is created, the Initializer records its
location in the RPV label via set_disk_table_loc. This program
simply extracts the UID and VTOCE index from the branch for
disk_table_, and forces them into the label (fsout_vol).
999...111555...999 TTTeeemmmppp WWWiiirrriiinnnggg
user_wire is the interface to pc_wired$wire_wait and
pc_wired$unwire. It accepts either a pathname or a segptr. The
entry pointer is fed to activate. If wiring is being done, the
ASTE is entry held so that pc_wired will work (and the pages
stay). The AST is unlocked and the directory unlocked before
leaving.
999...111555...111000 UUUIIIDDD PPPaaattthhh UUUtttiiillliiitttiiieeesss
uid_path_util performs mapping of UID pathnames into real
pathnames and the mapping of segment pointers and pathnames into
UID pathnames.
The get entry is given a pointer to a directory and returns the
UID pathname of its parent. This is a simple matter of
iteratively calling get_kstep$dir and looking up the UIDs within
the KST entries. Just as kst_info, this entry has no access
requirements since it returns only KST information. This
information could not have changed since the object in question
was initiated; also, this information is not affected by whether
the object still exists or not.
get_uid_path is a gate entry which, given a pathname, returns a
UID pathname. It uses dc_find to get an entry pointer, derives
the directory pointer from that, and uses uid_path_util$get.
decode_uidpath is a gate entry which, given a UID pathname,
returns a directory and entry name. It also uses dc_find for the
lookup.
9-19
Multics File System MDD-006
APPENDIX A
GLOSSARY
ACL
access control list
AIM
access isolation mechanism
AIM privilege
a flag, recorded in pds$access_authorization, that allows
the process to defeat AIM requirements with respect to a
particular subsystem. The AIM privileges that relate to the
file system are seg and dir privilege.
IACL
initial access control list
ISOT
internal static offset table
KST
known segment table
KST garbage collection
the process by which directories that are no longer needed
are cleaned out of the address space
LOT
linkage offset table
MSF component indicator
the normal value that is assigned to the bit count for a
directory
PAM
pathname associative memory
RNT
reference name table
A-1
MDD-006 Multics File System
SDW
segment descriptor word
UID
unique identifier
access control list (ACL)
a list of user id/access mode pairs specifying the access
that particular user groups have to a branch. The ACL is
Multics specification of discretionary access control.
access control
the process of limiting the operations a user may perform on
an object according to a set of rules
access isolation mechanism (AIM)
the Multics specification of nondiscretionary control. AIM
associates with each user an authorization (level and series
of categories) and with each object an access class. The
relationship between the user's authorization and the
object's access class determines the user's allowed
operations upon the object.
access modes
the set of flags indicating what operations a user is
allowed to perform on an object (such as read, write,
execute)
activation
the process of obtaining a page table for a segment, thereby
allowing the paging of pages of the segment. A segment must
be active to be connected to a process; refer to connection.
address and name space management
that portion of the Multics supervisor which governs the
introduction of segments and directories into the address
space, the removal there from, and keeping track of the
association between pathnames and segment numbers; also that
portion which maintains the reference name table
address space
the set of segments that can be addressed by the Multics
hardware at any given time
attribute property
a property of an entry for which the user may have access to
either the entry or the parent of the entry to operate upon
the property
audit
to record an event in the security log. The term audit is
used in this manual to refer to the decision to generate an
A-2
Multics File System MDD-006
audit message associated with a particular event; the audit
message may or may not be added to the security log
depending on the audit flags for the user.
authorization access modes
the access modes a user has to an object factoring in ACL
and AIM
branch
a directory entry for a directory or a segment; also used to
refer to the directory or segment so described
connection
the process of making the SDW for the process for a given
segment valid. After a segment is connected to a process,
the process may reference the segment, via the hardware.
The process of connecting to a segment may also require
making the segment active; any connected segment must be
active, but a segment that is active need not be connected
to those processes whose address spaces contain it.
contents property
a property of an entry for which the access requirement is
specific access to the entry
dc_find
the master module within directory control that locates
directories and directory entries, enforces the system's
security policy and audits the granting of access and
attempted access violations
dir_lock_seg
the data structure that records the complete set of
directories locked by all processes
directory
a data structure, implemented as a segment, that contains
entries describing segments, directories, links, as well as
access control lists and other describing information
directory compactor
a function of the directory salvager that can recover unused
space within a directory
directory salvager
a system program that examines directories for correctness,
and recovers and corrects directory entries
directory write behind
a function (requested via the dirw parameter) that causes a
force write of a directory when it is unlocked after having
been locked for writing
A-3
MDD-006 Multics File System
dirw
directory write behind
dtbm
date-time branch modified (see also dtem)
dtem
date-time entry modified
effective access modes
the access modes a user has to an object factoring in ACL,
AIM and rings
entry
in this manual, refers to an entry in a directory that
describes a branch or a link
file system object
a branch or a link; that is, anything described by a
directory entry
initial access control list (IACL)
two per ring ACLs associated with a directory, one for
segments and one for directories. Objects created of the
corresponding type are automatically given this ACL, along
with any user supplied ACL terms.
initiation
the request on behalf of a user to associate a segment
number in the address space with a pathname
known segment table (KST)
the table that provides the mapping between the segment
numbers within a process' address space and the segment's
location in the file system hierarchy
link
a directory entry that contains a pathname of another
directory or directory entry
link chasing
the process of encountering a link when searching for an
entry, using the target pathname of that link to find a new
entry, encountering another link in that process, using that
link target to find yet another entry, etc.
making known
the process of associating a KST entry with a segment in the
file system hierarchy
A-4
Multics File System MDD-006
making unknown
the process of disassociating a KST entry with a segment in
the file system hierarchy
name lookup policy
the security policy that prevents the user from knowing the
existence of an object if the user does not have sufficient
access to perform any operation at all upon the object
name space
the set of names associated with each segment in a process'
address space
pathname associative memory (PAM)
an associative memory that maps segment numbers for
directories into their pathnames
property
a piece of information associated with an entry; see status,
contents and attributes property
pseudo directory
a fabricated directory header, with a UID inserted so as to
allow locking a directory whose existence or location in the
hierarchy is unknown
raw access modes
the access modes a user has to an object factoring in only
the ACL
reference name table (RNT)
a per ring table providing a set of names to be associated
with each segment in the address space for use by the
initiated segments dynamic linker search rule
ring brackets
a set of ring numbers associated with a segment used to
limit the set of rings within which a specific type of
access may be performed upon the segment
root
the directory in the Multics directory hierarchy under which
all other directories are to some level subordinate
segment
the smallest collection of machine addressable words over
which the Multics hardware allows access control. A segment
is an identifiable part of an address space. In normal user
manuals, segment refers only to those segments that user
processes may read, write or execute. In this manual,
segment refers to both segments and directories (which are
implemented as segments), unless otherwise noted.
A-5
MDD-006 Multics File System
segment descriptor word (SDW)
a hardware known per segment control word that provides the
hardware address for the segment, as well as the hardware
enforced access control information
setfaults
a function of segment control that revokes all process'
access to a segment, called when a process potentially
changes processes' access to the segment
status property
a property of an entry for which the user needs to have
specific access to the parent of the entry to perform the
operation
termination
the user request to disassociate a segment number with a
pathname
unique identifier
a unique 36 bit value assigned to each file system object at
its creation
usage count
a per ring count of the number of outstanding initiations of
the corresponding segment, used to protect segments from
being made unknown
-----------------------------------------------------------
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