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 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 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<<>>>>AA VV>>>>>AA AVV>>>>>AA V>>>>>>>A V>>>>>>>A AV V AV>>>>>>VV A<<<<<>>>>>>>>>>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 A<><><><><><><><><><><>>>>>>>>>V V V<<<<<>>X>>>>>>>>>>>>>>>V V V 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 V V V V V V V<<<<<<<<<X>>>>>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<<>>>>>>V V<<<<<>>X>>>V V>>>X>>>>>>>V V V V V V V V V V V V<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); 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