Hi guys,

I got a question about linsertCommand. This inserting process starts with initializing an iterator but only uses entry as the pivot to insert a new value. And after listTypeInsert successfully, either entry or iter loses the information about the current entry.

void linsertCommand(client *c) {
    ...
    /* Seek pivot from head to tail */
    iter = listTypeInitIterator(subject,0,LIST_TAIL);
    while (listTypeNext(iter,&entry)) {
        if (listTypeEqual(&entry,c->argv[3])) {
            listTypeInsert(&entry,c->argv[4],where);
            inserted = 1;
            break;
        }
    }
    listTypeReleaseIterator(iter);
    ...

For now this works well as we only insert one entry and no need to worry about the position of the new entry. But if we want to insert more entry at one time in future, I think it might be better to pass iterator into listTypeInsert, so we could know the position of the updated entry just like quicklistDelEntry does.

void quicklistDelEntry(quicklistIter *iter, quicklistEntry *entry) ;

By the way, when we release a quicklistIter in listTypeReleaseIterator, why just use zfree rather than quicklistReleaseIterator? 

/* Clean up the iterator. */
void listTypeReleaseIterator(listTypeIterator *li) {
    zfree(li->iter);
    zfree(li);
}

Comment From: sundb

1) I think there is no need to increase the code complexity for unknown requirements is better. 2) This should be a bug, should use quicklistReleaseIterator, may cause the last iterated element will not be recompressed, Can you make a pr?

Comment From: enjoy-binbin

1: I agree with sundb

2: I took a look. Seems to be a bug. So i made https://github.com/redis/redis/pull/8994 to fix it . Hope you don't mind :) ↑ forget about that one

Comment From: DarrenJiang13

I do not think it is that easy to just use quicklistReleaseIterator in listTypeReleaseIterator. Cause I was trying to use it but encountered a problem like 

==19869==ERROR: AddressSanitizer: heap-use-after-free on address 0x6030000a3dcc at pc 0x000103970859 bp 0x70000a3f6610 sp 0x70000a3f6608

The function calling is like "linsertCommand->listTypeInsert->quicklistInsertBefore->_quicklistInsert->_quicklistMergeNodes->_quicklistZiplistMerge->__quicklistDelNode". Which means, in some situations, the node was deleted, but the iter->current was not updated. So when we try to call quicklistReleaseIterator, error comes.

void quicklistReleaseIterator(quicklistIter *iter) {
    if (iter->current)
        quicklistCompress(iter->quicklist, iter->current);

    zfree(iter);
}

So I guess the designer used zfree for this kind of reason: when you insert with a node change, the quicklistIterator.current points to another node or anywhere. Then it becomes meaningless or even dangerous to use quicklistReleaseIterator.

This could also support my opinion passing iterators during insertion. Adding iterators might be complex, but this could make the quicklist more like stl implementations, which also enables merging and spliting list in future.

Comment From: enjoy-binbin

ohh... I will go deeper when i have time. And the meaning time maybe you can ping core team

Comment From: sundb

Thanks, @DarrenJiang13 Now it seems like it might be worthwhile to modify quicklistInsert* like quicklistDelEntry. Still need to see if others have other comments. ping @oranagra

Comment From: oranagra

It seems to me that the conclusion from the discussion above is correct. i.e. we can't use quicklistReleaseIterator unless we fix the other problem (which leaves the iterator in an unusable state).

Since there's no bug currently, there's no rush to fix this, but i agree that it would be nice to improve listTypeInsert to take (and update) an iterator. or maybe have a version of it that does that (we may also want to keep the option of using it without an iterator). The challenge may be to produce elegant and safe code that's easy to review and see that it's bug free.

Comment From: DarrenJiang13

Thank you guys, seems interesting to me to make a new quicklist version with iterators.

Comment From: DarrenJiang13

Seems to be fixed in #9849 . Closed.