Import wiredtiger: 315f1424f9a8f97a4634b0cb001e2e7d0ed4b587 from branch mongodb-4.4

ref: c3bb82693f..315f1424f9
for: 4.4.16

WT-9096       Fix search near returning wrong key/value sometimes when key doesn't exist

8 files changed, 69 insertions, 15 deletions

diff --git a/src/third_party/wiredtiger/import.data b/src/third_party/wiredtiger/import.data
index a8a3739cf9c..0b0997732d0 100644
--- a/src/third_party/wiredtiger/import.data
+++ b/src/third_party/wiredtiger/import.data
@@ -2,5 +2,5 @@
     "vendor": "wiredtiger",
     "github": "wiredtiger/wiredtiger.git",
     "branch": "mongodb-4.4",
-    "commit": "c3bb82693f115a3aec828aa5d83b9f1b618140d5"
+    "commit": "315f1424f9a8f97a4634b0cb001e2e7d0ed4b587"
 }
diff --git a/src/third_party/wiredtiger/src/btree/bt_curnext.c b/src/third_party/wiredtiger/src/btree/bt_curnext.c
index 6953eb3dc02..90aaf333027 100644
--- a/src/third_party/wiredtiger/src/btree/bt_curnext.c
+++ b/src/third_party/wiredtiger/src/btree/bt_curnext.c
@@ -440,7 +440,12 @@ restart_read_insert:
         cbt->slot = cbt->row_iteration_slot / 2 - 1;
 restart_read_page:
         rip = &page->pg_row[cbt->slot];
+        /*
+         * The saved cursor key from the slot is used later to match the prefix match or get the
+         * value from the history store if the on-disk data is not visible.
+         */
         WT_RET(__cursor_row_slot_key_return(cbt, rip, &kpack));
+
         /*
          * If the cursor has prefix search configured we can early exit here if the key that we are
          * visiting is after our prefix.
@@ -449,6 +454,7 @@ restart_read_page:
             WT_STAT_CONN_DATA_INCR(session, cursor_search_near_prefix_fast_paths);
             return (WT_NOTFOUND);
         }
+
         WT_RET(
           __wt_txn_read(session, cbt, &cbt->iface.key, WT_RECNO_OOB, WT_ROW_UPDATE(page, rip)));
         if (cbt->upd_value->type == WT_UPDATE_INVALID) {
diff --git a/src/third_party/wiredtiger/src/btree/bt_curprev.c b/src/third_party/wiredtiger/src/btree/bt_curprev.c
index 3941ada539c..08c47d708e2 100644
--- a/src/third_party/wiredtiger/src/btree/bt_curprev.c
+++ b/src/third_party/wiredtiger/src/btree/bt_curprev.c
@@ -589,6 +589,10 @@ restart_read_insert:
         cbt->slot = cbt->row_iteration_slot / 2 - 1;
 restart_read_page:
         rip = &page->pg_row[cbt->slot];
+        /*
+         * The saved cursor key from the slot is used later to get the value from the history store
+         * if the on-disk data is not visible.
+         */
         WT_RET(__cursor_row_slot_key_return(cbt, rip, &kpack));
         /*
          * If the cursor has prefix search configured we can early exit here if the key we are
diff --git a/src/third_party/wiredtiger/src/btree/bt_cursor.c b/src/third_party/wiredtiger/src/btree/bt_cursor.c
index 6cd2b3c3fc7..c30027e4193 100644
--- a/src/third_party/wiredtiger/src/btree/bt_cursor.c
+++ b/src/third_party/wiredtiger/src/btree/bt_cursor.c
@@ -321,6 +321,19 @@ __wt_cursor_valid(WT_CURSOR_BTREE *cbt, WT_ITEM *key, uint64_t recno, bool *vali
         if (cbt->ins != NULL)
             return (0);
 
+        /* Paranoia. */
+        WT_ASSERT(session, recno == WT_RECNO_OOB);
+
+        /*
+         * The key can be NULL only when we didn't find an exact match, copy the search found key
+         * into the temporary buffer for further use.
+         */
+        if (key == NULL) {
+            WT_RET(__wt_row_leaf_key(
+              session, cbt->ref->page, &cbt->ref->page->pg_row[cbt->slot], cbt->tmp, true));
+            key = cbt->tmp;
+        }
+
         /* Check for an update. */
         WT_RET(__wt_txn_read(session, cbt, key, WT_RECNO_OOB,
           (page->modify != NULL && page->modify->mod_row_update != NULL) ?
@@ -662,10 +675,14 @@ __wt_btcur_search_near(WT_CURSOR_BTREE *cbt, int *exactp)
          * better match. This test is simplistic as we're ignoring append lists (there may be no
          * page slots or we might be legitimately positioned after the last page slot). Ignore those
          * cases, it makes things too complicated.
+         *
+         * If there's an exact match, the row-store search function built the key in the cursor's
+         * temporary buffer.
          */
         if (leaf_found &&
           (cbt->compare == 0 || (cbt->slot != 0 && cbt->slot != cbt->ref->page->entries - 1)))
-            WT_ERR(__wt_cursor_valid(cbt, cbt->tmp, WT_RECNO_OOB, &valid));
+            WT_ERR(
+              __wt_cursor_valid(cbt, (cbt->compare == 0 ? cbt->tmp : NULL), WT_RECNO_OOB, &valid));
     }
     if (!valid) {
         WT_ERR(__wt_cursor_func_init(cbt, true));
@@ -676,7 +693,12 @@ __wt_btcur_search_near(WT_CURSOR_BTREE *cbt, int *exactp)
          */
         if (btree->type == BTREE_ROW) {
             WT_ERR(__cursor_row_search(cbt, true, NULL, NULL));
-            WT_ERR(__wt_cursor_valid(cbt, cbt->tmp, WT_RECNO_OOB, &valid));
+            /*
+             * If there's an exact match, the row-store search function built the key in the
+             * cursor's temporary buffer.
+             */
+            WT_ERR(
+              __wt_cursor_valid(cbt, (cbt->compare == 0 ? cbt->tmp : NULL), WT_RECNO_OOB, &valid));
         } else {
             WT_ERR(__cursor_col_search(cbt, NULL, NULL));
             WT_ERR(__wt_cursor_valid(cbt, NULL, cbt->recno, &valid));
diff --git a/src/third_party/wiredtiger/src/btree/bt_ret.c b/src/third_party/wiredtiger/src/btree/bt_ret.c
index 3709c112c2b..6180c085ebf 100644
--- a/src/third_party/wiredtiger/src/btree/bt_ret.c
+++ b/src/third_party/wiredtiger/src/btree/bt_ret.c
@@ -39,15 +39,14 @@ __key_return(WT_CURSOR_BTREE *cbt)
             return (0);
         }
 
+        /*
+         * If there's an exact match, the row-store search function built the key we want to return
+         * in the cursor's temporary buffer. Swap the cursor's search-key and temporary buffers so
+         * we can return it (it's unsafe to return the temporary buffer itself because our caller
+         * might do another search in this table using the key we return, and we'd corrupt the
+         * search key during any subsequent search that used the temporary buffer).
+         */
         if (cbt->compare == 0) {
-            /*
-             * If not in an insert list and there's an exact match, the row-store search function
-             * built the key we want to return in the cursor's temporary buffer. Swap the cursor's
-             * search-key and temporary buffers so we can return it (it's unsafe to return the
-             * temporary buffer itself because our caller might do another search in this table
-             * using the key we return, and we'd corrupt the search key during any subsequent search
-             * that used the temporary buffer).
-             */
             tmp = cbt->row_key;
             cbt->row_key = cbt->tmp;
             cbt->tmp = tmp;
diff --git a/src/third_party/wiredtiger/src/btree/row_srch.c b/src/third_party/wiredtiger/src/btree/row_srch.c
index 310659bb197..abd98bbd506 100644
--- a/src/third_party/wiredtiger/src/btree/row_srch.c
+++ b/src/third_party/wiredtiger/src/btree/row_srch.c
@@ -61,6 +61,16 @@ __search_insert_append(WT_SESSION_IMPL *session, WT_CURSOR_BTREE *cbt, WT_INSERT
         cbt->compare = -cmp;
         cbt->ins = ins;
         cbt->ins_head = ins_head;
+
+        /*
+         * If we find an exact match, copy the key into the temporary buffer, our callers expect to
+         * find it there.
+         */
+        if (cbt->compare == 0) {
+            cbt->tmp->data = WT_INSERT_KEY(cbt->ins);
+            cbt->tmp->size = WT_INSERT_KEY_SIZE(cbt->ins);
+        }
+
         *donep = 1;
     }
     return (0);
@@ -471,7 +481,6 @@ leaf_only:
             ins_head = WT_ROW_INSERT_SMALLEST(page);
         } else {
             cbt->slot = WT_ROW_SLOT(page, page->pg_row + (page->entries - 1));
-
             ins_head = WT_ROW_INSERT_SLOT(page, cbt->slot);
         }
 
@@ -586,7 +595,8 @@ leaf_match:
 
     /*
      * Test for an append first when inserting onto an insert list, try to catch cursors repeatedly
-     * inserting at a single point.
+     * inserting at a single point, then search the insert list. If we find an exact match, copy the
+     * key into the temporary buffer, our callers expect to find it there.
      */
     if (insert) {
         WT_ERR(__search_insert_append(session, cbt, ins_head, srch_key, &done));
@@ -594,7 +604,10 @@ leaf_match:
             return (0);
     }
     WT_ERR(__wt_search_insert(session, cbt, ins_head, srch_key));
-
+    if (cbt->compare == 0) {
+        cbt->tmp->data = WT_INSERT_KEY(cbt->ins);
+        cbt->tmp->size = WT_INSERT_KEY_SIZE(cbt->ins);
+    }
     return (0);
 
 err:
diff --git a/src/third_party/wiredtiger/src/include/txn_inline.h b/src/third_party/wiredtiger/src/include/txn_inline.h
index c9247515bb8..6e7b40e9cad 100644
--- a/src/third_party/wiredtiger/src/include/txn_inline.h
+++ b/src/third_party/wiredtiger/src/include/txn_inline.h
@@ -991,7 +991,7 @@ retry:
     WT_ASSERT(session, cbt->upd_value->type == WT_UPDATE_INVALID);
 
     /* If there is no ondisk value, there can't be anything in the history store either. */
-    if (cbt->ref->page->dsk == NULL || cbt->slot == UINT32_MAX) {
+    if (cbt->ref->page->dsk == NULL) {
         cbt->upd_value->type = WT_UPDATE_TOMBSTONE;
         return (0);
     }
diff --git a/src/third_party/wiredtiger/test/checkpoint/workers.c b/src/third_party/wiredtiger/test/checkpoint/workers.c
index 5ed22005fe5..2845658e106 100644
--- a/src/third_party/wiredtiger/test/checkpoint/workers.c
+++ b/src/third_party/wiredtiger/test/checkpoint/workers.c
@@ -195,6 +195,16 @@ worker_op(WT_CURSOR *cursor, uint64_t keyno, u_int new_val)
                 return (WT_ROLLBACK);
             return (log_print_err("cursor.search_near", ret, 1));
         }
+
+        /* Retry the result of search_near again to confirm the result. */
+        if (new_val % 2 == 0) {
+            if ((ret = cursor->search(cursor)) != 0) {
+                if (ret == WT_ROLLBACK)
+                    return (WT_ROLLBACK);
+                return (log_print_err("cursor.search", ret, 1));
+            }
+        }
+
         if (cmp < 0) {
             if ((ret = cursor->next(cursor)) != 0) {
                 if (ret == WT_NOTFOUND)