Skip to content

Fix crash due to delete entry from compress quicklistNode and wrongly split quicklistNode#11242

Merged
oranagra merged 7 commits intoredis:unstablefrom
sundb:fix-quicklist-uncompress
Sep 19, 2022
Merged

Fix crash due to delete entry from compress quicklistNode and wrongly split quicklistNode#11242
oranagra merged 7 commits intoredis:unstablefrom
sundb:fix-quicklist-uncompress

Conversation

@sundb
Copy link
Collaborator

@sundb sundb commented Sep 6, 2022

This PR mainly deals with 2 crashes introduced in #9357, and fix the QUICKLIST-PACKED-THRESHOLD mess in extern
test mode.

  1. Fix crash due to deleting an entry from a compress quicklistNode
    When inserting a large element, we need to create a new quicklistNode first, and then delete its previous element, if the node where the deleted element is located is compressed, it will cause a crash.
    Now add dont_compress to quicklistNode, if we want to use a quicklistNode after some operation, we can use this flag like following:

    node->dont_compress = 1; /* Prevent to be compressed */
    some_operation(node); /* This operation might try to compress this node */
    some_other_operation(node); /* We can use this node without decompress it */
    node->dont_compress = 0; /* Re-able compression */
    quicklistCompressNode(node);

    Perhaps in the future, we could just disable the current entry from being compressed during the iterator loop, but that would require more work.

  2. Fix crash due to wrongly split quicklist
    before Add support for list type to store elements larger than 4GB #9357, the offset param of _quicklistSplitNode() will not negative.
    For now, when offset is negative, the split extent will be wrong.
    following example:

    int orig_start = after ? offset + 1 : 0;
    int orig_extent = after ? -1 : offset;
    int new_start = after ? 0 : offset;
    int new_extent = after ? offset + 1 : -1;
    # offset: -2, after: 1, node->count: 2
    # current wrong range: [-1,-1] [0,-1]
    # correct range: [1,-1] [0, 1]

    Because only _quicklistInsert() splits the quicklistNode and only quicklistInsertAfter(), quicklistInsertBefore() call _quicklistInsert(),
    so quicklistReplaceEntry() and listTypeInsert() might occur this crash.
    But the iterator of listTypeInsert() is alway from head to tail(iter->offset is always positive), so it is not affected.
    The final conclusion is this crash only occur when we insert a large element with negative index into a list, that affects LSET command and RM_ListSet module api.

  3. In extern test mode, we need to restore quicklist packed threshold after when the end of test.

  4. Show node->count in quicklistRepr().

  5. Add new tcl proc config_get_set to support restoring config in tests.

@sundb sundb changed the title Fix crash due to delete entry from compress quicklist node Fix crash due to delete entry from compress quicklistNode and wrongly split quicklistNode Sep 6, 2022
@sundb sundb force-pushed the fix-quicklist-uncompress branch from 43c34cc to bdf7696 Compare September 6, 2022 11:50
Comment on lines +912 to +913
/* Need positive offset for calculating extent below. */
if (offset < 0) offset = node->count + offset;
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

can we specify in the top comment in which conditions this bug will trigger?
i.e. so that users can know if they're affected and must upgrade.
will it always result in a crash or also sometimes in messing up the data?

Copy link
Collaborator Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Updated the top comment, please see again.

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

i meant something that's more useful to end users.
like when a certain argument for a certain command is negative.
some way that users can use to figure out if they're using it this way and if they're at risk.

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

ohh, i see you did mention it as the end.
so only LSET with negative index and a big (> 1gb) object?

Copy link
Collaborator Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Yes, LSET with a bit object is the only way that will trigger this crash.

@sundb sundb force-pushed the fix-quicklist-uncompress branch 2 times, most recently from fbb9947 to bf72d4b Compare September 8, 2022 03:52
@sundb sundb force-pushed the fix-quicklist-uncompress branch from bf72d4b to faca95a Compare September 9, 2022 08:05
@yossigo yossigo requested a review from oranagra September 11, 2022 19:45
@oranagra oranagra merged commit 13d25dd into redis:unstable Sep 19, 2022
@oranagra oranagra added the release-notes indication that this issue needs to be mentioned in the release notes label Sep 19, 2022
@sundb sundb deleted the fix-quicklist-uncompress branch September 19, 2022 06:48
@oranagra oranagra mentioned this pull request Sep 21, 2022
oranagra pushed a commit that referenced this pull request Sep 21, 2022
… split quicklistNode (#11242)

This PR mainly deals with 2 crashes introduced in #9357,
and fix the QUICKLIST-PACKED-THRESHOLD mess in external test mode.

1. Fix crash due to deleting an entry from a compress quicklistNode
   When inserting a large element, we need to create a new quicklistNode first,
   and then delete its previous element, if the node where the deleted element is
   located is compressed, it will cause a crash.
   Now add `dont_compress` to quicklistNode, if we want to use a quicklistNode
   after some operation, we can use this flag like following:

    ```c
    node->dont_compress = 1; /* Prevent to be compressed */
    some_operation(node); /* This operation might try to compress this node */
    some_other_operation(node); /* We can use this node without decompress it */
    node->dont_compress = 0; /* Re-able compression */
    quicklistCompressNode(node);
    ```

   Perhaps in the future, we could just disable the current entry from being
   compressed during the iterator loop, but that would require more work.

2. Fix crash due to wrongly split quicklist
   before #9357, the offset param of _quicklistSplitNode() will not negative.
   For now, when offset is negative, the split extent will be wrong.
   following example:
    ```c
    int orig_start = after ? offset + 1 : 0;
    int orig_extent = after ? -1 : offset;
    int new_start = after ? 0 : offset;
    int new_extent = after ? offset + 1 : -1;
    # offset: -2, after: 1, node->count: 2
    # current wrong range: [-1,-1] [0,-1]
    # correct range: [1,-1] [0, 1]
    ```

   Because only `_quicklistInsert()` splits the quicklistNode and only
   `quicklistInsertAfter()`, `quicklistInsertBefore()` call _quicklistInsert(), 
   so `quicklistReplaceEntry()` and `listTypeInsert()` might occur this crash.
   But the iterator of `listTypeInsert()` is alway from head to tail(iter->offset is
   always positive), so it is not affected.
   The final conclusion is this crash only occur when we insert a large element
   with negative index into a list, that affects `LSET` command and `RM_ListSet`
   module api.
     
3. In external test mode, we need to restore quicklist packed threshold after
   when the end of test.
4. Show `node->count` in quicklistRepr().
5. Add new tcl proc `config_get_set` to support restoring config in tests.

(cherry picked from commit 13d25dd)
madolson pushed a commit to madolson/redis that referenced this pull request Apr 19, 2023
… split quicklistNode (redis#11242)

This PR mainly deals with 2 crashes introduced in redis#9357,
and fix the QUICKLIST-PACKED-THRESHOLD mess in external test mode.

1. Fix crash due to deleting an entry from a compress quicklistNode
   When inserting a large element, we need to create a new quicklistNode first,
   and then delete its previous element, if the node where the deleted element is
   located is compressed, it will cause a crash.
   Now add `dont_compress` to quicklistNode, if we want to use a quicklistNode
   after some operation, we can use this flag like following:

    ```c
    node->dont_compress = 1; /* Prevent to be compressed */
    some_operation(node); /* This operation might try to compress this node */
    some_other_operation(node); /* We can use this node without decompress it */
    node->dont_compress = 0; /* Re-able compression */
    quicklistCompressNode(node);
    ```

   Perhaps in the future, we could just disable the current entry from being
   compressed during the iterator loop, but that would require more work.

2. Fix crash due to wrongly split quicklist
   before redis#9357, the offset param of _quicklistSplitNode() will not negative.
   For now, when offset is negative, the split extent will be wrong.
   following example:
    ```c
    int orig_start = after ? offset + 1 : 0;
    int orig_extent = after ? -1 : offset;
    int new_start = after ? 0 : offset;
    int new_extent = after ? offset + 1 : -1;
    # offset: -2, after: 1, node->count: 2
    # current wrong range: [-1,-1] [0,-1]
    # correct range: [1,-1] [0, 1]
    ```

   Because only `_quicklistInsert()` splits the quicklistNode and only
   `quicklistInsertAfter()`, `quicklistInsertBefore()` call _quicklistInsert(), 
   so `quicklistReplaceEntry()` and `listTypeInsert()` might occur this crash.
   But the iterator of `listTypeInsert()` is alway from head to tail(iter->offset is
   always positive), so it is not affected.
   The final conclusion is this crash only occur when we insert a large element
   with negative index into a list, that affects `LSET` command and `RM_ListSet`
   module api.
     
3. In external test mode, we need to restore quicklist packed threshold after
   when the end of test.
4. Show `node->count` in quicklistRepr().
5. Add new tcl proc `config_get_set` to support restoring config in tests.
patpatbear added a commit to ctripcorp/Redis-On-Rocks that referenced this pull request Jun 7, 2023
patpatbear added a commit to ctripcorp/Redis-On-Rocks that referenced this pull request Jun 7, 2023
enjoy-binbin pushed a commit to enjoy-binbin/redis that referenced this pull request Jul 31, 2023
… split quicklistNode (redis#11242)

This PR mainly deals with 2 crashes introduced in redis#9357,
and fix the QUICKLIST-PACKED-THRESHOLD mess in external test mode.

1. Fix crash due to deleting an entry from a compress quicklistNode
   When inserting a large element, we need to create a new quicklistNode first,
   and then delete its previous element, if the node where the deleted element is
   located is compressed, it will cause a crash.
   Now add `dont_compress` to quicklistNode, if we want to use a quicklistNode
   after some operation, we can use this flag like following:

    ```c
    node->dont_compress = 1; /* Prevent to be compressed */
    some_operation(node); /* This operation might try to compress this node */
    some_other_operation(node); /* We can use this node without decompress it */
    node->dont_compress = 0; /* Re-able compression */
    quicklistCompressNode(node);
    ```

   Perhaps in the future, we could just disable the current entry from being
   compressed during the iterator loop, but that would require more work.

2. Fix crash due to wrongly split quicklist
   before redis#9357, the offset param of _quicklistSplitNode() will not negative.
   For now, when offset is negative, the split extent will be wrong.
   following example:
    ```c
    int orig_start = after ? offset + 1 : 0;
    int orig_extent = after ? -1 : offset;
    int new_start = after ? 0 : offset;
    int new_extent = after ? offset + 1 : -1;
    # offset: -2, after: 1, node->count: 2
    # current wrong range: [-1,-1] [0,-1]
    # correct range: [1,-1] [0, 1]
    ```

   Because only `_quicklistInsert()` splits the quicklistNode and only
   `quicklistInsertAfter()`, `quicklistInsertBefore()` call _quicklistInsert(), 
   so `quicklistReplaceEntry()` and `listTypeInsert()` might occur this crash.
   But the iterator of `listTypeInsert()` is alway from head to tail(iter->offset is
   always positive), so it is not affected.
   The final conclusion is this crash only occur when we insert a large element
   with negative index into a list, that affects `LSET` command and `RM_ListSet`
   module api.
     
3. In external test mode, we need to restore quicklist packed threshold after
   when the end of test.
4. Show `node->count` in quicklistRepr().
5. Add new tcl proc `config_get_set` to support restoring config in tests.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

release-notes indication that this issue needs to be mentioned in the release notes

Projects

Status: Done

Development

Successfully merging this pull request may close these issues.

2 participants