1. 11 Nov, 2021 1 commit
    • Ozan Tezcan's avatar
      Add sanitizer support and clean up sanitizer findings (#9601) · b91d8b28
      Ozan Tezcan authored
      - Added sanitizer support. `address`, `undefined` and `thread` sanitizers are available.  
      - To build Redis with desired sanitizer : `make SANITIZER=undefined`
      - There were some sanitizer findings, cleaned up codebase
      - Added tests with address and undefined behavior sanitizers to daily CI.
      - Added tests with address sanitizer to the per-PR CI (smoke out mem leaks sooner).
      
      Basically, there are three types of issues : 
      
      **1- Unaligned load/store** : Most probably, this issue may cause a crash on a platform that
      does not support unaligned access. Redis does unaligned access only on supported platforms.
      
      **2- Signed integer overflow.** Although, signed overflow issue can be problematic time to time
      and change how compiler generates code, current findings mostly about signed shift or simple
      addition overflow. For most platforms Redis can be compiled for, this wouldn't cause any issue
      as far as I can tell (checked generated code on godbolt.org).
      
       **3 -Minor leak** (redis-cli), **use-after-free**(just before calling exit());
      
      UB means nothing guaranteed and risky to reason about program behavior but I don't think any
      of the fixes here worth backporting. As sanitizers are now part of the CI, preventing new issues
      will be the real benefit. 
      b91d8b28
  2. 03 Nov, 2021 1 commit
    • perryitay's avatar
      Add support for list type to store elements larger than 4GB (#9357) · f27083a4
      perryitay authored
      
      
      Redis lists are stored in quicklist, which is currently a linked list of ziplists.
      Ziplists are limited to storing elements no larger than 4GB, so when bigger
      items are added they're getting truncated.
      This PR changes quicklists so that they're capable of storing large items
      in quicklist nodes that are plain string buffers rather than ziplist.
      
      As part of the PR there were few other changes in redis: 
      1. new DEBUG sub-commands: 
         - QUICKLIST-PACKED-THRESHOLD - set the threshold of for the node type to
           be plan or ziplist. default (1GB)
         - QUICKLIST <key> - Shows low level info about the quicklist encoding of <key>
      2. rdb format change:
         - A new type was added - RDB_TYPE_LIST_QUICKLIST_2 . 
         - container type (packed / plain) was added to the beginning of the rdb object
           (before the actual node list).
      3. testing:
         - Tests that requires over 100MB will be by default skipped. a new flag was
           added to 'runtest' to run the large memory tests (not used by default)
      Co-authored-by: default avatarsundb <sundbcn@gmail.com>
      Co-authored-by: default avatarOran Agra <oran@redislabs.com>
      f27083a4
  3. 04 Oct, 2021 1 commit
    • Oran Agra's avatar
      Fix ziplist and listpack overflows and truncations (CVE-2021-32627, CVE-2021-32628) (#9589) · c5e6a620
      Oran Agra authored
      
      
      - fix possible heap corruption in ziplist and listpack resulting by trying to
        allocate more than the maximum size of 4GB.
      - prevent ziplist (hash and zset) from reaching size of above 1GB, will be
        converted to HT encoding, that's not a useful size.
      - prevent listpack (stream) from reaching size of above 1GB.
      - XADD will start a new listpack if the new record may cause the previous
        listpack to grow over 1GB.
      - XADD will respond with an error if a single stream record is over 1GB
      - List type (ziplist in quicklist) was truncating strings that were over 4GB,
        now it'll respond with an error.
      Co-authored-by: default avatarsundb <sundbcn@gmail.com>
      c5e6a620
  4. 14 Sep, 2021 1 commit
    • Viktor Söderqvist's avatar
      Modules: Add remaining list API functions (#8439) · ea36d4de
      Viktor Söderqvist authored
      List functions operating on elements by index:
      
      * RM_ListGet
      * RM_ListSet
      * RM_ListInsert
      * RM_ListDelete
      
      Iteration is done using a simple for loop over indices.
      The index based functions use an internal iterator as an optimization.
      This is explained in the docs:
      
      ```
       * Many of the list functions access elements by index. Since a list is in
       * essence a doubly-linked list, accessing elements by index is generally an
       * O(N) operation. However, if elements are accessed sequentially or with
       * indices close together, the functions are optimized to seek the index from
       * the previous index, rather than seeking from the ends of the list.
       *
       * This enables iteration to be done efficiently using a simple for loop:
       *
       *     long n = RM_ValueLength(key);
       *     for (long i = 0; i < n; i++) {
       *         RedisModuleString *elem = RedisModule_ListGet(key, i);
       *         // Do stuff...
       *     }
      ```
      ea36d4de
  5. 06 Sep, 2021 1 commit
    • Viktor Söderqvist's avatar
      Optimize quicklistIndex to seek from the nearest end (#9454) · 547c3405
      Viktor Söderqvist authored
      Until now, giving a negative index seeks from the end of a list and a
      positive seeks from the beginning. This change makes it seek from
      the nearest end, regardless of the sign of the given index.
      
      quicklistIndex is used by all list commands which operate by index.
      
      LINDEX key 999999 in a list if 1M elements is greately optimized by
      this change. Latency is cut by 75%.
      
      LINDEX key -1000000 in a list of 1M elements, likewise.
      
      LRANGE key -1 -1 is affected by this, since LRANGE converts the
      indices to positive numbers before seeking.
      
      The tests for corrupt dumps are updated to make sure the corrup
      data is seeked in the same direction as before.
      547c3405
  6. 08 Aug, 2021 1 commit
    • Binbin's avatar
      Fix the wrong method used in quicklistTest. (#8951) · 563ba7a3
      Binbin authored
      The test try to test `insert before 1 element`, but it use quicklist
      InsertAfter, a copy-paste typo.
      
      The commit also add an assert to verify results in some tests
      to make sure it is as expected.
      563ba7a3
  7. 04 Aug, 2021 1 commit
    • sundb's avatar
      Fix head and tail check with negative offset in _quicklistInsert (#9311) · b4eda142
      sundb authored
      Some background:
      This fixes a problem that used to be dead code till now,
      but became alive (only in the unit tests, not in redis) when #9113 got merged.
      The problem it fixes doesn't actually cause any significant harm,
      but that PR also added a test that fails verification because of that.
      This test was merged with that problem due to human error, we didn't run it
      on the last modified version before merging.
      The fix in this PR existed in #8641 (closed because it's just dead code)
      and #4674 (still pending but has other changes in it).
      
      Now to the actual fix:
      On quicklist insertion, if the insertion offset is -1 or `-(quicklist->count)`,
      we can insert into the head of the next node rather than the tail of the
      current node. this is especially important when the current node is full,
      and adding anything to it will cause it to be split (or be over it's fill limit setting).
      
      The bug was that the code attempted to determine that we're adding to
      the tail of the current node by matching `offset == node->count` when in
      fact it should have been `offset == node->count-1` (so it never entered that `if`).
      and also that since we take negative offsets too, we can also match `-1`.
      same applies for the head, i.e. `0` and `-count`.
      
      The bug will cause the code to attempt inserting into the current node (thinking
      we have to insert into the middle of the node rather than head or tail), and
      in case the current node is full it'll have to be split (something that also
      happens in valid cases).
      On top of that, since it calls _quicklistSplitNode with an edge case, it'll actually
      split the node in a way that all the entries fall into one split, and 0 into the other,
      and then still insert the new entry into the first one, causing it to be populated
      beyond it's intended fill limit.
      
      This problem does not create any bug in redis, because the existing code does
      not iterate from tail to head, and the offset never has a negative value when insert.
      
      The other change this PR makes in the test code is just for some coverage,
      insertion at index 0 is tested a lot, so it's nice to test some negative offsets too.
      b4eda142
  8. 02 Aug, 2021 1 commit
    • cmemory's avatar
      improve quicklist insert head/tail while head/tail node is full. (#9113) · 27a68a4d
      cmemory authored
      In _quicklistInsert when `at_head` / `at_tail` is true, but `prev` / `next` is NULL,
      the code was reaching the last if-else block at the bottom of the function,
      and would have unnecessarily executed _quicklistSplitNode, instead of just creating a new node.
      This was because the penultimate if-else was checking `node->next && full_next`.
      but in fact it was unnecessary to check if `node->next` exists, if we're gonna create one anyway,
      we only care that it's not full, or doesn't exist, so the condition could have been changed to `!node->next || full_next`.
      
      Instead, this PR makes a small refactory to negate `full_next` to a more meaningful variable
      `avail_next` that indicates that the next node is available for pushing additional elements or
      not (this would be true only if it exists and it is non-full)
      27a68a4d
  9. 10 May, 2021 1 commit
  10. 10 Mar, 2021 1 commit
    • sundb's avatar
      Add run all test support with define REDIS_TEST (#8570) · 95d6297d
      sundb authored
      1. Add `redis-server test all` support to run all tests.
      2. Add redis test to daily ci.
      3. Add `--accurate` option to run slow tests for more iterations (so that
         by default we run less cycles (shorter time, and less prints).
      4. Move dict benchmark to REDIS_TEST.
      5. fix some leaks in tests
      6. make quicklist tests run on a specific fill set of options rather than huge ranges
      7. move some prints in quicklist test outside their loops to reduce prints
      8. removing sds.h from dict.c since it is now used in both redis-server and
         redis-cli (uses hiredis sds)
      95d6297d
  11. 08 Mar, 2021 1 commit
    • Huang Zhw's avatar
      __quicklistCompress may compress more node than required (#8311) · 9b4edfdf
      Huang Zhw authored
      When a quicklist has quicklist->compress * 2 nodes, then call
      __quicklistCompress, all nodes will be decompressed and the middle
      two nodes will be recompressed again. This violates the fact that
      quicklist->compress * 2 nodes are uncompressed. It's harmless
      because when visit a node, we always try to uncompress node first.
      This only happened when a quicklist has quicklist->compress * 2 + 1
      nodes, then delete a node. For other scenarios like insert node and
      iterate this will not happen.
      9b4edfdf
  12. 04 Mar, 2021 1 commit
    • sundb's avatar
      Fix memory overlap in quicklistRotate (#8599) · f07b7393
      sundb authored
      When the length of the quicklist is 1(only one zipmap), the rotate operation will cause
      memory overlap when moving an entity from the tail of the zipmap to the head.
      quicklistRotate is a dead code, so it has no impact on the existing code.
      f07b7393
  13. 24 Feb, 2021 1 commit
  14. 16 Feb, 2021 1 commit
  15. 08 Feb, 2021 1 commit
  16. 09 Jan, 2021 1 commit
  17. 22 Dec, 2020 1 commit
  18. 06 Dec, 2020 2 commits
    • Oran Agra's avatar
      Sanitize dump payload: performance optimizations and tuning · e288430c
      Oran Agra authored
      First, if the ziplist header is surely inside the ziplist, do fast path
      decoding rather than the careful one.
      
      In that case, streamline the encoding if-else chain to be executed only
      once, and the encoding validity tested at the end.
      
      encourage inlining
      
      likely / unlikely hints for speculative execution
      
      Assertion used _exit(1) to tell the compiler that the code after them is
      not reachable and get rid of warnings.
      
      But in some cases assertions are placed inside tight loops, and any
      piece of code in them can slow down execution (code cache and other
      reasons), instead using either abort() or better yet, unreachable
      builtin.
      e288430c
    • Oran Agra's avatar
      Sanitize dump payload: fuzz tester and fixes for segfaults and leaks it exposed · c31055db
      Oran Agra authored
      The test creates keys with various encodings, DUMP them, corrupt the payload
      and RESTORES it.
      It utilizes the recently added use-exit-on-panic config to distinguish between
       asserts and segfaults.
      If the restore succeeds, it runs random commands on the key to attempt to
      trigger a crash.
      
      It runs in two modes, one with deep sanitation enabled and one without.
      In the first one we don't expect any assertions or segfaults, in the second one
      we expect assertions, but no segfaults.
      We also check for leaks and invalid reads using valgrind, and if we find them
      we print the commands that lead to that issue.
      
      Changes in the code (other than the test):
      - Replace a few NPD (null pointer deference) flows and division by zero with an
        assertion, so that it doesn't fail the test. (since we set the server to use
        `exit` rather than `abort` on assertion).
      - Fix quite a lot of flows in rdb.c that could have lead to memory leaks in
        RESTORE command (since it now responds with an error rather than panic)
      - Add a DEBUG flag for SET-SKIP-CHECKSUM-VALIDATION so that the test don't need
        to bother with faking a valid checksum
      - Remove a pile of code in serverLogObjectDebugInfo which is actually unsafe to
        run in the crash report (see comments in the code)
      - fix a missing boundary check in lzf_decompress
      
      test suite infra improvements:
      - be able to run valgrind checks before the process terminates
      - rotate log files when restarting servers
      c31055db
  19. 09 Sep, 2020 1 commit
  20. 02 Apr, 2020 1 commit
  21. 18 Feb, 2020 1 commit
    • Oran Agra's avatar
      Defrag big lists in portions to avoid latency and freeze · 485425ce
      Oran Agra authored
      When active defrag kicks in and finds a big list, it will create a bookmark to
      a node so that it is able to resume iteration from that node later.
      
      The quicklist manages that bookmark, and updates it in case that node is deleted.
      
      This will increase memory usage only on lists of over 1000 (see
      active-defrag-max-scan-fields) quicklist nodes (1000 ziplists, not 1000 items)
      by 16 bytes.
      
      In 32 bit build, this change reduces the maximum effective config of
      list-compress-depth and list-max-ziplist-size (from 32767 to 8191)
      485425ce
  22. 03 Jul, 2018 1 commit
  23. 04 Dec, 2017 1 commit
  24. 28 Oct, 2016 1 commit
  25. 27 Jun, 2016 1 commit
    • antirez's avatar
      Fix quicklistReplaceAtIndex() by updating the quicklist ziplist size. · 5e176e1a
      antirez authored
      The quicklist takes a cached version of the ziplist representation size
      in bytes. The implementation must update this length every time the
      underlying ziplist changes. However quicklistReplaceAtIndex() failed to
      fix the length.
      
      During LSET calls, the size of the ziplist blob and the cached size
      inside the quicklist diverged. Later, when this size is used in an
      authoritative way, for example during nodes splitting in order to copy
      the nodes, we end with a duplicated node that may contain random
      garbage.
      
      This commit should fix issue #3343, however several problems were found
      reviewing the quicklist.c code in search of this bug that should be
      addressed soon or later.
      
      For example:
      
      1. To take a cached ziplist length is fragile since failing to update it
      leads to this kind of issues.
      
      2. The node splitting code needs auditing. For example it works just for
      a side effect of ziplistDeleteRange() to be able to cope with a wrong
      count of elements to remove. The code inside quicklist.c assumes that
      -1 means "delete till the end" while actually it's just a count of how
      many elements to delete, and is an unsigned count. So -1 gets converted
      into the maximum integer, and just by chance the ziplist code stops
      deleting elements after there are no more to delete.
      
      3. Node splitting is extremely inefficient, it copies the node and
      removes elements from both nodes even when actually there is to move a
      single entry from one node to the other, or when the new resulting node
      is empty at all so there is nothing to copy but just to create a new
      node.
      
      However at least for Redis 3.2 to introduce fresh code inside
      quicklist.c may be even more risky, so instead I'm writing a better
      fuzzy tester to stress the internals a bit more in order to anticipate
      other possible bugs.
      
      This bug was found using a fuzzy tester written after having some clue
      about where the bug could be. The tester eventually created a ~2000
      commands sequence able to always crash Redis. I wrote a better version
      of the tester that searched for the smallest sequence that could crash
      Redis automatically. Later this smaller sequence was minimized by
      removing random commands till it still crashed the server. This resulted
      into a sequence of 7 commands. With this small sequence it was just a
      matter of filling the code with enough printf() to understand enough
      state to fix the bug.
      5e176e1a
  26. 20 Jun, 2016 1 commit
  27. 17 Feb, 2015 2 commits
  28. 02 Jan, 2015 8 commits
    • Matt Stancliff's avatar
      Set optional 'static' for Quicklist+Redis · 25e12d10
      Matt Stancliff authored
      This also defines REDIS_STATIC='' for building everything
      inside src/ and everything inside deps/lua/.
      25e12d10
    • Matt Stancliff's avatar
      Add branch prediction hints to quicklist · bbbbfb14
      Matt Stancliff authored
      Actually makes a noticeable difference.
      
      Branch hints were selected based on profiler hotspots.
      bbbbfb14
    • Matt Stancliff's avatar
      Cleanup quicklist style · 5f506b6d
      Matt Stancliff authored
      Small fixes due to a new version of clang-format (it's less
      crazy than the older version).
      5f506b6d
    • Matt Stancliff's avatar
      Allow compression of interior quicklist nodes · abdd1414
      Matt Stancliff authored
      Let user set how many nodes to *not* compress.
      
      We can specify a compression "depth" of how many nodes
      to leave uncompressed on each end of the quicklist.
      
      Depth 0 = disable compression.
      Depth 1 = only leave head/tail uncompressed.
        - (read as: "skip 1 node on each end of the list before compressing")
      Depth 2 = leave head, head->next, tail->prev, tail uncompressed.
        - ("skip 2 nodes on each end of the list before compressing")
      Depth 3 = Depth 2 + head->next->next + tail->prev->prev
        - ("skip 3 nodes...")
      etc.
      
      This also:
        - updates RDB storage to use native quicklist compression (if node is
          already compressed) instead of uncompressing, generating the RDB string,
          then re-compressing the quicklist node.
        - internalizes the "fill" parameter for the quicklist so we don't
          need to pass it to _every_ function.  Now it's just a property of
          the list.
        - allows a runtime-configurable compression option, so we can
          expose a compresion parameter in the configuration file if people
          want to trade slight request-per-second performance for up to 90%+
          memory savings in some situations.
        - updates the quicklist tests to do multiple passes: 200k+ tests now.
      abdd1414
    • Matt Stancliff's avatar
      Remove malloc failure checks · 8d702189
      Matt Stancliff authored
      We trust zmalloc to kill the whole process on memory failure
      8d702189
    • Matt Stancliff's avatar
      Add adaptive quicklist fill factor · c6bf20c2
      Matt Stancliff authored
      Fill factor now has two options:
        - negative (1-5) for size-based ziplist filling
        - positive for length-based ziplist filling with implicit size cap.
      
      Negative offsets define ziplist size limits of:
        -1: 4k
        -2: 8k
        -3: 16k
        -4: 32k
        -5: 64k
      
      Positive offsets now automatically limit their max size to 8k.  Any
      elements larger than 8k will be in individual nodes.
      
      Positive ziplist fill factors will keep adding elements
      to a ziplist until one of:
        - ziplist has FILL number of elements
          - or -
        - ziplist grows above our ziplist max size (currently 8k)
      
      When using positive fill factors, if you insert a large
      element (over 8k), that element will automatically allocate
      an individual quicklist node with one element and no other elements will be
      in the same ziplist inside that quicklist node.
      
      When using negative fill factors, elements up to the size
      limit can be added to one quicklist node.  If an element
      is added larger than the max ziplist size, that element
      will be allocated an individual ziplist in a new quicklist node.
      
      Tests also updated to start testing at fill factor -5.
      c6bf20c2
    • Matt Stancliff's avatar
      Add ziplistMerge() · 9d2dc024
      Matt Stancliff authored
      This started out as #2158 by sunheehnus, but I kept rewriting it
      until I could understand things more easily and get a few more
      correctness guarantees out of the readability flow.
      
      The original commit created and returned a new ziplist with the contents of
      both input ziplists, but I prefer to grow one of the input ziplists
      and destroy the other one.
      
      So, instead of malloc+copy as in #2158, the merge now reallocs one of
      the existing ziplists and copies the other ziplist into the new space.
      
      Also added merge test cases to ziplistTest()
      9d2dc024
    • Matt Stancliff's avatar
      Add quicklist implementation · 5e362b84
      Matt Stancliff authored
      This replaces individual ziplist vs. linkedlist representations
      for Redis list operations.
      
      Big thanks for all the reviews and feedback from everybody in
      https://github.com/antirez/redis/pull/2143
      5e362b84