libbacktrace patch committed: Only keep 16 entries on free list

[Ian Lance Taylor]

PR 68239 points out that libbacktrace can sometimes take a long time
scanning the list of free memory blocks looking for one that is large
enough.  Since the libbacktrace memory allocator does not have to be
perfect in practice, only keep the 16 largest entries on the free
list.  Bootstrapped and ran libbacktrace and libgo tests on
x86_64-pc-linux-gnu.  Committed to mainline.

Ian

2018-01-24  Ian Lance Taylor  <i...@golang.org>

PR other/68239
* mmap.c (backtrace_free_locked): Don't put more than 16 entries
on the free list.

Index: mmap.c
===================================================================
--- mmap.c      (revision 257038)
+++ mmap.c      (working copy)
@@ -69,11 +69,33 @@ struct backtrace_freelist_struct
 static void
 backtrace_free_locked (struct backtrace_state *state, void *addr, size_t size)
 {
-  /* Just leak small blocks.  We don't have to be perfect.  */
+  /* Just leak small blocks.  We don't have to be perfect.  Don't put
+     more than 16 entries on the free list, to avoid wasting time
+     searching when allocating a block.  If we have more than 16
+     entries, leak the smallest entry.  */
+
   if (size >= sizeof (struct backtrace_freelist_struct))
     {
+      size_t c;
+      struct backtrace_freelist_struct **ppsmall;
+      struct backtrace_freelist_struct **pp;
       struct backtrace_freelist_struct *p;
 
+      c = 0;
+      ppsmall = NULL;
+      for (pp = &state->freelist; *pp != NULL; pp = &(*pp)->next)
+       {
+         if (ppsmall == NULL || (*pp)->size < (*ppsmall)->size)
+           ppsmall = pp;
+         ++c;
+       }
+      if (c >= 16)
+       {
+         if (size <= (*ppsmall)->size)
+           return;
+         *ppsmall = (*ppsmall)->next;
+       }
+
       p = (struct backtrace_freelist_struct *) addr;
       p->next = state->freelist;
       p->size = size;