WT-2307: add HAVE_DIAGNOSTIC checks for cursors not returning keys

out-of-order.

7 files changed, 104 insertions, 79 deletions

diff --git a/src/btree/bt_curnext.c b/src/btree/bt_curnext.c
index 8b74a2c7ffd..d2e659fca78 100644
--- a/src/btree/bt_curnext.c
+++ b/src/btree/bt_curnext.c
@@ -389,6 +389,14 @@ __wt_btcur_iterate_setup(WT_CURSOR_BTREE *cbt)
 	 */
 	cbt->page_deleted_count = 0;
 
+#ifdef HAVE_DIAGNOSTIC
+	/*
+	 * If starting a new iteration, clear the last-key returned, it doesn't
+	 * apply.
+	 */
+	cbt->lastkey->size = 0;
+	cbt->lastrecno = WT_RECNO_OOB;
+#endif
 	/*
 	 * 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.
@@ -430,63 +438,105 @@ __wt_btcur_iterate_setup(WT_CURSOR_BTREE *cbt)
 	}
 }
 
+#ifdef HAVE_DIAGNOSTIC
 /*
- * __wt_set_last_op --
- *	Set the last operation.
+ * __cursor_key_order_check_col --
+ *	Check key ordering for column-store cursor movements.
  */
-void
-__wt_set_last_op(WT_CURSOR_BTREE *cbt, int v)
+static int
+__cursor_key_order_check_col(
+    WT_SESSION_IMPL *session, WT_CURSOR_BTREE *cbt, bool next)
 {
-	int i;
+	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;
+	}
 
-	for (i = 20; --i > 0;)
-		cbt->last_op[i] = cbt->last_op[i - 1];
-	cbt->last_op[0] = v;
+	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);
 }
 
 /*
- * __key_order_check --
- *	Check key ordering for cursor movements.
+ * __cursor_key_order_check_row --
+ *	Check key ordering for row-store cursor movements.
  */
 static int
-__key_order_check(WT_SESSION_IMPL *session, WT_CURSOR_BTREE *cbt)
+__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 ((ret = __wt_compare(
-	    session, btree->collator, cbt->lastkey, key, &cmp)) != 0)
-		WT_RET_MSG(session, ret,
-		    "WT-2307: comparison function failed");
-	if (cmp < 0)
-		return (0);
+	if (cbt->lastkey->size != 0)
+		WT_RET(__wt_compare(
+		    session, btree->collator, cbt->lastkey, key, &cmp));
 
-	/* Flag an error and keep going */
-	__wt_errx(session, "encountered out of order key");
+	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));
 
-	/*
-	 * The cursor next hit a bug due to a race in splits, move the cursor
-	 * back to the last known good position and retry the next.
-	 */
-	key->data = cbt->lastkey->data;
-	key->size = cbt->lastkey->size;
-	if ((ret = __wt_btcur_search(cbt)) != 0)
-		WT_RET_MSG(session, ret,
-		    "WT-2307: searching for the previous key failed");
+	WT_ERR(__wt_scr_alloc(session, 512, &a));
+	WT_ERR(__wt_buf_set_printable(
+	    session, a, cbt->lastkey->data, cbt->lastkey->size));
+
+	WT_ERR(__wt_scr_alloc(session, 512, &b));
+	WT_ERR(__wt_buf_set_printable(session, b, key->data, key->size));
 
-	/* Set last op as a next, in case we need to loop retrying */
-	cbt->last_op[0] = WT_LASTOP_NEXT;
+	WT_PANIC_ERR(session, EINVAL,
+	    "WT_CURSOR.%s out-of-order returns: returned key %.*s then "
+	    "key %.*s",
+	    next ? "next" : "prev",
+	    (int)a->size, (const char *)a->data,
+	    (int)b->size, (const char *)b->data);
 
-	/* Return a duplicate key error to tell next it needs to retry. */
-	return (WT_DUPLICATE_KEY);
+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);
+	}
+}
+#endif
+
+/*
  * __wt_btcur_next --
  *	Move to the next record in the tree.
  */
@@ -508,7 +558,7 @@ __wt_btcur_next(WT_CURSOR_BTREE *cbt, bool truncating)
 	if (truncating)
 		LF_SET(WT_READ_TRUNCATE);
 
-retry:	WT_RET(__cursor_func_init(cbt, false));
+	WT_RET(__cursor_func_init(cbt, false));
 
 	/*
 	 * If we aren't already iterating in the right direction, there's
@@ -587,24 +637,10 @@ retry:	WT_RET(__cursor_func_init(cbt, false));
 		WT_ERR_TEST(cbt->ref == NULL, WT_NOTFOUND);
 	}
 
-	/*
-	 * WT-2307 check that the previous key returned sorts less than
-	 * the current key being returned. If it didn't we've searched back
-	 * to the previous key, retry the next operation.
-	 */
-	if (ret == 0 && page->type == WT_PAGE_ROW_LEAF) {
-		if (cbt->last_op[0] == WT_LASTOP_NEXT &&
-		    cbt->lastkey != NULL && cbt->lastkey->size != 0) {
-			ret = __key_order_check(session, cbt);
-			if (ret == WT_DUPLICATE_KEY)
-				goto retry;
-			WT_ERR(ret);
-		}
-
-		WT_ERR(__wt_buf_set(session,
-		    cbt->lastkey, cbt->iface.key.data, cbt->iface.key.size));
-	}
-	__wt_set_last_op(cbt, WT_LASTOP_NEXT);
+#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));
diff --git a/src/btree/bt_curprev.c b/src/btree/bt_curprev.c
index 5ce54f60648..1e4b1daa090 100644
--- a/src/btree/bt_curprev.c
+++ b/src/btree/bt_curprev.c
@@ -532,7 +532,6 @@ __wt_btcur_prev(WT_CURSOR_BTREE *cbt, bool truncating)
 	bool newpage;
 
 	session = (WT_SESSION_IMPL *)cbt->iface.session;
-	__wt_set_last_op(cbt, WT_LASTOP_PREV);
 
 	WT_STAT_FAST_CONN_INCR(session, cursor_prev);
 	WT_STAT_FAST_DATA_INCR(session, cursor_prev);
@@ -619,6 +618,10 @@ __wt_btcur_prev(WT_CURSOR_BTREE *cbt, bool truncating)
 		WT_ERR(__wt_tree_walk(session, &cbt->ref, flags));
 		WT_ERR_TEST(cbt->ref == NULL, WT_NOTFOUND);
 	}
+#ifdef HAVE_DIAGNOSTIC
+	if (ret == 0)
+		WT_ERR(__wt_cursor_key_order_check(session, cbt, false));
+#endif
 
 err:	if (ret != 0)
 		WT_TRET(__cursor_reset(cbt));
diff --git a/src/btree/bt_cursor.c b/src/btree/bt_cursor.c
index 55c7b8fef33..28b51fd2865 100644
--- a/src/btree/bt_cursor.c
+++ b/src/btree/bt_cursor.c
@@ -313,7 +313,6 @@ __wt_btcur_search(WT_CURSOR_BTREE *cbt)
 	session = (WT_SESSION_IMPL *)cursor->session;
 	upd = NULL;					/* -Wuninitialized */
 
-	__wt_set_last_op(cbt, WT_LASTOP_SEARCH);
 	WT_STAT_FAST_CONN_INCR(session, cursor_search);
 	WT_STAT_FAST_DATA_INCR(session, cursor_search);
 
@@ -381,7 +380,6 @@ __wt_btcur_search_near(WT_CURSOR_BTREE *cbt, int *exactp)
 	upd = NULL;					/* -Wuninitialized */
 	exact = 0;
 
-	__wt_set_last_op(cbt, WT_LASTOP_SEARCH_NEAR);
 	WT_STAT_FAST_CONN_INCR(session, cursor_search_near);
 	WT_STAT_FAST_DATA_INCR(session, cursor_search_near);
 
@@ -489,7 +487,6 @@ __wt_btcur_insert(WT_CURSOR_BTREE *cbt)
 	cursor = &cbt->iface;
 	session = (WT_SESSION_IMPL *)cursor->session;
 
-	__wt_set_last_op(cbt, WT_LASTOP_INSERT);
 	WT_STAT_FAST_CONN_INCR(session, cursor_insert);
 	WT_STAT_FAST_DATA_INCR(session, cursor_insert);
 	WT_STAT_FAST_DATA_INCRV(session,
@@ -658,7 +655,6 @@ __wt_btcur_remove(WT_CURSOR_BTREE *cbt)
 	cursor = &cbt->iface;
 	session = (WT_SESSION_IMPL *)cursor->session;
 
-	__wt_set_last_op(cbt, WT_LASTOP_REMOVE);
 	WT_STAT_FAST_CONN_INCR(session, cursor_remove);
 	WT_STAT_FAST_DATA_INCR(session, cursor_remove);
 	WT_STAT_FAST_DATA_INCRV(session, cursor_remove_bytes, cursor->key.size);
@@ -744,7 +740,6 @@ __wt_btcur_update(WT_CURSOR_BTREE *cbt)
 	cursor = &cbt->iface;
 	session = (WT_SESSION_IMPL *)cursor->session;
 
-	__wt_set_last_op(cbt, WT_LASTOP_UPDATE);
 	WT_STAT_FAST_CONN_INCR(session, cursor_update);
 	WT_STAT_FAST_DATA_INCR(session, cursor_update);
 	WT_STAT_FAST_DATA_INCRV(
@@ -1164,8 +1159,6 @@ __wt_btcur_range_truncate(WT_CURSOR_BTREE *start, WT_CURSOR_BTREE *stop)
 	cbt = (start != NULL) ? start : stop;
 	session = (WT_SESSION_IMPL *)cbt->iface.session;
 	btree = cbt->btree;
-
-	__wt_set_last_op(cbt, WT_LASTOP_TRUNCATE);
 	WT_STAT_FAST_DATA_INCR(session, cursor_truncate);
 
 	/*
@@ -1241,7 +1234,10 @@ __wt_btcur_open(WT_CURSOR_BTREE *cbt)
 	cbt->row_key = &cbt->_row_key;
 	cbt->tmp = &cbt->_tmp;
 
+#ifdef HAVE_DIAGNOSTIC
 	cbt->lastkey = &cbt->_lastkey;
+	cbt->lastrecno = WT_RECNO_OOB;
+#endif
 }
 
 /*
@@ -1267,7 +1263,9 @@ __wt_btcur_close(WT_CURSOR_BTREE *cbt, bool lowlevel)
 
 	__wt_buf_free(session, &cbt->_row_key);
 	__wt_buf_free(session, &cbt->_tmp);
+#ifdef HAVE_DIAGNOSTIC
 	__wt_buf_free(session, &cbt->_lastkey);
+#endif
 
 	return (ret);
 }
diff --git a/src/include/cursor.h b/src/include/cursor.h
index db5774e5cb6..4f232ce4fd0 100644
--- a/src/include/cursor.h
+++ b/src/include/cursor.h
@@ -192,22 +192,6 @@ struct __wt_cursor_btree {
 	WT_UPDATE *modify_update;
 
 	/*
-	 * WT-2307 tracking for a bug where cursor next jumps backwards.
-	 */
-	WT_ITEM *lastkey, _lastkey;
-
-#define	WT_LASTOP_NEXT		1
-#define	WT_LASTOP_PREV		2
-#define	WT_LASTOP_RESET		3
-#define	WT_LASTOP_SEARCH	4
-#define	WT_LASTOP_SEARCH_NEAR	5
-#define	WT_LASTOP_INSERT	6
-#define	WT_LASTOP_TRUNCATE	7
-#define	WT_LASTOP_UPDATE	8
-#define	WT_LASTOP_REMOVE	9
-	uint8_t last_op[20];		/* Last 20 operations */
-
-	/*
 	 * Fixed-length column-store items are a single byte, and it's simpler
 	 * and cheaper to allocate the space for it now than keep checking to
 	 * see if we need to grow the buffer.
@@ -216,6 +200,12 @@ struct __wt_cursor_btree {
 
 	uint8_t	append_tree;		/* Cursor appended to the tree */
 
+#ifdef HAVE_DIAGNOSTIC
+	/* Check that cursor next/prev never returns keys out-of-order. */
+	WT_ITEM *lastkey, _lastkey;
+	uint64_t lastrecno;
+#endif
+
 #define	WT_CBT_ACTIVE		0x01	/* Active in the tree */
 #define	WT_CBT_ITERATE_APPEND	0x02	/* Col-store: iterating append list */
 #define	WT_CBT_ITERATE_NEXT	0x04	/* Next iteration configuration */
diff --git a/src/include/cursor.i b/src/include/cursor.i
index f7f6e74e018..2e382591313 100644
--- a/src/include/cursor.i
+++ b/src/include/cursor.i
@@ -279,8 +279,6 @@ __cursor_reset(WT_CURSOR_BTREE *cbt)
 {
 	WT_DECL_RET;
 
-	__wt_set_last_op(cbt, WT_LASTOP_RESET);
-
 	/*
 	 * The cursor is leaving the API, and no longer holds any position,
 	 * generally called to clean up the cursor after an error.
diff --git a/src/include/extern.h b/src/include/extern.h
index b3257f8a045..18d1d292c15 100644
--- a/src/include/extern.h
+++ b/src/include/extern.h
@@ -91,7 +91,7 @@ extern int __wt_bloom_drop(WT_BLOOM *bloom, const char *config);
 extern int __wt_compact(WT_SESSION_IMPL *session, const char *cfg[]);
 extern int __wt_compact_page_skip(WT_SESSION_IMPL *session, WT_REF *ref, bool *skipp);
 extern void __wt_btcur_iterate_setup(WT_CURSOR_BTREE *cbt);
-extern void __wt_set_last_op(WT_CURSOR_BTREE *cbt, int v);
+extern int __wt_cursor_key_order_check( WT_SESSION_IMPL *session, WT_CURSOR_BTREE *cbt, bool next);
 extern int __wt_btcur_next(WT_CURSOR_BTREE *cbt, bool truncating);
 extern int __wt_btcur_prev(WT_CURSOR_BTREE *cbt, bool truncating);
 extern int __wt_btcur_reset(WT_CURSOR_BTREE *cbt);
diff --git a/test/format/ops.c b/test/format/ops.c
index c705d362fe8..7e299b7d975 100644
--- a/test/format/ops.c
+++ b/test/format/ops.c
@@ -504,7 +504,7 @@ skip_insert:			if (col_update(tinfo,
 		 */
 		if (!insert) {
 			dir = (int)mmrand(&tinfo->rnd, 0, 1);
-			for (np = 0; np < mmrand(&tinfo->rnd, 1, 8); ++np) {
+			for (np = 0; np < mmrand(&tinfo->rnd, 1, 30); ++np) {
 				if (notfound)
 					break;
 				if (nextprev(cursor, dir, &notfound))