Init commit.HEADmaster

29 files changed, 1832 insertions, 0 deletions

diff --git a/utils/build-static-symbols.tcl b/utils/build-static-symbols.tcl
new file mode 100644
index 0000000..e634cbe
--- /dev/null
+++ b/utils/build-static-symbols.tcl
@@ -0,0 +1,22 @@
+# Build a symbol table for static symbols of redis.c
+# Useful to get stack traces on segfault without a debugger. See redis.c
+# for more information.
+#
+# Copyright(C) 2009 Salvatore Sanfilippo, under the BSD license.
+
+set fd [open redis.c]
+set symlist {}
+while {[gets $fd line] != -1} {
+    if {[regexp {^static +[A-z0-9]+[ *]+([A-z0-9]*)\(} $line - sym]} {
+        lappend symlist $sym
+    }
+}
+set symlist [lsort -unique $symlist]
+puts "static struct redisFunctionSym symsTable\[\] = {"
+foreach sym $symlist {
+    puts "{\"$sym\",(unsigned long)$sym},"
+}
+puts "{NULL,0}"
+puts "};"
+
+close $fd
diff --git a/utils/cluster_fail_time.tcl b/utils/cluster_fail_time.tcl
new file mode 100644
index 0000000..8739949
--- /dev/null
+++ b/utils/cluster_fail_time.tcl
@@ -0,0 +1,50 @@
+# This simple script is used in order to estimate the average PFAIL->FAIL
+# state switch after a failure.
+
+set ::sleep_time 10     ; # How much to sleep to trigger PFAIL.
+set ::fail_port 30016   ; # Node to put in sleep.
+set ::other_port 30001  ; # Node to use to monitor the flag switch.
+
+proc avg vector {
+    set sum 0.0
+    foreach x $vector {
+        set sum [expr {$sum+$x}]
+    }
+    expr {$sum/[llength $vector]}
+}
+
+set samples {}
+while 1 {
+    exec redis-cli -p $::fail_port debug sleep $::sleep_time > /dev/null &
+
+    # Wait for fail? to appear.
+    while 1 {
+        set output [exec redis-cli -p $::other_port cluster nodes]
+        if {[string match {*fail\?*} $output]} break
+        after 100
+    }
+
+    puts "FAIL?"
+    set start [clock milliseconds]
+
+    # Wait for fail? to disappear.
+    while 1 {
+        set output [exec redis-cli -p $::other_port cluster nodes]
+        if {![string match {*fail\?*} $output]} break
+        after 100
+    }
+
+    puts "FAIL"
+    set now [clock milliseconds]
+    set elapsed [expr {$now-$start}]
+    puts $elapsed
+    lappend samples $elapsed
+
+    puts "AVG([llength $samples]): [avg $samples]"
+
+    # Wait for the instance to be available again.
+    exec redis-cli -p $::fail_port ping
+
+    # Wait for the fail flag to be cleared.
+    after 2000
+}
diff --git a/utils/corrupt_rdb.c b/utils/corrupt_rdb.c
new file mode 100644
index 0000000..7ba9cae
--- /dev/null
+++ b/utils/corrupt_rdb.c
@@ -0,0 +1,44 @@
+/* Trivia program to corrupt an RDB file in order to check the RDB check
+ * program behavior and effectiveness.
+ *
+ * Copyright (C) 2016 Salvatore Sanfilippo.
+ * This software is released in the 3-clause BSD license. */
+
+#include <stdio.h>
+#include <fcntl.h>
+#include <sys/stat.h>
+#include <stdlib.h>
+#include <unistd.h>
+#include <time.h>
+
+int main(int argc, char **argv) {
+    struct stat stat;
+    int fd, cycles;
+
+    if (argc != 3) {
+        fprintf(stderr,"Usage: <filename> <cycles>\n");
+        exit(1);
+    }
+
+    srand(time(NULL));
+    cycles = atoi(argv[2]);
+    fd = open("dump.rdb",O_RDWR);
+    if (fd == -1) {
+        perror("open");
+        exit(1);
+    }
+    fstat(fd,&stat);
+
+    while(cycles--) {
+        unsigned char buf[32];
+        unsigned long offset = rand()%stat.st_size;
+        int writelen = 1+rand()%31;
+        int j;
+
+        for (j = 0; j < writelen; j++) buf[j] = (char)rand();
+        lseek(fd,offset,SEEK_SET);
+        printf("Writing %d bytes at offset %lu\n", writelen, offset);
+        write(fd,buf,writelen);
+    }
+    return 0;
+}
diff --git a/utils/create-cluster/.gitignore b/utils/create-cluster/.gitignore
new file mode 100644
index 0000000..2988ee9
--- /dev/null
+++ b/utils/create-cluster/.gitignore
@@ -0,0 +1,5 @@
+config.sh
+*.rdb
+*.aof
+*.conf
+*.log
diff --git a/utils/create-cluster/README b/utils/create-cluster/README
new file mode 100644
index 0000000..1f43748
--- /dev/null
+++ b/utils/create-cluster/README
@@ -0,0 +1,27 @@
+Create-custer is a small script used to easily start a big number of Redis
+instances configured to run in cluster mode. Its main goal is to allow manual
+testing in a condition which is not easy to replicate with the Redis cluster
+unit tests, for example when a lot of instances are needed in order to trigger
+a give bug.
+
+The tool can also be used just to easily create a number of instances in a
+Redis Cluster in order to experiment a bit with the system.
+
+USAGE
+---
+
+To create a cluster, follow this steps:
+
+1. Edit create-cluster and change the start / end port, depending on the
+number of instances you want to create.
+2. Use "./create-cluster start" in order to run the instances.
+3. Use "./create-cluster create" in order to execute redis-trib create, so that
+an actual Redis cluster will be created.
+4. Now you are ready to play with the cluster. AOF files and logs for each instances are created in the current directory.
+
+In order to stop a cluster:
+
+1. Use "./craete-cluster stop" to stop all the instances. After you stopped the instances you can use "./create-cluster start" to restart them if you change ideas.
+2. Use "./create-cluster clean" to remove all the AOF / log files to restat with a clean environment.
+
+Use the command "./create-cluster help" to get the full list of features.
diff --git a/utils/create-cluster/create-cluster b/utils/create-cluster/create-cluster
new file mode 100644
index 0000000..9894149
--- /dev/null
+++ b/utils/create-cluster/create-cluster
@@ -0,0 +1,95 @@
+#!/bin/bash
+
+# Settings
+PORT=30000
+TIMEOUT=2000
+NODES=6
+REPLICAS=1
+
+# You may want to put the above config parameters into config.sh in order to
+# override the defaults without modifying this script.
+
+if [ -a config.sh ]
+then
+    source "config.sh"
+fi
+
+# Computed vars
+ENDPORT=$((PORT+NODES))
+
+if [ "$1" == "start" ]
+then
+    while [ $((PORT < ENDPORT)) != "0" ]; do
+        PORT=$((PORT+1))
+        echo "Starting $PORT"
+        ../../src/redis-server --port $PORT --cluster-enabled yes --cluster-config-file nodes-${PORT}.conf --cluster-node-timeout $TIMEOUT --appendonly yes --appendfilename appendonly-${PORT}.aof --dbfilename dump-${PORT}.rdb --logfile ${PORT}.log --daemonize yes
+    done
+    exit 0
+fi
+
+if [ "$1" == "create" ]
+then
+    HOSTS=""
+    while [ $((PORT < ENDPORT)) != "0" ]; do
+        PORT=$((PORT+1))
+        HOSTS="$HOSTS 127.0.0.1:$PORT"
+    done
+    ../../src/redis-trib.rb create --replicas $REPLICAS $HOSTS
+    exit 0
+fi
+
+if [ "$1" == "stop" ]
+then
+    while [ $((PORT < ENDPORT)) != "0" ]; do
+        PORT=$((PORT+1))
+        echo "Stopping $PORT"
+        ../../src/redis-cli -p $PORT shutdown nosave
+    done
+    exit 0
+fi
+
+if [ "$1" == "watch" ]
+then
+    PORT=$((PORT+1))
+    while [ 1 ]; do
+        clear
+        date
+        ../../src/redis-cli -p $PORT cluster nodes | head -30
+        sleep 1
+    done
+    exit 0
+fi
+
+if [ "$1" == "tail" ]
+then
+    INSTANCE=$2
+    PORT=$((PORT+INSTANCE))
+    tail -f ${PORT}.log
+    exit 0
+fi
+
+if [ "$1" == "call" ]
+then
+    while [ $((PORT < ENDPORT)) != "0" ]; do
+        PORT=$((PORT+1))
+        ../../src/redis-cli -p $PORT $2 $3 $4 $5 $6 $7 $8 $9
+    done
+    exit 0
+fi
+
+if [ "$1" == "clean" ]
+then
+    rm -rf *.log
+    rm -rf appendonly*.aof
+    rm -rf dump*.rdb
+    rm -rf nodes*.conf
+    exit 0
+fi
+
+echo "Usage: $0 [start|create|stop|watch|tail|clean]"
+echo "start       -- Launch Redis Cluster instances."
+echo "create      -- Create a cluster using redis-trib create."
+echo "stop        -- Stop Redis Cluster instances."
+echo "watch       -- Show CLUSTER NODES output (first 30 lines) of first node."
+echo "tail <id>   -- Run tail -f of instance at base port + ID."
+echo "clean       -- Remove all instances data, logs, configs."
diff --git a/utils/generate-command-help.rb b/utils/generate-command-help.rb
new file mode 100644
index 0000000..f3dfb31
--- /dev/null
+++ b/utils/generate-command-help.rb
@@ -0,0 +1,116 @@
+#!/usr/bin/env ruby
+
+GROUPS = [
+  "generic",
+  "string",
+  "list",
+  "set",
+  "sorted_set",
+  "hash",
+  "pubsub",
+  "transactions",
+  "connection",
+  "server",
+  "scripting",
+  "hyperloglog",
+  "cluster",
+  "geo"
+].freeze
+
+GROUPS_BY_NAME = Hash[*
+  GROUPS.each_with_index.map do |n,i|
+    [n,i]
+  end.flatten
+].freeze
+
+def argument arg
+  name = arg["name"].is_a?(Array) ? arg["name"].join(" ") : arg["name"]
+  name = arg["enum"].join "|" if "enum" == arg["type"]
+  name = arg["command"] + " " + name if arg["command"]
+  if arg["multiple"]
+    name = "#{name} [#{name} ...]"
+  end
+  if arg["optional"]
+    name = "[#{name}]"
+  end
+  name
+end
+
+def arguments command
+  return "-" unless command["arguments"]
+  command["arguments"].map do |arg|
+    argument arg
+  end.join " "
+end
+
+def commands
+  return @commands if @commands
+
+  require "rubygems"
+  require "net/http"
+  require "net/https"
+  require "json"
+  require "uri"
+
+  url = URI.parse "https://raw.githubusercontent.com/antirez/redis-doc/master/commands.json"
+  client = Net::HTTP.new url.host, url.port
+  client.use_ssl = true
+  response = client.get url.path
+  if response.is_a?(Net::HTTPSuccess)
+    @commands = JSON.parse(response.body)
+  else
+    response.error!
+  end
+end
+
+def generate_groups
+  GROUPS.map do |n|
+    "\"#{n}\""
+  end.join(",\n    ");
+end
+
+def generate_commands
+  commands.to_a.sort do |x,y|
+    x[0] <=> y[0]
+  end.map do |key, command|
+    group = GROUPS_BY_NAME[command["group"]]
+    if group.nil?
+      STDERR.puts "Please update groups array in #{__FILE__}"
+      raise "Unknown group #{command["group"]}"
+    end
+
+    ret = <<-SPEC
+{ "#{key}",
+    "#{arguments(command)}",
+    "#{command["summary"]}",
+    #{group},
+    "#{command["since"]}" }
+    SPEC
+    ret.strip
+  end.join(",\n    ")
+end
+
+# Write to stdout
+puts <<-HELP_H
+/* Automatically generated by #{__FILE__}, do not edit. */
+
+#ifndef __REDIS_HELP_H
+#define __REDIS_HELP_H
+
+static char *commandGroups[] = {
+    #{generate_groups}
+};
+
+struct commandHelp {
+  char *name;
+  char *params;
+  char *summary;
+  int group;
+  char *since;
+} commandHelp[] = {
+    #{generate_commands}
+};
+
+#endif
+HELP_H
+
diff --git a/utils/graphs/commits-over-time/README.md b/utils/graphs/commits-over-time/README.md
new file mode 100644
index 0000000..b28019e
--- /dev/null
+++ b/utils/graphs/commits-over-time/README.md
@@ -0,0 +1,16 @@
+This Tcl script is what I used in order to generate the graph you
+can find at http://antirez.com/news/98. It's really quick & dirty, more
+a trow away program than anything else, but probably could be reused or
+modified in the future in order to visualize other similar data or an
+updated version of the same data.
+
+The usage is trivial:
+
+    ./genhtml.tcl > output.html
+
+The generated HTML is quite broken but good enough to grab a screenshot
+from the browser. Feel free to improve it if you got time / interest.
+
+Note that the code filtering the tags, and the hardcoded branch name, does
+not make the script, as it is, able to analyze a different repository.
+However the changes needed are trivial.
diff --git a/utils/graphs/commits-over-time/genhtml.tcl b/utils/graphs/commits-over-time/genhtml.tcl
new file mode 100644
index 0000000..c4b4e09
--- /dev/null
+++ b/utils/graphs/commits-over-time/genhtml.tcl
@@ -0,0 +1,96 @@
+#!/usr/bin/env tclsh
+
+# Load commits history as "sha1 unixtime".
+set commits [exec git log unstable {--pretty="%H %at"}]
+set raw_tags [exec git tag]
+
+# Load all the tags that are about stable releases.
+foreach tag $raw_tags {
+    if {[string match v*-stable $tag]} {
+        set tag [string range $tag 1 end-7]
+        puts $tag
+    }
+    if {[regexp {^[0-9]+.[0-9]+.[0-9]+$} $tag]} {
+        lappend tags $tag
+    }
+}
+
+# For each tag, create a list of "name unixtime"
+foreach tag $tags {
+    set taginfo [exec git log $tag -n 1 "--pretty=\"$tag %at\""]
+    set taginfo [string trim $taginfo {"}]
+    lappend labels $taginfo
+}
+
+# For each commit, check the amount of code changed and create an array
+# mapping the commit to the number of lines affected.
+foreach c $commits {
+    set stat [exec git show --oneline --numstat [lindex $c 0]]
+    set linenum 0
+    set affected 0
+    foreach line [split $stat "\n"] {
+        incr linenum
+        if {$linenum == 1 || [string match *deps/* $line]} continue
+        if {[catch {llength $line} numfields]} continue
+        if {$numfields == 0} continue
+        catch {
+            incr affected [lindex $line 0]
+            incr affected [lindex $line 1]
+        }
+    }
+    set commit_to_affected([lindex $c 0]) $affected
+}
+
+set base_time [lindex [lindex $commits end] 1]
+puts [clock format $base_time]
+
+# Generate a graph made of HTML DIVs.
+puts {<html>
+<style>
+.box {
+    position:absolute;
+    width:10px;
+    height:5px;
+    border:1px black solid;
+    background-color:#44aa33;
+    opacity: 0.04;
+}
+.label {
+    position:absolute;
+    background-color:#dddddd;
+    font-family:helvetica;
+    font-size:12px;
+    padding:2px;
+    color:#666;
+    border:1px #aaa solid;
+    border-radius: 5px;
+}
+#outer {
+    position:relative;
+    width:1500;
+    height:500;
+    border:1px #aaa solid;
+}
+</style>
+<div id="outer">
+}
+foreach c $commits {
+    set sha [lindex $c 0]
+    set t [expr {([lindex $c 1]-$base_time)/(3600*24*2)}]
+    set affected [expr $commit_to_affected($sha)]
+    set left $t
+    set height [expr {log($affected)*20}]
+    puts "<div class=\"box\" style=\"left:$left; bottom:0; height:$height\"></div>"
+}
+
+set bottom -30
+foreach l $labels {
+    set name [lindex $l 0]
+    set t [expr {([lindex $l 1]-$base_time)/(3600*24*2)}]
+    set left $t
+    if {$left < 0} continue
+    incr bottom -20
+    if  {$bottom == -210} {set bottom -30}
+    puts "<div class=\"label\" style=\"left:$left; bottom:$bottom\">$name</div>"
+}
+puts {</div></html>}
diff --git a/utils/hashtable/README b/utils/hashtable/README
new file mode 100644
index 0000000..e2862f0
--- /dev/null
+++ b/utils/hashtable/README
@@ -0,0 +1,13 @@
+Hash table implementation related utilities.
+
+rehashing.c
+---
+
+Visually show buckets in the two hash tables between rehashings. Also stress
+test getRandomKeys() implementation, that may actually disappear from
+Redis soon, however visualizaiton some code is reusable in new bugs
+investigation.
+
+Compile with:
+
+    cc -I ../../src/ rehashing.c ../../src/zmalloc.c ../../src/dict.c -o rehashing_test
diff --git a/utils/hashtable/rehashing.c b/utils/hashtable/rehashing.c
new file mode 100644
index 0000000..b57a904
--- /dev/null
+++ b/utils/hashtable/rehashing.c
@@ -0,0 +1,142 @@
+#include "redis.h"
+#include "dict.h"
+
+void _redisAssert(char *x, char *y, int l) {
+    printf("ASSERT: %s %s %d\n",x,y,l);
+    exit(1);
+}
+
+unsigned int dictKeyHash(const void *keyp) {
+    unsigned long key = (unsigned long)keyp;
+    key = dictGenHashFunction(&key,sizeof(key));
+    key += ~(key << 15);
+    key ^=  (key >> 10);
+    key +=  (key << 3);
+    key ^=  (key >> 6);
+    key += ~(key << 11);
+    key ^=  (key >> 16);
+    return key;
+}
+
+int dictKeyCompare(void *privdata, const void *key1, const void *key2) {
+    unsigned long k1 = (unsigned long)key1;
+    unsigned long k2 = (unsigned long)key2;
+    return k1 == k2;
+}
+
+dictType dictTypeTest = {
+    dictKeyHash,                   /* hash function */
+    NULL,                          /* key dup */
+    NULL,                          /* val dup */
+    dictKeyCompare,                /* key compare */
+    NULL,                          /* key destructor */
+    NULL                           /* val destructor */
+};
+
+void showBuckets(dictht ht) {
+    if (ht.table == NULL) {
+        printf("NULL\n");
+    } else {
+        int j;
+        for (j = 0; j < ht.size; j++) {
+            printf("%c", ht.table[j] ? '1' : '0');
+        }
+        printf("\n");
+    }
+}
+
+void show(dict *d) {
+    int j;
+    if (d->rehashidx != -1) {
+        printf("rhidx: ");
+        for (j = 0; j < d->rehashidx; j++)
+            printf(".");
+        printf("|\n");
+    }
+    printf("ht[0]: ");
+    showBuckets(d->ht[0]);
+    printf("ht[1]: ");
+    showBuckets(d->ht[1]);
+    printf("\n");
+}
+
+int sortPointers(const void *a, const void *b) {
+    unsigned long la, lb;
+
+    la = (long) (*((dictEntry**)a));
+    lb = (long) (*((dictEntry**)b));
+    return la-lb;
+}
+
+void stressGetKeys(dict *d, int times, int *perfect_run, int *approx_run) {
+    int j;
+
+    dictEntry **des = zmalloc(sizeof(dictEntry*)*dictSize(d));
+    for (j = 0; j < times; j++) {
+        int requested = rand() % (dictSize(d)+1);
+        int returned = dictGetSomeKeys(d, des, requested);
+        int dup = 0;
+
+        qsort(des,returned,sizeof(dictEntry*),sortPointers);
+        if (returned > 1) {
+            int i;
+            for (i = 0; i < returned-1; i++) {
+                if (des[i] == des[i+1]) dup++;
+            }
+        }
+
+        if (requested == returned && dup == 0) {
+            (*perfect_run)++;
+        } else {
+            (*approx_run)++;
+            printf("Requested, returned, duplicated: %d %d %d\n",
+                requested, returned, dup);
+        }
+    }
+    zfree(des);
+}
+
+#define MAX1 120
+#define MAX2 1000
+int main(void) {
+    dict *d = dictCreate(&dictTypeTest,NULL);
+    unsigned long i;
+    srand(time(NULL));
+
+    for (i = 0; i < MAX1; i++) {
+        dictAdd(d,(void*)i,NULL);
+        show(d);
+    }
+    printf("Size: %d\n", (int)dictSize(d));
+
+    for (i = 0; i < MAX1; i++) {
+        dictDelete(d,(void*)i);
+        dictResize(d);
+        show(d);
+    }
+    dictRelease(d);
+
+    d = dictCreate(&dictTypeTest,NULL);
+
+    printf("Stress testing dictGetSomeKeys\n");
+    int perfect_run = 0, approx_run = 0;
+
+    for (i = 0; i < MAX2; i++) {
+        dictAdd(d,(void*)i,NULL);
+        stressGetKeys(d,100,&perfect_run,&approx_run);
+    }
+
+    for (i = 0; i < MAX2; i++) {
+        dictDelete(d,(void*)i);
+        dictResize(d);
+        stressGetKeys(d,100,&perfect_run,&approx_run);
+    }
+
+    printf("dictGetSomeKey, %d perfect runs, %d approximated runs\n",
+        perfect_run, approx_run);
+
+    dictRelease(d);
+
+    printf("TEST PASSED!\n");
+    return 0;
+}
diff --git a/utils/hyperloglog/.gitignore b/utils/hyperloglog/.gitignore
new file mode 100644
index 0000000..2211df6
--- /dev/null
+++ b/utils/hyperloglog/.gitignore
@@ -0,0 +1 @@
+*.txt
diff --git a/utils/hyperloglog/hll-err.rb b/utils/hyperloglog/hll-err.rb
new file mode 100644
index 0000000..75bb8e4
--- /dev/null
+++ b/utils/hyperloglog/hll-err.rb
@@ -0,0 +1,27 @@
+# hll-err.rb - Copyright (C) 2014 Salvatore Sanfilippo
+# BSD license, See the COPYING file for more information.
+#
+# Check error of HyperLogLog Redis implementation for different set sizes.
+
+require 'rubygems'
+require 'redis'
+require 'digest/sha1'
+
+r = Redis.new
+r.del('hll')
+i = 0
+while true do
+    100.times {
+        elements = []
+        1000.times {
+            ele = Digest::SHA1.hexdigest(i.to_s)
+            elements << ele
+            i += 1
+        }
+        r.pfadd('hll',*elements)
+    }
+    approx = r.pfcount('hll')
+    abs_err = (approx-i).abs
+    rel_err = 100.to_f*abs_err/i
+    puts "#{i} vs #{approx}: #{rel_err}%"
+end
diff --git a/utils/hyperloglog/hll-gnuplot-graph.rb b/utils/hyperloglog/hll-gnuplot-graph.rb
new file mode 100644
index 0000000..6c7596d
--- /dev/null
+++ b/utils/hyperloglog/hll-gnuplot-graph.rb
@@ -0,0 +1,88 @@
+# hll-err.rb - Copyright (C) 2014 Salvatore Sanfilippo
+# BSD license, See the COPYING file for more information.
+#
+# This program is suited to output average and maximum errors of
+# the Redis HyperLogLog implementation in a format suitable to print
+# graphs using gnuplot.
+
+require 'rubygems'
+require 'redis'
+require 'digest/sha1'
+
+# Generate an array of [cardinality,relative_error] pairs
+# in the 0 - max range, with the specified step.
+#
+# 'r' is the Redis object used to perform the queries.
+# 'seed' must be different every time you want a test performed
+# with a different set. The function guarantees that if 'seed' is the
+# same, exactly the same dataset is used, and when it is different,
+# a totally unrelated different data set is used (without any common
+# element in practice).
+def run_experiment(r,seed,max,step)
+    r.del('hll')
+    i = 0
+    samples = []
+    step = 1000 if step > 1000
+    while i < max do
+        elements = []
+        step.times {
+            ele = Digest::SHA1.hexdigest(i.to_s+seed.to_s)
+            elements << ele
+            i += 1
+        }
+        r.pfadd('hll',elements)
+        approx = r.pfcount('hll')
+        err = approx-i
+        rel_err = 100.to_f*err/i
+        samples << [i,rel_err]
+    end
+    samples
+end
+
+def filter_samples(numsets,max,step,filter)
+    r = Redis.new
+    dataset = {}
+    (0...numsets).each{|i|
+        dataset[i] = run_experiment(r,i,max,step)
+        STDERR.puts "Set #{i}"
+    }
+    dataset[0].each_with_index{|ele,index|
+        if filter == :max
+            card=ele[0]
+            err=ele[1].abs
+            (1...numsets).each{|i|
+                err = dataset[i][index][1] if err < dataset[i][index][1]
+            }
+            puts "#{card} #{err}"
+        elsif filter == :avg
+            card=ele[0]
+            err = 0
+            (0...numsets).each{|i|
+                err += dataset[i][index][1]
+            }
+            err /= numsets
+            puts "#{card} #{err}"
+        elsif filter == :absavg
+            card=ele[0]
+            err = 0
+            (0...numsets).each{|i|
+                err += dataset[i][index][1].abs
+            }
+            err /= numsets
+            puts "#{card} #{err}"
+        elsif filter == :all
+            (0...numsets).each{|i|
+                card,err = dataset[i][index]
+                puts "#{card} #{err}"
+            }
+        else
+            raise "Unknown filter #{filter}"
+        end
+    }
+end
+
+if ARGV.length != 4
+    puts "Usage: hll-gnuplot-graph <samples> <max> <step> (max|avg|absavg|all)"
+    exit 1
+end
+filter_samples(ARGV[0].to_i,ARGV[1].to_i,ARGV[2].to_i,ARGV[3].to_sym)
diff --git a/utils/install_server.sh b/utils/install_server.sh
new file mode 100644
index 0000000..3d920a1
--- /dev/null
+++ b/utils/install_server.sh
@@ -0,0 +1,278 @@
+#!/bin/sh
+
+# Copyright 2011 Dvir Volk <dvirsk at gmail dot com>. All rights reserved.
+#
+# Redistribution and use in source and binary forms, with or without
+# modification, are permitted provided that the following conditions are met:
+#
+#   1. Redistributions of source code must retain the above copyright notice,
+#   this list of conditions and the following disclaimer.
+#
+#   2. Redistributions in binary form must reproduce the above copyright
+#   notice, this list of conditions and the following disclaimer in the
+#   documentation and/or other materials provided with the distribution.
+#
+# THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
+# WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+# MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
+# EVENT SHALL Dvir Volk OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+# INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
+# OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+# LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+# NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
+# EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+#
+################################################################################
+#
+# Service installer for redis server, runs interactively by default.
+#
+# To run this script non-interactively (for automation/provisioning purposes),
+# feed the variables into the script. Any missing variables will be prompted!
+# Tip: Environment variables also support command substitution (see REDIS_EXECUTABLE)
+#
+# Example:
+#
+# sudo REDIS_PORT=1234 \
+# 		 REDIS_CONFIG_FILE=/etc/redis/1234.conf \
+# 		 REDIS_LOG_FILE=/var/log/redis_1234.log \
+# 		 REDIS_DATA_DIR=/var/lib/redis/1234 \
+# 		 REDIS_EXECUTABLE=`command -v redis-server` ./utils/install_server.sh
+#
+# This generates a redis config file and an /etc/init.d script, and installs them.
+#
+# /!\ This script should be run as root
+#
+################################################################################
+
+die () {
+	echo "ERROR: $1. Aborting!"
+	exit 1
+}
+
+
+#Absolute path to this script
+SCRIPT=$(readlink -f $0)
+#Absolute path this script is in
+SCRIPTPATH=$(dirname $SCRIPT)
+
+#Initial defaults
+_REDIS_PORT=6379
+_MANUAL_EXECUTION=false
+
+echo "Welcome to the redis service installer"
+echo "This script will help you easily set up a running redis server"
+echo
+
+#check for root user
+if [ "$(id -u)" -ne 0 ] ; then
+	echo "You must run this script as root. Sorry!"
+	exit 1
+fi
+
+if ! echo $REDIS_PORT | egrep -q '^[0-9]+$' ; then
+	_MANUAL_EXECUTION=true
+	#Read the redis port
+	read  -p "Please select the redis port for this instance: [$_REDIS_PORT] " REDIS_PORT
+	if ! echo $REDIS_PORT | egrep -q '^[0-9]+$' ; then
+		echo "Selecting default: $_REDIS_PORT"
+		REDIS_PORT=$_REDIS_PORT
+	fi
+fi
+
+if [ -z "$REDIS_CONFIG_FILE" ] ; then
+	_MANUAL_EXECUTION=true
+	#read the redis config file
+	_REDIS_CONFIG_FILE="/etc/redis/$REDIS_PORT.conf"
+	read -p "Please select the redis config file name [$_REDIS_CONFIG_FILE] " REDIS_CONFIG_FILE
+	if [ -z "$REDIS_CONFIG_FILE" ] ; then
+		REDIS_CONFIG_FILE=$_REDIS_CONFIG_FILE
+		echo "Selected default - $REDIS_CONFIG_FILE"
+	fi
+fi
+
+if [ -z "$REDIS_LOG_FILE" ] ; then
+	_MANUAL_EXECUTION=true
+	#read the redis log file path
+	_REDIS_LOG_FILE="/var/log/redis_$REDIS_PORT.log"
+	read -p "Please select the redis log file name [$_REDIS_LOG_FILE] " REDIS_LOG_FILE
+	if [ -z "$REDIS_LOG_FILE" ] ; then
+		REDIS_LOG_FILE=$_REDIS_LOG_FILE
+		echo "Selected default - $REDIS_LOG_FILE"
+	fi
+fi
+
+if [ -z "$REDIS_DATA_DIR" ] ; then
+	_MANUAL_EXECUTION=true
+	#get the redis data directory
+	_REDIS_DATA_DIR="/var/lib/redis/$REDIS_PORT"
+	read -p "Please select the data directory for this instance [$_REDIS_DATA_DIR] " REDIS_DATA_DIR
+	if [ -z "$REDIS_DATA_DIR" ] ; then
+		REDIS_DATA_DIR=$_REDIS_DATA_DIR
+		echo "Selected default - $REDIS_DATA_DIR"
+	fi
+fi
+
+if [ ! -x "$REDIS_EXECUTABLE" ] ; then
+	_MANUAL_EXECUTION=true
+	#get the redis executable path
+	_REDIS_EXECUTABLE=`command -v redis-server`
+	read -p "Please select the redis executable path [$_REDIS_EXECUTABLE] " REDIS_EXECUTABLE
+	if [ ! -x "$REDIS_EXECUTABLE" ] ; then
+		REDIS_EXECUTABLE=$_REDIS_EXECUTABLE
+
+		if [ ! -x "$REDIS_EXECUTABLE" ] ; then
+			echo "Mmmmm...  it seems like you don't have a redis executable. Did you run make install yet?"
+			exit 1
+		fi
+	fi
+fi
+
+#check the default for redis cli
+CLI_EXEC=`command -v redis-cli`
+if [ -z "$CLI_EXEC" ] ; then
+	CLI_EXEC=`dirname $REDIS_EXECUTABLE`"/redis-cli"
+fi
+
+echo "Selected config:"
+
+echo "Port           : $REDIS_PORT"
+echo "Config file    : $REDIS_CONFIG_FILE"
+echo "Log file       : $REDIS_LOG_FILE"
+echo "Data dir       : $REDIS_DATA_DIR"
+echo "Executable     : $REDIS_EXECUTABLE"
+echo "Cli Executable : $CLI_EXEC"
+
+if $_MANUAL_EXECUTION == true ; then
+	read -p "Is this ok? Then press ENTER to go on or Ctrl-C to abort." _UNUSED_
+fi
+
+mkdir -p `dirname "$REDIS_CONFIG_FILE"` || die "Could not create redis config directory"
+mkdir -p `dirname "$REDIS_LOG_FILE"` || die "Could not create redis log dir"
+mkdir -p "$REDIS_DATA_DIR" || die "Could not create redis data directory"
+
+#render the templates
+TMP_FILE="/tmp/${REDIS_PORT}.conf"
+DEFAULT_CONFIG="${SCRIPTPATH}/../redis.conf"
+INIT_TPL_FILE="${SCRIPTPATH}/redis_init_script.tpl"
+INIT_SCRIPT_DEST="/etc/init.d/redis_${REDIS_PORT}"
+PIDFILE="/var/run/redis_${REDIS_PORT}.pid"
+
+if [ ! -f "$DEFAULT_CONFIG" ]; then
+	echo "Mmmmm... the default config is missing. Did you switch to the utils directory?"
+	exit 1
+fi
+
+#Generate config file from the default config file as template
+#changing only the stuff we're controlling from this script
+echo "## Generated by install_server.sh ##" > $TMP_FILE
+
+read -r SED_EXPR <<-EOF
+s#^port [0-9]{4}\$#port ${REDIS_PORT}#; \
+s#^logfile .+\$#logfile ${REDIS_LOG_FILE}#; \
+s#^dir .+\$#dir ${REDIS_DATA_DIR}#; \
+s#^pidfile .+\$#pidfile ${PIDFILE}#; \
+s#^daemonize no\$#daemonize yes#;
+EOF
+sed -r "$SED_EXPR" $DEFAULT_CONFIG  >> $TMP_FILE
+
+#cat $TPL_FILE | while read line; do eval "echo \"$line\"" >> $TMP_FILE; done
+cp $TMP_FILE $REDIS_CONFIG_FILE || die "Could not write redis config file $REDIS_CONFIG_FILE"
+
+#Generate sample script from template file
+rm -f $TMP_FILE
+
+#we hard code the configs here to avoid issues with templates containing env vars
+#kinda lame but works!
+REDIS_INIT_HEADER=\
+"#!/bin/sh\n
+#Configurations injected by install_server below....\n\n
+EXEC=$REDIS_EXECUTABLE\n
+CLIEXEC=$CLI_EXEC\n
+PIDFILE=\"$PIDFILE\"\n
+CONF=\"$REDIS_CONFIG_FILE\"\n\n
+REDISPORT=\"$REDIS_PORT\"\n\n
+###############\n\n"
+
+REDIS_CHKCONFIG_INFO=\
+"# REDHAT chkconfig header\n\n
+# chkconfig: - 58 74\n
+# description: redis_${REDIS_PORT} is the redis daemon.\n
+### BEGIN INIT INFO\n
+# Provides: redis_6379\n
+# Required-Start: \$network \$local_fs \$remote_fs\n
+# Required-Stop: \$network \$local_fs \$remote_fs\n
+# Default-Start: 2 3 4 5\n
+# Default-Stop: 0 1 6\n
+# Should-Start: \$syslog \$named\n
+# Should-Stop: \$syslog \$named\n
+# Short-Description: start and stop redis_${REDIS_PORT}\n
+# Description: Redis daemon\n
+### END INIT INFO\n\n"
+
+if command -v chkconfig >/dev/null; then
+	#if we're a box with chkconfig on it we want to include info for chkconfig
+	echo "$REDIS_INIT_HEADER" "$REDIS_CHKCONFIG_INFO" > $TMP_FILE && cat $INIT_TPL_FILE >> $TMP_FILE || die "Could not write init script to $TMP_FILE"
+else
+	#combine the header and the template (which is actually a static footer)
+	echo "$REDIS_INIT_HEADER" > $TMP_FILE && cat $INIT_TPL_FILE >> $TMP_FILE || die "Could not write init script to $TMP_FILE"
+fi
+
+###
+# Generate sample script from template file
+# - No need to check which system we are on. The init info are comments and
+#   do not interfere with update_rc.d systems. Additionally:
+#     Ubuntu/debian by default does not come with chkconfig, but does issue a
+#     warning if init info is not available.
+
+cat > ${TMP_FILE} <<EOT
+#!/bin/sh
+#Configurations injected by install_server below....
+
+EXEC=$REDIS_EXECUTABLE
+CLIEXEC=$CLI_EXEC
+PIDFILE=$PIDFILE
+CONF="$REDIS_CONFIG_FILE"
+REDISPORT="$REDIS_PORT"
+###############
+# SysV Init Information
+# chkconfig: - 58 74
+# description: redis_${REDIS_PORT} is the redis daemon.
+### BEGIN INIT INFO
+# Provides: redis_${REDIS_PORT}
+# Required-Start: \$network \$local_fs \$remote_fs
+# Required-Stop: \$network \$local_fs \$remote_fs
+# Default-Start: 2 3 4 5
+# Default-Stop: 0 1 6
+# Should-Start: \$syslog \$named
+# Should-Stop: \$syslog \$named
+# Short-Description: start and stop redis_${REDIS_PORT}
+# Description: Redis daemon
+### END INIT INFO
+
+EOT
+cat ${INIT_TPL_FILE} >> ${TMP_FILE}
+
+#copy to /etc/init.d
+cp $TMP_FILE $INIT_SCRIPT_DEST && \
+	chmod +x $INIT_SCRIPT_DEST || die "Could not copy redis init script to  $INIT_SCRIPT_DEST"
+echo "Copied $TMP_FILE => $INIT_SCRIPT_DEST"
+
+#Install the service
+echo "Installing service..."
+if command -v chkconfig >/dev/null 2>&1; then
+	# we're chkconfig, so lets add to chkconfig and put in runlevel 345
+	chkconfig --add redis_${REDIS_PORT} && echo "Successfully added to chkconfig!"
+	chkconfig --level 345 redis_${REDIS_PORT} on && echo "Successfully added to runlevels 345!"
+elif command -v update-rc.d >/dev/null 2>&1; then
+	#if we're not a chkconfig box assume we're able to use update-rc.d
+	update-rc.d redis_${REDIS_PORT} defaults && echo "Success!"
+else
+	echo "No supported init tool found."
+fi
+
+/etc/init.d/redis_$REDIS_PORT start || die "Failed starting service..."
+
+#tada
+echo "Installation successful!"
+exit 0
diff --git a/utils/lru/README b/utils/lru/README
new file mode 100644
index 0000000..f043b29
--- /dev/null
+++ b/utils/lru/README
@@ -0,0 +1,19 @@
+The test-lru.rb program can be used in order to check the behavior of the
+Redis approximated LRU algorithm against the theoretical output of true
+LRU algorithm.
+
+In order to use the program you need to recompile Redis setting the define
+REDIS_LRU_CLOCK_RESOLUTION to 1, by editing the file server.h.
+This allows to execute the program in a fast way since the 1 ms resolution
+is enough for all the objects to have a different enough time stamp during
+the test.
+
+The program is executed like this:
+
+    ruby test-lru.rb /tmp/lru.html
+
+You can optionally specify a number of times to run, so that the program
+will output averages of different runs, by adding an additional argument.
+For instance in order to run the test 10 times use:
+
+    ruby test-lru.rb /tmp/lru.html 10
diff --git a/utils/lru/lfu-simulation.c b/utils/lru/lfu-simulation.c
new file mode 100644
index 0000000..6aa5911
--- /dev/null
+++ b/utils/lru/lfu-simulation.c
@@ -0,0 +1,158 @@
+#include <stdio.h>
+#include <time.h>
+#include <stdint.h>
+#include <stdlib.h>
+
+int decr_every = 1;
+int keyspace_size = 1000000;
+time_t switch_after = 30; /* Switch access pattern after N seconds. */
+
+struct entry {
+    /* Field that the LFU Redis implementation will have (we have
+     * 24 bits of total space in the object->lru field). */
+    uint8_t counter;    /* Logarithmic counter. */
+    uint16_t decrtime;  /* (Reduced precision) time of last decrement. */
+
+    /* Fields only useful for visualization. */
+    uint64_t hits;      /* Number of real accesses. */
+    time_t ctime;       /* Key creation time. */
+};
+
+#define to_16bit_minutes(x) ((x/60) & 65535)
+#define COUNTER_INIT_VAL 5
+
+/* Compute the difference in minutes between two 16 bit minutes times
+ * obtained with to_16bit_minutes(). Since they can wrap around if
+ * we detect the overflow we account for it as if the counter wrapped
+ * a single time. */
+uint16_t minutes_diff(uint16_t now, uint16_t prev) {
+    if (now >= prev) return now-prev;
+    return 65535-prev+now;
+}
+
+/* Increment a couter logaritmically: the greatest is its value, the
+ * less likely is that the counter is really incremented.
+ * The maximum value of the counter is saturated at 255. */
+uint8_t log_incr(uint8_t counter) {
+    if (counter == 255) return counter;
+    double r = (double)rand()/RAND_MAX;
+    double baseval = counter-COUNTER_INIT_VAL;
+    if (baseval < 0) baseval = 0;
+    double limit = 1.0/(baseval*10+1);
+    if (r < limit) counter++;
+    return counter;
+}
+
+/* Simulate an access to an entry. */
+void access_entry(struct entry *e) {
+    e->counter = log_incr(e->counter);
+    e->hits++;
+}
+
+/* Return the entry LFU value and as a side effect decrement the
+ * entry value if the decrement time was reached. */
+uint8_t scan_entry(struct entry *e) {
+    if (minutes_diff(to_16bit_minutes(time(NULL)),e->decrtime)
+        >= decr_every)
+    {
+        if (e->counter) {
+            if (e->counter > COUNTER_INIT_VAL*2) {
+                e->counter /= 2;
+            } else {
+                e->counter--;
+            }
+        }
+        e->decrtime = to_16bit_minutes(time(NULL));
+    }
+    return e->counter;
+}
+
+/* Print the entry info. */
+void show_entry(long pos, struct entry *e) {
+    char *tag = "normal       ";
+
+    if (pos >= 10 && pos <= 14) tag = "new no access";
+    if (pos >= 15 && pos <= 19) tag = "new accessed ";
+    if (pos >= keyspace_size -5) tag= "old no access";
+
+    printf("%ld] <%s> frequency:%d decrtime:%d [%lu hits | age:%ld sec]\n",
+        pos, tag, e->counter, e->decrtime, (unsigned long)e->hits,
+            time(NULL) - e->ctime);
+}
+
+int main(void) {
+    time_t start = time(NULL);
+    time_t new_entry_time = start;
+    time_t display_time = start;
+    struct entry *entries = malloc(sizeof(*entries)*keyspace_size);
+    long j;
+
+    /* Initialize. */
+    for (j = 0; j < keyspace_size; j++) {
+        entries[j].counter = COUNTER_INIT_VAL;
+        entries[j].decrtime = to_16bit_minutes(start);
+        entries[j].hits = 0;
+        entries[j].ctime = time(NULL);
+    }
+
+    while(1) {
+        time_t now = time(NULL);
+        long idx;
+
+        /* Scan N random entries (simulates the eviction under maxmemory). */
+        for (j = 0; j < 3; j++) {
+            scan_entry(entries+(rand()%keyspace_size));
+        }
+
+        /* Access a random entry: use a power-law access pattern up to
+         * 'switch_after' seconds. Then revert to flat access pattern. */
+        if (now-start < switch_after) {
+            /* Power law. */
+            idx = 1;
+            while((rand() % 21) != 0 && idx < keyspace_size) idx *= 2;
+            if (idx > keyspace_size) idx = keyspace_size;
+            idx = rand() % idx;
+        } else {
+            /* Flat. */
+            idx = rand() % keyspace_size;
+        }
+
+        /* Never access entries between position 10 and 14, so that
+         * we simulate what happens to new entries that are never
+         * accessed VS new entries which are accessed in positions
+         * 15-19.
+         *
+         * Also never access last 5 entry, so that we have keys which
+         * are never recreated (old), and never accessed. */
+        if ((idx < 10 || idx > 14) && (idx < keyspace_size-5))
+            access_entry(entries+idx);
+
+        /* Simulate the addition of new entries at positions between
+         * 10 and 19, a random one every 10 seconds. */
+        if (new_entry_time <= now) {
+            idx = 10+(rand()%10);
+            entries[idx].counter = COUNTER_INIT_VAL;
+            entries[idx].decrtime = to_16bit_minutes(time(NULL));
+            entries[idx].hits = 0;
+            entries[idx].ctime = time(NULL);
+            new_entry_time = now+10;
+        }
+
+        /* Show the first 20 entries and the last 20 entries. */
+        if (display_time != now) {
+            printf("=============================\n");
+            printf("Current minutes time: %d\n", (int)to_16bit_minutes(now));
+            printf("Access method: %s\n",
+                (now-start < switch_after) ? "power-law" : "flat");
+
+            for (j = 0; j < 20; j++)
+                show_entry(j,entries+j);
+
+            for (j = keyspace_size-20; j < keyspace_size; j++)
+                show_entry(j,entries+j);
+            display_time = now;
+        }
+    }
+    return 0;
+}
+
diff --git a/utils/lru/test-lru.rb b/utils/lru/test-lru.rb
new file mode 100644
index 0000000..d511e20
--- /dev/null
+++ b/utils/lru/test-lru.rb
@@ -0,0 +1,223 @@
+require 'rubygems'
+require 'redis'
+
+$runs = []; # Remember the error rate of each run for average purposes.
+$o = {};    # Options set parsing arguments
+
+def testit(filename)
+    r = Redis.new
+    r.config("SET","maxmemory","2000000")
+    if $o[:ttl]
+        r.config("SET","maxmemory-policy","volatile-ttl")
+    else
+        r.config("SET","maxmemory-policy","allkeys-lru")
+    end
+    r.config("SET","maxmemory-samples",5)
+    r.config("RESETSTAT")
+    r.flushall
+
+    html = ""
+    html << <<EOF
+    <html>
+    <body>
+    <style>
+    .box {
+        width:5px;
+        height:5px;
+        float:left;
+        margin: 1px;
+    }
+
+    .old {
+        border: 1px black solid;
+    }
+
+    .new {
+        border: 1px green solid;
+    }
+
+    .otherdb {
+        border: 1px red solid;
+    }
+
+    .ex {
+        background-color: #666;
+    }
+    </style>
+    <pre>
+EOF
+
+    # Fill the DB up to the first eviction.
+    oldsize = r.dbsize
+    id = 0
+    while true
+        id += 1
+        begin
+            r.set(id,"foo")
+        rescue
+            break
+        end
+        newsize = r.dbsize
+        break if newsize == oldsize # A key was evicted? Stop.
+        oldsize = newsize
+    end
+
+    inserted = r.dbsize
+    first_set_max_id = id
+    html << "#{r.dbsize} keys inserted.\n"
+
+    # Access keys sequentially, so that in theory the first part will be expired
+    # and the latter part will not, according to perfect LRU.
+
+    if $o[:ttl]
+        STDERR.puts "Set increasing expire value"
+        (1..first_set_max_id).each{|id|
+            r.expire(id,1000+id)
+            STDERR.print(".") if (id % 150) == 0
+        }
+    else
+        STDERR.puts "Access keys sequentially"
+        (1..first_set_max_id).each{|id|
+            r.get(id)
+            sleep 0.001
+            STDERR.print(".") if (id % 150) == 0
+        }
+    end
+    STDERR.puts
+
+    # Insert more 50% keys. We expect that the new keys will rarely be expired
+    # since their last access time is recent compared to the others.
+    #
+    # Note that we insert the first 100 keys of the new set into DB1 instead
+    # of DB0, so that we can try how cross-DB eviction works.
+    half = inserted/2
+    html << "Insert enough keys to evict half the keys we inserted.\n"
+    add = 0
+
+    otherdb_start_idx = id+1
+    otherdb_end_idx = id+100
+    while true
+        add += 1
+        id += 1
+        if id >= otherdb_start_idx && id <= otherdb_end_idx
+            r.select(1)
+            r.set(id,"foo")
+            r.select(0)
+        else
+            r.set(id,"foo")
+        end
+        break if r.info['evicted_keys'].to_i >= half
+    end
+
+    html << "#{add} additional keys added.\n"
+    html << "#{r.dbsize} keys in DB.\n"
+
+    # Check if evicted keys respect LRU
+    # We consider errors from 1 to N progressively more serious as they violate
+    # more the access pattern.
+
+    errors = 0
+    e = 1
+    error_per_key = 100000.0/first_set_max_id
+    half_set_size = first_set_max_id/2
+    maxerr = 0
+    (1..(first_set_max_id/2)).each{|id|
+        if id >= otherdb_start_idx && id <= otherdb_end_idx
+            r.select(1)
+            exists = r.exists(id)
+            r.select(0)
+        else
+            exists = r.exists(id)
+        end
+        if id < first_set_max_id/2
+            thiserr = error_per_key * ((half_set_size-id).to_f/half_set_size)
+            maxerr += thiserr
+            errors += thiserr if exists
+        elsif id >= first_set_max_id/2
+            thiserr = error_per_key * ((id-half_set_size).to_f/half_set_size)
+            maxerr += thiserr
+            errors += thiserr if !exists
+        end
+    }
+    errors = errors*100/maxerr
+
+    STDERR.puts "Test finished with #{errors}% error! Generating HTML on stdout."
+
+    html << "#{errors}% error!\n"
+    html << "</pre>"
+    $runs << errors
+
+    # Generate the graphical representation
+    (1..id).each{|id|
+        # Mark first set and added items in a different way.
+        c = "box"
+        if id >= otherdb_start_idx && id <= otherdb_end_idx
+            c << " otherdb"
+        elsif id <= first_set_max_id
+            c << " old"
+        else
+            c << " new"
+        end
+
+        # Add class if exists
+        if id >= otherdb_start_idx && id <= otherdb_end_idx
+            r.select(1)
+            exists = r.exists(id)
+            r.select(0)
+        else
+            exists = r.exists(id)
+        end
+
+        c << " ex" if exists
+        html << "<div title=\"#{id}\" class=\"#{c}\"></div>"
+    }
+
+    # Close HTML page
+
+    html << <<EOF
+    </body>
+    </html>
+EOF
+
+    f = File.open(filename,"w")
+    f.write(html)
+    f.close
+end
+
+def print_avg
+    avg = ($runs.reduce {|a,b| a+b}) / $runs.length
+    puts "#{$runs.length} runs, AVG is #{avg}"
+end
+
+if ARGV.length < 1
+    STDERR.puts "Usage: ruby test-lru.rb <html-output-filename> [--runs <count>] [--ttl]"
+    STDERR.puts "Options:"
+    STDERR.puts "  --runs <count>    Execute the test <count> times."
+    STDERR.puts "  --ttl             Set keys with increasing TTL values"
+    STDERR.puts "                    (starting from 1000 seconds) in order to"
+    STDERR.puts "                    test the volatile-lru policy."
+    exit 1
+end
+
+filename = ARGV[0]
+$o[:numruns] = 1
+
+# Options parsing
+i = 1
+while i < ARGV.length
+    if ARGV[i] == '--runs'
+        $o[:numruns] = ARGV[i+1].to_i
+        i+= 1
+    elsif ARGV[i] == '--ttl'
+        $o[:ttl] = true
+    else
+        STDERR.puts "Unknown option #{ARGV[i]}"
+        exit 1
+    end
+    i+= 1
+end
+
+$o[:numruns].times {
+    testit(filename)
+    print_avg if $o[:numruns] != 1
+}
diff --git a/utils/redis-copy.rb b/utils/redis-copy.rb
new file mode 100644
index 0000000..7c5c52d
--- /dev/null
+++ b/utils/redis-copy.rb
@@ -0,0 +1,35 @@
+# redis-copy.rb - Copyright (C) 2009-2010 Salvatore Sanfilippo
+# BSD license, See the COPYING file for more information.
+#
+# Copy the whole dataset from one Redis instance to another one
+#
+# WARNING: this utility is deprecated and serves as a legacy adapter
+#          for the more-robust redis-copy gem.
+
+require 'shellwords'
+
+def redisCopy(opts={})
+  src = "#{opts[:srchost]}:#{opts[:srcport]}"
+  dst = "#{opts[:dsthost]}:#{opts[:dstport]}"
+  `redis-copy #{src.shellescape} #{dst.shellescape}`
+rescue Errno::ENOENT
+  $stderr.puts 'This utility requires the redis-copy executable',
+               'from the redis-copy gem on https://rubygems.org',
+               'To install it, run `gem install redis-copy`.'
+  exit 1
+end
+
+$stderr.puts "This utility is deprecated. Use the redis-copy gem instead."
+if ARGV.length != 4
+    puts "Usage: redis-copy.rb <srchost> <srcport> <dsthost> <dstport>"
+    exit 1
+end
+puts "WARNING: it's up to you to FLUSHDB the destination host before to continue, press any key when ready."
+STDIN.gets
+srchost = ARGV[0]
+srcport = ARGV[1]
+dsthost = ARGV[2]
+dstport = ARGV[3]
+puts "Copying #{srchost}:#{srcport} into #{dsthost}:#{dstport}"
+redisCopy(:srchost => srchost, :srcport => srcport.to_i,
+          :dsthost => dsthost, :dstport => dstport.to_i)
diff --git a/utils/redis-sha1.rb b/utils/redis-sha1.rb
new file mode 100644
index 0000000..24498e2
--- /dev/null
+++ b/utils/redis-sha1.rb
@@ -0,0 +1,52 @@
+# redis-sha1.rb - Copyright (C) 2009 Salvatore Sanfilippo
+# BSD license, See the COPYING file for more information.
+#
+# Performs the SHA1 sum of the whole datset.
+# This is useful to spot bugs in persistence related code and to make sure
+# Slaves and Masters are in SYNC.
+#
+# If you hack this code make sure to sort keys and set elements as this are
+# unsorted elements. Otherwise the sum may differ with equal dataset.
+
+require 'rubygems'
+require 'redis'
+require 'digest/sha1'
+
+def redisSha1(opts={})
+    sha1=""
+    r = Redis.new(opts)
+    r.keys('*').sort.each{|k|
+        vtype = r.type?(k)
+        if vtype == "string"
+            len = 1
+            sha1 = Digest::SHA1.hexdigest(sha1+k)
+            sha1 = Digest::SHA1.hexdigest(sha1+r.get(k))
+        elsif vtype == "list"
+            len = r.llen(k)
+            if len != 0
+                sha1 = Digest::SHA1.hexdigest(sha1+k)
+                sha1 = Digest::SHA1.hexdigest(sha1+r.list_range(k,0,-1).join("\x01"))
+            end
+        elsif vtype == "set"
+            len = r.scard(k)
+            if len != 0
+                sha1 = Digest::SHA1.hexdigest(sha1+k)
+                sha1 = Digest::SHA1.hexdigest(sha1+r.set_members(k).to_a.sort.join("\x02"))
+            end
+        elsif vtype == "zset"
+            len = r.zcard(k)
+            if len != 0
+                sha1 = Digest::SHA1.hexdigest(sha1+k)
+                sha1 = Digest::SHA1.hexdigest(sha1+r.zrange(k,0,-1).join("\x01"))
+            end
+        end
+        # puts "#{k} => #{sha1}" if len != 0
+    }
+    sha1
+end
+
+host = ARGV[0] || "127.0.0.1"
+port = ARGV[1] || "6379"
+db = ARGV[2] || "0"
+puts "Performing SHA1 of Redis server #{host} #{port} DB: #{db}"
+p "Dataset SHA1: #{redisSha1(:host => host, :port => port.to_i, :db => db)}"
diff --git a/utils/redis_init_script b/utils/redis_init_script
new file mode 100644
index 0000000..4dfe980
--- /dev/null
+++ b/utils/redis_init_script
@@ -0,0 +1,42 @@
+#!/bin/sh
+#
+# Simple Redis init.d script conceived to work on Linux systems
+# as it does use of the /proc filesystem.
+
+REDISPORT=6379
+EXEC=/usr/local/bin/redis-server
+CLIEXEC=/usr/local/bin/redis-cli
+
+PIDFILE=/var/run/redis_${REDISPORT}.pid
+CONF="/etc/redis/${REDISPORT}.conf"
+
+case "$1" in
+    start)
+        if [ -f $PIDFILE ]
+        then
+                echo "$PIDFILE exists, process is already running or crashed"
+        else
+                echo "Starting Redis server..."
+                $EXEC $CONF
+        fi
+        ;;
+    stop)
+        if [ ! -f $PIDFILE ]
+        then
+                echo "$PIDFILE does not exist, process is not running"
+        else
+                PID=$(cat $PIDFILE)
+                echo "Stopping ..."
+                $CLIEXEC -p $REDISPORT shutdown
+                while [ -x /proc/${PID} ]
+                do
+                    echo "Waiting for Redis to shutdown ..."
+                    sleep 1
+                done
+                echo "Redis stopped"
+        fi
+        ;;
+    *)
+        echo "Please use start or stop as first argument"
+        ;;
+esac
diff --git a/utils/redis_init_script.tpl b/utils/redis_init_script.tpl
new file mode 100644
index 0000000..2e5b613
--- /dev/null
+++ b/utils/redis_init_script.tpl
@@ -0,0 +1,44 @@
+
+case "$1" in
+    start)
+        if [ -f $PIDFILE ]
+        then
+            echo "$PIDFILE exists, process is already running or crashed"
+        else
+            echo "Starting Redis server..."
+            $EXEC $CONF
+        fi
+        ;;
+    stop)
+        if [ ! -f $PIDFILE ]
+        then
+            echo "$PIDFILE does not exist, process is not running"
+        else
+            PID=$(cat $PIDFILE)
+            echo "Stopping ..."
+            $CLIEXEC -p $REDISPORT shutdown
+            while [ -x /proc/${PID} ]
+            do
+                echo "Waiting for Redis to shutdown ..."
+                sleep 1
+            done
+            echo "Redis stopped"
+        fi
+        ;;
+    status)
+        PID=$(cat $PIDFILE)
+        if [ ! -x /proc/${PID} ]
+        then
+            echo 'Redis is not running'
+        else
+            echo "Redis is running ($PID)"
+        fi
+        ;;
+    restart)
+        $0 stop
+        $0 start
+        ;;
+    *)
+        echo "Please use start, stop, restart or status as first argument"
+        ;;
+esac
diff --git a/utils/releasetools/01_create_tarball.sh b/utils/releasetools/01_create_tarball.sh
new file mode 100644
index 0000000..54bca8c
--- /dev/null
+++ b/utils/releasetools/01_create_tarball.sh
@@ -0,0 +1,15 @@
+#!/bin/sh
+if [ $# != "1" ]
+then
+    echo "Usage: ./mkrelease.sh <git-ref>"
+    exit 1
+fi
+
+TAG=$1
+TARNAME="redis-${TAG}.tar"
+echo "Generating /tmp/${TARNAME}"
+cd ~/hack/redis
+git archive $TAG --prefix redis-${TAG}/ > /tmp/$TARNAME || exit 1
+echo "Gizipping the archive"
+rm -f /tmp/$TARNAME.gz
+gzip -9 /tmp/$TARNAME
diff --git a/utils/releasetools/02_upload_tarball.sh b/utils/releasetools/02_upload_tarball.sh
new file mode 100644
index 0000000..ed70653
--- /dev/null
+++ b/utils/releasetools/02_upload_tarball.sh
@@ -0,0 +1,6 @@
+#!/bin/bash
+echo "Uploading..."
+scp /tmp/redis-${1}.tar.gz [email protected]:/var/virtual/download.redis.io/httpdocs/releases/
+echo "Updating web site... (press any key if it is a stable release, or Ctrl+C)"
+read x
+ssh [email protected] "cd /var/virtual/download.redis.io/httpdocs; ./update.sh ${1}"
diff --git a/utils/releasetools/03_test_release.sh b/utils/releasetools/03_test_release.sh
new file mode 100644
index 0000000..3dfdcd6
--- /dev/null
+++ b/utils/releasetools/03_test_release.sh
@@ -0,0 +1,26 @@
+#!/bin/sh
+if [ $# != "1" ]
+then
+    echo "Usage: ${0} <git-ref>"
+    exit 1
+fi
+
+TAG=$1
+TARNAME="redis-${TAG}.tar.gz"
+DOWNLOADURL="http://download.redis.io/releases/${TARNAME}"
+
+ssh antirez@metal "export TERM=xterm;
+                   cd /tmp;
+                   rm -rf test_release_tmp_dir;
+                   cd test_release_tmp_dir;
+                   rm -f $TARNAME;
+                   rm -rf redis-${TAG};
+                   wget $DOWNLOADURL;
+                   tar xvzf $TARNAME;
+                   cd redis-${TAG};
+                   make;
+                   ./runtest;
+                   ./runtest-sentinel;
+                   if [ -x runtest-cluster ]; then
+                       ./runtest-cluster;
+                   fi"
diff --git a/utils/releasetools/04_release_hash.sh b/utils/releasetools/04_release_hash.sh
new file mode 100644
index 0000000..9d5c6ad
--- /dev/null
+++ b/utils/releasetools/04_release_hash.sh
@@ -0,0 +1,8 @@
+#!/bin/bash
+SHA=$(curl -s http://download.redis.io/releases/redis-${1}.tar.gz | shasum -a 256 | cut -f 1 -d' ')
+ENTRY="hash redis-${1}.tar.gz sha256 $SHA http://download.redis.io/releases/redis-${1}.tar.gz"
+echo $ENTRY >> ~/hack/redis-hashes/README
+vi ~/hack/redis-hashes/README
+echo "Press any key to commit, Ctrl-C to abort)."
+read yes
+(cd ~/hack/redis-hashes; git commit -a -m "${1} hash."; git push)
diff --git a/utils/releasetools/changelog.tcl b/utils/releasetools/changelog.tcl
new file mode 100644
index 0000000..4b5424c
--- /dev/null
+++ b/utils/releasetools/changelog.tcl
@@ -0,0 +1,30 @@
+#!/usr/bin/env tclsh
+
+if {[llength $::argv] != 2} {
+    puts "Usage: $::argv0 <branch> <version>"
+    exit 1
+}
+
+set branch [lindex $::argv 0]
+set ver [lindex $::argv 1]
+
+set template {
+================================================================================
+Redis %ver%     Released %date%
+================================================================================
+
+Upgrade urgency <URGENCY>: <DESCRIPTION>
+}
+
+set template [string trim $template]
+append template "\n\n"
+set date [clock format [clock seconds]]
+set template [string map [list %ver% $ver %date% $date] $template]
+
+append template [exec git log $branch~30..$branch "--format=format:%an in commit %h:%n %s" --shortstat]
+
+#Older, more verbose version.
+#
+#append template [exec git log $branch~30..$branch "--format=format:+-------------------------------------------------------------------------------%n| %s%n| By %an, %ai%n+--------------------------------------------------------------------------------%nhttps://github.com/antirez/redis/commit/%H%n%n%b" --stat]
+
+puts $template
diff --git a/utils/speed-regression.tcl b/utils/speed-regression.tcl
new file mode 100644
index 0000000..86a7d8d
--- /dev/null
+++ b/utils/speed-regression.tcl
@@ -0,0 +1,130 @@
+#!/usr/bin/env tclsh8.5
+# Copyright (C) 2011 Salvatore Sanfilippo
+# Released under the BSD license like Redis itself
+
+source ../tests/support/redis.tcl
+set ::port 12123
+set ::tests {PING,SET,GET,INCR,LPUSH,LPOP,SADD,SPOP,LRANGE_100,LRANGE_600,MSET}
+set ::datasize 16
+set ::requests 100000
+
+proc run-tests branches {
+    set runs {}
+    set branch_id 0
+    foreach b $branches {
+        cd ../src
+        puts "Benchmarking $b"
+        exec -ignorestderr git checkout $b 2> /dev/null
+        exec -ignorestderr make clean 2> /dev/null
+        puts "  compiling..."
+        exec -ignorestderr make 2> /dev/null
+
+        if {$branch_id == 0} {
+            puts "  copy redis-benchmark from unstable to /tmp..."
+            exec -ignorestderr cp ./redis-benchmark /tmp
+            incr branch_id
+            continue
+        }
+
+        # Start the Redis server
+        puts "  starting the server... [exec ./redis-server -v]"
+        set pids [exec echo "port $::port\nloglevel warning\n" | ./redis-server - > /dev/null 2> /dev/null &]
+        puts "  pids: $pids"
+        after 1000
+        puts "  running the benchmark"
+
+        set r [redis 127.0.0.1 $::port]
+        set i [$r info]
+        puts "  redis INFO shows version: [lindex [split $i] 0]"
+        $r close
+
+        set output [exec /tmp/redis-benchmark -n $::requests -t $::tests -d $::datasize --csv -p $::port]
+        lappend runs $b $output
+        puts "  killing server..."
+        catch {exec kill -9 [lindex $pids 0]}
+        catch {exec kill -9 [lindex $pids 1]}
+        incr branch_id
+    }
+    return $runs
+}
+
+proc get-result-with-name {output name} {
+    foreach line [split $output "\n"] {
+        lassign [split $line ","] key value
+        set key [string tolower [string range $key 1 end-1]]
+        set value [string range $value 1 end-1]
+        if {$key eq [string tolower $name]} {
+            return $value
+        }
+    }
+    return "n/a"
+}
+
+proc get-test-names output {
+    set names {}
+    foreach line [split $output "\n"] {
+        lassign [split $line ","] key value
+        set key [string tolower [string range $key 1 end-1]]
+        lappend names $key
+    }
+    return $names
+}
+
+proc combine-results {results} {
+    set tests [get-test-names [lindex $results 1]]
+    foreach test $tests {
+        puts $test
+        foreach {branch output} $results {
+            puts [format "%-20s %s" \
+                $branch [get-result-with-name $output $test]]
+        }
+        puts {}
+    }
+}
+
+proc main {} {
+    # Note: the first branch is only used in order to get the redis-benchmark
+    # executable. Tests are performed starting from the second branch.
+    set branches {
+        slowset 2.2.0 2.4.0 unstable slowset
+    }
+    set results [run-tests $branches]
+    puts "\n"
+    puts "# Test results: datasize=$::datasize requests=$::requests"
+    puts [combine-results $results]
+}
+
+# Force the user to run the script from the 'utils' directory.
+if {![file exists speed-regression.tcl]} {
+    puts "Please make sure to run speed-regression.tcl while inside /utils."
+    puts "Example: cd utils; ./speed-regression.tcl"
+    exit 1
+}
+
+# Make sure there is not already a server runnign on port 12123
+set is_not_running [catch {set r [redis 127.0.0.1 $::port]}]
+if {!$is_not_running} {
+    puts "Sorry, you have a running server on port $::port"
+    exit 1
+}
+
+# parse arguments
+for {set j 0} {$j < [llength $argv]} {incr j} {
+    set opt [lindex $argv $j]
+    set arg [lindex $argv [expr $j+1]]
+    if {$opt eq {--tests}} {
+        set ::tests $arg
+        incr j
+    } elseif {$opt eq {--datasize}} {
+        set ::datasize $arg
+        incr j
+    } elseif {$opt eq {--requests}} {
+        set ::requests $arg
+        incr j
+    } else {
+        puts "Wrong argument: $opt"
+        exit 1
+    }
+}
+
+main
diff --git a/utils/whatisdoing.sh b/utils/whatisdoing.sh
new file mode 100644
index 0000000..e4059ca
--- /dev/null
+++ b/utils/whatisdoing.sh
@@ -0,0 +1,24 @@
+# This script is from http://poormansprofiler.org/
+#
+# NOTE: Instead of using this script, you should use the Redis
+# Software Watchdog, which provides a similar functionality but in
+# a more reliable / easy to use way.
+#
+# Check http://redis.io/topics/latency for more information.
+
+#!/bin/bash
+nsamples=1
+sleeptime=0
+pid=$(ps auxww | grep '[r]edis-server' | awk '{print $2}')
+
+for x in $(seq 1 $nsamples)
+  do
+    gdb -ex "set pagination 0" -ex "thread apply all bt" -batch -p $pid
+    sleep $sleeptime
+  done | \
+awk '
+  BEGIN { s = ""; } 
+  /Thread/ { print s; s = ""; } 
+  /^\#/ { if (s != "" ) { s = s "," $4} else { s = $4 } } 
+  END { print s }' | \
+sort | uniq -c | sort -r -n -k 1,1