1 files changed, 155 insertions, 14 deletions

diff --git a/src/third_party/wiredtiger/src/btree/bt_curnext.c b/src/third_party/wiredtiger/src/btree/bt_curnext.c
index 55843d1cae5..63b2e2abebc 100644
--- a/src/third_party/wiredtiger/src/btree/bt_curnext.c
+++ b/src/third_party/wiredtiger/src/btree/bt_curnext.c
@@ -1,5 +1,5 @@
 /*-
- * Copyright (c) 2014-2015 MongoDB, Inc.
+ * Copyright (c) 2014-2016 MongoDB, Inc.
  * Copyright (c) 2008-2014 WiredTiger, Inc.
  *	All rights reserved.
  *
@@ -31,13 +31,12 @@ __cursor_fix_append_next(WT_CURSOR_BTREE *cbt, bool newpage)
 			return (WT_NOTFOUND);
 
 	/*
-	 * This code looks different from the cursor-previous code.  The append
-	 * list appears on the last page of the tree, but it may be preceded by
-	 * other rows, which means the cursor's recno will be set to a value and
-	 * we simply want to increment it.  If the cursor's recno is NOT set,
-	 * we're starting our iteration in a tree that has only appended items.
-	 * In that case, recno will be 0 and happily enough the increment will
-	 * set it to 1, which is correct.
+	 * This code looks different from the cursor-previous code. The append
+	 * list may be preceded by other rows, which means the cursor's recno
+	 * will be set to a value and we simply want to increment it. If the
+	 * cursor's recno is NOT set, we're starting an iteration in a tree with
+	 * only appended items. In that case, recno will be 0 and happily enough
+	 * the increment will set it to 1, which is correct.
 	 */
 	__cursor_set_recno(cbt, cbt->recno + 1);
 
@@ -368,6 +367,140 @@ new_insert:	if ((ins = cbt->ins) != NULL) {
 	/* NOTREACHED */
 }
 
+#ifdef HAVE_DIAGNOSTIC
+/*
+ * __cursor_key_order_check_col --
+ *	Check key ordering for column-store cursor movements.
+ */
+static int
+__cursor_key_order_check_col(
+    WT_SESSION_IMPL *session, WT_CURSOR_BTREE *cbt, bool next)
+{
+	int cmp;
+
+	cmp = 0;			/* -Werror=maybe-uninitialized */
+
+	if (cbt->lastrecno != WT_RECNO_OOB) {
+		if (cbt->lastrecno < cbt->recno)
+			cmp = -1;
+		if (cbt->lastrecno > cbt->recno)
+			cmp = 1;
+	}
+
+	if (cbt->lastrecno == WT_RECNO_OOB ||
+	    (next && cmp < 0) || (!next && cmp > 0)) {
+		cbt->lastrecno = cbt->recno;
+		return (0);
+	}
+
+	WT_PANIC_RET(session, EINVAL,
+	    "WT_CURSOR.%s out-of-order returns: returned key %" PRIu64 " then "
+	    "key %" PRIu64,
+	    next ? "next" : "prev", cbt->lastrecno, cbt->recno);
+}
+
+/*
+ * __cursor_key_order_check_row --
+ *	Check key ordering for row-store cursor movements.
+ */
+static int
+__cursor_key_order_check_row(
+    WT_SESSION_IMPL *session, WT_CURSOR_BTREE *cbt, bool next)
+{
+	WT_BTREE *btree;
+	WT_ITEM *key;
+	WT_DECL_RET;
+	WT_DECL_ITEM(a);
+	WT_DECL_ITEM(b);
+	int cmp;
+
+	btree = S2BT(session);
+	key = &cbt->iface.key;
+	cmp = 0;			/* -Werror=maybe-uninitialized */
+
+	if (cbt->lastkey->size != 0)
+		WT_RET(__wt_compare(
+		    session, btree->collator, cbt->lastkey, key, &cmp));
+
+	if (cbt->lastkey->size == 0 || (next && cmp < 0) || (!next && cmp > 0))
+		return (__wt_buf_set(session,
+		    cbt->lastkey, cbt->iface.key.data, cbt->iface.key.size));
+
+	WT_ERR(__wt_scr_alloc(session, 512, &a));
+	WT_ERR(__wt_scr_alloc(session, 512, &b));
+
+	WT_PANIC_ERR(session, EINVAL,
+	    "WT_CURSOR.%s out-of-order returns: returned key %s then key %s",
+	    next ? "next" : "prev",
+	    __wt_buf_set_printable(
+	    session, cbt->lastkey->data, cbt->lastkey->size, a),
+	    __wt_buf_set_printable(session, key->data, key->size, b));
+
+err:	__wt_scr_free(session, &a);
+	__wt_scr_free(session, &b);
+
+	return (ret);
+}
+
+/*
+ * __wt_cursor_key_order_check --
+ *	Check key ordering for cursor movements.
+ */
+int
+__wt_cursor_key_order_check(
+    WT_SESSION_IMPL *session, WT_CURSOR_BTREE *cbt, bool next)
+{
+	switch (cbt->ref->page->type) {
+	case WT_PAGE_COL_FIX:
+	case WT_PAGE_COL_VAR:
+		return (__cursor_key_order_check_col(session, cbt, next));
+	case WT_PAGE_ROW_LEAF:
+		return (__cursor_key_order_check_row(session, cbt, next));
+	WT_ILLEGAL_VALUE(session);
+	}
+	/* NOTREACHED */
+}
+
+/*
+ * __wt_cursor_key_order_init --
+ *	Initialize key ordering checks for cursor movements after a successful
+ * search.
+ */
+int
+__wt_cursor_key_order_init(WT_SESSION_IMPL *session, WT_CURSOR_BTREE *cbt)
+{
+	/*
+	 * Cursor searches set the position for cursor movements, set the
+	 * last-key value for diagnostic checking.
+	 */
+	switch (cbt->ref->page->type) {
+	case WT_PAGE_COL_FIX:
+	case WT_PAGE_COL_VAR:
+		cbt->lastrecno = cbt->recno;
+		return (0);
+	case WT_PAGE_ROW_LEAF:
+		return (__wt_buf_set(session,
+		    cbt->lastkey, cbt->iface.key.data, cbt->iface.key.size));
+	WT_ILLEGAL_VALUE(session);
+	}
+	/* NOTREACHED */
+}
+
+/*
+ * __wt_cursor_key_order_reset --
+ *	Turn off key ordering checks for cursor movements.
+ */
+void
+__wt_cursor_key_order_reset(WT_CURSOR_BTREE *cbt)
+{
+	/*
+	 * Clear the last-key returned, it doesn't apply.
+	 */
+	cbt->lastkey->size = 0;
+	cbt->lastrecno = WT_RECNO_OOB;
+}
+#endif
+
 /*
  * __wt_btcur_iterate_setup --
  *	Initialize a cursor for iteration, usually based on a search.
@@ -393,10 +526,14 @@ __wt_btcur_iterate_setup(WT_CURSOR_BTREE *cbt)
 	 * If we don't have a search page, then we're done, we're starting at
 	 * the beginning or end of the tree, not as a result of a search.
 	 */
-	if (cbt->ref == NULL)
+	if (cbt->ref == NULL) {
+#ifdef HAVE_DIAGNOSTIC
+		__wt_cursor_key_order_reset(cbt);
+#endif
 		return;
-	page = cbt->ref->page;
+	}
 
+	page = cbt->ref->page;
 	if (page->type == WT_PAGE_ROW_LEAF) {
 		/*
 		 * For row-store pages, we need a single item that tells us the
@@ -468,7 +605,6 @@ __wt_btcur_next(WT_CURSOR_BTREE *cbt, bool truncating)
 	 */
 	for (newpage = false;; newpage = true) {
 		page = cbt->ref == NULL ? NULL : cbt->ref->page;
-		WT_ASSERT(session, page == NULL || !WT_PAGE_IS_INTERNAL(page));
 
 		if (F_ISSET(cbt, WT_CBT_ITERATE_APPEND)) {
 			switch (page->type) {
@@ -502,9 +638,9 @@ __wt_btcur_next(WT_CURSOR_BTREE *cbt, bool truncating)
 				break;
 
 			/*
-			 * The last page in a column-store has appended entries.
-			 * We handle it separately from the usual cursor code:
-			 * it's only that one page and it's in a simple format.
+			 * Column-store pages may have appended entries. Handle
+			 * it separately from the usual cursor code, it's in a
+			 * simple format.
 			 */
 			if (page->type != WT_PAGE_ROW_LEAF &&
 			    (cbt->ins_head = WT_COL_APPEND(page)) != NULL) {
@@ -531,6 +667,11 @@ __wt_btcur_next(WT_CURSOR_BTREE *cbt, bool truncating)
 		WT_ERR_TEST(cbt->ref == NULL, WT_NOTFOUND);
 	}
 
+#ifdef HAVE_DIAGNOSTIC
+	if (ret == 0)
+		WT_ERR(__wt_cursor_key_order_check(session, cbt, true));
+#endif
+
 err:	if (ret != 0)
 		WT_TRET(__cursor_reset(cbt));
 	return (ret);