.ifi init_plm "FS-00" .srv draft "" .srv draft_date "" .srv section %Arg1% .pdl 66 .ifi l0h "Directory Structures" .ifi hit "K|directory~structure" 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 .ifi hit "K|directory~structure~elements" 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. .ifi l1h "Directory Header" A directory starts out with a directory header (described by .ifi hit "K|directory~structure~header" 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. .inl +5 .unl +5 dir.type .brf the value DIR_HEADER_TYPE (3) to designate this area (which starts at word 0 of the directory) as the directory header .unl +5 dir.size .brf size of the directory header .unl +5 dir.version_number .brf the version number of the header, currently 2 .unl +5 dir.modify .brf the value of the process id of the process currently modifying this .ifi hit "K|directory~modification~in progress" directory. This field is set when a process begins a modification sequence .ifi hit "K|directory salvager" 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. .unl +5 dir.dtc .brf obsolete .unl +5 dir.uid .brf the UID of the directory, copied from the branch. This is "777777777777"b3 for the root. .unl +5 dir.pvid .brf the physical volume id of the directory, copied from the branch .unl +5 dir.sons_lvid .brf 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. .unl +5 dir.access_class .brf AIM attributes of the directory, copied from branch .unl +5 dir.vtocx .brf the VTOC index of this directory, copied from branch .unl +5 dir.per_process_sw .brf indicates that this directory contains per process segments .unl +5 dir.master_dir .brf TRUE if this is a master directory .unl +5 dir.force_rpv .brf TRUE if segments created under this directory must be on the RPV .unl +5 dir.tree_depth .brf the number of levels from the root of this directory. This is zero for the root. .unl +5 dir.dts .brf the date-time this directory was last salvaged .unl +5 dir.master_dir_uid .brf the UID of the superior master directory. This is "777777777777"b3 for the root. .unl +5 dir.change_pclock .brf the directory change pseudo-clock. It is incremented by one each time the .ifi hit "K|directory~locks~relocking" 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. .unl +5 dir.owner .brf the UID of the parent directory (used for validity checks). This is "777777777777"b3 for the root. .inl -5 .ifi l1h "Directory Allocation Area" Other than the directory header, which always starts at word 0 of a .ifi hit "K|directory~structure~allocation area" 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 .ifi hit "K|fs_alloc" directory as a simplified area. This area is found from the directory header. It is described by dir_allocation_area.incl.pl1. .inl +5 .unl +5 dir.arearp .brf the relative pointer to the beginning of the allocation area .inl -5 The area management policy is as follows. A directory, at any given .ifi hit "K|directory~structure~allocation" 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, .ifi hit "K|directory salvager~compactor" nor the blocks rearranged except by the directory compactor (within the salvager). .inl +5 .unl +5 area.nsizes .brf the number of block sizes available .unl +5 area.lu .brf (last used) the next available word offset within the directory describing the unused area .unl +5 area.lw .brf the last word offset within the directory .unl +5 area.array.fptr (size_index) .brf the relative offset of the first free block of the given size .unl +5 area.array.size (size_index) .brf the size of this given set of blocks .inl -5 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. .ifi l1h "Directory Entries" The various entries within a directory, whether they describe a branch .ifi hit "K|directory~structure~entry" or a link, are threaded into a single list of entries. These lists are found from the directory header. .inl +5 .unl +5 dir.seg_count .brf the number of non-directory branches .unl +5 dir.dir_count .brf the number of directory branches .unl +5 dir.lcount .brf the number of links .unl +5 dir.entryfrp .brf the relative pointer to the beginning of the entry list .unl +5 dir.entrybrp .brf the relative pointer to the end of the entry list .inl -5 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. .inl +5 .unl +5 entry.type, link.type .brf 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) .unl +5 entry.size, link.size .brf the size of this directory entry .unl +5 entry.efrp, link.efrp .brf the forward (relative) pointer to the next directory entry .unl +5 entry.ebrp, link.ebrp .brf the backward (relative) pointer to the previous directory entry .unl +5 entry.bs, link.bs .brf (branch switch) TRUE if this is a branch entry .unl +5 entry.uid, link.uid .brf the unique id of the entry .unl +5 entry.dtem, link.dtem .brf the date-time this entry was last modified. This can be used to detect the .ifi hit "K|access modes~recomputation" possible need to recompute access on the entry. (Refer to directory entry relocking mechanisms for more details.) .unl +5 entry.dtd, link.dtd .brf the date-time dumped of this entry .inl -5 For a branch entry, the following fields are defined. .ifi hit "K|directory~structure~branch" .inl +5 .unl +5 entry.dirsw .brf TRUE if this is a directory branch .unl +5 entry.pvid .brf the physical volume id of the object .unl +5 entry.vtocx .brf the VTOC entry index of the object .unl +5 entry.oosw .brf obsolete .unl +5 entry.per_process_sw .brf indicates segment is per process .unl +5 entry.copysw .brf TRUE if a copy should be made of this segment upon a write violation .unl +5 entry.safety_sw .brf TRUE if the object is not to be deleted .unl +5 entry.multiple_class .brf TRUE if the segment has multiple security classes .unl +5 entry.audit_flag .brf TRUE if the segment must be audited for security (not currently used) .unl +5 entry.security_oosw .brf TRUE if the object is out-of-service for security reasons .unl +5 entry.entrypt_sw .brf TRUE if call limiter is to be enabled in the SDW .unl +5 entry.entrypt_bound .brf call limiter for the SDW (gates only) .unl +5 entry.master_dir .brf TRUE for a master directory .unl +5 entry.tpd .brf obsolete .unl +5 entry.access_class .brf AIM security attributes .unl +5 entry.ring_brackets .brf ring brackets on segment .unl +5 entry.ex_ring_brackets .brf extended ring brackets .unl +5 entry.bc .brf bit count for a segment, msf component indicator for a directory .unl +5 entry.sons_lvid .brf logical volume id for immediately inferior non-directory segments (directories only) .unl +5 entry.owner .brf UID of containing directory (must match dir.uid) .inl -5 If this is a non-branch entry (link), the following fields are defined. .ifi hit "K|directory~structure~link" .inl +5 .unl +5 link.pathname_size .brf the number of characters in link.pathname .unl +5 link.pathname .brf pathname of link .unl +5 link.owner .brf UID of the containing directory (must match dir.uid) .inl -5 .ifi l1h "Entry Names" Each entry in a directory may have an arbitrarily large number of names. .ifi hit "K|directory~structure~entry 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. .inl +5 .unl +5 entry.primary_name, link.primary_name .brf the area reserved within the entry for the name structure holding the primary name .unl +5 entry.nnames, link.nnames .brf number of names for this entry .unl +5 entry.name_frp, link.name_frp .brf relative pointer to the start of the name list (this will point to entry/link.primary_name) .unl +5 entry.name_brp, link.name_brp .brf relative pointer to the end of the name list .unl +5 names.type .brf the value NAME_TYPE (6) .unl +5 names.size .brf the size of this structure .unl +5 names.fp .brf relative pointer to the next name .unl +5 names.bp .brf relative pointer to the previous name .unl +5 names.name .brf a name for this entry .unl +5 names.entry_rp .brf relative pointer to the owning entry .unl +5 names.owner .brf UID of the owning entry .inl -5 .ifi l1h "Hash Table" For speed when looking for a name within a directory, a hash table is .ifi hit "K|directory~structure~hash table" 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. .inl +5 .unl +5 dir.hash_table_rp .brf relative pointer to the start of the name hash table .unl +5 dir.htsize .brf the size of hash table .unl +5 dir.htused .brf (hash table used) the total of the number of names of all of the entries in this directory .unl +5 dir.rehashing .brf 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. .inl -5 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. .inl +5 .unl +5 hash_table.type .brf the value HASH_TABLE_TYPE (13 octal) .unl +5 hash_table.size .brf the size of this structure .unl +5 hash_table.name_rp .brf the hash table array (dir.htsize) .unl +5 hash_table.modify .brf obsolete .unl +5 hash_table.checksum .brf obsolete .unl +5 hash_table.owner .brf obsolete .unl +5 names.ht_index .brf index of hash table entry for this name .unl +5 names.hash_thread .brf relative pointer to the next name that hashes to the same value as this one .inl -5 .ifi l1h "ACL and Access Names" Each branch entry can have an ACL. Also, a directory may contain an IACL .ifi hit "K|directory~structure~ACL" .ifi hit "K|ACL~directory structure" .ifi hit "S|ACL~see also properties, ACL" 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). .inl +5 .unl +5 dir.acle_total .brf the total number of ACL entries in directory .unl +5 dir.iacl_count.seg (validation level) .brf the number of initial ACL entries for segments .unl +5 dir.iacl_count.dir (validation level) .brf the number of initial ACL entries for directories .unl +5 dir.iacl.seg_frp (validation level) .brf relative pointer to the start of the initial ACL for segments .unl +5 dir.iacl.seg_brp (validation level) .brf relative pointer to the end of the initial ACL for segments .unl +5 dir.iacl.dir_frp (validation level) .brf relative pointer to the start of the initial ACL for directories .unl +5 dir.iacl.dir_brp (validation level) .brf relative pointer to the end of the initial ACL for directories .unl +5 entry.acle_count .brf the number of entries on the ACL for the branch .unl +5 entry.acl_frp .brf relative pointer to the start of the ACL for the branch .unl +5 entry.acl_brp .brf relative pointer to the end of the ACL for the branch .unl +5 acl_entry.type .brf the value ACLE_TYPE (2) .unl +5 acl_entry.size .brf the size of this structure .unl +5 acl_entry.frp .brf relative pointer to the next ACL entry in this ACL .unl +5 acl_entry.brp .brf relative pointer to the previous ACL entry in this ACL .unl +5 acl_entry.mode .brf corresponding access modes for the userid described by this ACL entry .unl +5 acl_entry.ex_mode .brf corresponding extended access modes for the userid described by this ACL entry .unl +5 acl_entry.checksum .brf obsolete .unl +5 acl_entry.owner .brf the UID of the owning entry. For IACLs, this is the UID of the directory. .inl -5 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 .ifi hit "K|directory~structure~access names" .ifi hit "K|ACL~access names" 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). .inl +5 .unl +5 entry.author.pers_rp, link.author.pers_rp .brf relative pointer to the person name structure for the user who created the branch .unl +5 entry.author.proj_rp, link.author.proj_rp .brf relative pointer to the project name structure for the user who created the branch .unl +5 entry.author.tag, link.author.tag .brf the tag of the user who created the branch .unl +5 entry.bc_author.pers_rp .brf relative pointer to the person name structure for the user who set the bit count .unl +5 entry.bc_author.proj_rp .brf relative pointer to the project name structure for the user who set the bit count .unl +5 entry.bc_author.tag .brf the tag of the user who set the bit count .unl +5 acl_entry.name.pers_rp .brf 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 "*". .unl +5 acl_entry.name.proj_rp .brf 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 "*". .unl +5 acl_entry.name.tag .brf the tag of the userid associated with this ACL entry .inl -5 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 .ifi hit "K|acc_name_" 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. .inl +5 .unl +5 dir.pers_brp .brf relative pointer to the end of the person name list .unl +5 dir.proj_brp .brf relative pointer to the end of the project name list .unl +5 dir.pers_frp .brf relative pointer to the start of the person name list .unl +5 dir.proj_frp .brf relative pointer to the start of the project name list .unl +5 access_name.type .brf the value ACCESS_NAME_TYPE (1) .unl +5 access_name.size .brf the size of this structure .unl +5 access_name.frp .brf relative pointer to the next name structure within the directory .unl +5 access_name.brp .brf relative pointer to the previous name structure within the directory .unl +5 access_name.salv_flag .brf obsolete .unl +5 access_name.usage .brf 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. .unl +5 access_name.name .brf the person or project name itself .unl +5 access_name.checksum .brf obsolete .unl +5 access_name.owner .brf the UID of the containing directory (must match dir.uid) .inl -5 .ifi l1h "Example" As an example, consider the directory containing the following entries. .ifi hit "K|directory~structure~example" .fif 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 .fin 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. .fif .brp /=========\ /=========\ /=========\ /=========\ | 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 .brp /=========\ /=========\ /=========\ /=========\ | 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 .brp /=========\ /=========\ /=========\ /=========\ | 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 V V V V V V V V /=========\ /=========\ V V V V |acl_entry| |acl_entry| V V V V | | | | V V V V | | | | V V V V | | | | V V V V | | | | V V V V | | | | V V V V | | | | V V V V \=========/ \=========/ V V V V V V V V V V V<<<<<>>>>>>>V V<<<<<>>>>>>>V V A<><><><><><><><><><><>>>>>>>>>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<