Fix abnormal compression due to out-of-control recompress (#9849)

This pr is following #9779 .

## Describe of feature
Now when we turn on the `list-compress-depth` configuration, the list will compress
the ziplist between `[list-compress-depth, -list-compress-depth]`.
When we need to use the compressed data, we will first decompress it, then use it,
and finally compress it again.
It's controlled by `quicklistNode->recompress`, which is designed to avoid the need to
re-traverse the entire quicklist for compression after each decompression, we only need
to recompress the quicklsitNode being used.
In order to ensure the correctness of recompressing, we should normally let
quicklistDecompressNodeForUse and quicklistCompress appear in pairs, otherwise,
it may lead to the head and tail being compressed or the middle ziplist not being
compressed correctly, which is exactly the problem this pr needs to solve.

## Solution
1. Reset `quicklistIter` after insert and replace.
    The quicklist node will be compressed in `quicklistInsertAfter`, `quicklistInsertBefore`,
   `quicklistReplaceAtIndex`, so we can safely reset the quicklistIter to avoid it being used again
2. `quicklistIndex` will return an iterator that can be used to recompress the current node after use.
    
## Test
1. In the `Stress Tester for #3343-Similar Errors` test, when the server crashes or when
   `valgrind` or `asan` error is detected, print violating commands.
2. Add a crash test due to wrongly recompressing after `lrem`.
3. Remove `insert before with 0 elements` and `insert after with 0 elements`,
   Now we forbid any operation on an NULL quicklistIter.

1 files changed, 295 insertions, 239 deletions

diff --git a/src/quicklist.c b/src/quicklist.c
index 346f44b73..b735d98e2 100644
--- a/src/quicklist.c
+++ b/src/quicklist.c
@@ -112,6 +112,14 @@ void _quicklistBookmarkDelete(quicklist *ql, quicklistBookmark *bm);
         (e)->sz = 0;                                                           \
     } while (0)
 
+/* Reset the quicklistIter to prevent it from being used again after
+ * insert, replace, or other against quicklist operation. */
+#define resetIterator(iter)                                                    \
+    do {                                                                       \
+        (iter)->current = NULL;                                                \
+        (iter)->zi = NULL;                                                     \
+    } while (0)
+
 /* Create a new quicklist.
  * Free with quicklistRelease(). */
 quicklist *quicklistCreate(void) {
@@ -294,10 +302,10 @@ size_t quicklistGetLzf(const quicklistNode *node, void **data) {
  * If compress depth is larger than the entire list, we return immediately. */
 REDIS_STATIC void __quicklistCompress(const quicklist *quicklist,
                                       quicklistNode *node) {
-    /* The head and tail should never be compressed (we should not attempt to recompress them)
-     * This needs to be an assertion in the future */
-    if (quicklist->head) quicklist->head->recompress = 0;
-    if (quicklist->tail) quicklist->tail->recompress = 0;
+    if (quicklist->len == 0) return;
+
+    /* The head and tail should never be compressed (we should not attempt to recompress them) */
+    assert(quicklist->head->recompress == 0 && quicklist->tail->recompress == 0);
 
     /* If length is less than our compress depth (from both sides),
      * we can't compress anything. */
@@ -418,6 +426,8 @@ REDIS_STATIC void __quicklistInsertNode(quicklist *quicklist,
 
     if (old_node)
         quicklistCompress(quicklist, old_node);
+
+    quicklistCompress(quicklist, new_node);
 }
 
 /* Wrappers for node inserting around existing node. */
@@ -716,12 +726,15 @@ void quicklistDelEntry(quicklistIter *iter, quicklistEntry *entry) {
 }
 
 /* Replace quicklist entry by 'data' with length 'sz'. */
-void quicklistReplaceEntry(quicklist *quicklist, quicklistEntry *entry,
-                           void *data, size_t sz) {
+void quicklistReplaceEntry(quicklistIter *iter, quicklistEntry *entry,
+                           void *data, size_t sz)
+{
+    quicklist* quicklist = iter->quicklist;
+
     if (likely(!QL_NODE_IS_PLAIN(entry->node) && !isLargeElement(sz))) {
         entry->node->entry = lpReplace(entry->node->entry, &entry->zi, data, sz);
         quicklistNodeUpdateSz(entry->node);
-        /* quicklistNext() and quicklistIndex() provide an uncompressed node */
+        /* quicklistNext() and quicklistGetIteratorEntryAtIdx() provide an uncompressed node */
         quicklistCompress(quicklist, entry->node);
     } else if (QL_NODE_IS_PLAIN(entry->node)) {
         if (isLargeElement(sz)) {
@@ -731,19 +744,23 @@ void quicklistReplaceEntry(quicklist *quicklist, quicklistEntry *entry,
             memcpy(entry->node->entry, data, sz);
             quicklistCompress(quicklist, entry->node);
         } else {
-            quicklistInsertAfter(quicklist, entry, data, sz);
+            quicklistInsertAfter(iter, entry, data, sz);
             __quicklistDelNode(quicklist, entry->node);
         }
     } else {
-        quicklistInsertAfter(quicklist, entry, data, sz);
-        if (entry->node->count == 1)
+        quicklistInsertAfter(iter, entry, data, sz);
+        if (entry->node->count == 1) {
             __quicklistDelNode(quicklist, entry->node);
-        else {
+        } else {
             unsigned char *p = lpSeek(entry->node->entry, -1);
             quicklistDelIndex(quicklist, entry->node, &p);
             quicklistCompress(quicklist, entry->node->next);
         }
     }
+
+    /* In any case, we reset iterator to forbid use of iterator after insert.
+     * Notice: iter->current has been compressed above. */
+    resetIterator(iter);
 }
 
 /* Replace quicklist entry at offset 'index' by 'data' with length 'sz'.
@@ -753,8 +770,10 @@ void quicklistReplaceEntry(quicklist *quicklist, quicklistEntry *entry,
 int quicklistReplaceAtIndex(quicklist *quicklist, long index, void *data,
                             size_t sz) {
     quicklistEntry entry;
-    if (likely(quicklistIndex(quicklist, index, &entry))) {
-        quicklistReplaceEntry(quicklist, &entry, data, sz);
+    quicklistIter *iter = quicklistGetIteratorEntryAtIdx(quicklist, index, &entry);
+    if (likely(iter)) {
+        quicklistReplaceEntry(iter, &entry, data, sz);
+        quicklistReleaseIterator(iter);
         return 1;
     } else {
         return 0;
@@ -911,8 +930,10 @@ REDIS_STATIC quicklistNode *_quicklistSplitNode(quicklistNode *node, int offset,
  *
  * If after==1, the new value is inserted after 'entry', otherwise
  * the new value is inserted before 'entry'. */
-REDIS_STATIC void _quicklistInsert(quicklist *quicklist, quicklistEntry *entry,
-                                   void *value, const size_t sz, int after) {
+REDIS_STATIC void _quicklistInsert(quicklistIter *iter, quicklistEntry *entry,
+                                   void *value, const size_t sz, int after)
+{
+    quicklist *quicklist = iter->quicklist;
     int full = 0, at_tail = 0, at_head = 0, avail_next = 0, avail_prev = 0;
     int fill = quicklist->fill;
     quicklistNode *node = entry->node;
@@ -1034,16 +1055,22 @@ REDIS_STATIC void _quicklistInsert(quicklist *quicklist, quicklistEntry *entry,
     }
 
     quicklist->count++;
+
+    /* In any case, we reset iterator to forbid use of iterator after insert.
+     * Notice: iter->current has been compressed in _quicklistInsert(). */
+    resetIterator(iter); 
 }
 
-void quicklistInsertBefore(quicklist *quicklist, quicklistEntry *entry,
-                           void *value, const size_t sz) {
-    _quicklistInsert(quicklist, entry, value, sz, 0);
+void quicklistInsertBefore(quicklistIter *iter, quicklistEntry *entry,
+                           void *value, const size_t sz)
+{
+    _quicklistInsert(iter, entry, value, sz, 0);
 }
 
-void quicklistInsertAfter(quicklist *quicklist, quicklistEntry *entry,
-                          void *value, const size_t sz) {
-    _quicklistInsert(quicklist, entry, value, sz, 1);
+void quicklistInsertAfter(quicklistIter *iter, quicklistEntry *entry,
+                          void *value, const size_t sz)
+{
+    _quicklistInsert(iter, entry, value, sz, 1);
 }
 
 /* Delete a range of elements from the quicklist.
@@ -1067,13 +1094,15 @@ int quicklistDelRange(quicklist *quicklist, const long start,
         extent = -start; /* c.f. LREM -29 29; just delete until end. */
     }
 
-    quicklistEntry entry;
-    if (!quicklistIndex(quicklist, start, &entry))
+    quicklistIter *iter = quicklistGetIteratorAtIdx(quicklist, AL_START_TAIL, start);
+    if (!iter)
         return 0;
 
     D("Quicklist delete request for start %ld, count %ld, extent: %ld", start,
       count, extent);
-    quicklistNode *node = entry.node;
+    quicklistNode *node = iter->current;
+    long offset = iter->offset;
+    quicklistReleaseIterator(iter);
 
     /* iterate over next nodes until everything is deleted. */
     while (extent) {
@@ -1081,22 +1110,22 @@ int quicklistDelRange(quicklist *quicklist, const long start,
 
         unsigned long del;
         int delete_entire_node = 0;
-        if (entry.offset == 0 && extent >= node->count) {
+        if (offset == 0 && extent >= node->count) {
             /* If we are deleting more than the count of this node, we
              * can just delete the entire node without listpack math. */
             delete_entire_node = 1;
             del = node->count;
-        } else if (entry.offset >= 0 && extent + entry.offset >= node->count) {
+        } else if (offset >= 0 && extent + offset >= node->count) {
             /* If deleting more nodes after this one, calculate delete based
              * on size of current node. */
-            del = node->count - entry.offset;
-        } else if (entry.offset < 0) {
+            del = node->count - offset;
+        } else if (offset < 0) {
             /* If offset is negative, we are in the first run of this loop
              * and we are deleting the entire range
              * from this start offset to end of list.  Since the Negative
              * offset is the number of elements until the tail of the list,
              * just use it directly as the deletion count. */
-            del = -entry.offset;
+            del = -offset;
 
             /* If the positive offset is greater than the remaining extent,
              * we only delete the remaining extent, not the entire offset.
@@ -1111,13 +1140,13 @@ int quicklistDelRange(quicklist *quicklist, const long start,
 
         D("[%ld]: asking to del: %ld because offset: %d; (ENTIRE NODE: %d), "
           "node count: %u",
-          extent, del, entry.offset, delete_entire_node, node->count);
+          extent, del, offset, delete_entire_node, node->count);
 
         if (delete_entire_node || QL_NODE_IS_PLAIN(node)) {
             __quicklistDelNode(quicklist, node);
         } else {
             quicklistDecompressNodeForUse(node);
-            node->entry = lpDeleteRange(node->entry, entry.offset, del);
+            node->entry = lpDeleteRange(node->entry, offset, del);
             quicklistNodeUpdateSz(node);
             node->count -= del;
             quicklist->count -= del;
@@ -1130,7 +1159,7 @@ int quicklistDelRange(quicklist *quicklist, const long start,
 
         node = next;
 
-        entry.offset = 0;
+        offset = 0;
     }
     return 1;
 }
@@ -1145,7 +1174,7 @@ int quicklistCompare(quicklistEntry* entry, unsigned char *p2, const size_t p2_l
 
 /* Returns a quicklist iterator 'iter'. After the initialization every
  * call to quicklistNext() will return the next element of the quicklist. */
-quicklistIter *quicklistGetIterator(const quicklist *quicklist, int direction) {
+quicklistIter *quicklistGetIterator(quicklist *quicklist, int direction) {
     quicklistIter *iter;
 
     iter = zmalloc(sizeof(*iter));
@@ -1168,25 +1197,66 @@ quicklistIter *quicklistGetIterator(const quicklist *quicklist, int direction) {
 
 /* Initialize an iterator at a specific offset 'idx' and make the iterator
  * return nodes in 'direction' direction. */
-quicklistIter *quicklistGetIteratorAtIdx(const quicklist *quicklist,
+quicklistIter *quicklistGetIteratorAtIdx(quicklist *quicklist,
                                          const int direction,
-                                         const long long idx) {
-    quicklistEntry entry;
+                                         const long long idx)
+{
+    quicklistNode *n;
+    unsigned long long accum = 0;
+    unsigned long long index;
+    int forward = idx < 0 ? 0 : 1; /* < 0 -> reverse, 0+ -> forward */
 
-    if (quicklistIndex(quicklist, idx, &entry)) {
-        quicklistIter *base = quicklistGetIterator(quicklist, direction);
-        base->zi = NULL;
-        base->current = entry.node;
-        base->offset = entry.offset;
-        return base;
-    } else {
+    index = forward ? idx : (-idx) - 1;
+    if (index >= quicklist->count)
+        return NULL;
+
+    /* Seek in the other direction if that way is shorter. */
+    int seek_forward = forward;
+    unsigned long long seek_index = index;
+    if (index > (quicklist->count - 1) / 2) {
+        seek_forward = !forward;
+        seek_index = quicklist->count - 1 - index;
+    }
+
+    n = seek_forward ? quicklist->head : quicklist->tail;
+    while (likely(n)) {
+        if ((accum + n->count) > seek_index) {
+            break;
+        } else {
+            D("Skipping over (%p) %u at accum %lld", (void *)n, n->count,
+              accum);
+            accum += n->count;
+            n = seek_forward ? n->next : n->prev;
+        }
+    }
+
+    if (!n)
         return NULL;
+
+    /* Fix accum so it looks like we seeked in the other direction. */
+    if (seek_forward != forward) accum = quicklist->count - n->count - accum;
+
+    D("Found node: %p at accum %llu, idx %llu, sub+ %llu, sub- %llu", (void *)n,
+      accum, index, index - accum, (-index) - 1 + accum);
+
+    quicklistIter *iter = quicklistGetIterator(quicklist, direction);
+    iter->current = n;
+    if (forward) {
+        /* forward = normal head-to-tail offset. */
+        iter->offset = index - accum;
+    } else {
+        /* reverse = need negative offset for tail-to-head, so undo
+         * the result of the original index = (-idx) - 1 above. */
+        iter->offset = (-index) - 1 + accum;
     }
+
+    return iter;
 }
 
 /* Release iterator.
  * If we still have a valid current node, then re-encode current node. */
 void quicklistReleaseIterator(quicklistIter *iter) {
+    if (!iter) return;
     if (iter->current)
         quicklistCompress(iter->quicklist, iter->current);
 
@@ -1339,76 +1409,15 @@ quicklist *quicklistDup(quicklist *orig) {
  * from the tail, -1 is the last element, -2 the penultimate
  * and so on. If the index is out of range 0 is returned.
  *
- * Returns 1 if element found
- * Returns 0 if element not found */
-int quicklistIndex(const quicklist *quicklist, const long long idx,
-                   quicklistEntry *entry) {
-    quicklistNode *n;
-    unsigned long long accum = 0;
-    unsigned long long index;
-    int forward = idx < 0 ? 0 : 1; /* < 0 -> reverse, 0+ -> forward */
-
-    initEntry(entry);
-    entry->quicklist = quicklist;
-
-    index = forward ? idx : (-idx) - 1;
-    if (index >= quicklist->count)
-        return 0;
-
-    /* Seek in the other direction if that way is shorter. */
-    int seek_forward = forward;
-    unsigned long long seek_index = index;
-    if (index > (quicklist->count - 1) / 2) {
-        seek_forward = !forward;
-        seek_index = quicklist->count - 1 - index;
-    }
-
-    n = seek_forward ? quicklist->head : quicklist->tail;
-    while (likely(n)) {
-        if ((accum + n->count) > seek_index) {
-            break;
-        } else {
-            D("Skipping over (%p) %u at accum %lld", (void *)n, n->count,
-              accum);
-            accum += n->count;
-            n = seek_forward ? n->next : n->prev;
-        }
-    }
-
-    if (!n)
-        return 0;
-
-    /* Fix accum so it looks like we seeked in the other direction. */
-    if (seek_forward != forward) accum = quicklist->count - n->count - accum;
-
-    D("Found node: %p at accum %llu, idx %llu, sub+ %llu, sub- %llu", (void *)n,
-      accum, index, index - accum, (-index) - 1 + accum);
-
-    entry->node = n;
-    if (forward) {
-        /* forward = normal head-to-tail offset. */
-        entry->offset = index - accum;
-    } else {
-        /* reverse = need negative offset for tail-to-head, so undo
-         * the result of the original index = (-idx) - 1 above. */
-        entry->offset = (-index) - 1 + accum;
-    }
-
-    quicklistDecompressNodeForUse(entry->node);
-
-    if (unlikely(QL_NODE_IS_PLAIN(entry->node))) {
-        entry->value = entry->node->entry;
-        entry->sz = entry->node->sz;
-        return 1;
-    }
-
-    entry->zi = lpSeek(entry->node->entry, entry->offset);
-    unsigned int sz = 0;
-    entry->value = lpGetValue(entry->zi, &sz, &entry->longval);
-    /* The caller will use our result, so we don't re-compress here.
-     * The caller can recompress or delete the node as needed. */
-    entry->sz = sz;
-    return 1;
+ * Returns an iterator at a specific offset 'idx' if element found
+ * Returns NULL if element not found */
+quicklistIter *quicklistGetIteratorEntryAtIdx(quicklist *quicklist, const long long idx,
+                                              quicklistEntry *entry)
+{
+    quicklistIter *iter = quicklistGetIteratorAtIdx(quicklist, AL_START_TAIL, idx);
+    if (!iter) return NULL;
+    assert(quicklistNext(iter, entry));
+    return iter;
 }
 
 static void quicklistRotatePlain(quicklist *quicklist) {
@@ -1597,8 +1606,12 @@ void quicklistRepr(unsigned char *ql, int full) {
 
     while(node != NULL) {
         printf("{quicklist node(%d)\n", i++);
-        printf("{container : %s, encoding: %s, size: %zu}\n", QL_NODE_IS_PLAIN(node) ? "PLAIN": "PACKED",
-               (node->encoding == QUICKLIST_NODE_ENCODING_RAW) ? "RAW": "LZF", node->sz);
+        printf("{container : %s, encoding: %s, size: %zu, recompress: %d, attempted_compress: %d}\n",
+               QL_NODE_IS_PLAIN(node) ? "PLAIN": "PACKED",
+               (node->encoding == QUICKLIST_NODE_ENCODING_RAW) ? "RAW": "LZF",
+               node->sz,
+               node->recompress,
+               node->attempted_compress);
 
         if (full) {
             quicklistDecompressNode(node);
@@ -1794,6 +1807,39 @@ static int itrprintr_rev(quicklist *ql, int print) {
         err += _ql_verify((a), (b), (c), (d), (e));                            \
     } while (0)
 
+static int _ql_verify_compress(quicklist *ql) {
+    int errors = 0;
+    if (quicklistAllowsCompression(ql)) {
+        quicklistNode *node = ql->head;
+        unsigned int low_raw = ql->compress;
+        unsigned int high_raw = ql->len - ql->compress;
+
+        for (unsigned int at = 0; at < ql->len; at++, node = node->next) {
+            if (node && (at < low_raw || at >= high_raw)) {
+                if (node->encoding != QUICKLIST_NODE_ENCODING_RAW) {
+                    yell("Incorrect compression: node %d is "
+                         "compressed at depth %d ((%u, %u); total "
+                         "nodes: %lu; size: %zu; recompress: %d)",
+                         at, ql->compress, low_raw, high_raw, ql->len, node->sz,
+                         node->recompress);
+                    errors++;
+                }
+            } else {
+                if (node->encoding != QUICKLIST_NODE_ENCODING_LZF &&
+                    !node->attempted_compress) {
+                    yell("Incorrect non-compression: node %d is NOT "
+                         "compressed at depth %d ((%u, %u); total "
+                         "nodes: %lu; size: %zu; recompress: %d; attempted: %d)",
+                         at, ql->compress, low_raw, high_raw, ql->len, node->sz,
+                         node->recompress, node->attempted_compress);
+                    errors++;
+                }
+            }
+        }
+    }
+    return errors;
+}
+
 /* Verify list metadata matches physical list contents. */
 static int _ql_verify(quicklist *ql, uint32_t len, uint32_t count,
                       uint32_t head_count, uint32_t tail_count) {
@@ -1846,38 +1892,18 @@ static int _ql_verify(quicklist *ql, uint32_t len, uint32_t count,
         errors++;
     }
 
-    if (quicklistAllowsCompression(ql)) {
-        quicklistNode *node = ql->head;
-        unsigned int low_raw = ql->compress;
-        unsigned int high_raw = ql->len - ql->compress;
-
-        for (unsigned int at = 0; at < ql->len; at++, node = node->next) {
-            if (node && (at < low_raw || at >= high_raw)) {
-                if (node->encoding != QUICKLIST_NODE_ENCODING_RAW) {
-                    yell("Incorrect compression: node %d is "
-                         "compressed at depth %d ((%u, %u); total "
-                         "nodes: %lu; size: %zu; recompress: %d)",
-                         at, ql->compress, low_raw, high_raw, ql->len, node->sz,
-                         node->recompress);
-                    errors++;
-                }
-            } else {
-                if (node->encoding != QUICKLIST_NODE_ENCODING_LZF &&
-                    !node->attempted_compress) {
-                    yell("Incorrect non-compression: node %d is NOT "
-                         "compressed at depth %d ((%u, %u); total "
-                         "nodes: %lu; size: %zu; recompress: %d; attempted: %d)",
-                         at, ql->compress, low_raw, high_raw, ql->len, node->sz,
-                         node->recompress, node->attempted_compress);
-                    errors++;
-                }
-            }
-        }
-    }
-
+    errors += _ql_verify_compress(ql);
     return errors;
 }
 
+/* Release iterator and verify compress correctly. */
+static void ql_release_iterator(quicklistIter *iter) {
+    quicklist *ql = NULL;
+    if (iter) ql = iter->quicklist;
+    quicklistReleaseIterator(iter);
+    if (ql) assert(!_ql_verify_compress(ql));
+}
+
 /* Generate new string concatenating integer i against string 'prefix' */
 static char *genstr(char *prefix, int i) {
     static char result[64] = {0};
@@ -1931,6 +1957,7 @@ int quicklistTest(int argc, char *argv[], int flags) {
     for (int _i = 0; _i < (int)option_count; _i++) {
         printf("Testing Compression option %d\n", options[_i]);
         long long start = mstime();
+        quicklistIter *iter;
 
         TEST("create list") {
             quicklist *ql = quicklistNew(-2, options[_i]);
@@ -2034,7 +2061,7 @@ int quicklistTest(int argc, char *argv[], int flags) {
                         entry.value, buf, i);
                 i++;
             }
-            quicklistReleaseIterator(iter);
+            ql_release_iterator(iter);
             quicklistRelease(ql);
         }
 
@@ -2055,7 +2082,7 @@ int quicklistTest(int argc, char *argv[], int flags) {
                 assert(strncmp(strings[j], (char *)entry.value, strlen(strings[j])) == 0);
                 j++;
             }
-            quicklistReleaseIterator(iter);
+            ql_release_iterator(iter);
             quicklistRelease(ql);
         }
 
@@ -2233,7 +2260,7 @@ int quicklistTest(int argc, char *argv[], int flags) {
             if (count != 500)
                 ERR("Didn't iterate over exactly 500 elements (%d)", i);
             ql_verify(ql, 16, 500, 20, 32);
-            quicklistReleaseIterator(iter);
+            ql_release_iterator(iter);
             quicklistRelease(ql);
         }
 
@@ -2255,41 +2282,7 @@ int quicklistTest(int argc, char *argv[], int flags) {
             if (i != 500)
                 ERR("Didn't iterate over exactly 500 elements (%d)", i);
             ql_verify(ql, 16, 500, 20, 32);
-            quicklistReleaseIterator(iter);
-            quicklistRelease(ql);
-        }
-
-        TEST("insert before with 0 elements") {
-            quicklist *ql = quicklistNew(-2, options[_i]);
-            quicklistEntry entry;
-            quicklistIndex(ql, 0, &entry);
-            quicklistInsertBefore(ql, &entry, "abc", 4);
-            ql_verify(ql, 1, 1, 1, 1);
-
-            /* verify results */
-            quicklistIndex(ql, 0, &entry);
-            if (strncmp((char *)entry.value, "abc", 3)) {
-                int sz = entry.sz;
-                ERR("Value 0 didn't match, instead got: %.*s", sz,
-                    entry.value);
-            }
-            quicklistRelease(ql);
-        }
-
-        TEST("insert after with 0 elements") {
-            quicklist *ql = quicklistNew(-2, options[_i]);
-            quicklistEntry entry;
-            quicklistIndex(ql, 0, &entry);
-            quicklistInsertAfter(ql, &entry, "abc", 4);
-            ql_verify(ql, 1, 1, 1, 1);
-
-            /* verify results */
-            quicklistIndex(ql, 0, &entry);
-            int sz = entry.sz;
-            if (strncmp((char *)entry.value, "abc", 3)) {
-                ERR("Value 0 didn't match, instead got: %.*s", sz,
-                    entry.value);
-            }
+            ql_release_iterator(iter);
             quicklistRelease(ql);
         }
 
@@ -2297,24 +2290,27 @@ int quicklistTest(int argc, char *argv[], int flags) {
             quicklist *ql = quicklistNew(-2, options[_i]);
             quicklistPushHead(ql, "hello", 6);
             quicklistEntry entry;
-            quicklistIndex(ql, 0, &entry);
-            quicklistInsertAfter(ql, &entry, "abc", 4);
+            iter = quicklistGetIteratorEntryAtIdx(ql, 0, &entry);
+            quicklistInsertAfter(iter, &entry, "abc", 4);
+            ql_release_iterator(iter);
             ql_verify(ql, 1, 2, 2, 2);
 
             /* verify results */
-            quicklistIndex(ql, 0, &entry);
+            iter = quicklistGetIteratorEntryAtIdx(ql, 0, &entry);
             int sz = entry.sz;
             if (strncmp((char *)entry.value, "hello", 5)) {
                 ERR("Value 0 didn't match, instead got: %.*s", sz,
                     entry.value);
             }
-            quicklistIndex(ql, 1, &entry);
+            ql_release_iterator(iter);
+
+            iter = quicklistGetIteratorEntryAtIdx(ql, 1, &entry);
             sz = entry.sz;
             if (strncmp((char *)entry.value, "abc", 3)) {
                 ERR("Value 1 didn't match, instead got: %.*s", sz,
                     entry.value);
             }
-
+            ql_release_iterator(iter);
             quicklistRelease(ql);
         }
 
@@ -2322,24 +2318,27 @@ int quicklistTest(int argc, char *argv[], int flags) {
             quicklist *ql = quicklistNew(-2, options[_i]);
             quicklistPushHead(ql, "hello", 6);
             quicklistEntry entry;
-            quicklistIndex(ql, 0, &entry);
-            quicklistInsertBefore(ql, &entry, "abc", 4);
+            iter = quicklistGetIteratorEntryAtIdx(ql, 0, &entry);
+            quicklistInsertBefore(iter, &entry, "abc", 4);
+            ql_release_iterator(iter);
             ql_verify(ql, 1, 2, 2, 2);
 
             /* verify results */
-            quicklistIndex(ql, 0, &entry);
+            iter = quicklistGetIteratorEntryAtIdx(ql, 0, &entry);
             int sz = entry.sz;
             if (strncmp((char *)entry.value, "abc", 3)) {
                 ERR("Value 0 didn't match, instead got: %.*s", sz,
                     entry.value);
             }
-            quicklistIndex(ql, 1, &entry);
+            ql_release_iterator(iter);
+
+            iter = quicklistGetIteratorEntryAtIdx(ql, 1, &entry);
             sz = entry.sz;
             if (strncmp((char *)entry.value, "hello", 5)) {
                 ERR("Value 1 didn't match, instead got: %.*s", sz,
                     entry.value);
             }
-
+            ql_release_iterator(iter);
             quicklistRelease(ql);
         }
 
@@ -2349,9 +2348,10 @@ int quicklistTest(int argc, char *argv[], int flags) {
                 quicklistPushTail(ql, genstr("hello", i), 6);
             quicklistSetFill(ql, -1);
             quicklistEntry entry;
-            quicklistIndex(ql, -10, &entry);
+            iter = quicklistGetIteratorEntryAtIdx(ql, -10, &entry);
             char buf[4096] = {0};
-            quicklistInsertBefore(ql, &entry, buf, 4096);
+            quicklistInsertBefore(iter, &entry, buf, 4096);
+            ql_release_iterator(iter);
             ql_verify(ql, 4, 11, 1, 2);
             quicklistRelease(ql);
         }
@@ -2362,9 +2362,10 @@ int quicklistTest(int argc, char *argv[], int flags) {
                 quicklistPushHead(ql, genstr("hello", i), 6);
             quicklistSetFill(ql, -1);
             quicklistEntry entry;
-            quicklistIndex(ql, -1, &entry);
+            iter = quicklistGetIteratorEntryAtIdx(ql, -1, &entry);
             char buf[4096] = {0};
-            quicklistInsertAfter(ql, &entry, buf, 4096);
+            quicklistInsertAfter(iter, &entry, buf, 4096);
+            ql_release_iterator(iter);
             ql_verify(ql, 4, 11, 2, 1);
             quicklistRelease(ql);
         }
@@ -2388,40 +2389,51 @@ int quicklistTest(int argc, char *argv[], int flags) {
                 while (quicklistNext(iter, &entry)) {
                     if (!strncmp((char *)entry.value, "bob", 3)) {
                         /* Insert as fill = 1 so it spills into new node. */
-                        quicklistInsertBefore(ql, &entry, "bar", 3);
+                        quicklistInsertBefore(iter, &entry, "bar", 3);
                         break; /* didn't we fix insert-while-iterating? */
                     }
                 }
+                ql_release_iterator(iter);
                 itrprintr(ql, 0);
 
                 /* verify results */
-                quicklistIndex(ql, 0, &entry);
+                iter = quicklistGetIteratorEntryAtIdx(ql, 0, &entry);
                 int sz = entry.sz;
 
                 if (strncmp((char *)entry.value, "abc", 3))
                     ERR("Value 0 didn't match, instead got: %.*s", sz,
                         entry.value);
-                quicklistIndex(ql, 1, &entry);
+                ql_release_iterator(iter);
+
+                iter = quicklistGetIteratorEntryAtIdx(ql, 1, &entry);
                 if (strncmp((char *)entry.value, "def", 3))
                     ERR("Value 1 didn't match, instead got: %.*s", sz,
                         entry.value);
-                quicklistIndex(ql, 2, &entry);
+                ql_release_iterator(iter);
+
+                iter = quicklistGetIteratorEntryAtIdx(ql, 2, &entry);
                 if (strncmp((char *)entry.value, "bar", 3))
                     ERR("Value 2 didn't match, instead got: %.*s", sz,
                         entry.value);
-                quicklistIndex(ql, 3, &entry);
+                ql_release_iterator(iter);
+
+                iter = quicklistGetIteratorEntryAtIdx(ql, 3, &entry);
                 if (strncmp((char *)entry.value, "bob", 3))
                     ERR("Value 3 didn't match, instead got: %.*s", sz,
                         entry.value);
-                quicklistIndex(ql, 4, &entry);
+                ql_release_iterator(iter);
+
+                iter = quicklistGetIteratorEntryAtIdx(ql, 4, &entry);
                 if (strncmp((char *)entry.value, "foo", 3))
                     ERR("Value 4 didn't match, instead got: %.*s", sz,
                         entry.value);
-                quicklistIndex(ql, 5, &entry);
+                ql_release_iterator(iter);
+
+                iter = quicklistGetIteratorEntryAtIdx(ql, 5, &entry);
                 if (strncmp((char *)entry.value, "zoo", 3))
                     ERR("Value 5 didn't match, instead got: %.*s", sz,
                         entry.value);
-                quicklistReleaseIterator(iter);
+                ql_release_iterator(iter);
                 quicklistRelease(ql);
             }
         }
@@ -2434,8 +2446,9 @@ int quicklistTest(int argc, char *argv[], int flags) {
                     quicklistPushTail(ql, genstr("hello", i), 32);
                 for (int i = 0; i < 250; i++) {
                     quicklistEntry entry;
-                    quicklistIndex(ql, 250, &entry);
-                    quicklistInsertBefore(ql, &entry, genstr("abc", i), 32);
+                    iter = quicklistGetIteratorEntryAtIdx(ql, 250, &entry);
+                    quicklistInsertBefore(iter, &entry, genstr("abc", i), 32);
+                    ql_release_iterator(iter);
                 }
                 if (fills[f] == 32)
                     ql_verify(ql, 25, 750, 32, 20);
@@ -2451,8 +2464,9 @@ int quicklistTest(int argc, char *argv[], int flags) {
                     quicklistPushHead(ql, genstr("hello", i), 32);
                 for (int i = 0; i < 250; i++) {
                     quicklistEntry entry;
-                    quicklistIndex(ql, 250, &entry);
-                    quicklistInsertAfter(ql, &entry, genstr("abc", i), 32);
+                    iter = quicklistGetIteratorEntryAtIdx(ql, 250, &entry);
+                    quicklistInsertAfter(iter, &entry, genstr("abc", i), 32);
+                    ql_release_iterator(iter);
                 }
 
                 if (ql->count != 750)
@@ -2503,12 +2517,15 @@ int quicklistTest(int argc, char *argv[], int flags) {
                 for (int i = 0; i < 500; i++)
                     quicklistPushTail(ql, genstr("hello", i + 1), 32);
                 quicklistEntry entry;
-                quicklistIndex(ql, 1, &entry);
+                iter = quicklistGetIteratorEntryAtIdx(ql, 1, &entry);
                 if (strcmp((char *)entry.value, "hello2") != 0)
                     ERR("Value: %s", entry.value);
-                quicklistIndex(ql, 200, &entry);
+                ql_release_iterator(iter);
+
+                iter = quicklistGetIteratorEntryAtIdx(ql, 200, &entry);
                 if (strcmp((char *)entry.value, "hello201") != 0)
                     ERR("Value: %s", entry.value);
+                ql_release_iterator(iter);
                 quicklistRelease(ql);
             }
 
@@ -2518,12 +2535,15 @@ int quicklistTest(int argc, char *argv[], int flags) {
                 for (int i = 0; i < 500; i++)
                     quicklistPushTail(ql, genstr("hello", i + 1), 32);
                 quicklistEntry entry;
-                quicklistIndex(ql, -1, &entry);
+                iter = quicklistGetIteratorEntryAtIdx(ql, -1, &entry);
                 if (strcmp((char *)entry.value, "hello500") != 0)
                     ERR("Value: %s", entry.value);
-                quicklistIndex(ql, -2, &entry);
+                ql_release_iterator(iter);
+
+                iter = quicklistGetIteratorEntryAtIdx(ql, -2, &entry);
                 if (strcmp((char *)entry.value, "hello499") != 0)
                     ERR("Value: %s", entry.value);
+                ql_release_iterator(iter);
                 quicklistRelease(ql);
             }
 
@@ -2533,9 +2553,10 @@ int quicklistTest(int argc, char *argv[], int flags) {
                 for (int i = 0; i < 500; i++)
                     quicklistPushTail(ql, genstr("hello", i + 1), 32);
                 quicklistEntry entry;
-                quicklistIndex(ql, -100, &entry);
+                iter = quicklistGetIteratorEntryAtIdx(ql, -100, &entry);
                 if (strcmp((char *)entry.value, "hello401") != 0)
                     ERR("Value: %s", entry.value);
+                ql_release_iterator(iter);
                 quicklistRelease(ql);
             }
 
@@ -2546,9 +2567,11 @@ int quicklistTest(int argc, char *argv[], int flags) {
                     quicklistPushTail(ql, genstr("hello", i + 1), 32);
                 quicklistEntry entry;
                 int sz = entry.sz;
-                if (quicklistIndex(ql, 50, &entry))
+                iter = quicklistGetIteratorEntryAtIdx(ql, 50, &entry);
+                if (iter)
                     ERR("Index found at 50 with 50 list: %.*s", sz,
                         entry.value);
+                ql_release_iterator(iter);
                 quicklistRelease(ql);
             }
         }
@@ -2653,34 +2676,55 @@ int quicklistTest(int argc, char *argv[], int flags) {
             quicklistPushTail(ql, "4444", 4);
             ql_verify(ql, 1, 4, 4, 4);
             quicklistEntry entry;
-            quicklistIndex(ql, 0, &entry);
+            iter = quicklistGetIteratorEntryAtIdx(ql, 0, &entry);
             if (entry.longval != 1111)
                 ERR("Not 1111, %lld", entry.longval);
-            quicklistIndex(ql, 1, &entry);
+            ql_release_iterator(iter);
+
+            iter = quicklistGetIteratorEntryAtIdx(ql, 1, &entry);
             if (entry.longval != 2222)
                 ERR("Not 2222, %lld", entry.longval);
-            quicklistIndex(ql, 2, &entry);
+            ql_release_iterator(iter);
+
+            iter = quicklistGetIteratorEntryAtIdx(ql, 2, &entry);
             if (entry.longval != 3333)
                 ERR("Not 3333, %lld", entry.longval);
-            quicklistIndex(ql, 3, &entry);
+            ql_release_iterator(iter);
+
+            iter = quicklistGetIteratorEntryAtIdx(ql, 3, &entry);
             if (entry.longval != 4444)
                 ERR("Not 4444, %lld", entry.longval);
-            if (quicklistIndex(ql, 4, &entry))
+            ql_release_iterator(iter);
+
+            iter = quicklistGetIteratorEntryAtIdx(ql, 4, &entry);
+            if (iter)
                 ERR("Index past elements: %lld", entry.longval);
-            quicklistIndex(ql, -1, &entry);
+            ql_release_iterator(iter);
+            
+            iter = quicklistGetIteratorEntryAtIdx(ql, -1, &entry);
             if (entry.longval != 4444)
                 ERR("Not 4444 (reverse), %lld", entry.longval);
-            quicklistIndex(ql, -2, &entry);
+            ql_release_iterator(iter);
+
+            iter = quicklistGetIteratorEntryAtIdx(ql, -2, &entry);
             if (entry.longval != 3333)
                 ERR("Not 3333 (reverse), %lld", entry.longval);
-            quicklistIndex(ql, -3, &entry);
+            ql_release_iterator(iter);
+
+            iter = quicklistGetIteratorEntryAtIdx(ql, -3, &entry);
             if (entry.longval != 2222)
                 ERR("Not 2222 (reverse), %lld", entry.longval);
-            quicklistIndex(ql, -4, &entry);
+            ql_release_iterator(iter);
+            
+            iter = quicklistGetIteratorEntryAtIdx(ql, -4, &entry);
             if (entry.longval != 1111)
                 ERR("Not 1111 (reverse), %lld", entry.longval);
-            if (quicklistIndex(ql, -5, &entry))
+            ql_release_iterator(iter);
+            
+            iter = quicklistGetIteratorEntryAtIdx(ql, -5, &entry);
+            if (iter)
                 ERR("Index past elements (reverse), %lld", entry.longval);
+            ql_release_iterator(iter);
             quicklistRelease(ql);
         }
 
@@ -2697,16 +2741,18 @@ int quicklistTest(int argc, char *argv[], int flags) {
             quicklistPushTail(ql, "xxxxxxxxxxxxxxxxxxxx", 20);
             quicklistEntry entry;
             for (int i = 0; i < 5000; i++) {
-                quicklistIndex(ql, i, &entry);
+                iter = quicklistGetIteratorEntryAtIdx(ql, i, &entry);
                 if (entry.longval != nums[i])
                     ERR("[%d] Not longval %lld but rather %lld", i, nums[i],
                         entry.longval);
                 entry.longval = 0xdeadbeef;
+                ql_release_iterator(iter);
             }
-            quicklistIndex(ql, 5000, &entry);
+            iter = quicklistGetIteratorEntryAtIdx(ql, 5000, &entry);
             if (strncmp((char *)entry.value, "xxxxxxxxxxxxxxxxxxxx", 20))
                 ERR("String val not match: %s", entry.value);
             ql_verify(ql, 157, 5001, 32, 9);
+            ql_release_iterator(iter);
             quicklistRelease(ql);
         }
 
@@ -2744,7 +2790,7 @@ int quicklistTest(int argc, char *argv[], int flags) {
                     }
                     i++;
                 }
-                quicklistReleaseIterator(iter);
+                ql_release_iterator(iter);
 
                 /* check result of lrem 0 bar */
                 iter = quicklistGetIterator(ql, AL_START_HEAD);
@@ -2759,7 +2805,7 @@ int quicklistTest(int argc, char *argv[], int flags) {
                     }
                     i++;
                 }
-                quicklistReleaseIterator(iter);
+                ql_release_iterator(iter);
 
                 quicklistPushTail(ql, "foo", 3);
 
@@ -2776,7 +2822,7 @@ int quicklistTest(int argc, char *argv[], int flags) {
                         break;
                     i++;
                 }
-                quicklistReleaseIterator(iter);
+                ql_release_iterator(iter);
 
                 /* check result of lrem -2 foo */
                 /* (we're ignoring the '2' part and still deleting all foo
@@ -2797,7 +2843,7 @@ int quicklistTest(int argc, char *argv[], int flags) {
                     i++;
                 }
 
-                quicklistReleaseIterator(iter);
+                ql_release_iterator(iter);
                 quicklistRelease(ql);
             }
         }
@@ -2820,7 +2866,7 @@ int quicklistTest(int argc, char *argv[], int flags) {
                     }
                     i++;
                 }
-                quicklistReleaseIterator(iter);
+                ql_release_iterator(iter);
 
                 if (i != 5)
                     ERR("Didn't iterate 5 times, iterated %d times.", i);
@@ -2836,7 +2882,7 @@ int quicklistTest(int argc, char *argv[], int flags) {
                     }
                     i++;
                 }
-                quicklistReleaseIterator(iter);
+                ql_release_iterator(iter);
                 quicklistRelease(ql);
             }
         }
@@ -2862,7 +2908,7 @@ int quicklistTest(int argc, char *argv[], int flags) {
                             nums[i]);
                     i++;
                 }
-                quicklistReleaseIterator(iter);
+                ql_release_iterator(iter);
                 quicklistRelease(ql);
             }
         }
@@ -2884,11 +2930,12 @@ int quicklistTest(int argc, char *argv[], int flags) {
                 quicklistDelRange(ql, 0, 0);
                 quicklistEntry entry;
                 for (int i = 0; i < 7; i++) {
-                    quicklistIndex(ql, i, &entry);
+                    iter = quicklistGetIteratorEntryAtIdx(ql, i, &entry);
                     if (entry.longval != nums[25 + i])
                         ERR("Deleted invalid range!  Expected %lld but got "
                             "%lld",
                             entry.longval, nums[25 + i]);
+                    ql_release_iterator(iter);
                 }
                 if (fills[f] == 32)
                     ql_verify(ql, 1, 7, 7, 7);
@@ -2916,24 +2963,32 @@ int quicklistTest(int argc, char *argv[], int flags) {
                 if (fills[f] == 32)
                     ql_verify(ql, 1, 12, 12, 12);
                 quicklistEntry entry;
-                quicklistIndex(ql, 0, &entry);
+
+                iter = quicklistGetIteratorEntryAtIdx(ql, 0, &entry);
                 if (entry.longval != 5)
                     ERR("A: longval not 5, but %lld", entry.longval);
-                quicklistIndex(ql, -1, &entry);
+                ql_release_iterator(iter);
+
+                iter = quicklistGetIteratorEntryAtIdx(ql, -1, &entry);
                 if (entry.longval != 16)
                     ERR("B! got instead: %lld", entry.longval);
                 quicklistPushTail(ql, "bobobob", 7);
-                quicklistIndex(ql, -1, &entry);
+                ql_release_iterator(iter);
+
+                iter = quicklistGetIteratorEntryAtIdx(ql, -1, &entry);
                 int sz = entry.sz;
                 if (strncmp((char *)entry.value, "bobobob", 7))
                     ERR("Tail doesn't match bobobob, it's %.*s instead",
                         sz, entry.value);
+                ql_release_iterator(iter);
+
                 for (int i = 0; i < 12; i++) {
-                    quicklistIndex(ql, i, &entry);
+                    iter = quicklistGetIteratorEntryAtIdx(ql, i, &entry);
                     if (entry.longval != nums[5 + i])
                         ERR("Deleted invalid range!  Expected %lld but got "
                             "%lld",
                             entry.longval, nums[5 + i]);
+                    ql_release_iterator(iter);
                 }
                 quicklistRelease(ql);
             }
@@ -2958,9 +3013,10 @@ int quicklistTest(int argc, char *argv[], int flags) {
                 if (fills[f] == 32)
                     ql_verify(ql, 1, 1, 1, 1);
                 quicklistEntry entry;
-                quicklistIndex(ql, 0, &entry);
+                iter = quicklistGetIteratorEntryAtIdx(ql, 0, &entry);
                 if (entry.longval != -5157318210846258173)
                     ERROR;
+                ql_release_iterator(iter);
                 quicklistRelease(ql);
             }
         }