.ifi init_plm "FS-00" .srv draft "" .srv draft_date "" .srv section %Arg1% .pdl 66 .ifi l0h "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. .ifi l1h "The KST" kst_seg (the KST) is actually divided into three areas (other than the .ifi hit "K|KST" 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 .ifi hit "K|private_logical_volume" private_logical_volume, and is not discussed here further. The UID hash table is a hash table used in conjunction with UID hash .ifi hit "K|kstsrch" .ifi hit "K|KST~UID hash table" 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. .ifi l2h "KST Entries" The fields within a KST entry are below explained. .inl +5 .unl +5 kste.fp .brf 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. .unl +5 kste.segno .brf 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. .unl +5 kste.usage_count (0:7) .brf 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 .ifi hit "K|usage count" 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. .unl +5 kste.entryp .brf 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 .ifi hit "K|validate_entryp" unlocked at any time that this entry pointer is being referenced, and so the pointer is not guaranteed valid. Refer to validate_entryp within sum for details of the mechanism used to reference kste.entryp. .unl +5 kste.uid .brf the UID of the segment. This is "777777777777"b3 for the root. .unl +5 kste.access_information.dtbm .brf 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 .ifi hit "K|access modes~recomputation" 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. .unl +5 kste.access_information.extended_access .brf extended access from the branch .unl +5 kste.access_information.access .brf "rew" authorization access computed from the branch .unl +5 kste.access_information.ex_rb .brf ring brackets from branch .unl +5 kste.flags.dirsw .brf TRUE if the segment is a directory .unl +5 kste.flags.allow_write .brf FALSE if initiated without write permission. This is used to mask out write permission that would otherwise be given by the branch. .unl +5 kste.flags.priv_init .brf TRUE if the segment was privileged initiated. The presence of this bit .ifi hit "K|privilege~initiation" overrides AIM computations for this segment; it also allows truncations to be performed on the segment independent of AIM. .unl +5 kste.flags.tms .brf (transparent modify switch) causes modifications of the segment to not set the .ifi hit "K|transparent usage/modification" 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. .unl +5 kste.flags.tus .brf (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. .unl +5 kste.flags.tpd .brf (transparent paging device) obsolete .unl +5 kste.flags.audit .brf obsolete .unl +5 kste.flags.explicit_deact_ok .brf 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. .unl +5 kste.infcount .brf 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. .inl -5 .ifi l1h "The RNT" The reference name table provides the ability of a process to establish .ifi hit "K|RNT" .ifi hit "K|dynamic linker" an arbitrary number of names with a segment. These 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 .ifi hit "K|RNT~creation" .ifi hit "K|makestack" 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. .ifi l2h "RNT Entries" 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. .brp ----------------------------------------------------------- Historical Background This edition of the Multics software materials and documentation is provided and donated to Massachusetts Institute of Technology by Group BULL including BULL HN Information Systems Inc. as a contribution to computer science knowledge. This donation is made also to give evidence of the common contributions of Massachusetts Institute of Technology, Bell Laboratories, General Electric, Honeywell Information Systems Inc., Honeywell BULL Inc., Groupe BULL and BULL HN Information Systems Inc. to the development of this operating system. Multics development was initiated by Massachusetts Institute of Technology Project MAC (1963-1970), renamed the MIT Laboratory for Computer Science and Artificial Intelligence in the mid 1970s, under the leadership of Professor Fernando Jose Corbato. Users consider that Multics provided the best software architecture for managing computer hardware properly and for executing programs. Many subsequent operating systems incorporated Multics principles. Multics was distributed in 1975 to 2000 by Group Bull in Europe , and in the U.S. by Bull HN Information Systems Inc., as successor in interest by change in name only to Honeywell Bull Inc. and Honeywell Information Systems Inc. . ----------------------------------------------------------- Permission to use, copy, modify, and distribute these programs and their documentation for any purpose and without fee is hereby granted,provided that the below copyright notice and historical background appear in all copies and that both the copyright notice and historical background and this permission notice appear in supporting documentation, and that the names of MIT, HIS, BULL or BULL HN not be used in advertising or publicity pertaining to distribution of the programs without specific prior written permission. Copyright 1972 by Massachusetts Institute of Technology and Honeywell Information Systems Inc. Copyright 2006 by BULL HN Information Systems Inc. Copyright 2006 by Bull SAS All Rights Reserved