Hi,

Now that the latest chunk scan optimization diff is committed, it's
time to present a malloc feature diff. 

This diff adds instrumentation to a MALLOC_STATS enabled malloc.c to
detect and report memory leaks, including the address of the code that
allocated memory that was not freed. With the help of gdb, you can
translate this address into a source file location. 

For instructions and to show some of the possibilities, check

        http://www.drijf.net/malloc/

Diff also below. It was good fun working on this, and I hope you'll
enjoy it as well.

Note that this diff a a bit bigger than strictly needed, I moved the
stats reporting code to the bottom of the file. Something I wanted to
do for a long time. 

        -Otto

Index: malloc.c
===================================================================
RCS file: /cvs/src/lib/libc/stdlib/malloc.c,v
retrieving revision 1.130
diff -u -p -r1.130 malloc.c
--- malloc.c    5 May 2011 12:11:20 -0000       1.130
+++ malloc.c    5 May 2011 12:14:51 -0000
@@ -43,6 +43,7 @@
 #include <unistd.h>
 
 #ifdef MALLOC_STATS
+#include <sys/tree.h>
 #include <fcntl.h>
 #endif
 
@@ -94,6 +95,9 @@
 struct region_info {
        void *p;                /* page; low bits used to mark chunks */
        uintptr_t size;         /* size for pages, or chunk_info pointer */
+#ifdef MALLOC_STATS
+       void *f;                /* where allocated from */
+#endif
 };
 
 LIST_HEAD(chunk_head, chunk_info);
@@ -125,9 +129,11 @@ struct dir_info {
        size_t cheap_reallocs;
 #define STATS_INC(x) ((x)++)
 #define STATS_ZERO(x) ((x) = 0)
+#define STATS_SETF(x,y) ((x)->f = (y))
 #else
 #define STATS_INC(x)   /* nothing */
 #define STATS_ZERO(x)  /* nothing */
+#define STATS_SETF(x,y)        /* nothing */
 #endif /* MALLOC_STATS */
        u_int32_t canary2;
 };
@@ -143,6 +149,9 @@ struct dir_info {
 struct chunk_info {
        LIST_ENTRY(chunk_info) entries;
        void *page;                     /* pointer to the page */
+#ifdef MALLOC_STATS
+       void *f;
+#endif
        u_int32_t canary;
        u_short size;                   /* size of this page's chunks */
        u_short shift;                  /* how far to shift for this size */
@@ -192,6 +201,14 @@ static u_char getrnibble(void);
 
 extern char    *__progname;
 
+#ifdef MALLOC_STATS
+void malloc_dump(int);
+static void malloc_exit(void);
+#define CALLER __builtin_return_address(0)
+#else
+#define CALLER NULL
+#endif
+
 /* low bits of r->p determine size: 0 means >= page size and p->size holding
  *  real size, otherwise r->size is a shift count, or 1 for malloc(0)
  */
@@ -217,142 +234,6 @@ hash(void *p)
        return sum;
 }
 
-#ifdef MALLOC_STATS
-static void
-dump_chunk(int fd, struct chunk_info *p, int fromfreelist)
-{
-       char buf[64];
-
-       while (p != NULL) {
-               snprintf(buf, sizeof(buf), "chunk %d %d/%d %p\n", p->size,
-                   p->free, p->total, p->page);
-               write(fd, buf, strlen(buf));
-               if (!fromfreelist)
-                       break;
-               p = LIST_NEXT(p, entries);
-               if (p != NULL) {
-                       snprintf(buf, sizeof(buf), "    ");
-                       write(fd, buf, strlen(buf));
-               }
-       }
-}
-
-static void
-dump_free_chunk_info(int fd, struct dir_info *d)
-{
-       char buf[64];
-       int i;
-
-       snprintf(buf, sizeof(buf), "Free chunk structs:\n");
-       write(fd, buf, strlen(buf));
-       for (i = 0; i < MALLOC_MAXSHIFT; i++) {
-               struct chunk_info *p = LIST_FIRST(&d->chunk_dir[i]);
-               if (p != NULL) {
-                       snprintf(buf, sizeof(buf), "%2d) ", i);
-                       write(fd, buf, strlen(buf));
-                       dump_chunk(fd, p, 1);
-               }
-       }
-
-}
-
-static void
-dump_free_page_info(int fd, struct dir_info *d)
-{
-       char buf[64];
-       int i;
-
-       snprintf(buf, sizeof(buf), "Free pages cached: %zu\n",
-           d->free_regions_size);
-       write(fd, buf, strlen(buf));
-       for (i = 0; i < mopts.malloc_cache; i++) {
-               if (d->free_regions[i].p != NULL) {
-                       snprintf(buf, sizeof(buf), "%2d) ", i);
-                       write(fd, buf, strlen(buf));
-                       snprintf(buf, sizeof(buf), "free at %p: %zu\n",
-                           d->free_regions[i].p, d->free_regions[i].size);
-                       write(fd, buf, strlen(buf));
-               }
-       }
-}
-
-static void
-malloc_dump1(int fd, struct dir_info *d)
-{
-       char buf[64];
-       size_t i, realsize;
-
-       snprintf(buf, sizeof(buf), "Malloc dir of %s at %p\n", __progname, d);
-       write(fd, buf, strlen(buf));
-       if (d == NULL)
-               return;
-       snprintf(buf, sizeof(buf), "Regions slots %zu\n", d->regions_total);
-       write(fd, buf, strlen(buf));
-       snprintf(buf, sizeof(buf), "Finds %zu/%zu %f\n", d->finds,
-           d->find_collisions,
-           1.0 + (double)d->find_collisions / d->finds);
-       write(fd, buf, strlen(buf));
-       snprintf(buf, sizeof(buf), "Inserts %zu/%zu %f\n", d->inserts,
-           d->insert_collisions,
-           1.0 + (double)d->insert_collisions / d->inserts);
-       write(fd, buf, strlen(buf));
-       snprintf(buf, sizeof(buf), "Deletes %zu/%zu\n", d->deletes,
-            d->delete_moves);
-       write(fd, buf, strlen(buf));
-       snprintf(buf, sizeof(buf), "Cheap reallocs %zu/%zu\n",
-           d->cheap_reallocs, d->cheap_realloc_tries);
-       write(fd, buf, strlen(buf));
-       snprintf(buf, sizeof(buf), "Regions slots free %zu\n", d->regions_free);
-       write(fd, buf, strlen(buf));
-       for (i = 0; i < d->regions_total; i++) {
-               if (d->r[i].p != NULL) {
-                       size_t h = hash(d->r[i].p) &
-                           (d->regions_total - 1);
-                       snprintf(buf, sizeof(buf), "%4zx) #%zx %zd ",
-                           i, h, h - i);
-                       write(fd, buf, strlen(buf));
-                       REALSIZE(realsize, &d->r[i]);
-                       if (realsize > MALLOC_MAXCHUNK) {
-                               snprintf(buf, sizeof(buf),
-                                   "%p: %zu\n", d->r[i].p, realsize);
-                               write(fd, buf, strlen(buf));
-                       } else
-                               dump_chunk(fd,
-                                   (struct chunk_info *)d->r[i].size, 0);
-               }
-       }
-       dump_free_chunk_info(fd, d);
-       dump_free_page_info(fd, d);
-       snprintf(buf, sizeof(buf), "In use %zu\n", malloc_used);
-       write(fd, buf, strlen(buf));
-       snprintf(buf, sizeof(buf), "Guarded %zu\n", malloc_guarded);
-       write(fd, buf, strlen(buf));
-}
-
-
-void
-malloc_dump(int fd)
-{
-       malloc_dump1(fd, g_pool);
-}
-
-static void
-malloc_exit(void)
-{
-       static const char q[] = "malloc() warning: Couldn't dump stats\n";
-       int save_errno = errno, fd;
-
-       fd = open("malloc.out", O_RDWR|O_APPEND);
-       if (fd != -1) {
-               malloc_dump(fd);
-               close(fd);
-       } else
-               write(STDERR_FILENO, q, sizeof(q) - 1);
-       errno = save_errno;
-}
-#endif /* MALLOC_STATS */
-
-
 static void
 wrterror(char *msg, void *p)
 {
@@ -827,7 +708,7 @@ alloc_chunk_info(struct dir_info *d)
 }
 
 static int
-insert(struct dir_info *d, void *p, size_t sz)
+insert(struct dir_info *d, void *p, size_t sz, void *f)
 {
        size_t index;
        size_t mask;
@@ -848,6 +729,9 @@ insert(struct dir_info *d, void *p, size
        }
        d->r[index].p = p;
        d->r[index].size = sz;
+#ifdef MALLOC_STATS
+       d->r[index].f = f;
+#endif
        d->regions_free--;
        return 0;
 }
@@ -970,7 +854,7 @@ omalloc_make_chunks(struct dir_info *d, 
        if ((uintptr_t)pp & bits)
                wrterror("pp & bits", pp);
 
-       insert(d, (void *)((uintptr_t)pp | bits), (uintptr_t)bp);
+       insert(d, (void *)((uintptr_t)pp | bits), (uintptr_t)bp, NULL);
        return bp;
 }
 
@@ -979,7 +863,7 @@ omalloc_make_chunks(struct dir_info *d, 
  * Allocate a chunk
  */
 static void *
-malloc_bytes(struct dir_info *d, size_t size)
+malloc_bytes(struct dir_info *d, size_t size, void *f)
 {
        int             i, j;
        size_t          k;
@@ -1039,6 +923,10 @@ malloc_bytes(struct dir_info *d, size_t 
                        i = 0;
        }
        d->chunk_start += i + 1;
+#ifdef MALLOC_STATS
+       if (i == 0)
+               bp->f = f;
+#endif
 
        *lp ^= u;
 
@@ -1111,7 +999,7 @@ free_bytes(struct dir_info *d, struct re
 
 
 static void *
-omalloc(size_t sz, int zero_fill)
+omalloc(size_t sz, int zero_fill, void *f)
 {
        void *p;
        size_t psz;
@@ -1128,7 +1016,7 @@ omalloc(size_t sz, int zero_fill)
                        errno = ENOMEM;
                        return NULL;
                }
-               if (insert(g_pool, p, sz)) {
+               if (insert(g_pool, p, sz, f)) {
                        unmap(g_pool, p, psz);
                        errno = ENOMEM;
                        return NULL;
@@ -1165,7 +1053,7 @@ omalloc(size_t sz, int zero_fill)
 
        } else {
                /* takes care of SOME_JUNK */
-               p = malloc_bytes(g_pool, sz);
+               p = malloc_bytes(g_pool, sz, f);
                if (zero_fill && p != NULL && sz > 0)
                        memset(p, 0, sz);
        }
@@ -1221,7 +1109,7 @@ malloc(size_t size)
                malloc_recurse();
                return NULL;
        }
-       r = omalloc(size, mopts.malloc_zero);
+       r = omalloc(size, mopts.malloc_zero, CALLER);
        malloc_active--;
        _MALLOC_UNLOCK();
        if (r == NULL && mopts.malloc_xmalloc) {
@@ -1329,14 +1217,14 @@ free(void *ptr)
 
 
 static void *
-orealloc(void *p, size_t newsz)
+orealloc(void *p, size_t newsz, void *f)
 {
        struct region_info *r;
        size_t oldsz, goldsz, gnewsz;
        void *q;
 
        if (p == NULL)
-               return omalloc(newsz, 0);
+               return omalloc(newsz, 0, f);
 
        r = find(g_pool, p);
        if (r == NULL) {
@@ -1376,6 +1264,7 @@ orealloc(void *p, size_t newsz)
                                                memset(q, SOME_JUNK,
                                                    rnewsz - roldsz);
                                        r->size = newsz;
+                                       STATS_SETF(r, f);
                                        STATS_INC(g_pool->cheap_reallocs);
                                        return p;
                                } else if (q != MAP_FAILED)
@@ -1394,29 +1283,34 @@ orealloc(void *p, size_t newsz)
                        }
                        unmap(g_pool, (char *)p + rnewsz, roldsz - rnewsz);
                        r->size = gnewsz;
+                       STATS_SETF(r, f);
                        return p;
                } else {
                        if (newsz > oldsz && mopts.malloc_junk)
                                memset((char *)p + newsz, SOME_JUNK,
                                    rnewsz - mopts.malloc_guard - newsz);
                        r->size = gnewsz;
+                       STATS_SETF(r, f);
                        return p;
                }
        }
        if (newsz <= oldsz && newsz > oldsz / 2 && !mopts.malloc_realloc) {
                if (mopts.malloc_junk && newsz > 0)
                        memset((char *)p + newsz, SOME_JUNK, oldsz - newsz);
+               STATS_SETF(r, f);
                return p;
        } else if (newsz != oldsz || mopts.malloc_realloc) {
-               q = omalloc(newsz, 0);
+               q = omalloc(newsz, 0, f);
                if (q == NULL)
                        return NULL;
                if (newsz != 0 && oldsz != 0)
                        memcpy(q, p, oldsz < newsz ? oldsz : newsz);
                ofree(p);
                return q;
-       } else
+       } else {
+               STATS_SETF(r, f);
                return p;
+       }
 }
 
 void *
@@ -1435,7 +1329,7 @@ realloc(void *ptr, size_t size)
                malloc_recurse();
                return NULL;
        }
-       r = orealloc(ptr, size);
+       r = orealloc(ptr, size, CALLER);
   
        malloc_active--;
        _MALLOC_UNLOCK();
@@ -1478,7 +1372,7 @@ calloc(size_t nmemb, size_t size)
        }
 
        size *= nmemb;
-       r = omalloc(size, 1);
+       r = omalloc(size, 1, CALLER);
   
        malloc_active--;
        _MALLOC_UNLOCK();
@@ -1516,3 +1410,246 @@ posix_memalign(void **memptr, size_t ali
        return 0;
 }
 
+#ifdef MALLOC_STATS
+
+struct malloc_leak {
+       void (*f)();
+       size_t total_size;
+       int count;
+};
+
+struct leaknode {
+       RB_ENTRY(leaknode) entry;
+       struct malloc_leak d;
+};
+
+static int
+leakcmp(struct leaknode *e1, struct leaknode *e2)
+{
+       return (e1->d.f < e2->d.f ? -1 : e1->d.f > e2->d.f);
+}
+
+static RB_HEAD(leaktree, leaknode) leakhead;
+RB_GENERATE_STATIC(leaktree, leaknode, entry, leakcmp)
+
+
+static void
+putleakinfo(void *f, size_t sz, int cnt)
+{
+       struct leaknode key, *p;
+       static struct leaknode *page;
+       static int used;
+
+       key.d.f = f;
+       p = RB_FIND(leaktree, &leakhead, &key);
+       if (p == NULL) {
+               if (p == NULL ||
+                   used >= MALLOC_PAGESIZE / sizeof(struct leaknode)) {
+                   page = MMAP(MALLOC_PAGESIZE);
+                   if (page == MAP_FAILED)
+                       return;
+                   used = 0;
+               }
+               p = &page[used++];
+               p->d.f = f;
+               p->d.total_size = sz * cnt;
+               p->d.count = cnt;
+               RB_INSERT(leaktree, &leakhead, p);
+       } else {
+               p->d.total_size += sz * cnt;
+               p->d.count += cnt;
+       }
+}
+
+static struct malloc_leak *malloc_leaks;
+
+static void
+dump_leaks(int fd)
+{
+       struct leaknode *p;
+       char buf[64];
+       int i = 0;
+
+       snprintf(buf, sizeof(buf), "Leak report\n");
+       write(fd, buf, strlen(buf));
+       snprintf(buf, sizeof(buf), "           f     sum      #    avg\n");
+       write(fd, buf, strlen(buf));
+       // XXX
+       malloc_leaks = MMAP(MALLOC_PAGESIZE);
+       RB_FOREACH(p, leaktree, &leakhead) {
+               snprintf(buf, sizeof(buf), "%12p %7zu %6u %6zu\n", p->d.f,
+                   p->d.total_size, p->d.count, p->d.total_size / p->d.count);
+               write(fd, buf, strlen(buf));
+               if (i >= MALLOC_PAGESIZE / sizeof(struct malloc_leak))
+                       continue;
+               malloc_leaks[i].f = p->d.f;
+               malloc_leaks[i].total_size = p->d.total_size;
+               malloc_leaks[i].count = p->d.count;
+               i++;
+       }
+}
+
+static void
+dump_chunk(int fd, struct chunk_info *p, int fromfreelist)
+{
+       char buf[64];
+
+       while (p != NULL) {
+               snprintf(buf, sizeof(buf), "chunk %12p %12p %4d %d/%d\n",
+                   p->page, ((p->bits[0] & 1) ? NULL : p->f),
+                   p->size, p->free, p->total);
+               write(fd, buf, strlen(buf));
+               if (!fromfreelist) {
+                       if (p->bits[0] & 1) 
+                               putleakinfo(NULL, p->size, p->total - p->free);
+                       else {
+                               putleakinfo(p->f, p->size, 1);
+                               putleakinfo(NULL, p->size,
+                                   p->total - p->free - 1);
+                       }
+                       break;
+               }
+               p = LIST_NEXT(p, entries);
+               if (p != NULL) {
+                       snprintf(buf, sizeof(buf), "    ");
+                       write(fd, buf, strlen(buf));
+               }
+       }
+}
+
+static void
+dump_free_chunk_info(int fd, struct dir_info *d)
+{
+       char buf[64];
+       int i;
+
+       snprintf(buf, sizeof(buf), "Free chunk structs:\n");
+       write(fd, buf, strlen(buf));
+       for (i = 0; i < MALLOC_MAXSHIFT; i++) {
+               struct chunk_info *p = LIST_FIRST(&d->chunk_dir[i]);
+               if (p != NULL) {
+                       snprintf(buf, sizeof(buf), "%2d) ", i);
+                       write(fd, buf, strlen(buf));
+                       dump_chunk(fd, p, 1);
+               }
+       }
+
+}
+
+static void
+dump_free_page_info(int fd, struct dir_info *d)
+{
+       char buf[64];
+       int i;
+
+       snprintf(buf, sizeof(buf), "Free pages cached: %zu\n",
+           d->free_regions_size);
+       write(fd, buf, strlen(buf));
+       for (i = 0; i < mopts.malloc_cache; i++) {
+               if (d->free_regions[i].p != NULL) {
+                       snprintf(buf, sizeof(buf), "%2d) ", i);
+                       write(fd, buf, strlen(buf));
+                       snprintf(buf, sizeof(buf), "free at %p: %zu\n",
+                           d->free_regions[i].p, d->free_regions[i].size);
+                       write(fd, buf, strlen(buf));
+               }
+       }
+}
+
+static void
+malloc_dump1(int fd, struct dir_info *d)
+{
+       char buf[64];
+       size_t i, realsize;
+
+       snprintf(buf, sizeof(buf), "Malloc dir of %s at %p\n", __progname, d);
+       write(fd, buf, strlen(buf));
+       if (d == NULL)
+               return;
+       snprintf(buf, sizeof(buf), "Regions slots %zu\n", d->regions_total);
+       write(fd, buf, strlen(buf));
+       snprintf(buf, sizeof(buf), "Finds %zu/%zu %f\n", d->finds,
+           d->find_collisions,
+           1.0 + (double)d->find_collisions / d->finds);
+       write(fd, buf, strlen(buf));
+       snprintf(buf, sizeof(buf), "Inserts %zu/%zu %f\n", d->inserts,
+           d->insert_collisions,
+           1.0 + (double)d->insert_collisions / d->inserts);
+       write(fd, buf, strlen(buf));
+       snprintf(buf, sizeof(buf), "Deletes %zu/%zu\n", d->deletes,
+            d->delete_moves);
+       write(fd, buf, strlen(buf));
+       snprintf(buf, sizeof(buf), "Cheap reallocs %zu/%zu\n",
+           d->cheap_reallocs, d->cheap_realloc_tries);
+       write(fd, buf, strlen(buf));
+       snprintf(buf, sizeof(buf), "Regions slots free %zu\n", d->regions_free);
+       write(fd, buf, strlen(buf));
+       dump_free_chunk_info(fd, d);
+       dump_free_page_info(fd, d);
+       snprintf(buf, sizeof(buf),
+           "slot)  hash d  type         page            f size [free/n]\n");
+       write(fd, buf, strlen(buf));
+       for (i = 0; i < d->regions_total; i++) {
+               if (d->r[i].p != NULL) {
+                       size_t h = hash(d->r[i].p) &
+                           (d->regions_total - 1);
+                       snprintf(buf, sizeof(buf), "%4zx) #%4zx %zd ",
+                           i, h, h - i);
+                       write(fd, buf, strlen(buf));
+                       REALSIZE(realsize, &d->r[i]);
+                       if (realsize > MALLOC_MAXCHUNK) {
+                               putleakinfo(d->r[i].f, realsize, 1);
+                               snprintf(buf, sizeof(buf),
+                                   "pages %12p %12p %zu\n", d->r[i].p, 
+                                   d->r[i].f, realsize);
+                               write(fd, buf, strlen(buf));
+                       } else
+                               dump_chunk(fd,
+                                   (struct chunk_info *)d->r[i].size, 0);
+               }
+       }
+       snprintf(buf, sizeof(buf), "In use %zu\n", malloc_used);
+       write(fd, buf, strlen(buf));
+       snprintf(buf, sizeof(buf), "Guarded %zu\n", malloc_guarded);
+       write(fd, buf, strlen(buf));
+       dump_leaks(fd);
+       write(fd, "\n", 1);
+}
+
+void
+malloc_dump(int fd)
+{
+       int i;
+       void *p;
+       struct region_info *r;
+
+       for (i = 0; i < MALLOC_DELAYED_CHUNKS; i++) {
+               p = g_pool->delayed_chunks[i];
+               if (p == NULL)
+                       continue;
+               r = find(g_pool, p);
+               if (r == NULL) 
+                       wrterror("bogus pointer in malloc_dump", p);
+               free_bytes(g_pool, r, p);
+               g_pool->delayed_chunks[i] = NULL;
+       }
+       RB_INIT(&leakhead);
+       malloc_dump1(fd, g_pool);
+}
+
+static void
+malloc_exit(void)
+{
+       static const char q[] = "malloc() warning: Couldn't dump stats\n";
+       int save_errno = errno, fd;
+
+       fd = open("malloc.out", O_RDWR|O_APPEND);
+       if (fd != -1) {
+               malloc_dump(fd);
+               close(fd);
+       } else
+               write(STDERR_FILENO, q, sizeof(q) - 1);
+       errno = save_errno;
+}
+
+#endif /* MALLOC_STATS */

Reply via email to