Memento: Speed improvements.

Avoid searching the linked list of blocks in order to remove a
block by moving to a doubly linked list. This can be done
without increasing the amount of memory in use by making better
use of the 'parent' pointer that is only used when displaying
nested blocks.

Also store magic values in the 'child' and 'sibling' pointers
(again only used when displaying nested blocks) so that we
can quickly verify that a block is real before doing too much
with it.

Those changes drastically reduce the time required for
MEMENTO_LEAKONLY runs (now the same order of magnitude as non
memento runs).

Normal memento runs are still very slow when the numbers of
blocks increase due to the paranoid checking taking time.

To ameliorate this a bit, we try 2 other things.

Firstly, we optimise the searching of blocks by making use of
int aligned tests. This still doesn't make much difference.

Secondly, we introduce a new mechanism for the 'paranoia'
levels. If a negative number is given for the paranoia level
(say -n) then we first perform our overwrite checks after n events.
We next test after 2n events, then 4n, then 8n etc.

The new default paranoia level is set to be -1024.

This makes a huge difference, and brings normal memento runs
down to be comparable with debug runs.

1 files changed, 266 insertions, 153 deletions

diff --git a/source/fitz/memento.c b/source/fitz/memento.c
index abf7274c..8af5a424 100644
--- a/source/fitz/memento.c
+++ b/source/fitz/memento.c
@@ -1,4 +1,4 @@
-/* Copyright (C) 2009-2015 Artifex Software, Inc.
+/* Copyright (C) 2009-2016 Artifex Software, Inc.
    All Rights Reserved.
 
    This software is provided AS-IS with no warranty, either express or
@@ -25,7 +25,7 @@
 
 /* We have some GS specific tweaks; more for the GS build environment than
  * anything else. */
-#undef MEMENTO_GS_HACKS
+/* #define MEMENTO_GS_HACKS */
 
 #ifdef MEMENTO_GS_HACKS
 /* For GS we include malloc_.h. Anyone else would just include memento.h */
@@ -43,6 +43,10 @@ int atexit(void (*)(void));
 #include <stdio.h>
 #include <stdlib.h>
 #endif
+#ifndef _MSC_VER
+#include <stdint.h>
+#include <limits.h>
+#endif
 
 #ifdef MEMENTO
 
@@ -54,11 +58,11 @@ int atexit(void (*)(void));
 static int
 android_fprintf(FILE *file, const char *fmt, ...)
 {
-	va_list args;
+    va_list args;
 
-	va_start(args, fmt);
-	__android_log_vprint(ANDROID_LOG_ERROR,"memento", fmt, args);
-	va_end(args);
+    va_start(args, fmt);
+    __android_log_vprint(ANDROID_LOG_ERROR,"memento", fmt, args);
+    va_end(args);
 }
 
 #define fprintf android_fprintf
@@ -71,20 +75,20 @@ android_fprintf(FILE *file, const char *fmt, ...)
 static int
 windows_fprintf(FILE *file, const char *fmt, ...)
 {
-	va_list args;
-	char text[4096];
-	int ret;
+    va_list args;
+    char text[4096];
+    int ret;
 
-	va_start(args, fmt);
-	ret = vfprintf(file, fmt, args);
-	va_end(args);
+    va_start(args, fmt);
+    ret = vfprintf(file, fmt, args);
+    va_end(args);
 
-	va_start(args, fmt);
-	vsnprintf(text, 4096, fmt, args);
-	OutputDebugStringA(text);
-	va_end(args);
+    va_start(args, fmt);
+    vsnprintf(text, 4096, fmt, args);
+    OutputDebugStringA(text);
+    va_end(args);
 
-	return ret;
+    return ret;
 }
 
 #define fprintf windows_fprintf
@@ -138,11 +142,30 @@ enum {
     Memento_PostSize = 16
 };
 
+/* Some compile time checks */
+typedef struct
+{
+    char MEMENTO_PRESIZE_MUST_BE_A_MULTIPLE_OF_4[Memento_PreSize & 3 ? -1 : 1];
+    char MEMENTO_POSTSIZE_MUST_BE_A_MULTIPLE_OF_4[Memento_PostSize & 3 ? -1 : 1];
+    char MEMENTO_POSTSIZE_MUST_BE_AT_LEAST_4[Memento_PostSize >= 4 ? 1 : -1];
+    char MEMENTO_PRESIZE_MUST_BE_AT_LEAST_4[Memento_PreSize >= 4 ? 1 : -1];
+} MEMENTO_SANITY_CHECK_STRUCT;
+
+#define MEMENTO_UINT32 unsigned int
+#define MEMENTO_UINT16 unsigned short
+
+#define MEMENTO_PREFILL_UINT32  ((MEMENTO_UINT32)(MEMENTO_PREFILL  | (MEMENTO_PREFILL <<8) | (MEMENTO_PREFILL <<16) |(MEMENTO_PREFILL <<24)))
+#define MEMENTO_POSTFILL_UINT16 ((MEMENTO_UINT16)(MEMENTO_POSTFILL | (MEMENTO_POSTFILL<<8)))
+#define MEMENTO_POSTFILL_UINT32 ((MEMENTO_UINT32)(MEMENTO_POSTFILL | (MEMENTO_POSTFILL<<8) | (MEMENTO_POSTFILL<<16) |(MEMENTO_POSTFILL<<24)))
+#define MEMENTO_FREEFILL_UINT16 ((MEMENTO_UINT16)(MEMENTO_FREEFILL | (MEMENTO_FREEFILL<<8)))
+#define MEMENTO_FREEFILL_UINT32 ((MEMENTO_UINT32)(MEMENTO_FREEFILL | (MEMENTO_FREEFILL<<8) | (MEMENTO_FREEFILL<<16) |(MEMENTO_FREEFILL<<24)))
+
 enum {
     Memento_Flag_OldBlock = 1,
     Memento_Flag_HasParent = 2,
     Memento_Flag_BreakOnFree = 4,
-    Memento_Flag_BreakOnRealloc = 8
+    Memento_Flag_BreakOnRealloc = 8,
+    Memento_Flag_Freed = 16
 };
 
 /* When we list leaked blocks at the end of execution, we search for pointers
@@ -164,6 +187,9 @@ enum {
 #endif
 #endif
 
+#define MEMENTO_CHILD_MAGIC   ((Memento_BlkHeader *)('M' | ('3' << 8) | ('m' << 16) | ('3' << 24)))
+#define MEMENTO_SIBLING_MAGIC ((Memento_BlkHeader *)('n' | ('t' << 8) | ('0' << 16) | ('!' << 24)))
+
 typedef struct Memento_BlkHeader Memento_BlkHeader;
 
 struct Memento_BlkHeader
@@ -173,11 +199,12 @@ struct Memento_BlkHeader
     int                lastCheckedOK;
     int                flags;
     Memento_BlkHeader *next;
-    Memento_BlkHeader *parent; /* Only used while printing out nested list */
+    Memento_BlkHeader *prev; /* Reused as 'parent' when printing nested list */
 
     const char        *label;
 
-    /* Entries for nesting display calculations */
+    /* Entries for nesting display calculations. Set to magic
+     * values at all other time.  */
     Memento_BlkHeader *child;
     Memento_BlkHeader *sibling;
 
@@ -189,8 +216,8 @@ struct Memento_BlkHeader
  */
 typedef struct Memento_Blocks
 {
-    Memento_BlkHeader  *head;
-    Memento_BlkHeader **tail;
+    Memento_BlkHeader *head;
+    Memento_BlkHeader *tail;
 } Memento_Blocks;
 
 /* And our global structure */
@@ -233,7 +260,7 @@ static struct {
 #define MEMBLK_FROMBLK(B)   (&((Memento_BlkHeader*)(void *)(B))[-1])
 #define MEMBLK_TOBLK(B)     ((void*)(&((Memento_BlkHeader*)(void*)(B))[1]))
 #define MEMBLK_POSTPTR(B) \
-          (&((char *)(void *)(B))[(B)->rawsize + sizeof(Memento_BlkHeader)])
+          (&((unsigned char *)(void *)(B))[(B)->rawsize + sizeof(Memento_BlkHeader)])
 
 void Memento_breakpoint(void)
 {
@@ -251,11 +278,16 @@ static void Memento_addBlockHead(Memento_Blocks    *blks,
                                  Memento_BlkHeader *b,
                                  int                type)
 {
-    if (blks->tail == &blks->head) {
-        /* Adding into an empty list, means the tail changes too */
-        blks->tail = &b->next;
-    }
+    if (blks->tail == NULL)
+        blks->tail = b;
     b->next    = blks->head;
+    b->prev    = NULL;
+    if (blks->head)
+    {
+        VALGRIND_MAKE_MEM_DEFINED(&blks->head->prev, sizeof(blks->head->prev));
+        blks->head->prev = b;
+        VALGRIND_MAKE_MEM_NOACCESS(&blks->head->prev, sizeof(blks->head->prev));
+    }
     blks->head = b;
 #ifndef MEMENTO_LEAKONLY
     memset(b->preblk, MEMENTO_PREFILL, Memento_PreSize);
@@ -274,11 +306,17 @@ static void Memento_addBlockTail(Memento_Blocks    *blks,
                                  Memento_BlkHeader *b,
                                  int                type)
 {
-    VALGRIND_MAKE_MEM_DEFINED(blks->tail, sizeof(Memento_BlkHeader *));
-    *blks->tail = b;
-    blks->tail  = &b->next;
+    VALGRIND_MAKE_MEM_DEFINED(&blks->tail, sizeof(Memento_BlkHeader *));
+    if (blks->head == NULL)
+        blks->head = b;
+    b->prev = blks->tail;
     b->next = NULL;
-    VALGRIND_MAKE_MEM_NOACCESS(blks->tail, sizeof(Memento_BlkHeader *));
+    if (blks->tail) {
+        VALGRIND_MAKE_MEM_DEFINED(&blks->tail->next, sizeof(blks->tail->next));
+        blks->tail->next = b;
+        VALGRIND_MAKE_MEM_NOACCESS(&blks->tail->next, sizeof(blks->tail->next));
+    }
+    blks->tail = b;
 #ifndef MEMENTO_LEAKONLY
     memset(b->preblk, MEMENTO_PREFILL, Memento_PreSize);
     memset(MEMBLK_POSTPTR(b), MEMENTO_POSTFILL, Memento_PostSize);
@@ -290,6 +328,7 @@ static void Memento_addBlockTail(Memento_Blocks    *blks,
         VALGRIND_MAKE_MEM_NOACCESS(MEMBLK_TOBLK(b), b->rawsize);
     }
     VALGRIND_MAKE_MEM_NOACCESS(b, sizeof(Memento_BlkHeader));
+    VALGRIND_MAKE_MEM_NOACCESS(&blks->tail, sizeof(Memento_BlkHeader *));
 }
 
 typedef struct BlkCheckData {
@@ -303,25 +342,56 @@ typedef struct BlkCheckData {
 static int Memento_Internal_checkAllocedBlock(Memento_BlkHeader *b, void *arg)
 {
 #ifndef MEMENTO_LEAKONLY
-    int           i;
-    char         *p;
-    int           corrupt = 0;
-    BlkCheckData *data = (BlkCheckData *)arg;
+    int             i;
+    MEMENTO_UINT32 *ip;
+    unsigned char  *p;
+    BlkCheckData   *data = (BlkCheckData *)arg;
 
-    p = b->preblk;
-    i = Memento_PreSize;
+    ip = (MEMENTO_UINT32 *)(void *)(b->preblk);
+    i = Memento_PreSize>>2;
     do {
-        corrupt |= (*p++ ^ (char)MEMENTO_PREFILL);
+        if (*ip++ != MEMENTO_PREFILL_UINT32)
+            goto pre_corrupt;
     } while (--i);
-    if (corrupt) {
+    if (0) {
+pre_corrupt:
         data->preCorrupt = 1;
     }
+    /* Postfill may not be aligned, so have to be slower */
     p = MEMBLK_POSTPTR(b);
-    i = Memento_PreSize;
+    i = Memento_PostSize-4;
+    if ((intptr_t)p & 1)
+    {
+        if (*p++ != MEMENTO_POSTFILL)
+            goto post_corrupt;
+        i--;
+    }
+    if ((intptr_t)p & 2)
+    {
+        if (*(MEMENTO_UINT16 *)p != MEMENTO_POSTFILL_UINT16)
+            goto post_corrupt;
+        p += 2;
+        i -= 2;
+    }
     do {
-        corrupt |= (*p++ ^ (char)MEMENTO_POSTFILL);
-    } while (--i);
-    if (corrupt) {
+        if (*(MEMENTO_UINT32 *)p != MEMENTO_POSTFILL_UINT32)
+            goto post_corrupt;
+        p += 4;
+        i -= 4;
+    } while (i >= 0);
+    if (i & 2)
+    {
+        if (*(MEMENTO_UINT16 *)p != MEMENTO_POSTFILL_UINT16)
+            goto post_corrupt;
+        p += 2;
+    }
+    if (i & 1)
+    {
+        if (*p != MEMENTO_POSTFILL)
+            goto post_corrupt;
+    }
+    if (0) {
+post_corrupt:
         data->postCorrupt = 1;
     }
     if ((data->freeCorrupt | data->preCorrupt | data->postCorrupt) == 0) {
@@ -335,53 +405,32 @@ static int Memento_Internal_checkAllocedBlock(Memento_BlkHeader *b, void *arg)
 static int Memento_Internal_checkFreedBlock(Memento_BlkHeader *b, void *arg)
 {
 #ifndef MEMENTO_LEAKONLY
-    int           i;
-    char         *p;
-    BlkCheckData *data = (BlkCheckData *)arg;
+    int            i;
+    unsigned char *p;
+    BlkCheckData  *data = (BlkCheckData *)arg;
 
-    p = MEMBLK_TOBLK(b);
-    i = b->rawsize;
+    p = MEMBLK_TOBLK(b); /* p will always be aligned */
+    i = b->rawsize - 4;
     /* Attempt to speed this up by checking an (aligned) int at a time */
-    do {
-        if (((size_t)p) & 1) {
-            if (*p++ != (char)MEMENTO_FREEFILL)
-                break;
-            i--;
-            if (i == 0)
-                break;
-        }
-        if ((i >= 2) && (((size_t)p) & 2)) {
-            if (*(short *)p != (short)(MEMENTO_FREEFILL | (MEMENTO_FREEFILL<<8)))
-                goto mismatch;
-            p += 2;
-            i -= 2;
-            if (i == 0)
-                break;
-        }
+    while (i >= 0) {
+        if (*(MEMENTO_UINT32 *)p != MEMENTO_FREEFILL_UINT32)
+            goto mismatch;
+        p += 4;
         i -= 4;
-        while (i >= 0) {
-            if (*(int *)p != (MEMENTO_FREEFILL |
-                              (MEMENTO_FREEFILL<<8) |
-                              (MEMENTO_FREEFILL<<16) |
-                              (MEMENTO_FREEFILL<<24)))
-                goto mismatch;
-            p += 4;
-            i -= 4;
-        }
-        i += 4;
-        if ((i >= 2) && (((size_t)p) & 2)) {
-            if (*(short *)p != (short)(MEMENTO_FREEFILL | (MEMENTO_FREEFILL<<8)))
-                goto mismatch;
-            p += 2;
-            i -= 2;
-        }
+    }
+    i += 4;
+    if (i & 2) {
+        if (*(MEMENTO_UINT16 *)p != MEMENTO_FREEFILL_UINT16)
+            goto mismatch;
+        p += 2;
+        i -= 2;
+    }
 mismatch:
-        while (i) {
-            if (*p++ != (char)MEMENTO_FREEFILL)
-                break;
-            i--;
-        }
-    } while (0);
+    while (i) {
+        if (*p++ != (unsigned char)MEMENTO_FREEFILL)
+            break;
+        i--;
+    }
     if (i) {
         data->freeCorrupt = 1;
         data->index       = b->rawsize-i;
@@ -395,42 +444,21 @@ mismatch:
 static void Memento_removeBlock(Memento_Blocks    *blks,
                                 Memento_BlkHeader *b)
 {
-    Memento_BlkHeader *head = blks->head;
-    Memento_BlkHeader *prev = NULL;
-    while ((head) && (head != b)) {
-        VALGRIND_MAKE_MEM_DEFINED(head, sizeof(*head));
-        prev = head;
-        head = head->next;
-        VALGRIND_MAKE_MEM_NOACCESS(prev, sizeof(*prev));
-    }
-    if (head == NULL) {
-        /* FAIL! Will have been reported to user earlier, so just exit. */
-        return;
-    }
-    VALGRIND_MAKE_MEM_DEFINED(blks->tail, sizeof(*blks->tail));
-    if (*blks->tail == head) {
-        /* Removing the tail of the list */
-        if (prev == NULL) {
-            /* Which is also the head */
-            blks->tail = &blks->head;
-        } else {
-            /* Which isn't the head */
-            blks->tail = &prev->next;
-        }
+    VALGRIND_MAKE_MEM_DEFINED(b, sizeof(*b));
+    if (b->next) {
+        VALGRIND_MAKE_MEM_DEFINED(&b->next->prev, sizeof(b->next->prev));
+        b->next->prev = b->prev;
+        VALGRIND_MAKE_MEM_NOACCESS(&b->next->prev, sizeof(b->next->prev));
     }
-    if (prev == NULL) {
-        /* Removing from the head of the list */
-        VALGRIND_MAKE_MEM_DEFINED(head, sizeof(*head));
-        blks->head = head->next;
-        VALGRIND_MAKE_MEM_NOACCESS(head, sizeof(*head));
-    } else {
-        /* Removing from not-the-head */
-        VALGRIND_MAKE_MEM_DEFINED(head, sizeof(*head));
-        VALGRIND_MAKE_MEM_DEFINED(prev, sizeof(*prev));
-        prev->next = head->next;
-        VALGRIND_MAKE_MEM_NOACCESS(head, sizeof(*head));
-        VALGRIND_MAKE_MEM_NOACCESS(prev, sizeof(*prev));
+    if (b->prev) {
+        VALGRIND_MAKE_MEM_DEFINED(&b->prev->next, sizeof(b->prev->next));
+        b->prev->next = b->next;
+        VALGRIND_MAKE_MEM_NOACCESS(&b->prev->next, sizeof(b->prev->next));
     }
+    if (blks->tail == b)
+        blks->tail = b->prev;
+    if (blks->head == b)
+        blks->head = b->next;
 }
 
 static int Memento_Internal_makeSpace(size_t space)
@@ -451,7 +479,7 @@ static int Memento_Internal_makeSpace(size_t space)
     /* Make sure we haven't just completely emptied the free list */
     /* (This should never happen, but belt and braces... */
     if (globals.free.head == NULL)
-        globals.free.tail = &globals.free.head;
+        globals.free.tail = NULL;
     return 1;
 }
 
@@ -478,11 +506,12 @@ static int Memento_appBlocks(Memento_Blocks *blks,
     return 0;
 }
 
-static int Memento_appBlock(Memento_Blocks    *blks,
-                            int                (*app)(Memento_BlkHeader *,
-                                                      void *),
-                            void              *arg,
-                            Memento_BlkHeader *b)
+/* Distrustful - check the block is a real one */
+static int Memento_appBlockUser(Memento_Blocks    *blks,
+                                int                (*app)(Memento_BlkHeader *,
+                                                          void *),
+                                void              *arg,
+                                Memento_BlkHeader *b)
 {
     Memento_BlkHeader *head = blks->head;
     Memento_BlkHeader *next;
@@ -490,7 +519,7 @@ static int Memento_appBlock(Memento_Blocks    *blks,
     while (head && head != b) {
         VALGRIND_MAKE_MEM_DEFINED(head, sizeof(Memento_BlkHeader));
         next = head->next;
-        VALGRIND_MAKE_MEM_NOACCESS(MEMBLK_POSTPTR(head), Memento_PostSize);
+       VALGRIND_MAKE_MEM_NOACCESS(MEMBLK_POSTPTR(head), Memento_PostSize);
         head = next;
     }
     if (head == b) {
@@ -505,6 +534,22 @@ static int Memento_appBlock(Memento_Blocks    *blks,
     return 0;
 }
 
+static int Memento_appBlock(Memento_Blocks    *blks,
+                            int                (*app)(Memento_BlkHeader *,
+                                                      void *),
+                            void              *arg,
+                            Memento_BlkHeader *b)
+{
+    int result;
+    VALGRIND_MAKE_MEM_DEFINED(b, sizeof(Memento_BlkHeader));
+    VALGRIND_MAKE_MEM_DEFINED(MEMBLK_TOBLK(b),
+                              b->rawsize + Memento_PostSize);
+    result = app(b, arg);
+    VALGRIND_MAKE_MEM_NOACCESS(MEMBLK_POSTPTR(b), Memento_PostSize);
+    VALGRIND_MAKE_MEM_NOACCESS(b, sizeof(Memento_BlkHeader));
+    return result;
+}
+
 static void showBlock(Memento_BlkHeader *b, int space)
 {
     fprintf(stderr, "0x%p:(size=%d,num=%d)",
@@ -571,9 +616,9 @@ static
 int Memento_listBlocksNested(void)
 {
     int count, size, i;
-    Memento_BlkHeader *b;
+    Memento_BlkHeader *b, *prev;
     void **blocks, *minptr, *maxptr;
-    long mask;
+    intptr_t mask;
 
     /* Count the blocks */
     count = 0;
@@ -604,7 +649,7 @@ int Memento_listBlocksNested(void)
         b->flags &= ~Memento_Flag_HasParent;
         b->child   = NULL;
         b->sibling = NULL;
-        b->parent  = NULL;
+        b->prev    = NULL; /* parent */
     }
     qsort(blocks, count, sizeof(void *), ptrcmp);
 
@@ -617,7 +662,7 @@ int Memento_listBlocksNested(void)
             void **r;
 
             /* Do trivial checks on pointer */
-            if ((mask & (int)q) != mask || q < minptr || q > maxptr)
+            if ((mask & (intptr_t)q) != mask || q < minptr || q > maxptr)
                 continue;
 
             /* Search for pointer */
@@ -629,7 +674,7 @@ int Memento_listBlocksNested(void)
 
                 /* We're assuming tree structure, not graph - ignore second
                  * and subsequent pointers. */
-                if (child->parent != NULL)
+                if (child->prev != NULL) /* parent */
                     continue;
                 if (child->flags & Memento_Flag_HasParent)
                     continue;
@@ -640,15 +685,15 @@ int Memento_listBlocksNested(void)
 
                 /* We're also assuming acyclicness here. If this is one of
                  * our parents, ignore it. */
-                parent = b->parent;
+                parent = b->prev; /* parent */
                 while (parent != NULL && parent != child)
-                    parent = parent->parent;
+                    parent = parent->prev; /* parent */
                 if (parent == child)
                     continue;
 
                 child->sibling = b->child;
                 b->child = child;
-                child->parent = b;
+                child->prev = b; /* parent */
                 child->flags |= Memento_Flag_HasParent;
             }
         }
@@ -664,9 +709,15 @@ int Memento_listBlocksNested(void)
 
     MEMENTO_UNDERLYING_FREE(blocks);
 
-    /* Now put the blocks back for valgrind */
+    /* Now put the blocks back for valgrind, and restore the prev
+     * and magic values. */
+    prev = NULL;
     for (b = globals.used.head; b;) {
       Memento_BlkHeader *next = b->next;
+      b->prev = prev;
+      b->child = MEMENTO_CHILD_MAGIC;
+      b->sibling = MEMENTO_SIBLING_MAGIC;
+      prev = b;
       VALGRIND_MAKE_MEM_NOACCESS(b, sizeof(*b));
       b = next;
     }
@@ -697,7 +748,8 @@ static int Memento_listNewBlock(Memento_BlkHeader *b,
     return Memento_listBlock(b, arg);
 }
 
-void Memento_listNewBlocks(void) {
+void Memento_listNewBlocks(void)
+{
     int counts[2];
     counts[0] = 0;
     counts[1] = 0;
@@ -762,9 +814,9 @@ static void Memento_init(void)
     memset(&globals, 0, sizeof(globals));
     globals.inited    = 1;
     globals.used.head = NULL;
-    globals.used.tail = &globals.used.head;
+    globals.used.tail = NULL;
     globals.free.head = NULL;
-    globals.free.tail = &globals.free.head;
+    globals.free.tail = NULL;
     globals.sequence  = 0;
     globals.countdown = 1024;
 
@@ -774,7 +826,7 @@ static void Memento_init(void)
     env = getenv("MEMENTO_PARANOIA");
     globals.paranoia = (env ? atoi(env) : 0);
     if (globals.paranoia == 0)
-        globals.paranoia = 1024;
+        globals.paranoia = -1024;
 
     env = getenv("MEMENTO_PARANOIDAT");
     globals.paranoidAt = (env ? atoi(env) : 0);
@@ -950,7 +1002,14 @@ static void Memento_event(void)
     }
     if (--globals.countdown == 0) {
         Memento_checkAllMemory();
-        globals.countdown = globals.paranoia;
+        if (globals.paranoia > 0)
+            globals.countdown = globals.paranoia;
+        else
+        {
+            globals.countdown = -globals.paranoia;
+            if (globals.paranoia > INT_MIN/2)
+                globals.paranoia *= 2;
+        }
     }
 
     if (globals.sequence == globals.breakAt) {
@@ -1045,8 +1104,8 @@ void *Memento_malloc(size_t s)
     memblk->lastCheckedOK = memblk->sequence;
     memblk->flags         = 0;
     memblk->label         = 0;
-    memblk->child         = NULL;
-    memblk->sibling       = NULL;
+    memblk->child         = MEMENTO_CHILD_MAGIC;
+    memblk->sibling       = MEMENTO_SIBLING_MAGIC;
     Memento_addBlockHead(&globals.used, memblk, 0);
     return MEMBLK_TOBLK(memblk);
 }
@@ -1060,11 +1119,60 @@ void *Memento_calloc(size_t n, size_t s)
     return block;
 }
 
+/* Treat blocks from the user with suspicion, and check them the slow
+ * but safe way. */
+static int checkBlockUser(Memento_BlkHeader *memblk, const char *action)
+{
+#ifndef MEMENTO_LEAKONLY
+    BlkCheckData data;
+
+    memset(&data, 0, sizeof(data));
+    Memento_appBlockUser(&globals.used, Memento_Internal_checkAllocedBlock,
+                         &data, memblk);
+    if (!data.found) {
+        /* Failure! */
+        fprintf(stderr, "Attempt to %s block ", action);
+        showBlock(memblk, 32);
+        fprintf(stderr, "\n");
+        Memento_breakpoint();
+        return 1;
+    } else if (data.preCorrupt || data.postCorrupt) {
+        fprintf(stderr, "Block ");
+        showBlock(memblk, ' ');
+        fprintf(stderr, " found to be corrupted on %s!\n", action);
+        if (data.preCorrupt) {
+            fprintf(stderr, "Preguard corrupted\n");
+        }
+        if (data.postCorrupt) {
+            fprintf(stderr, "Postguard corrupted\n");
+        }
+        fprintf(stderr, "Block last checked OK at allocation %d. Now %d.\n",
+                memblk->lastCheckedOK, globals.sequence);
+        Memento_breakpoint();
+        return 1;
+    }
+#endif
+    return 0;
+}
+
 static int checkBlock(Memento_BlkHeader *memblk, const char *action)
 {
 #ifndef MEMENTO_LEAKONLY
     BlkCheckData data;
+#endif
 
+    if (memblk->child != MEMENTO_CHILD_MAGIC ||
+        memblk->sibling != MEMENTO_SIBLING_MAGIC)
+    {
+        /* Failure! */
+        fprintf(stderr, "Attempt to %s invalid block ", action);
+        showBlock(memblk, 32);
+        fprintf(stderr, "\n");
+        Memento_breakpoint();
+        return 1;
+    }
+
+#ifndef MEMENTO_LEAKONLY
     memset(&data, 0, sizeof(data));
     Memento_appBlock(&globals.used, Memento_Internal_checkAllocedBlock,
                      &data, memblk);
@@ -1128,6 +1236,7 @@ void Memento_free(void *blk)
 #ifndef MEMENTO_LEAKONLY
         memset(MEMBLK_TOBLK(memblk), MEMENTO_FREEFILL, memblk->rawsize);
 #endif
+        memblk->flags |= Memento_Flag_Freed;
         Memento_addBlockTail(&globals.free, memblk, 1);
     } else {
         MEMENTO_UNDERLYING_FREE(memblk);
@@ -1151,6 +1260,7 @@ void *Memento_realloc(void *blk, size_t newsize)
         return NULL;
 
     memblk     = MEMBLK_FROMBLK(blk);
+    VALGRIND_MAKE_MEM_DEFINED(memblk, sizeof(*memblk));
     if (checkBlock(memblk, "realloc"))
         return NULL;
 
@@ -1207,7 +1317,7 @@ int Memento_checkBlock(void *blk)
     if (blk == NULL)
         return 0;
     memblk = MEMBLK_FROMBLK(blk);
-    return checkBlock(memblk, "check");
+    return checkBlockUser(memblk, "check");
 }
 
 static int Memento_Internal_checkAllAlloced(Memento_BlkHeader *memblk, void *arg)
@@ -1302,7 +1412,10 @@ int Memento_checkAllMemory(void)
 int Memento_setParanoia(int i)
 {
     globals.paranoia = i;
-    globals.countdown = globals.paranoia;
+    if (globals.paranoia > 0)
+        globals.countdown = globals.paranoia;
+    else
+        globals.countdown = -globals.paranoia;
     return i;
 }
 
@@ -1482,14 +1595,14 @@ size_t Memento_setMax(size_t max)
 
 void *operator new(size_t size)
 {
-	if (size == 0)
-	size = 1;
-	return malloc(size);
+    if (size == 0)
+        size = 1;
+    return malloc(size);
 }
 
 void  operator delete(void *pointer)
 {
-	return free(pointer);
+    return free(pointer);
 }
 
 /* Some C++ systems (apparently) don't provide new[] or delete[]
@@ -1497,14 +1610,14 @@ void  operator delete(void *pointer)
 #ifndef MEMENTO_CPP_NO_ARRAY_CONSTRUCTORS
 void *operator new[](size_t size)
 {
-	if (size == 0)
-	size = 1;
-	return malloc(size);
+    if (size == 0)
+        size = 1;
+    return malloc(size);
 }
 
 void  operator delete[](void *pointer)
 {
-	return free(pointer);
+    return free(pointer);
 }
 #endif /* MEMENTO_CPP_NO_ARRAY_CONSTRUCTORS */
 #endif /* __cplusplus */