Hopefully better memory test on crash.

The old test, designed to do a transformation on the bits that was
invertible, in order to avoid touching the original memory content, was
not effective as it was redis-server --test-memory. The former often
reported OK while the latter was able to spot the error.

So the test was substituted with one that may perform better, however
the new one must backup the memory tested, so it tests memory in small
pieces. This limits the effectiveness because of the CPU caches. However
some attempt is made in order to trash the CPU cache between the fill
and the check stages, but not for the addressing test unfortunately.

We'll see if this test will be able to find errors where the old failed.

3 files changed, 133 insertions, 86 deletions

diff --git a/src/debug.c b/src/debug.c
index 0c81a8711..e2958c426 100644
--- a/src/debug.c
+++ b/src/debug.c
@@ -757,18 +757,33 @@ void logRegisters(ucontext_t *uc) {
 #endif
 }
 
+/* Return a file descriptor to write directly to the Redis log with the
+ * write(2) syscall, that can be used in critical sections of the code
+ * where the rest of Redis can't be trusted (for example during the memory
+ * test) or when an API call requires a raw fd.
+ *
+ * Close it with closeDirectLogFiledes(). */
+int openDirectLogFiledes(void) {
+    int log_to_stdout = server.logfile[0] == '\0';
+    int fd = log_to_stdout ?
+        STDOUT_FILENO :
+        open(server.logfile, O_APPEND|O_CREAT|O_WRONLY, 0644);
+    return fd;
+}
+
+/* Used to close what closeDirectLogFiledes() returns. */
+void closeDirectLogFiledes(int fd) {
+    int log_to_stdout = server.logfile[0] == '\0';
+    if (!log_to_stdout) close(fd);
+}
+
 /* Logs the stack trace using the backtrace() call. This function is designed
  * to be called from signal handlers safely. */
 void logStackTrace(ucontext_t *uc) {
     void *trace[101];
-    int trace_size = 0, fd;
-    int log_to_stdout = server.logfile[0] == '\0';
+    int trace_size = 0, fd = openDirectLogFiledes();
 
-    /* Open the log file in append mode. */
-    fd = log_to_stdout ?
-        STDOUT_FILENO :
-        open(server.logfile, O_APPEND|O_CREAT|O_WRONLY, 0644);
-    if (fd == -1) return;
+    if (fd == -1) return; /* If we can't log there is anything to do. */
 
     /* Generate the stack trace */
     trace_size = backtrace(trace+1, 100);
@@ -786,7 +801,7 @@ void logStackTrace(ucontext_t *uc) {
     backtrace_symbols_fd(trace+1, trace_size, fd);
 
     /* Cleanup */
-    if (!log_to_stdout) close(fd);
+    closeDirectLogFiledes(fd);
 }
 
 /* Log information about the "current" client, that is, the client that is
@@ -829,19 +844,24 @@ void logCurrentClient(void) {
 }
 
 #if defined(HAVE_PROC_MAPS)
-void memtest_non_destructive_invert(void *addr, size_t size);
-void memtest_non_destructive_swap(void *addr, size_t size);
+
 #define MEMTEST_MAX_REGIONS 128
 
+/* A non destructive memory test executed during segfauls. */
 int memtest_test_linux_anonymous_maps(void) {
-    FILE *fp = fopen("/proc/self/maps","r");
+    FILE *fp;
     char line[1024];
+    char logbuf[1024];
     size_t start_addr, end_addr, size;
     size_t start_vect[MEMTEST_MAX_REGIONS];
     size_t size_vect[MEMTEST_MAX_REGIONS];
     int regions = 0, j;
-    uint64_t crc1 = 0, crc2 = 0, crc3 = 0;
 
+    int fd = openDirectLogFiledes();
+    if (!fd) return 0;
+
+    fp = fopen("/proc/self/maps","r");
+    if (!fp) return 0;
     while(fgets(line,sizeof(line),fp) != NULL) {
         char *start, *end, *p = line;
 
@@ -865,49 +885,28 @@ int memtest_test_linux_anonymous_maps(void) {
 
         start_vect[regions] = start_addr;
         size_vect[regions] = size;
-        printf("Testing %lx %lu\n", (unsigned long) start_vect[regions],
-                                    (unsigned long) size_vect[regions]);
+        snprintf(logbuf,sizeof(logbuf),
+            "*** Preparing to test memory region %lx (%lu bytes)\n",
+                (unsigned long) start_vect[regions],
+                (unsigned long) size_vect[regions]);
+        if (write(fd,logbuf,strlen(logbuf)) == -1) { /* Nothing to do. */ }
         regions++;
     }
 
-    /* Test all the regions as an unique sequential region.
-     * 1) Take the CRC64 of the memory region. */
+    int errors = 0;
     for (j = 0; j < regions; j++) {
-        crc1 = crc64(crc1,(void*)start_vect[j],size_vect[j]);
+        if (write(fd,".",1) == -1) { /* Nothing to do. */ }
+        errors += memtest_preserving_test((void*)start_vect[j],size_vect[j],1);
+        if (write(fd, errors ? "E" : "O",1) == -1) { /* Nothing to do. */ }
     }
-
-    /* 2) Invert bits, swap adjacent words, swap again, invert bits.
-     * This is the error amplification step. */
-    for (j = 0; j < regions; j++)
-        memtest_non_destructive_invert((void*)start_vect[j],size_vect[j]);
-    for (j = 0; j < regions; j++)
-        memtest_non_destructive_swap((void*)start_vect[j],size_vect[j]);
-    for (j = 0; j < regions; j++)
-        memtest_non_destructive_swap((void*)start_vect[j],size_vect[j]);
-    for (j = 0; j < regions; j++)
-        memtest_non_destructive_invert((void*)start_vect[j],size_vect[j]);
-
-    /* 3) Take the CRC64 sum again. */
-    for (j = 0; j < regions; j++)
-        crc2 = crc64(crc2,(void*)start_vect[j],size_vect[j]);
-
-    /* 4) Swap + Swap again */
-    for (j = 0; j < regions; j++)
-        memtest_non_destructive_swap((void*)start_vect[j],size_vect[j]);
-    for (j = 0; j < regions; j++)
-        memtest_non_destructive_swap((void*)start_vect[j],size_vect[j]);
-
-    /* 5) Take the CRC64 sum again. */
-    for (j = 0; j < regions; j++)
-        crc3 = crc64(crc3,(void*)start_vect[j],size_vect[j]);
+    if (write(fd,"\n",1) == -1) { /* Nothing to do. */ }
 
     /* NOTE: It is very important to close the file descriptor only now
      * because closing it before may result into unmapping of some memory
      * region that we are testing. */
     fclose(fp);
-
-    /* If the two CRC are not the same, we trapped a memory error. */
-    return crc1 != crc2 || crc2 != crc3;
+    closeDirectLogFiledes(fd);
+    return errors;
 }
 #endif
 
@@ -960,10 +959,10 @@ void sigsegvHandler(int sig, siginfo_t *info, void *secret) {
     serverLogRaw(LL_WARNING|LL_RAW, "\n------ FAST MEMORY TEST ------\n");
     bioKillThreads();
     if (memtest_test_linux_anonymous_maps()) {
-        serverLog(LL_WARNING,
+        serverLogRaw(LL_WARNING|LL_RAW,
             "!!! MEMORY ERROR DETECTED! Check your memory ASAP !!!");
     } else {
-        serverLog(LL_WARNING,
+        serverLogRaw(LL_WARNING|LL_RAW,
             "Fast memory test PASSED, however your memory can still be broken. Please run a memory test for several hours if possible.");
     }
 #endif
diff --git a/src/memtest.c b/src/memtest.c
index a25290852..a455430f5 100644
--- a/src/memtest.c
+++ b/src/memtest.c
@@ -26,7 +26,7 @@
  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  * POSSIBILITY OF SUCH DAMAGE.
  */
-
+#include <stdint.h>
 #include <stdlib.h>
 #include <stdio.h>
 #include <string.h>
@@ -123,27 +123,33 @@ int memtest_addressing(unsigned long *l, size_t bytes, int interactive) {
 /* Fill words stepping a single page at every write, so we continue to
  * touch all the pages in the smallest amount of time reducing the
  * effectiveness of caches, and making it hard for the OS to transfer
- * pages on the swap. */
+ * pages on the swap.
+ *
+ * In this test we can't call rand() since the system may be completely
+ * unable to handle library calls, so we have to resort to our own
+ * PRNG that only uses local state. We use an xorshift* PRNG. */
+#define xorshift64star_next() do { \
+        rseed ^= rseed >> 12; \
+        rseed ^= rseed << 25; \
+        rseed ^= rseed >> 27; \
+        rout = rseed * UINT64_C(2685821657736338717); \
+} while(0)
+
 void memtest_fill_random(unsigned long *l, size_t bytes, int interactive) {
     unsigned long step = 4096/sizeof(unsigned long);
     unsigned long words = bytes/sizeof(unsigned long)/2;
     unsigned long iwords = words/step;  /* words per iteration */
     unsigned long off, w, *l1, *l2;
+    uint64_t rseed = UINT64_C(0xd13133de9afdb566); /* Just a random seed. */
+    uint64_t rout = 0;
 
     assert((bytes & 4095) == 0);
     for (off = 0; off < step; off++) {
         l1 = l+off;
         l2 = l1+words;
         for (w = 0; w < iwords; w++) {
-#ifdef MEMTEST_32BIT
-            *l1 = *l2 = ((unsigned long)     (rand()&0xffff)) |
-                        (((unsigned long)    (rand()&0xffff)) << 16);
-#else
-            *l1 = *l2 = ((unsigned long)     (rand()&0xffff)) |
-                        (((unsigned long)    (rand()&0xffff)) << 16) |
-                        (((unsigned long)    (rand()&0xffff)) << 32) |
-                        (((unsigned long)    (rand()&0xffff)) << 48);
-#endif
+            xorshift64star_next();
+            *l1 = *l2 = (unsigned long) rout;
             l1 += step;
             l2 += step;
             if ((w & 0xffff) == 0 && interactive)
@@ -254,7 +260,75 @@ int memtest_test(unsigned long *m, size_t bytes, int passes, int interactive) {
         if (interactive) memtest_progress_end();
         errors += memtest_compare_times(m,bytes,pass,4,interactive);
     }
-    free(m);
+    return errors;
+}
+
+/* A version of memtest_test() that tests memory in small pieces
+ * in order to restore the memory content at exit.
+ *
+ * One problem we have with this approach, is that the cache can avoid
+ * real memory accesses, and we can't test big chunks of memory at the
+ * same time, because we need to backup them on the stack (the allocator
+ * may not be usable or we may be already in an out of memory condition).
+ * So what we do is to try to trash the cache with useless memory accesses
+ * between the fill and compare cycles. */
+#define MEMTEST_BACKUP_WORDS (1024*(1024/sizeof(long)))
+/* Random accesses of MEMTEST_DECACHE_SIZE are performed at the start and
+ * end of the region between fill and compare cycles in order to trash
+ * the cache. */
+#define MEMTEST_DECACHE_SIZE (1024*8)
+int memtest_preserving_test(unsigned long *m, size_t bytes, int passes) {
+    unsigned long backup[MEMTEST_BACKUP_WORDS];
+    unsigned long *p = m;
+    unsigned long *end = (unsigned long*) (((unsigned char*)m)+(bytes-MEMTEST_DECACHE_SIZE));
+    size_t left = bytes;
+    int errors = 0;
+
+    if (bytes & 4095) return 0; /* Can't test across 4k page boundaries. */
+    if (bytes < 4096*2) return 0; /* Can't test a single page. */
+
+    while(left) {
+        /* If we have to test a single final page, go back a single page
+         * so that we can test two pages, since the code can't test a single
+         * page but at least two. */
+        if (left == 4096) {
+            left += 4096;
+            p -= 4096/sizeof(unsigned long);
+        }
+
+        int pass = 0;
+        size_t len = (left > sizeof(backup)) ? sizeof(backup) : left;
+
+        /* Always test an even number of pages. */
+        if (len/4096 % 2) len -= 4096;
+
+        memcpy(backup,p,len); /* Backup. */
+        while(pass != passes) {
+            pass++;
+            errors += memtest_addressing(p,len,0);
+            memtest_fill_random(p,len,0);
+            if (bytes >= MEMTEST_DECACHE_SIZE) {
+                memtest_compare_times(m,MEMTEST_DECACHE_SIZE,pass,1,0);
+                memtest_compare_times(end,MEMTEST_DECACHE_SIZE,pass,1,0);
+            }
+            errors += memtest_compare_times(p,len,pass,4,0);
+            memtest_fill_value(p,len,0,(unsigned long)-1,'S',0);
+            if (bytes >= MEMTEST_DECACHE_SIZE) {
+                memtest_compare_times(m,MEMTEST_DECACHE_SIZE,pass,1,0);
+                memtest_compare_times(end,MEMTEST_DECACHE_SIZE,pass,1,0);
+            }
+            errors += memtest_compare_times(p,len,pass,4,0);
+            memtest_fill_value(p,len,ULONG_ONEZERO,ULONG_ZEROONE,'C',0);
+            if (bytes >= MEMTEST_DECACHE_SIZE) {
+                memtest_compare_times(m,MEMTEST_DECACHE_SIZE,pass,1,0);
+                memtest_compare_times(end,MEMTEST_DECACHE_SIZE,pass,1,0);
+            }
+            errors += memtest_compare_times(p,len,pass,4,0);
+        }
+        memcpy(p,backup,len); /* Restore. */
+        left -= len;
+        p += len/sizeof(unsigned long);
+    }
     return errors;
 }
 
@@ -272,32 +346,6 @@ void memtest_alloc_and_test(size_t megabytes, int passes) {
     free(m);
 }
 
-void memtest_non_destructive_invert(void *addr, size_t size) {
-    volatile unsigned long *p = addr;
-    size_t words = size / sizeof(unsigned long);
-    size_t j;
-
-    /* Invert */
-    for (j = 0; j < words; j++)
-        p[j] = ~p[j];
-}
-
-void memtest_non_destructive_swap(void *addr, size_t size) {
-    volatile unsigned long *p = addr;
-    size_t words = size / sizeof(unsigned long);
-    size_t j;
-
-    /* Swap */
-    for (j = 0; j < words; j += 2) {
-        unsigned long a, b;
-
-        a = p[j];
-        b = p[j+1];
-        p[j] = b;
-        p[j+1] = a;
-    }
-}
-
 void memtest(size_t megabytes, int passes) {
     if (ioctl(1, TIOCGWINSZ, &ws) == -1) {
         ws.ws_col = 80;
diff --git a/src/server.h b/src/server.h
index 0953a1fe9..242a0267b 100644
--- a/src/server.h
+++ b/src/server.h
@@ -1650,7 +1650,7 @@ void enableWatchdog(int period);
 void disableWatchdog(void);
 void watchdogScheduleSignal(int period);
 void serverLogHexDump(int level, char *descr, void *value, size_t len);
-int memtest_test(unsigned long *m, size_t bytes, int passes, int interactive);
+int memtest_preserving_test(unsigned long *m, size_t bytes, int passes);
 
 #define redisDebug(fmt, ...) \
     printf("DEBUG %s:%d > " fmt "\n", __FILE__, __LINE__, __VA_ARGS__)