On Thu, May 05, 2011 at 02:29:39PM +0200, Otto Moerbeek wrote:
> 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.
Updated diff. Kent R. Spillner spotted a glitch that caused a (ironly!)
memory leak in the reporting code,
-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 18:15:15 -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 (page == 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 */
