1. 10 Apr, 2023 1 commit
  2. 21 Mar, 2023 1 commit
  3. 08 Mar, 2023 9 commits
  4. 20 Jan, 2023 1 commit
    • Viktor Söderqvist's avatar
      Key as dict entry - memory optimization for sets (#11595) · f3f6f7c0
      Viktor Söderqvist authored
      If a dict has only keys, and no use of values, then a key can be stored directly in a
      dict's hashtable. The key replaces the dictEntry. To distinguish between a key and
      a dictEntry, we only use this optimization if the key is odd, i.e. if the key has the least
      significant bit set. This is true for sds strings, since the sds header is always an odd
      number of bytes.
      
      Dict entries are used as a fallback when there is a hash collision. A special dict entry
      without a value (only key and next) is used so we save one word in this case too.
      
      This saves 24 bytes per set element for larges sets, and also gains some speed improvement
      as a side effect (less allocations and cache misses).
      
      A quick test adding 1M elements to a set using the command below resulted in memory
      usage of 28.83M, compared to 46.29M on unstable.
      That's 18 bytes per set element on average.
      
          eval 'for i=1,1000000,1 do redis.call("sadd", "myset", "x"..i) end' 0
      
      Other changes:
      
      Allocations are ensured to have at least 8 bits alignment on all systems. This affects 32-bit
      builds compiled without HAVE_MALLOC_SIZE (not jemalloc or glibc) in which Redis
      stores the size of each allocation, after this change in 8 bytes instead of previously 4 bytes
      per allocation. This is done so we can reliably use the 3 least significant bits in a pointer to
      encode stuff.
      f3f6f7c0
  5. 11 Jan, 2023 3 commits
    • Viktor Söderqvist's avatar
      Remove the bucket-cb from dictScan and move dictEntry defrag to dictScanDefrag · b60d33c9
      Viktor Söderqvist authored
      This change deletes the dictGetNext and dictGetNextRef functions, so the
      dict API doesn't expose the next field at all.
      
      The bucket function in dictScan is deleted. A separate dictScanDefrag function
      is added which takes a defrag alloc function to defrag-reallocate the dict entries.
      
      "Dirty" code accessing the dict internals in active defrag is removed.
      
      An 'afterReplaceEntry' is added to dictType, which allows the dict user
      to keep the dictEntry metadata up to date after reallocation/defrag/move.
      
      Additionally, for updating the cluster slot-to-key mapping, after a dictEntry
      has been reallocated, we need to know which db a dict belongs to, so we store
      a pointer to the db in a new metadata section in the dict struct, which is
      a new mechanism similar to dictEntry metadata. This adds some complexity but
      provides better isolation.
      b60d33c9
    • Viktor Söderqvist's avatar
      activeDefragSdsDict use scan instead of iterator and drop dictSetNext · d4e9e0ae
      Viktor Söderqvist authored
      Also delete unused function activeDefragSdsListAndDict
      d4e9e0ae
    • Viktor Söderqvist's avatar
      Make dictEntry opaque · c84248b5
      Viktor Söderqvist authored
      Use functions for all accesses to dictEntry (except in dict.c). Dict abuses
      e.g. in defrag.c have been replaced by support functions provided by dict.
      c84248b5
  6. 10 Jan, 2023 1 commit
  7. 30 Nov, 2022 1 commit
    • Huang Zhw's avatar
      Add a special notification unlink available only for modules (#9406) · c8181314
      Huang Zhw authored
      
      
      Add a new module event `RedisModule_Event_Key`, this event is fired
      when a key is removed from the keyspace.
      The event includes an open key that can be used for reading the key before
      it is removed. Modules can also extract the key-name, and use RM_Open
      or RM_Call to access key from within that event, but shouldn't modify anything
      from within this event.
      
      The following sub events are available:
        - `REDISMODULE_SUBEVENT_KEY_DELETED`
        - `REDISMODULE_SUBEVENT_KEY_EXPIRED`
        - `REDISMODULE_SUBEVENT_KEY_EVICTED`
        - `REDISMODULE_SUBEVENT_KEY_OVERWRITE`
      
      The data pointer can be casted to a RedisModuleKeyInfo structure
      with the following fields:
      ```
           RedisModuleKey *key;    // Opened Key
       ```
      
      ### internals
      
      * We also add two dict functions:
        `dictTwoPhaseUnlinkFind` finds an element from the table, also get the plink of the entry.
        The entry is returned if the element is found. The user should later call `dictTwoPhaseUnlinkFree`
        with it in order to unlink and release it. Otherwise if the key is not found, NULL is returned.
        These two functions should be used in pair. `dictTwoPhaseUnlinkFind` pauses rehash and
        `dictTwoPhaseUnlinkFree` resumes rehash.
      * We change `dbOverwrite` to `dbReplaceValue` which just replaces the value of the key and
        doesn't fire any events. The "overwrite" part (which emits events) is just when called from `setKey`,
        the other places that called dbOverwrite were ones that just update the value in-place (INCR*, SPOP,
        and dbUnshareStringValue). This should not have any real impact since `moduleNotifyKeyUnlink` and
        `signalDeletedKeyAsReady` wouldn't have mattered in these cases anyway (i.e. module keys and
        stream keys didn't have direct calls to dbOverwrite)
      * since we allow doing RM_OpenKey from withing these callbacks, we temporarily disable lazy expiry.
      * We also temporarily disable lazy expiry when we are in unlink/unlink2 callback and keyspace 
        notification callback.
      * Move special definitions to the top of redismodule.h
        This is needed to resolve compilation errors with RedisModuleKeyInfoV1
        that carries a RedisModuleKey member.
      Co-authored-by: default avatarOran Agra <oran@redislabs.com>
      c8181314
  8. 26 Nov, 2022 1 commit
    • Viktor Söderqvist's avatar
      Shrink dict without rehashing (#11540) · abf70309
      Viktor Söderqvist authored
      When we're shrinking the hash table, we don't need to hash the keys. 
      Since the table sizes are powers of two, we can simply mask the bucket 
      index in the larger table to get the bucket index in the smaller table. We 
      avoid loading the keys into memory and save CPU time.
      abf70309
  9. 08 Sep, 2022 1 commit
  10. 18 Jul, 2022 1 commit
    • ranshid's avatar
      Avoid using unsafe C functions (#10932) · eacca729
      ranshid authored
      replace use of:
      sprintf --> snprintf
      strcpy/strncpy  --> redis_strlcpy
      strcat/strncat  --> redis_strlcat
      
      **why are we making this change?**
      Much of the code uses some unsafe variants or deprecated buffer handling
      functions.
      While most cases are probably not presenting any issue on the known path
      programming errors and unterminated strings might lead to potential
      buffer overflows which are not covered by tests.
      
      **As part of this PR we change**
      1. added implementation for redis_strlcpy and redis_strlcat based on the strl implementation: https://linux.die.net/man/3/strl
      2. change all occurrences of use of sprintf with use of snprintf
      3. change occurrences of use of  strcpy/strncpy with redis_strlcpy
      4. change occurrences of use of strcat/strncat with redis_strlcat
      5. change the behavior of ll2string/ull2string/ld2string so that it will always place null
        termination ('\0') on the output buffer in the first index. this was done in order to make
        the use of these functions more safe in cases were the user will not check the output
        returned by them (for example in rdbRemoveTempFile)
      6. we added a compiler directive to issue a deprecation error in case a use of
        sprintf/strcpy/strcat is found during compilation which will result in error during compile time.
        However keep in mind that since the deprecation attribute is not supported on all compilers,
        this is expected to fail during push workflows.
      
      
      **NOTE:** while this is only an initial milestone. We might also consider
      using the *_s implementation provided by the C11 Extensions (however not
      yet widly supported). I would also suggest to start
      looking at static code analyzers to track unsafe use cases.
      For example LLVM clang checker supports security.insecureAPI.DeprecatedOrUnsafeBufferHandling
      which can help locate unsafe function usage.
      https://clang.llvm.org/docs/analyzer/checkers.html#security-insecureapi-deprecatedorunsafebufferhandling-c
      The main reason not to onboard it at this stage is that the alternative
      excepted by clang is to use the C11 extensions which are not always
      supported by stdlib.
      eacca729
  11. 14 Jun, 2022 1 commit
  12. 19 Dec, 2021 1 commit
    • Binbin's avatar
      Fix some nonsense came from LGTM (#9962) · 0fb1aa06
      Binbin authored
      1. Local variable 's' hides a parameter of the same name.
      ```
      int anetTcpAccept(char *err, int s, char *ip, size_t ip_len, int *port) {
          if ((fd = anetGenericAccept(err,s,(struct sockaddr*)&sa,&salen)) == ANET_ERR){}
      }
      ```
      Change the parameter name from `s` to `serversock`,
      also unified with the header file definition.
      
      2. Comparison is always false because i <= 48.
      ```
      for (i = 0; i < DICT_STATS_VECTLEN-1; i++) {  // i < 49
          (i == DICT_STATS_VECTLEN-1)?">= ":"",  // i == 49
      }
      ```
      `i == DICT_STATS_VECTLEN-1` always result false, it is a dead code.
      
      3. Empty block without comment.
      `else if (!strcasecmp(opt,"ch")) {}`, add a comment to avoid warnings.
      
      4. Bit field fill of type int should have explicitly unsigned integral, explicitly signed integral, or enumeration type.
      Modify `int fill: QL_FILL_BITS;` to `unsigned int fill: QL_FILL_BITS;`
      
      5. The result of this call to reconnectingRedisCommand is not checked for null, but 80% of calls to reconnectingRedisCommand check for null.
      Just a cleanup job like others.
      0fb1aa06
  13. 13 Dec, 2021 1 commit
    • yoav-steinberg's avatar
      Fix possible int overflow when hashing an sds. (#9916) · c7dc17fc
      yoav-steinberg authored
      This caused a crash when adding elements larger than 2GB to a set (same goes for hash keys). See #8455.
      
      Details:
      * The fix makes the dict hash functions receive a `size_t` instead of an `int`. In practice the dict hash functions
        call siphash which receives a `size_t` and the callers to the hash function pass a `size_t` to it so the fix is trivial.
      * The issue was recreated by attempting to add a >2gb value to a set. Appropriate tests were added where I create
        a set with large elements and check basic functionality on it (SADD, SCARD, SPOP, etc...).
      * When I added the tests I also refactored a bit all the tests code which is run under the `--large-memory` flag.
        This removed code duplication for the test framework's `write_big_bulk` and `write_big_bulk` code and also takes
        care of not allocating the test frameworks helper huge string used by these tests when not run under `--large-memory`.
      * I also added the _violoations.tcl_ unit tests to be part of the entire test suite and leaned up non relevant list related
        tests that were in there. This was done in this PR because most of the _violations_ tests are "large memory" tests.
      c7dc17fc
  14. 07 Dec, 2021 1 commit
  15. 16 Nov, 2021 1 commit
  16. 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
  17. 31 Aug, 2021 1 commit
    • Viktor Söderqvist's avatar
      Slot-to-keys using dict entry metadata (#9356) · f24c63a2
      Viktor Söderqvist authored
      
      
      * Enhance dict to support arbitrary metadata carried in dictEntry
      Co-authored-by: default avatarViktor Söderqvist <viktor.soderqvist@est.tech>
      
      * Rewrite slot-to-keys mapping to linked lists using dict entry metadata
      
      This is a memory enhancement for Redis Cluster.
      
      The radix tree slots_to_keys (which duplicates all key names prefixed with their
      slot number) is replaced with a linked list for each slot. The dict entries of
      the same cluster slot form a linked list and the pointers are stored as metadata
      in each dict entry of the main DB dict.
      
      This commit also moves the slot-to-key API from db.c to cluster.c.
      Co-authored-by: default avatarJim Brunner <brunnerj@amazon.com>
      f24c63a2
  18. 15 Aug, 2021 1 commit
  19. 05 Aug, 2021 2 commits
    • Oran Agra's avatar
      Improvements to corrupt payload sanitization (#9321) · 0c90370e
      Oran Agra authored
      
      
      Recently we found two issues in the fuzzer tester: #9302 #9285
      After fixing them, more problems surfaced and this PR (as well as #9297) aims to fix them.
      
      Here's a list of the fixes
      - Prevent an overflow when allocating a dict hashtable
      - Prevent OOM when attempting to allocate a huge string
      - Prevent a few invalid accesses in listpack
      - Improve sanitization of listpack first entry
      - Validate integrity of stream consumer groups PEL
      - Validate integrity of stream listpack entry IDs
      - Validate ziplist tail followed by extra data which start with 0xff
      Co-authored-by: default avatarsundb <sundbcn@gmail.com>
      0c90370e
    • yoav-steinberg's avatar
      dict struct memory optimizations (#9228) · 5e908a29
      yoav-steinberg authored
      Reduce dict struct memory overhead
      on 64bit dict size goes down from jemalloc's 96 byte bin to its 56 byte bin.
      
      summary of changes:
      - Remove `privdata` from callbacks and dict creation. (this affects many files, see "Interface change" below).
      - Meld `dictht` struct into the `dict` struct to eliminate struct padding. (this affects just dict.c and defrag.c)
      - Eliminate the `sizemask` field, can be calculated from size when needed.
      - Convert the `size` field into `size_exp` (exponent), utilizes one byte instead of 8.
      
      Interface change: pass dict pointer to dict type call back functions.
      This is instead of passing the removed privdata field. In the future if
      we'd like to have private data in the callbacks we can extract it from
      the dict type. We can extend dictType to include a custom dict struct
      allocator and use it to allocate more data at the end of the dict
      struct. This data can then be used to store private data later acccessed
      by the callbacks.
      5e908a29
  20. 09 May, 2021 1 commit
  21. 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
  22. 20 Feb, 2021 1 commit
    • Jim Brunner's avatar
      dict: pause rehash, minor readability refactor (#8515) · 06966d2a
      Jim Brunner authored
      The `dict` field `iterators` is misleading and incorrect. 
      This variable is used for 1 purpose - to pause rehashing.
      
      The current `iterators` field doesn't actually count "iterators".
      It counts "safe iterators".  But - it doesn't actually count safe iterators
      either.  For one, it's only incremented once the safe iterator begins to
      iterate, not when it's created.  It's also incremented in `dictScan` to
      prevent rehashing (and commented to make it clear why `iterators` is
      being incremented during a scan).
      
      This update renames the field as `pauserehash` and creates 2 helper
      macros `dictPauseRehashing(d)` and `dictResumeRehashing(d)`
      06966d2a
  23. 17 Feb, 2021 1 commit
  24. 23 Dec, 2020 1 commit
    • Greg Femec's avatar
      Fix random element selection for large hash tables. (#8133) · 266949c7
      Greg Femec authored
      
      
      When a database on a 64 bit build grows past 2^31 keys, the underlying hash table expands to 2^32 buckets. After this point, the algorithms for selecting random elements only return elements from half of the available buckets because they use random() which has a range of 0 to 2^31 - 1. This causes problems for eviction policies which use dictGetSomeKeys or dictGetRandomKey. Over time they cause the hash table to become unbalanced because, while new keys are spread out evenly across all buckets, evictions come from only half of the available buckets. Eventually this half of the table starts to run out of keys and it takes longer and longer to find candidates for eviction. This continues until no more evictions can happen.
      
      This solution addresses this by using a 64 bit PRNG instead of libc random().
      Co-authored-by: default avatarGreg Femec <gfemec@google.com>
      266949c7
  25. 22 Dec, 2020 1 commit
  26. 17 Dec, 2020 1 commit
  27. 06 Dec, 2020 2 commits
    • Oran Agra's avatar
      Sanitize dump payload: fail RESTORE if memory allocation fails · 7ca00d69
      Oran Agra authored
      When RDB input attempts to make a huge memory allocation that fails,
      RESTORE should fail gracefully rather than die with panic
      7ca00d69
    • Wang Yuan's avatar
      Limit the main db and expires dictionaries to expand (#7954) · 75f9dec6
      Wang Yuan authored
      As we know, redis may reject user's requests or evict some keys if
      used memory is over maxmemory. Dictionaries expanding may make
      things worse, some big dictionaries, such as main db and expires dict,
      may eat huge memory at once for allocating a new big hash table and be
      far more than maxmemory after expanding.
      There are related issues: #4213 #4583
      
      More details, when expand dict in redis, we will allocate a new big
      ht[1] that generally is double of ht[0], The size of ht[1] will be
      very big if ht[0] already is big. For db dict, if we have more than
      64 million keys, we need to cost 1GB for ht[1] when dict expands.
      
      If the sum of used memory and new hash table of dict needed exceeds
      maxmemory, we shouldn't allow the dict to expand. Because, if we
      enable keys eviction, we still couldn't add much more keys after
      eviction and rehashing, what's worse, redis will keep less keys when
      redis only remains a little memory for storing new hash table instead
      of users' data. Moreover users can't write data in redis if disable
      keys eviction.
      
      What this commit changed ?
      
      Add a new member function expandAllowed for dict type, it provide a way
      for caller to allow expand or not. We expose two parameters for this
      function: more memory needed for expanding and dict current load factor,
      users can implement a function to make a decision by them.
      For main db dict and expires dict type, these dictionaries may be very
      big and cost huge memory for expanding, so we implement a judgement
      function: we can stop dict to expand provisionally if used memory will
      be over maxmemory after dict expands, but to guarantee the performance
      of redis, we still allow dict to expand if dict load factor exceeds the
      safe load factor.
      Add test cases to verify we don't allow main db to expand when left
      memory is not enough, so that avoid keys eviction.
      
      Other changes:
      
      For new hash table size when expand. Before this commit, the size is
      that double used of dict and later _dictNextPower. Actually we aim to
      control a dict load factor between 0.5 and 1.0. Now we replace *2 with
      +1, since the first check is that used >= size, the outcome of before
      will usually be the same as _dictNextPower(used+1). The only case where
      it'll differ is when dict_can_resize is false during fork, so that later
      the _dictNextPower(used*2) will cause the dict to jump to *4 (i.e.
      _dictNextPower(1025*2) will return 4096).
      Fix rehash test cases due to changing algorithm of new hash table size
      when expand.
      75f9dec6
  28. 28 Oct, 2020 1 commit