1. 21 Jun, 2012 2 commits
    • antirez's avatar
      b3f28b90
    • antirez's avatar
      Fixed a timing attack on AUTH (Issue #560). · 4b3865cb
      antirez authored
      The way we compared the authentication password using strcmp() allowed
      an attacker to gain information about the password using a well known
      class of attacks called "timing attacks".
      
      The bug appears to be practically not exploitable in most modern systems
      running Redis since even using multiple bytes of differences in the
      input at a time instead of one the difference in running time in in the
      order of 10 nanoseconds, making it hard to exploit even on LAN. However
      attacks always get better so we are providing a fix ASAP.
      
      The new implementation uses two fixed length buffers and a constant time
      comparison function, with the goal of:
      
      1) Completely avoid leaking information about the content of the
      password, since the comparison is always performed between 512
      characters and without conditionals.
      2) Partially avoid leaking information about the length of the
      password.
      
      About "2" we still have a stage in the code where the real password and
      the user provided password are copied in the static buffers, we also run
      two strlen() operations against the two inputs, so the running time
      of the comparison is a fixed amount plus a time proportional to
      LENGTH(A)+LENGTH(B). This means that the absolute time of the operation
      performed is still related to the length of the password in some way,
      but there is no way to change the input in order to get a difference in
      the execution time in the comparison that is not just proportional to
      the string provided by the user (because the password length is fixed).
      
      Thus in practical terms the user should try to discover LENGTH(PASSWORD)
      looking at the whole execution time of the AUTH command and trying to
      guess a proportionality between the whole execution time and the
      password length: this appears to be mostly unfeasible in the real world.
      
      Also protecting from this attack is not very useful in the case of Redis
      as a brute force attack is anyway feasible if the password is too short,
      while with a long password makes it not an issue that the attacker knows
      the length.
      4b3865cb
  2. 15 Jun, 2012 3 commits
    • antirez's avatar
      Redis 2.5.11 (2.6 RC5). · 0c9cf452
      antirez authored
      0c9cf452
    • antirez's avatar
      Fix c->reply_bytes computation in setDeferredMultiBulkLength() · 6fe9c402
      antirez authored
      In order to implement reply buffer limits introduced in 2.6 and useful
      to close the connection under user-selected circumastances of big output
      buffers (for instance slow consumers in pub/sub, a blocked slave, and so
      forth) Redis takes a counter with the amount of used memory in objects
      inside the output list stored into c->reply.
      
      The computation was broken in the function setDeferredMultiBulkLength(),
      in the case the object was glued with the next one. This caused the
      c->reply_bytes field to go out of sync, be subtracted more than needed,
      and wrap back near to ULONG_MAX values.
      
      This commit fixes this bug and adds an assertion that is able to trap
      this class of problems.
      
      This problem was discovered looking at the INFO output of an unrelated
      issue (issue #547).
      6fe9c402
    • antirez's avatar
      ziplistFind(): don't assume that entries are comparable by encoding. · 8361d6c4
      antirez authored
      Because Redis 2.6 introduced new integer encodings it is no longer true
      that if two entries have a different encoding they are not equal.
      
      An old ziplist can be loaded from an RDB file generated with Redis 2.4,
      in this case for instance a small unsigned integers is encoded with a
      16 bit encoding, while in Redis 2.6 a more specific 8 bit encoding
      format is used.
      
      Because of this bug hashes ended with duplicated values or fields lookup
      failed, causing many bad behaviors.
      This in turn caused a crash while converting the ziplist encoded hash into
      a real hash table because an assertion was raised on duplicated elements.
      
      This commit fixes issue #547.
      
      Many thanks to Pinterest's Marty Weiner and colleagues for discovering
      the problem and helping us in the debugging process.
      8361d6c4
  3. 13 Jun, 2012 1 commit
    • Ted Nyman's avatar
      Standardize punctuation in redis-cli help. · e612508d
      Ted Nyman authored
      Right there is a mix of help entries ending with periods or
      without periods. This standardizes the end of command as without
      periods, which seems to be the general custom in most unix tools,
      at least.
      e612508d
  4. 11 Jun, 2012 1 commit
    • antirez's avatar
      Dump ziplist hex value on failed assertion. · 0b8441c1
      antirez authored
      The ziplist -> hashtable conversion code is triggered every time an hash
      value must be promoted to a full hash table because the number or size of
      elements reached the threshold.
      
      If a problem in the ziplist causes the same field to be present
      multiple times, the assertion of successful addition of the element
      inside the hash table will fail, crashing server with a failed
      assertion, but providing little information about the problem.
      
      This code adds a new logging function to perform the hex dump of binary
      data, and makes sure that the ziplist -> hashtable conversion code uses
      this new logging facility to dump the content of the ziplist when the
      assertion fails.
      
      This change was originally made in order to investigate issue #547.
      0b8441c1
  5. 07 Jun, 2012 1 commit
  6. 02 Jun, 2012 2 commits
    • Alex Mitrofanov's avatar
      Fixed RESTORE hash failure (Issue #532) · 591c9e65
      Alex Mitrofanov authored
      (additional commit notes by antirez@gmail.com):
      
      The rdbIsObjectType() macro was not updated when the new RDB object type
      of ziplist encoded hashes was added.
      
      As a result RESTORE, that uses rdbLoadObjectType(), failed when a
      ziplist encoded hash was loaded.
      This does not affected normal RDB loading because in that case we use
      the lower-level function rdbLoadType().
      
      The commit also adds a regression test.
      591c9e65
    • antirez's avatar
      RDB type loading functions clarified in comments. · ebdcd723
      antirez authored
      Improved comments to make clear that rdbLoadType() just loads a
      general TYPE in the context of RDB that can be an object type or an
      expire type, end-of-file, and so forth.
      
      While rdbLoadObjectType() enforces that the type is a valid Object Type
      otherwise it returns -1.
      ebdcd723
  7. 31 May, 2012 1 commit
    • antirez's avatar
      BITOP bug when called against non existing keys fixed. · 8f0658cd
      antirez authored
      In the issue #529 an user reported a bug that can be triggered with the
      following code:
      
      flushdb
      set a
      "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
      bitop or x a b
      
      The bug was introduced with the speed optimization in commit 8bbc0768
      that specializes every BITOP operation loop up to the minimum length of
      the input strings.
      
      However the computation of the minimum length contained an error when a
      non existing key was present in the input, after a key that was non zero
      length.
      
      This commit fixes the bug and adds a regression test for it.
      8f0658cd
  8. 25 May, 2012 1 commit
    • antirez's avatar
      Four new persistence fields in INFO. A few renamed. · 6b4d92e2
      antirez authored
      The 'persistence' section of INFO output now contains additional four
      fields related to RDB and AOF persistence:
      
       rdb_last_bgsave_time_sec       Duration of latest BGSAVE in sec.
       rdb_current_bgsave_time_sec    Duration of current BGSAVE in sec.
       aof_last_rewrite_time_sec      Duration of latest AOF rewrite in sec.
       aof_current_rewrite_time_sec   Duration of current AOF rewrite in sec.
      
      The 'current' fields are set to -1 if a BGSAVE / AOF rewrite is not in
      progress. The 'last' fileds are set to -1 if no previous BGSAVE / AOF
      rewrites were performed.
      
      Additionally a few fields in the persistence section were renamed for
      consistency:
      
       changes_since_last_save -> rdb_changes_since_last_save
       bgsave_in_progress -> rdb_bgsave_in_progress
       last_save_time -> rdb_last_save_time
       last_bgsave_status -> rdb_last_bgsave_status
       bgrewriteaof_in_progress -> aof_rewrite_in_progress
       bgrewriteaof_scheduled -> aof_rewrite_scheduled
      
      After the renaming, fields in the persistence section start with rdb_ or
      aof_ prefix depending on the persistence method they describe.
      The field 'loading' and related fields are not prefixed because they are
      unique for both the persistence methods.
      6b4d92e2
  9. 24 May, 2012 11 commits
    • antirez's avatar
      BITOP command 10x speed improvement. · 8bbc0768
      antirez authored
      This commit adds a fast-path to the BITOP that can be used for all the
      bytes from 0 to the minimal length of the string, and if there are
      at max 16 input keys.
      
      Often the intersected bitmaps are roughly the same size, so this
      optimization can provide a 10x speed boost to most real world usages
      of the command.
      
      Bytes are processed four full words at a time, in loops specialized
      for the specific BITOP sub-command, without the need to check for
      length issues with the inputs (since we run this algorithm only as far
      as there is data from all the keys at the same time).
      
      The remaining part of the string is intersected in the usual way using
      the slow but generic algorith.
      
      It is possible to do better than this with inputs that are not roughly
      the same size, sorting the input keys by length, by initializing the
      result string in a smarter way, and noticing that the final part of the
      output string composed of only data from the longest string does not
      need any proecessing since AND, OR and XOR against an empty string does
      not alter the output (zero in the first case, and the original string in
      the other two cases).
      
      More implementations will be implemented later likely, but this should
      be enough to release Redis 2.6-RC4 with bitops merged in.
      
      Note: this commit also adds better testing for BITOP NOT command, that
      is currently the faster and hard to optimize further since it just
      flips the bits of a single input string.
      8bbc0768
    • antirez's avatar
      BITOP: handle integer encoded objects correctly. · f0d962c0
      antirez authored
      A bug in the implementation caused BITOP to crash the server if at least
      one one of the source objects was integer encoded.
      
      The new implementation takes an additional array of Redis objects
      pointers and calls getDecodedObject() to get a reference to a string
      encoded object, and then uses decrRefCount() to release the object.
      
      Tests modified to cover the regression and improve coverage.
      f0d962c0
    • antirez's avatar
      BITCOUNT performance improved. · c19bfe9f
      antirez authored
      At Redis's default optimization level the command is now much faster,
      always using a constant-time bit manipualtion technique to count bits
      instead of GCC builtin popcount, and unrolling the loop.
      
      The current implementation performance is 1.5GB/s in a MBA 11" (1.8 Ghz
      i7) compiled with both GCC and clang.
      
      The algorithm used is described here:
      
      http://graphics.stanford.edu/~seander/bithacks.html
      c19bfe9f
    • antirez's avatar
      bitop.c renamed bitops.c · e53a1fdd
      antirez authored
      bitop.c contains the "Bit related string operations" so it seems more
      logical to call it bitops instead of bitop.
      This also makes it matching the name of the test (unit/bitops.tcl).
      e53a1fdd
    • antirez's avatar
      popcount() optimization for speed. · d12a68d4
      antirez authored
      We run the array by 32 bit words instead of processing it byte per byte.
      If the code is compiled using GCC __builtin_popcount() builtin function
      is used instead.
      d12a68d4
    • antirez's avatar
      BITCOUNT refactoring. · 7ffa248c
      antirez authored
      The low level popualtion counting function is now separated from the
      BITCOUNT command implementation, so that the low level function can be
      further optimized and eventually used in other contexts if needed.
      7ffa248c
    • antirez's avatar
      Bit-related string operations moved to bitop.c · 84ec6706
      antirez authored
      All the general string operations are implemented in t_string.c, however
      the bit operations, while targeting the string type, are better served
      in a specific file where we have the implementations of the following
      four commands and helper functions:
      
          GETBIT
          SETBIT
          BITOP
          BITCOUNT
      
      In the future this file will probably contain more code related to
      making the BITOP and BITCOUNT operations faster.
      84ec6706
    • antirez's avatar
      New commands: BITOP and BITCOUNT. · 4a789dec
      antirez authored
      The motivation for this new commands is to be search in the usage of
      Redis for real time statistics. See the article "Fast real time metrics
      using Redis".
      
      http://blog.getspool.com/2011/11/29/fast-easy-realtime-metrics-using-redis-bitmaps/
      
      In general Redis strings when used as bitmaps using the SETBIT/GETBIT
      command provide a very space-efficient and fast way to store statistics.
      For instance in a web application with users, every user can be
      associated with a key that shows every day in which the user visited the
      web service. This information can be really valuable to extract user
      behaviour information.
      
      With Redis bitmaps doing this is very simple just saying that a given
      day is 0 (the data the service was put online) and all the next days are
      1, 2, 3, and so forth. So with SETBIT it is possible to set the bit
      corresponding to the current day every time the user visits the site.
      
      It is possible to take the count of the bit sets on the run, this is
      extremely easy using a Lua script. However a fast bit count native
      operation can be useful, especially if it can operate on ranges, or when
      the string is small like in the case of days (even if you consider many
      years it is still extremely little data).
      
      For this reason BITOP was introduced. The command counts the number of
      bits set to 1 in a string, with optional range:
      
      BITCOUNT key [start end]
      
      The start/end parameters are similar to GETRANGE. If omitted the whole
      string is tested.
      
      Population counting is more useful when bit-level operations like AND,
      OR and XOR are avaialble. For instance I can test multiple users to see
      the number of days three users visited the site at the same time. To do
      this we can take the AND of all the bitmaps, and then count the set bits.
      
      For this reason the BITOP command was introduced:
      
      BITOP [AND|OR|XOR|NOT] dest_key src_key1 src_key2 src_key3 ... src_keyN
      
      In the special case of NOT (that inverts the bits) only one source key
      can be passed.
      
      The judicious use of BITCOUNT and BITOP combined can lead to interesting
      use cases with very space efficient representation of data.
      
      The implementation provided is still not tested and optimized for speed,
      next commits will introduce unit tests. Later the implementation will be
      profiled to see if it is possible to gain an important amount of speed
      without making the code much more complex.
      4a789dec
    • antirez's avatar
      Add aof_rewrite_buffer_length INFO field. · bec74b1b
      antirez authored
      The INFO output, persistence section, already contained the field
      describing the size of the current AOF buffer to flush on disk. However
      the other AOF buffer, used to accumulate changes during an AOF rewrite,
      was not mentioned in the INFO output.
      
      This commit introduces a new field called aof_rewrite_buffer_length with
      the length of the rewrite buffer.
      bec74b1b
    • antirez's avatar
      Allow an AOF rewrite buffer > 2GB (Fix for issue #504). · edb95253
      antirez authored
      During the AOF rewrite process, the parent process needs to accumulate
      the new writes in an in-memory buffer: when the child will terminate the
      AOF rewriting process this buffer (that ist the difference between the
      dataset when the rewrite was started, and the current dataset) is
      flushed to the new AOF file.
      
      We used to implement this buffer using an sds.c string, but sds.c has a
      2GB limit. Sometimes the dataset can be big enough, the amount of writes
      so high, and the rewrite process slow enough that we overflow the 2GB
      limit, causing a crash, documented on github by issue #504.
      
      In order to prevent this from happening, this commit introduces a new
      system to accumulate writes, implemented by a linked list of blocks of
      10 MB each, so that we also avoid paying the reallocation cost.
      
      Note that theoretically modern operating systems may implement realloc()
      simply as a remaping of the old pages, thus with very good performances,
      see for instance the mremap() syscall on Linux. However this is not
      always true, and jemalloc by default avoids doing this because there are
      issues with the current implementation of mremap().
      
      For this reason we are using a linked list of blocks instead of a single
      block that gets reallocated again and again.
      
      The changes in this commit lacks testing, that will be performed before
      merging into the unstable branch. This fix will not enter 2.4 because it
      is too invasive. However 2.4 will log a warning when the AOF rewrite
      buffer is near to the 2GB limit.
      edb95253
    • antirez's avatar
      Dead code removed from replication.c. · 8152d0c0
      antirez authored
      The user @jokea noticed that the following line of code into
      replication.c made little sense:
      
          addReplySds(slave,sdsempty());
      
      Investigating a bit I found that this was introduced by commit 6208b3a7
      three years ago in the early stages of Redis. The code apparently is not
      useful at all, so I'm removing it.
      
      This change will not be backported into 2.4 so that in the rare case
      this should introduce a bug, we'll have a chance to detect it into the
      development branch. However following the code path it seems like the
      code is not useful at all, so the risk is truly small.
      8152d0c0
  10. 23 May, 2012 3 commits
    • antirez's avatar
      Use comments to split aof.c into sections. · 27fc5bf5
      antirez authored
      This makes the code more readable, it is still not the case to split the
      file itself into three different files, but the logical separation
      improves the readability especially since new commits are going to
      introduce an additional section.
      27fc5bf5
    • jokea's avatar
    • antirez's avatar
      Fixed issue #516 (ZINTERSTORE mixing sets and zsets). · 4dada1b5
      antirez authored
      Weeks ago trying to fix an harmless GCC warning I introduced a bug in
      the ziplist-encoded implementations of sorted sets.
      
      The bug completely broke zuiNext() iterator, that is used in the
      ZINTERSTORE and ZUNIONSTORE implementation, so those two commands are no
      longer reliable starting from Redis version 2.4.12 and latest 2.6.0-RC
      releases.
      
      This commit fixes the problem and adds a regression test.
      4dada1b5
  11. 16 May, 2012 1 commit
  12. 14 May, 2012 7 commits
    • Pieter Noordhuis's avatar
      Whitespace · d318803f
      Pieter Noordhuis authored
      d318803f
    • Dave Pacheco's avatar
      use port_getn instead of port_get · 72f30bcd
      Dave Pacheco authored
      72f30bcd
    • Dave Pacheco's avatar
      first cut at event port support · 2aa1efb8
      Dave Pacheco authored
      2aa1efb8
    • antirez's avatar
      Added time.h include in redis-cli. · e67d014d
      antirez authored
      redis-cli.c uses the time() function to seed the PRNG, but time.h was
      not included. This was not noticed since sys/time.h is included and was
      enough in most systems (but not correct). With Ubuntu 12.04 GCC
      generates a warning that made us aware of the issue.
      e67d014d
    • antirez's avatar
      activeExpireCycle(): better precision in max time used. · eee68054
      antirez authored
      activeExpireCycle() can consume no more than a few milliseconds per
      iteration. This commit improves the precision of the check for the time
      elapsed in two ways:
      
      1) We check every 16 iterations instead of the main loop instead of 256.
      2) We reset iterations at the start of the function and not every time
         we switch to the next database, so the check is correctly performed
         every 16 iterations.
      eee68054
    • antirez's avatar
      Impovements for: Redis timer, hashes rehashing, keys collection. · a8a981a8
      antirez authored
      A previous commit introduced REDIS_HZ define that changes the frequency
      of calls to the serverCron() Redis function. This commit improves
      different related things:
      
      1) Software watchdog: now the minimal period can be set according to
      REDIS_HZ. The minimal period is two times the timer period, that is:
      
          (1000/REDIS_HZ)*2 milliseconds
      
      2) The incremental rehashing is now performed in the expires dictionary
      as well.
      
      3) The activeExpireCycle() function was improved in different ways:
      
      - Now it checks if it already used too much time using microseconds
        instead of milliseconds for better precision.
      - The time limit is now calculated correctly, in the previous version
        the division was performed before of the multiplication resulting in
        a timelimit of 0 if HZ was big enough.
      - Databases with less than 1% of buckets fill in the hash table are
        skipped, because getting random keys is too expensive in this
        condition.
      
      4) tryResizeHashTables() is now called at every timer call, we need to
         match the number of calls we do to the expired keys colleciton cycle.
      
      5) REDIS_HZ was raised to 100.
      a8a981a8
    • antirez's avatar
      Redis timer interrupt frequency configurable as REDIS_HZ. · f7f2b261
      antirez authored
      Redis uses a function called serverCron() that is very similar to the
      timer interrupt of an operating system. This function is used to handle
      a number of asynchronous things, like active expired keys collection,
      clients timeouts, update of statistics, things related to the cluster
      and replication, triggering of BGSAVE and AOF rewrite process, and so
      forth.
      
      In the past the timer was called 1 time per second. At some point it was
      raised to 10 times per second, but it still was fixed and could not be
      changed even at compile time, because different functions called from
      serverCron() assumed a given fixed frequency.
      
      This commmit makes the frequency configurable, so that it is simpler to
      pick a good tradeoff between overhead of this function (that is usually
      very small) and the responsiveness of Redis during a few critical
      circumstances where a lot of work is done inside the timer.
      
      An example of such a critical condition is mass-expire of a lot of keys
      in the same second. Up to a given percentage of CPU time is used to
      perform expired keys collection per expire cylce. Now changing the
      REDIS_HZ macro it is possible to do less work but more times per second
      in order to block the server for less time.
      
      If this patch will work well in our tests it will enter Redis 2.6-final.
      f7f2b261
  13. 12 May, 2012 5 commits
  14. 09 May, 2012 1 commit