Memento: Store callstacks for events.

Add Memento_info(address) that will show the details of a block
(callstacks when it was allocatd, realloced, freed etc).

This works on MSVC and GNUC using two different methods.

1 files changed, 389 insertions, 66 deletions

diff --git a/source/fitz/memento.c b/source/fitz/memento.c
index 8af5a424..5d87c1ee 100644
--- a/source/fitz/memento.c
+++ b/source/fitz/memento.c
@@ -17,6 +17,9 @@
  * to speed the operation */
 /* #define MEMENTO_LEAKONLY */
 
+/* Set the following to keep extra details about the history of blocks */
+#define MEMENTO_DETAILS
+
 /* Don't keep blocks around if they'd mean losing more than a quarter of
  * the freelist. */
 #define MEMENTO_FREELIST_MAX_SINGLE_BLOCK (MEMENTO_FREELIST_MAX/4)
@@ -98,6 +101,9 @@ windows_fprintf(FILE *file, const char *fmt, ...)
 #ifdef __GNUC__
 #define MEMENTO_STACKTRACE_METHOD 1
 #endif
+#ifdef _WIN32
+#define MEMENTO_STACKTRACE_METHOD 2
+#endif
 #endif
 
 #if defined(__linux__)
@@ -168,6 +174,29 @@ enum {
     Memento_Flag_Freed = 16
 };
 
+enum {
+    Memento_EventType_malloc = 0,
+    Memento_EventType_calloc = 1,
+    Memento_EventType_realloc = 2,
+    Memento_EventType_free = 3,
+    Memento_EventType_new = 4,
+    Memento_EventType_delete = 5,
+    Memento_EventType_newArray = 6,
+    Memento_EventType_deleteArray = 7
+};
+
+static const char *eventType[] =
+{
+    "malloc",
+    "calloc",
+    "realloc",
+    "free",
+    "new",
+    "delete",
+    "new[]",
+    "delete[]"
+};
+
 /* When we list leaked blocks at the end of execution, we search for pointers
  * between blocks in order to be able to give a nice nested view.
  * Unfortunately, if you have are running your own allocator (such as
@@ -190,25 +219,43 @@ enum {
 #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)))
 
+#ifdef MEMENTO_DETAILS
+typedef struct Memento_BlkDetails Memento_BlkDetails;
+
+struct Memento_BlkDetails
+{
+    Memento_BlkDetails *next;
+    char                type;
+    char                count;
+    int                 sequence;
+    void               *stack[1];
+};
+#endif /* MEMENTO_DETAILS */
+
 typedef struct Memento_BlkHeader Memento_BlkHeader;
 
 struct Memento_BlkHeader
 {
-    size_t             rawsize;
-    int                sequence;
-    int                lastCheckedOK;
-    int                flags;
-    Memento_BlkHeader *next;
-    Memento_BlkHeader *prev; /* Reused as 'parent' when printing nested list */
+    size_t               rawsize;
+    int                  sequence;
+    int                  lastCheckedOK;
+    int                  flags;
+    Memento_BlkHeader   *next;
+    Memento_BlkHeader   *prev; /* Reused as 'parent' when printing nested list */
 
-    const char        *label;
+    const char          *label;
 
     /* Entries for nesting display calculations. Set to magic
      * values at all other time.  */
-    Memento_BlkHeader *child;
-    Memento_BlkHeader *sibling;
+    Memento_BlkHeader   *child;
+    Memento_BlkHeader   *sibling;
 
-    char               preblk[Memento_PreSize];
+#ifdef MEMENTO_DETAILS
+    Memento_BlkDetails  *details;
+    Memento_BlkDetails **details_tail;
+#endif
+
+    char                 preblk[Memento_PreSize];
 };
 
 /* In future this could (should) be a smarter data structure, like, say,
@@ -262,6 +309,202 @@ static struct {
 #define MEMBLK_POSTPTR(B) \
           (&((unsigned char *)(void *)(B))[(B)->rawsize + sizeof(Memento_BlkHeader)])
 
+enum
+{
+    SkipStackBackTraceLevels = 4
+};
+
+#if defined(MEMENTO_STACKTRACE_METHOD) && MEMENTO_STACKTRACE_METHOD == 1
+extern size_t backtrace(void **, int);
+extern void backtrace_symbols_fd(void **, size_t, int);
+
+static void Memento_initStacktracer(void)
+{
+}
+
+static int Memento_getStacktrace(void **stack)
+{
+    void *local[256];
+    size_t num;
+
+    num = backtrace(&local[0], 256);
+
+    if (num <= SkipStackBackTraceLevels)
+        return 0;
+    memcpy(stack, &local[SkipStackBackTraceLevels], sizeof(void *) * (num-SkipStackBackTraceLevels));
+    return (int)(num-SkipStackBackTraceLevels);
+}
+
+static void Memento_showStacktrace(void **stack, int numberOfFrames)
+{
+    backtrace_symbols_fd(stack, (size_t)numberOfFrames, 2);
+}
+#elif defined(MEMENTO_STACKTRACE_METHOD) && MEMENTO_STACKTRACE_METHOD == 2
+#include <Windows.h>
+
+/* We use DbgHelp.dll rather than DbgHelp.lib. This avoids us needing
+ * extra link time complications, and enables us to fall back gracefully
+ * if the DLL cannot be found.
+ *
+ * To achieve this we have our own potted versions of the required types
+ * inline here.
+ */
+#ifdef _WIN64
+typedef DWORD64 DWORD_NATIVESIZED;
+#else
+typedef DWORD DWORD_NATIVESIZED;
+#endif
+
+typedef USHORT (__stdcall *My_CaptureStackBackTraceType)(__in ULONG, __in ULONG, __out PVOID*, __out_opt PULONG);
+
+typedef struct MY_IMAGEHLP_LINE {
+    DWORD    SizeOfStruct;
+    PVOID    Key;
+    DWORD    LineNumber;
+    PCHAR    FileName;
+    DWORD_NATIVESIZED    Address;
+} MY_IMAGEHLP_LINE, *MY_PIMAGEHLP_LINE;
+
+typedef BOOL (__stdcall *My_SymGetLineFromAddrType)(HANDLE hProcess, DWORD_NATIVESIZED dwAddr, PDWORD pdwDisplacement, MY_PIMAGEHLP_LINE Line);
+
+typedef struct MY_SYMBOL_INFO {
+    ULONG       SizeOfStruct;
+    ULONG       TypeIndex;        // Type Index of symbol
+    ULONG64     Reserved[2];
+    ULONG       info;
+    ULONG       Size;
+    ULONG64     ModBase;          // Base Address of module comtaining this symbol
+    ULONG       Flags;
+    ULONG64     Value;            // Value of symbol, ValuePresent should be 1
+    ULONG64     Address;          // Address of symbol including base address of module
+    ULONG       Register;         // register holding value or pointer to value
+    ULONG       Scope;            // scope of the symbol
+    ULONG       Tag;              // pdb classification
+    ULONG       NameLen;          // Actual length of name
+    ULONG       MaxNameLen;
+    CHAR        Name[1];          // Name of symbol
+} MY_SYMBOL_INFO, *MY_PSYMBOL_INFO;
+
+typedef BOOL (__stdcall *My_SymFromAddrType)(HANDLE hProcess, DWORD64 Address, PDWORD64 Displacement, MY_PSYMBOL_INFO Symbol);
+typedef BOOL (__stdcall *My_SymInitializeType)(HANDLE hProcess, PSTR UserSearchPath, BOOL fInvadeProcess);
+
+static My_CaptureStackBackTraceType Memento_CaptureStackBackTrace;
+static My_SymGetLineFromAddrType Memento_SymGetLineFromAddr;
+static My_SymFromAddrType Memento_SymFromAddr;
+static My_SymInitializeType Memento_SymInitialize;
+static HANDLE Memento_process;
+
+static void Memento_initStacktracer(void)
+{
+    HMODULE mod = LoadLibrary("kernel32.dll");
+
+    if (mod == NULL)
+        return;
+    Memento_CaptureStackBackTrace = (My_CaptureStackBackTraceType)(GetProcAddress(mod, "RtlCaptureStackBackTrace"));
+    if (Memento_CaptureStackBackTrace == NULL)
+        return;
+    mod = LoadLibrary("Dbghelp.dll");
+    if (mod == NULL) {
+        Memento_CaptureStackBackTrace = NULL;
+        return;
+    }
+    Memento_SymGetLineFromAddr =
+            (My_SymGetLineFromAddrType)(GetProcAddress(mod,
+#ifdef _WIN64
+                                                       "SymGetLineFromAddr64"
+#else
+                                                       "SymGetLineFromAddr"
+#endif
+                                        ));
+    if (Memento_SymGetLineFromAddr == NULL) {
+        Memento_CaptureStackBackTrace = NULL;
+        return;
+    }
+    Memento_SymFromAddr = (My_SymFromAddrType)(GetProcAddress(mod, "SymFromAddr"));
+    if (Memento_SymFromAddr == NULL) {
+        Memento_CaptureStackBackTrace = NULL;
+        return;
+    }
+    Memento_SymInitialize = (My_SymInitializeType)(GetProcAddress(mod, "SymInitialize"));
+    if (Memento_SymInitialize == NULL) {
+        Memento_CaptureStackBackTrace = NULL;
+        return;
+    }
+    Memento_process = GetCurrentProcess();
+    Memento_SymInitialize(Memento_process, NULL, TRUE);
+}
+
+static int Memento_getStacktrace(void **stack)
+{
+    if (Memento_CaptureStackBackTrace == NULL)
+        return 0;
+
+    return Memento_CaptureStackBackTrace(SkipStackBackTraceLevels, 63-SkipStackBackTraceLevels, stack, NULL);
+}
+
+static void Memento_showStacktrace(void **stack, int numberOfFrames)
+{
+    MY_IMAGEHLP_LINE line;
+    int i;
+    char symbol_buffer[sizeof(MY_SYMBOL_INFO) + 1024 + 1];
+    MY_SYMBOL_INFO *symbol = (MY_SYMBOL_INFO *)symbol_buffer;
+
+    symbol->MaxNameLen = 1024;
+    symbol->SizeOfStruct = sizeof(MY_SYMBOL_INFO);
+    line.SizeOfStruct = sizeof(MY_IMAGEHLP_LINE);
+    for (i = 0; i < numberOfFrames; i++)
+    {
+        DWORD64 dwDisplacement64;
+        DWORD dwDisplacement;
+        Memento_SymFromAddr(Memento_process, (DWORD64)(stack[i]), &dwDisplacement64, symbol);
+        Memento_SymGetLineFromAddr(Memento_process, (DWORD_NATIVESIZED)(stack[i]), &dwDisplacement, &line);
+        fprintf(stderr, "    %s in %s:%d\n", symbol->Name, line.FileName, line.LineNumber);
+    }
+}
+#else
+static void Memento_initStacktracer(void)
+{
+}
+
+static int Memento_getStacktrace(void **stack)
+{
+    return 0;
+}
+
+static void Memento_showStacktrace(void **stack, int numberOfFrames)
+{
+}
+#endif /* MEMENTO_STACKTRACE_METHOD */
+
+#ifdef MEMENTO_DETAILS
+static void Memento_storeDetails(Memento_BlkHeader *head, int type)
+{
+    void *stack[64];
+    Memento_BlkDetails *details;
+    int count;
+
+#ifdef MEMENTO_STACKTRACE_METHOD
+    count = Memento_getStacktrace(stack);
+#else
+    count = 0;
+#endif
+
+    details = MEMENTO_UNDERLYING_MALLOC(sizeof(*details) + (count-1) * sizeof(void *));
+    if (details == NULL)
+        return;
+
+    if (count)
+        memcpy(&details->stack, stack, count * sizeof(void *));
+
+    details->type = type;
+    details->count = count;
+    details->sequence = globals.sequence;
+    details->next = NULL;
+    *head->details_tail = details;
+    head->details_tail = &details->next;
+}
+#endif
+
 void Memento_breakpoint(void)
 {
     /* A handy externally visible function for breakpointing */
@@ -461,6 +704,21 @@ static void Memento_removeBlock(Memento_Blocks    *blks,
         blks->head = b->next;
 }
 
+static void free_block(Memento_BlkHeader *head)
+{
+#ifdef MEMENTO_DETAILS
+    Memento_BlkDetails *details = head->details;
+
+    while (details)
+    {
+        Memento_BlkDetails *next = details->next;
+        MEMENTO_UNDERLYING_FREE(details);
+        details = next;
+    }
+#endif
+    MEMENTO_UNDERLYING_FREE(head);
+}
+
 static int Memento_Internal_makeSpace(size_t space)
 {
     /* If too big, it can never go on the freelist */
@@ -474,7 +732,7 @@ static int Memento_Internal_makeSpace(size_t space)
         VALGRIND_MAKE_MEM_DEFINED(head, sizeof(*head));
         globals.free.head = head->next;
         globals.freeListSize -= MEMBLK_SIZE(head->rawsize);
-        MEMENTO_UNDERLYING_FREE(head);
+        free_block(head);
     }
     /* Make sure we haven't just completely emptied the free list */
     /* (This should never happen, but belt and braces... */
@@ -842,9 +1100,85 @@ static void Memento_init(void)
 
     atexit(Memento_fin);
 
+    Memento_initStacktracer();
+
     Memento_inited();
 }
 
+typedef struct findBlkData {
+    void              *addr;
+    Memento_BlkHeader *blk;
+    int                flags;
+} findBlkData;
+
+static int Memento_containsAddr(Memento_BlkHeader *b,
+                                void *arg)
+{
+    findBlkData *data = (findBlkData *)arg;
+    char *blkend = &((char *)MEMBLK_TOBLK(b))[b->rawsize];
+    if ((MEMBLK_TOBLK(b) <= data->addr) &&
+        ((void *)blkend > data->addr)) {
+        data->blk = b;
+        data->flags = 1;
+        return 1;
+    }
+    if (((void *)b <= data->addr) &&
+        (MEMBLK_TOBLK(b) > data->addr)) {
+        data->blk = b;
+        data->flags = 2;
+        return 1;
+    }
+    if (((void *)blkend <= data->addr) &&
+        ((void *)(blkend + Memento_PostSize) > data->addr)) {
+        data->blk = b;
+        data->flags = 3;
+        return 1;
+    }
+    return 0;
+}
+
+#ifdef MEMENTO_DETAILS
+static void showInfo(Memento_BlkHeader *b)
+{
+    Memento_BlkDetails *details;
+
+    fprintf(stderr, "0x%p:(size=%d,num=%d)",
+            MEMBLK_TOBLK(b), (int)b->rawsize, b->sequence);
+    if (b->label)
+        fprintf(stderr, " (%s)", b->label);
+    fprintf(stderr, "\nEvents:\n");
+
+    details = b->details;
+    while (details)
+    {
+      fprintf(stderr, "  Event %d (%s)\n", details->sequence, eventType[(int)details->type]);
+        Memento_showStacktrace(details->stack, details->count);
+        details = details->next;
+    }
+}
+#endif
+
+void Memento_info(void *addr)
+{
+#ifdef MEMENTO_DETAILS
+    findBlkData data;
+
+    data.addr  = addr;
+    data.blk   = NULL;
+    data.flags = 0;
+    Memento_appBlocks(&globals.used, Memento_containsAddr, &data);
+    if (data.blk != NULL)
+        showInfo(data.blk);
+    data.blk   = NULL;
+    data.flags = 0;
+    Memento_appBlocks(&globals.free, Memento_containsAddr, &data);
+    if (data.blk != NULL)
+        showInfo(data.blk);
+#else
+    printf("Memento not compiled with details support\n");
+#endif
+}
+
 #ifdef MEMENTO_HAS_FORK
 #include <unistd.h>
 #include <sys/wait.h>
@@ -861,13 +1195,6 @@ static void Memento_init(void)
 /* stashed_map[j] = i means that filedescriptor i-1 was duplicated to j */
 int stashed_map[OPEN_MAX];
 
-#ifdef MEMENTO_STACKTRACE_METHOD
-#if MEMENTO_STACKTRACE_METHOD == 1
-extern size_t backtrace(void **, int);
-extern void backtrace_symbols_fd(void **, size_t, int);
-#endif
-#endif
-
 static void Memento_signal(void)
 {
     fprintf(stderr, "SEGV after Memory squeezing @ %d\n", globals.squeezeAt);
@@ -1072,7 +1399,7 @@ int Memento_failThisEvent(void)
     return failThisOne;
 }
 
-void *Memento_malloc(size_t s)
+static void *do_malloc(size_t s, int eventType)
 {
     Memento_BlkHeader *memblk;
     size_t             smem = MEMBLK_SIZE(s);
@@ -1106,13 +1433,23 @@ void *Memento_malloc(size_t s)
     memblk->label         = 0;
     memblk->child         = MEMENTO_CHILD_MAGIC;
     memblk->sibling       = MEMENTO_SIBLING_MAGIC;
+#ifdef MEMENTO_DETAILS
+    memblk->details       = NULL;
+    memblk->details_tail  = &memblk->details;
+    Memento_storeDetails(memblk, Memento_EventType_malloc);
+#endif /* MEMENTO_DETAILS */
     Memento_addBlockHead(&globals.used, memblk, 0);
     return MEMBLK_TOBLK(memblk);
 }
 
+void *Memento_malloc(size_t s)
+{
+    return do_malloc(s, Memento_EventType_malloc);
+}
+
 void *Memento_calloc(size_t n, size_t s)
 {
-    void *block = Memento_malloc(n*s);
+    void *block = do_malloc(n*s, Memento_EventType_calloc);
 
     if (block)
         memset(block, 0, n*s);
@@ -1202,7 +1539,7 @@ static int checkBlock(Memento_BlkHeader *memblk, const char *action)
     return 0;
 }
 
-void Memento_free(void *blk)
+static void do_free(void *blk, int eventType)
 {
     Memento_BlkHeader *memblk;
 
@@ -1219,6 +1556,10 @@ void Memento_free(void *blk)
     if (checkBlock(memblk, "free"))
         return;
 
+#ifdef MEMENTO_DETAILS
+    Memento_storeDetails(memblk, Memento_EventType_free);
+#endif
+
     VALGRIND_MAKE_MEM_DEFINED(memblk, sizeof(*memblk));
     if (memblk->flags & Memento_Flag_BreakOnFree)
         Memento_breakpoint();
@@ -1239,23 +1580,21 @@ void Memento_free(void *blk)
         memblk->flags |= Memento_Flag_Freed;
         Memento_addBlockTail(&globals.free, memblk, 1);
     } else {
-        MEMENTO_UNDERLYING_FREE(memblk);
+        free_block(memblk);
     }
 }
 
-void *Memento_realloc(void *blk, size_t newsize)
+void Memento_free(void *blk)
+{
+    do_free(blk, Memento_EventType_free);
+}
+
+static void *do_realloc(void *blk, size_t newsize, int type)
 {
     Memento_BlkHeader *memblk, *newmemblk;
     size_t             newsizemem;
     int                flags;
 
-    if (blk == NULL)
-        return Memento_malloc(newsize);
-    if (newsize == 0) {
-        Memento_free(blk);
-        return NULL;
-    }
-
     if (Memento_failThisEvent())
         return NULL;
 
@@ -1264,6 +1603,10 @@ void *Memento_realloc(void *blk, size_t newsize)
     if (checkBlock(memblk, "realloc"))
         return NULL;
 
+#ifdef MEMENTO_DETAILS
+    Memento_storeDetails(memblk, type);
+#endif
+
     VALGRIND_MAKE_MEM_DEFINED(memblk, sizeof(*memblk));
     if (memblk->flags & Memento_Flag_BreakOnRealloc)
         Memento_breakpoint();
@@ -1310,6 +1653,18 @@ void *Memento_realloc(void *blk, size_t newsize)
     return MEMBLK_TOBLK(newmemblk);
 }
 
+void *Memento_realloc(void *blk, size_t newsize)
+{
+    if (blk == NULL)
+        return do_malloc(newsize, Memento_EventType_realloc);
+    if (newsize == 0) {
+        do_free(blk, Memento_EventType_realloc);
+        return NULL;
+    }
+
+    return do_realloc(blk, newsize, Memento_EventType_realloc);
+}
+
 int Memento_checkBlock(void *blk)
 {
     Memento_BlkHeader *memblk;
@@ -1444,38 +1799,6 @@ int Memento_check(void)
     return result;
 }
 
-typedef struct findBlkData {
-    void              *addr;
-    Memento_BlkHeader *blk;
-    int                flags;
-} findBlkData;
-
-static int Memento_containsAddr(Memento_BlkHeader *b,
-                                void *arg)
-{
-    findBlkData *data = (findBlkData *)arg;
-    char *blkend = &((char *)MEMBLK_TOBLK(b))[b->rawsize];
-    if ((MEMBLK_TOBLK(b) <= data->addr) &&
-        ((void *)blkend > data->addr)) {
-        data->blk = b;
-        data->flags = 1;
-        return 1;
-    }
-    if (((void *)b <= data->addr) &&
-        (MEMBLK_TOBLK(b) > data->addr)) {
-        data->blk = b;
-        data->flags = 2;
-        return 1;
-    }
-    if (((void *)blkend <= data->addr) &&
-        ((void *)(blkend + Memento_PostSize) > data->addr)) {
-        data->blk = b;
-        data->flags = 3;
-        return 1;
-    }
-    return 0;
-}
-
 int Memento_find(void *a)
 {
     findBlkData data;
@@ -1597,12 +1920,12 @@ void *operator new(size_t size)
 {
     if (size == 0)
         size = 1;
-    return malloc(size);
+    return do_malloc(size, Memento_EventType_new);
 }
 
 void  operator delete(void *pointer)
 {
-    return free(pointer);
+    return do_free(pointer, Memento_EventType_delete);
 }
 
 /* Some C++ systems (apparently) don't provide new[] or delete[]
@@ -1612,12 +1935,12 @@ void *operator new[](size_t size)
 {
     if (size == 0)
         size = 1;
-    return malloc(size);
+    return do_malloc(size, Memento_EventType_newArray);
 }
 
 void  operator delete[](void *pointer)
 {
-    return free(pointer);
+    return do_free(pointer, Memento_EventType_deleteArray);
 }
 #endif /* MEMENTO_CPP_NO_ARRAY_CONSTRUCTORS */
 #endif /* __cplusplus */