10/17/84 vfile_find_bad_nodes Syntax as a command: vfile_find_bad_nodes {path} {-control_args} Syntax as an active function: [vfile_find_bad_nodes {path} {-control_args}] Function: examines a vfile_ keyed file to determine whether the vfile_ multisegment file (MSF) components that contain keys are in a consistent state. The keys in a keyed file are maintained in a tree structure in which each node of the tree is stored in a separate page of an MSF component. The consistency checks that are performed are summarized below. Nodes reported as bad by this heuristic are almost certainly damaged. Arguments: path is pathname of the indexed file whose nodes are to be checked. Control arguments: -check MODES, -ck MODES enables only the types of checking given in the MODES string (see "List of modes"). (Default: -check default) -io_switch STR, -isw STR identifies an I/O switch that is already attached to the indexed file to be checked. The switch may be closed; if open, it must be opened for keyed_sequential_input. -no_request_loop, -nrql prints information about the bad nodes and then continues checking without entring the request loop. (Default: when invoked as an active function) -request_loop, -rql enters the request loop when bad nodes are found. (Default: when invoked as a command) List of modes: all is a shorthand for enabling all possible checking. It it equivalent to node_branch,key_region,key_loc,key_overlap,key_order,node_tree. default is a shorthand way of enabling checks that can be quickly performed. It is equivalent to node_branch,key_region,key_loc. The settings of other modes are not affected. key_loc, ^key_loc performs key-location checking, as described below. key_order, ^key_order performs key-order checking, as described below. key_overlap, ^key_overlap performs key-overlap checking, as described below. key_region, ^key_region performs key-region checking, as described below. node_branch, ^node_branch performs node-branch checking, as described below. node_tree, ^node_tree performs node-tree checking, as described below. List of consistency checks: The following consistency checks are always performed to validate the file header: 1) Does the counted number of nonempty (key-containing) nodes equal the count stored in the file header? If not, the file header may have been damaged. 2) Does the counted number of keys in all nodes equal the count stored in the file header? If not, the file header may have been damaged. 3) Does the counted total length of all keys equal the count stored in the file header? If not, the file header may have been damaged. For each node in the file the following consistency checks are performed: 4) Is this a freed node? If so, skip further checks. 5) Are there any branches (keys) in this node? If not, skip further checks. Node-branch checks 6) Is branch_count greater than 313? If so, node is bad because space in a page limits a node to having, at most, 313 one-character keys. 7) Is branch_count less than 0? If so, node is bad. Key-region checks 8) Is start_of_key_region greater than 4096? If so, node is bad because the character position of the first key must lie within the node page. 9) Does start_of_key_region overwrite the branch array? If so, node is bad because keys have overwritten the array of branches in the node. 10) Is scattered_free_key_space greater than 4096 minus start_of_key_region? If so, node is bad because the count of unused space within the key region is greater than the size of the key region itself. 11) Is scattered_free_key_space less than 0? If so, node is bad. 12) Is length of all keys in node equal to 4096 minus start_of_key_region minus scattered_free_key_space? If not, node header is bad. Key-location checks 13) Does any branch declare its key to begin prior to start_of_key_region? If so, node is bad. 14) Does any branch declare its key to extend beyond end of node page? If so, node is bad. Key-overlap check 15) Does the storage for any key overlap storage for another key? If so, node is bad. Note that this test is somewhat time consuming. Key-order check 16) Are the keys within the node ordered in increasing ASCII collating sequence? If not, the node is bad. Note that this test is somewhat time consuming. Node-tree check 17) For each child pointer in the node, does the child pointer reference another node that resides in a node-containing component of the vfile? If not, the child pointer is bad. 18) Does the child pointer reference another node that contains keys (is nonempty)? If not, the child pointer is bad. 19) Does the child pointer reference another node that is not on the list of freed nodes? If not, the child pointer is bad. 20) Does each child pointer in the node reference another node that is not the root node? If not, the child pointer is bad. 21) Is every nonempty node but the root node referenced by a child pointer of some other node? If not, the node is inaccessible and its keys are effectively not part of the key tree. 22) Is any nonempty node referenced by more than one superior node? If so, the key tree is inconsistent. List of requests: . gives name and version number of this program, plus pathname or I/O switch of file being examined. .. escapes Multics command level to execute command_line. ? lists available requests. continue, c continues searching for damaged nodes. quit, q stops further processing, reporting total of damage found so far. total, tt stops reporting, for remainder of this MSF component, information about each damaged node and counts the damaged nodes in this component. Notes: Give either a pathname argument or -io_switch to identify the file to be checked. As an active function, returns true if bad nodes are found, false otherwise. Normal diagnostic messages are still printed. Notes on request loop operation: When a bad node is found, its location is printed out, followed by the number of branches in the node, its low_key_pos, and its unused key space (scat_space). Then a request loop is entered that allows you to continue checking other nodes, to quit further checking, or to enter a totaling loop that counts the number of damaged nodes in the current component without printing their statistics. The request ..ds node_seg node_offset count -ch is a useful thing to do. Type "c" in the request loop to continue checking the next node. ----------------------------------------------------------- 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