-
- treePathTable [level].node = curNodeNum;
-
- if ( ((BTNodeDescriptor*)nodeRec.buffer)->kind == kBTLeafNode)
- {
- treePathTable [level].index = index;
- break; // were done...
- }
-
- if ( (keyFound != true) && (index != 0))
- --index;
-
- treePathTable [level].index = index;
-
- GetRecordByIndex (btreePtr, nodeRec.buffer, index, &keyPtr, &dataPtr, &dataSize);
- curNodeNum = *(UInt32 *)dataPtr;
- err = ReleaseNode (btreePtr, &nodeRec);
- if (err != noErr)
- {
- goto ErrorExit;
- }
+ //
+ // [2550929] Sanity check the node height and node type. We expect
+ // particular values at each iteration in the search. This checking
+ // quickly finds bad pointers, loops, and other damage to the
+ // hierarchy of the B-tree.
+ //
+ if (((BTNodeDescriptor*)nodeRec.buffer)->height != level)
+ {
+// Panic("\pIncorrect node height");
+ err = btBadNode;
+ goto ReleaseAndExit;
+ }
+ nodeKind = ((BTNodeDescriptor*)nodeRec.buffer)->kind;
+ if (level == 1)
+ {
+ // Nodes at level 1 must be leaves, by definition
+ if (nodeKind != kBTLeafNode)
+ {
+ // Panic("\pIncorrect node type: expected leaf");
+ err = btBadNode;
+ goto ReleaseAndExit;
+ }
+ }
+ else
+ {
+ // A node at any other depth must be an index node
+ if (nodeKind != kBTIndexNode)
+ {
+// Panic("\pIncorrect node type: expected index");
+ err = btBadNode;
+ goto ReleaseAndExit;
+ }
+ }
+
+ keyFound = SearchNode (btreePtr, nodeRec.buffer, searchKey, &index);
+
+ treePathTable [level].node = curNodeNum;
+
+ if (nodeKind == kBTLeafNode)
+ {
+ treePathTable [level].index = index;
+ break; // were done...
+ }
+
+ if ( (keyFound != true) && (index != 0))
+ --index;
+
+ treePathTable [level].index = index;
+
+ err = GetRecordByIndex (btreePtr, nodeRec.buffer, index, &keyPtr, &dataPtr, &dataSize);
+ if (err != noErr)
+ {
+ // [2550929] If we got an error, it is probably because the index was bad
+ // (typically a corrupt node that confused SearchNode). Invalidate the node
+ // so we won't accidentally use the corrupted contents. NOTE: the Mac OS 9
+ // sources call this InvalidateNode.
+
+ (void) TrashNode(btreePtr, &nodeRec);
+ goto ErrorExit;
+ }
+
+ // Get the child pointer out of this index node. We're now done with the current
+ // node and can continue the search with the child node.
+ curNodeNum = *(UInt32 *)dataPtr;
+ err = ReleaseNode (btreePtr, &nodeRec);
+ if (err != noErr)
+ {
+ goto ErrorExit;
+ }
+
+ // The child node should be at a level one less than the parent.
+ --level;
projects / apple / xnu.git / blobdiff