1 10/17/84  vfile_find_bad_nodes
  2 
  3 Syntax as a command:  vfile_find_bad_nodes {path} {-control_args}
  4 
  5 
  6 Syntax as an active function:
  7    [vfile_find_bad_nodes {path} {-control_args}]
  8 
  9 
 10 Function: examines a vfile_ keyed file to determine whether the vfile_
 11 multisegment file (MSF) components that contain keys are in a
 12 consistent state.  The keys in a keyed file are maintained in a tree
 13 structure in which each node of the tree is stored in a separate page
 14 of an MSF component.  The consistency checks that are performed are
 15 summarized below.  Nodes reported as bad by this heuristic are almost
 16 certainly damaged.
 17 
 18 
 19 Arguments:
 20 path
 21    is pathname of the indexed file whose nodes are to be checked.
 22 
 23 
 24 Control arguments:
 25 -check MODES, -ck MODES
 26    enables only the types of checking given in the MODES string (see
 27    "List of modes").  (Default: -check default)
 28 -io_switch STR, -isw STR
 29    identifies an I/O switch that is already attached to the indexed
 30    file to be checked.  The switch may be closed; if open, it must be
 31    opened for keyed_sequential_input.
 32 -no_request_loop, -nrql
 33    prints information about the bad nodes and then continues checking
 34    without entring the request loop.  (Default: when invoked as an
 35    active function)
 36 -request_loop, -rql
 37    enters the request loop when bad nodes are found.  (Default: when
 38    invoked as a command)
 39 
 40 
 41 List of modes:
 42 all
 43    is a shorthand for enabling all possible checking.  It it equivalent
 44    to node_branch,key_region,key_loc,key_overlap,key_order,node_tree.
 45 default
 46    is a shorthand way of enabling checks that can be quickly performed.
 47    It is equivalent to node_branch,key_region,key_loc.  The settings of
 48    other modes are not affected.
 49 key_loc, ^key_loc
 50    performs key-location checking, as described below.
 51 key_order, ^key_order
 52    performs key-order checking, as described below.
 53 key_overlap, ^key_overlap
 54    performs key-overlap checking, as described below.
 55 
 56 
 57 key_region, ^key_region
 58    performs key-region checking, as described below.
 59 node_branch, ^node_branch
 60    performs node-branch checking, as described below.
 61 node_tree, ^node_tree
 62    performs node-tree checking, as described below.
 63 
 64 
 65 List of consistency checks:
 66    The following consistency checks are always performed to validate
 67    the file header:
 68    1)  Does the counted number of nonempty (key-containing) nodes equal
 69        the count stored in the file header?  If not, the file header
 70        may have been damaged.
 71    2)  Does the counted number of keys in all nodes equal the count
 72        stored in the file header?  If not, the file header may have
 73        been damaged.
 74    3)  Does the counted total length of all keys equal the count stored
 75        in the file header?  If not, the file header may have been
 76        damaged.
 77 
 78 
 79    For each node in the file the following consistency checks are
 80    performed:
 81    4)  Is this a freed node?  If so, skip further checks.
 82    5)  Are there any branches (keys) in this node?  If not, skip
 83        further checks.
 84 
 85 Node-branch checks
 86    6)  Is branch_count greater than 313?  If so, node is bad because
 87        space in a page limits a node to having, at most, 313
 88        one-character keys.
 89    7)  Is branch_count less than 0?  If so, node is bad.
 90 
 91 
 92 Key-region checks
 93    8)  Is start_of_key_region greater than 4096?  If so, node is bad
 94        because the character position of the first key must lie within
 95        the node page.
 96    9)  Does start_of_key_region overwrite the branch array?  If so,
 97        node is bad because keys have overwritten the array of branches
 98        in the node.
 99    10) Is scattered_free_key_space greater than 4096 minus
100        start_of_key_region?  If so, node is bad because the count of
101        unused space within the key region is greater than the size of
102        the key region itself.
103    11) Is scattered_free_key_space less than 0?  If so, node is bad.
104    12) Is length of all keys in node equal to 4096 minus
105        start_of_key_region minus scattered_free_key_space?  If not, node
106        header is bad.
107 
108 
109 Key-location checks
110    13) Does any branch declare its key to begin prior to
111        start_of_key_region?  If so, node is bad.
112    14) Does any branch declare its key to extend beyond end of node
113        page?  If so, node is bad.
114 
115 Key-overlap check
116    15) Does the storage for any key overlap storage for another key?
117        If so, node is bad.  Note that this test is somewhat time
118        consuming.
119 
120 Key-order check
121    16) Are the keys within the node ordered in increasing ASCII
122        collating sequence?  If not, the node is bad.  Note that this
123        test is somewhat time consuming.
124 
125 
126 Node-tree check
127    17) For each child pointer in the node, does the child pointer
128        reference another node that resides in a node-containing
129        component of the vfile?  If not, the child pointer is bad.
130    18) Does the child pointer reference another node that contains keys
131        (is nonempty)?  If not, the child pointer is bad.
132    19) Does the child pointer reference another node that is not on the
133        list of freed nodes?  If not, the child pointer is bad.
134    20) Does each child pointer in the node reference another node that
135        is not the root node?  If not, the child pointer is bad.
136    21) Is every nonempty node but the root node referenced by a child
137        pointer of some other node?  If not, the node is inaccessible
138        and its keys are effectively not part of the key tree.
139    22) Is any nonempty node referenced by more than one superior node?
140        If so, the key tree is inconsistent.
141 
142 
143 List of requests:
144 .
145    gives name and version number of this program, plus pathname or I/O
146    switch of file being examined.
147 ..
148    escapes Multics command level to execute command_line.
149 ?
150    lists available requests.
151 
152 
153 continue, c
154    continues searching for damaged nodes.
155 quit, q
156    stops further processing, reporting total of damage found so far.
157 total, tt
158    stops reporting, for remainder of this MSF component, information
159    about each damaged node and counts the damaged nodes in this
160    component.
161 
162 
163 Notes: Give either a pathname argument or -io_switch to identify the
164 file to be checked.
165 
166 As an active function, returns true if bad nodes are found, false
167 otherwise.  Normal diagnostic messages are still printed.
168 
169 
170 Notes on request loop operation: When a bad node is found, its
171 location is printed out, followed by the number of branches in the
172 node, its low_key_pos, and its unused key space (scat_space).  Then a
173 request loop is entered that allows you to continue checking other
174 nodes, to quit further checking, or to enter a totaling loop that
175 counts the number of damaged nodes in the current component without
176 printing their statistics.  The request
177    ..ds node_seg node_offset count -ch
178 is a useful thing to do.  Type "c" in the request loop to continue
179 checking the next node.