+static void
+mem_error (const char *format,
+ ...)
+{
+ const char *pname;
+ va_list args;
+ /* at least, put out "MEMORY-ERROR", in case we segfault during the rest of the function */
+ fputs ("\n***MEMORY-ERROR***: ", stderr);
+ pname = g_get_prgname();
+ fprintf (stderr, "%s[%ld]: GSlice: ", pname ? pname : "", (long)getpid());
+ va_start (args, format);
+ vfprintf (stderr, format, args);
+ va_end (args);
+ fputs ("\n", stderr);
+ abort();
+ _exit (1);
+}
+
+/* --- g-slice memory checker tree --- */
+typedef size_t SmcKType; /* key type */
+typedef size_t SmcVType; /* value type */
+typedef struct {
+ SmcKType key;
+ SmcVType value;
+} SmcEntry;
+static void smc_tree_insert (SmcKType key,
+ SmcVType value);
+static gboolean smc_tree_lookup (SmcKType key,
+ SmcVType *value_p);
+static gboolean smc_tree_remove (SmcKType key);
+
+
+/* --- g-slice memory checker implementation --- */
+static void
+smc_notify_alloc (void *pointer,
+ size_t size)
+{
+ size_t adress = (size_t) pointer;
+ if (pointer)
+ smc_tree_insert (adress, size);
+}
+
+#if 0
+static void
+smc_notify_ignore (void *pointer)
+{
+ size_t adress = (size_t) pointer;
+ if (pointer)
+ smc_tree_remove (adress);
+}
+#endif
+
+static int
+smc_notify_free (void *pointer,
+ size_t size)
+{
+ size_t adress = (size_t) pointer;
+ SmcVType real_size;
+ gboolean found_one;
+
+ if (!pointer)
+ return 1; /* ignore */
+ found_one = smc_tree_lookup (adress, &real_size);
+ if (!found_one)
+ {
+ fprintf (stderr, "GSlice: MemChecker: attempt to release non-allocated block: %p size=%" G_GSIZE_FORMAT "\n", pointer, size);
+ return 0;
+ }
+ if (real_size != size && (real_size || size))
+ {
+ fprintf (stderr, "GSlice: MemChecker: attempt to release block with invalid size: %p size=%" G_GSIZE_FORMAT " invalid-size=%" G_GSIZE_FORMAT "\n", pointer, real_size, size);
+ return 0;
+ }
+ if (!smc_tree_remove (adress))
+ {
+ fprintf (stderr, "GSlice: MemChecker: attempt to release non-allocated block: %p size=%" G_GSIZE_FORMAT "\n", pointer, size);
+ return 0;
+ }
+ return 1; /* all fine */
+}
+
+/* --- g-slice memory checker tree implementation --- */
+#define SMC_TRUNK_COUNT (4093 /* 16381 */) /* prime, to distribute trunk collisions (big, allocated just once) */
+#define SMC_BRANCH_COUNT (511) /* prime, to distribute branch collisions */
+#define SMC_TRUNK_EXTENT (SMC_BRANCH_COUNT * 2039) /* key address space per trunk, should distribute uniformly across BRANCH_COUNT */
+#define SMC_TRUNK_HASH(k) ((k / SMC_TRUNK_EXTENT) % SMC_TRUNK_COUNT) /* generate new trunk hash per megabyte (roughly) */
+#define SMC_BRANCH_HASH(k) (k % SMC_BRANCH_COUNT)
+
+typedef struct {
+ SmcEntry *entries;
+ unsigned int n_entries;
+} SmcBranch;
+
+static SmcBranch **smc_tree_root = NULL;
+
+static void
+smc_tree_abort (int errval)
+{
+ const char *syserr = strerror (errval);
+ mem_error ("MemChecker: failure in debugging tree: %s", syserr);
+}
+
+static inline SmcEntry*
+smc_tree_branch_grow_L (SmcBranch *branch,
+ unsigned int index)
+{
+ unsigned int old_size = branch->n_entries * sizeof (branch->entries[0]);
+ unsigned int new_size = old_size + sizeof (branch->entries[0]);
+ SmcEntry *entry;
+ mem_assert (index <= branch->n_entries);
+ branch->entries = (SmcEntry*) realloc (branch->entries, new_size);
+ if (!branch->entries)
+ smc_tree_abort (errno);
+ entry = branch->entries + index;
+ memmove (entry + 1, entry, (branch->n_entries - index) * sizeof (entry[0]));
+ branch->n_entries += 1;
+ return entry;
+}
+
+static inline SmcEntry*
+smc_tree_branch_lookup_nearest_L (SmcBranch *branch,
+ SmcKType key)
+{
+ unsigned int n_nodes = branch->n_entries, offs = 0;
+ SmcEntry *check = branch->entries;
+ int cmp = 0;
+ while (offs < n_nodes)
+ {
+ unsigned int i = (offs + n_nodes) >> 1;
+ check = branch->entries + i;
+ cmp = key < check->key ? -1 : key != check->key;
+ if (cmp == 0)
+ return check; /* return exact match */
+ else if (cmp < 0)
+ n_nodes = i;
+ else /* (cmp > 0) */
+ offs = i + 1;
+ }
+ /* check points at last mismatch, cmp > 0 indicates greater key */
+ return cmp > 0 ? check + 1 : check; /* return insertion position for inexact match */
+}
+
+static void
+smc_tree_insert (SmcKType key,
+ SmcVType value)
+{
+ unsigned int ix0, ix1;
+ SmcEntry *entry;
+
+ g_mutex_lock (&smc_tree_mutex);
+ ix0 = SMC_TRUNK_HASH (key);
+ ix1 = SMC_BRANCH_HASH (key);
+ if (!smc_tree_root)
+ {
+ smc_tree_root = calloc (SMC_TRUNK_COUNT, sizeof (smc_tree_root[0]));
+ if (!smc_tree_root)
+ smc_tree_abort (errno);
+ }
+ if (!smc_tree_root[ix0])
+ {
+ smc_tree_root[ix0] = calloc (SMC_BRANCH_COUNT, sizeof (smc_tree_root[0][0]));
+ if (!smc_tree_root[ix0])
+ smc_tree_abort (errno);
+ }
+ entry = smc_tree_branch_lookup_nearest_L (&smc_tree_root[ix0][ix1], key);
+ if (!entry || /* need create */
+ entry >= smc_tree_root[ix0][ix1].entries + smc_tree_root[ix0][ix1].n_entries || /* need append */
+ entry->key != key) /* need insert */
+ entry = smc_tree_branch_grow_L (&smc_tree_root[ix0][ix1], entry - smc_tree_root[ix0][ix1].entries);
+ entry->key = key;
+ entry->value = value;
+ g_mutex_unlock (&smc_tree_mutex);
+}
+
+static gboolean
+smc_tree_lookup (SmcKType key,
+ SmcVType *value_p)
+{
+ SmcEntry *entry = NULL;
+ unsigned int ix0 = SMC_TRUNK_HASH (key), ix1 = SMC_BRANCH_HASH (key);
+ gboolean found_one = FALSE;
+ *value_p = 0;
+ g_mutex_lock (&smc_tree_mutex);
+ if (smc_tree_root && smc_tree_root[ix0])
+ {
+ entry = smc_tree_branch_lookup_nearest_L (&smc_tree_root[ix0][ix1], key);
+ if (entry &&
+ entry < smc_tree_root[ix0][ix1].entries + smc_tree_root[ix0][ix1].n_entries &&
+ entry->key == key)
+ {
+ found_one = TRUE;
+ *value_p = entry->value;
+ }
+ }
+ g_mutex_unlock (&smc_tree_mutex);
+ return found_one;
+}
+
+static gboolean
+smc_tree_remove (SmcKType key)
+{
+ unsigned int ix0 = SMC_TRUNK_HASH (key), ix1 = SMC_BRANCH_HASH (key);
+ gboolean found_one = FALSE;
+ g_mutex_lock (&smc_tree_mutex);
+ if (smc_tree_root && smc_tree_root[ix0])
+ {
+ SmcEntry *entry = smc_tree_branch_lookup_nearest_L (&smc_tree_root[ix0][ix1], key);
+ if (entry &&
+ entry < smc_tree_root[ix0][ix1].entries + smc_tree_root[ix0][ix1].n_entries &&
+ entry->key == key)
+ {
+ unsigned int i = entry - smc_tree_root[ix0][ix1].entries;
+ smc_tree_root[ix0][ix1].n_entries -= 1;
+ memmove (entry, entry + 1, (smc_tree_root[ix0][ix1].n_entries - i) * sizeof (entry[0]));
+ if (!smc_tree_root[ix0][ix1].n_entries)
+ {
+ /* avoid useless pressure on the memory system */
+ free (smc_tree_root[ix0][ix1].entries);
+ smc_tree_root[ix0][ix1].entries = NULL;
+ }
+ found_one = TRUE;
+ }
+ }
+ g_mutex_unlock (&smc_tree_mutex);
+ return found_one;
+}
+
+#ifdef G_ENABLE_DEBUG
+void
+g_slice_debug_tree_statistics (void)
+{
+ g_mutex_lock (&smc_tree_mutex);
+ if (smc_tree_root)
+ {
+ unsigned int i, j, t = 0, o = 0, b = 0, su = 0, ex = 0, en = 4294967295u;
+ double tf, bf;
+ for (i = 0; i < SMC_TRUNK_COUNT; i++)
+ if (smc_tree_root[i])
+ {
+ t++;
+ for (j = 0; j < SMC_BRANCH_COUNT; j++)
+ if (smc_tree_root[i][j].n_entries)
+ {
+ b++;
+ su += smc_tree_root[i][j].n_entries;
+ en = MIN (en, smc_tree_root[i][j].n_entries);
+ ex = MAX (ex, smc_tree_root[i][j].n_entries);
+ }
+ else if (smc_tree_root[i][j].entries)
+ o++; /* formerly used, now empty */
+ }
+ en = b ? en : 0;
+ tf = MAX (t, 1.0); /* max(1) to be a valid divisor */
+ bf = MAX (b, 1.0); /* max(1) to be a valid divisor */
+ fprintf (stderr, "GSlice: MemChecker: %u trunks, %u branches, %u old branches\n", t, b, o);
+ fprintf (stderr, "GSlice: MemChecker: %f branches per trunk, %.2f%% utilization\n",
+ b / tf,
+ 100.0 - (SMC_BRANCH_COUNT - b / tf) / (0.01 * SMC_BRANCH_COUNT));
+ fprintf (stderr, "GSlice: MemChecker: %f entries per branch, %u minimum, %u maximum\n",
+ su / bf, en, ex);
+ }
+ else
+ fprintf (stderr, "GSlice: MemChecker: root=NULL\n");
+ g_mutex_unlock (&smc_tree_mutex);
+
+ /* sample statistics (beast + GSLice + 24h scripted core & GUI activity):
+ * PID %CPU %MEM VSZ RSS COMMAND
+ * 8887 30.3 45.8 456068 414856 beast-0.7.1 empty.bse
+ * $ cat /proc/8887/statm # total-program-size resident-set-size shared-pages text/code data/stack library dirty-pages
+ * 114017 103714 2354 344 0 108676 0
+ * $ cat /proc/8887/status
+ * Name: beast-0.7.1
+ * VmSize: 456068 kB
+ * VmLck: 0 kB
+ * VmRSS: 414856 kB
+ * VmData: 434620 kB
+ * VmStk: 84 kB
+ * VmExe: 1376 kB
+ * VmLib: 13036 kB
+ * VmPTE: 456 kB
+ * Threads: 3
+ * (gdb) print g_slice_debug_tree_statistics ()
+ * GSlice: MemChecker: 422 trunks, 213068 branches, 0 old branches
+ * GSlice: MemChecker: 504.900474 branches per trunk, 98.81% utilization
+ * GSlice: MemChecker: 4.965039 entries per branch, 1 minimum, 37 maximum
+ */
+}
+#endif /* G_ENABLE_DEBUG */